📊 statistics

Near-Linear Time Generalized Sinkhorn Algorithms for Bounded Genus Graphs

This paper introduces GenusSink, a novel class of approximate generalized Sinkhorn algorithms that achieve near-linear time and memory complexity for optimal transport on bounded genus graphs by leveraging separator-based decomposition, computational geometry, and fast matrix-vector multiplication techniques to overcome the quadratic bottlenecks of brute-force methods.

Original authors: Krzysztof Choromanski, Derek Long, Ananya Parashar, Dwaipayan Saha

Published 2026-05-12

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Krzysztof Choromanski, Derek Long, Ananya Parashar, Dwaipayan Saha

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have two massive crowds of people standing on a complex, winding map. One crowd needs to move to the other side of the map to match up with the second crowd. The goal is to move everyone with the least amount of total walking distance possible. This is a classic math problem called Optimal Transport.

Usually, to solve this, you have to calculate the walking distance between every single person in the first crowd and every single person in the second crowd. If you have 10,000 people, that's 100 million distance calculations. If you have 100,000 people, the math explodes, and your computer crashes. This is the "brute-force" method: accurate, but painfully slow.

There is a faster way called the Sinkhorn algorithm, which is like a smart shortcut. It approximates the answer quickly. However, even this smart shortcut usually hits a wall when the map is complex (like a 3D object or a city street grid) because it still needs to store a massive list of all those distances in its memory.

The New Solution: GenusSink

The authors of this paper introduce a new tool called GenusSink. Think of it as a "GPS for massive crowds" that works incredibly fast on maps that don't have too many loops or holes (mathematically called "bounded genus" graphs, which includes flat maps and surfaces like donuts or spheres).

Here is how GenusSink works, using simple analogies:

1. The "Divide and Conquer" Strategy (The Separator)

Imagine you have a huge, tangled ball of yarn. To understand it, you don't look at every thread at once. Instead, you find a few key knots that, if you cut them, would split the ball into two smaller, manageable balls.

The Paper's Method: GenusSink finds these "knots" (called separators) in the map. It cuts the map into smaller pieces, solves the movement problem for the small pieces, and then stitches the answers back together.
The Magic: Because the maps they handle (like 3D models or city roads) have a specific shape, these "knots" are very small. This allows the computer to break the problem down recursively, like a set of Russian nesting dolls, without getting overwhelmed.

2. The "Smart Calculator" (S-GFI)

Usually, when you split a map, you lose the ability to quickly calculate distances between the two new pieces. You'd have to re-measure everything.

The Paper's Innovation: They built a special data structure called a Separation Graph Field Integrator (S-GFI). Think of this as a pre-calculated "cheat sheet" or a specialized calculator attached to every cut in the map.
How it helps: Instead of measuring the distance between two people on opposite sides of a cut from scratch, the S-GFI uses math tricks (like Fourier analysis, which is how your phone compresses music) to instantly estimate that distance based on the "cheat sheet." This turns a slow, heavy calculation into a lightning-fast one.

3. The Result: Speed and Accuracy

The paper claims that GenusSink achieves three things that previous methods couldn't do all at once:

Near-Linear Speed: As you add more people to the map, the time it takes to solve the problem grows very slowly (almost like a straight line), rather than exploding exponentially.
Low Memory: It doesn't need to store the massive "100 million distance" list. It only keeps the small "cheat sheets."
High Accuracy: Unlike other fast methods that guess and lose precision, GenusSink is mathematically proven to be almost as accurate as the slow, brute-force method. In their tests, it was "orders of magnitude" more accurate than other fast algorithms while still being fast.

Real-World Tests Mentioned in the Paper

The authors didn't just do math on paper; they tested this on real-world scenarios:

