# The Class of Random Graphs Arising from Exchangeable Random Measures

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

## Key facts

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

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

- [Order Matters: Probabilistic Modeling of Node Sequence for Graph Generation](https://mlsanity.com/paper/2106.06189/) (2021)
- [Asymptotics of Network Embeddings Learned via Subsampling](https://mlsanity.com/paper/2107.02363/) (2021)
- [Node Copying: A Random Graph Model for Effective Graph Sampling](https://mlsanity.com/paper/2208.02435/) (2022)
- [Learning Mean Field Games on Sparse Graphs: A Hybrid Graphex Approach](https://mlsanity.com/paper/2401.12686/) (2024)
- [Flowette: Flow Matching with Graphette Priors for Graph Generation](https://mlsanity.com/paper/2602.23566/) (2026)
- [GraphSPNs: Sum-Product Networks Benefit From Canonical Orderings](https://mlsanity.com/paper/2408.09451/) (2024)
- [Learning Mean Field Control on Sparse Graphs](https://mlsanity.com/paper/2501.17079/) (2025)
- [Graphons of Line Graphs](https://mlsanity.com/paper/2409.01656/) (2024)
- [Asymptotics of ℓ2 Regularized Network Embeddings](https://mlsanity.com/paper/2201.01689/) (2022)
- [Rapidly Varying Completely Random Measures for Modeling Extremely Sparse Networks](https://mlsanity.com/paper/2505.13206/) (2025)
- [Information Loss and Disparate Effects in Network Embeddings](https://mlsanity.com/paper/2509.12396/) (2025)
- [Intensity Dot Product Graphs](https://mlsanity.com/paper/2604.07810/) (2026)
- [Partially Observed Sparse Graphs: The Unknown Sampling Rate is a Tail Index](https://mlsanity.com/paper/2609.26199/) (2026)
- [Rethinking Epistemic Uncertainty in Node Classification through Information Growth](https://mlsanity.com/paper/2610.03418/) (2026)

## Abstract (arXiv)

We introduce a class of random graphs that we argue meets many of the desiderata one would demand of a model to serve as the foundation for a statistical analysis of real-world networks. The class of random graphs is defined by a probabilistic symmetry: invariance of the distribution of each graph to an arbitrary relabelings of its vertices. In particular, following Caron and Fox, we interpret a symmetric simple point process on ℝ_+2 as the edge set of a random graph, and formalize the probabilistic symmetry as joint exchangeability of the point process. We give a representation theorem for the class of random graphs satisfying this symmetry via a straightforward specialization of Kallenberg's representation theorem for jointly exchangeable random measures on ℝ_+2. The distribution of every such random graph is characterized by three (potentially random) components: a nonnegative real I ∈ ℝ_+, an integrable function S: ℝ_+ → ℝ_+, and a symmetric measurable function W: ℝ_+2 → [0,1] that satisfies several weak integrability conditions. We call the triple (I,S,W) a graphex, in analogy to graphons, which characterize the (dense) exchangeable graphs on mathbbN. Indeed, the model we introduce here contains the exchangeable graphs as a special case, as well as the "sparse exchangeable" model of Caron and Fox. We study the structure of these random graphs, and show that they can give rise to interesting structure, including sparse graph sequences. We give explicit equations for expectations of certain graph statistics, as well as the limiting degree distribution. We also show that certain families of graphexes give rise to random graphs that, asymptotically, contain an arbitrarily large fraction of the vertices in a single connected component.