An efficient alternative to Ollivier-Ricci curvature based on the Jaccard metric.

Siddharth Pal, Feng Yu, Terrence J. Moore, Ram Ramanathan, Amotz Bar-Noy, Ananthram SwamiarXiv 2017 · OpenReview

TL;DR

This paper introduces two new graph curvature metrics, Jaccard Curvature (JC) and Generalized Jaccard Curvature (gJC), as computationally efficient alternatives to the popular but expensive Ollivier-Ricci (OR) curvature. The authors demonstrate that gJC, in particular, provides a high-fidelity approximation of OR across various network topologies—from random graph models to real-world social and infrastructure networks—while offering speedups of several orders of magnitude.

What Problem Does This Paper Address?

In differential geometry, Ricci curvature measures how much a manifold deviates from being "flat." In network science, discrete versions like Ollivier-Ricci (OR) curvature have become powerful tools for identifying bottlenecks, measuring network robustness, and distinguishing between healthy and cancerous gene expression networks.

The problem is computational cost. Calculating OR curvature for an edge requires solving an optimal mass transport (Wasserstein distance) problem. For large, dense networks, this is prohibitively expensive, scaling poorly with the degree of the nodes. While simpler alternatives like Forman-Ricci curvature exist, they often fail to capture the nuanced structural information that makes OR curvature so useful. The authors aim to bridge this gap by providing a metric that is as informative as OR but as practical as simpler heuristics.

Methods

The authors propose two metrics based on the Jaccard index, which traditionally measures the similarity between two sets (in this case, the neighborhoods of two adjacent nodes).

  1. Jaccard Curvature (JC): A simple linear transformation of the Jaccard index designed to map neighborhood overlap to the standard $(-2, 1)$ range of OR curvature.
  2. Generalized Jaccard Curvature (gJC): A more sophisticated metric that partitions "exclusive" neighbors (those not shared by both nodes) based on their distance from the other node's neighborhood. It accounts for nodes that are 1, 2, or 3 hops away, effectively creating a discrete, low-complexity approximation of the mass transport problem.

The authors provide a rigorous complexity analysis, showing that for a $d$-regular graph with $n$ nodes, gJC scales at $O(nd^3)$, whereas OR curvature scales at $O(nd^4 \log^2 d)$.

This figure illustrates the intuition behind gJC: it categorizes neighbors by their distance to the adjacent node's neighborhood to approximate mass transport costs.

Datasets

The researchers evaluated their metrics using both synthetic models and real-world datasets:

  • Synthetic Models: Erdös-Rényi (ER), Barabási-Albert (BA), Watts-Strogatz (WS) small-world, and Random Geometric Graphs (RGG).
  • Real-World Networks: A diverse set including the US Power Grid, EuroRoad (European highways), PGP (social web of trust), p2p-Gnutella, Email communication, Hamsterster (social), Human protein-protein interactions, and Jazz musician collaborations.

Key Insights and Ideas

  • Asymptotic Alignment: The authors prove theoretically that for Erdös-Rényi graphs, gJC matches the asymptotic behavior of OR curvature across different scaling regimes (from very sparse to very dense).
  • The "Sweet Spot" of Complexity: There is a clear hierarchy. Forman curvature is the fastest but least accurate; JC is a good proxy only for highly clustered networks; gJC serves as the "sweet spot," providing high correlation with OR across almost all scenarios with significantly lower overhead.
  • Neighborhood Geometry: The paper reinforces the idea that positive curvature in graphs is fundamentally tied to neighborhood overlap (triangles), while negative curvature is tied to tree-like, branching structures.
This table shows how gJC and OR curvatures align perfectly across different scaling regimes of Erdös-Rényi graphs, unlike the simpler JC metric.

Key Results

  • High Fidelity: In ER graphs, gJC achieved Pearson correlation coefficients ($r_p$) often exceeding 0.9 with OR curvature.
  • Dramatic Speedups: On the PGP social network (~10,000 nodes), calculating OR curvature took over 1,000 seconds, while gJC took only 5.2 seconds—a roughly 200x improvement.
  • Real-World Performance: gJC consistently outperformed both JC and Forman curvature in tracking OR curvature across almost every real-world network tested, particularly in social and biological networks where neighborhood clustering is a key feature.

Limitations and Future Work

  • Unweighted Focus: The current study focuses primarily on unweighted graphs. While the Jaccard logic can be extended, the specific performance on weighted networks remains to be fully explored.
  • Parameter Sensitivity: The gJC formula relies on specific weights $(\alpha, \beta, \gamma, \delta, \zeta)$ derived from canonical graphs (like grids and trees). While these work well generally, there may be room for domain-specific optimization.
  • Directed Graphs: The paper does not address directed networks, which are common in many real-world applications like the web or citation networks.

Summary updated

Abstract

We study Ollivier-Ricci curvature, a discrete version of Ricci curvature, which has gained popularity over the past several years and has found applications in diverse fields. However, the Ollivier-Ricci curvature requires an optimal mass transport problem to be solved, which can be computationally expensive for large networks. In view of this, we propose two alternative measures of curvature to Ollivier-Ricci which are motivated by the Jaccard coefficient and are demonstrably less computationally intensive, a cheaper Jaccard (JC) and a more expensive generalized Jaccard (gJC) curvature metric. We show theoretically that the gJC closely matches the Ollivier-Ricci curvature for Erdos-Renyi graphs in the asymptotic regime of large networks. Furthermore, we study the goodness of approximation between the proposed curvature metrics and Ollivier-Ricci curvature for several network models and real networks. Our results suggest that in comparison to an alternative curvature metric for graphs, the Forman-Ricci curvature, the gJC exhibits a reasonably good fit to the Ollivier-Ricci curvature for a wide range of networks, while the JC is shown to be a good proxy only for certain scenarios.
BibTeX
@misc{pal2017efficient,
  author = {Siddharth Pal and Feng Yu and Terrence J. Moore and Ram Ramanathan and Amotz Bar-Noy and Ananthram Swami},
  title = {{An efficient alternative to Ollivier-Ricci curvature based on the Jaccard metric.}},
  year = {2017},
  eprint = {1710.01724},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1710.01724},
}
Figure