Boot camp on graphons for graph learning
summary
Introduces graphons rigorously, defines homomorphism density and cut distance, proves graphs sampled from a graphon converge in cut distance, and builds graphon integral operators with discrete spectra; shows convolutional GNNs (fixed filter weights) converge spectrally to graphon convolutions because graph eigenvalues converge, then lifts convergence to node domain under spectral-gap or Lipschitz-filter conditions; provides nonasymptotic transferability bounds that scale with filter Lipschitz constant and c‑band cardinality, demonstrates learning-by-transference that trains on growing small graphs to approach the graphon ERM (saves compute in movie-recommendation and 100‑agent control experiments), and flags limitations for truly sparse graphs and alternative limit models.
AI-written summary · about
chapters (11)
- 0:00Introduction to graphons
- 2:10Graphon definitions
- 4:48Graph convergence concepts
- 10:32Graphons as generative models
- 13:52Measuring graph distances
- 23:44Graphons in machine learning
- 33:37Spectral convergence of GNNs
- 43:37Node domain convergence
- 52:15Transferability analysis
- 1:05:11Advanced graphon applications
- 1:22:50Limitations and conclusions
related talks
18mGraphon Neural Networks and the Transferability of Graph Neural Networks
01h 31mGraphons and Graph Limits 2
16mPreview: Graph NNs
01h 02mGraph Powering
31mGraph-Based Machine Learning with Python
39mUsing Graph Neural Networks to Embrace the Dependency Within Your Data
30mGraph Machine Learning in All Its Glory!
59mTransforming DataFrames: Intro to Graphs & GNNs with PyTorch Geometric