Aug 2026· Annals of Statistics· 0 citations· 45 references
TL;DR
The joint asymptotic distribution of any finite collection of network moments in random graphs sampled from a graphon, which includes both the nondegenerate case as well as the degenerate case, provides the higher-order fluctuation theory for subgraph counts in the graphon model.
Abstract
Exchangeable random graphs, which include some of the most widely studied network models, have emerged as the mainstay of statistical network analysis in recent years. Graphons, which are the central objects in graph limit theory, provide a natural way to sample exchangeable random graphs. It is well known that network moments (motif/subgraph counts) identify a graphon (up to an isomorphism); hence, understanding the sampling distribution of subgraph counts in random graphs sampled from a graphon is pivotal for nonparametric network inference. Although there are a few results regarding the asymptotic normality of subgraph counts in graphon models, for many commonly appearing graphons this distribution is degenerate. This degeneracy phenomenon was overlooked until very recently and its consequences in network inference have remained unexplored. Toward this, we obtain the following results: We derive the joint asymptotic distribution of any finite collection of network moments in random graphs sampled from a graphon, which includes both the nondegenerate case (where the distribution is Gaussian) as well as the degenerate case (where the distribution has both Gaussian or non-Gaussian components). This provides the higher-order fluctuation theory for subgraph counts in the graphon model. Furthermore, we develop a novel multiplier bootstrap for graphons that consistently approximates the limiting distribution of the network moments (both in the Gaussian and non-Gaussian regimes). Using this and a procedure for testing degeneracy, we construct joint confidence sets for any finite collection of motif densities. This provides a general framework for statistical inference based on network moments in the graphon model. Examples and simulations are provided to validate the general theory. To illustrate the broad scope of our results, we also consider the problem of detecting global structure (i.e., testing whether the graphon is a constant function) based on small subgraphs. We propose a consistent test for this problem, invoking celebrated results on quasirandom graphs, and derive its limiting distribution both under the null and the alternative.
We study dynamic random graphs in which the set of nodes is fixed, but edges evolve over time according to an underlying stochastic mechanism. Using a maximum-entropy approach, we define a probability distribution on graph trajectories that is consistent with observed constraints, capturing the inherent uncertainty in partially observed networks. We introduce a moment-based estimator for the parameters of this distribution and establish its statistical properties, such as consistency and asymptotic normality, with explicit formulas for the covariance structure. Numerical experiments demonstrate the estimator's accuracy and robustness across various dynamic network scenarios. Our framework bridges probabilistic modeling and statistical inference in time-varying networks, providing practical tools for understanding and predicting complex edge dynamics.
Diego Garlaschelli, M. Mandjes, F. Pijpers et al.· 0 citations
Predicting the percolation threshold of highly clustered networks from local statistics remains difficult, because short loops break the independence assumption underlying tree-like message passing. Existing remedies address loopy connectivity either through prescribed local motifs in random-graph ensembles or through a single network's realized topology, leaving an ensemble-level treatment of arbitrary connectivity patterns absent. Here, we develop a loopy message-passing framework for random clustered graph ensembles based on generalized-edge statistics, which characterize overlap patterns among the neighborhoods of different nodes. This yields a progressively refined approximation scheme based on neighborhoods of increasing size around each node. The low-order approximations recover previous equations for random network ensembles, and the new result that yields refined threshold prediction is developed by the second-order approximation. We show that the effectiveness of this framework depends not only on short-cycle density but also on the internal consistency of generalized edges. To diagnose this effectiveness, we introduce the generalized-edge closure coefficient (GECC) to quantify this consistency. Because GECC is computed entirely from local statistics and does not rely on any percolation calculation, it serves as an a priori diagnostic for the reliability of the approximation. Using synthetic and real networks, the threshold is evaluated via the second-order and lower-order approximations. Comparisons with Monte Carlo simulations show that GECC captures key structural features that strongly affect the percolation threshold. These results establish ensemble-based loopy message passing as an efficient route for predicting the percolation threshold in large clustered networks.
Reconstructing an unknown graph from the trajectory of a random walk arises both for spatial correlation networks in astrophysics and for connectivity inference in network science. We present a reconstruction pipeline whose observable is the random-walk co-visitation matrix, whose model is a pairwise edge-weight basis, and whose fitter is a frame-balanced Levenberg-Marquardt (fbLM) scheme with per-node group weights and a self-calibrated edge readout. Unlike the marginal occupation, the co-visitation retains the ordered pair before the row sum is taken, and the pairwise basis can represent structure that an additive node-potential model cannot; neither change suffices alone. We apply the pipeline to an email communication subgraph, to Delaunay and Voronoi networks built from a COSMOS sky catalogue, and to two controlled 12-vertex test graphs, one unicyclic and one a tree, under both analytic-noise and finite-walk regimes. Reconstructions are scored against the ground-truth adjacency, which enters nowhere in the fit, by true/false positives and the Matthews correlation coefficient (MCC). All test-beds are reconstructed with high fidelity at full graph size: on finite-walk data we recover the COSMOS Delaunay and Voronoi graphs at MCC above 0.98 up to their full extent, N=119 and N=223, the whole graph rather than a cut-out of it, and the empirical email-Eu-core graph at N=240 (417 edges). On the full Delaunay graph a graphical-lasso reference returns MCC 0.540 against 0.988 for fbLM. Each reconstructed edge carries a Fisher-propagated uncertainty, and the residual misses are almost entirely confined to edges the walk never traverses. In the finite-walk regime the limiting factor is therefore walk coverage rather than the fit: essentially every edge the walk visits is recovered, so reconstructibility is governed by the sampling of the graph rather than by the estimator.
The principle of maximum entropy provides a fundamental framework for characterizing typical structures of large random networks subject to observable constraints. In their pioneering numerical experiments \cite{radin2014asymptotics}, Radin, Ren, and Sadun conjectured that entropy-maximizing graphons satisfying subgraph density constraints are stochastic block models a conjecture we term the RRS conjecture. While several special cases have been proven for single-relation graphs with specific constraint families, the general problem has remained open, particularly for multi-relational networks. We resolve the RRS conjecture for constrained multi-relational graphons in the non-extremal regime, proving that entropy-maximizing solutions are step functions with finitely many blocks under the condition the subgraph density constraints are analytically independent and for almost all feasible combinations of sufficient statistics. Our proof employs a differential geometric technique to study solutions of constrained optimization problems in function space via functions with a finite parametrization (step functions). The two cornerstones of this work are: the generalization of subgraph density notion to $h$-subgraph density and the proof that manifolds that define the constrained region for the solutions maintain topological stability without developing new connected components under refinement. Together, these enable proving that no new global optima emerge in higher-dimensional spaces.
We consider multipartite random graphs with given degree sequences, within and across different partitions. Under general assumptions, we prove the local limit of this graph is a multi-type branching process, establish that a giant component exists only when the local limit survives, and deduce that the typical distance is of logarithmic order in probability in the supercritical regime. Our analysis removes two major assumptions from Gamarnik and Misra (2015), where the giant component problem for this model was first considered. In particular, we do not assume irreducibility of the local limit, and provide a general framework to extract giant components even when the limiting branching process is reducible, which we hope to be useful in other contexts. We also provide a new simpler survival criterion of multi-type branching processes, which we hope to be useful when direct calculation of the spectral radius of the offspring matrix may prove to be difficult.