Scalable Gromov-Wasserstein Learning for Graph Partitioning and Matching

Abstract

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.

33rd Conference on Neural Information Processing Systems (NeurIPS 2019), Vancouver, Canada

References in corpus (5)

• Fast unfolding of communities in large networks
• Near linear time algorithm to detect community structures in large-scale networks
• Gromov-Wasserstein Learning for Graph Matching and Node Embedding
• Learning Generative Models across Incomparable Spaces
• Fused Gromov-Wasserstein distance for structured objects: theoretical foundations and mathematical properties

Cited by in corpus (9)

• Scalable Optimal Transport Methods in Machine Learning: A Contemporary Survey
• Learning Autoencoders with Relational Regularization
• Linear-Time Gromov Wasserstein Distances using Low Rank Couplings and Costs
• Gromov-Wasserstein Factorization Models for Graph Clustering
• Feature Robust Optimal Transport for High-dimensional Data
• Sliced Multi-Marginal Optimal Transport
• Online Graph Dictionary Learning
• Aligning Time Series on Incomparable Spaces
• Balanced Coarsening for Multilevel Hypergraph Partitioning via Wasserstein Discrepancy