pith. sign in

arxiv: 2605.09782 · v3 · pith:Y42FOHJDnew · submitted 2026-05-10 · 💻 cs.DS · stat.ME

Near-Linear Time Generalized Sinkhorn Algorithms for Bounded Genus Graphs

Krzysztof Choromanski , Derek Long , Ananya Parashar , Dwaipayan Saha This is my paper

Pith reviewed 2026-05-20 22:40 UTC · model grok-4.3

classification 💻 cs.DS stat.ME
keywords Sinkhorn algorithmoptimal transportbounded genus graphsplanar graphsnear-linear timegeodesic distancesseparator decompositionlow displacement rank
0
0 comments X

The pith

GenusSink computes approximate generalized Sinkhorn algorithms in near-linear time and memory for shortest-path costs on bounded-genus graphs.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper presents GenusSink as a method that accelerates approximate optimal transport computations on graphs of bounded genus, including planar graphs and meshes that approximate 3D surfaces, by replacing brute-force quadratic-time Sinkhorn iterations with separator-based decompositions. It achieves near-linear time for preprocessing, each iteration step, and final transport plan queries while using near-linear memory, through new fast matrix-vector multiplication results that draw on Fourier analysis and low-displacement-rank theory. This matters for any setting where distributions live on manifolds approximated by large graphs and costs are geodesic distances, because the standard approach scales quadratically and quickly becomes impractical. The same machinery yields numerical equivalence to the exact brute-force geodesic Sinkhorn algorithm when the underlying graph has treewidth O(log log n), such as on trees.

Core claim

GenusSink delivers near-linear time preprocessing, near-linear time per iteration, near-linear time for querying the final transport plan matrix, and near-linear memory for approximate generalized Sinkhorn algorithms with shortest-path-distance costs on bounded-genus graphs; it obtains these bounds by combining separator-based graph decompositions with computational-geometry techniques and fast matrix-vector multiplications for generalized distance matrices, and it is numerically equivalent to the brute-force geodesic Sinkhorn algorithm on any n-vertex graph of treewidth O(log log n).

What carries the argument

Separator-based decompositions of bounded-genus graphs that support fast matrix-vector multiplications with generalized distance matrices via Fourier analysis and low-displacement-rank theory, realized through separation graph field integrators (S-GFIs).

If this is right

  • Optimal transport plans with geodesic costs become feasible on large planar meshes and bounded-genus surfaces that arise in 3D modeling.
  • Preprocessing, iteration, and query steps each scale near-linearly instead of quadratically in the number of vertices.
  • Memory usage remains near-linear, removing the quadratic storage bottleneck of dense distance matrices.
  • The algorithm is numerically identical to brute-force geodesic Sinkhorn on any graph of treewidth O(log log n), including all trees.
  • The same separator and fast-multiplication primitives apply to any matrix operation whose entries depend on shortest-path distances on the graph.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The approach may extend directly to other minor-closed graph families that admit small separators, such as graphs of bounded treewidth or planar minors.
  • Runtime gains could be measured on real-world road networks or surface meshes to quantify practical speedups beyond worst-case asymptotics.
  • The fast distance-matrix multiplication primitives might be reused for other kernel-based methods that rely on geodesic costs.
  • Convergence guarantees could be tested by comparing iteration counts on high-genus versus low-genus graphs of equal size.

Load-bearing premise

Bounded-genus graphs admit separator decompositions whose treewidth properties let the fast matrix-vector multiplications run without hidden super-linear factors in constants or iteration count.

What would settle it

Measure wall-clock time for preprocessing plus a fixed number of iterations on a family of planar graphs whose vertex count increases by successive factors of two; the observed scaling deviates from linear if super-linear factors are present.

Figures

Figures reproduced from arXiv: 2605.09782 by Ananya Parashar, Derek Long, Dwaipayan Saha, Krzysztof Choromanski.

Figure 1
Figure 1. Figure 1: Left: Seven-vertex planar graph. Right: A pictorial description of its treewidth decomposition, with the treewidth parameter upper-bounding the sizes of the clusters of nodes above (that we will refer to as bags, see: Sec. 2.1). Two graph pieces, obtained with the separator {B, C, D}, are highlighted via red dashed boxes. The treewidth decomposition provides a gateway for designing efficient algorithms for… view at source ↗
Figure 2
Figure 2. Figure 2: Left to right: 2D-surfaces of 3D objects with genus values: 0, 1, 2 and 3. In this paper, we are especially interested in families of graphs with bounded genus that can be used in particular to provide discretized mesh representations of the above surfaces. distributions defined on the manifolds approximated by weighted graphs and with cost functions given by geodesic distances. We conduct rigorous theoret… view at source ↗
Figure 3
Figure 3. Figure 3: Left: The pictorial representation of the S-GFI data structure. In that example, the corresponding tree has a root with two children and four grandchildren. Right: The visualization of the cross_compute function with the medians depicted in red/green and their corresponding splits highlighted as dashed lines. ξi = X j∈RB f(ai [k] + bj [k])I[wk i ≺ z k j ]vj (11) We can then continue the calculations recurs… view at source ↗
Figure 4
Figure 4. Figure 4: ). In contrast, most approximate baselines exhibit a clear accuracy gap. 0 5000 10000 15000 20000 Number of nodes 10 13 10 9 10 5 10 1 10 3 |O Tf ull O Tm e t h o d| 0 5000 10000 15000 20000 Number of nodes 10 13 10 9 10 5 10 1 10 3 |O Tf ull O Tm e t h o d| 0 5000 10000 15000 20000 Number of nodes 10 13 10 9 10 5 10 1 10 3 |O Tf ull O Tm e t h o d| 0 5000 10000 15000 20000 Number of nodes 10 2 10 1 10 0 1… view at source ↗
Figure 5
Figure 5. Figure 5: Left: examples of Thingi10K meshes. Middle: absolute OT-cost error relative to dense geodesic Sinkhorn for several efficient Sinkhorn methods. As before, GenusSink stays numerically exact while providing significant computational gains. Right: runtime scaling for dense geodesic kernel construction versus two most accurate efficient methods: GenusSink and Greenkhorn (see: left), with error bars over repeate… view at source ↗
Figure 6
Figure 6. Figure 6: Bronx road graph (left), mean response times across different Sinkhorn methods (middle), and tail response time gaps relative to GenusSink at quantiles from 0.95 onwards (right). 5 Conclusion We proposed in this paper GenusSink, a new class of efficient Sinkhorn algorithms operating on graph metric spaces for bounded genus graphs and characterized by near-linear time (1) pre-processing, (2) iteration step,… view at source ↗
Figure 7
Figure 7. Figure 7: Planar dumbbell graphs after the root separator split. The two lobes form the left and right subgraphs, while the narrow bridge induces a small separator; the examples above correspond to two different handle widths. w ∈ {1, 2, 3}, and initial/target distributions given by two-component Gaussian mixtures localized on the left and right lobes, respectively, and normalized over the graph vertices. The entrop… view at source ↗
Figure 8
Figure 8. Figure 8: Planar dumbbell experiments for handle widths w = 1, 2, 3 (left to right). Top: absolute Sinkhorn￾cost error relative to the dense geodesic full-kernel baseline. Bottom: total runtime for the baseline and two most accurate efficient methods: Sparse Sinkhorn and GenusSink. Across all widths, GenusSink remains numerically exact while providing significant computational gains. In addition to the dumbbell grap… view at source ↗
Figure 9
Figure 9. Figure 9: Pseudo-genus surface family used in our synthetic experiments. We show planar sphere-topology surface meshes embedded in R 3 for pseudo-genus orders 1, 2, and 3, colored according to the root separator split used to initialize the separation tree. mixtures in the surface parameter coordinates and normalized over the graph vertices. We again compare GenusSink against the dense geodesic full-kernel Sinkhorn … view at source ↗
read the original abstract

