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

Abstract

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}=e_s/s^2$ 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 $n_s/n_1\to s^{1+\sigma }$, so the sampling rate becomes estimable once the tail index $\sigma$ is, and substituting it back gives $e_s(n_1/n_s{)}^{2/(1+\sigma )}$ -- 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 $\sigma =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 \emph{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\%$).