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
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^=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%).
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× 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 ∣Δα∣ is the sampling floor, which does not vanish with the tail-index error.
β
α
invalid
ground truth
1.270
1.919±0.384
—
geometric, oracle params
1.276±0.002
1.922±0.384
0%
arithmetic, oracle params
1.282±0.001
3.056±1.150
27%
full pipeline (all estimated)
1.283±0.003
1.835±0.304
0%
graphon baseline
2 (identity)
—
edge error 473%
TABLE I: Synthetic round trip at 10.9× . 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
α mean
α sd
energy
β
ground truth
—
1.924
0.400
0.0319
1.265
flow (ours)
100%
1.913
0.390
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 θ -space, trained on 2250 synthetic graphexes and evaluated against 750 held out. valid is the fraction of generated θ 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 θ and is a memorisation reference, not a usable model.
R
bulk nodes
β 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
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 .
β 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
0.0300
−0.0097
5.01
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 ψ 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≈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×
18.9/22.1/23.3%
2079.3/659.8/311.4%
oregon1_010331 ( 11k )
2.06
57/10/6×
29.9/24.5/21.2%
2000.0/560.9/277.9%
oregon1_010526 ( 11k )
2.09
57/10/6×
21.6/20.1/21.5%
2147.9/629.9/312.8%
p2p-Gnutella31 ( 63k )
2.36
34/11/6×
45.8/16.9/3.7%
954.4/365.0/210.4%
p2p-Gnutella25 ( 23k )
2.41
30/10/6×
44.6/21.0/8.4%
860.3/325.7/186.8%
ca-HepTh ( 9.9k )
2.63
27/9/5×
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.
β from
median
mean
p (net-level)
wins
sparse
dense
constant mean degree
β=1
62.2%
61.9%
2.4×10−4
13/13
55.0%
69.2%
Hill tail-index estimator
61.4%
61.0%
2.4×10−4
13/13
53.5%
68.5%
fixed graphon
β=2
260.3%
444.5%
2.4×10−4
13/13
365.0%
129.4%
log–log regression on internal sub-samples
35.0%
38.9%
1.7×10−3
12/13
33.0%
43.8%
degree-distribution fit (ours)
26.8%
30.2%
—
—
22.2%
33.9%
graphex tail index [ 24 ] , p=0.8
24.8%
26.9%
9.4×10−2
3/13
22.9%
24.9%
TABLE VII: Where the accuracy comes from, over 13 networks ×3 budgets and 15 sub-sampling seeds per setting. All rows but the last use the same prediction es(n1/ns)β and differ only in how β 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 ]
ds/s
as20000102
0.17
0.35
0.30
2.83
0.37
1.47
oregon1_010526
0.24
0.36
0.30
2.29
0.39
1.47
ca-GrQc
0.32
0.31
0.63
2.17
0.24
1.18
p2p-Gnutella25
0.38
0.36
0.54
2.33
0.37
1.26
p2p-Gnutella08
0.44
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 α . 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 α≈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
0.32
2.17
33%
700%
ca-HepTh
0.284
0.003
0.45
2.16
44%
763%
ca-CondMat
0.264
0.003
0.82
1.81
66%
415%
p2p-Gnutella08
0.021
0.005
0.44
1.97
41%
524%
as20000102
0.010
0.032
0.17
2.83
43%
1735%
Appendix
TABLE IX: Training on 10% sub-samples and generating at full size (a 10 – 30× 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.
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.
egen/ereal
relative error
network
s
α^
naive
anchored
naive
anchored
ca-CondMat
0.25
1.94
3.48
0.58
248%
42%
p2p-Gnutella25
0.25
1.62
1.85
0.71
85%
29%
as20000102
0.10
1.40
0.48
0.81
52%
19%
p2p-Gnutella08
0.25
1.51
0.43
0.58
57%
42%
oregon1_010526
0.25
1.30
0.57
0.64
43%
36%
Appendix
TABLE X: Naive against anchored generation. The two over-producing settings are in bold; anchoring removes over-production everywhere.
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.
Inferring network topology from noisy node observations is a central problem in graph signal processing. In this paper, we consider Laplacian-constrained graph estimation for Gaussian Markov random fields, focusing on the underdetermined regime in which the number of samples is smaller than the number of graph nodes. Existing approaches often formulate the problem as a sparsity-regularized maximum-likelihood estimation problem. While effective, such methods typically require iterative optimization and are often computationally demanding, particularly under Laplacian constraints. Instead, we propose a non-iterative estimator of graph Laplacians that uses effective resistance for regularization, and evaluate the method using a simple sparsification procedure. Experiments show that with some trade-off in edge and weight recovery on the considered dataset, computational cost for moderately sized graphs can be substantially reduced.
Christoffer Kjellson, Claudio Altafini, Emma Tegling
Department of Automatic Control, Lund University · ELLIIT Strategic Research Area · Division of Automatic Control, Department of Electrical Engineering, Linköping University
Query optimization of Basic Graph Patterns (BGP) SPARQL queries over Knowledge Graphs (KG) requires accurate cardinality estimation. Recently published learned estimators outperform statistics- and sampling-based approaches, but share a limitation preventing their adoption in real-world triplestores: they are transductive and require retraining when the underlying graph changes or when applied to new graphs. We present FICE (Fully Inductive Cardinality Estimation), the first learned cardinality estimator for BGP queries over KGs that generalizes to entirely unseen graphs (including unseen relations), without any retraining. FICE is a graph neural network (GNN) with two coupled components. First, an encoder GNN over a factor-graph view of the KG produces entity and relation embeddings. We prove that BGP cardinality is a local function of the 2-hop neighborhood around bound terms in this view, motivating the local message-passing encoder. A decoder GNN then composes these embeddings along the join topology of the query to predict log-cardinality. The encoder and decoder are trained jointly, making the embeddings specialized for cardinality estimation. FICE is trained using neighborhood sampling to scale to KGs with millions of triples, and decouples embedding generation from cardinality decoding to enable estimation latency below a millisecond. Compared to learned and non-learned baselines over 10 KGs, FICE reduces the overall median q-error from 13.54 (for the best competitor) to 5.34 and dominates all approaches in tail behavior.