Abstract
We give a quasipolynomial time algorithm for the graph matching problem (also known as noisy or robust graph isomorphism) on correlated random graphs. Specifically, for every $\gamma>0$, we give a $n^{O(\log n)}$ time algorithm that given a pair of $\gamma$-correlated $G(n,p)$ graphs $G_0,G_1$ with average degree between $n^{\varepsilon}$ and $n^{1/153}$ for $\varepsilon = o(1)$, recovers the "ground truth" permutation $\pi\in S_n$ that matches the vertices of $G_0$ to the vertices of $G_n$ in the way that minimizes the number of mismatched edges. We also give a recovery algorithm for a denser regime, and a polynomial-time algorithm for distinguishing between correlated and uncorrelated graphs. Prior work showed that recovery is information-theoretically possible in this model as long the average degree was at least $\log n$, but sub-exponential time algorithms were only known in the dense case (i.e., for $p > n^{-o(1)}$). Moreover, "Percolation Graph Matching", which is the most common heuristic for this problem, has been shown to require knowledge of $n^{\Omega(1)}$ "seeds" (i.e., input/output pairs of the permutation $\pi$) to succeed in this regime. In contrast our algorithms require no seed and succeed for $p$ which is as low as $n^{o(1)-1}$.
Introduction
The graph matching problem, or noisy graph isomorphism, involves finding a hidden alignment between two correlated networks. This problem is particularly relevant in fields like social network de-anonymization, where one might attempt to match users across different platforms despite noise and missing data.
Mathematically, this is modeled using the Correlated Erdős-Rényi model. A base random graph is generated, and two subgraphs ($G_0$ and $G_1$) are created by independently keeping each edge with probability $\gamma$. The vertices of $G_1$ are then randomly permuted. The goal is to recover this permutation $\pi$. While information theory suggests recovery is possible for average degrees as low as $\log n$, finding an efficient algorithm for sparse graphs has remained a significant challenge.
Methods: A "Flock of Black Swans"
Standard heuristics, such as matching vertices by degree or spectral properties, fail in sparse regimes because random noise significantly shifts these local statistics. Instead, this paper introduces a subgraph matching approach based on "black swans"—rare, highly structured subgraphs that act as robust signatures.
The algorithm proceeds in several steps:
- Test Graph Construction: The authors prove the existence of a family of "strictly balanced" test graphs of size $O(\log n)$. These graphs have no symmetries and are designed so that no sub-component is disproportionately denser than the whole.
- Rare Structure Detection: Because these graphs are strictly balanced, they are extremely unlikely to appear by chance in a random graph. If such a structure appears in both $G_0$ and $G_1$, it is highly likely to represent the same set of vertices.
- Seed Generation and Boosting: These rare matches provide an initial "seed set." The algorithm then uses a percolation-like procedure to propagate these matches across the entire graph.
Key Results
The primary contribution is a quasipolynomial-time algorithm ($n^{O(\log n)}$) that achieves recovery in sparse regimes where only exponential-time algorithms were previously known.
Key findings include:
- Quasipolynomial Recovery: The algorithm succeeds for average degrees between $n^{o(1)}$ and $n^{1/153}$, and in a denser regime between $n^{2/3}$ and $n^{1-\epsilon}$.
- Polynomial-Time Distinguishing: A strictly polynomial-time algorithm is provided for hypothesis testing—distinguishing between correlated and independent random graphs.
- Sparsity Thresholds: This work significantly lowers the density requirement for tractable graph matching from $n^{\Omega(1)}$ down to nearly logarithmic sparsity ($n^{o(1)}$).
Limitations and Future Work
Despite these advances, a strictly polynomial-time algorithm for recovery in the sparse regime remains an open problem. Additionally, there is a "parameter gap" for average degrees between $n^{1/153}$ and $n^{2/3}$ where the current construction of test graphs does not apply. Future research may focus on closing this gap and adapting these theoretical insights into practical heuristics for real-world network analysis.
Summary updated