Source-linked AI summary
Optimal Transport for Network Comparison: A Review with Machine Learning Applications
James Hyun, François G. Meyer
TL;DR
Graph comparison needs distances that handle non-Euclidean structure without costly alignment or NP-hard computation. This paper reviews Wasserstein, Gromov-Wasserstein, and Bures-Wasserstein approaches, combining closed forms, Sinkhorn computation, and transport-plan interpretation. The distances compare networks across sizes and expose structural changes, while experiments show limitations for node attributes and large high-dimensional graphs.
Problem
Existing graph distances can be NP-hard, depend on graph size, require alignment, or inadequately represent network structure.
Method
The paper maps graphs to empirical measures, graph signal distributions, and metric measure spaces, then applies Wasserstein, Bures-Wasserstein, and Gromov-Wasserstein distances.
Results
Transport plans reveal structural differences and anomalous nodes; in the feature experiment, bridge removal produced W1 ≈ 10.7881 versus W1 ≈ 0.0159 for intra-community removal.
Takeaways & Limitations
These transport distances support efficient comparison of differently sized networks while providing visual explanations of their dissimilarity.
Takeaways & Limitations
The distances fail to capture node-attribute differences in the clustering experiment, and large high-dimensional computation remains challenging.
Abstract
from arXiv · showhide
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 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 capture which specific nodes influence the distance after graph perturbation. For the Bures-Wasserstein distance, we derive bounds using Laplacian spectra to bypass full spectral decompositions. Finally, we evaluate these distances using a synthetic network dataset for clustering and a real-world time series network for anomaly detection.
1 Introduction
Graph comparison is important but difficult because graphs are non-Euclidean and many established distances are computationally expensive or require restrictive representations. Optimal transport is presented as a way to address these bottlenecks while providing practical network-comparison guidance.
- Graphs arise across many domains, making graph dissimilarity a central data-science problem.
- Gromov-Hausdorff-based graph distances are mathematically well-defined but NP-hard to compute.
- Vector- and matrix-based distances are easier to compute but may depend on graph size or require graph alignment.
- Graph edit and graphlet-based distances avoid some representation constraints but remain NP-hard to compute.
- Optimal transport has emerged as an approach intended to avoid these computational and representational bottlenecks in network comparison.
2 Optimal Transportation in Networks
The paper introduces graph representations and optimal-transport formulations for comparing networks. It covers transport plans, one-dimensional Monge maps, and Sinkhorn-based approximations for efficient computation.
- 2.1 Graph Theory: An undirected unweighted graph consists of nodes and edges, while its adjacency and Laplacian matrices encode connectivity and degree structure.The Laplacian is L = D − A, and its zero-eigenvalue multiplicity equals the number of connected components.
- 2.2 Optimal Transport: Optimal transport minimizes the cost of moving mass between probability spaces over feasible transport plans with prescribed marginals.A transport plan records how much mass moves between source and target bins.
- 2.2 Optimal Transport: Without mass splitting, the Kantorovich formulation becomes the Monge problem, which optimizes a transport map pushing one measure onto another.The resulting optimal map is called the Monge map.
- 2.2 Optimal Transport: With convex costs in one dimension, the Monge map has the closed form T = G^-1 ∘ F and is monotonic.F and G are the cumulative distribution functions of the source and target measures.
- 2.3 Sinkhorn Algorithm: The Sinkhorn algorithm approximates optimal transport plans by adding entropy regularization and solving through fixed-point iterations.Each stated iteration has quadratic time complexity, while variants approach near-linear time.
3 Transport Distances Between Networks
The paper compares networks through Wasserstein, Gromov-Wasserstein, and Bures-Wasserstein constructions, using node features, metric-measure spaces, and graph signal distributions. These distances provide closed forms or spectral bounds in selected settings, while revealing limitations such as feature-dependent sensitivity and permutation dependence.
- Wasserstein distance: The Wasserstein distance compares graphs as distributions of node features, so differing graph sizes pose no conceptual difficulty.The paper focuses on W1, which in one dimension equals the L1 distance between cumulative distribution functions and is computable after sorting.
- Wasserstein distance: Harmonic centrality makes W1 sensitive to perturbation placement: intra-community edge removal gives W1 ≈ 0.0159, versus W1 ≈ 10.7881 for bridge removal.The cumulative distributions nearly overlap for the intra-community removal but differ substantially after bridge removal.
- Wasserstein distance: For same-sized graphs using Laplacian eigenvalues as features, W1 remains constant regardless of which edge is removed.With one fewer edge and uniform empirical measures, the proposition gives W1(µG, µG1) = 2/n.
- Gromov-Wasserstein distance: Gromov-Wasserstein aligns metric-measure spaces by minimizing internal distance distortion, supports different dimensions or features, and generally lacks a closed-form Monge map.Its objective is nonconvex, although a one-dimensional closed form exists when the two supports have equal size.
- Bures-Wasserstein distance: Bures-Wasserstein compares zero-mean graph signal distributions built from Laplacian pseudoinverses and is the only discussed transport distance with a closed form in high dimensions.Unlike Gromov-Wasserstein, it is not invariant under node permutation; nevertheless, it can distinguish nonisomorphic isospectral graphs because zero distance requires identical Laplacians.
- Spectral bounds: The paper derives Bures-Wasserstein bounds for disconnected graphs and analyzes their asymptotics when Laplacian eigenbases are imperfectly aligned.For circulant graphs, shared Fourier eigenvectors support a specialized corollary; generally, the gap between the exact distance and a lower bound grows under perturbation.
4 Numerical Experiments
The experiments compare transport distances on synthetic networks for clustering and on weekly Enron email networks for anomaly detection. Results show similar clustering among several transport distances, while their time-series behavior differs across the Enron data.
- SYNTHIE clustering: 400 SYNTHIE networks with 90 or 100 nodes were clustered into four groups using pairwise distances and PAM.The dataset combines two structural types with two attribute types.
- SYNTHIE clustering: W1,h, W1,L, BW, and GW2 achieved almost the same clustering scores across the evaluated mathematical constructions.The clustering scores were evaluated with ARI, AMI, and V-measure.
- SYNTHIE clustering: Edit distance performed no better than random clustering, while W1,a using dataset node attributes failed to classify structural and attribute variations.The edit distance captures topology, whereas W1,a uses the dataset’s node attributes.
- Enron anomaly detection: W1 spiked in weeks without an event, GW2 remained flat, and BW changes appeared to track weeks with event labels.The normalized distances are plotted in Fig. 4.
- Enron anomaly detection: During the Dynegy–Enron event week, the normalized distances were W1 ≈ 0.4869, BW = 1, and GW ≈ 0.1447.The transport plans of W1 and GW2 were plotted for that week; BW’s map was omitted because it lacks an individual node-to-scalar mapping.
5 Discussion
The discussion contrasts the distances’ size and feature-space requirements and highlights transport plans as a way to inspect structural changes. It also identifies scalability and richer network embeddings as unresolved challenges.
- Scope and comparison: Wasserstein and Gromov-Wasserstein distances are independent of network size, whereas Bures-Wasserstein requires zero-padding Laplacian pseudoinverses to match dimensions.Wasserstein requires a shared metric space; Gromov-Wasserstein supports heterogeneous metric spaces.
- Scope and comparison: The distances classify topological differences but failed to capture node-attribute differences in the clustering experiment.This limitation is reported specifically for the evaluated clustering setting.
- Interpretability: Transport plans reveal mass shifts between nodes, helping pinpoint structural changes and identify key nodes in anomaly detection.This node-level interpretability distinguishes the transport approach from traditional graph metrics in the paper’s experiments.
- Open challenges: Computing these distances for large networks in high dimension remains a key challenge despite the one-dimensional closed form and Sinkhorn-based fast computation.The paper also identifies high-dimensional embeddings that capture both node attributes and graph topology as a future direction.
6 Conclusion
The paper adapts Wasserstein, Bures-Wasserstein, and Gromov-Wasserstein distances to network representations and uses transport plans and spectral bounds for comparison and interpretation.
- Network representations: Networks are mapped into empirical measures, graph signal distributions, and discrete metric measure spaces to adapt three transport distances.The mappings support Wasserstein, Bures-Wasserstein, and Gromov-Wasserstein comparison.
- Computation: Closed-form solutions or the Sinkhorn algorithm provide fast computation for the adapted distances.The paper’s Bures-Wasserstein treatment derives spectral bounds that bypass full Laplacian spectral decompositions.
- Interpretation: Transport plans highlight structural differences and identify nodes associated with anomalies, while enabling comparison of networks with different sizes.The Bures-Wasserstein distance does not provide a node-to-scalar transport map.
A.1 Proof of Proposition 1
The proof represents deleting one edge as a rank-1 Laplacian perturbation, then uses its spectrum to establish eigenvalue interlacing and a trace identity.
- Perturbed Laplacian: Removing edge (i,j) changes the Laplacian from L to L1 = L − (e_i − e_j)(e_i − e_j)^T.The vectors e_i and e_j are standard basis vectors.
- Perturbation spectrum: The outer-product perturbation has eigenvalues 2 and 0, with algebraic multiplicities 1 and n − 1, respectively.
- Eigenvalue interlacing: The eigenvalues of L1 interleave with those of L according to 1 ≤ λ′1 ≤ λ1 ≤ λ′2 ≤ λ2 ≤ … ≤ λ′n ≤ λn.
- Trace identity: The proof also obtains tr(L − L1) = 2 from the closed form for the perturbation.
A.2 Proof of Theorem 1
The proof bounds the Bures-Wasserstein distance by expressing Laplacian pseudoinverses through spectral decompositions, aligning eigenbases, and applying matrix inequalities.
- Spectral representation: The Laplacian pseudoinverses are written from the spectral decompositions L = UΛU^T and L1 = U1Λ1U1^T.
- Eigenbasis alignment: Defining O = U^T U1 rewrites the relevant matrix in terms of the eigenvalue matrices and an orthogonal transformation.
- Matrix inequality: The matrix Hardy-Littlewood-Pólya rearrangement inequality is applied to positive semidefinite matrices A = O(Λ1)^−1OT and B = Λ^−1.
- Distance bounds: The resulting eigenvalue inequalities are substituted into the Bures-Wasserstein distance to derive lower and upper bounds.
A.3 Proof of Theorem 2
The proof analyzes the gap between the Bures-Wasserstein distance and its lower bound when the eigenbasis transformation is close to identity.
- Perturbation assumption: Theorem 2 assumes U^T U1 = I + E with spectral norm ||E||2 = ϵ.
- Expansion: Substituting O = I + E expands the matrix into a baseline term plus terms involving E, ET, and the inverse square-root eigenvalue matrices.
- Bounding step: Triangle inequality and spectral-norm submultiplicativity bound the expansion, after which multiplying by 2 and summing yields the stated result.