A Local Graph Limits Perspective on Sampling-Based GNNs
summary
Uses the Benjamini–Schramm limits framework to prove that, under mild assumptions (local samplers, Lipschitz loss), parameters trained on many small fixed‑size subgraph samples lie within an ε‑neighborhood of parameters trained on the whole large graph. Gives explicit bounds: about 1/ε^2 samples and only constant‑size subgraphs are required asymptotically, proves gradient and loss convergence, and shows empirically on PubMed (≈20k nodes) that GraphSAGE/GCN sampling reproduces full‑graph validation loss. Open gaps: adaptive samplers and dynamic graphs.
AI-written summary · about
chapters (8)
- 0:00Introduction
- 1:01Large-scale GNNs recap
- 3:33Graph sampling methods
- 8:15Sampling-based GNNs theory
- 12:15Local graph limits
- 23:05Theoretical results and proofs
- 27:55PubMed dataset validation
- 28:57Key takeaways and open questions
related talks
01h 31mGraphons and Graph Limits 2
18mGraphon Neural Networks and the Transferability of Graph Neural Networks
35mDistributed Models for Private Analysis of Graph Data
16mPreview: Graph NNs
01h 26mStreaming, Sketching and Sufficient Statistics II
48mBig Graph: Big Data applied to giant, dynamic graphs
27mDistribution Learning Meets Graph Structure Sampling
46mOn the Foundations of Deep Learning: SGD, Overparametrization, and Generalization