Completed
How to construct the vertex signature?
Class Central Classrooms beta
YouTube videos curated by Class Central.
Classroom Contents
Random Graph Matching at Otter's Threshold via Counting Chandeliers
Automatically move to the next video in the Classroom when playback concludes
- 1 Intro
- 2 Motivating example from network de-anonymization
- 3 Motivating example from biology
- 4 Motivating example from computer vision
- 5 Real-world challenges
- 6 MLE: Quadratic Assignment Problem (QAP)
- 7 State of the art (polynomial-time algorithms)
- 8 Our results
- 9 Phase transition diagram for exact recovery
- 10 Meta algorithm
- 11 How to construct the vertex signature?
- 12 Rooted subgraph count
- 13 Graph matching via counting rooted subgraphs
- 14 Graph matching via counting rooted signed subgraphs
- 15 Desirable properties of similarity scores (Mean)
- 16 Desirable properties of similarity scores (Variance)
- 17 Which family of rooted subgraphs to count?
- 18 A special family of rooted trees - Chandeliers
- 19 Control of fluctuation via counting Chandeliers
- 20 Why do chandeliers work?
- 21 Conclusion
