Matching recovery threshold for correlated random graphs

DOI10.1214/23-AOS2305arXiv2205.14650MaRDI QIDQ6183756FDOQ6183756

Authors:

Publication date: 4 January 2024

Published in: The Annals of Statistics (Search for Journal in Brave)

Abstract: For two correlated graphs which are independently sub-sampled from a common ErdH{o}s-R'enyi graph $mathbfG(n,p)$, we wish to recover their emph{latent} vertex matching from the observation of these two graphs emph{without labels}. When $p=n^{-alpha+o(1)}$ for $alphain(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.

Full work available at URL: https://arxiv.org/abs/2205.14650

Recommendations

• Exact matching of random graphs with constant correlation
• Partial Recovery in the Graph Alignment Problem
• Efficient random graph matching via degree profiles
• Aligning random graphs with a sub-tree similarity message-passing algorithm

zbMATH Keywords

correlated Erdős-Rényi random graphinformation thresholdmatching recovery

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Cites Work

• Efficient random graph matching via degree profiles
• Settling the Sharp Reconstruction Thresholds of Random Graph Matching
• Seeded graph matching for correlated Erdős-Rényi graphs
• Exact matching of random graphs with constant correlation
• The densest subgraph problem in sparse random graphs
• Load balancing and orientability thresholds for random hypergraphs
• The \(k\)-orientability thresholds for \(G_{n,p}\)
• The random graph threshold for \(k\)-orientiability and a fast algorithm for optimal multiple-choice allocation
• Performance of global load balancing by local adjustment
• Title not available (Why is that?)
• The cycle structure of random permutations
• Introduction to Random Graphs
• Generalized Sphere-Packing Bounds on the Size of Codes for Combinatorial Channels
• The planted matching problem: sharp threshold and infinite-order phase transition
• Testing correlation of unlabeled random graphs
• Correlated randomly growing graphs
• The Multiple-Orientability Thresholds for Random Hypergraphs
• Spectral graph matching and regularized quadratic relaxations. II: Erdős-Rényi graphs and universality

Cited In (8)

• Aligning random graphs with a sub-tree similarity message-passing algorithm
• Correlation detection in trees for planted graph alignment
• Weak Recovery Conditions from Graph Partitioning Bounds and Order Statistics
• The planted matching problem: sharp threshold and infinite-order phase transition
• Partial Recovery in the Graph Alignment Problem
• Information Recovery in Shuffled Graphs via Graph Matching
• A polynomial-time approximation scheme for the maximal overlap of two independent Erdős-Rényi graphs
• Exact matching of random graphs with constant correlation

This page was built for publication: Matching recovery threshold for correlated random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6183756)