Spectral Graph Matching and Regularized Quadratic Relaxations: Algorithm and Theory

Zhou Fan, Cheng Mao, Yihong Wu, Jiaming Xu
Proceedings of the 37th International Conference on Machine Learning, PMLR 119:2985-2995, 2020.

Abstract

Graph matching, also known as network alignment, aims at recovering the latent vertex correspondence between two unlabeled, edge-correlated weighted graphs. To tackle this task, we propose a spectral method, GRAph Matching by Pairwise eigen-Alignments (GRAMPA), which first constructs a similarity matrix as a weighted sum of outer products between all pairs of eigenvectors of the two graphs, and then outputs a matching by a simple rounding procedure. For a universality class of correlated Wigner models, GRAMPA achieves exact recovery of the latent matching between two graphs with edge correlation $1 - 1/\mathrm{polylog}(n)$ and average degree at least $\mathrm{polylog}(n)$. This matches the state-of-the-art guarantees for polynomial-time algorithms established for correlated Erdős-Rényi graphs, and significantly improves over existing spectral methods. The superiority of GRAMPA is also demonstrated on a variety of synthetic and real datasets, in terms of both statistical accuracy and computational efficiency.

Cite this Paper

BibTeX
@InProceedings{pmlr-v119-fan20a, title = {Spectral Graph Matching and Regularized Quadratic Relaxations: Algorithm and Theory}, author = {Fan, Zhou and Mao, Cheng and Wu, Yihong and Xu, Jiaming}, booktitle = {Proceedings of the 37th International Conference on Machine Learning}, pages = {2985--2995}, year = {2020}, editor = {III, Hal Daumé and Singh, Aarti}, volume = {119}, series = {Proceedings of Machine Learning Research}, month = {13--18 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v119/fan20a/fan20a.pdf}, url = {https://proceedings.mlr.press/v119/fan20a.html}, abstract = {Graph matching, also known as network alignment, aims at recovering the latent vertex correspondence between two unlabeled, edge-correlated weighted graphs. To tackle this task, we propose a spectral method, GRAph Matching by Pairwise eigen-Alignments (GRAMPA), which first constructs a similarity matrix as a weighted sum of outer products between all pairs of eigenvectors of the two graphs, and then outputs a matching by a simple rounding procedure. For a universality class of correlated Wigner models, GRAMPA achieves exact recovery of the latent matching between two graphs with edge correlation $1 - 1/\mathrm{polylog}(n)$ and average degree at least $\mathrm{polylog}(n)$. This matches the state-of-the-art guarantees for polynomial-time algorithms established for correlated Erdős-Rényi graphs, and significantly improves over existing spectral methods. The superiority of GRAMPA is also demonstrated on a variety of synthetic and real datasets, in terms of both statistical accuracy and computational efficiency.} }
Endnote
%0 Conference Paper %T Spectral Graph Matching and Regularized Quadratic Relaxations: Algorithm and Theory %A Zhou Fan %A Cheng Mao %A Yihong Wu %A Jiaming Xu %B Proceedings of the 37th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2020 %E Hal Daumé III %E Aarti Singh %F pmlr-v119-fan20a %I PMLR %P 2985--2995 %U https://proceedings.mlr.press/v119/fan20a.html %V 119 %X Graph matching, also known as network alignment, aims at recovering the latent vertex correspondence between two unlabeled, edge-correlated weighted graphs. To tackle this task, we propose a spectral method, GRAph Matching by Pairwise eigen-Alignments (GRAMPA), which first constructs a similarity matrix as a weighted sum of outer products between all pairs of eigenvectors of the two graphs, and then outputs a matching by a simple rounding procedure. For a universality class of correlated Wigner models, GRAMPA achieves exact recovery of the latent matching between two graphs with edge correlation $1 - 1/\mathrm{polylog}(n)$ and average degree at least $\mathrm{polylog}(n)$. This matches the state-of-the-art guarantees for polynomial-time algorithms established for correlated Erdős-Rényi graphs, and significantly improves over existing spectral methods. The superiority of GRAMPA is also demonstrated on a variety of synthetic and real datasets, in terms of both statistical accuracy and computational efficiency.
APA
Fan, Z., Mao, C., Wu, Y. & Xu, J.. (2020). Spectral Graph Matching and Regularized Quadratic Relaxations: Algorithm and Theory. Proceedings of the 37th International Conference on Machine Learning, in Proceedings of Machine Learning Research 119:2985-2995 Available from https://proceedings.mlr.press/v119/fan20a.html.

Related Material