Testing Correlation of Unlabeled Random Graphs

on YouTube ↗40m

" summary

Derives a sharp statistical threshold: when edge-correlation squared (roughly s^2) exceeds about 2 log n / n (equivalently intersection average degree ≳ log n after rescaling by p) total variation →1, and below a matching lower bound TV→0; proofs use a conditional second moment on the likelihood ratio and an edge-orbit decomposition of the permutation-induced edge action to control short cycles. Shows an optimal but NP-hard max-correlation test, gives polynomial-time algorithms via degree/subgraph counts and weighted-tree counts when s is constant, and identifies a persistent computation–statistical gap in sparse regimes.

AI-written summary · about

" chapters (13)

1. 0:00Intro
2. 1:39Beyond worst-case: Noisy graph isomorphism
3. 9:19Threshold for detection: sparse Erdős-Rényi graphs
4. 10:36What is known algorithmically
5. 12:49Proof of positive results: QAP statistic
6. 13:47Proof of negative results: second-moment method
7. 16:29Second-moment calculation: cycle decomposition
8. 18:35Failure of second-moment We show
9. 20:48Conditional second-moment: dense regime It suffices to consider k=1
10. 25:56Classification of edge orbits
11. 28:36Backbone graph representation
12. 29:24Concluding remarks
13. 35:25Conditional second-moment: orbit pseduoforest

" related talks

• 54mExact Matching Of Random Graphs With Constant CorrelationCheng Mao · Algorithmic Advances for Statistical Inference with Combinatorial Structure
• 52mNew Algorithms For The Graph Alignment ProblemMarc Lelarge · Algorithmic Advances for Statistical Inference with Combinatorial Structure
• 56mTesting Thresholds for High-dimensional Sparse Random Geometric GraphsSiqi Liu · Structural Results 2023
• 11mSharp Threshold for the Planted Matching ProblemDana Yang · Meet the Fellows Welcome Event
• 48mHow Hard Is Inference for Structured Prediction?Tim Roughgarden · Learning, Algorithm Design and Beyond Worst-Case Analysis
• 45mCorrelated Stochastic Block Models: Graph Matching And Community RecoveryMiklos Racz · Algorithmic Advances for Statistical Inference with Combinatorial Structure
• 25mConstrained Rank Aggregation and Correlation ClusteringOlgica Milenkovic · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 43mInformation-Theoretic Bounds and Phase Transitions in Community Detection and High-Dimensional ClustCris Moore · Random Instances and Phase Transitions (Simons Institute, 2016)