Edge-exchangeable graphs and sparsity
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...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Morgan Kaufmann Publishers
2020
|
| Online Access: | https://hdl.handle.net/1721.1/128782 |
| _version_ | 1811068467903725568 |
|---|---|
| author | Campbell, Trevor David Broderick, Tamara A |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Campbell, Trevor David Broderick, Tamara A |
| author_sort | Campbell, Trevor David |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T07:56:27Z |
| format | Article |
| id | mit-1721.1/128782 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T07:56:27Z |
| publishDate | 2020 |
| publisher | Morgan Kaufmann Publishers |
| record_format | dspace |
| spelling | mit-1721.1/1287822022-09-23T09:47:47Z Edge-exchangeable graphs and sparsity Campbell, Trevor David Broderick, Tamara A Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory 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. 2020-12-10T21:33:13Z 2020-12-10T21:33:13Z 2017-02 2020-12-03T17:48:13Z Article http://purl.org/eprint/type/ConferencePaper 1049-5258 https://hdl.handle.net/1721.1/128782 Cai, Diana, Trevor Campbell and Tamara Broderick. “Edge-exchangeable graphs and sparsity.” Advances in Neural Information Processing Systems, 29 (February 2017) © 2017 The Author(s) en Advances in Neural Information Processing Systems Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Morgan Kaufmann Publishers Neural Information Processing Systems (NIPS) |
| spellingShingle | Campbell, Trevor David Broderick, Tamara A Edge-exchangeable graphs and sparsity |
| title | Edge-exchangeable graphs and sparsity |
| title_full | Edge-exchangeable graphs and sparsity |
| title_fullStr | Edge-exchangeable graphs and sparsity |
| title_full_unstemmed | Edge-exchangeable graphs and sparsity |
| title_short | Edge-exchangeable graphs and sparsity |
| title_sort | edge exchangeable graphs and sparsity |
| url | https://hdl.handle.net/1721.1/128782 |
| work_keys_str_mv | AT campbelltrevordavid edgeexchangeablegraphsandsparsity AT brodericktamaraa edgeexchangeablegraphsandsparsity |