2024/05/20 by Taha Ameen, Ameen, Taha, Bruce Hajek +1
Computer Science · #Bayesian Modeling and Causal Inference #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph Theory and Algorithms #Statistics Theory (math.ST)
paper · pdf · doi:10.48550/arxiv.2405.12293
openalex publication_date 2024/05/20 · openalex created_date 2024/05/23 · openalex updated_date 2026/07/28
This work studies fundamental limits for recovering the underlying correspondence among multiple correlated graphs. In the setting of inhomogeneous random graphs, we present and analyze a matching algorithm: first partially match the graphs pairwise and then combine the partial matchings by transitivity. Our analysis yields a sufficient condition on the problem parameters to exactly match all nodes across all the graphs. In the setting of homogeneous (Erdős-Rényi) graphs, we show that this condition is also necessary, i.e. the algorithm works down to the information theoretic threshold. This reveals a scenario where exact matching between two graphs alone is impossible, but leveraging more than two graphs allows exact matching among all the graphs. Converse results are also given in the inhomogeneous setting and transitivity again plays a role. Along the way, we derive independent results about the k-core of inhomogeneous random graphs.