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

Jian Xu; Delu Zeng; John Paisley; Qibin Zhao

cs.LGAug 14, 2026

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

Authors: Jian Xu, Delu Zeng, John Paisley, Qibin Zhao

Organizations: RIKEN iTHEMS, Wako, Japan · RIKEN Center for Advanced Intelligence Project (AIP), Tokyo, Japan · South China University of Technology, Guangzhou, China · Columbia University, New York, NY, USA

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+σ}$ , 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\%$ ).

Figures & tables

Figure 1: Tail index along the interpolation path (Propositions 2 and 3 ). The geometric path coincides with the linear reference exactly — the grey band beneath it is that reference. The arithmetic path is pinned at the heavier tail for every interior $t$ and jumps only at the endpoint, so the quantity the model must learn is absent from the whole trajectory.

Figure 2: Verification of Proposition 5 . Measured against predicted relative edge error over extrapolation ratios $2$ – $25\times$ and tail-index errors $0.1$ – $0.6$ ( $r=0.978$ ). Points approach the identity as the first-order term grows; the systematic excess at small $|\Delta\alpha|$ is the sampling floor, which does not vanish with the tail-index error.

	$\beta$	$\alpha$	invalid
ground truth	$1.270$	$1.919\pm 0.384$	—
geometric, oracle params	$\mathbf{1.276}\pm 0.002$	$\mathbf{1.922}\pm 0.384$	$0\%$
arithmetic, oracle params	$1.282\pm 0.001$	$3.056\pm 1.150$	$\mathbf{27\%}$
full pipeline (all estimated)	$1.283\pm 0.003$	$1.835\pm 0.304$	$0\%$
graphon baseline	$2$ (identity)	—	edge error $473\%$

TABLE I: Synthetic round trip at

10.9\times

. oracle params isolates the flow by training on true parameters; full pipeline estimates everything from observed graphs. The graphon edge error is an identity, not a fitted quantity.

	transitivity	assortativity	LCC frac.	mean deg.	degW1
ground truth	$0.0366$	$0.0712$	$0.848$	$5.00$	—
geometric, oracle	$0.0363$	$0.0771$	$0.832$	$4.77$	$0.048$
arithmetic, oracle	$0.0353$	$0.0886$	$0.841$	$4.53$	$0.029$
full pipeline	$0.0256$	$-0.0109$	$0.918$	$5.00$	$0.021$

TABLE II: Structural statistics on the large graphs. degW1 is the

1

-Wasserstein distance between degree distributions on

\log(1+d)

. The arithmetic arm is competitive here while being badly wrong in Table I .

generator	valid	$\alpha$ mean	$\alpha$ sd	energy	$\beta$
ground truth	—	$1.924$	$0.400$	$0.0319$	$1.265$
flow (ours)	$\mathbf{100\%}$	$1.913$	$0.390$	$\mathbf{0.0372}$	$1.272$
full-covariance Gaussian	$98\%$	$1.923$	$0.375$	$0.0761$	$1.294$
diagonal Gaussian	$0\%$	$1.938$	$0.380$	$0.3868$	$1.265$
kernel density	$0\%$	$1.989$	$0.500$	$0.4188$	$1.268$
bootstrap (memorisation)	$100\%$	$1.926$	$0.392$	$0.0503$	$1.271$

TABLE III: Generators over

\theta

-space, trained on

2250

synthetic graphexes and evaluated against

750

held out. valid is the fraction of generated

\theta

that are admissible graphexes; energy is the energy distance to the held-out set, whose achievable floor — the training sample against the held-out sample — is

0.0319

. bootstrap resamples training

\theta

and is a memorisation reference, not a usable model.

$R$	bulk nodes	$\beta$ MAE	transitivity	assortativity	degW1
$25$	$24$	$0.100$	$0.032$	$-0.023$	$0.046$
$50$	$47$	$0.064$	$0.026$	$-0.020$	$0.021$
$100$	$86$	$\mathbf{0.045}$	$0.025$	$-0.011$	$0.046$
$200$	$132$	$0.084$	$0.026$	$-0.005$	$0.040$
$400$	$173$	$0.157$	$0.024$	$-0.006$	$0.069$
ground truth		—	$0.037$	$0.070$	—

TABLE IV: Bulk capacity

R

. Scaling accuracy is

U

-shaped with an optimum at

R=100

; structure improves only marginally and assortativity never recovers its sign, consistent with Proposition 4 .

	$\beta$ MAE	transitivity	assortativity	mean deg.	degW1
ground truth	—	$0.0346$	$0.0687$	$4.68$	—
single-pass	$0.0500$	$0.0236$	$-0.0101$	$4.77$	$0.0331$
fixed point, $1$ it.	$0.0500$	$\mathbf{0.0300}$	$-0.0097$	$5.01$	$\mathbf{0.0242}$
fixed point, $3$ it.	$0.0500$	$0.0307$	$-0.0105$	$5.08$	$0.0322$

TABLE V: Single-pass rank-one inversion against iterating

\psi

and

K

to marginal consistency. The tail index is untouched — it comes from the degree fit, not the inversion — while one iteration improves structural fidelity.

Figure 3: Out-of-sample extrapolation error across $13$ real networks and $39$ fit/extrapolate settings, against edge density. The method is ahead by roughly an order of magnitude throughout the sparse regime, the two curves meet near $e/n\approx 10$ , and inside the dense control ( $e/n=16.3$ ) the graphon baseline is the better model — the crossover the construction predicts.

dataset ( $n$ )	$e/n$	extrapolation	ours	graphon
as20000102 ( $6.5k$ )	$1.94$	$53/17/8\times$	$18.9/22.1/23.3\%$	$2079.3/659.8/311.4\%$
oregon1_010331 ( $11k$ )	$2.06$	$57/10/6\times$	$29.9/24.5/21.2\%$	$2000.0/560.9/277.9\%$
oregon1_010526 ( $11k$ )	$2.09$	$57/10/6\times$	$21.6/20.1/21.5\%$	$2147.9/629.9/312.8\%$
p2p-Gnutella31 ( $63k$ )	$2.36$	$34/11/6\times$	$45.8/16.9/3.7\%$	$954.4/365.0/210.4\%$
p2p-Gnutella25 ( $23k$ )	$2.41$	$30/10/6\times$	$44.6/21.0/8.4\%$	$860.3/325.7/186.8\%$
ca-HepTh ( $9.9k$ )	$2.63$	$27/9/5\times$	$36.7/44.3/23.1\%$	$760.3/255.6/132.4\%$

TABLE VI: Out-of-sample extrapolation on real networks: fit the tail index on a sub-sample only, predict the full-size edge count. All numbers are means over the

15

sub-sampling seeds of Table VII , so they are directly comparable to the baselines there. email-Eu-core is a deliberate dense control. All

13

networks are listed, ordered by edge density.

$\beta$ from		median	mean	$p$ (net-level)	wins	sparse	dense
constant mean degree	$\beta=1$	$62.2\%$	$61.9\%$	$2.4\!\times\!10^{-4}$	$13/13$	$55.0\%$	$69.2\%$
Hill tail-index estimator		$61.4\%$	$61.0\%$	$2.4\!\times\!10^{-4}$	$13/13$	$53.5\%$	$68.5\%$
fixed graphon	$\beta=2$	$260.3\%$	$444.5\%$	$2.4\!\times\!10^{-4}$	$13/13$	$365.0\%$	$129.4\%$
log–log regression on internal sub-samples		$35.0\%$	$38.9\%$	$1.7\!\times\!10^{-3}$	$12/13$	$33.0\%$	$43.8\%$
degree-distribution fit (ours)		$26.8\%$	$30.2\%$	—	—	$\mathbf{22.2\%}$	$33.9\%$
graphex tail index [ 24 ] , $p=0.8$		$24.8\%$	$26.9\%$	$9.4\!\times\!10^{-2}$	$3/13$	$22.9\%$	$24.9\%$

TABLE VII: Where the accuracy comes from, over

13

networks

\times

3

budgets and

15

sub-sampling seeds per setting. All rows but the last use the same prediction

e_{s}(n_{1}/n_{s})^{\beta}

and differ only in how

\beta

is obtained; the last knows the true inclusion probability. Median and mean are over the

39

settings. The test is network-level : errors are averaged within each network first, since the three budgets share a graph and are not independent, and a two-sided Wilcoxon signed-rank test is then run on the

13

paired values. “wins” counts networks on which ours is ahead. The last two columns split the settings at

e/n=3

Figure 4: Sampling budget against estimation error, median over $13$ networks at each budget. The ordering of methods is unchanged across the range, so an estimator can be chosen without knowing the budget in advance. The gap to the oracle — the price of not knowing the sampling rate — is roughly a factor of four and does not close as the budget grows.

	$s$ unknown				$s$ known
network	ours	[ 34 ]	sample	graphon	[ 34 ]	$d_{s}/s$
as20000102	$\mathbf{0.17}$	$0.35$	$0.30$	$2.83$	$0.37$	$1.47$
oregon1_010526	$\mathbf{0.24}$	$0.36$	$0.30$	$2.29$	$0.39$	$1.47$
ca-GrQc	$0.32$	$\mathbf{0.31}$	$0.63$	$2.17$	$0.24$	$1.18$
p2p-Gnutella25	$0.38$	$\mathbf{0.36}$	$0.54$	$2.33$	$0.37$	$1.26$
p2p-Gnutella08	$0.44$	$\mathbf{0.26}$	$0.74$	$1.97$	$0.24$	$1.08$

TABLE VIII: Degree-distribution estimation at full size from a

10\%

sample,

1

-Wasserstein distance on

\log(1+d)

, means over

15

seeds. Lower is better; bold marks the best method that does not know

s

. The two right-hand columns are oracles.

