Nonparametric Bayesian Methods: Models, Algorithms, and Applications IV
summary
Explains why node exchangeability (Aldous–Hoover/graphon representation) forces dense or empty growing graphs with edges ~N^2, and proposes edge exchangeability with a graph-paintbox representation where steps add edges, not nodes. Shows a practical subclass: assign countable vertex rates Wi from a completely random measure with power-law tails and connect i–j with probability ~WiWj, which yields sparse graphs (edges grow subquadratically; with tails ∝x^(−α) one gets power-law vertex growth and linear edge growth for 1/2<α<1).
AI-written summary · about
chapters (16)
- 0:00Intro
- 1:41Probabilistic models for graphs
- 6:38Sequence of graphs
- 9:45The Old Way: Nodes
- 11:21The Old Way: Exchangeability
- 11:44The Old Way: Node exchangeability
- 12:03Aldous-Hoover
- 17:04A New Way: Edges
- 18:47Edge exchangeability
- 25:12Exchangeable probability functions
- 36:51Feature allocation is exchangeable if it has a feature paintbox representation
- 39:03Edge-exchangeable graph
- 40:39Cor (CCB). A graph sequence is edge- exchangeable iff it has a graph paintbox
- 45:25How to prove sparsity?
- 48:07What we know so far
- 51:55Nonparametric Bayes
related talks
35mDistributed Models for Private Analysis of Graph Data
54mNode Privacy, High-dimensional Graph Summaries, and Block Models
49mRecent Advances in Counting Sparse Graphs
01h 02mGraph Powering
01h 40mBoot camp on generalization theory for graph learning
01h 01mToward Universal Graph Representations: Foundations and Frontiers of Graph Foundation Models
31mSimple Models and Exact Algorithms for Computing Network Modules
45mCorrelated Stochastic Block Models: Graph Matching And Community Recovery