Spectrally Robust Graph Isomorphism

on YouTube ↗29m

" summary

Introduces a relaxation of graph isomorphism based on spectral similarity of Laplacians and studies when two graphs are spectrally close despite not being isomorphic. Describes algorithms and structural conditions that allow detection or certification of this spectral robustness using Laplacian and spectral techniques.

AI-written summary · about

" chapters (8)

1. 0:00Intro
2. 0:39Graph Isomorphism and Graph Similarity
3. 6:45Talk Outline
4. 9:38Graph Dominance Problem
5. 15:45Spectrally Robust Graph Isomorphism
6. 20:41Open Problems and how Randomness might help
7. 23:57Approximate 'Subspace Isomorphism
8. 26:38Open(?) Problem

" related talks

• 56mGraph Matching: Relax or Not?Alex Bronstein · Spectral Algorithms: From Theory to Practice 2014
• 49mSpectral Approaches to Nearest Neighbor SearchAlexandr Andoni · Spectral Algorithms: From Theory to Practice 2014
• 54mSzemerédi Regularity Lemma in Graph Machine LearningRon Levie · Graph Learning Meets Theoretical Computer Science 2025
• 01h 02mGraph PoweringEmmanuel Abbe · Optimization, Statistics and Uncertainty
• 49mRobust Spectral Diffusions for Data ApplicationsDavid Gleich · Spectral Algorithms: From Theory to Practice 2014
• 44mSome Problems of Robust High-dimensional StatisticsGilad Lerman · Robust and High-Dimensional Statistics (Simons Institute workshop, 2018)
• 52mNew Algorithms For The Graph Alignment ProblemMarc Lelarge · Algorithmic Advances for Statistical Inference with Combinatorial Structure
• 49mMetric Representations: Algorithms and GeometryAnna Gilbert · Algorithmic Advances for Statistical Inference with Combinatorial Structure