Source-linked AI summary
Gromov-Wasserstein Learning for Graph Matching and Node Embedding
Hongteng Xu, Dixin Luo, Hongyuan Zha, Lawrence Carin
TL;DR
Graph matching is difficult with noisy graphs, and node embedding and matching are often solved independently. The paper jointly learns node embeddings and optimal transport through a regularized Gromov-Wasserstein framework, solved with a proximal point method. The authors report superior performance across various matching tasks compared with alternative approaches.
Problem
Graph matching is NP-hard, sensitive to noisy edges, and commonly separated from node embedding despite their close relationship.
Method
The framework jointly learns node embeddings and optimal transport by minimizing a regularized Gromov-Wasserstein discrepancy, using a proximal point method.
Results
The authors report superior performance in various real-world graph matching tasks compared with alternative approaches.
Takeaways & Limitations
Joint learning makes graph matching and node embedding mutually beneficial and supports more robust matching of noisy graphs.
Takeaways & Limitations
The method’s matching strategy is affected by noisy observed interaction sets, motivating embedding-based regularization; its optimization can also be sensitive to hyperparameter γ under the Sinkhorn alternative.
Abstract
from arXiv · showhide
A novel Gromov-Wasserstein learning framework is proposed to jointly match (align) graphs and learn embedding vectors for the associated graph nodes. Using Gromov-Wasserstein discrepancy, we measure the dissimilarity between two graphs and find their correspondence, according to the learned optimal transport. The node embeddings associated with the two graphs are learned under the guidance of the optimal transport, the distance of which not only reflects the topological structure of each graph but also yields the correspondence across the graphs. These two learning steps are mutually-beneficial, and are unified here by minimizing the Gromov-Wasserstein discrepancy with structural regularizers. This framework leads to an optimization problem that is solved by a proximal point method. We apply the proposed method to matching problems in real-world networks, and demonstrate its superior performance compared to alternative approaches.
1. Introduction
The paper addresses graph matching and node embedding jointly through a Gromov-Wasserstein learning framework. It uses optimal transport to align graphs while learning embeddings that reflect graph topology and cross-graph correspondence.
- Motivation: Graph matching seeks correspondences across graphs but is NP-hard and vulnerable to noisy or unreliable edges.Traditional methods are often heuristic, and noisy observed interactions can produce unsatisfying matches.
- Motivation: Node embeddings approximate graph topology, yet graph matching and embedding are commonly treated independently.Single-graph embedding methods do not share information across graphs, while many matching methods ignore node embeddings.
- Proposed approach: The proposed framework jointly learns graph correspondences and node embeddings to improve both tasks.The framework measures graph dissimilarity using Gromov-Wasserstein discrepancy and learns an optimal transport between nodes.
- Proposed approach: Embedding distances are constrained to reflect within-graph topology and cross-graph correspondence indicated by optimal transport.The two learning processes mutually guide one another through the learned transport and embedding-based distances.
- Benefits: Joint learning uses embedding distances as complementary information to improve robustness on noisy graphs and avoids explicit transformations between graph embeddings.The authors report encouraging matching results compared with alternative approaches on real-world matching problems.
2. Gromov-Wasserstein Learning Framework
The framework represents graphs as metric-measure spaces, optimizes a Gromov-Wasserstein objective with embedding-based regularization, and derives node correspondences from optimal transport. Embeddings and transport are learned jointly so each informs the other.
- Graph representation: Each graph is represented by nodes, weighted interactions, a distance or dissimilarity matrix, and a degree-based empirical node distribution.The distribution reflects the probability of each node appearing in observed interactions.
- Gromov-Wasserstein discrepancy: Gromov-Wasserstein discrepancy compares within-graph pairwise distances relationally through an optimal transport coupling.The transport matrix preserves the node distributions as marginals and its entries encode matching probabilities.
- Regularized objective: The model jointly learns optimal transport and node embeddings, requiring embedding distances to remain close to observed graph distances.An optional cross-graph term uses partial correspondences when available.
- Regularized objective: Observed graph distances are combined with within-graph embedding distances, while cross-graph embedding distances contribute a Wasserstein discrepancy.The hyperparameter α controls the contribution of embedding-based distances.
- Interpretation: Embedding-based distances can suppress noise in data-driven distances, while transport values regularize embeddings by indicating which node pairs should be close.This makes graph matching and node embedding mutually beneficial within one framework.
3. Learning Algorithm
The method alternates between updating optimal transport and node embeddings within a nested optimization scheme. It uses proximal-point and gradient-based procedures, with distance design and complexity analyses supporting implementation and scalability.
- Optimization procedure: The algorithm alternates optimal-transport and embedding updates through nested outer and inner iterations.The outer loop updates embeddings-related quantities, while inner iterations update the target optimal transport.
- Optimization procedure: A KL-divergence proximal term regularizes optimal-transport updates, and projected gradient descent solves the resulting subproblem.With a suitable learning rate, the update is equivalent to an entropy-regularized optimal transport problem.
- Convergence: Every limit point generated by the proximal point method is a stationary point of the optimization problem.
- Solver comparison: An alternative Sinkhorn-based solver is more sensitive to the hyperparameter γ in convergence and numerical stability.The paper compares this alternative with the proximal point method in supplementary material.
- Implementation details: The embedding influence parameter α is initialized small and increased linearly across outer iterations because initial embeddings are unreliable.The schedule sets α_m according to the outer-iteration index and maximum number of outer iterations M.
- Distance design: The data-driven distance matrix assigns shorter distances to node pairs with many interactions, while cosine-based and RBF-based embedding distances are evaluated.The experiments report that both embedding-based distance choices work well across various matching tasks.
- Complexity and scalability: The loss matrix admits an efficient formulation for MSE/KL losses, while the reported complexity is O(V^3) for loss computation and O(V^2D) for embedding distances.The method can also use one-step Sinkhorn-Knopp projection in each inner iteration.
- Complexity and scalability: The proposed method has lower complexity than GRAAL variants, which require O(V^5), and its complexity is independent of the number of edges.Its complexity is reported as at least comparable to NETAL under the stated alternatives.
4. Related Work
The related-work literature spans Gromov-Wasserstein learning, graph matching, and node embedding. Prior methods address structural matching, cross-domain correspondence, and graph representation through distinct approaches.
- Gromov-Wasserstein learning: Gromov-Wasserstein discrepancy extends optimal transport to unregistered target domains and has been applied to shape, object, language, and network matching.
- Gromov-Wasserstein learning: Prior work includes Gromov-Wasserstein barycenters and fast Sinkhorn projection algorithms, as well as fused Gromov-Wasserstein distances.
- Graph matching: Graph matching methods for protein-interaction networks use local neighborhood information or global structural information.Examples include GRAAL variants, IsoRank, and MAGNA++.
- Node embedding: Representative node-embedding methods include LINE, DeepWalk, and node2vec, which commonly generate node sequences with random walks before learning embeddings.
5. Experiments
Experiments evaluate GWL on synthetic graph matching, real-world communication-network matching, and procedure recommendation. Across these settings, the method is tested against GWD and established alternatives, with results supporting robustness, stability, and improved matching or recommendation performance.
- Experimental setup: GWL is evaluated on synthetic and real-world matching tasks, with GWL-C, GWL-R, and the GWD baseline compared against state-of-the-art methods.The experiments use cosine- and RBF-based distances for GWL and compare them with GWD and established graph-matching methods.
- 5.1. Synthetic data: On synthetic graphs, GWL-C achieves almost 100% node correctness when the target graph is identical to the source, while GW discrepancy approaches zero.As target-graph noise increases, GW discrepancy increases accordingly, indicating greater graph dissimilarity.
- 5.1. Synthetic data: When synthetic target-graph noise exceeds 20%, GWL-C becomes much better than GWD, supporting improved robustness from learning node embeddings.At low noise, GWD is comparable to GWL-C; the advantage appears as q increases beyond 20.
- 5.1. Synthetic data: Embedding-based and optimal-transport-based node correctness are nearly identical on synthetic data, indicating that cross-graph embedding distances capture learned correspondences.The same correspondence consistency is observed as GW discrepancy decreases and node correctness increases over iterations.
- 5.2. MC3: Matching communication networks: On MC3 communication networks, GWL-R and GWL-C outperform alternatives across sparse and dense graph settings, where competing methods show inconsistent performance.For example, GRAAL performs similarly on sparse graphs but becomes much worse on dense graphs; GWD is sensitive to graph noise.
- 5.2. MC3: Matching communication networks: GWL shows good stability across initializations, while GW discrepancy decreases and both node-correctness measures increase and converge with outer iterations.The learned embeddings from different graphs occupy the same manifold, and overlapping embeddings indicate matched pairs.
- 5.3. MIMIC-III: Procedure recommendation: Clinical reviewers judged over 77.42% of disease–procedure pairs identified through learned transport as clearly related to treatments, side effects, or complications.The transport matrix is normalized, and pairs are selected using maximum transport or bTij > 0.15.
6. Conclusions and Future Work
The paper unifies graph matching and node-embedding learning through a Gromov-Wasserstein framework, reporting benefits for both objectives across matching tasks and identifying extensions for future work.
- The proposed Gromov-Wasserstein learning method unifies graph matching and node-embedding learning in a single framework.
- Joint learning is reported to benefit both graph matching and node embedding, yielding superior performance across various matching tasks.
- Future work includes extending the method to multi-graph matching, potentially involving Gromov-Wasserstein barycenters.
- The authors also plan to explore new Gromov-Wasserstein learning algorithms to improve scalability.
7. Supplementary Material
The supplementary material describes the proximal-point optimization, convergence guarantee, comparisons with Sinkhorn methods, synthetic and real-world experiments, and runtime and clinical-pair analyses.
- Optimization and convergence: The proximal point method decomposes the nonconvex problem into convex regularized optimal-transport updates solved using Sinkhorn projections.
- Optimization and convergence: Every limit point generated by the proximal point method is a stationary point of the original optimization problem.
- Connections and comparisons: The Sinkhorn method can achieve lower GW discrepancy at γ = 1e−3 and J = 1, but both methods risk numerical instability in that setting.
- Connections and comparisons: The proposed method is more robust to γ changes, balancing convergence and stability across a wider range than the Sinkhorn method.
- Runtime: Runtime was about 15 seconds for 100-node synthetic graphs and about 8 minutes for 622-node MC3 graphs on a CPU.
- Experiments: For synthetic data, the proposed method consistently outperforms the baseline method on node correctness.
- Experiments: In MIMIC-III, over 73.6% of disease–procedure pairs were judged reasonable as treatments or complications by clinical evaluation.