Graphons and Graph Limits 2
Talkat Graph Limits and Processes on Networks: From Epidemics to Misinformation Boot Camp · 2022-08-29..09-02·
summary
Defines dense graph limits as graphons and shows that cut metric convergence is equivalent to matching subgraph frequencies, sampled-k distributions, generalized min‑cuts and physicists’ free energies, with quantitative bounds (e.g. total‑variation ≤ 10/√(log2 K) from K‑samples). Uses inhomogeneous random graphs and a sampling coupling to recover graphons, and proves a constructive approximation: every graphon is within ε in cut norm of a stochastic block model with ≤ 4^{1/ε^2} classes via the weak regularity lemma, using a potential‑function refinement that increases by ε^2 per step.
AI-written summary · about
chapters (35)
- 0:00Introduction to Graphs
- 1:15Measuring Similarity
- 2:56Cuts and Free Energy
- 3:47The Cut Metric
- 5:46Cut Distance Formula
- 7:49Equivalence Theorems
- 10:12Proof Idea
- 12:54Subgraph Frequencies
- 15:23Graphon Properties
- 17:31Comparing Graphons
- 20:13Iterative Difference Estimation
- 24:35Total Variation Distance
- 27:04Inhomogeneous Random Graphs
- 29:34Stochastic Block Models
- 30:45Sampling and Concentration
- 33:05Convergence Rates
- 37:28Lecture Summary
- 39:39Limits in Cut Metric
- 41:10Defining Limit Convergence
- 43:28Uniqueness and Compactness
- 55:13Completion of Graph Space
- 58:16Weak Regularity Lemma
- 59:10Block Model Approximation
- 1:02:03Constructing Approximations
- 1:02:54Partitioning Techniques
- 1:05:05Proof of Lemma
- 1:08:44Iterative Refinement Proof
- 1:11:50Contradiction Method
- 1:14:19Scalar Product Inequality
- 1:16:00Iterative Squared Bounds
- 1:19:30Controlling the Error
- 1:21:45Constructive Bounds
- 1:24:39Optimal Bounds
- 1:25:53Topological Completion
- 1:27:16Final Proof Review
related talks
01h 28mBoot camp on graphons for graph learning
49mExtremal Cuts of Sparse Random Graphs
39mA Local Graph Limits Perspective on Sampling-Based GNNs
54mSzemerédi Regularity Lemma in Graph Machine Learning
18mGraphon Neural Networks and the Transferability of Graph Neural Networks
49mRecent Advances in Counting Sparse Graphs
54mGraph Machine Learning & Random Graph Models
45mThe lower tail: Poisson approximation revisited