Theory Seminar
Abstract: We’ll discuss some recent work with Yihong Wu and Jiaming Xu on the “graph matching” problem of identifying the vertex matching between two graphs with correlated edges. We propose a simple spectral algorithm, which is related to a popular convex relaxation approach for this problem and also to the behavior of eigenvector moment flows for random matrices. We’ll describe a theoretical result establishing conditions under which this algorithm exactly recovers the vertex matching between two correlated Erdos-Renyi random graphs, and discuss some of the ideas of its proof and some open questions.