API Reference

Main Function

orc_bound.residual_shell_ricci_approximation(graph: Graph, num_nodes: int, k: int = 1, alpha_lazy: float = 0.0, l_shell: int = 3, rbar_mode: str = 'local-max', tol: float = 1e-12, symmetric: bool = False, n_jobs: int | None = None) → csr_matrix[source]

Compute lower bounds on Ollivier-Ricci Curvature (ORC) via residual-shell W1 upper bounds.

The ORC lower bound for an edge (u, v) is:

kappa_lb(u, v) = 1 - W_1(mu_u, mu_v) / dist(u, v)

where mu_u is the k-hop lazy random walk measure at u and W_1 is approximated using the residual-shell bucket matching algorithm.

Parameters:

  • graph (nx.Graph) – Input graph.

  • num_nodes (int) – Number of nodes. Must match len(graph.nodes()).

  • k (int, default=1) – Number of random walk steps (k-hop neighborhood). Higher k gives a more global measure.

  • alpha_lazy (float, default=0.0) – Lazy mixing parameter in [0, 1]. Controls the weight of the stationary distribution.

  • l_shell (int, default=3) – Maximum shell distance for bucket matching. The effective l is min(l_shell, 2*k+1).

  • rbar_mode (str, default="local-max") – Method for residual distance estimation. Options: "local-max", "global".

  • tol (float, default=1e-12) – Numerical tolerance for mass pruning.

  • symmetric (bool, default=False) – If True, populate both (u,v) and (v,u) entries.

  • n_jobs (int or None, default=None) – Number of parallel workers for edge curvature computation. - None or 0: use all available CPU cores. - Positive int: use exactly that many workers. - -1: use all cores minus one.

Returns:

curvature_matrix – Sparse matrix of shape (num_nodes, num_nodes). Entry (i, j) is the ORC lower bound for the edge from node i to node j. Non-edge entries are zero.

Return type:

scipy.sparse.csr_matrix

Notes

The distance cutoff is automatically set to 2*k + 1, which is the maximum possible distance between any two points in the supports of mu_u^(k) and mu_v^(k) when both are centered at u and v respectively.

Multi-threading: Each edge’s curvature is computed independently, so the computation parallelizes naturally across edges.

Examples

>>> import networkx as nx
>>> from orc_bound import residual_shell_ricci_approximation
>>> G = nx.watts_strogatz_graph(80, 6, 0.2, seed=0)
>>> C = residual_shell_ricci_approximation(G, G.number_of_nodes(), k=2)
>>> C.nnz  # number of non-zero entries (edges)
240

Parallel execution:

>>> C = residual_shell_ricci_approximation(G, G.number_of_nodes(), k=5, n_jobs=8)

Core Functions

orc_bound.build_lazy_measures_k(G: Graph, alpha_lazy: float, k: int) → Dict[int, Dict[int, float]][source]

Build k-hop lazy random walk probability measures for all nodes.

For each node x, the measure is:

mu_x^(k)[y] = alpha_lazy * delta_x(y) + (1 - alpha_lazy) * P^k(x, y)

Parameters:

  • G (nx.Graph) – Input graph.

  • alpha_lazy (float) – Lazy mixing parameter in [0, 1]. Higher values weight the stationary distribution more heavily.

  • k (int) – Number of random walk steps (k-hop neighborhood).

Returns:

mu_dict – Dictionary mapping each node to its mass dictionary, where keys are neighbor nodes and values are probabilities.

Return type:

Dict[int, Dict[int, float]]

Examples

>>> import networkx as nx
>>> G = nx.path_graph(5)
>>> mu = build_lazy_measures_k(G, alpha_lazy=0.0, k=2)
>>> abs(sum(mu[0].values()) - 1.0) < 1e-10
True
orc_bound.all_pairs_shortest_path_matrix_cutoff(G: Graph, cutoff: int) → Tuple[List[int], Dict[int, int], ndarray][source]

Compute the all-pairs shortest path distance matrix up to a cutoff.

Distances larger than the cutoff are stored as np.inf. This is significantly faster than full APSP when the cutoff is small relative to the graph diameter.

Parameters:

  • G (nx.Graph) – Input graph.

  • cutoff (int) – Maximum distance to compute. Distances beyond this are inf.

Returns:

  • nodes (List[int]) – List of node IDs in the same order as the index map.

  • idx (Dict[int, int]) – Mapping from node ID to matrix row/column index.

  • D (np.ndarray) – Distance matrix of shape (n, n) where n = |nodes|. D[i, j] is the shortest path distance from nodes[i] to nodes[j], or np.inf if the distance exceeds the cutoff.

Examples

>>> import networkx as nx
>>> G = nx.path_graph(5)
>>> nodes, idx, D = all_pairs_shortest_path_matrix_cutoff(G, cutoff=3)
>>> D[idx[0], idx[4]]
4.0
>>> D[idx[0], idx[2]]
2.0
orc_bound.residual_shell_upper_bound(mu_x: Dict[int, float], mu_y: Dict[int, float], D: ndarray, idx: Dict[int, int], l: int = 2, tol: float = 1e-12, rbar_mode: str = 'local-max') → Tuple[float, ndarray, float, float][source]

Compute the residual-shell upper bound on W_1(mu_x, mu_y).

The algorithm performs bucket-based matching between the supports of the two measures, grouping pairs by their graph distance.

Parameters:

  • mu_x (Dict[int, float]) – Measure at node x, as a dict of {node: mass}.

  • mu_y (Dict[int, float]) – Measure at node y, as a dict of {node: mass}.

  • D (np.ndarray) – Precomputed distance matrix from all_pairs_shortest_path_matrix_cutoff().

  • idx (Dict[int, int]) – Node-to-index mapping.

  • l (int, default=2) – Maximum shell distance to consider. Pairs at distance > l are assigned to the residual shell.

  • tol (float, default=1e-12) – Pruning threshold. Masses below this are ignored.

  • rbar_mode (str, default="local-max") – How to compute the residual distance rbar: - "local-max": max distance between residual supports. - "global": max finite distance in the matrix.

Returns:

  • ub (float) – Upper bound on the 1-Wasserstein distance.

  • m_r (np.ndarray) – Mass assigned to each bucket r=0..l.

  • residual_mass (float) – Remaining unmatched mass.

  • rbar (float) – Effective residual distance.

Raises:

RuntimeError – If no finite residual distances are found (cutoff too small).

Examples

>>> import numpy as np
>>> D = np.array([[0., 1., 2.],
...               [1., 0., 1.],
...               [2., 1., 0.]], dtype=float)
>>> idx = {0: 0, 1: 1, 2: 2}
>>> mu_x = {0: 0.5, 1: 0.5}
>>> mu_y = {1: 0.5, 2: 0.5}
>>> ub, m_r, Rl, rbar = residual_shell_upper_bound(mu_x, mu_y, D, idx, l=2)
>>> ub >= 0
True

Return Type

All functions that compute a curvature matrix return a scipy.sparse.csr_matrix of shape (num_nodes, num_nodes). Non-zero entries correspond to graph edges; their values are the ORC lower bounds.

from scipy.sparse import csr_matrix
C = residual_shell_ricci_approximation(G, G.number_of_nodes(), k=2)

# Average curvature over all edges
avg_curv = C.sum() / C.nnz

# Per-edge curvature: iterate over non-zero entries
for i, j, v in zip(C.row, C.col, C.data):
    print(f"Edge ({i}, {j}): κ_lb = {v:.4f}")

# Access a specific edge
i, j = 0, 1
kappa_ij = C[i, j]

Utility Functions

orc_bound.utils.parallel._cpu_count(n_jobs: int | None) → int[source]

Resolve the number of workers for parallel execution.

Parameters:

n_jobs (int or None) –

  • None or 0: use all CPUs.

  • Positive int: use exactly that many workers.

  • -1: use all CPUs minus one.

Returns:

Number of workers to use (always at least 1).

Return type:

int

orc_bound.utils.search.search_orc_literature(query: str, num_results: int = 10, serpapi_key: str | None = None, lang: str = 'en') → List[Dict[str, Any]][source]

Search for ORC-related literature via Google Scholar through SerpAPI.

Parameters:

  • query (str) – Search query string. Example: "optimal rank canonical graph curvature".

  • num_results (int, default=10) – Number of results to return (max 100).

  • serpapi_key (str or None) – SerpAPI key. If None, reads from the SERPAPI_KEY environment variable.

  • lang (str, default="en") – Language code for results (e.g., "en", "zh").

Returns:

List of search results. Each dict contains: - title: Paper title. - link: URL to the paper. - snippet: Short abstract or description. - position: Rank in results.

Return type:

List[Dict[str, Any]]

Raises:

  • EnvironmentError – If the SerpAPI key is not available.

  • ImportError – If the google-search-results package is not installed. Install with: pip install google-search-results

  • RuntimeError – If the SerpAPI request fails.

Examples

>>> results = search_orc_literature(
...     query="Ricci curvature graph networks",
...     num_results=5,
...     serpapi_key="your-key-here",
... )
>>> for r in results:
...     print(r["title"])
orc_bound.utils.search.search_general(query: str, num_results: int = 10, serpapi_key: str | None = None, engine: str = 'google') → List[Dict[str, Any]][source]

General web search via SerpAPI.

Parameters:

  • query (str) – Search query.

  • num_results (int, default=10) – Number of results (max 100).

  • serpapi_key (str or None) – SerpAPI key. If None, reads from SERPAPI_KEY env var.

  • engine (str, default="google") – Search engine: "google", "bing", "duckduckgo", etc.

Returns:

List of results with title, link, and snippet.

Return type:

List[Dict[str, Any]]

Examples

>>> results = search_general(
...     "residual shell Ricci curvature graph",
...     num_results=5,
...     serpapi_key="your-key-here",
... )

Parameter Reference

Parameter

Default

Description

graph

—

Input NetworkX graph. Must be unweighted.

num_nodes

—

Number of nodes. Must equal len(graph.nodes()).

k

1

Number of random walk steps (k-hop neighborhood). Higher k gives more global measure.

alpha_lazy

0.0

Lazy mixing parameter in [0, 1]. 0 = pure random walk; 1 = trivial delta measure.

l_shell

3

Maximum shell distance for bucket matching. Effective value is min(l_shell, 2*k+1).

rbar_mode

"local-max"

Residual distance mode: "local-max" or "global".

tol

1e-12

Pruning threshold. Masses below this are ignored.

symmetric

False

If True, populate both (u,v) and (v,u) entries.

n_jobs

None

Number of parallel workers. None/0 = all cores; -1 = all minus one.