NIPS 2016 Spotlight Video: Edge-exchangeable graphs and sparsity

D. Cai, T. Campbell, T. Broderick. Edge-exchangeable graphs and sparsity, NIPS 2016. Early versions in NIPS 2015 workshops on Networks in the Social and Information Sciences and Bayesian Nonparametrics. Submitted Oct/Nov 2015, accepted Nov 2015. [More info below.]

Diana Cai (UChicago Statistics): dianacai.com
Trevor Campbell (MIT CSAIL): trevorcampbell.me
Tamara Broderick (MIT CSAIL): tamarabroderick.com

Poster on Monday Dec. 5 @ Area 5+6+7+8 #162

Paper and appendix: https://papers.nips.cc/paper/6586-edge-exchangeable-graphs-and-sparsity

Abstract:

Many popular network models rely on the assumption of (vertex) exchangeability, in which the distribution of the graph is invariant to relabelings of the vertices. However, the Aldous-Hoover theorem guarantees that these graphs are dense or empty with probability one, whereas many real-world graphs are sparse. We present an alternative notion of exchangeability for random graphs, which we call edge exchangeability, in which the distribution of a graph sequence is invariant to the order of the edges. We demonstrate that edge-exchangeable models, unlike models that are traditionally vertex-exchangeable, can exhibit sparsity. To do so, we outline a general framework for graph generative models; by contrast to the pioneering work of Caron and Fox, models within our framework are stationary across steps of the graph sequence. In particular, our model grows the graph by instantiating more latent atoms of a single random measure as the data set size increases, rather than adding new atoms to the measure.

Early work appeared as:

1) T. Broderick and D. Cai. Edge-exchangeable graphs, sparsity, and power laws. NIPS 2015 Workshop on Bayesian nonparametrics: The Next Generation. Submitted Oct 20, accepted Nov 2. https://sites.google.com/site/nipsbnp2015/

Presented on Dec 12, 2015. All materials available on the workshop website, including:
Slides: https://drive.google.com/file/d/0B1-Vx4o3v8xfbU03ZjBRbWtkZHM/view
Poster: https://drive.google.com/file/d/0B1-Vx4o3v8xfempsWlNySlZoUkE/view
Paper: https://drive.google.com/file/d/0B1-Vx4o3v8xfTW5LQTBpeTV4T00/view

2) T. Broderick and D. Cai. Edge-exchangeable graphs and sparsity. NIPS 2015 Workshop on Networks in the Social and Information Sciences. Submitted Nov 2, accepted Nov 6. Presented on Dec 12, 2015.

Paper available on workshop website: http://stanford.edu/~jugander/NetworksNIPS2015/papers/NIPS_Networks_2015_edge_exchangeable.pdf

3) D. Cai and T. Broderick. Completely random measures for modeling power laws in sparse graphs. NIPS 2015 Workshop on Networks in the Social and Informational Sciences. Submitted Nov 2, accepted Nov 6. Presented on Dec 12, 2015.

Paper available on workshop website: http://stanford.edu/~jugander/NetworksNIPS2015/papers/NIPS_Networks_2015_power_laws.pdf

This work is concurrent to, and independent from, the following papers:
H. Crane and W. Dempsey. A framework for statistical network modeling. arXiv preprint 1509.08185, 2015.
H. Crane and W. Dempsey. Edge exchangeable models for network data. arXiv preprint 1603.04571, 2016.