Source-linked AI summary
Consistency under sampling of exponential random graph models
Cosma Rohilla Shalizi, Alessandro Rinaldo
TL;DR
The paper asks whether models fitted to sampled sub-networks can validly describe whole networks. It develops general projectibility results for exponential families and applies them to ERGMs, finding that many appealing models fail consistency while projectibility sharply restricts model structure.
Problem
Inference from sampled sub-networks assumes that the same ERGM and parameters describe both sub-networks and whole networks, but this probabilistic consistency has often gone unexamined.
Method
The paper proves general projectibility and maximum-likelihood consistency results for exponential families of dependent variables, then applies them to ERGMs.
Results
Projectibility requires additive sufficient-statistic structure with strong independence implications, and many popular ERGM specifications involving network dependence are nonprojective.
Takeaways & Limitations
Projective ERGMs are limited in expressive power, with dyadic-independence models remaining projective but sociologically implausible and poor at reproducing observed data.
Takeaways & Limitations
The paper concludes that resolving ERGM nonprojectibility may require different model families and additional data, such as models of network evolution over time.
Abstract
from arXiv · showhide
The growing availability of network data and of scientific interest in distributed systems has led to the rapid development of statistical models of network structure. Typically, however, these are models for the entire network, while the data consists only of a sampled sub-network. Parameters for the whole network, which is what is of interest, are estimated by applying the model to the sub-network. This assumes that the model is consistent under sampling, or, in terms of the theory of stochastic processes, that it defines a projective family. Focusing on the popular class of exponential random graph models (ERGMs), we show that this apparently trivial condition is in fact violated by many popular and scientifically appealing models, and that satisfying it drastically limits ERGM's expressive power. These results are actually special cases of more general results about exponential families of dependent random variables, which we also prove. Using such results, we offer easily checked conditions for the consistency of maximum likelihood estimation in ERGMs, and discuss some possible constructive responses.
1. Introduction.
The paper examines whether fitting ERGMs to sampled sub-networks can support inference about whole networks. It argues that projective consistency is a prior requirement and that many appealing ERGM specifications fail it.
- Network analysts commonly fit a model to an observed sub-network and extrapolate the same parameters to the larger network.
- The paper separates probabilistic consistency under sampling from the later question of maximum likelihood estimation consistency.
- The results extend beyond networks to exponential families of dependent stochastic processes.
- The paper shows that projectibility requires additive structure in sufficient statistics and implies strong independence properties.
- Many popular social-network and stochastic-graph specifications cannot satisfy projectibility, despite the importance and appeal of ERGMs.
- Earlier sampling research documented distorted sub-network properties, but the authors identify consistency under projection as an unaddressed issue.
2. Projective statistical models and exponential families.
The paper formalizes projective statistical models as families whose smaller-sample distributions arise by projecting larger observations. It then develops exponential-family notation centered on sufficient statistics, increments, and volume factors.
- A projective family assigns distributions across nested observation sets so that the smaller model is recovered by marginalizing the larger one for every parameter.
- The framework applies to increasingly large samples, time series, spatial regions, grids, and sub-graphs from a single network.
- For networks, nested observation sets correspond to induced sub-graphs, and projection removes the additional nodes and associated data.
- Projectibility is automatic for IID models and generally straightforward for models specified through conditional distributions, but joint-distribution models may fail it.
- Each model uses a sufficient-statistics function and a partition function, while the sufficient statistic itself has an exponential-family distribution.
- Completely additive sufficient statistics describe independent, though not necessarily identically distributed, observations; other statistics can encode dependence.
- For nested sets, the sufficient-statistic increment is t_B\A(x,y) = t_B(x,y) − t_A(x), and joint and conditional volume factors support the projectibility analysis.
3. Projective structure in exponential families.
The paper characterizes projectibility in exponential families through separable increments of sufficient statistics, which impose independence consequences and provide tests for failure. It also connects these structural results to predictive sufficiency, counterexamples, parameter transformations, and entropy additivity.
- 3. Projective structure in exponential families.: Separable increments are intrinsic to the sufficient-statistic forms and do not depend on the model parameters.Because distributions share the same support, the property holds for every parameter value or none.
- 3. Projective structure in exponential families.: Projectibility is equivalent to separable increments of the sufficient statistics.The condition requires increment ranges to be independent of prior observations and conditional volume factors to be constant in the prior data.
- 3.1. Independence properties.: Projectibility implies independent increments, but independent increments alone are insufficient for projectibility.A counterexample has independent statistic increments while its conditional volume factors vary with the observed configuration, violating separability.
- 3.1. Independence properties.: Independent increments of sufficient statistics do not imply independence of the underlying observations.In the one-dimensional Ising model, statistic increments are independent even though the variables remain dependent on one another.
- 3.2. Remarks, applications and extensions.: Projectibility can be checked by testing whether sufficient-statistic increments are independent, while predictive distributions depend on new-data increments in projective families.The paper also identifies separated volume factors with additive Boltzmann entropy across system parts.
- 3.2. Remarks, applications and extensions.: The framework has scope boundaries involving nonuniform base measures, transformations of parameters, and extensions beyond exponential families.The paper notes that nonuniform measures may destroy separable increments and leaves the necessity of the exponential form as an open question.
4. Consistency of maximum likelihood estimators.
The section derives strong consistency of maximum likelihood estimators from projectivity, independent increments, and exact scaling, then gives weaker conditions for consistency in probability.
- MLE formulation: The MLE is obtained by matching the expected sufficient statistic to its observed value.This follows from the exponential-family likelihood equations and identifies the parameter estimate through the sufficient statistic.
- Strong consistency: Projectivity and independent increments allow the sufficient-statistic process to be represented as a time-transformed Lévy process.The transformation uses the proportional cumulant-generating functions across growing sets.
- Strong consistency: Strong consistency follows because T_A/r_|A| converges almost surely to ∇a(θ), forcing the MLE to converge almost surely to θ.The strong law of large numbers is applied to the IID increments of the Lévy process.
- Strong consistency: Under exact scaling of the log partition function, the MLE exists and is strongly consistent.The theorem assumes projectivity and the scaling relation for every set A.
- Conditions and scope: Exact scaling requires all components of a multidimensional sufficient statistic to use the same size factor; differing orders such as |A| and |A|^3 violate the condition.Strong consistency may therefore hold only for parameter regions where the scaling relation applies.
- Consistency in probability: Approximate scaling of the log partition function yields consistency in probability, even when exact scaling fails.The argument replaces the dependent heterogeneous variables with homogenized IID effective variables up to o_P(r_|A|), reducing almost-sure convergence to stochastic convergence.
5. Application: Nonprojectibility of exponential random graph models.
ERGMs are applied to sampled sub-networks but often fail to define projective families, preventing parameters from generalizing across network sizes. The application establishes a near-dichotomy: dyadic-independence models are projective, whereas models counting larger motifs are not.
- ERGMs and projectibility: ERGMs model graphs using sufficient statistics that count edges, triangles, cliques, k-stars, and other motifs, potentially normalized or combined with nodal covariates.The graph or adjacency matrix is treated as an exponential-family stochastic process conditional on fixed covariates.
- Projective ERGMs: Dyadic-independence models are projective because their statistics add separate contributions from independent dyads as nodes are added.Adding a node contributes terms unconstrained by the configuration among existing nodes, yielding separable increments.
- Nonprojective motif models: Triangle counts cannot have separable increments, because new-node ties can complete triangles involving existing edges and alter the possible increment range.Therefore ERGMs using triangle statistics cannot be projective.
- Nonprojective motif models: Counts of any k-node motif with k > 2 similarly depend on edges involving future nodes, producing nonseparable increments and nonprojective families.The same reasoning applies to larger motifs, not only triangles.
- Inference consequences: Some nonprojective ERGMs can still yield exponentially concentrating maximum-likelihood estimates, but their parameters cannot be extrapolated between smaller and larger graphs.More observations from subgraphs therefore cannot improve parameter estimates for the whole graph through direct extrapolation.
- Projective ERGMs: Degree-corrected block models satisfy the projectibility conditions because the configurations producing each degree have ranges independent of smaller subgraphs.These models provide an example of a projective ERGM specification.
- Inference consequences: For a nonprojective ERGM postulated for the whole network, inference must treat unobserved network portions as missing data rather than extrapolate parameters from a sub-network.The paper mentions expectation-maximization as one possible approach, with potentially substantial uncertainty about the missing portion.
6. Conclusion.
The paper places ERGM nonprojectibility within a broader problem for exponential families of dependent variables: projectibility requires carefully structured, separable interactions. It concludes that richer network dependence conflicts with this requirement, motivating alternative specifications and further algebraic work.
- General conclusion: Exponential families of dependent variables require statistics chosen carefully to achieve separable increments, unlike IID exponential-family models, which are always projective.The difficulty arises in joint distributions; conditional specifications do not have the same problem.
- Implications for network models: Dyadic independence is projective but sociologically implausible, while clustering specifications are more interesting yet never have separable increments.The paper describes this as an impasse within the usual ERGM framework.
- Implications for network models: Temporal conditional exponential-family models are presented as one possible alternative because triangle changes in conditional specifications do not trigger the same projectibility issue.This alternative requires more and different data.
- General conclusion: Nonprojective dependencies permit interactions among arbitrary collections of variables, preventing one part of the system from being screened off by conditioning.This explains why the relevant sufficient statistics fail to support projective structure.
- General conclusion: A compatible sufficient statistic must partition into marginal contributions from disjoint subassemblies plus interactions strictly between them.The paper expresses this through an additive decomposition of the statistic for the larger information set.
- Open directions: Abandoning the exponential-family form while retaining finite-dimensional sufficient statistics may not resolve the issue, and a purely algebraic characterization is left for future work.The paper bases this concern on results about semigroup-structured sufficient statistics.
- Open directions: Every infinite exchangeable graph distribution is a mixture over projective dyadic-independence distributions, suggesting a possible route for understanding the observed conflict.Along subgraph sequences, motif densities approach limits identifying a projective dyadic-independence distribution.
APPENDIX: PROOFS
The appendix notation fixes nested information sets and expresses a larger observation as an existing subset together with its complement.
- Appendix notation: For nested sets A ⊂ B, a point in the larger space is written x_B = (x,y), with x in X_A and y in X_{B\A}.The increment statistic t_{B\A}(x,y) abbreviates t_B(x,y) − t_A(x).
A.1. Proof of Theorem 1.
The proof establishes that projectibility and separable increments are equivalent for the sufficient statistics, with factorization of volume factors and independence providing the bridge.
- Proof structure: The reverse implication proceeds through preliminary lemmas linking separable increments, volume-factor factorization, independent increments, and projective distributions.The argument separates the two directions and uses total probability to connect the factorized quantities.
- Projectibility implies separable increments: Projectibility implies separable increments: vB\A|A(δ,x) is independent of x whenever A ⊂B.The proof identifies this conditional-volume invariance by comparing Laplace transforms over an open parameter set.
- Projectibility implies separable increments: Equality of Laplace transforms on an open parameter set forces identical increment measures, supports, and densities for every x.The common normalizing factor then yields vB\A|A(δ,x)=vB\A(δ).
- Separable increments imply projectibility: Separable increments imply that the joint volume factor factorizes as vA,B\A(t,δ)=vA(t)vB\A(δ).This factorization is the first lemma used in the reverse implication.
- Separable increments imply projectibility: Factorized volume factors make the sufficient-statistic increments independent and establish projectibility of their distribution.The proof derives independence by factorizing the joint probability, then obtains projectibility through normalization constants.
- Caveat: Joint volume-factor separation alone is insufficient; the conditional volume factor must also remain constant in x.This condition distinguishes separable increments from ordinary factorization of the joint volume factor.
A.2. Other proofs.
The additional proofs derive consequences of projective exponential families, including independent increments, conditional exponential-family structure, and large-deviation behavior.
- Projectivity and increments: Projective exponential families have separable and independent sufficient-statistic increments, and independent increments conversely imply projective statistic distributions and separated volume factors.These implications are established through Propositions 1–3 and the Neyman factorization theorem.
- Volume-factor factorization: Volume-factor separation follows by combining independent increments with sufficient-statistic factorization and normalization.The proof introduces functions gB\A, kA, and kB\A to express the resulting factorization.
- Conditional distributions: The conditional distribution of XB\A given XA is an exponential family with parameter θ, sufficient statistic TB\A, and partition function zB\A|A(θ)=zB(θ)/zA(θ).This follows by taking the ratio of projective joint and marginal densities.
- Moment generating functions: The moment generating function of TB\A can be computed conditionally and used unconditionally because TB\A is independent of XA.The proof combines the conditional exponential-family form with Proposition 2.
Non-uniform base measures and conditional projectibility
The supplementary material extends the analysis to nonuniform base measures and a broader form of conditional projectibility.
- Extensions: The supplementary material treats nonuniform base measures and studies conditional projectibility, which implies that stochastic block models are projective.These extensions broaden the projectivity results beyond the main setting.