Boot camp on generalization theory for graph learning

on YouTube ↗01h 40m

" summary

VC bounds tie capacity to combinatorial expressivity, provably equating VC dimension to the number of 1WL equivalence classes for MPNNs on n‑node graphs, Rademacher bounds give data‑dependent rates that blow up with max node degree so Rademacher scales with max degree Q, covering number bounds use a forest/transport pseudometric that recovers VC at radius zero, continuous GCN and graphon analyses show n−1/2 or n−1 rates for dense/sparser regimes, sparse limits break spectral continuity, and computational lower bounds prove exponential SQ lower bounds in nodes or feature dim so many results are constructive but loose.

AI-written summary · about

" chapters (38)

1. 0:00Generalization theory intro
2. 1:07Graph learning basics & MPNNs
3. 2:34Formalizing generalization
4. 4:23In- vs out-distribution generalization
5. 5:28Uniform bounds & VC dimension
6. 7:12VC limits for MPNNs
7. 8:41Rademacher complexity for MPNNs
8. 15:56Empirical Rademacher definition
9. 19:16Rademacher bounds via computation
10. 24:40Rademacher limits
11. 25:01Covering number bounds
12. 26:50Covering numbers role
13. 31:30Graphon compactness
14. 32:37Lipschitz for MPNNs
15. 36:58Distribution-free bounds
16. 37:44Graphon data models
17. 38:48Node/link prediction challenges
18. 40:12Future directions in theory
19. 43:05Survey papers on graph learning
20. 43:27Q&A on bounds
21. 48:42Thien Le introduces out-of-distribution generalization
22. 49:02Lower bounds for GNNs
23. 51:41cSQ model limits
24. 56:21cSQ learning hardness
25. 59:18Gradient descent as cSQ
26. 1:01:35Lower bounds for shallow GNNs
27. 1:04:33Q&A on lower bounds
28. 1:06:42Out-of-distribution generalization assumptions
29. 1:09:42GCN approximation theory
30. 1:15:08GCN graphon bounds
31. 1:17:57Graphon spectral bounds
32. 1:21:15Sparse graph limits
33. 1:23:27Graph limits via P-operators
34. 1:26:41Extrapolation lower bounds
35. 1:29:12Tree mover distance bounds
36. 1:31:22Algorithmic alignment
37. 1:33:10OOD assumptions summary
38. 1:35:00Q&A on graphon bounds

" related talks

• 01h 04mNonparametric Bayesian Methods: Models, Algorithms, and Applications IVTamara Broderick · Foundations of Machine Learning Boot Camp 2017
• 49mRecent Advances in Counting Sparse GraphsSourav Chatterjee · Random Instances and Phase Transitions (Simons Institute, 2016)
• 31mStatistical Estimation on GraphsAndrea Montanari · Coding: From Practice to Theory
• 01h 07mTheory of Computation IIChristos Papadimitriou · The Brain and Computation Boot Camp
• 01h 21mTutorial: Implicit Bias INati Srebro · Deep Learning Theory Workshop and Summer School 2022
• 27mDistribution Learning Meets Graph Structure SamplingSayantan Sen · Workshop on Local Algorithms (WoLA) 2024
• 35mSize-free Generalization Bounds for Convolutional Neural NetworksHanie Sedghi · Frontiers of Deep Learning 2019
• 59mTutorial: Statistical Learning Theory and Neural Networks ISpencer Frei · Deep Learning Theory Workshop and Summer School 2022