Exact Matching Of Random Graphs With Constant Correlation
Talkat Algorithmic Advances for Statistical Inference with Combinatorial Structure · 2021-10-11..10-15·
summary
Provides a polynomial-time algorithm that achieves exact recovery of the latent permutation for two correlated Erdős–Rényi graphs when average degree is between (1+ε)log n and n^{1/(C log log n)} and correlation is a fixed constant (delta < delta0 and < ε/4), with success probability 1−n^{-Ω(1)} and runtime n^{2+o(1)}. Key tools are partition trees that split R-spheres into labeled set-leaves, entrywise sparsified signatures built from leaf-degree sums, and an iterative neighborhood-intersection refinement; the method provably converts a high-quality partial matching to exact recovery.
AI-written summary · about
chapters (8)
- 0:00Introduction and context
- 0:41Problem formulation
- 4:09Model and goals
- 10:27Literature review
- 16:40Partition tree construction
- 30:15Vertex signatures
- 37:20Iterative refinement
- 43:18Future work and Q&A
related talks
40mTesting Correlation of Unlabeled Random Graphs
56mGraph Matching: Relax or Not?
11mSharp Threshold for the Planted Matching Problem
38mSome Easy Optimization Problems Have the Overlap-Gap Property
48mHow Hard Is Inference for Structured Prediction?
47mLearning Probabilistic Models for Graph Partitioning in the Presence of Noise
56mTesting Thresholds for High-dimensional Sparse Random Geometric Graphs
51mExact Recovery via Convex Relaxations