📊 statistics

Parametric Bootstrap for Fixed Edge-Probability Network Models

This paper proposes a two-level parametric bootstrap procedure to correct the inherent bias of standard network resampling methods under the Chung-Lu model, thereby enabling more accurate uncertainty quantification and confidence interval construction for general network statistics.

Original authors: Zhixuan Shao, Can M. Le

Published 2026-05-29

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Zhixuan Shao, Can M. Le

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a giant, complex social network, like a map of who knows whom in a massive city. You want to understand specific features of this city, such as "How many groups of three friends exist?" (triangles) or "How tightly knit is a specific person's neighborhood?" (clustering coefficient).

The problem is that you only have one snapshot of this city. You don't know the "true" rules that govern how people made friends in the first place. You only see the result. To make smart decisions or predictions, you need to know: How much could these numbers change if we took a different snapshot of the same city? In statistics, this is called uncertainty.

This paper proposes a new way to measure that uncertainty, specifically for networks where every person has their own unique personality (some are popular, some are shy), rather than assuming everyone is exactly the same.

Here is the breakdown of their solution using simple analogies:

1. The Problem: The "Blind Chef" Mistake

Imagine you are a chef trying to guess the exact recipe of a soup you just tasted.

The Old Way (Standard Bootstrap): You taste the soup, guess the recipe (e.g., "It has 2 spoons of salt and 1 carrot"), and then try to recreate the soup in your kitchen using your guess of the recipe. You taste your new soup and compare it to the original.
The Flaw: The paper shows that this method is often biased. Because your guess of the recipe isn't perfect, your new soup tastes slightly different from the original, even if you followed your guess perfectly. In the paper's language, the "natural" way of resampling networks (estimating the model first, then simulating) creates a systematic error. It's like the chef's guess of the salt amount is slightly off, so every soup they make is too salty, leading them to think the original soup was too salty when it wasn't.

2. The Solution: The "Double-Check" Kitchen (Two-Level Bootstrap)

To fix this, the authors introduce a Two-Level Bootstrap. Think of this as a "meta-tasting" process.

