Papers › Efficient random graph matching via degree profiles
Efficient random graph matching via degree profiles
Jian Ding, Zongming Ma, Yihong Wu, Jiaming Xu
Random graph matching refers to recovering the underlying vertex correspondence between two random graphs with correlated edges; a prominent example is when the two random graphs are given by Erd\H{o}s-R\'{e}nyi graphs G(n,d/n). This can be viewed as an average-case and noisy version of the graph isomorphism problem. Under this model, the maximum likelihood estimator is equivalent to solving the intractable quadratic assignment problem. This work develops an Õ(n d²+n²)-time algorithm which perfectly recovers the true vertex correspondence with high probability, provided that the average degree is at least d = Ω(log² n) and the two graphs differ by at most δ= O( log⁻²(n) ) fraction of edges. For dense graphs and sparse graphs, this can be improved to δ= O( log^(-2/3)(n) ) and δ= O( log⁻²(d) ) respectively, both in polynomial time. The methodology is based on appropriately chosen distance statistics of the degree profiles (empirical distribution of the degrees of neighbors). Before this work, the best known result achieves δ=O(1) and nᵒ⁽¹⁾ ≤d ≤nᶜ for some constant c with an nᴼ⁽ˡᵒᵍⁿ⁾-time algorithm \cite{barak2018nearly} and δ=Õ((d/n)⁴) and d = Ω̃(n^(4/5)) with a polynomial-time algorithm \cite{dai2018performance}.
In Syntology Open this paper in Syntology's Atlas, the map of the papers in Syntology's graph and their citations.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Tasks
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections