Scalable Gromov-Wasserstein Learning for Graph Partitioning and Matching

2019/05/18 by Xu, Hongteng, Luo, Dixin, Carin, Lawrence · 9 citations
#FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Social and Information Networks (cs.SI)

paper · doi:10.48550/arxiv.1905.07645

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 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.

Cited by

• Optimal Transport-Based Clustering of Attributed Graphs with an Application to Road Traffic Data
• DistDF: Time-Series Forecasting Needs Joint-Distribution Wasserstein Alignment
• Enhancing CLIP Robustness via Cross-Modality Alignment
• Transfer Learning on Edge Connecting Probability Estimation under Graphon Model
• Bootstrap Learning for Combinatorial Graph Alignment with Sequential GNNs
• Graph-based Clustering Revisited: A Relaxation of Kernel k-Means Perspective
• Gromov-Wasserstein and optimal transport: from assignment problems to probabilistic numeric
• Convergence of empirical Gromov-Wasserstein distance
• FRAM: Frobenius-Regularized Assignment Matching with Mixed-Precision Computing

Related

• Generalized Spectral Clustering via Gromov-Wasserstein Learning
• Semi-relaxed Gromov-Wasserstein divergence with applications on graphs
• Gromov-Wasserstein Factorization Models for Graph Clustering
• Fast and Provably Convergent Algorithms for Gromov-Wasserstein in Graph Data
• Gromov-Wasserstein Graph Coarsening