Scalable Gromov-Wasserstein Learning for Graph Partitioning and Matching

• Gromov-Wasserstein discrepancy provides node correspondence through optimal transport and supports graph matching between distinct graphs.Source: §1 · p. 1
• Graph partitioning is formulated by comparing an observed graph with a disconnected graph, whose optimal transport reveals node clusters.Source: §1 · pp. 1–2
• A learned Gromov-Wasserstein barycenter graph extends the framework to multi-graph matching and partitioning through indirect transport-based correspondences.Source: §1 · p. 2
• S-GWL recursively applies K-way partitioning and uses regularized proximal gradient updates to improve scalability for sparse large graphs.Source: §1 · p. 2
• O(K(E + V) log_K V) time complexity supports large-scale analysis, while experiments report a trade-off between accuracy and efficiency.Source: §1 · p. 2

• A measure graph consists of nodes, an adjacency matrix, and a Borel probability measure over nodes.Source: §2 · p. 2
• GW discrepancy compares graph relations and returns an optimal transport that acts as a joint distribution over nodes in the two graphs.Source: §2.1 · pp. 2–3

Graph matching

• For graph matching, transport entries represent node assignments between source and target graphs.Source: §2.1 · p. 3

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.Source: §2.1 · p. 3

Multi-graph matching

• A Gromov-Wasserstein barycenter minimizes weighted discrepancy to observed graphs and serves as a reference for matching nodes across multiple graphs.Source: §2.2 · p. 3

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.Source: §2.2 · p. 3

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.Source: §3 · p. 3, §3.1 · pp. 3–4
• 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.Source: §3.1 · p. 4
• 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.Source: §3.1 · p. 4

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.Source: §3.2 · p. 5
• 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.Source: §3.2 · p. 5
• 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.Source: §3.2 · pp. 5–6, Figure 2 · p. 6

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.Source: §4 · p. 6
• 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.Source: §4 · p. 6

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).Source: §5.1 · p. 7
• 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.Source: §5.1 · p. 7

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.Source: §5.2 · p. 7
• 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.Source: §5.2 · p. 7
• 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.Source: §5.2 · p. 8

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.Source: §5.2 · p. 8

• S-GWL unifies large-scale graph partitioning and matching within a theoretically supported Gromov-Wasserstein learning framework.Source: §6 · p. 8
• 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.Source: §6 · p. 8
• Future work will study how hyperparameters affect convergence and adapt their settings to observed data.Source: §6 · p. 8
• The method’s decomposition of large graphs into independent small graphs may support further acceleration through parallel processing or distributed learning.Source: §6 · p. 8

Graph matching

• Graph matching computes a proximal-gradient transport and assigns each source node to the target node with maximum transport value.Source: §A.1 · p. 12

Graph partitioning

• Graph partitioning constructs a K-node disconnected graph, computes transport to it, and assigns each input node to its highest-transport cluster.Source: §A.1 · p. 12

Multi-graph matching

• Multi-graph matching initializes equal graph weights and aggregates node correspondences across graphs through shared transport assignments.Source: §A.1 · p. 12

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.Source: §A.2 · p. 13

GWL

• O(VE) time and O(V^2) memory characterize two-graph GWL after sparse matrix multiplication and comparable-size assumptions.Source: §A.3 · p. 13
• O(MVE) time and O(MV^2) memory characterize multi-graph GWL when graphs and the barycenter have comparable sizes.Source: §A.3 · p. 13

Partitioning

• O(EsK + VsK) time and O(Es + VsK) memory characterize partitioning against a disconnected K-node target.Source: §A.3 · p. 13
• O(MK(E + V)) time and O(M(E + VK)) memory characterize the multi-graph extension using a disconnected target.Source: §A.3 · p. 13

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.Source: §A.3 · p. 14
• 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.Source: §A.3 · pp. 13–14

• 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].Source: §A.4 · p. 14

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.Source: §B.1 · pp. 14–15

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.Source: §B.1 · p. 15, Table 6 · p. 15

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.Source: §B.1 · p. 15
• 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.Source: §B.1 · p. 15

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.Source: §B.2 · p. 15
• 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).Source: §B.2 · p. 15
• 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.Source: §B.2 · p. 15

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.Source: §B.2 · p. 15, Table 7 · p. 16
• 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.Source: §B.2 · p. 16