Random Graph Matching at Otter's Threshold via Counting Chandeliers

Learn about efficient graph matching algorithms through this technical lecture from Yale's Yihong Wu at Harvard CMSA. Explore a novel approach using similarity scores constructed from counting weighted trees rooted at each vertex, specifically designed for matching Erdős–Rényi graphs with correlated edges. Discover how this groundbreaking polynomial-time algorithm succeeds at an explicit constant correlation and works for both sparse and dense graphs, requiring only that nq approaches infinity and the edge correlation coefficient satisfies specific conditions related to Otter's tree-counting constant. Delve into the concept of "chandeliers" - specially curated rooted trees that enable effective extraction of graph correlation while minimizing interference between different trees. Follow along as the lecture progresses from motivating examples in network de-anonymization, biology, and computer vision to practical challenges, state-of-the-art solutions, and detailed technical analysis of the algorithm's properties. Understand the phase transition diagram for exact recovery, meta algorithm implementation, and the crucial role of rooted subgraph counting in achieving successful graph matching.