# Edge-exchangeable graphs and sparsity

arXiv: https://arxiv.org/abs/1603.06898 · HTML: https://mlsanity.com/paper/1603.06898/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Mar 2016.

## Built on by (most cited first, 7 of 7)

- [Order Matters: Probabilistic Modeling of Node Sequence for Graph Generation](https://mlsanity.com/paper/2106.06189/) (2021)
- [Anomalous Edge Detection in Edge Exchangeable Social Network Models](https://mlsanity.com/paper/2109.12727/) (2021)
- [Conformal Inductive Graph Neural Networks](https://mlsanity.com/paper/2407.09173/) (2024)
- [Graphons of Line Graphs](https://mlsanity.com/paper/2409.01656/) (2024)
- [Goodness-of-Fit of Attributed Probabilistic Graph Generative Models](https://mlsanity.com/paper/2308.03773/) (2023)
- [Rapidly Varying Completely Random Measures for Modeling Extremely Sparse Networks](https://mlsanity.com/paper/2505.13206/) (2025)
- [Partially Observed Sparse Graphs: The Unknown Sampling Rate is a Tail Index](https://mlsanity.com/paper/2609.26199/) (2026)

## Abstract (arXiv)

A known failing of many popular random graph models is that the Aldous-Hoover Theorem guarantees these graphs are dense with probability one; that is, the number of edges grows quadratically with the number of nodes. This behavior is considered unrealistic in observed graphs. We define a notion of edge exchangeability for random graphs in contrast to the established notion of infinite exchangeability for random graphs --- which has traditionally relied on exchangeability of nodes (rather than edges) in a graph. We show that, unlike node exchangeability, edge exchangeability encompasses models that are known to provide a projective sequence of random graphs that circumvent the Aldous-Hoover Theorem and exhibit sparsity, i.e., sub-quadratic growth of the number of edges with the number of nodes. We show how edge-exchangeability of graphs relates naturally to existing notions of exchangeability from clustering (a.k.a. partitions) and other familiar combinatorial structures.