New Algorithms For The Graph Alignment Problem

on YouTube ↗52m

" summary

Defines a correlated Erdos-Renyi model and reduces matching to local hypothesis tests on Galton-Watson neighborhoods, computing a local likelihood-ratio recursion to score candidate pairs; shows a polynomial-time algorithm that thresholding these scores achieves one-sided partial recovery whenever the KL divergence of tree laws diverges and λs>1, giving an easy/hard phase diagram. Also trains an equivariant graph net (FGNN) on synthetic permuted pairs; it outperforms spectral/SDP baselines at moderate density but fails near the conjectured hard region.

AI-written summary · about

" chapters (7)

1. 0:00Start
2. 21:46Computing the likelihood ratio
3. 25:44Correlation detection in trees
4. 37:00One-sided partial graph alignement
5. 39:09Learning the graph alignment problem with Siamese GNS
6. 43:35Results on synthetic data
7. 50:04Conclusion

" related talks

• 40mTesting Correlation of Unlabeled Random GraphsJiaming Xu · Computational Phase Transitions (Simons Institute, 2020)
• 31mSimple Models and Exact Algorithms for Computing Network ModulesGunnar Klau · Network Biology 2016
• 35mLocal Statistics, Semidefinite Programming, and Community Detection IISidhanth Mohanty · Computational Phase Transitions (Simons Institute, 2020)
• 39mLocal Algorithms for Community DetectionElchanan Mossel · Approximate Counting, Markov Chains and Phase Transitions
• 11mSharp Threshold for the Planted Matching ProblemDana Yang · Meet the Fellows Welcome Event
• 56mGraph Matching: Relax or Not?Alex Bronstein · Spectral Algorithms: From Theory to Practice 2014
• 47mLearning Probabilistic Models for Graph Partitioning in the Presence of NoiseAravindan Vijayaraghavan · Learning, Algorithm Design and Beyond Worst-Case Analysis
• 48mHow Hard Is Inference for Structured Prediction?Tim Roughgarden · Learning, Algorithm Design and Beyond Worst-Case Analysis