Gromov-Wasserstein Learning for Graph Matching and Node Embedding

Hongteng Xu, Dixin Luo, Hongyuan Zha, Lawrence Carin Duke
Proceedings of the 36th International Conference on Machine Learning, PMLR 97:6932-6941, 2019.

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v97-xu19b, title = {Gromov-{W}asserstein Learning for Graph Matching and Node Embedding}, author = {Xu, Hongteng and Luo, Dixin and Zha, Hongyuan and Duke, Lawrence Carin}, booktitle = {Proceedings of the 36th International Conference on Machine Learning}, pages = {6932--6941}, year = {2019}, editor = {Chaudhuri, Kamalika and Salakhutdinov, Ruslan}, volume = {97}, series = {Proceedings of Machine Learning Research}, month = {09--15 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v97/xu19b/xu19b.pdf}, url = {https://proceedings.mlr.press/v97/xu19b.html}, 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.} }
Endnote
%0 Conference Paper %T Gromov-Wasserstein Learning for Graph Matching and Node Embedding %A Hongteng Xu %A Dixin Luo %A Hongyuan Zha %A Lawrence Carin Duke %B Proceedings of the 36th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Ruslan Salakhutdinov %F pmlr-v97-xu19b %I PMLR %P 6932--6941 %U https://proceedings.mlr.press/v97/xu19b.html %V 97 %X 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.
APA
Xu, H., Luo, D., Zha, H. & Duke, L.C.. (2019). Gromov-Wasserstein Learning for Graph Matching and Node Embedding. Proceedings of the 36th International Conference on Machine Learning, in Proceedings of Machine Learning Research 97:6932-6941 Available from https://proceedings.mlr.press/v97/xu19b.html.

Related Material