Gromov-Wasserstein Learning for Graph Matching and Node Embedding

Abstract

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.

References in corpus (9)

• Adam: A Method for Stochastic Optimization
• BPR: Bayesian Personalized Ranking from Implicit Feedback
• Point-Set Registration: Coherent Point Drift
• Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration
• Adversarial Text Generation via Feature-Mover's Distance
• Triangular Alignment (TAME): A Tensor-based Approach for Higher-order Network Alignment
• Unsupervised Alignment of Embeddings with Wasserstein Procrustes
• Distilled Wasserstein Learning for Word Embedding and Topic Modeling
• Fused Gromov-Wasserstein distance for structured objects: theoretical foundations and mathematical properties

Cited by in corpus (26)

• Metrics for Graph Comparison: A Practitioner's Guide
• Space-Time Correspondence as a Contrastive Random Walk
• Wasserstein Weisfeiler-Lehman Graph Kernels
• Scalable Gromov-Wasserstein Learning for Graph Partitioning and Matching
• Scalable Optimal Transport Methods in Machine Learning: A Contemporary Survey
• A Survey on Optimal Transport for Machine Learning: Theory and Applications
• Generalized Spectral Clustering via Gromov-Wasserstein Learning
• Fast and Robust Comparison of Probability Measures in Heterogeneous Spaces
• Finding Heterophilic Neighbors via Confidence-based Subgraph Matching for Semi-supervised Node Classification
• Graph Matching with Partially-Correct Seeds
• Linear-Time Gromov Wasserstein Distances using Low Rank Couplings and Costs
• Gromov-Wasserstein Factorization Models for Graph Clustering
• CAPER: Coarsen, Align, Project, Refine - A General Multilevel Framework for Network Alignment
• Flow-based Alignment Approaches for Probability Measures in Different Spaces
• COPT: Coordinated Optimal Transport for Graph Sketching
• Fused Gromov-Wasserstein Alignment for Hawkes Processes
• Interpretable ICD Code Embeddings with Self- and Mutual-Attention Mechanisms
• Sketching Merge Trees for Scientific Data Visualization
• Unsupervised Learning of Graph Hierarchical Abstractions with Differentiable Coarsening and Optimal Transport
• Approximating Optimal Transport via Low-rank and Sparse Factorization
• Sliced Multi-Marginal Optimal Transport
• Aligning Time Series on Incomparable Spaces
• Hawkes Processes on Graphons
• Density of States Graph Kernels
• Balanced Coarsening for Multilevel Hypergraph Partitioning via Wasserstein Discrepancy
• A Hypergradient Approach to Robust Regression without Correspondence