Graph Matching in Correlated Random Graphs via Small Subgraph Statistics

on YouTube ↗01h 03m

" summary

Gives a quasi-polynomial-time algorithm that recovers the planted permutation between two correlated G(n,p) graphs when gamma is constant (example gamma ≈ 1/100) and p sits in a specified sparse range (e.g. p ≈ n^{-0.999}); information-theoretic recovery needs p·gamma^2 ≳ (log n)/n. Algorithm uses small strictly-balanced subgraphs and the second-moment method to get concentration, matches rare subgraphs (logarithmic size) to seed a percolation, and yields a polynomial-time hypothesis test to distinguish planted vs null. Limitations: specific degree regimes and quasi-polynomial runtime for full recovery.

AI-written summary · about

" chapters (16)

1. 0:00Introduction and problem
2. 0:42Graph matching overview
3. 2:20Planted correlation model
4. 4:32Comparison with null model
5. 5:49Connectivity and recovery
6. 6:49Limitations of existing methods
7. 9:08Prior work and main results
8. 12:00Technical parameter ranges
9. 14:40Subgraph counting approach
10. 15:52Hypothesis testing intuition
11. 19:10Variance and concentration
12. 25:41Strictly balanced graphs
13. 30:48Constructing test graphs
14. 41:28Recovery via rare subgraphs
15. 47:23Computational complexity context
16. 55:13Open questions and discussion