Source-linked AI summary
Nonparametric graphon estimation
Patrick J. Wolfe, Sofia C. Olhede
TL;DR
The paper addresses limited large-sample theory and flexible inference tools for networks. It introduces graphon-based nonparametric estimation with profile likelihood, proving consistency and rates across dense and sparse settings. The results cover growing-class stochastic blockmodels under misspecification and connect network inference to approximation theory and graph limits.
Problem
Large-sample properties and theoretically guaranteed inference tools remain limited for network models beyond simple settings.
Method
The paper models networks with graphons and uses blockmodel maximum profile likelihood to estimate graphons across dense and sparse regimes.
Results
The paper establishes graphon-estimation consistency and rates, including dense and sparse growing-class stochastic blockmodels under model misspecification.
Takeaways & Limitations
The results provide a foundational connection between nonparametric network analysis, approximation theory, nonparametric function estimation, and graph limits.
Takeaways & Limitations
The fitted and oracle community assignments need not be unique, both because of label switching and because uniqueness is not guaranteed more generally.
Abstract
from arXiv · showhide
We propose a nonparametric framework for the analysis of networks, based on a natural limit object termed a graphon. We prove consistency of graphon estimation under general conditions, giving rates which include the important practical setting of sparse networks. Our results cover dense and sparse stochastic blockmodels with a growing number of classes, under model misspecification. We use profile likelihood methods, and connect our results to approximation theory, nonparametric function estimation, and the theory of graph limits.
1. Introduction.
The paper develops a nonparametric framework for network analysis because large-sample properties remain poorly understood beyond simple settings. It connects graph-based network models to limiting objects and classical nonparametric theory.
- Network data are increasingly important, but their large-sample properties remain understood only in the simplest settings.
- The framework relates kernel-based random graph models, stochastic blockmodels, and degree-based models within one nonparametric perspective.
- The theory treats limiting network objects analogously to infinite-dimensional functions in classical nonparametric statistics.
- The resulting connections span generalized linear models, contingency tables, nonparametric function approximation, and graph limits.
2. Model elicitation.
The model represents an observed network as Bernoulli edges whose probabilities are generated by a scaled graphon evaluated at latent node positions. This formulation accommodates both dense and sparse networks while treating node ordering as uninformative.
- A network is represented by a symmetric binary adjacency matrix with structural zeros on the diagonal.
- Each edge follows a Bernoulli model, with symmetric entries and no self-edges.
- A graphon is a bounded, measurable, nonnegative symmetric function that maps edge probabilities to an analytic limit object independent of network size.
- The model sets pij = ρn f(ξi, ξj), where latent positions ξi are iid Uniform(0, 1) and ρn controls expected edge probability.
- Because latent positions index nodes and graphon axes can be measure-preservingly rearranged, observed node ordering carries no information.
3. Main result.
The main result establishes consistency and mean-squared-error control for maximum-profile-likelihood graphon estimators under smoothness, sparsity, grouping, and effective-sample-size conditions. The estimator addresses unknown node ordering through permutation and grouping operations.
- Consistency holds for maximum-likelihood graphon estimation when the graphon is Hölder continuous and the sparsity scaling satisfies the theorem’s growth condition.
- The estimator first permutes adjacency-matrix rows and columns, then groups nodes to construct a graphon approximation.
- The error criterion allows measure-preserving rearrangements of graphon axes, matching graph-limit cut-distance invariance.
- The theorem assumes controlled group sizes, a growing number of groups, and sufficiently large minimum and average effective sample sizes.
- The mean-squared error of the blockmodel maximum profile likelihood estimator satisfies the theorem’s stated bound.
4. Nonparametric graphon approximation via blockmodels.
Growing-class stochastic blockmodels provide stepfunction approximations to graphons, motivating regularized blockmodel fitting for nonparametric estimation. Profile likelihood estimates community assignments by fitting block means to observed network data and approximating the underlying edge-probability matrix.
- Stochastic blockmodels: A blockmodel assigns nodes to communities and estimates an interaction rate for every pair of communities.
- Stochastic blockmodels: Community assignments combine community sizes with a node permutation before partitioning the unit interval.
- Graphon approximation: When the number of communities grows, blockmodels become stepfunction approximations of graphons on (0, 1)^2.
- Graphon approximation: Arbitrary graphons are theoretically well approximated by blocks, but regularization is needed when accurate approximations require many communities and degrees of freedom.
- Profile likelihood: For a fixed assignment, likelihood maximization sets each block parameter θab to the observed block average Āab.
- Profile likelihood: Maximum profile likelihood assignment is equivalent to minimizing Bernoulli Kullback–Leibler divergence as a proxy for the best blockmodel approximation of the underlying probabilities.
5. Sparse blockmodel consistency under model misspecification.
Theorem 5.1 establishes vanishing excess risk for profile-likelihood blockmodel fitting under model misspecification, with rates determined by sparsity and community-size growth. The result covers dense, sparse, and ultra-sparse networks, subject primarily to sufficient effective sample sizes for fitted blocks.
- The profile-likelihood assignment achieves risk approaching the best possible blockmodel approximation as n grows large.The method selects admissible community assignments and evaluates fitted blockmodels through likelihood risk relative to the underlying Bernoulli parameters.
- Consistency requires expected and blockwise densities to avoid approaching 0 or 1 too rapidly, while every possible community must grow sufficiently quickly.The assumptions impose lower bounds through sequences for expected density, block density, and minimum community size.
- Theorem 5.1 gives conditions under which excess blockmodel risk converges to zero even when the true generative model is unknown.The result is driven primarily by effective sample sizes of fitted blocks.
- Dense networks: Dense-network rates are at least log(n)/n when k = O(n3/4), but decrease to log n/n2(1−δ) when k grows like n^δ for 3/4 < δ < 1.These rates describe the dense regime under constant lower and average edge-density bounds.
- Sparse networks: Sparse-network rates range from log(n)3/2/n1/2−γ to log n/n2(1−δ−γ), depending on density decay and the growth of k.Here densities decrease like n−2γ, with the rate changing as k grows.
- Ultra-sparse networks: In the ultra-sparse regime, density of order log(n)3+β/n yields rate log(n)−β/2 when k = O(n1/2).This matches the regime studied by Choi, Wolfe and Airoldi (2012).
6. From blockmodels to smooth graphon estimation.
The paper connects stochastic blockmodel estimation to smooth graphon approximation by reordering nodes, partitioning them into blocks, and controlling approximation risk under Hölder smoothness. This yields a route from blockmodel likelihood results to consistent graphon estimation.
- From blockmodels to smooth graphon estimation: Smoothness controls graphon estimation risk by making the block approximation error vanish.The argument assumes a positive, symmetric, bounded graphon that is α-Hölder continuous.
- From blockmodels to smooth graphon estimation: A blockmodel reorders network rows and columns, then averages entries within blocks to form a piecewise-constant graphon approximation.The blocks are defined by intervals induced by the partition H, with local averages determining the approximation values.
- From blockmodels to smooth graphon estimation: Community assignments determine both block sizes and the node permutation used before applying the partition.The assignment can be represented as the composition H−1 ◦Πz.
- From blockmodels to smooth graphon estimation: An oracle permutation orders latent Uniform(0, 1) variables, linking empirical block probabilities to graphon averages.Hölder continuity transfers convergence of the ordered latent sample to convergence of the random block averages.
- From blockmodels to smooth graphon estimation: The oracle likelihood risk is controlled under admissible assignments and model misspecification, enabling estimation of groupings with good risk properties.The admissible class remains valid after composing the partition with permutations, although the optimal ordering is unknown.
7. Rates of convergence.
The convergence analysis separates variability, block-approximation bias, and ordering-related error. The resulting graphon rate reflects graphon smoothness and block size, while the oracle blockmodel risk also depends on sparsity and admissible block sizes.
- Rates of convergence: The graphon convergence rate depends on Hölder regularity through both ordered-sample variance and block-size bias.Variance comes from convergence of the ordered latent sample, while bias depends on h∨/n.
- Rates of convergence: The graphon rate is self-scaling relative to network sparsity because it does not depend on ρn.This contrasts with the blockmodel risk, which depends on sparsity and block-size conditions.
- Rates of convergence: Theorem 5.1 controls excess blockmodel risk under model misspecification, allowing groupings with good risk properties to be estimated despite data variability.Its conditions depend on ρn, h∧, and the average block size h̄.
- Rates of convergence: Theorems 5.1 and 6.1 together establish mean-square graphon consistency at the rates stated in Theorem 3.1.The combined rate includes terms from blockmodel risk, smooth graphon approximation, and discrete-to-continuous conversion.
8. Conclusion.
The paper develops graphons as analytic limit objects for nonparametric network inference and establishes consistency results covering dense and sparse settings. Its results connect network analysis to approximation theory, nonparametric function estimation, and graph limits.
- Conclusion: Graphons provide the natural limiting-object foundation for a nonparametric framework for network inference.The paper emphasizes understanding graphons analytically and characterizing dense and sparse networks through them.
- Conclusion: Consistency of graphon estimation holds under general conditions with rates that include sparse networks.The results also treat dense and sparse stochastic blockmodels with a growing number of classes under model misspecification.
- Conclusion: The framework links network inference to approximation theory, nonparametric function estimation, and graph-limit theory.These connections are presented as foundational for nonparametric statistical network analysis.
A.1. Proof of Theorem 3.1.
The proof expands graphon mean-squared error pointwise, bounds the infimum over measure-preserving bijections using a selected permutation, and substitutes earlier theorem bounds. It relies on boundedness of the graphon to control block averages.
- A.1. Proof of Theorem 3.1: Boundedness of the Hölder-continuous graphon controls expectations and second moments of block averages.The proof invokes Markov’s inequality after bounding these quantities uniformly over admissible partitions and groups.
- A.1. Proof of Theorem 3.1: The squared graphon error is evaluated at a selected measure-preserving bijection to upper-bound the infimum over all such bijections.The selected σ∗ is chosen according to the later oracle-permutation argument.
- A.1. Proof of Theorem 3.1: The proof combines bounds from Lemmas A.2, A.3, and C.9 with Theorems 5.1 and 6.1 to obtain the stated rate.The final substitution applies when the estimator is fitted by maximum profile likelihood.
A.2. Auxiliary lemmas needed for Theorem 3.1.
These auxiliary lemmas establish moment, covariance, approximation, and blockwise likelihood bounds used to prove consistency of smooth graphon estimation.
- The lemmas derive expectations, variances, and covariances for adjacency-related quantities under the graphon model.
- Measure-preserving bijections are restricted to block permutations so the graphon’s Hölder continuity is preserved within domains.
- Blockwise graphon averages are matched to latent positions and compared with fitted block averages through rank-based assignments.
- Taylor expansions and Markov’s inequality control likelihood terms when fitted block probabilities avoid 0 and 1.
- The denominator and remaining diagonal terms are bounded separately, after which their ratio yields the desired auxiliary result.
B.1. Proof of Theorem 5.1.
The proof of Theorem 5.1 controls fitted-block likelihood terms uniformly over admissible assignments, then transfers the result to the maximum profile likelihood estimator.
- The proof is divided into four technical steps, each handled by a lemma controlling a component of the likelihood comparison.
- The proof requires fitted block probabilities to stay away from 0 and 1 and minimum effective block sizes to grow.
- Uniform control over all assignments allows the bounds to apply to the maximum profile likelihood estimator and its oracle counterpart.
- The empirical assignment serves as a proxy for the oracle assignment because their normalized likelihood difference converges to zero.
- The resulting convergence rate is governed by the dominant rate term, with a sufficient condition involving ¯h^2¯ρ = ω(·).
B.2. Proofs and auxiliary lemmas needed for Theorem 5.1.
This section proves the concentration and approximation results needed for Theorem 5.1, including control of degenerate blocks, likelihood divergences, and Poisson–Binomial moments.
- Likelihood discrepancies are expressed through sums of nonnegative Kullback–Leibler divergences and shown to converge after suitable normalization.
- Sufficient effective block size and probability-separation conditions control the probability of degenerate fitted blocks.
- Uniform concentration over all admissible assignments follows from moment bounds, Bernstein concentration, and a union bound.
- Poisson–Binomial moment bounds are obtained by splitting central and tail contributions and comparing even central moments with a matched-mean binomial variable.
C.2. Auxiliary lemmas needed for Theorem 6.1.
These lemmas control the approximation error between a Hölder graphon and its blockwise step-function approximation, including sampled-order and likelihood-divergence terms.
- Under rn → 0, the principal approximation term is OP(rn), while boundedness and concentration inequalities control the remaining terms.
- The analysis assumes a symmetric Hölder function and a step-function approximation defined on the block partition.
- Hölder continuity bounds the approximation error within each block and supports uniform norm control.
- Ordered uniform samples are aligned with blocks through rank-based assignments, allowing latent positions to be compared with deterministic block locations.
- The likelihood comparison is decomposed using Taylor expansions of Bernoulli Kullback–Leibler divergences and controlled through blockwise error ratios.