Statistical Inference from a Single Network Realization

47 concepts33 papers1 proposal

Standard frequentist statistics relies on a simple recipe: collect $N$ independent and identically distributed (i.i.d.) samples, average them, and let the Law of Large Numbers guarantee convergence to the truth. But what happens when your data is a single, massive social network, a brain connectome, or a global financial market?

In these domains, $N=1$. You cannot observe a thousand independent copies of the internet to infer its underlying physics. This constraint creates a fundamental challenge for traditional statistical tools, which struggle to provide valid confidence intervals, p-values, or consistent parameter estimates when the sample size is effectively one.

The core insight of single-sample network inference is that large-scale interconnected systems exhibit internal concentration of measure. Instead of collecting independent samples across multiple parallel universes, we can exploit the weak dependencies within a single, growing universe. If a network is large enough (the number of nodes $n \to \infty$) and its internal dependencies decay fast enough, the single network snapshot contains enough internal variation to act as its own statistical ensemble.

Ergodicity and Internal Concentration

How can a single observation substitute for an entire ensemble of data? The answer lies in extending the classical time-series concept of ergodicity to graph structures.

As Fernando Gama demonstrates in Ergodicity in Stationary Graph Processes: A Weak Law of Large Numbers, for stationary graph signals, local spatial averages computed via network diffusion converge to the true global ensemble mean as the network grows. This means that observing different neighborhoods of a single large graph provides a mathematically equivalent signal to observing multiple independent realizations of smaller graphs.

Traditional Statistics (N → ∞):
[Sample 1]  [Sample 2]  [Sample 3]  ...  [Sample N]  --> Average over Universes

Single-Sample Inference (n → ∞ nodes):
[ Subgraph A <---> Subgraph B <---> Subgraph C ]     --> Average over Space

This internal variation allows for rigorous hypothesis testing on a single graph. Debarghya Ghoshdastidar et al. show in Two-Sample Tests for Large Random Graphs Using Network Statistics that global network statistics—such as triangle counts or eigenvalues—concentrate tightly around their expected values as the graph size increases. Because of this concentration, a researcher can confidently execute a two-sample hypothesis test (e.g., determining if two large graphs originate from the same underlying distribution) even when they only possess a single observation of each network.

Turning Dependencies into Signals

In classical regression, dependencies between data points are treated as a nuisance or a violation of i.i.d. assumptions. In single-sample network inference, however, these dependencies are precisely the source of information.

In Regression from Dependent Observations, Constantinos Daskalakis et al. prove that data generated within a weak dependency regime contains enough internal variation to achieve consistent parameter estimation from a single snapshot. Rather than needing longitudinal or temporal snapshots to see how a system evolves, the spatial correlations present in a single slice of time reveal the rules of interaction.

For example, consider trying to estimate "peer effects"—how much individuals in a social network influence one another's behavior. Constantinos Daskalakis et al. demonstrate in Logistic regression with peer-group effects via inference in higher-order Ising models that both individual attributes and collective social influence parameters can be accurately recovered from a single observation of a large network. As the network size increases, the spatial correlations between interconnected nodes compensate for the lack of multiple independent samples.

ANTHIMOS VARDIS KANDIROS et al. formalize this principle in Statistical Estimation from Dependent Data. By modeling dependencies using Markov Random Fields and employing a Maximum Pseudo-Likelihood Estimator (MPLE), the authors show that dependencies are not noise; they provide structural information. The collective information from local dependencies provides a sufficient signal for convergence, allowing global parameters to be learned from a single, highly interconnected sample.

Goodness-of-Fit Testing with a Sample Size of One

If we only have one network realization, how do we evaluate whether a generative model accurately captures its structure? Standard goodness-of-fit tests require a large set of reference samples to compare against a model's output, which is impossible when evaluating unique biological or sociological networks.

To solve this, researchers look for sharp phase transitions where structured models diverge from random noise. Guy Bresler et al. show in Optimal Single Sample Tests for Structured versus Unstructured Network Data that it is possible to distinguish between structured network data (like an Ising model on a sparse graph) and unstructured data using only a single sample, identifying a sharp mathematical threshold above which near-optimal testing is guaranteed.

Furthermore, network models often suffer from "intractable normalization constants," making traditional likelihood-based testing computationally impossible. Wenkai Xu et al. bypass this in A Stein Goodness-of-test for Exponential Random Graph Models by combining Stein's method with kernel-based discrepancies. Their framework treats the individual components of a single observed network realization as a rich source of internal dependencies, allowing for rigorous hypothesis testing and valid p-value generation without requiring multiple independent samples of the entire system.

Simulating Multiple Samples via Graph Fission

Perhaps the most direct confrontation with the $N=1$ problem is to mathematically break the single sample into pieces. In traditional machine learning, we split data into training and validation sets. In graph data, this is notoriously difficult because cutting edges or separating nodes disrupts the very dependencies we want to study.

In Graph fission and cross-validation, Aaditya Ramdas et al. introduce a technique called graph fission, which allows a researcher to split a single, interconnected graph dataset into multiple independent "synthetic" copies. By carefully decomposing the graph's adjacency matrix, graph fission creates independent channels of information. This breakthrough allows powerful statistical tools like cross-validation and post-selection inference to be applied directly to a single observed network, effectively turning an $N=1$ problem into an $N>1$ workflow.

Key Foundational Work

Graph model selection using maximum likelihood (2006) — contributed 1 concept elements to this direction.
Estimating the Average of a Lipschitz-Continuous Function from One Sample (2011) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_single_sample_network_inference_b6ee67e3,
  title = {single-sample network inference},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/single-sample-network-inference/rdr_b6ee67e362fd4e95ae358824756058ed},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_single_sample_network_inference_b6ee67e3_v1,
  title = {single-sample network inference},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/single-sample-network-inference/rdr_b6ee67e362fd4e95ae358824756058ed/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake