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

arXiv:2609.26199v1 Announce Type: new 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_1o 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 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%).

Source: arXiv cs.LG | 2026-09-23