Correlation detection in trees for planted graph alignment
summary
Works in the sparse constant-degree regime and reduces matching to correlation detection in trees by comparing neighborhoods up to depth D ≈ log n, using a recursive likelihood ratio that grows double-exponentially under the planted model. A polynomial-time message-passing algorithm computes these scores and achieves one-sided partial recovery (vanishing false matches, positive true rate) when KL divergence on trees diverges and λs>1. Exact recovery is impossible when λs<1, information-theoretically possible (nonefficient) for λs≥4, and a conjectured hard phase appears when λ s^2 ≤1.
AI-written summary · about
chapters (10)
- 0:00Intro
- 0:22The graph alignment problem
- 7:15Measure of performance
- 10:33A local approach
- 12:06From graphs to trees
- 13:37Computing the likelihood ratio
- 15:16Correlation detection in trees
- 17:24Belief propagation for partial graph alignement
- 18:14Partial alignment in the regime with constant mean degree
- 21:37Conclusion
related talks
10mQuery, Communication and Discrepancy
32mThe Computational Benefit of Correlated Instances
35mLow-Density Parity-Check Codes And Spatial Coupling For Quantitative Group Testing
01h 07mMarrying Graph Convergence and Cascade Models
30mOptimal Lower Bounds for Distributed and Streaming Spanning Forest Computation
39mBroadcasting on Directed Acyclic Graphs
01h 23mProperty Testing for Graphs
01h 37mGraphons and Graph Limits 3