Spectral graph matching and regularized quadratic relaxations

Add to your list(s) Download to your calendar using vCal

• Yihong Wu (Yale University)
• Friday 13 September 2019, 14:00-15:00
• Room 503, EEE.

If you have a question about this talk, please contact Vanessa Rodriguez-Gonzalez.

Graph matching aims at finding the vertex correspondence that maximally aligns the edge sets of two given graphs. This task amounts to solving a computationally intractable quadratic assignment problem. We propose a new spectral method, which computes the eigendecomposition of the two adjacency matrices and returns a matching based on the pairwise alignments between all eigenvectors of the first graph with all eigenvectors of the second. Each alignment is inversely weighted by the gap between the corresponding eigenvalues. This spectral method can be equivalently viewed as solving a regularized quadratic programming relaxation of the quadratic assignment problem. We show that for a correlated Erdos-Renyi model, this method finds the exact matching with high probability if the two graphs differ by at most a 1/polylog(n) fraction of edges, both for dense graphs and for sparse graphs with at least polylog(n) average degree. The proposed algorithm matches the state of the art of polynomial-time algorithms based on combinatorial ideas, and exponentially improves the performance of prior spectral methods that only compare top eigenvectors or eigenvectors of the same order. The analysis exploits local laws for the resolvents of sparse Wigner matrices.

Based on joint work with Zhou Fan and Cheng Mao at Yale University and Jiaming Xu at Duke University. Preprints available at https://arxiv.org/abs/1907.08880 and https://arxiv.org/abs/1907.08883.

This talk is part of the Vanessa Rodriguez-Gonzalez's list series.

This talk is included in these lists:

• Room 503, EEE

Note that ex-directory lists are not shown.