Abstract: Random graph matching refers to recovering the underlying vertex correspondence between
two Erd\H{o}s-R\'{e}nyi graphs with correlated edges. This can be viewed as an average-case and noisy
version of the graph isomorphism problem. The maximum likelihood estimator is equivalent to the
intractable quadratic assignment problem.
For seeded problems, where an initial seed set of correctly matched vertex pairs is revealed as side
information, our result provides a dramatic improvement over previously known results. We show
that it is possible to achieve the information-theoretic limit of graph sparsity in time polynomial in
the number of vertices $n$. Moreover, we show the number of seeds needed for exact recovery in
polynomial-time can be as low as $n^{\epsilon}$ in the sparse graph regime with the average degree
smaller than $n^{\epsilon}$) and $\Omega(\log n)$ in the dense graph regime.
For unseeded problems, we develop a nearly linear-time algorithm which perfectly recovers the
underlying true vertex correspondence, provided that the two observed graphs differ by at most
$epsilon=O(1/log^2(n) )$ fraction of edges in the sparse graph regime and $espilon=O( 1/log^{2/3}(n) )$
fraction of edges in the dense graph regime. The best-known result before this work achieves $\epsilon=
O(1)$ with an $n^{O(\log n)}$-time algorithm.
Bio: Jiaming Xu is an Assistant Professor in the academic area of decision sciences in the Fuqua School
of Business at Duke University. He received a B.E. from Tsinghua University in Beijing in 2009, an M.S.
from UT Austin in 2011, and a Ph.D. from University of Illinois at Urbana-Champaign in 2014, all in
Electrical and Computer Engineering. He joined the Krannert School of Management at Purdue University
as an Assistant Professor in 2016. Before that, he was a Research Fellow with the Simons Institute for the
Theory of Computing, University of California, Berkeley, and a Postdoctoral Fellow with the Statistics
Department, The Wharton School, University of Pennsylvania. His research interests include data science,
high-dimensional statistical inference, information theory, convex and non-convex optimization, queueing
theory, and game theory. Dr. Xu received a Simons-Berkeley Fellowship in 2016 and the Outstanding
Graduate Student Award conferred by the UIUC College of Engineering in 2014.
