# Bootstrapping Exchangeable Random Graphs

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

## Key facts

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

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

- [One-Hot Graph Encoder Embedding](https://mlsanity.com/paper/2109.13098/) (2021)
- [Dynamic Silos: Increased Modularity in Intra-organizational Communication Networks during the Covid-19 Pandemic](https://mlsanity.com/paper/2104.00641/) (2021)
- [Higher-order accurate two-sample network inference and network hashing](https://mlsanity.com/paper/2208.07573/) (2022)
- [Confidence Intervals for Error Rates in 1:1 Matching Tasks: Critical Statistical Analysis and Recommendations](https://mlsanity.com/paper/2306.01198/) (2023)
- [Block Dense Weighted Networks with Augmented Degree Correction](https://mlsanity.com/paper/2105.12290/) (2021)
- [Valid Bootstraps for Network Embeddings with Applications to Network Visualisation](https://mlsanity.com/paper/2410.20895/) (2024)
- [Rethinking Epistemic Uncertainty in Node Classification through Information Growth](https://mlsanity.com/paper/2610.03418/) (2026)

## Abstract (arXiv)

We introduce two new bootstraps for exchangeable random graphs. One, the "empirical graphon bootstrap", is based purely on resampling, while the other, the "histogram bootstrap", is a model-based "sieve" bootstrap. We show that both of them accurately approximate the sampling distributions of motif densities, i.e., of the normalized counts of the number of times fixed subgraphs appear in the network. These densities characterize the distribution of (infinite) exchangeable networks. Our bootstraps therefore give a valid quantification of uncertainty in inferences about fundamental network statistics, and so of parameters identifiable from them.