Which edges need optimal transport?
Cheap bounds certify the sign of many edges' Ollivier–Ricci curvature. See which ones still need a transport problem.
Ollivier–Ricci (OR) curvature compares the neighbourhoods of an edge’s two endpoints by solving an optimal transport problem, one per edge. Balanced Forman (BF) curvature is a cheap combinatorial stand-in. In From Proxy to Certificate, Tebe Nigrelli and I show that the BF value of an edge certifies an interval for its lazy OR curvature without solving any transport problem, and that the edge’s 2-hop neighbourhood sharpens it.
To decide whether $\kappa_{\mathrm{OR}} < \tau$ for every edge, certify-then-solve computes the 2-hop interval, which settles every edge the BF interval settles and more, intersects it with a certificate from the bounds of Tian, Lubberts and Weber (TLW), and solves a transport problem only for the edges still undecided. The map shows this one stage at a time, as the paper’s figure does: (a) what the BF interval alone decides, (b) the 2-hop interval, (c) the TLW certificate, and (d) the transport problems that remain. Each stage draws the edges it decides in colour and the edges decided earlier in grey; edges still undecided aren’t drawn.
decided here, κOR < τ decided here, κOR ≥ τ decided by an earlier stage undecided: not drawn
What you’re seeing
On the paper’s graph at $\tau = 0$, the sign query, the BF interval alone decides 52.8% of the edges, the 2-hop interval brings that to 63.4% and the TLW certificate to 73.8%, so 781 of the 2,985 edges need a transport problem. Almost everything the BF interval decides has $\kappa_{\mathrm{OR}} \geq 0$, and almost everything the 2-hop interval and the TLW certificate add has $\kappa_{\mathrm{OR}} < 0$.
Moving $\tau$ changes which edges sit close to the threshold, and so which ones are hard. The chart shows, for every $\tau$ from −1 to 1, how the edges split between the four stages; the vertical line marks the current $\tau$, and dragging along the chart moves it. Denser graphs leave more to the solver: at $\tau = 0$, the random geometric graphs of expected degree 6 send between 19% and 22% of their edges to it, those of degree 12 between 28% and 33%.
As in the paper’s code, every interval is widened by $10^{-9}$ against floating-point rounding before it is compared with $\tau$, so an interval whose lower end is exactly $\tau$ doesn’t decide its edge. That is the spike in the chart at $\tau = 0$: on the paper’s graph, 92 of the 781 transport problems at $\tau = 0$ are edges whose lower end is exactly 0.
How it’s computed
Every interval and curvature comes from the paper’s code, Curvature-Transfer-Code, with the exact values from orcut, the solver behind every exact value in the paper. The intervals don’t depend on $\tau$, so the page stores them at full precision and reruns the cascade in your browser whenever $\tau$ moves, with the same comparisons as the code, so every count matches the code’s.
The random geometric graphs have 800 uniform points in the unit square, joined when closer than $r$, with the expected degree $800 \pi r^2$ set to 6, 8 or 12; each is restricted to its largest component and drawn at its points. Seed 0 at degree 8 is the graph of the paper’s figure, and “Draw another graph” steps through three more seeds. Yeast and the karate club are two of the paper’s real networks, drawn with a Kamada–Kawai layout.
The paper’s figure shows the four stages side by side, on the default graph at $\tau = 0$:
