Near-Linear Time Generalized Sinkhorn Algorithms for Bounded Genus Graphs
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).
Related
- Incidence Rank and Bounded Defect for Linear Hypergraphs with Cograph Line Graphs
- Annealed Sinkhorn with Momentum: Certified Unregularized Optimal Transport in Linear Memory
- Improved Algorithms for Beck--Fiala with Bounded Sets
- Approximation Algorithms for Maximum-Weight Degree-Bounded Forests
- On the ACC for Minimal Log Discrepancies for Bounded Generalized Sub-Pairs
BibTeX
@misc{choromanski2026nearlinear,
title = {{Near-Linear Time Generalized Sinkhorn Algorithms for Bounded Genus Graphs}},
author = {Krzysztof Choromanski and Derek Long and Ananya Parashar and Dwaipayan Saha},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2605.09782},
eprint = {2605.09782},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2605.09782},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Near-Linear Time Generalized Sinkhorn Algorithms for Bounded Genus Graphs
AU - Krzysztof Choromanski
AU - Derek Long
AU - Ananya Parashar
AU - Dwaipayan Saha
PY - 2026
DA - 2026/09/27
PB - arXiv
DO - 10.48550/arxiv.2605.09782
UR - https://arxiv.org/abs/2605.09782
AB - 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).
ER -