Timezone: »

 
Poster
Scalable Gromov-Wasserstein Learning for Graph Partitioning and Matching
Hongteng Xu · Dixin Luo · Lawrence Carin

Tue Dec 10 05:30 PM -- 07:30 PM (PST) @ East Exhibition Hall B + C #63
in Algorithms -- Unsupervised Learning »
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 is a predefined graph with isolated but self-connected nodes ($i.e.$, disconnected graph), the optimal transport indicates the clustering structure of the other graph and achieves graph partitioning. Further, we extend our method to multi-graph partitioning and matching by learning a Gromov-Wasserstein barycenter graph for multiple observed graphs. Our method combines a recursive $K$-partition mechanism with a warm-start 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.
Keywords: Unsupervised Learning · Network Analysis · Applications · Algorithms
[ Paper]  [ Poster] 

Author Information

Hongteng Xu (Infinia ML and Duke University)
Dixin Luo (Duke University)
Lawrence Carin (Duke University)

More from the Same Authors