# Sparse graphs using exchangeable random measures

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

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Jan 2014.

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

- [Anomalous Edge Detection in Edge Exchangeable Social Network Models](https://mlsanity.com/paper/2109.12727/) (2021)
- [Advancing Graph Generation through Beta Diffusion](https://mlsanity.com/paper/2406.09357/) (2024)
- [Using Embeddings for Causal Estimation of Peer Influence in Social Networks](https://mlsanity.com/paper/2205.08033/) (2022)
- [Nonparametric Sparse Tensor Factorization with Hierarchical Gamma Processes](https://mlsanity.com/paper/2110.10082/) (2021)
- [Nonparametric Embeddings of Sparse High-Order Interaction Events](https://mlsanity.com/paper/2207.03639/) (2022)
- [Nonparametric Modeling of Higher-Order Interactions via Hypergraphons](https://mlsanity.com/paper/2105.08678/) (2021)
- [Node Copying: A Random Graph Model for Effective Graph Sampling](https://mlsanity.com/paper/2208.02435/) (2022)
- [EEGNN: Edge Enhanced Graph Neural Network with a Bayesian Nonparametric Graph Model](https://mlsanity.com/paper/2208.06322/) (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)
- [Random Edge Coding: One-Shot Bits-Back Coding of Large Labeled Graphs](https://mlsanity.com/paper/2305.09705/) (2023)
- [Learning Mean Field Control on Sparse Graphs](https://mlsanity.com/paper/2501.17079/) (2025)
- [Modularity maximisation for graphons](https://mlsanity.com/paper/2101.00503/) (2021)
- [Implications of sparsity and high triangle density for graph representation learning](https://mlsanity.com/paper/2210.15277/) (2022)
- [Graphons of Line Graphs](https://mlsanity.com/paper/2409.01656/) (2024)
- [Geodesic Length Distribution in Sparse Network Ensembles](https://mlsanity.com/paper/2111.02330/) (2021)
- [Nonlinear Permuted Granger Causality](https://mlsanity.com/paper/2308.06220/) (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)
- [When Edge Independence Fails: Joint Graph Diffusion with Latent Sociability Priors](https://mlsanity.com/paper/2610.13765/) (2026)

## Abstract (arXiv)

Statistical network modeling has focused on representing the graph as a discrete structure, namely the adjacency matrix, and considering the exchangeability of this array. In such cases, the Aldous-Hoover representation theorem (Aldous, 1981;Hoover, 1979 applies and informs us that the graph is necessarily either dense or empty. In this paper, we instead consider representing the graph as a measure on ℝ_+2. For the associated definition of exchangeability in this continuous space, we rely on the Kallenberg representation theorem (Kallenberg, 2005). We show that for certain choices of such exchangeable random measures underlying our graph construction, our network process is sparse with power-law degree distribution. In particular, we build on the framework of completely random measures (CRMs) and use the theory associated with such processes to derive important network properties, such as an urn representation for our analysis and network simulation. Our theoretical results are explored empirically and compared to common network models. We then present a Hamiltonian Monte Carlo algorithm for efficient exploration of the posterior distribution and demonstrate that we are able to recover graphs ranging from dense to sparse--and perform associated tests--based on our flexible CRM-based formulation. We explore network properties in a range of real datasets, including Facebook social circles, a political blogosphere, protein networks, citation networks, and world wide web networks, including networks with hundreds of thousands of nodes and millions of edges.