Random Graph Matching at Otter's Threshold via Counting Chandeliers

Random Graph Matching at Otter's Threshold via Counting Chandeliers

Harvard CMSA via YouTube Direct link

Intro

1 of 21

1 of 21

Intro

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. 1 Intro
  2. 2 Motivating example from network de-anonymization
  3. 3 Motivating example from biology
  4. 4 Motivating example from computer vision
  5. 5 Real-world challenges
  6. 6 MLE: Quadratic Assignment Problem (QAP)
  7. 7 State of the art (polynomial-time algorithms)
  8. 8 Our results
  9. 9 Phase transition diagram for exact recovery
  10. 10 Meta algorithm
  11. 11 How to construct the vertex signature?
  12. 12 Rooted subgraph count
  13. 13 Graph matching via counting rooted subgraphs
  14. 14 Graph matching via counting rooted signed subgraphs
  15. 15 Desirable properties of similarity scores (Mean)
  16. 16 Desirable properties of similarity scores (Variance)
  17. 17 Which family of rooted subgraphs to count?
  18. 18 A special family of rooted trees - Chandeliers
  19. 19 Control of fluctuation via counting Chandeliers
  20. 20 Why do chandeliers work?
  21. 21 Conclusion

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Someone learning on their laptop while sitting on the floor.