We present GenusSink, a new class of approximate generalized Sinkhorn algorithms with shortest-path-distance costs for bounded genus (e.g. planar) graphs, providing near-linear time: (1) pre-processing, (2) iteration step, (3) final transport plan matrix querying and near-linear memory. Graphs handled by GenusSink include in particular planar graphs and bounded-genus meshes approximating 3D objects. GenusSink addresses total quadratic time complexity of its brute-force counterpart by leveraging separator-based decomposition of graphs, computational geometry techniques, and new results on fast matrix-vector multiplications with generalized distance matrices, using, in particular, Fourier analysis and low displacement rank theory. It is inspired by recent breakthroughs in graph theory on approximating bounded genus metrics with small treewidth metrics \citep{minor-free-paper}. The graph-centric approach enables us to target optimal transport problem with the corresponding distributions defined on the manifolds approximated by weighted graphs and with cost functions given by geodesic distances. We conduct rigorous theoretical analysis of GenusSink, provide practical implementations, leveraging newly introduced in this paper \textit{separation graph field integrators} (S-GFIs) data structures and present empirical verification. GenusSink provides orders of magnitude more accurate computations than other efficient Sinkhorn algorithms, while still guaranteeing significant computational improvements, as compared to the baseline. As a by-product of the developed methods, we show that GenusSink is \textbf{numerically equivalent} to the brute-force geodesic Sinkhorn algorithm on $n$-vertex graphs with treewidth $O(\log \log (n))$ (e.g. on trees).

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper introduces GenusSink, a new class of approximate generalized Sinkhorn algorithms for shortest-path-distance costs on bounded-genus graphs (including planar graphs and meshes). It claims near-linear time for preprocessing, each iteration step, and final transport-plan querying, together with near-linear memory, by combining separator-based decompositions, Fourier analysis, and low-displacement-rank matrix-vector multiplication. The approach is inspired by metric approximations of bounded-genus graphs by small-treewidth graphs; the manuscript supplies theoretical analysis, implementations based on newly introduced separation graph field integrators (S-GFIs), empirical comparisons, and a by-product showing numerical equivalence to brute-force geodesic Sinkhorn on graphs of treewidth O(log log n).

Significance. If the near-linear runtime claims are substantiated, the result would be a meaningful contribution to scalable optimal transport on geometric graphs, enabling efficient geodesic OT on planar and bounded-genus meshes that arise in computational geometry and 3-D modeling. The synthesis of graph separators with structured linear-algebra techniques, together with the low-treewidth equivalence result, offers both algorithmic and practical value.

major comments (2)
  1. [Theoretical analysis of fast matrix-vector multiplication] The central near-linear per-iteration claim rests on fast matrix-vector multiplication for generalized distance matrices via separator decompositions and low-displacement-rank structure. Bounded-genus graphs admit balanced separators of size Θ(√(g n)); the recursive hierarchy therefore risks displacement ranks or Fourier-mode counts that scale with separator size or depth, potentially yielding Ω(n^{3/2}) rather than O(n polylog n) multiplication cost. The manuscript must supply an explicit rank bound independent of n and g (or a concrete recurrence showing the total cost remains near-linear) to support the headline runtime.
  2. [Rigorous theoretical analysis] The abstract and description assert 'rigorous theoretical analysis' together with error bounds and iteration counts, yet no derivation details, explicit convergence rates, or dependence of iteration count on the approximation parameters are visible. Because the overall near-linear guarantee is the product of per-iteration cost and iteration count, this omission is load-bearing for the main claim.
minor comments (2)
  1. [Abstract] The placeholder citation 'minor-free-paper' should be expanded to a full bibliographic entry.
  2. [Implementation and data structures] Clarify the precise definition and construction of the separation graph field integrators (S-GFIs) data structure, including space and query-time bounds, so that the near-linear memory claim can be verified independently.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the detailed and constructive report. The comments on the matrix-vector multiplication analysis and the presentation of convergence guarantees are well-taken. Below we respond point by point, clarifying the existing arguments while agreeing that additional explicit bounds and derivations will improve the manuscript. We will revise accordingly.

