Graph Matching: Relax or Not?

on YouTube ↗56m

" summary

Convex quadratic relaxation over pseudo-stochastic matrices recovers the exact permutation whenever adjacency matrices have simple spectrum and no eigenvector is orthogonal to the all-ones vector — called friendly graphs — because first-order optimality in the eigenbasis forces a unique identity solution; the uniqueness is stable under small noise (explicit but n-dependent bound) and simulations on 1,000 randomized graphs (n up to ~50) show a sharp phase transition, while adding seeded attributes equal to the symmetry count removes degeneracy and yields correct matches.

AI-written summary · about

" chapters (15)

1. 0:00Intro
2. 0:30Minimum-distortion correspondences
3. 3:29Graph matching' problems
4. 4:24Convex relaxation
5. 9:19Relax or not?
6. 17:06Main result
7. 18:28Sketch of the proof
8. 22:51Inexact graph matching
9. 28:24Experimental validation on 1000 strongly friendly graphs
10. 32:26Unfriendly graphs and symmetry
11. 37:41Matching of unfriendly graphs
12. 39:10Seeds and attributes
13. 40:53Seeded/attributed graph matching
14. 44:22Experimental validation on 1000 symmetric graphs
15. 46:14Questions

" related talks

• 45mCorrelated Stochastic Block Models: Graph Matching And Community RecoveryMiklos Racz · Algorithmic Advances for Statistical Inference with Combinatorial Structure
• 54mExact Matching Of Random Graphs With Constant CorrelationCheng Mao · Algorithmic Advances for Statistical Inference with Combinatorial Structure
• 47mPhase Transitions in Semidefinite Relaxations (A Fast & Robust Algorithm for Community Detection)Fedrico Ricci-Tersenghi · Random Instances and Phase Transitions (Simons Institute, 2016)
• 52mNew Algorithms For The Graph Alignment ProblemMarc Lelarge · Algorithmic Advances for Statistical Inference with Combinatorial Structure
• 45mCommunity Detection with the Non-Backtracking OperatorMarc Lelarge · Random Instances and Phase Transitions (Simons Institute, 2016)
• 46mCan Non-Convex Optimization be Robust?Rong Ge · Robust and High-Dimensional Statistics (Simons Institute workshop, 2018)
• 09mConvex Programs, Computational Phase Transitions, and Robust AlgorithmsSam Hopkins · Meet the Fellows Welcome Event
• 29mSpectrally Robust Graph IsomorphismYiannis Koutis · Randomized Numerical Linear Algebra and Applications 2018