Partially Observed Sparse Graphs: The Unknown Sampling Rate is a Tail Index
cs.LG
Submitted: 2026-08-14
Updated: 2026-08-14
License: http://creativecommons.org/licenses/by/4.0/
The gist: A large graph is often available only in part: a crawl stopped by its budget, a panel, a partial dump.
Terminology
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 e=e s/s squared 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+σ, so the sampling rate becomes estimable once the tail index σ is, and substituting it back gives e s(n 1/n s) 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%).
Sources
- DiPhon: Diffusion on Graphons for Scalable Graph Generation
- The Class of Random Graphs Arising from Exchangeable Random Measures
- Flow Matching for Generative Modeling
- Flow Straight and Fast: Learning to Generate and Transfer Data with Rectified Flow
- Building Normalizing Flows with Stochastic Interpolants
- DiGress: Discrete Denoising diffusion for graph generation
- Categorical Flow Maps
- Sparse Training of Discrete Diffusion Models for Graph Generation
Related papers
- Polynomial-Augmented Neural Networks (PANNs) with Weak Orthogonality Constraints for Enhanced Function and PDE Approximation
- AIRL-S: Unifying Reinforcement Learning and Search-Based Test-Time Scaling via Adversarial Inverse Reinforcement Learning
- Transformers as Bayesian In-Context Experimenters: Smoothness-Adaptive Efficient ATE Estimation
- Convergence issues in Relational Concept Analysis based on AOC-posets
- Beliefs Beyond Posteriors: Local-Consistency Optimisation for Bayesian Neural Networks
- Understanding Diffusion Models via Ratio-Based Function Approximation with SignReLU Networks