CS Paper Radar

Graph Similarity Meets Optimal Transport

Jens Breitung, Timo Gervens, Martin Grohe

cs.DM ·submitted 2026-11-03 15:16 UTC · v2
theoryhot direction

Abstract

A natural way to compare two graphs is to align their vertex sets by a bijection and to measure the difference of the aligned adjacency matrices in a matrix norm. Depending on the norm, this yields, for example, the edit distance, the cut distance, the spectral distance, and the local edit distance. To make these distances applicable to graphs of different order, one can consider blowups of the graphs or, equivalently, relax bijections to fractional alignments, that is, optimal transport plans between the uniform distributions on the vertex sets, in the spirit of Gromov-Wasserstein distances. We investigate how much the optimal transport versions can differ from their bijective counterparts, that is, we quantify their integrality gaps. For the edit distance, we improve the best known upper bound on the integrality gap from 3 to 2 and the lower bound from 6/5 to 4/3. For the cut distance, we approach Lovász's conjecture that $δ_\square \le 2δ_\square^{\rm OT}$ from both sides. We improve the previously best known upper bound $δ_\square \le 32 \cdot (δ_\square^{\rm OT})^{1/67}$ (Borgs, Chayes, Lovász, Sós and Vesztergombi, Adv. Math. 2008) to $δ_\square \le C_\varepsilon \cdot (δ_\square^{\rm OT})^{1-\varepsilon}$ for every $\varepsilon > 0$, and we construct graphs $G,H$ with $δ_\square(G,H) = 2δ_\square^{\rm OT}(G,H)$, establishing a factor-2 lower bound that matches Lovász's conjecture. For the local edit and spectral distances, we obtain upper bounds of order $\sqrt{t\ln(1/t)}$ and $\sqrt{t}$, respectively, where $t$ is the corresponding optimal transport distance, and we show that, unlike for the edit and cut distances, no linear upper bounds are possible. Finally, we show that computing the optimal transport distances is NP-hard, and we give hardness of approximation results for the cut, spectral, and local edit distances.

Comment
v2: fixed typos and broken link to Lean repository

Closest papers

Nearest neighbours by meaning across the whole index.

Optimal Transport for Network Comparison: A Unified Review with New Spectral Bounds and Machine Learning Applications

cs.LG stat.MLcs.SI ·2026-08-27 ·James Hyun, François G. Meyer
theory similarity 0.74
Abstract

Network comparison using optimal transport is a growing area of research in network science. Unlike standard graph metrics, optimal transport computes both network dissimilarity and a transport plan that explains how one graph morphs into another. In this paper, we review how optimal transport compares undirected, unweighted simple graphs using three primary distances: the Wasserstein, Gromov-Wasserstein, and Bures-Wasserstein distances. We examine the closed form of the Wasserstein distance in one dimension via node feature probability distributions, and show how the transport plans of the Wasserstein and Gromov-Wasserstein distances visualize how mass is shifted to transform one network into another. Beyond reviewing existing transport-based approaches, we establish new spectral lower and upper bounds for the Bures-Wasserstein distance and characterize the tightness of the lower bound under eigenbasis perturbations. Finally, we evaluate these distances using a synthetic network dataset for clustering and a real-world temporal network.

0.17

Graph Distortion Distances, Gromov-Hausdorff and the Hardness of Gromov-Wasserstein

cs.DM cs.CCmath.CO ·2026-10-12 ·Jens Breitung, Timo Gervens, Julius Pörzgen
similarity 0.68
Abstract

We study the computational complexity of graph distortion distances, a family of graph metrics measuring how vertex distances differ between two graphs. Formally, these distances are defined in terms of standard matrix norms on the difference of distance matrices under an optimal vertex alignment. The resulting metrics have natural interpretations, corresponding to three ways of measuring the distortion of shortest-path distances: the maximum distortion among all vertex pairs (entrywise maximum norm), global aggregation (entrywise $p$-norms), and local aggregation (operator $p$-norms) of distortions. For maximum distortion, we show that approximation below a factor of two is NP-hard even for highly restricted trees. Due to the close connection to the Gromov-Hausdorff distance, we obtain a similar hardness result for the latter. In both cases, we show essentially optimal additive inapproximability. On the algorithmic side, we give a subcubic-time algorithm for optimal embeddings of connected graphs into paths, based on a structural decomposition along a diametral path. Additionally, we give a simple approximation algorithm when one input graph has a "relatively path-like" metric structure, i.e. has bounded pathlength. For local and global distortion, we derive various hardness results even for restricted inputs. Making use of a close connection between the global distortion distances and Gromov-Wasserstein distances, we give the first formal proof of NP-hardness of the latter, which has been claimed in the literature many times but has, to the best of our knowledge, never been correctly proven.

