Edge-exchangeable graphs and sparsity (NIPS 2016)





The interactive transcript could not be loaded.


Rating is available when the video has been rented.
This feature is not available right now. Please try again later.
Published on Nov 13, 2016

Edge-exchangeable graphs and sparsity: NIPS 2016 spotlight video

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


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.

Comments are turned off
When autoplay is enabled, a suggested video will automatically play next.

Up next

to add this to Watch Later

Add to

Loading playlists...