# Partially Observed Sparse Graphs: The Unknown Sampling Rate is a Tail Index

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 18 of its 35 references that are in the map.
- First posted on arXiv 14 Aug 2026.

## Builds on (most cited first, 18 of 18)

- [Flow Matching for Generative Modeling](https://mlsanity.com/paper/2210.02747/) (2022)
- [Flow Straight and Fast: Learning to Generate and Transfer Data with Rectified Flow](https://mlsanity.com/paper/2209.03003/) (2022)
- [Building Normalizing Flows with Stochastic Interpolants](https://mlsanity.com/paper/2209.15571/) (2022)
- [DiGress: Discrete Denoising diffusion for graph generation](https://mlsanity.com/paper/2209.14734/) (2022)
- [A Survey on Generative Diffusion Model](https://mlsanity.com/paper/2209.02646/) (2022)
- [Categorical Flow Maps](https://mlsanity.com/paper/2602.12233/) (2026)
- [Efficient and Scalable Graph Generation through Iterative Local Expansion](https://mlsanity.com/paper/2312.11529/) (2023)
- [Sparse Training of Discrete Diffusion Models for Graph Generation](https://mlsanity.com/paper/2311.02142/) (2023)
- [Unifying Generation and Prediction on Graphs with Latent Graph Diffusion](https://mlsanity.com/paper/2402.02518/) (2024)
- [Sparse graphs using exchangeable random measures](https://mlsanity.com/paper/1401.1137/) (2014)
- [Generative Modelling of Structurally Constrained Graphs](https://mlsanity.com/paper/2406.17341/) (2024)
- [The Class of Random Graphs Arising from Exchangeable Random Measures](https://mlsanity.com/paper/1512.03099/) (2015)
- [A General Framework for Estimating Graphlet Statistics via Random Walk](https://mlsanity.com/paper/1603.07504/) (2016)
- [Edge-exchangeable graphs and sparsity](https://mlsanity.com/paper/1603.06898/) (2016)
- [Sampling and Estimation for (Sparse) Exchangeable Graphs](https://mlsanity.com/paper/1611.00843/) (2016)
- [Sampling unknown large networks restricted by low sampling rates](https://mlsanity.com/paper/2308.14279/) (2023)
- [Estimating network degree distributions under sampling: An inverse problem, with applications to monitoring social media networks](https://mlsanity.com/paper/1305.4977/) (2013)
- [DiPhon: Diffusion on Graphons for Scalable Graph Generation](https://mlsanity.com/paper/2607.07232/) (2026)

## Abstract (arXiv)

A large graph is often available only in part: a crawl stopped by its budget, a panel, a partial dump. When the sampled fraction s is known by design the total edge count follows from hat e=es/s2 and no model is needed. We treat the case where s is unknown and the population size is known. Our main result is a reduction: under a sparse exchangeable (graphex) model the expected non-isolated fraction obeys ns/n1→ s1+σ, so the sampling rate becomes estimable once the tail index σ is, and substituting it back gives es(n1/ns)2/(1+σ) -- the same estimator, with the design quantity inferred. Estimating global edge cardinality in a sparse graph is therefore, in expectation, tail-index estimation, and the quadratic graphon estimator is the case σ=0: it fails by an identity rather than by a fit (260% median error against 27%). We bound the finite-size error of the substitution and show the reduction is modular in the tail-index estimator --- filled with a published closed-form one it reaches 21.7% over 13 networks and 39 sampling budgets with no fitting at all. Fitting a full graphex additionally returns the degree distribution at any size and a generative object, in a representation where sparsity is a coordinate and the interpolation path is dictated rather than chosen. Two limits are exact: rank-one graphexes have transitivity fixed by the degree profile, so high-clustering graphs lie outside the class; and under snowball or random-walk crawls every method here fails, the design-based oracle worst of all (7.8% to 588%).