Source-linked AI summary
Scalable Gromov-Wasserstein Learning for Graph Partitioning and Matching
Hongteng Xu, Dixin Luo, Lawrence Carin
TL;DR
The paper addresses the limited scalability of Gromov-Wasserstein methods for large-scale graph analysis. It proposes S-GWL, which unifies matching and partitioning through optimal transport and learned barycenter graphs, using recursive partitioning and regularized optimization. The method achieves large-scale analysis with reported accuracy-efficiency trade-offs and outperforms state-of-the-art methods in many situations.
Problem
Gromov-Wasserstein methods have theoretical appeal for graph analysis but are often impractical at large scale because of computational limitations.
Method
S-GWL combines GW-based optimal transport, disconnected or learned barycenter graphs, recursive K-partitioning, and a regularized proximal gradient method.
Results
The approach unifies large-scale graph partitioning and matching, outperforms state-of-the-art methods in many situations, and achieves O(K(E + V) log_K V) time complexity for graphs with V nodes and E edges.
Takeaways & Limitations
GW discrepancy can serve as a common optimization basis for graph matching, partitioning, and multi-graph analysis at large scale.
Takeaways & Limitations
S-GWL is sensitive to hyperparameters, with γ, a, and b requiring careful settings; large graphs generally require large γ and many iterations.
Abstract
from arXiv · showhide
We propose a scalable Gromov-Wasserstein learning (S-GWL) method and establish a novel and theoretically-supported paradigm for large-scale graph analysis. The proposed method is based on the fact that Gromov-Wasserstein discrepancy is a pseudometric on graphs. Given two graphs, the optimal transport associated with their Gromov-Wasserstein discrepancy provides the correspondence between their nodes and achieves graph matching. When one of the graphs has isolated but self-connected nodes ($i.e.$, a disconnected graph), the optimal transport indicates the clustering structure of the other graph and achieves graph partitioning. Using this concept, we extend our method to multi-graph partitioning and matching by learning a Gromov-Wasserstein barycenter graph for multiple observed graphs; the barycenter graph plays the role of the disconnected graph, and since it is learned, so is the clustering. Our method combines a recursive $K$-partition mechanism with a regularized proximal gradient algorithm, whose time complexity is $\mathcal{O}(K(E+V)\log_K V)$ for graphs with $V$ nodes and $E$ edges. To our knowledge, our method is the first attempt to make Gromov-Wasserstein discrepancy applicable to large-scale graph analysis and unify graph partitioning and matching into the same framework. It outperforms state-of-the-art graph partitioning and matching methods, achieving a trade-off between accuracy and efficiency.
1 Introduction
The paper develops S-GWL to make Gromov-Wasserstein analysis scalable and to unify graph partitioning, matching, and their multi-graph extensions. A recursive partitioning strategy and regularized optimization support large-scale computation while experiments report competitive accuracy-efficiency trade-offs.
- Gromov-Wasserstein discrepancy provides node correspondence through optimal transport and supports graph matching between distinct graphs.
- Graph partitioning is formulated by comparing an observed graph with a disconnected graph, whose optimal transport reveals node clusters.
- A learned Gromov-Wasserstein barycenter graph extends the framework to multi-graph matching and partitioning through indirect transport-based correspondences.
- S-GWL recursively applies K-way partitioning and uses regularized proximal gradient updates to improve scalability for sparse large graphs.
- O(K(E + V) log_K V) time complexity supports large-scale analysis, while experiments report a trade-off between accuracy and efficiency.
2 Graph Analysis Based on Gromov-Wasserstein Learning
The GWL framework uses Gromov-Wasserstein optimal transport to represent node correspondences, graph partitions, and multi-graph alignments. A disconnected graph encodes clusters, while a learned barycenter graph provides a shared reference for multiple observed graphs.
- A measure graph consists of nodes, an adjacency matrix, and a Borel probability measure over nodes.
- GW discrepancy compares graph relations and returns an optimal transport that acts as a joint distribution over nodes in the two graphs.
- Graph matching: For graph matching, transport entries represent node assignments between source and target graphs.
- Graph partitioning: K-way partitioning compares an observed graph with a disconnected graph of K isolated self-connected nodes, assigning each node to the cluster indicated by its largest transport entry.
- Multi-graph matching: A Gromov-Wasserstein barycenter minimizes weighted discrepancy to observed graphs and serves as a reference for matching nodes across multiple graphs.
- Multi-graph partitioning: For multi-graph partitioning, a barycenter initialized with K isolated nodes is learned so that nodes transported to the same barycenter node share a cluster.
3 Scalable Gromov-Wasserstein Learning
The paper scales GWL through regularized proximal-gradient optimization and recursive K-way decomposition, reducing complexity while supporting graph matching and partitioning.
- 3.1 Regularized proximal gradient method: The GWL framework uses a regularized proximal gradient method to solve successive convex subproblems and obtain stable optimal transports.The KL divergence is used as a proximal term, and Sinkhorn-Knopp solves each subproblem.
- 3.1 Regularized proximal gradient method: Node-based regularization incorporates differences in node distributions to directly encourage similarity between nodes during optimal-transport learning.The cost matrix uses cij = |µs_i − µt_j|, with τ controlling the regularizer’s significance.
- 3.1 Regularized proximal gradient method: The barycenter graph is learned by alternating between optimal-transport updates for observed graphs and adjacency-matrix updates.Its weights, node count, and node distribution are predefined, while the adjacency matrix is updated iteratively.
- 3.2 A recursive K-partition mechanism for large-scale graph matching: The recursive K-partition mechanism decomposes large graphs into aligned sub-graph pairs, then applies barycenter-based matching recursively.At each recursion, corresponding subgraphs are extracted from the jointly partitioned observed graphs.
- 3.2 A recursive K-partition mechanism for large-scale graph matching: O(MK(E + V) log_K V) time and O(M(E + V/K)) memory are achieved for M graphs with V nodes and E edges.The complexity follows from recursive decomposition and smaller aligned subgraph pairs.
- 3.2 A recursive K-partition mechanism for large-scale graph matching: S-GWL is consistently faster than GWL across configurations varying the partition count K and recursion count R.Figure 2(b) visualizes runtime comparisons on synthetic graph matching.
4 Related Work
Related work establishes GW discrepancy as a tool for relational matching and graph analysis, while prior large-scale graph applications remain computationally challenging.
- 4 Related Work: GW discrepancy has supported matching problems including 3D-object registration and cross-language vocabulary matching.Prior extensions also combine GW discrepancy with Wasserstein discrepancy, node embeddings, or adversarial learning.
- 4 Related Work: Existing graph partitioning methods heuristically explore node clustering through modularity maximization, while graph matching supports network alignment and object registration.The paper positions GWL as a unified framework for these two graph-analysis problems.
5 Experiments
Experiments evaluate GWL and S-GWL for graph partitioning, two-graph matching, and multi-graph matching against established baselines on synthetic and real-world data. The methods generally achieve strong accuracy, robustness to noise, and improved efficiency, with S-GWL offering a favorable accuracy–runtime trade-off.
- Graph partitioning: GWL consistently outperforms partitioning baselines on AMI and is faster than most competitors except Metis.Its runtime is especially competitive on sparse graphs, where E = O(V log V).
- Graph partitioning: On real-world partitioning datasets, GWL is at least comparable on raw data and more robust to noise than other methods.The evaluation adds 10% noisy inter-community edges to email and village networks.
- Two-graph matching: On synthetic matching tasks, GW discrepancy-based methods achieve higher node correctness than heuristic methods.GWL+Emb has the highest node correctness, while GWL is about 10 times faster and S-GWL further accelerates it.
- Two-graph matching: S-GWL achieves high node correctness with runtime comparable to the fastest matching methods, including HubAlign and NETAL.The recursive mechanism provides additional acceleration over the original GWL framework.
- Two-graph matching: On real-world matching tasks, GW discrepancy-based methods outperform others in node correctness, especially for highly noisy graphs.S-GWL achieves a good trade-off between accuracy and efficiency.
- Multi-graph matching: For multi-graph matching on yeast networks, GWL and S-GWL obtain performance comparable to MultiAlign on three-graph matching, with GWL performing best.Several alternative methods are impractical for the evaluated graph sizes because of time or memory requirements.
6 Conclusion and Future Work
S-GWL provides a theoretically supported unified framework for large-scale graph partitioning and matching, but its performance depends sensitively on hyperparameter settings.
- S-GWL unifies large-scale graph partitioning and matching within a theoretically supported Gromov-Wasserstein learning framework.
- S-GWL is sensitive to hyperparameters, particularly γ, a, and b, which significantly influence performance.For large-scale graphs, γ generally must be large and solving the associated problem requires many iterations.
- Future work will study how hyperparameters affect convergence and adapt their settings to observed data.
- The method’s decomposition of large graphs into independent small graphs may support further acceleration through parallel processing or distributed learning.
A.1 The GWL framework for different tasks
The GWL framework implements graph matching and partitioning through proximal-gradient optimal transport, recursively applying K-way partitioning for scalable multi-graph processing.
- Graph matching: Graph matching computes a proximal-gradient transport and assigns each source node to the target node with maximum transport value.
- Graph partitioning: Graph partitioning constructs a K-node disconnected graph, computes transport to it, and assigns each input node to its highest-transport cluster.
- Multi-graph matching: Multi-graph matching initializes equal graph weights and aggregates node correspondences across graphs through shared transport assignments.
- Recursive S-GWL: S-GWL recursively applies multi-graph K-partitioning for R recursions, then performs two-graph or multi-graph matching on the resulting graph sets.
A.3 Detailed complexity analysis for GWL and S-GWL
Recursive partitioning reduces GWL’s graph-scale computations, yielding S-GWL time complexity O(MK(E + V) log_K V) and memory complexity O(M(E + VK)).
- GWL: O(VE) time and O(V^2) memory characterize two-graph GWL after sparse matrix multiplication and comparable-size assumptions.
- GWL: O(MVE) time and O(MV^2) memory characterize multi-graph GWL when graphs and the barycenter have comparable sizes.
- Partitioning: O(EsK + VsK) time and O(Es + VsK) memory characterize partitioning against a disconnected K-node target.
- Partitioning: O(MK(E + V)) time and O(M(E + VK)) memory characterize the multi-graph extension using a disconnected target.
- S-GWL: The recursion’s final subgraphs have size O(V/K^R), and terminal matching computations can be ignored when K^R is comparable to V.
- S-GWL: O(MK(E + V) log_K V) overall time and O(M(E + VK)) memory result from recursive barycenter computation across ⌊log_K V⌋ recursions.The analysis retains edge-related terms in one setting because Es can be comparable to VsK even for sparse graphs.
A.4 Usefulness of node prior
Node priors improve the convergence behavior of the regularized proximal-gradient method for computing Gromov-Wasserstein discrepancy.
- Fewer iterations and lower GW discrepancy are achieved by the node-prior regularized proximal method on two synthetic 1,000-node graphs.Its convergence is reported as faster than both the entropy-based method in and the vanilla proximal-gradient method in [49].
B.1 Implementation details
The experiments document baseline implementations and hyperparameter handling, while emphasizing non-uniform node distributions for multi-graph partitioning and matching.
- Baseline implementations: The evaluation uses C and Python implementations of graph partitioning and graph matching baselines.The listed partitioning baselines include Metis, FastGreedy, Louvain, and Fluid; matching baselines include PISwap, GHOST, MI-GRAAL, MAGNA++, HubAlign, NETAL, and CPD+Emb.
- Hyperparameters: Baseline methods run with default settings, while GWL and S-GWL hyperparameters are set empirically across experiments.The corresponding experiment-specific settings are reported in Table 6.
- Node distributions: Non-uniform node distributions are important for S-GWL, especially in multi-graph partitioning and matching.For multi-graph partitioning, the barycenter adjacency matrix is initialized diagonally and its node distribution is estimated from observed graphs.
- Node distributions: Degree-based node distributions improve partitioning consistency across different graphs.Uniform distributions can initialize the barycenter with [0.5, 0.5]^⊤ and 0.5I_2, creating an identification problem in the described case.
B.2 Performance on some challenging cases
The method performs strongly on Gaussian partition graphs but encounters reduced node correctness and weaker acceleration on challenging Barabási–Albert and incomparable-graph cases.
- Barabási–Albert graphs: S-GWL’s strong averaged matching performance is mainly driven by Gaussian partition graphs, where it achieves high node correctness and near-fastest runtime.The reported average covers ten trials: five Gaussian random partition graphs and five Barabási–Albert graphs.
- Barabási–Albert graphs: On Barabási–Albert graphs, GW discrepancy-based methods outperform many baselines but trail state-of-the-art methods in node correctness.This gap is reported in Figure 4(b).
- Barabási–Albert graphs: Unequal recursive sub-graph sizes reduce S-GWL’s acceleration on Barabási–Albert graphs to about 10–20 times.The largest sub-graph determines runtime, compared with over 100 times acceleration for more balanced Gaussian partitions.
- Incomparable graphs: Matching incomparable graphs degrades GW discrepancy-based performance, illustrated by yeast and human PPI networks with 2,340 and 9,141 nodes.The supplied passage introduces this setting as common in bioinformatics; Table 7 reports edge-correctness comparisons.
- Incomparable graphs: GWL and S-GWL outperform most competitors except HubAlign and NETAL in the reported incomparable-graph experiments.The stated explanation is that optimal-transport constraints oversmooth correspondences when the target graph is much larger.