In this paper, we introduce GenusSink, a new class of approximate generalized Sinkhorn algorithms for bounded genus (e.g., planar) graphs with shortest-path distance costs, providing near-linear:
- Pre-processing
- Iteration step
- Final transport plan matrix querying
and near-linear memory usage. The graphs handled by GenusSink particularly include planar graphs and bounded-genus meshes approximating 3D objects. The algorithm addresses the 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, specifically utilizing Fourier analysis and low displacement rank theory.
It is inspired by recent breakthroughs in graph theory regarding approximating bounded genus metrics with small treewidth metrics. The graph-centric approach allows us to target the optimal transport problem with corresponding distributions defined on the manifolds approximated by weighted graphs, with cost functions given by geodesic distances. We conduct rigorous theoretical analysis of GenusSink, provide practical implementations leveraging the newly introduced 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 compared to the baseline. As a by-product of the developed methods, we show that GenusSink is numerically equivalent to the brute-force geodesic Sinkhorn algorithm on $n$-vertex graphs with treewidth $O(\log\log(n))$ (e.g., on trees).
Blogger's Review: The GenusSink algorithm significantly enhances the efficiency of generalized Sinkhorn algorithms on bounded genus graphs through innovative graph processing and mathematical theory. By combining geometric techniques with Fourier analysis, this algorithm not only holds theoretical importance but also offers higher computational accuracy for practical applications, showcasing the profound intersection potential of graph theory and computational geometry.