Source-linked AI summary
Network histograms and universality of blockmodel approximation
Sofia C. Olhede, Patrick J. Wolfe
TL;DR
The paper addresses how to represent unlabeled network interactions when stochastic blockmodels need not be correctly specified as the data-generating mechanism. It defines network histograms through blockmodel approximations and shows how bandwidth and complexity choices support flexible representations while allowing multiple community assignments and interpretations.
Problem
Comparing network-generating mechanisms requires representations invariant to symmetric rearrangements, while stochastic blockmodels are traditionally analyzed as correctly specified generative models.
Method
The paper constructs network histograms by grouping nodes into communities, comparing graphons under measure-preserving rearrangements, and developing an automatic bandwidth-selection procedure.
Results
The blockmodel provides a universal representation for interactions in unlabeled networks, with more blocks improving approximation at the cost of increasing complexity.
Takeaways & Limitations
Network communities should be interpreted as one of multiple potentially valid representations, with labels or covariates helping order bins and reveal different insights.
Takeaways & Limitations
The bandwidth-selection procedure can fail to reflect the smoothness of the underlying graphon when its canonical marginal is smoother than the graphon itself.
Abstract
from arXiv · showhide
In this article we introduce the network histogram: a statistical summary of network interactions, to be used as a tool for exploratory data analysis. A network histogram is obtained by fitting a stochastic blockmodel to a single observation of a network dataset. Blocks of edges play the role of histogram bins, and community sizes that of histogram bandwidths or bin sizes. Just as standard histograms allow for varying bandwidths, different blockmodel estimates can all be considered valid representations of an underlying probability model, subject to bandwidth constraints. Here we provide methods for automatic bandwidth selection, by which the network histogram approximates the generating mechanism that gives rise to exchangeable random graphs. This makes the blockmodel a universal network representation for unlabeled graphs. With this insight, we discuss the interpretation of network communities in light of the fact that many different community assignments can all give an equally valid representation of such a network. To demonstrate the fidelity-versus-interpretability tradeoff inherent in considering different numbers and sizes of communities, we analyze two publicly available networks - political weblogs and student friendships - and discuss how to interpret the network histogram when additional information related to node and edge labeling is present.
1 From stochastic networks to histograms
The paper models unlabeled networks through exchangeable graphons and summarizes a single adjacency matrix with a stochastic-blockmodel network histogram. Its bins average edges among groups of similarly connected nodes, with bandwidth determining community size and resolution.
- Network model: An adjacency matrix records binary edge indicators among n nodes, with Aij = 1 for a connection and Aij = 0 otherwise.
- Network model: Exchangeability models networks without treating the observed node ordering as informative, using a graphon, latent uniform node indices, and sparsity scaling.
- Network model: The graphon is estimated up to symmetric axis rearrangement because such rearrangements produce the same distribution on unlabeled graphs.
- Network histogram: A network histogram fits a stochastic blockmodel to one adjacency matrix, with bandwidth h equivalent to choosing the number of communities k.
- Network histogram: Writing n = hk + r sets k = floor(n/h), while community assignments group nodes into equal-sized bins except for a possible remainder.
- Network histogram: Each histogram bin height is the proportion of present edges in its corresponding block of Bernoulli trials, averaged under a likelihood-based node grouping.
2 Universality of blockmodel approximation
The network histogram evaluates blockmodel approximations after removing arbitrary node ordering, allowing a blockmodel to represent unlabeled networks without assuming it is the true generative model. Bandwidth controls the resolution of this approximation.
- Invariant approximation: Approximation error is measured by cut-distance-compatible MISE minimized over measure-preserving symmetric rearrangements of graphon axes.
- Invariant approximation: This rearrangement-invariant criterion accounts for unknown latent ordering, while the fitted assignment vector determines which adjacency entries are averaged.
- Interpretation: Using a single bandwidth shifts the blockmodel from modeling community structure to universally representing arbitrary unlabeled networks.
- Interpretation: The fitted groups collect nodes with similar interaction patterns rather than claiming to recover true latent communities.
- Oracle labeling: An oracle labels nodes by their latent graphon indices, providing ideal scaling and ordering information for evaluating each fixed bandwidth.
3 Determining the histogram bandwidth
The paper selects histogram bandwidth by balancing graphon smoothness, network sparsity, and sample size. An oracle error decomposition motivates data-driven rules, while degree-based smoothness estimation has a stated scope limitation.
- Oracle bandwidth: The oracle bandwidth analysis assumes differentiable graphons, while the result extends to Hölder-continuous functions.
- Oracle bandwidth: Oracle error decomposes into smoothing bias, resolution bias, and variance governed by the effective degrees of freedom h^2ρ_n.
- Oracle bandwidth: For dense networks with ρ_n proportional to 1, the oracle bandwidth scales as √n; greater sparsity requires larger h, whereas steeper graphon gradients require smaller h.
- Oracle bandwidth: The bandwidth h* minimizes the oracle error bound, whose value gives the best possible performance for specified n, ρ_n, and M.
- Automatic selection: The rule of thumb estimates graphon smoothness from sorted degrees and uses that estimate to calculate the histogram bandwidth.
- Automatic selection: The degree-based smoothness estimate can fail to reflect graphon smoothness when the canonical marginal is smoother than the graphon itself.
4 Data analysis using network histograms
The network histogram reveals fine-grained interaction structure in political weblog and student friendship networks, while covariates help interpret otherwise permutation-invariant fitted groups.
- Political weblog data: Using n = 1224 blogs, bandwidth h = 72 produced k = 17 equal-sized histogram bins.The estimated oracle error bound was approximately 1.8 × 10^-2, and each off-diagonal bin had approximately 116 effective degrees of freedom.
- Political weblog data: Nineteen of the 20 most influential liberal blogs were assigned to group 8, while 17 of the top 20 conservative blogs were assigned to group 9.Groups were ordered by political majority and the strength of cross-party connections.
- Political weblog data: Political weblogs show dense within-party linkages, sparse cross-party connections, and additional heterogeneity beyond a two-community division.Nearly 40% of histogram bins are empty, while central groups contain substantial cross-party linkage structure.
- Student friendship data: For School 44, bandwidth h = 66 produced k = 17 equal-sized bins with an oracle error bound of approximately 5.6 × 10^-2.The network was sparser and less smooth than the political weblog network, with approximately 35 effective degrees of freedom per off-diagonal bin.
- Student friendship data: For student friendships, race and grade orderings reveal separated connectivity patterns, whereas friend nominations show less assortativity by race or grade.Groups were ordered post-hoc by mean race, grade, and nominated-friend values.
- Student friendship data: The network histogram summarizes interactions concisely while remaining interpretable through additional covariate information.The student friendship analysis indicates that aggregate race and grade statistics alone may not capture the full pattern of reported social interactions.
5 Discussion
The discussion presents the blockmodel as a flexible representation for unlabeled network interactions, with bandwidth selection controlling approximation precision and complexity. Covariates and labels can order otherwise equivalent histogram representations for interpretation.
- Discussion: Increasing the number of blocks improves approximation of the underlying data-generating mechanism at the cost of greater complexity.The paper frames this as a fidelity-versus-complexity tradeoff analogous to choosing histogram resolution.
- Discussion: The network histogram uses a blockmodel as a nonparametric summary of link densities rather than assuming it is the correctly specified generative mechanism.This approximation-based use requires a milder assumption than treating the blockmodel as the data-generating model.
- Discussion: Automatic bandwidth selection is derived under a smooth Hölder-continuous graphon assumption, with favorable estimation properties also possible for finitely many axis-parallel discontinuities.The latter case includes graphons corresponding to actual blockmodels.
- Discussion: Because histogram bins are defined only up to permutation, observed labels and covariates can guide bin ordering and support multiple useful representations.The student friendship analysis illustrates how alternative orderings can reveal different aspects of network structure.
A Auxiliary results for the proof of Theorem 1
The appendix develops auxiliary lemmas and moment calculations for the oracle estimator under a symmetric α-Hölder graphon assumption. These results characterize block averages, estimator expectations, variances, and the ordering and indexing used in the proof.
- Assumptions: The proof assumes that f is symmetric and α-Hölder continuous on (0, 1)^2, with Hölder constant M and 0 < α ≤ 1.The Euclidean metric on R^2 is used in the Hölder condition.
- Oracle construction: The proof defines block index sets R_ab so that aggregating A_ij over each set recovers the corresponding oracle block estimator.Block regions ω_ab and their edge-index ranges account for interior and boundary groups.
- Moment calculations: The resulting expressions separate approximation effects from sampling variation through linear and square quadrature bounds over the histogram blocks.The proof uses local averages of f and normalized integrals of f^2 over ω_ab, with boundary groups handled separately.
- Oracle construction: The oracle construction orders latent variables ξ and assigns nodes to histogram groups through the inverse rank mapping.The estimator uses i_n = i/(n + 1) and the labeling induced by the ordered latent vector.
- Proof conclusion: The appendix completes the expectation and variance derivations for the oracle estimator, including diagonal and off-diagonal block cases and enlarged boundary widths.For a = k or b = k, the bound replaces h by 2h.
- Moment calculations: The auxiliary lemmas derive the means and variances of individual edge indicators and use them to establish the corresponding moments of each oracle block estimator.The argument combines conditioning, Jensen’s inequality, the law of total variance, and covariance calculations.