Level 1 (The First Guess): You taste the original soup and guess the recipe (let's call this Recipe A).
Level 2 (The Second Guess): Now, imagine you have a team of sous-chefs. Each one takes Recipe A and tries to guess their own version of the recipe based on it. They create Recipe B, Recipe C, Recipe D, etc.
The Magic: By comparing the soups made from Recipe A against the soups made from Recipes B, C, and D, you can mathematically calculate exactly how much your first guess (Recipe A) was off.

This "double-check" allows the authors to subtract the error caused by their initial guess. It's like realizing, "Oh, my first guess of the salt was 10% too high, so I need to adjust my final conclusion."

3. Why This Matters: The "Fixed" vs. "Random" City

Most previous methods assumed that the city was generated by a "random" process where everyone is interchangeable (like rolling dice for every friendship).

The Paper's Approach: This paper assumes the city has a fixed set of rules. Person A is naturally popular, and Person B is naturally shy. These traits don't change; only the specific friendships (the edges) are random.
The Benefit: This is crucial for local statistics. If you want to know how "central" a specific famous person is, you don't want to pretend they are a random person. You want to keep their specific identity fixed while testing how their connections might vary. The authors' method respects these fixed identities, whereas older methods might accidentally "shuffle" the personalities around, creating false uncertainty.

4. The Result: Sharper, More Accurate Confidence Intervals

When you measure uncertainty, you usually draw a "confidence interval" (a range of values where the true answer likely lies).

Without the fix: The range is often shifted in the wrong direction (biased) and might be too wide or too narrow.
With the Two-Level Bootstrap: The authors show that this method "corrects the aim." It shifts the range so it actually covers the true value more often.
The Bonus: They also prove that using this method often gives you a narrower range (more precise) than just looking at the raw data, because it uses the estimated rules of the network to filter out noise.

Summary Analogy

Imagine trying to guess the average height of a specific group of people, but you can only measure one person at a time, and your ruler is slightly bent.

Old Method: You measure the person, realize your ruler is bent, guess how much it's bent, and try to correct the measurement. But your guess about the bend is also wrong, so your final number is still off.
This Paper's Method: You measure the person. Then, you use your "bent ruler" to measure a second imaginary person. Then you use that result to measure a third. By comparing how the "bend" affects the chain of measurements, you can mathematically figure out exactly how much the ruler was distorting the truth and fix it.

In short: The paper provides a mathematical "error-correcting code" for network data. It admits that our first guess of how a network works is imperfect, and it uses a second layer of simulation to calculate and remove that imperfection, giving us much more reliable answers about the network's true structure.

Technical Summary: Parametric Bootstrap for Fixed Edge-Probability Network Models

Problem Statement

The paper addresses the challenge of quantifying the uncertainty of network statistics (e.g., subgraph counts, clustering coefficients, centrality measures) in random network data. While existing network resampling methods, such as subsampling and jackknife procedures, have been developed primarily for count statistics under node-exchangeable graphon models, they often fail to address two critical issues:

Non-exchangeability: Many practical applications involve networks with heterogeneous node properties where the assumption of node exchangeability (invariance to label permutations) is undesirable or incorrect. In such cases, preserving node-specific information is crucial.
Bootstrap Bias: The standard "natural" parametric bootstrap, which estimates the network-generating model parameters and then resamples from the estimated model, suffers from non-negligible bias. This bias arises because the plug-in estimator of the network statistic, $\hat{\mu} = \mu(\hat{P})$ , does not accurately approximate the true expectation $\mu(P)$ when the number of parameters grows with the network size $n$ . Specifically, the bias-to-standard-deviation ratio can be of order $\Theta(p^{-1/2})$ or $\Theta((np)^{-1/2})$ , rendering standard confidence intervals invalid, particularly in sparse networks.

The authors focus on the Chung–Lu model (a fixed edge-probability model where $P_{ij} = p\theta_i\theta_j$ ) as a working framework. Unlike graphon models where latent positions are random, this setting assumes fixed latent positions (or a fixed edge-probability matrix $P$ ), meaning the only randomness stems from the independent Bernoulli realization of edges.

Methodology

The paper proposes a two-level (double) bootstrap procedure to correct the bias inherent in the standard parametric bootstrap.

Natural Parametric Bootstrap (One-Level):
- Estimate the edge-probability matrix $\hat{P}$ from the observed network $A$ (e.g., using Maximum Likelihood Estimation or SVD).
- Generate $B$ bootstrap networks $\hat{A}^{(b)}$ from $\hat{P}$ .
- Compute the statistic $T(\hat{A}^{(b)})$ for each sample.
- The distribution of these statistics approximates the distribution of $T(A)$ , but the mean of this bootstrap distribution, $\mu(\hat{P})$ , is biased relative to the true mean $\mu(P)$ .
Two-Level Bootstrap (Bias Correction):
- Level 1: Generate $B_1$ bootstrap networks $\hat{A}^{(b)}$ from the estimated model $\hat{P}$ .
- Level 2: For each $\hat{A}^{(b)}$ , re-estimate the model parameters to obtain $\hat{\hat{P}}^{(b)}$ . Then, generate $B_2$ second-level networks $\hat{\hat{A}}^{(b,c)}$ from $\hat{\hat{P}}^{(b)}$ .
- Bias Estimation: The bias of the one-level estimator is estimated as:
  $\widehat{\text{Bias}}_{\hat{P}} = \mathbb{E}_{\hat{P}}[\mu(\hat{\hat{P}})] - \mu(\hat{P}) \approx \frac{1}{B_1} \sum_{b=1}^{B_1} \mu(\hat{\hat{P}}^{(b)}) - \mu(\hat{P})$
- Correction: The bias-corrected point estimate is constructed as $2\mu(\hat{P}) - \mathbb{E}_{\hat{P}}[\mu(\hat{\hat{P}})]$ .

This approach extends the classical iterative bootstrap principle to the network setting, where the parameter dimension scales with $n$ . The method is applicable to both global statistics (e.g., total triangle count) and local statistics (e.g., rooted subgraph counts, local clustering coefficients).

Key Contributions and Theoretical Results

1. Characterization of Bootstrap Bias

The authors derive the asymptotic order of the bootstrap bias for subgraph counts under the Chung–Lu model.

For a rooted subgraph count of a graph $R$ with $v$ vertices and $e$ edges, the bias is of order $\Theta(n^{v-2}p^{e-1})$ .
For a global subgraph count, the bias is of order $\Theta(n^{v-1}p^{e-1})$ .
Crucially, the ratio of bias to standard deviation is shown to be non-negligible:
- Global counts: $\Theta(p^{-1/2})$ .
- Rooted counts: $\Theta((np)^{-1/2})$ .
  This confirms that even with consistent parameter estimation, the plug-in estimator $\mu(\hat{P})$ is biased relative to the sampling variability, leading to invalid inference if uncorrected.

2. Bias Reduction via Two-Level Bootstrap

The paper proves that the two-level bootstrap reduces the order of the remaining bias:

For rooted counts, the remaining bias relative to the original bias is $O_P((np)^{-1/2})$ .
For global counts, the reduction is $O_P((np)^{-1})$ .
Consequently, the remaining bias becomes negligible relative to the standard deviation, enabling the construction of valid confidence intervals.

3. Variance Estimation and Confidence Intervals

The authors establish that the second-level bootstrap provides a consistent estimator for the variance of the plug-in estimator $\mu(\hat{P})$ .

Variance Comparison: For many statistics, $\text{Var}_P(\mu(\hat{P})) \ll \text{Var}_P(T(A))$ . This implies that confidence intervals based on the distribution of the plug-in estimator $\mu(\hat{P})$ (which uses the full network structure) are significantly narrower than those based on the raw statistic $T(A)$ alone.
Interval Construction: The paper proposes both normal-approximation intervals and non-normal (empirical bootstrap) intervals, both centered at the bias-corrected estimator.

4. Central Limit Theorem (CLT)

As a by-product, the paper establishes a CLT for subgraph counts under the inhomogeneous Erdős–Rényi model (a generalization of the Chung–Lu model). This result applies to both global and rooted subgraph counts under sparsity conditions that are weaker than those required by existing graphon-based literature.

Empirical Results

Numerical experiments were conducted using:

Synthetic Data: Networks generated from Stochastic Block Models (SBM) and Degree-Corrected SBMs (DCSBM) with varying sparsity levels.
Real Data: Zachary's Karate Club network and the Political Blogs network.

Findings:

Bias Correction: The naive bootstrap intervals (without bias correction) severely under-cover the true parameter, especially in sparse networks. The bias-corrected intervals achieve coverage close to the nominal level (e.g., 95%).
Interval Width: Intervals based on the distribution of $\mu(\hat{P})$ are consistently narrower than those based on $T(A)$ , particularly for local statistics and in sparse regimes.
Estimator Robustness: The bias correction works effectively even when $\hat{P}$ is estimated via SVD or when the model is slightly misspecified (e.g., wrong number of communities), though the DCSBM estimator generally yields better performance than SVD.
Computational Cost: While the two-level bootstrap is computationally intensive ( $O(B_1 B_2 n^2)$ ), it is parallelizable. The authors note that for statistics where the normal approximation holds, the computational cost can be reduced by using the bootstrap only for variance estimation.

Significance and Claims

The paper claims to provide a general remedy for the bootstrap bias problem in network statistics under fixed edge-probability models. Its significance lies in:

Extending Bootstrap Theory: It adapts the iterative bootstrap concept to settings where the number of parameters grows with the sample size, a scenario where standard bootstrap consistency often fails.
Handling Non-Exchangeability: By conditioning on fixed latent positions (or a fixed $P$ ), the method preserves node-specific properties, making it suitable for analyzing local statistics and heterogeneous networks where node exchangeability assumptions are inappropriate.
Practical Inference: The proposed method enables the construction of accurate, narrow confidence intervals for a wide class of network statistics, including those that are not U-statistics, filling a gap left by existing resampling methods that focus primarily on count statistics under graphon models.
Theoretical Foundation: The derivation of the bias order and the proof of the CLT for subgraph counts under inhomogeneous Erdős–Rényi models provide a rigorous theoretical basis for network inference in sparse regimes.

The authors emphasize that while the analysis is conducted under the Chung–Lu model, the bias phenomenon is expected to arise in more complex models (like multi-community DCSBMs), and the two-level bootstrap serves as a robust, simulation-based correction mechanism applicable across these settings.