read point-by-point responses

  1. Referee: [Theoretical analysis of fast matrix-vector multiplication] The central near-linear per-iteration claim rests on fast matrix-vector multiplication for generalized distance matrices via separator decompositions and low-displacement-rank structure. Bounded-genus graphs admit balanced separators of size Θ(√(g n)); the recursive hierarchy therefore risks displacement ranks or Fourier-mode counts that scale with separator size or depth, potentially yielding Ω(n^{3/2}) rather than O(n polylog n) multiplication cost. The manuscript must supply an explicit rank bound independent of n and g (or a concrete recurrence showing the total cost remains near-linear) to support the headline runtime.

    Authors: We appreciate this observation on the complexity of the recursive separator hierarchy. The analysis in the manuscript relies on the low-displacement-rank property of the generalized distance matrices induced by the S-GFI data structures, combined with the fact that bounded-genus metrics admit approximations by O(log log n)-treewidth graphs (as cited). This keeps the effective rank and Fourier mode count bounded by a function of g and the approximation parameter rather than growing with separator size at every level. Nevertheless, we agree that an explicit recurrence and rank bound would make the near-linear claim fully transparent. In the revision we will insert a new subsection deriving the recurrence T(n) = 2T(n/2) + O(r(g,δ) √n log n) where r(g,δ) is the displacement rank (independent of n), showing that the total cost remains O(n polylog n) with constants depending only on genus and accuracy parameters. revision: yes

  2. Referee: [Rigorous theoretical analysis] The abstract and description assert 'rigorous theoretical analysis' together with error bounds and iteration counts, yet no derivation details, explicit convergence rates, or dependence of iteration count on the approximation parameters are visible. Because the overall near-linear guarantee is the product of per-iteration cost and iteration count, this omission is load-bearing for the main claim.

    Authors: The manuscript contains the core convergence analysis in Sections 3.2 and 4.2, where we bound the approximation error of the generalized distance matrix by the treewidth approximation parameter δ and then invoke standard Sinkhorn convergence results under additive cost perturbations. The number of iterations is shown to be O((1/ε) log(1/δ)) for accuracy ε. We acknowledge, however, that the derivations are condensed and the dependence on δ is not stated as a single displayed equation. In the revised version we will expand these sections with the full step-by-step derivation of the iteration bound and an explicit statement of how the per-iteration near-linear cost multiplies with the iteration count to yield the overall guarantee. revision: yes

Circularity Check

0 steps flagged

No significant circularity; claims build on external graph-theoretic results

full rationale

The paper's derivation relies on separator-based decompositions of bounded-genus graphs, Fourier analysis, low-displacement-rank theory for fast matrix-vector multiplications, and an external citation to prior work on approximating bounded-genus metrics by small-treewidth metrics. The by-product numerical equivalence claim for O(log log n) treewidth graphs is presented as a derived consequence rather than an input definition. No quoted equations or steps reduce a claimed runtime or prediction to a fitted parameter, self-definition, or load-bearing self-citation chain. The method is self-contained against external benchmarks in graph theory and structured linear algebra, with no evident reduction of the near-linear bounds to internal construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the existence of efficient separators for bounded-genus graphs and on the applicability of low-displacement-rank and Fourier techniques to generalized distance matrices; these are treated as established or newly derived but are not unpacked in the abstract.

axioms (1)
  • domain assumption Bounded-genus graphs admit separator decompositions that reduce the problem to low-treewidth subproblems whose distance matrices have low displacement rank.
    Invoked when claiming near-linear matrix-vector multiplies; location: abstract paragraph on leveraging separator-based decomposition.

pith-pipeline@v0.9.0 · 5829 in / 1482 out tokens · 24158 ms · 2026-05-20T22:40:58.792814+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.