Graphons and Graph Limits 3
Talkat Graph Limits and Processes on Networks: From Epidemics to Misinformation Boot Camp · 2022-08-29..09-02·
summary
Focuses on sparse, unbounded-degree networks and gives concrete convergence definitions and estimators: shows two non-equivalent limits — a rescaled metric (divide by edge count, needs uniform upper regularity) and a stretched graphon (Poisson graphon process, needs uniform tail regularity) — and proves when each applies. Proposes a practical estimator (best K-block least-squares empirical graphon) with L2 consistency, gives node-level differential privacy algorithms that match min–max rates as privacy vanishes (n rho_n must grow ≥ O(log n)), and improves matrix-completion sampling thresholds toward the 1/n regime.
AI-written summary · about
chapters (9)
- 0:00Introduction and overview
- 2:55Dense graph foundations
- 8:24Left and sampling convergence
- 17:30Sparse graphs and models
- 26:40Rescaling and metrics
- 35:35Regularity and graph processes
- 45:07Estimation and latent variables
- 1:07:26Differential privacy
- 1:15:57Applications and conclusion
related talks
47mMultiscale Analysis on and of Graphs
01h 23mProperty Testing for Graphs
32mFrom Sparse Matrices to Graphs and Back Again
35mPairwise Network Differential Privacy
23mTowards General and Tight Hardness Results for Graph Problems
30mScalable Graph-Parallel Inference Algorithms and Systems
33mPrivacy of Decentralized Machine Learning
35mSuperlinear Lower Bounds for Multipass Graph Processing