Source-linked AI summary
Network Cross-Validation for Determining the Number of Communities in Network Data
Kehui Chen, Jing Lei
TL;DR
The paper addresses how to determine the number of communities and choose between regular and degree corrected block models when community recovery methods require K in advance. It develops an efficient NCV procedure based on block-wise node-pair splitting and evaluates candidate models by predictive loss. Under appropriate conditions, NCV avoids underestimating the number of communities with probability tending to one, with simulations and a political-blog example demonstrating its performance.
Problem
Most community recovery methods require K, the total number of communities, to be known in advance, while network model-selection theory remains open.
Method
NCV uses block-wise node-pair splitting to fit models on one portion of the adjacency matrix and compare candidate models using predictive loss on a testing portion.
Results
Under appropriate conditions, NCV does not underestimate the number of communities with probability tending to one, and simulations and a data example demonstrate its effectiveness.
Takeaways & Limitations
NCV can select among general, non-nested candidate models, including simultaneous choice between regular and degree corrected block models and the number of communities.
Takeaways & Limitations
The paper does not provide performance analysis of NCV for degree corrected block models, instead giving accuracy guarantees for community recovery and edge-probability estimation.
Abstract
from arXiv · showhide
The stochastic block model and its variants have been a popular tool in analyzing large network data with community structures. In this paper we develop an efficient network cross-validation (NCV) approach to determine the number of communities, as well as to choose between the regular stochastic block model and the degree corrected block model. The proposed NCV method is based on a block-wise node-pair splitting technique, combined with an integrated step of community recovery using sub-blocks of the adjacency matrix. We prove that the probability of under selection vanishes as the number of node increases, under mild conditions satisfied by a wide range of popular community recovery algorithms. The solid performance of our method is also demonstrated in extensive simulations and a data example.
1 Introduction
Network community models are widely used to represent hidden structure in growing network datasets, but selecting the number of communities remains difficult because most recovery methods assume it is known. The paper develops network cross-validation using block-wise node-pair splitting to support efficient model and community-number selection.
- Motivation: Network data and demand for statistical inference tools have grown rapidly, motivating methods for identifying hidden communities in observed networks.Community structure reflects differing edge densities within and between coherent subpopulations.
- Motivation: Stochastic block models and degree corrected block models provide established tools for modeling large networks with community structures.These models have been used across social science, biology, and information science.
- Open problem: Most community recovery methods require K, the total number of communities, to be known in advance.Existing approaches use tools including maximum likelihood, convex optimization, spectral methods, and belief propagation.
- Open problem: Determining the number of communities is challenging and has attracted increasing research interest.Prior work includes sequential extraction and recursive bipartition procedures with bootstrap or eigenvalue-based testing.
- Open problem: Traditional network cross-validation approaches can be computationally intensive, while theoretical guarantees for network model selection remain open.The paper focuses on a generic network cross-validation idea to address this gap.
- Proposed approach: The proposed NCV uses block-wise node-pair splitting and can choose among non-nested candidate models, including the regular and degree corrected block models with simultaneous selection of K.The method is illustrated on political blog data, where it selects the degree corrected block model with two communities.
2 Network cross-validation for stochastic block models
NCV estimates communities and edge probabilities from a block-wise node-pair split, then selects K by predictive loss on held-out node pairs. Under stated conditions, it provides theoretical protection against underestimation and supports efficient model selection.
- Block-wise node-pair splitting: NCV partitions nodes into N1 and N2, fitting on A(11) and A(12) and testing on A(22), thereby using the full adjacency matrix.The split supports direct comparison of candidate community counts through testing-set predictive loss.
- Block-wise node-pair splitting: Unlike node splitting, block-wise node-pair splitting uses cross-group edges and enables conditional treatment of memberships as parameters.This avoids likelihood calculations with missing memberships and reduces unnecessary randomness from discarding fitting–testing edges.
- Estimation and validation: Spectral clustering estimates memberships from the rectangular fitting matrix, after which plug-in edge probabilities are validated on held-out pairs.Negative log-likelihood and squared-error losses gave almost identical performance in the numerical experiments.
- Estimation and validation: The validated loss is expected to favor the true K because underfitting misses structure while overfitting produces noisy predictions on testing data.The paper evaluates candidate K values using predictive loss on the testing set.
- V-fold procedure: The V-fold procedure randomly partitions nodes into V subsets, fits each candidate after removing one subset's rows, and evaluates loss on that subset's within-block edges.The experiments used V = 3 and found performance insensitive to the choice of V.
- Theoretical properties: Under conditions A1–A3, the theory establishes under-selection protection, while Corollary 3 gives vanishing under-selection probability for fixed candidate sets containing the truth.The result combines community-recovery consistency with predictive-loss comparisons for candidate K values.
3 Degree corrected block models and further extensions
The degree corrected block model extends the stochastic block model by modeling node-specific activeness, and NCV can select between these models while choosing the number of communities. Theoretical guarantees cover community recovery and edge-probability estimation under stated conditions, but NCV performance analysis for DCBMs is outside the paper’s scope.
- Degree corrected block model: The degree corrected block model adds node-specific activeness parameters ψ_i to community memberships g and connectivity matrix B; SBM is recovered when ψ_i = 1.The parameters satisfy a block-wise identifiability constraint.
- Community recovery: Spherical spectral clustering normalizes singular-vector rows to separate community structure from node activeness before k-median clustering.The normalized matrix contains community information, while singular-vector row norms contain activeness information.
- NCV procedure: The resulting NCV procedure estimates community memberships, connectivity, and activeness, then computes validation probabilities for candidate models.The plug-in estimator uses an estimate of normalized activeness because of scaling identifiability.
- Scope: Performance analysis of NCV for degree corrected block models is beyond the scope of the paper.The paper instead provides accuracy guarantees for community recovery and edge-probability estimation.
- Theory: Under (A1)–(A3), spherical spectral clustering provides approximate community consistency, while stronger average-edge conditions control connectivity estimation error.The theorem also gives uniform relative accuracy for estimated edge probabilities on all but a vanishing proportion of node pairs when n = o(n^1/3).
- Model selection: NCV simultaneously chooses between SBM and DCBM and selects the number of communities by minimizing the overall cross-validation loss.The candidate models need not be nested or hierarchical.
4 Numerical Experiments
Simulations evaluate NCV for selecting community counts, comparing it with recursive bipartition, and jointly selecting SBM or DCBM with the community count. NCV performs strongly across sparse, imbalanced, general, and degree-corrected settings, and selects DCBM with two communities in the political-blog example.
- Simulation 1: Simulation 1 evaluates stochastic-block-model selection of K under five sparsity levels and varying smallest-community sizes with n = 1000.The sparsity values are r ∈ {0.01, 0.02, 0.05, 0.1, 0.2}, covering smallest expected degrees from 12 to 400.
- Simulation 2: Simulation 2 compares NCV with recursive bipartition across true K = 1, 2, 3, 4 and sample sizes n = 600 and n = 1200.The design uses general randomly generated block structures.
- Simulation 2: NCV performs uniformly better than bipartition and is much faster because bipartition requires bootstrap adjustment at each testing step.Both methods benefit from larger samples, while selecting K becomes harder as the true K increases.
- Simulation 2: For n = 1200, NCV’s empirical success rates are 100% for K = 1, 2, 84% for K = 3, and 72% for K = 4.These rates are reported for the general block-structure simulation.
- Simulation 3: Simulation 3 finds that NCV almost perfectly selects SBM and the correct K across tested sizes, while DCBM requires relatively larger samples.For n = 1200, NCV can almost always select the correct DCBM and K.
- Data example: On the political-blog network, three-fold NCV consistently selects DCBM with two communities, choosing that result in 99 of 100 independent splittings.The analyzed largest connected component contains 1222 nodes.
5 Discussion
The discussion presents NCV as applicable beyond SBM and DCBM when conditional edge independence and accurate estimation from adjacency-matrix row subsets hold. It also notes that fold choice has little empirical effect, while testing uses only diagonal blocks.
- Further extensions: NCV applies to network models with conditionally independent edges and edge probabilities estimable from a subset of adjacency-matrix rows.SBM and DCBM satisfy these two properties, and other models may also qualify.
- Data example: For the political-blog data, cross-validated negative log-likelihood compares dashed SBM candidates with solid DCBM candidates across repeated block splittings.The figure caption states that results are consistent over 100 repeated random splittings.
- Further extensions: The proposed approach uses only the fitting subset of node pairs for model fitting before validation.This is part of the block-wise node-pair design.
- Effect of the number of folds: Empirically, NCV is insensitive to the number of folds, although unlike traditional cross-validation its testing samples are only diagonal blocks.Consequently, the proportion of edges in testing samples differs from standard cross-validation.
A.1 Proof of Theorem 2
The proof analyzes NCV fold losses separately when the candidate community count is below the truth and when it equals the truth with consistent recovery. It uses random-splitting concentration and clustering-error arguments to establish the relevant loss behavior.
- Proof setup: The proof focuses on one NCV fold, with N1 providing fitting nodes and N2 providing testing nodes, then sums the resulting bounds over folds.True and estimated communities in N2 are represented by I_l and Ĩ_k.
- Under-selection case: When the candidate count satisfies ˜K < K, the proof identifies true communities merged by estimated clusters and exploits differing rows of B0.This creates node-pair groups whose edge probabilities differ under the true structure.
- Under-selection case: Hypergeometric tail bounds show that the testing block inherits the stochastic-block-model structure and assumptions with overwhelming probability over random splitting.The resulting block proportions may use a different constant π′_0.
- Loss comparison: The proof decomposes the fold loss difference into terms labeled I, II, and III and concludes the corresponding corollary.The decomposition is stated for the vth fold.
- Exact-recovery case: For ˜K = K with exact recovery, the estimated connectivity error is ϵ_n = O_P(√(ρ_n/n)), and fitting estimates are independent of testing edges.This supports concentration of the fold validation loss around its target.
A.2 Proof of Theorem 1 and Theorem 4
The proof represents the population matrix and its testing submatrix through community membership structure, while fixing notation for matrix norms and singular values.
- For an NCV fold, A(1) and P(1) denote the testing rectangular submatrices of the adjacency and population matrices.The population matrix satisfies Pij = B_gi_gj.
- The proof defines σK(M) as the Kth largest singular value and uses spectral and Frobenius norms for matrices.The spectral norm is σ1(M), while the Frobenius norm is the square root of the sum of squared singular values.
A.2.1 Preliminary results
The preliminary results control community sizes, adjacency-matrix perturbations, singular-subspace errors, and clustering accuracy under assumptions covering both SBM and DCBM settings.
- The technical lemmas establish the ingredients needed to prove the main theorems.These include split-community size, spectral norm, singular subspace, and clustering bounds.
- Under Assumption (A1), split-community sizes are controlled using hypergeometric large-deviation bounds and a union bound.The proof of this size result is omitted.
- Lemma 6 gives a high-probability spectral norm bound of order √nρn for partial adjacency matrices under the degree corrected block model.The argument also covers regular SBM, yielding ∥A(1) − P(1)∥ ≤ C√nρn with high probability.
- Lemma 7 bounds the top-K singular-subspace error by 2∥M̂ − M∥/σK(M) after an orthogonal alignment.The result follows from Wedin’s sin Θ theorem and Weyl’s inequality.
- Approximate k-means and k-median clustering recover all but error-proportional numbers of nodes when their embedding errors are small relative to row separation.The k-means bound uses the Frobenius norm, while the k-median analogue uses the ℓ2,1 norm and Assumption A2.
A.2.2 Proof of Theorem 1
Theorem 1 is proved by expressing the population testing matrix through normalized community memberships, controlling its singular subspace, and applying the k-means perturbation bound.
- The testing population matrix P(1) factors through the community-membership matrix, whose normalized columns are orthonormal.Consequently, its top-K right singular subspace is spanned by the normalized membership matrix up to an orthogonal transformation.
- With high probability, each split community is sufficiently large and the testing adjacency perturbation satisfies ∥A(1) − P(1)∥ ≤ C√nαn.The corresponding population singular value obeys σK(P(1)) ≥ Cnαn, enabling singular-subspace control.
- The k-means clustering algorithm misclusters no more than C/αn nodes.
A.2.3 Proof of Theorem 4
Theorem 4 extends the spectral-recovery argument to degree correction by using normalized degree-weighted memberships, k-median clustering, and consistency of estimated block probabilities.
- Under degree correction, the testing population matrix factors through a normalized degree-weighted membership matrix with orthonormal columns.The top-K right singular subspace is spanned by this matrix up to an orthogonal transformation.
- The population embedding has distinct community rows, and distinct row-normalized community centers are separated by a positive distance.Rows from different communities are orthogonal before row normalization.
- With high probability, split communities are sufficiently large and the partial adjacency perturbation is bounded by C√nαn.This permits application of the singular-subspace perturbation bound in the degree-corrected setting.
- The row-normalized embedding is handled by controlling normalization error, including possible zero rows, under the stated minimum degree and regularity assumptions.The proof bounds zero rows using the minimum row norm and then applies a vector normalization inequality with Cauchy–Schwarz and Assumption A3.
- Applying the k-median perturbation lemma yields agreement between estimated and true memberships except for an order-controlled number of nodes.
- For all but a vanishing proportion of node pairs, estimated and true community labels agree, supporting consistency of the estimated block probabilities.The proof compares numerator and denominator terms and shows their relevant ratios tend to one.