Skip to main content

Scalable gromov-wasserstein learning for graph partitioning and matching

Publication ,  Conference
Xu, H; Luo, D; Carin, L
Published in: Advances in Neural Information Processing Systems
January 1, 2019

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

Duke Scholars

Published In

Advances in Neural Information Processing Systems

ISSN

1049-5258

Publication Date

January 1, 2019

Volume

32

Related Subject Headings

  • 4611 Machine learning
  • 1702 Cognitive Sciences
  • 1701 Psychology
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Xu, H., Luo, D., & Carin, L. (2019). Scalable gromov-wasserstein learning for graph partitioning and matching. In Advances in Neural Information Processing Systems (Vol. 32).
Xu, H., D. Luo, and L. Carin. “Scalable gromov-wasserstein learning for graph partitioning and matching.” In Advances in Neural Information Processing Systems, Vol. 32, 2019.
Xu H, Luo D, Carin L. Scalable gromov-wasserstein learning for graph partitioning and matching. In: Advances in Neural Information Processing Systems. 2019.
Xu, H., et al. “Scalable gromov-wasserstein learning for graph partitioning and matching.” Advances in Neural Information Processing Systems, vol. 32, 2019.
Xu H, Luo D, Carin L. Scalable gromov-wasserstein learning for graph partitioning and matching. Advances in Neural Information Processing Systems. 2019.

Published In

Advances in Neural Information Processing Systems

ISSN

1049-5258

Publication Date

January 1, 2019

Volume

32

Related Subject Headings

  • 4611 Machine learning
  • 1702 Cognitive Sciences
  • 1701 Psychology