The Statistics Seminar speaker for Wednesday, September 18, 2019, is Zhou Fan, an Assistant Professor in the Department of Statistics and Data Science at Yale University. His research interests include random matrix theory, high dimensional and multivariate statistics, inference in random graphs and networks, discrete algorithms, and applications in genetics and computational biology. Zhou received his Ph.D. in Statistics at Stanford University. Prior to this, he developed statistical and software tools for molecular dynamics simulations at D. E. Shaw Research.
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 matching the vertices of the first graph to those of the second. We propose a new spectral method for this problem, which first constructs a similarity matrix as a weighted sum of outer products between all pairs of eigenvectors of the two graphs, with weights given by a Cauchy kernel applied to the separation of the corresponding eigenvalues, then outputs a matching by a simple rounding procedure. The similarity matrix can also be interpreted as the solution to a regularized quadratic programming relaxation of the quadratic assignment problem. We show that for a correlated Erdos-Renyi model, this method returns the exact matching with high probability if the 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.
This is joint work with Cheng Mao, Yihong Wu, and Jiaming Xu.