Efficient random graph matching via degree profiles
- PDF / 1,297,788 Bytes
- 87 Pages / 439.37 x 666.142 pts Page_size
- 57 Downloads / 206 Views
Efficient random graph matching via degree profiles Jian Ding1 · Zongming Ma1 · Yihong Wu2
· Jiaming Xu3
Received: 22 March 2019 / Revised: 19 August 2020 © Springer-Verlag GmbH Germany, part of Springer Nature 2020
Abstract 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˝os-Rényi graphs G(n, dn ). 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 2 + n 2 )-time algorithm which perassignment problem. This work develops an O(nd fectly recovers the true vertex correspondence with high probability, provided that the average degree is at least d = Ω(log2 n) and the two graphs differ by at most δ = O(log−2 (n)) fraction of edges. For dense graphs and sparse graphs, this can be improved to δ = O(log−2/3 (n)) and δ = O(log−2 (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 o(1) ≤ d ≤ n c for some con4 ) and d = Ω(n 4/5 ) with a stant c with an n O(log n) -time algorithm and δ = O((d/n) polynomial-time algorithm.
J. Ding is supported in part by the NSF Grant DMS-1757479 and an Alfred Sloan fellowship. Z. Ma is supported in part by an NSF CAREER award DMS-1352060 and an Alfred Sloan fellowship. Y. Wu is supported in part by the NSF Grant CCF-1527105, an NSF CAREER award CCF-1651588, and an Alfred Sloan fellowship. J. Xu is supported by the NSF Grants CCF-1850743, CCF-1856424, and IIS-1932630. J. Ding and Y. Wu would like to thank the Centre de Recherches Mathématiques at the Université de Montréal, where some of the work was carried out during the Workshop on Combinatorial Statistics. Y. Wu is also grateful to David Pollard for helpful discussions on small ball probability. J. Xu would like to thank Nadav Dym and Shahar Kovalsky for pointing out the connections between fractional isomorphism and iterated degree sequences. The authors are grateful to the anonymous referees for helpful comments and corrections.
B
Yihong Wu [email protected]
1
Department of Statistics, The Wharton School, University of Pennsylvania, Philadelphia, USA
2
Department of Statistics and Data Science, Yale University, New haven, USA
3
The Fuqua School of Business, Duke University, Durham, USA
123
J. Ding et al.
Keywords Graph matching · Degree profiles · Quadratic assignment problem · Random graph isomorphism · Erd˝os-Rényi graph Mathematics Subject Classification Primary 05C80 · Secondary 68Q87
1 Introduction Graph matching [12,32], also known as network alignment [20], aims at finding a bijective mapping between the vertex sets of two networks so that the number of adjacency disagreements between the two networks is minimized. It reduces t
Data Loading...
