In classical statistics, the power of an inference comes from the number of independent samples ($n$). To understand a population, we look at many individuals; to understand a process, we observe many trials. However, in fields like sociology, genomics, and physics, we often encounter the "$n=1$ problem." We have only one Internet, one human connectome, or one specific social network.
Traditional frequentist methods break down here because there are no replicates to provide a measure of variance or a null distribution. Yet, a growing body of research demonstrates that we can recover global parameters, test hypotheses, and even perform cross-validation using only a single interconnected snapshot.
Concentration of Measure as a Proxy for Replicates
The fundamental reason we can learn from a single graph is that a large network is not actually a single data point—it is a massive collection of local interactions governed by a shared set of rules. As the number of nodes ($N$) grows, the global properties of the network (like triangle counts or eigenvalues) tend to "concentrate" around their expected values.
Debarghya Ghoshdastidar, Alexandra Carpentier, and Ulrike von Luxburg show in Two-Sample Tests for Large Random Graphs Using Network Statistics that this internal concentration allows for consistent hypothesis testing. If you have two large graphs and want to know if they were generated by the same underlying distribution, you don't need a population of graphs. The sheer size of a single graph provides enough "internal replicates" of its structural motifs to distinguish signal from noise. They demonstrate that while simple node-by-node comparisons fail, structural statistics like the operator norm remain robust even in this data-starved regime.
Ergodicity and the Law of Large Numbers on Graphs
In time-series analysis, ergodicity allows us to estimate the properties of a process by looking at one long realization instead of many short ones. A similar principle applies to graphs. Fernando Gama explores this in Ergodicity in Stationary Graph Processes, proving a Weak Law of Large Numbers for signals on irregular graphs.
The intuition is that if a signal is "stationary" across the graph, local averages computed via diffusion (spreading information to neighbors) will converge to the true ensemble mean as the network grows. This means that the spatial variation within a single snapshot of a network—such as disease rates across counties—can substitute for the temporal variation researchers usually rely on to identify node-to-node influence.
Dependencies as Information, Not Noise
In standard statistics, dependencies between data points are often treated as a nuisance that violates i.i.d. assumptions. However, in single-sample inference, these dependencies are the primary source of information.
Yuval Dagan argues in Statistical Estimation from Dependent Data that the internal structure of dependencies in a Markov Random Field provides the necessary signal for parameter learning. As the network size increases, the collective information from these local dependencies provides sufficient signal for the Maximum Pseudo-Likelihood Estimator (MPLE) to converge. Essentially, the way one node affects its neighbor reveals the global "physics" of the system, allowing researchers to recover the rules of the game from a single finished board.
Breaking the Single Sample: Graph Fission
Perhaps the most counterintuitive advancement in this area is the ability to perform "sample splitting" on a single graph. Traditionally, you cannot use the same data to both select a model and test it without introducing massive bias.
The Graph fission and cross-validation framework solves this by "fissioning" a single graph into multiple synthetic copies that are statistically independent. This allows for post-selection inference and valid confidence intervals on a single network, effectively turning an $n=1$ problem into a multi-sample problem through clever probabilistic decomposition.
Limits and Phase Transitions
While learning from one sample is often possible, it is not always easy. Guy Bresler and Dheeraj Nagaraj identified a sharp phase transition in Optimal Single Sample Tests for Structured versus Unstructured Network Data. They found that above a certain "temperature" or noise threshold, near-optimal testing is possible; below it, the distributions become so entangled that they are mathematically indistinguishable from a single observation.
Similarly, Andreas Galanis shows that for "hard-constrained" models (where certain states are strictly forbidden), the task can shift from being solvable in linear time to being computationally impossible. These boundaries define the frontier of the field: determining exactly when the internal complexity of a single system is rich enough to reveal its own secrets.