Figure 5: Tail-index estimation on synthetic data with known $\alpha$ . The estimator tracks the truth inside the shaded band — the range spanned by the fitted indices of every genuinely sparse network in Section VI-H — and saturates near $\alpha\approx 2.2$ above it. The saturation point coincides with the density at which the method ceases to be competitive.

Appendix figures & tables3 assets

Supplementary material from the paper’s appendix.

Appendix

	transitivity		degW1		edge error
network	real	ours	ours	graphon	ours	graphon
ca-GrQc	$0.630$	$0.008$	$\mathbf{0.32}$	$2.17$	$\mathbf{33\%}$	$700\%$
ca-HepTh	$0.284$	$0.003$	$\mathbf{0.45}$	$2.16$	$\mathbf{44\%}$	$763\%$
ca-CondMat	$0.264$	$0.003$	$\mathbf{0.82}$	$1.81$	$\mathbf{66\%}$	$415\%$
p2p-Gnutella08	$0.021$	$0.005$	$\mathbf{0.44}$	$1.97$	$\mathbf{41\%}$	$524\%$
as20000102	$0.010$	$\mathbf{0.032}$	$\mathbf{0.17}$	$2.83$	$\mathbf{43\%}$	$1735\%$

Appendix

TABLE IX: Training on

10\%

sub-samples and generating at full size (a

10

–

30\times

extrapolation). The model recovers edge count and degree distribution; clustering behaves exactly as Proposition 4 predicts. as20000102 and oregon1 are low-clustering networks and are reproduced within the class.

Panel of Figure 6 — Figure 6: Left: transitivity of generated graphs against that of the target network. Both models saturate near $10^{-2}$ regardless of the target. For the rank-one case Proposition 4 says exactly why; for our fitted $K$ this is an empirical observation that the ceiling is not escaped, not a proof that it cannot be. Right: edge-count error at two fitting fractions. Our error is nearly flat in the fraction, while the graphon baseline improves steeply as the extrapolation ratio shrinks — so the advantage is a large-ratio phenomenon, and at $s=0.25$ on ca-CondMat it reverses.

			$e_{\mathrm{gen}}/e_{\mathrm{real}}$		relative error
network	$s$	$\hat{\alpha}$	naive	anchored	naive	anchored
ca-CondMat	$0.25$	$1.94$	$\mathbf{3.48}$	$0.58$	$248\%$	$\mathbf{42\%}$
p2p-Gnutella25	$0.25$	$1.62$	$\mathbf{1.85}$	$0.71$	$85\%$	$\mathbf{29\%}$
as20000102	$0.10$	$1.40$	$0.48$	$0.81$	$52\%$	$\mathbf{19\%}$
p2p-Gnutella08	$0.25$	$1.51$	$0.43$	$0.58$	$57\%$	$\mathbf{42\%}$
oregon1_010526	$0.25$	$1.30$	$0.57$	$0.64$	$43\%$	$\mathbf{36\%}$

Appendix

TABLE X: Naive against anchored generation. The two over-producing settings are in bold; anchoring removes over-production everywhere.

Graphons of Line Graphs
Sep 3, 2024Sevvandi Kandanaarachchi, Cheng Soon OngGraphon Theory
Fast Graph Laplacian Estimation using Effective Resistance
Sep 20, 2026Christoffer Kjellson, Claudio Altafini, Emma TeglingGraph Structure Learning Probabilistic Graphical Models
Department of Automatic Control, Lund University · ELLIIT Strategic Research Area · Division of Automatic Control, Department of Electrical Engineering, Linköping University
Fully Inductive Cardinality Estimation
Jul 30, 2026Tim Schwabe, Lukas Ketzer, Maribel AcostaGraph Neural Networks Knowledge Graphs
Technical University of Munich, Munich, Germany

Sep 3, 2024J/K move · Enter open · S save

Graphons of Line Graphs

Sevvandi Kandanaarachchi, Cheng Soon Ong

Graphon Theory

Open paper AskPDF arXiv

We consider the problem of estimating graph limits, known as graphons, from observations of sequences of sparse finite graphs. In this paper we show a simple method that can shed light on a subset of sparse graphs. The method involves mapping the original graphs to their line graphs. We show that graphs satisfying a particular property, which we call the square-degree property are sparse, but give rise to dense line graphs. This enables the use of results on graph limits of dense graphs to derive convergence. In particular, star graphs satisfy the square-degree property resulting in dense line graphs and non-zero graphons of line graphs. We demonstrate empirically that we can distinguish different numbers of stars (which are sparse) by the graphons of their corresponding line graphs. Whereas in the original graphs, the different number of stars all converge to the zero graphon due to sparsity. Similarly, superlinear preferential attachment graphs give rise to dense line graphs almost surely. In contrast, dense graphs, including Erdos-Renyi graphs make the line graphs sparse, resulting in the zero graphon.

Abstract

Explore similar work

Graphons of Line Graphs

Fast Graph Laplacian Estimation using Effective Resistance

Fully Inductive Cardinality Estimation