Institute of Information Science, Academia Sinica

The graph matching problem aims to find a (vertex) permutation between the two input graphs that minimizes the disagreement among edges. This is an extremely well studied computational problem and has wide applications in machine learning, computer vision, pattern recognition, computational biology, social network analysis, and de-anonimzation. In the worst case, the graph matching problem is NP-hard. Nevertheless, there exists polynomial-time algorithm for graph matching problem in the average case setting where one of the input graph is sampled from the Erdös-Rényi model and the other graph is yielded by applying a random permutation on the first graph.

In this work, we focus on the the input graphs being sampled from the correlated Erdös-Rényi model where each edge is deleted independently with probability half. Information-theoretically, this problem is solvable in a wide range of parameters. However, prior to our work, no non-trivial algorithm (other than brute force) is known to the best of our knowledge. Some common heuristics for this problem require knowledge of large fraction of seeds (i.e., pairs in the ground truth permutation). We give a quasi-polynomial time algorithm for correlated graphs with average degree between n^[@BackSlash]eps and n^{1/153} for [@BackSlash]eps=o(1) or between n^{2/3} and n^{1-[@BackSlash]eps} for [@BackSlash]eps=O(1). The central idea of our algorithm is based on constructing a family of well-structured subgraphs such that these subgraphs can uniquely cover the two correlated graphs with high probability.

This is a joint work with Boaz Barak, Zhixian Lei, Tselil Schramm, and Yueqi Sheng.

Chi-Ning Chou is a Ph.D. student at Harvard University advised by Professor Boaz Barak. He received his B.S. in computer science from National Taiwan University in 2016. He has various research interest in theoretical computer science including computational complexity, algebraic computation, hardness of approximation etc.