Matching recovery threshold for correlated random graphs
Jian Ding, Hang Du
Abstract
For two correlated graphs which are independently sub-sampled from a common Erdős–Rényi graph G(n,p), we wish to recover their latent vertex matching from the observation of these two graphs without labels. When p=n−α+o(1) for α∈(0,1], we establish a sharp information-theoretic threshold for whether it is possible to correctly match a positive fraction of vertices. Our result sharpens a constant factor in a recent work by Wu, Xu and Yu.
Topics & Concepts
MathematicsCombinatoricsVertex (graph theory)Matching (statistics)Fraction (chemistry)Random graphDiscrete mathematicsConstant (computer programming)Random regular graphGraphChordal graphStatistics1-planar graphChemistryComputer scienceOrganic chemistryProgramming languagePrivacy-Preserving Technologies in DataAdvanced Graph Neural NetworksStochastic Gradient Optimization Techniques