Discrete Ricci Curvature

Analyze graph geometry using Forman-Ricci and Ollivier-Ricci curvature.

Discrete Ricci curvature extends the concept of curvature from differential geometry to graphs. It reveals the local "shape" of the graph around each edge, distinguishing between clustered regions, branching points, and linear paths.

Geometric Intuition

In differential geometry, curvature measures how space bends:

Forman-Ricci Curvature

Forman-Ricci curvature is a combinatorial approximation based on the graph's local structure. It's fast to compute, making it suitable for large graphs.

Formula

For an edge e = (u, v):

$F(e) = 4 - \deg(u) - \deg(v) + 3 \cdot |T(e)|$

Where:

• deg(u), deg(v) are the degrees of the endpoint nodes
• T(e) is the set of triangles containing edge e

Simplified Formula

Without triangle counting:

$F(e) = 4 - \deg(u) - \deg(v)$

Complexity

O(E) — very fast, linear in the number of edges

Interpretation

Example

For an edge between two nodes with degrees 3 and 4:

$F(e) = 4 - 3 - 4 = -3$

This negative curvature indicates a branching structure.

Ollivier-Ricci Curvature

Ollivier-Ricci curvature uses optimal transport (Wasserstein distance) to measure how probability mass spreads from one node to another.

Formula

$\kappa(x, y) = 1 - \frac{W_1(\mu_x, \mu_y)}{d(x, y)}$

Where:

• W₁ is the Wasserstein-1 distance (Earth Mover's Distance)
• μₓ is the probability measure around node x
• d(x, y) is the graph distance between x and y

Probability Measure

For a node x, the probability distribution μₓ is defined as:

• μₓ(x) = α (probability of staying at x)
• μₓ(v) = (1 - α) / deg(x) for neighbors v ∈ N(x)
• μₓ(v) = 0 otherwise

Where α is the "laziness" parameter.

Parameters

Complexity

O(V × E) — slower but more accurate than Forman

Interpretation

Wasserstein Distance

The Wasserstein distance measures the cost of "transporting" one probability distribution to another.

Formula

$W_p(\mu, \nu) = \left( \inf_{\gamma \in \Gamma(\mu, \nu)} \int d(x, y)^p \, d\gamma(x, y) \right)^{1/p}$

Where:

• Γ(μ, ν) is the set of all couplings (transport plans)
• d(x, y) is the ground distance

For p = 1, this is the Earth Mover's Distance (EMD).

Implementation

Astrolabe uses the POT (Python Optimal Transport) library, with scipy as a fallback.

Curvature Statistics

Astrolabe computes aggregate statistics across all edges:

Global Interpretation

Node Curvature

Node curvature is derived by averaging the curvatures of incident edges:

$\kappa(v) = \frac{1}{\deg(v)} \sum_{e \ni v} \kappa(e)$

Interpretation in Lean

Choosing Between Forman and Ollivier

Practical Application

Example Workflow

1. Quick scan: Run Forman-Ricci on the full graph
2. Identify hotspots: Find highly negative (bridge) and positive (cluster) regions
3. Detailed analysis: Run Ollivier-Ricci on interesting subgraphs
4. Interpret: Map curvature to mathematical structure

In Lean Codebases

API Endpoints

GET /api/project/analysis/curvature    # Forman-Ricci (default, fast)

Returns:

• edge_curvatures: Edge → source, target, curvature
• node_curvatures: Node → average curvature
• statistics: Aggregate stats
• interpretation: Overall structure assessment

For Ollivier-Ricci, the endpoint accepts additional parameters:

GET /api/project/analysis/curvature?method=ollivier&alpha=0.5