Title: Spectral graph matching and regularized quadratic relaxations

Abstract: Given two unlabeled, edge-correlated graphs on the same set of vertices, we study the "graph matching" problem of identifying the unknown mapping from vertices of the first graph to those of the second. This amounts to solving a computationally intractable quadratic assignment problem. We propose a new spectral method, which computes the eigendecomposition of the two graph 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 distance 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 can return 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. Our analysis exploits local laws for the resolvents of sparse Wigner matrices. Based on joint work with Zhou Fan, Cheng Mao, Yihong Wu, all at Yale.

Bio: Jiaming Xu is an assistant professor in the Fuqua School of Business at Duke University which he joined in July 2018. Before that, he was an assistant professor in the Krannert School of Management at Purdue University from August 2016 to June 2018, a research fellow with the Simons Institute for the Theory of Computing, UC Berkeley from January 2016 to June 2016, and a postdoctoral fellow with the Statistics Department, The Wharton School, University of Pennsylvania from January 2015 to December 2015. He received the Ph.D. degree from UIUC in 2014 under the supervision of Prof. Bruce Hajek, the M.S. degree from UT-Austin in 2011, and the B.E. degree from Tsinghua University in 2009, all in Electrical and Computer Engineering. His research interests include random graphs, high-dimensional statistical inference, information theory, convex and non-convex optimization, and queueing theory.