Source-linked AI summary
The method of moments and degree distributions for network models
Peter J. Bickel, Aiyou Chen, Elizaveta Levina
TL;DR
Statistical tools for fitting network probability models are limited, especially when simple models cannot capture complex network structure. The paper develops a general method of moments based on empirical graph-pattern counts and establishes asymptotic results across average-degree regimes. It also applies the approach to block and nonparametric models and studies degree distributions.
Problem
Statistical inference for networks has limited development because analytically tractable models often fail to reproduce complex features of real networks.
Method
The paper fits broad network models using empirical frequencies of graph patterns such as triangles and stars as moments.
Results
The paper proves consistency and asymptotic normality for acyclic graph-moment estimates across the giant-component phase transition and shows that wheel moments determine the kernel operator T.
Takeaways & Limitations
Method-of-moments fitting applies beyond specific parametric models and supports estimation of block and nonparametric network structures from graph patterns.
Takeaways & Limitations
Recovering the nonparametric kernel from moments is theoretically and practically difficult because the inversion and subsequent eigenvector and eigenvalue estimation are ill-conditioned.
Abstract
from arXiv · showhide
Probability models on graphs are becoming increasingly important in many applications, but statistical tools for fitting such models are not yet well developed. Here we propose a general method of moments approach that can be used to fit a large class of probability models through empirical counts of certain patterns in a graph. We establish some general asymptotic properties of empirical graph moments and prove consistency of the estimates as the graph size grows for all ranges of the average degree including $Ω(1)$. Additional results are obtained for the important special case of degree distributions.
1. Introduction.
Network models are important across many fields, but statistical inference remains limited because analytically tractable models often fail to reproduce complex network features. The paper develops a general method-of-moments approach based on empirical pattern frequencies and applies it to broad model classes including block models.
- Statistical inference for networks remains limited despite extensive applications, partly because simple tractable models do not reproduce complex real-network features.
- The block model is specified by block proportions π and a symmetric matrix F of conditional edge probabilities, but it cannot represent nonuniform within-block connectivity such as hubs.
- The paper uses empirical or theoretical frequencies of graph patterns, including triangles and stars, as moments for fitting probability models.The approach is intended for general patterns rather than only a particular parametric model.
- The method of moments applies more generally than model-specific fitting procedures such as Bayesian sampling or profile likelihood for block models.
- ERGMs use network moments as sufficient statistics, but fitting them is difficult and many become asymptotically simplistic or nearly degenerate.
- The paper studies empirical graph moments, fits block and nonparametric models, analyzes degree distributions, and examines normalized degrees.
2. The asymptotic distribution of moments.
The paper defines graph-pattern quantities and their empirical estimates under a sparse random-graph parametrization, then derives asymptotic distributional results. These results extend across finite average-degree regimes and include consistency across the giant-component phase transition.
- Notation and parametrization: The model uses edge scale ρn with expected degree λn = (n − 1)ρn, while the graph kernel w is held independent of n.
- Graph moments: Graph moments are formed from counts of subgraphs and related population quantities P(R) and Q(R), which are estimated from the observed graph.
- Scaling: The sparse scaling ρn → 0 requires rescaling fixed-pattern probabilities because P(R) tends to zero for fixed patterns.
- Asymptotic results: When λn → λ < ∞, the asymptotic conclusions continue to hold, with variance quantities depending on λ as well as the pattern R.
- Asymptotic results: The same conclusions extend to non-acyclic patterns under a sufficiently large average-degree condition, specifically λn of order n^(1−2/p) or higher.
- Phase transition: Acyclic graph-moment estimates are consistent and asymptotically normal on both sides of the giant-component phase transition, for λ < 1 and λ ≥ 1.
Remarks.
The remarks clarify when different empirical moment estimators are consistent and root-n consistent, and show how wheel patterns connect moments to the kernel operator. They also identify computational and statistical limitations in intermediate sparsity regimes.
- Estimator interpretation: Unnormalized P and Q are zero unless λn is of order n, so the paper estimates features of the canonical kernel w using rescaled quantities.
- Estimator choices: For acyclic R with λn = o(n^1/2), ˇP(R) estimates ˜Q(R) with bias o(n^−1/2), whereas direct use of ˇQ requires stronger conditions.
- Estimator choices: For λn = Ω(n), ˇQ provides root-n-consistent estimates for any pattern, while ˇP is inconsistent unless the patterns are acyclic.
- Pattern-specific behavior: For triangles, ˇP and ˇQ coincide; ˇP is root-n consistent when λn ≥ εn^1/3 and otherwise is only consistent when λn → ∞.
- Wheel patterns: A (k,l)-wheel has one hub and l spokes, each a chain of k edges, and wheel moments have simple operator-based formulas.
- Computational limitations: For wheel estimates, the easily computed ˇP is preferred when λn = o(n^1/2), while no root-n-consistent estimate is exhibited in an intermediate average-degree range.
- Wheel patterns: All (k,l)-wheels are acyclic and provide all cross moments of T^m(ξ), making them potentially sufficient to determine the canonical kernel.
3. Moments and model identifiability.
The paper uses moments of graph patterns, especially wheels, to identify block-model parameters and more general latent graph-generating functions under stated regularity conditions. It also establishes consistency results and highlights assumptions that exclude some important cases.
- The block model: The block-model identifiability theorem requires linear independence of π,Fπ,...,F^(K−1)π and assumes ε ≤ λn = o(n^1/2).The linear-independence condition rules out matrices F having 1 as an eigenvector.
- The block model: Wheel moments identify the parameters of a known-K block model other than the sparsity scale ρ.The specified wheels use 1 ≤ l ≤ 2K − 1 and 2 ≤ k ≤ K.
- The block model: Under a full-rank gradient condition, projecting empirical wheel moments onto the model range yields a √n-consistent estimate of (π,S).The estimator is f^-1(P(ˇτ)), where P(ˇτ) is the closest point in the range of f to the empirical moment vector.
- Inference and limitations: Variance estimation for wheel moments becomes more difficult as pattern size grows, and the paper suggests but does not develop a bootstrap-based solution.The variance is expected to increase exponentially in p = kl + 1, while weighted nonlinear least squares would require these variances.
- The nonparametric model: Under additional spectral conditions, the joint distribution of iterated operator applications determines, and is determined by, the graph-generating function w.These conditions include simple eigenvalues and eigenfunctions that are not orthogonal to the constant function 1.
- The nonparametric model: For the general model, all wheel moments determine the operator-induced distributional object T, and under condition (A), empirical wheel moments are √n-consistent.The argument uses convergence of moment-generating functions so moments, including cross moments, determine the relevant vector distribution.
4. Degree distributions.
The paper uses normalized degrees and generalized m-degrees to estimate latent graph structure and block-model parameters, with consistency under increasing average degree.
- Degree distributions: The joint empirical distribution of degrees and m-degrees can estimate asymptotic approximations to w and potentially simplify wheel-moment computation.This approach also eliminates the need to know ρ_n.
- Degree distributions: The m-degree counts loopless paths of length m from a vertex and represents the volume of its radius-m geodesic sphere.Generalized degrees are computed as row sums after removing terms with repeated indices.
- Degree distributions: For λ_n = O(1) and m = 1, the limiting degree distribution is a mixture of Poisson distributions with means τ_w(ξ).The stated limit conditions use ξ uniformly distributed on (0,1).
- Degree distributions: ˆT_m(t) converges to T^(m−1)(τ)(τ^−1(t)), uniformly on compacts when the target functions are smooth.The fitted functions support consistent estimation of block-model parameters of any order.
5. Computation of moment estimates and estimation of their variances.
The paper addresses computational and variance-estimation challenges for wheel-based graph moments using approximations for sparse graphs and a vertex-resampling bootstrap.
- Computation: General acyclic graph moment estimates, including (k,l)-wheels, are computationally difficult.Even wheel-moment computation can have complexity of order O(n^λk).
- Computation: For very sparse graphs, intersecting paths can be ignored up to a certain order, allowing wheel counts to be approximated using normalized m-degrees.The approximation is tied to the conditions of Theorem 5.
- Variance estimation: The proposed bootstrap repeatedly samples vertices without replacement and estimates variance from the resulting moment estimates.The procedure associates each vertex with wheel counts, resamples m vertices, and repeats B times.
- Variance estimation: ˆσ² estimates the variance of the moment estimator when m/n →0 and m →∞.The bootstrap is stated to work when λ_n →∞, while its validity for λ_n = O(1) is conjectured.
6. Discussion.
The discussion outlines unresolved difficulties in nonparametric estimation, the relevance of increasing-degree asymptotics, and possible extensions to covariates and dynamic networks.
- 6. Discussion: Nonparametric estimation of w_CAN may be consistent in principle, but recovering w is ill-conditioned because it involves moment inversion and eigenfunction estimation.The authors identify both theoretical and practical difficulties in estimating the full function.
- 6. Discussion: The condition λ_n →∞ is relevant to networks with high average degree and can serve as an asymptotic regime for understanding graph patterns.The paper notes university Facebook networks with average degree λ of 15 or more and n in the low thousands.
- 6. Discussion: Adding vertex or edge covariates converts the latent-variable model into a mixed model, potentially a logistic mixed model, but the paper does not pursue this extension.Directed-graph extension is described as straightforward.
- 6. Discussion: Preferential-attachment models can yield limiting models of the considered type, with w based on an integral equation for τ(ξ).The authors defer this line of work to future research.
APPENDIX: ADDITIONAL LEMMAS AND PROOFS
The appendix supplies proofs for asymptotic normality and consistency results using conditional limit theorems, U-statistics, and the delta method. It also establishes identification of model quantities from moments and convergence of estimated degree-distribution functionals.
- Asymptotic limits: When λn = O(1), conditional sums and dependent-variable limit arguments establish the relevant Gaussian limits; when λn →∞, higher-order terms determine them.The proofs distinguish sparse and diverging-average-degree regimes, with some first-order terms becoming negligible as λn grows.
- Proof mechanisms: The proofs use U-statistic variance bounds and overlap-graph structure to establish convergence rates for empirical graph-pattern quantities.Acyclic intersections constrain covariance contributions, while a second-order U-statistic term is O(n−1).
- Asymptotic limits: The appendix derives asymptotic Gaussian behavior for key statistic pairs, with joint convergence used to obtain the stated limiting results.The arguments invoke U-statistic limit theory and asymptotic independence of component terms.
- Moment identification: The model proportions π1,...,πK are uniquely determined by the first 2K −1 moments of a variable taking K values vj with probabilities πj.This identification uses a Hausdorff–Hamburger moment theorem and the representation v(j) = Fπ.
- Moment identification: Under linear independence of π and the ordered values v(1),...,v(K), the matrix F is computable, and consistency follows from Theorem 1 and the delta method.The appendix connects identification conditions to the resulting n-consistency claim.
- Distributional consistency: The estimated distribution of θm(ξi) approaches its empirical counterpart in M2 distance, after which Glivenko–Cantelli and the Law of Large Numbers yield the theorem’s first conclusion.The proof also permits replacing the average degree by λn when λn is bounded away from zero.