0.52

Discrete Gromov-Wasserstein Duality: Algorithms and Isomorphism Testing

cs.IT math.STmath.OCstat.ML ·2026-09-02 ·Gabriel Rioux, Joanna Marks, Riccardo Passeggeri, Ziv Goldfeld
similarity 0.67
Abstract · 72 pages, 6 figures, 1 table

The Gromov-Wasserstein (GW) distance provides a principled framework for aligning metric measure (mm) spaces based solely on their intrinsic structure. Its ability to identify isomorphic representations of distributions across spaces renders it valuable for comparing data where equality up to isomorphism occurs naturally such as in graphs or, more generally, distributions on graphs. Recently, a type of dual form for the GW distance between Euclidean distributions with the squared Euclidean or inner product costs was derived, spurring the development of new statistical and algorithmic results for this setting. This work furnishes a novel duality result for GW distances with and without entropic regularization that is applicable to all finitely supported mm spaces. Leveraging this result, we derive the sample complexity of empirical GW distances between finite mm spaces, as well as limit distributions under proper centering and scaling. Furthermore, we propose new algorithms for solving the regularized GW problem which are subject to formal convergence guarantees. These statistical and algorithmic advancements give rise to a principled and efficient framework for testing whether two distributions on the set of graphs with a fixed number of nodes are isomorphic based on samples.

0.34

Unlocking Geodesic Gromov-Wasserstein Distances for 3D Modeling

cs.CV cs.DSeess.IV ·2026-09-26 ·Krzysztof Marcin Choromanski, Derek Long, Ananya Parashar, Dwaipayan Saha
similarity 0.65
Abstract

\textit{Gromov-Wasserstein Distances} (GWDs) provide quantitative ways of comparing probabilistic distributions defined on different metric spaces by applying techniques from the optimal transport theory. As such, GWD can be potentially useful in a large variety of applications ranging from graph matching problems to 3D object detection. However its practical use at scale is significantly limited by cubic time complexity computations involving dense intra-space distance matrices. Even though in the Euclidean metric spaces several techniques (e.g. involving scalable kernel methods) were proposed to address it, to the best of our knowledge, analogous techniques for general geodesic distances on manifolds, or shortest-path distance on graphs in their discretized variants, were not developed. In this paper, we present \textbf{E}fficient \textbf{G}eodesic \textbf{Gro}mov-\textbf{W}asserstein methods (EGGroW), a new class of efficient algorithms designed to calculate geodesic Gromov-Wasserstein distances with entropic Sinkhorn-like approaches, leveraging recently introduced \textit{GenusSink} methods \citep{genussink} and the theory of random features. We provide important downstream applications, namely: 3D pose estimation and 3D template detection. In the latter setting, we formulate a partial 3D template recovery as a staged problem: capacity-constrained scene selection is followed by semi-relaxed recovery of template visibility and correspondence. Our empirical findings show that EGGroW provides accurate solutions when standard Euclidean-based techniques fail and is characterized by light computational footprint, as our theoretical analysis predicts.

0.25

Computing All Optimal Partial $p$-Wasserstein Matchings on the Line

cs.CG cs.DS ·2026-08-19 ·Sebastian Angrick, Jacobus Conradi, Mónika Csikós, Niko Hastrich, Danny Mittal +3 more
theorycode/data similarity 0.63
Abstract

