Picture a university email network where a research group emails constantly among themselves and rarely emails anyone outside the lab. Somewhere in that graph sits a single email, sent maybe once a semester, that connects the lab to a different department entirely. That one thin connection is doing something structurally different from every other edge around it, and a paper out of Harvard, the University of Virginia, and the Center for Systems Biology Dresden argues that ordinary graph theory has been measuring the wrong thing when it tries to spot that difference. The paper proposes measuring the curvature of every edge instead, borrowing an idea from differential geometry that was never meant for graphs at all, and turning it into a working algorithm.
Key points
- The paper by Yu Tian, Zachary Lubberts, and Melanie Weber builds a single framework around two competing notions of discrete curvature, Ollivier’s and Forman’s, and shows exactly where each one wins or loses for graph clustering.
- It extends curvature based clustering beyond the usual case where every node belongs to one community, adding the first curvature method for overlapping, mixed membership communities by working on the graph’s line graph instead of the graph itself.
- It replaces the expensive optimal transport calculation behind Ollivier curvature with a combinatorial approximation, cutting the cost from roughly quadratic in node degree down to linear.
- It proves formulas connecting the curvature of a graph to the curvature of its line graph, so in many cases the line graph never has to be built at all.
- Across synthetic stochastic block models and four real networks, from academic coauthorship data to primate brain connectomes, the curvature based method matches or beats Louvain and spectral clustering, with its biggest edge appearing right at the point where communities become hard to detect.
What problem is this paper actually solving
Community detection sounds like a solved problem until you try to do it on a graph where the ground truth is not obvious. Louvain optimizes modularity by greedily merging nodes into groups. Spectral clustering looks at the eigenvectors of the graph Laplacian and asks you to already know how many clusters you expect. Both are fast, both are widely used, and both quietly assume every node belongs to exactly one community. That assumption breaks constantly in practice. A person belongs to a family circle and a work circle. A protein plays one role in a metabolic pathway and a different role in a signaling cascade. An author publishes in one venue this year and a different venue the next. The mixed membership stochastic block model exists precisely because real relational data refuses to sort itself into tidy, non overlapping boxes.
Curvature based clustering is a smaller subfield that tries to sidestep the partition assumption from a different angle. The intuition, first pushed by researchers like Ni, Sia, and Weber in earlier work, is that edges connecting two different communities tend to be geometrically flat or even negatively curved, while edges inside a tight community tend to be positively curved. Stretch that idea over time using something called Ricci flow, and the bridges between communities become easier and easier to spot as the flow runs, because their weight grows while everything else shrinks. The trouble is that nobody had worked out how to apply this to overlapping communities, and the two main ways of computing curvature on a graph disagree with each other often enough that picking one felt arbitrary. This paper tackles both gaps at once.
A short primer on curvature for people who last saw a manifold in college
Curvature in the classical sense describes how a space bends. On a sphere, nearby geodesics converge. On a saddle, they spread apart. Ricci curvature specifically measures how the volume of a small ball grows compared to flat Euclidean space, and a positive value means nearby points stay close together as you move, roughly the geometric signature of a tightly packed neighborhood. Graphs obviously are not smooth manifolds, so two separate camps of researchers built discrete stand ins for the idea, and both show up in this paper.
Two ways to discretize curvature
Ollivier curvature, introduced by Yann Ollivier, treats the neighborhood of each node as a probability distribution and asks how expensive it is to move the probability mass from one node’s neighborhood to an adjacent node’s neighborhood, using optimal transport. If the two neighborhoods overlap heavily, moving mass is cheap and the curvature is high. If the neighborhoods barely overlap, moving mass is expensive and the curvature drops toward zero or below. The transport cost itself is the Wasserstein distance familiar from generative modeling work, which is a nice reminder that this idea from geometry keeps resurfacing across machine learning in places you would not expect.
Forman curvature, introduced by Robin Forman, comes from an entirely different direction, a discrete version of the Bochner Weitzenbock identity from spectral geometry. In its plain unweighted form it reduces to something almost embarrassingly simple, four minus the degrees of the two endpoints of an edge. A bridge edge connecting two high degree hub nodes gets punished hard. An edge deep inside a sparse community barely moves. The appeal is speed. Forman curvature is a handful of arithmetic operations per edge, no optimization problem required, while Ollivier curvature in its original form needs the Hungarian algorithm or Sinkhorn iterations, both of which get expensive fast as node degree grows.
Why this matters beyond graph theory papers
Discrete curvature already shows up in biology, where negatively curved edges in protein networks tend to mark functional boundaries, in finance, where curvature has been used as an early warning signal for market fragility, and in neuroscience, where curvature patterns in brain connectomes correlate with disorders like autism. A cheaper, more reliable curvature computation is not just a theory improvement, it lowers the barrier for anyone applying this family of methods to a new dataset.
The core method, clustering by letting curvature reshape the graph
The authors organize every prior curvature based clustering algorithm they could find into one template, which they call Algorithm 1. Start with a graph, weighted or not. Compute the curvature of every edge. Update each edge weight using a Ricci flow rule that shrinks positively curved edges and grows negatively curved ones. Renormalize so the total weight stays comparable across iterations. Repeat for a fixed number of rounds, typically ten in their experiments. Then sweep through a series of cutoff thresholds, cut every edge whose weight sits above the threshold, and check the modularity of whatever connected components fall out. Keep the threshold that produces the best modularity score.
What is genuinely useful here is not the individual steps, most of which had appeared somewhere in prior work already, it is that the paper nails down exactly which choices matter. The step size for the flow, the number of iterations, and especially the spacing of the cutoff thresholds all have to be tuned differently depending on whether you are using Ollivier or Forman curvature, because the two produce wildly different weight distributions after the flow runs. Ollivier curvature stays roughly bounded. Forman curvature, especially the richer version that accounts for triangles, can blow up into a heavy tailed distribution where a handful of edges dominate everything else. The paper is refreshingly specific about this rather than hand waving it away, prescribing an adaptive step size tied to the maximum curvature magnitude seen in a given round.
Ollivier curvature of an edge, where \(W_1\) is the Wasserstein 1 distance between the neighborhood measures of the two endpoints and \(d_G\) is the shortest path distance between them.
The Ricci flow update rule. Step size \(\nu\) controls how aggressively curvature reshapes the edge weights each round.
Making Ollivier curvature affordable
The bottleneck in every prior curvature based clustering paper was the cost of solving the optimal transport problem for every single edge. Exact solutions run through the Hungarian algorithm at roughly cubic cost in node degree, and the popular Sinkhorn approximation still runs quadratic. On a graph with tens of thousands of edges and hub nodes with high degree, that adds up fast, which is why the authors report runs taking over a day on some real networks in their experiments.
Their fix leans on a classical result by Jost and Liu bounding Ollivier curvature above and below using nothing but triangle counts and node degrees, quantities you can compute in linear time with no optimization involved. The catch is those bounds were only proven for unweighted graphs, and Ricci flow immediately turns every graph into a weighted one after the first iteration. So the paper derives new upper and lower bounds for the weighted case, built from a dual description of the Wasserstein distance using Lipschitz functions rather than transport plans, and then approximates the true curvature as the midpoint between the two bounds. Figure 6 in the paper shows this approximation tracking almost exactly with the exact optimal transport solution across both stochastic block models and random geometric graphs, which is the kind of validation that makes an approximation trustworthy rather than just convenient.
From node clustering to edge clustering with line graphs
The more surprising contribution is the mixed membership extension, and it hinges on an old idea from graph theory called the line graph. Take a graph and build a new graph where every edge of the original becomes a node, and two of these new nodes are connected if their corresponding original edges shared an endpoint. It sounds like an abstract trick until you see why it solves the overlapping communities problem so cleanly. A node that belongs to two communities has edges pointing into both. Those edges cannot form a bridge in the original graph because there is no single boundary node to cut, the community structure genuinely overlaps at that node. But in the line graph, each of that node’s edges becomes its own separate vertex, and the edges among those new vertices now do form a bridge, one for each community the original node touched. The overlap gets untangled simply by looking at connectivity between edges instead of connectivity between nodes.
Running Algorithm 1 on the line graph instead of the original graph recovers mixed membership labels by assigning each original node a soft label built from how its incident edges got clustered. The obvious problem is that line graphs get big fast, since a node with degree d in the original graph turns into something close to a clique of size d in the line graph, so building it explicitly for a large or dense network becomes its own bottleneck. The paper’s answer is a set of theorems relating curvature in a graph directly to curvature in its line graph, expressed purely in terms of degrees and triangle counts in the original graph. For the lower bound on line graph curvature this works cleanly and the line graph never has to be constructed. The upper bound still needs some line graph information, though the authors show that simply using the trivial bound of one in its place barely hurts accuracy while meaningfully cutting runtime, a nice example of a paper finding the actual point of diminishing returns rather than chasing an exact result nobody needs.
What the experiments actually show
The benchmarking is thorough, running planted stochastic block models and mixed membership block models across a range of densities, alongside four real datasets, two DBLP coauthorship networks, two Facebook ego networks, and three animal brain connectomes from cats, roundworms, and macaques. Performance is measured with normalized mutual information against ground truth labels, plus an extended version of that metric for the overlapping case since standard NMI is not defined for soft memberships.
The headline result, at least for single membership clustering, is that the exact Ollivier curvature method reaches close to perfect recovery once the planted communities are reasonably separated, matching Louvain and spectral clustering in the easy regime and pulling ahead as the two block probabilities move closer together, which is exactly where community detection normally gets hard. The approximated version trades a bit of that accuracy for a large speed gain, and Forman curvature with triangle contributions works well once the graph is dense enough but falls apart in sparser graphs where triangles are scarce to begin with.
| Method | Sparse graphs near detectability threshold | Dense graphs | Relative cost |
|---|---|---|---|
| Exact Ollivier curvature | Strong, best in class | Strong | High, cubic or quadratic in degree |
| Approximated Ollivier curvature | Good, slightly behind exact | Comparable to exact | Low, linear in degree |
| Forman curvature with triangles | Weak | Comparable to Ollivier | Lowest, simple arithmetic |
| Louvain | Strong on easy cases, drops near threshold | Strong | Low, but needs many runs for stability |
| Spectral clustering | Strong, given true number of clusters | Strong | Moderate, needs cluster count as input |
The mixed membership results follow a similar pattern. Ollivier curvature on the line graph recovers overlapping community structure with extended NMI scores above 0.99 on most synthetic configurations, and on the real DBLP and Facebook networks it beats or ties every reference method except one Facebook network where the ground truth communities are unusually well described by plain modularity anyway. The Forman based approach on the line graph needs the richer version that also accounts for four sided faces, not just triangles, because a triangles only version turns out to depend almost entirely on raw node degree and loses most of its ability to separate community edges from bridge edges once the graph gets dense.
A number worth sitting with
On one real dataset, the Facebook ego network the authors call FB2, computing exact Ollivier curvature with Sinkhorn approximation took roughly ninety two minutes when the method was allowed access to a much larger memory allocation, and dropped to about forty two minutes using the paper’s combinatorial approximation. That is the difference between a method you can iterate on and one you queue overnight.
Where this fits and where it genuinely does not
It is worth being direct about something here. This is not a graph neural network paper. There is no learned embedding, no message passing, no gradient descent anywhere in the pipeline. Every curvature value and every clustering decision comes from closed form combinatorics or classical optimal transport, run once, not learned from data. If you came here expecting a trainable graph model, this is a different animal, closer to spectral graph theory than to representation learning. What earns it a place in a graph learning discussion anyway is that it operates on exactly the same objects, node embeddings, adjacency structure, and community labels, that graph neural networks are so often trained to predict, and it does so with none of the data hunger or training instability that comes with a learned model. For teams working on small or medium graphs where labeled examples are scarce, an unsupervised geometric method that needs zero training data is a genuinely different tool in the same toolbox, not a competitor trying to win the same benchmark.
There is also a real methodological question the paper raises without fully resolving, whether curvature is actually a better signal than modularity itself, given that the algorithm ultimately picks its cutoff threshold by maximizing modularity anyway. The authors are honest about this tension, noting that curvature seems to add the most value in exactly the regime where modularity based methods like Louvain start to struggle, near the detectability threshold, rather than replacing modularity as the underlying objective everywhere.
Where the method still struggles
The paper does not hide its rough edges, and neither should this analysis. Exact Ollivier curvature remains expensive enough that the authors themselves needed a specialized compute cluster and, in one case, two hundred fifty gigabytes of memory for a single dataset run. The approximation helps enormously but is still slower than Forman curvature or Louvain in absolute terms. Several key hyperparameters, including the number of Ricci flow iterations and the spacing of cutoff thresholds, are chosen by heuristic rather than derived from theory, and the paper’s own experiments show these choices interact with each other in ways that are not fully mapped out. The comparison against spectral clustering also carries an acknowledged asymmetry, since one strong spectral baseline gets to search over the true number of clusters as part of its grid search, an advantage the curvature based method never receives because it does not need to know the cluster count in advance. Finally, the whole framework as presented only handles undirected graphs, so anything involving directed relationships, citation graphs, follower networks, transaction flows, would need a nontrivial extension before this becomes directly usable.
Limitations worth flagging before you build on this
Beyond the computational caveats above, the theoretical guarantees in the paper, including the asymptotic Ricci flow proofs in the appendix, are established on a specific stylized family of graphs built from complete subgraphs glued together, not on arbitrary real world topologies. The real world evaluation is limited to four networks plus three brain connectomes, small by the standards of modern graph learning benchmarks, and the ground truth labels for the Facebook and DBLP data come from metadata proxies like friend lists and publication venues rather than any verified underlying community structure. Treat the strong NMI numbers as evidence the method is promising, not as proof it generalizes to every graph you might throw at it.
Conclusion
What this paper accomplishes, stripped of the mathematics, is turning a genuinely elegant idea, that community boundaries have a measurable geometric signature, into something a practitioner could actually run without a supercomputer. Curvature based clustering existed before this work, but it existed as a scattered set of papers each committed to one curvature notion, each vague about hyperparameters, and each stuck on the assumption that every node belongs to exactly one group. This paper collects those threads into one framework, is explicit about the tradeoffs between the two main curvature notions, and for the first time gives curvature based methods a real answer for overlapping community structure.
The conceptual move that makes the mixed membership extension possible, shifting the entire problem onto the line graph, is the kind of idea that reads as obvious in hindsight and clearly was not obvious to the field before now. Bridges between overlapping communities cannot exist in the original graph by definition, since the communities overlap at a shared node rather than separating cleanly, but the dual representation resurrects exactly the bridge structure the algorithm needs. That is a genuinely transferable insight, not tied to curvature specifically, and it is easy to imagine other graph algorithms built around bridge detection borrowing the same trick.
Whether this travels well outside the settings tested here is the open question. Social networks, coauthorship graphs, and brain connectomes all share a certain density and a certain homophily assumption, where similar nodes really do connect more than dissimilar ones. Sparser, noisier real world graphs, recommendation graphs with power law degree distributions, or graphs where community structure is weak or contested, will test the method’s assumptions much harder than the benchmarks here did.
The honest remaining gaps, an undirected only formulation, heuristic hyperparameters, and a computational cost that still trails the cheapest classical baselines even after the speedup, are the kind of gaps that tend to get closed by follow up work rather than staying open forever, especially once a clean open framework like this one exists for other researchers to extend.
For anyone deciding whether to spend an afternoon implementing this, the practical takeaway is narrower than the theoretical contribution. If you already have Louvain or spectral clustering working fine on your graph, this paper probably will not change your pipeline. If your graph sits right at the edge of what those methods can reliably separate, or if your nodes genuinely belong to more than one group and you have been forcing a single label onto them anyway, this is one of the few methods built specifically for that harder case, and it comes with code paths cheap enough to actually try.
Reference implementation, curvature computation and Ricci flow clustering
The code below implements the core pieces of Algorithm 1 from the paper, Ollivier curvature via the combinatorial upper and lower bound approximation, Forman curvature in its basic unweighted form, the Ricci flow weight update, and a threshold sweep that picks the best modularity. There is no neural network here because the paper itself proposes none, this is a combinatorial and optimal transport method, not a trained model, so the loop below iterates the Ricci flow rounds the way a training loop would iterate epochs, and modularity plays the role a loss function would normally play, as the quantity being optimized at each threshold check. A small synthetic two block graph stands in for the planted stochastic block models used in the paper’s own experiments.
# curvature_clustering.py
# Reference implementation of Algorithm 1 from Tian, Lubberts, and Weber (2025)
# Requires torch and networkx
# This is an unsupervised combinatorial and optimal transport method
# There is no trainable neural network layer, so this file has no
# conventional loss function, instead modularity is the objective
# maximized at each cutoff threshold, matching Section 2.3 of the paper
import torch
import networkx as nx
import itertools
class CurvatureClusterer:
"""Implements Algorithm 1, curvature driven Ricci flow clustering.
Supports approximated Ollivier curvature and basic Forman curvature."""
def __init__(self, curvature_type="ollivier", step_size=1.0,
iterations=10, n_thresholds=40):
self.curvature_type = curvature_type
self.step_size = step_size
self.iterations = iterations
self.n_thresholds = n_thresholds
def _shortest_paths(self, G, weight="weight"):
lengths = dict(nx.all_pairs_dijkstra_path_length(G, weight=weight))
return lengths
def _ollivier_bounds(self, G, u, v, lengths):
# Approximates Ollivier curvature as the mean of the combinatorial
# upper and lower bounds from Theorem 4 and Theorem 9 of the paper
du = G.degree(u)
dv = G.degree(v)
common_neighbors = len(list(nx.common_neighbors(G, u, v)))
upper = common_neighbors / max(du, dv)
term_a = max(0.0, 1 - 1/dv - 1/du - common_neighbors/min(du, dv))
term_b = max(0.0, 1 - 1/dv - 1/du - common_neighbors/max(du, dv))
lower = -term_a - term_b + common_neighbors/max(du, dv)
return (upper + lower) / 2.0
def _forman_curvature(self, G, u, v):
# Basic unweighted Forman curvature, four minus the two endpoint degrees
return 4 - G.degree(u) - G.degree(v)
def compute_curvature(self, G, lengths=None):
curvatures = {}
for u, v in G.edges():
if self.curvature_type == "ollivier":
curvatures[(u, v)] = self._ollivier_bounds(G, u, v, lengths)
else:
curvatures[(u, v)] = self._forman_curvature(G, u, v)
return curvatures
def ricci_flow_step(self, G):
lengths = self._shortest_paths(G)
curvatures = self.compute_curvature(G, lengths)
new_weights = {}
for (u, v), kappa in curvatures.items():
d_uv = G[u][v].get("weight", 1.0)
new_weights[(u, v)] = (1 - self.step_size * kappa) * d_uv
total = sum(new_weights.values()) or 1.0
n_edges = G.number_of_edges()
for (u, v), w in new_weights.items():
G[u][v]["weight"] = n_edges * w / total
return G
def _modularity(self, G, communities):
return nx.algorithms.community.quality.modularity(
G, communities, weight="weight"
)
def fit(self, G):
# The Ricci flow loop plays the role of the training loop
# Each round reshapes edge weights, no gradients are involved
working_graph = G.copy()
for edge in working_graph.edges():
working_graph[edge[0]][edge[1]]["weight"] = 1.0
for _ in range(self.iterations):
working_graph = self.ricci_flow_step(working_graph)
weights = [d["weight"] for _, _, d in working_graph.edges(data=True)]
if not weights:
return {n: 0 for n in G.nodes()}, 0.0
thresholds = torch.linspace(min(weights), max(weights), self.n_thresholds)
best_modularity = -1.0
best_labels = None
for x in thresholds:
trimmed = nx.Graph()
trimmed.add_nodes_from(working_graph.nodes())
for u, v, d in working_graph.edges(data=True):
if d["weight"] <= float(x):
trimmed.add_edge(u, v, weight=d["weight"])
components = list(nx.connected_components(trimmed))
if len(components) < 2:
continue
q = self._modularity(working_graph, components)
if q > best_modularity:
best_modularity = q
best_labels = components
label_map = {}
if best_labels:
for idx, comp in enumerate(best_labels):
for node in comp:
label_map[node] = idx
return label_map, best_modularity
def build_toy_two_block_graph():
# A tiny synthetic two block graph, roughly matching the planted
# SBM structure used in Section 7 of the paper, small enough for a
# fast smoke test
G = nx.Graph()
block_a = range(0, 8)
block_b = range(8, 16)
G.add_nodes_from(block_a)
G.add_nodes_from(block_b)
for u, v in itertools.combinations(block_a, 2):
if torch.rand(1).item() < 0.6:
G.add_edge(u, v)
for u, v in itertools.combinations(block_b, 2):
if torch.rand(1).item() < 0.6:
G.add_edge(u, v)
# a couple of thin bridges between the two blocks
G.add_edge(3, 9)
G.add_edge(6, 14)
return G
def evaluate_against_ground_truth(label_map, block_a, block_b):
# Simple purity style check against the two known blocks
# since this is unsupervised, there is no true accuracy target,
# only agreement with the planted structure used to build the toy graph
a_labels = [label_map[n] for n in block_a]
b_labels = [label_map[n] for n in block_b]
a_majority = max(set(a_labels), key=a_labels.count)
b_majority = max(set(b_labels), key=b_labels.count)
a_purity = a_labels.count(a_majority) / len(a_labels)
b_purity = b_labels.count(b_majority) / len(b_labels)
return (a_purity + b_purity) / 2.0
def smoke_test():
torch.manual_seed(0)
G = build_toy_two_block_graph()
clusterer = CurvatureClusterer(curvature_type="ollivier", iterations=8)
labels, modularity = clusterer.fit(G)
purity = evaluate_against_ground_truth(labels, range(0, 8), range(8, 16))
print(f"Best modularity found {modularity:.3f}")
print(f"Block purity against planted structure {purity:.3f}")
assert modularity > -1.0, "Clustering did not run"
print("Smoke test passed")
if __name__ == "__main__":
smoke_test()
This code is an independent, simplified reimplementation for educational purposes and does not reproduce the authors own codebase, which is not linked in the paper. Complexity constants, exact threshold spacing, and the weighted curvature bounds have been simplified from the full Theorem 9 formulas for readability.
Frequently asked questions
Is curvature based clustering better than Louvain or spectral clustering
Not universally. The paper’s own results show Louvain and spectral clustering matching or beating the curvature method on easy, well separated graphs. The curvature approach pulls ahead mainly in the harder regime, when the two communities are close to the detectability threshold, and in the mixed membership case where Louvain and standard spectral clustering have no direct answer at all.
Do I need a neural network to run this method
No. The entire pipeline is combinatorial graph theory and optimal transport. There is no training data requirement, no gradient descent, and no learned parameters, which is part of why it works reasonably well even on small real world networks with a few hundred nodes.
What is a line graph and why does it matter here
A line graph turns every edge of the original graph into a node, connecting two of these new nodes whenever their original edges shared an endpoint. The paper uses it to handle overlapping communities, since a node belonging to two communities creates a bridge among its edges in the line graph even though no such bridge exists among nodes in the original graph.
How expensive is this to actually run
Exact Ollivier curvature is the expensive part, potentially minutes to hours depending on graph size and density, since it involves solving an optimal transport problem for every edge. The paper’s combinatorial approximation cuts this dramatically, down to roughly linear cost in the maximum node degree, at a small accuracy cost. Forman curvature is cheap throughout, simple arithmetic on node degrees and triangle counts.
Can this handle directed graphs, like citation networks or follower graphs
Not as presented. The paper explicitly restricts its analysis to undirected networks and lists an extension to directed graphs as future work rather than something the current framework supports.
Where can I read the full paper
The complete paper, including all proofs and the extended appendix, is published open access through the Journal of Machine Learning Research, volume 26, under a Creative Commons attribution license.
Go straight to the source
The full paper includes every proof referenced above, the complete appendix of weighted curvature bounds, and all real world dataset statistics.
Tian, Y., Lubberts, Z., and Weber, M. (2025). Curvature based Clustering on Graphs. Journal of Machine Learning Research, 26, pages 1 to 67. Paper identifier 24-0781.
This analysis is based on the published paper and an independent evaluation of its claims.