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 [12], 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 dataset size increases, rather than adding new atoms to the measure.
Preliminary versions appeared as:
Main publication:
@inproceedings{cai2016edge,
title={Edge-exchangeable graphs and sparsity},
author={Cai, Diana and Campbell, Trevor and Broderick, Tamara},
booktitle={Advances in Neural Information Processing Systems 29},
pages={4249--4257},
year={2016}
}
Workshop papers:
@inproceedings{cai2015completely,
title={Completely random measures for modeling power laws in sparse graphs},
author={Cai, Diana and Broderick, Tamara},
booktitle={NIPS 2015 Workshop on Networks in the Social and Information Sciences},
year={2015}
}
@inproceedings{broderick2015edge,
title={Edge-exchangeable graphs and sparsity},
author={Broderick, Tamara and Cai, Diana},
booktitle={NIPS 2015 Workshop on Networks in the Social and Information Sciences},
year={2015}
}
@inproceedings{broderick2015edge,
title={Edge-exchangeable graphs, sparsity, and power laws},
author={Broderick, Tamara and Cai, Diana},
booktitle={NIPS 2015 Workshop on Bayesian Nonparametrics: The Next Generation},
year={2015}
}