For $p \ge 1$, the $p$-Wasserstein distance measures the minimum cost of transporting probability mass between distributions, where moving unit mass between two points costs the $p$th power of their distance. For discrete distributions in one dimension, full transport is especially simple: after sorting, mass is matched in order along the line. By contrast, partial and unbalanced transport on the line remains much less understood. Recently, Chapel and Tavenard [ICLR'25] showed that, for $p=1$, all optimal partial transport plans between distributions supported on $n$ points, with uniform mass at each point, can be computed in $O(n\log n)$ time by exploiting the metric structure of the cost. For $p>1$, this structure no longer applies, and existing approaches require $Ω(n^2)$ time. Our main contribution is an FFT-based data structure for balanced-interval transport queries, which bypasses this quadratic bottleneck and yields an $O(p\,n\log^2 n)$-time algorithm for computing all optimal partial transports on the line for every finite $p\ge 1$. We also provide an open-source C++ implementation that outperforms the state-of-the-art baseline on a range of synthetic instances. Finally, we establish a conditional lower bound for $p=\infty$: any subquadratic-time algorithm for computing all optimal partial transport plan costs on the line would violate the $(\min,+)$-Convolution Hypothesis. This separates the problem from full optimal transport, which is solvable in $O(n\log n)$.

0.25

A Cheeger Inequality for Hypergraphs and Its Applications

cs.DS math.CO ·2026-09-14 ·Raj Kamal, Amitabha Bagchi
similarity 0.63
Abstract

Hypergraphs provide a natural framework for modeling higher-order relationships, but the development of spectral techniques with provable guarantees for general non-uniform hypergraphs remains challenging. Building on Banerjee's normalized adjacency matrix and Spiro's averaging-based diffusion framework, we develop a spectral framework for non-uniform hypergraphs and establish Cheeger's inequality for their conductance. A fundamental result in the spectral theory of hypergraphs asserts that, for every non-covering hypergraph, the second-smallest eigenvalue of its normalized Laplacian is at most one. This spectral characterization yields an improved Cheeger's inequality for non-covering hypergraphs, and we show that the resulting inequality is tight on both sides using cycle and cube hypergraphs. Our framework further yields higher-order Cheeger inequalities and provides theoretical guarantees for Fiedler's spectral partitioning algorithm, all in the setting of hypergraphs. Finally and most notably, we construct a new family of optimal hypergraph expanders that is tight for the Alon-Boppana bound.

0.24

Unsupervised Multi-Scale Gromov-Wasserstein Hypergraph Alignment

cs.LG cs.SI ·2026-08-30 ·Lutz Oettershagen, Honglian Wang, Aristides Gionis
top venue similarity 0.62
Abstract · Accepted at ICDM 2026

We study unsupervised hypergraph alignment, where the goal is to infer node correspondences between two hypergraphs using only structural information, without node features, labels, seed matches, or side information. Direct higher-order formulations can represent hyperedge interactions faithfully, but they can be computationally demanding and cumbersome for non-uniform hypergraphs. Graph-reduction approaches introduce a different challenge: clique expansions keep the alignment problem on the original node set but collapse all hyperedge evidence into one pairwise graph, whereas bipartite expansions preserve incidence structure but enlarge the problem from nodes to nodes plus hyperedges. We introduce FALCON (Filtration-based hypergrAph aLignment via Cross-scale Optimal traNsport), an unsupervised optimal-transport framework for hypergraph alignment. Instead of representing each hypergraph by a single collapsed clique graph, FALCON constructs a filtration-induced sequence of clique-based co-occurrence dissimilarity matrices and jointly aligns all levels through one shared multi-scale Gromov--Wasserstein (GW) objective. The shared transport plan enforces a globally consistent node correspondence across filtration levels while avoiding the auxiliary hyperedge nodes introduced by bipartite expansion. Experiments on perturbation benchmarks derived from real-world hypergraphs show that FALCON is robust to structural noise and in almost all cases outperforms strong graph- and hypergraph-alignment baselines.

0.43

Optimal Passes and Perfect Sampling for Similarity Graph Statistics

cs.DS ·2026-09-17 ·Qin Zhang
hot direction similarity 0.62
Abstract · 32 pages

We study statistical estimation on implicit weighted similarity graphs presented as node-arrival streams. Previous work~\cite{LZ26b} obtained constant-pass, sublinear-space algorithms for several basic statistics of such graphs, including the diversity index $\mathsf{DI}=\sum_i d_i^{-1}$ and the degree moments $M_p=\sum_i d_i^p$ for $p>0$, together with their associated sampling problems $L_{\mathsf{DI}}$ and $L_{M_p}$. We settle three questions left unresolved by the previous work. First, we show that any two-pass streaming algorithm that $1.1$-approximates $\mathsf{DI}$ requires $Ω(n)$ bits of space; combined with the three-pass $\tilde{O}(\sqrt n)$-space algorithm of~\cite{LZ26b}, this establishes a sharp transition between two and three passes for $\mathsf{DI}$. Second and third, for every fixed $c>0$ we give a three-pass $n^{-c}$-perfect $L_{\mathsf{DI}}$-sampler using $O_c(\sqrt n\log n)$ words and a two-pass $n^{-c}$-perfect $L_{M_p}$-sampler using $O_{p,c}(n^{1-1/(p+1)}\log n)$ words. Matching lower bounds up to polylogarithmic factors show that both the number of passes and the polynomial dependence on $n$ are optimal.

0.44