# Sampling and Estimation for (Sparse) Exchangeable Graphs

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Nov 2016.

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

- [Nonparametric Modeling of Higher-Order Interactions via Hypergraphons](https://mlsanity.com/paper/2105.08678/) (2021)
- [Flowette: Flow Matching with Graphette Priors for Graph Generation](https://mlsanity.com/paper/2602.23566/) (2026)
- [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)

Sparse exchangeable graphs on ℝ_+, and the associated graphex framework for sparse graphs, generalize exchangeable graphs on mathbbN, and the associated graphon framework for dense graphs. We develop the graphex framework as a tool for statistical network analysis by identifying the sampling scheme that is naturally associated with the models of the framework, and by introducing a general consistent estimator for the parameter (the graphex) underlying these models. The sampling scheme is a modification of independent vertex sampling that throws away vertices that are isolated in the sampled subgraph. The estimator is a dilation of the empirical graphon estimator, which is known to be a consistent estimator for dense exchangeable graphs; both can be understood as graph analogues to the empirical distribution in the i.i.d. sequence setting. Our results may be viewed as a generalization of consistent estimation via the empirical graphon from the dense graph regime to also include sparse graphs.