3D Shapes: They tested it on digital meshes of 3D objects (like spheres with handles or "pseudo-genus" shapes). GenusSink matched the accuracy of the slow method but ran much faster as the shapes got bigger.
Ambulance Deployment in NYC: They used a real map of the Bronx (with over 33,000 road intersections) to figure out where to place ambulances.
- The Goal: Minimize the time it takes for an ambulance to reach an emergency.
- The Result: GenusSink found a better placement strategy than other fast methods. It reduced the average response time for severe emergencies to 12.5 minutes, compared to 13.4–14.5 minutes for other methods. It was especially better at handling the "worst-case" scenarios (the tail end of the response times).

Summary

GenusSink is a new mathematical tool that lets computers solve complex "moving mass" problems on 3D shapes and city maps almost instantly. It does this by cleverly cutting the map into small pieces, using pre-calculated "cheat sheets" to skip the heavy math, and stitching the answers back together. It is fast enough for real-time use (like moving ambulances) but accurate enough to be trusted with critical decisions.

Technical Summary: GenusSink Algorithms for Bounded Genus Graphs

Problem Statement

The paper addresses the computational bottleneck associated with solving the Optimal Transport (OT) problem on bounded genus graphs (including planar graphs and meshes approximating 3D objects) using shortest-path distances as cost functions.

Standard approaches to OT, such as the Sinkhorn algorithm (entropic regularization), typically require:

Quadratic time and space to materialize the full cost matrix $C$ (or the generalized distance matrix $K^\epsilon_f$ ), where $C_{ij}$ represents the cost between nodes $i$ and $j$ .
Cubic time for brute-force linear programming solutions.

While the Sinkhorn iteration reduces the complexity of finding the transport plan to quadratic time $O(n^2)$ , it still necessitates storing and operating on an $n \times n$ matrix. For large-scale graphs common in machine learning (e.g., 3D meshes, road networks), this quadratic memory and time requirement becomes prohibitive. Existing efficient approximations (e.g., Greenkhorn, Screenkhorn, Nyström methods) often sacrifice accuracy or fail to provide exact computations for specific graph structures like low-treewidth domains.

The core challenge is to design an algorithm that achieves near-linear time for pre-processing, iteration steps, and querying the transport plan, while maintaining near-linear memory and high accuracy, specifically for graphs where the cost is defined by geodesic (shortest-path) distances.

Methodology: GenusSink

The authors propose GenusSink, a new class of approximate generalized Sinkhorn algorithms. The methodology relies on three primary pillars:

1. Separator-Based Decomposition and Treewidth

The algorithm leverages the structural properties of bounded genus graphs.

Treewidth Approximation: While bounded genus graphs (like planar graphs) do not inherently have low treewidth (often $O(\sqrt{n})$ ), recent theoretical results [14] show that their metrics can be accurately approximated by metrics on graphs with low treewidth ( $O(\log \log n)$ ).
Tree Decomposition: GenusSink utilizes a tree decomposition of the graph (or a low-treewidth proxy) to facilitate a divide-and-conquer strategy. The graph is recursively split using balanced separators (sets of vertices whose removal divides the graph into roughly equal components).

2. Separation Graph Field Integrators (S-GFI)

A novel data structure, the Separation Graph Field Integrator (S-GFI), is introduced to efficiently compute matrix-vector multiplications with generalized distance matrices $D^\epsilon_f = [f_\epsilon(d_{i,j})]$ .

Structure: S-GFI is a binary tree where nodes correspond to balanced separators. Each node stores metadata including distance matrices between the separator and the subgraph components (left and right).
Integration Process: To compute $y = D^\epsilon_f x$ , the algorithm traverses the tree. For a given node with separator $S$ and components $A$ and $B$ , it computes contributions from paths crossing $S$ .
Cross-Computation: The core efficiency gain comes from the cross_compute procedure. Instead of computing all pairwise interactions between $A$ $A$ and $B$ $B$ explicitly, it utilizes:
- Computational Geometry: Sorting vectors of distances to handle inequality constraints efficiently.
- Fourier Analysis & Low Displacement Rank: For generalized functions $f$ , the paper leverages the theory of cordial functions and low displacement rank matrices (specifically Cauchy-type matrices) to perform near-linear time multiplications. For the standard exponential kernel ( $f(x) = e^{-x}$ ), the structure allows for exact $O(|A| + |B|)$ updates.
Complexity: The integrate function runs in $O(n \cdot \text{poly}(|S|) \cdot \log^{\text{poly}(|S|)}(n))$ . For graphs with treewidth $O(\log \log n)$ , the total construction and iteration time is near-linear in $n$ .

3. Practical Implementation for Bounded Genus

Since constructing a perfect low-treewidth embedding for general bounded genus graphs can be complex, the authors propose a practical heuristic:

Instead of a full theoretical embedding, they use linear-time algorithms to find $O(\sqrt{n})$ -size balanced separators.
They sub-sample the separators (keeping $O(\log \log n)$ points) and distribute the rest to child nodes.
The depth of the S-GFI tree is treated as a hyperparameter, allowing a trade-off between asymptotic speed and the use of brute-force matrix-vector multiplication for small subgraphs.

Key Contributions

GenusSink Algorithm: A new algorithmic framework providing near-linear time pre-processing, iteration, and querying for OT on bounded genus graphs with geodesic costs.
S-GFI Data Structure: A novel data structure that enables efficient matrix-vector multiplication with generalized distance matrices by exploiting separator-based decomposition and computational geometry.
Theoretical Guarantees:
- Proof that GenusSink is numerically equivalent to the brute-force geodesic Sinkhorn algorithm on graphs with treewidth $O(\log \log n)$ (e.g., trees).
- Demonstration that bounded genus metrics can be approximated by low-treewidth proxies with additive distortion, enabling the application of the algorithm to planar and bounded genus meshes.
Empirical Validation: Extensive experiments showing GenusSink matches the accuracy of dense geodesic baselines while offering significant speedups.

Experimental Results

The paper evaluates GenusSink on synthetic and real-world datasets:

Synthetic Pseudo-Genus Surfaces: On planar graphs with varying "pseudo-genus" (simulating complex topologies), GenusSink matches the dense geodesic full-kernel baseline to numerical precision. In contrast, other efficient methods (Greenkhorn, Screenkhorn, Sparse Sinkhorn, Nyström) exhibit significant accuracy gaps. GenusSink scales significantly faster than the brute-force baseline as the number of nodes increases (up to ~20,000 nodes).
Thingi10K Meshes: Applied to real 3D meshes (up to 13k vertices), GenusSink remains essentially exact compared to the dense geodesic Sinkhorn, whereas other approximation methods show visible errors.
Real-World Application (EMS Deployment): In a case study optimizing ambulance deployment in the Bronx (33k nodes), GenusSink produced deployments with lower mean response times (12.5 mins vs. 13.4–14.5 mins for baselines) and significantly better performance in the upper tail of response times (95th+ percentile).

Significance and Claims

The paper claims that GenusSink represents a significant advancement by bridging the gap between computational efficiency and numerical accuracy in optimal transport on non-Euclidean domains.

Accuracy: Unlike other "efficient" Sinkhorn variants that rely on sparsification or low-rank approximations which introduce errors, GenusSink provides orders of magnitude more accurate computations, effectively matching the brute-force geodesic solution for specific graph classes.
Efficiency: It achieves near-linear time complexity, overcoming the quadratic bottleneck of standard Sinkhorn implementations that require materializing the full cost matrix.
Generality: The approach is applicable to any bounded genus graph, making it suitable for 3D mesh processing, road networks, and manifold learning tasks where geodesic distances are the natural cost metric.

The authors note that the method is currently limited to bounded genus graphs but plan to extend it to minor-free graphs in future work. They emphasize that the algorithm is particularly effective for graphs where the treewidth is small or can be well-approximated by small treewidth structures.