Source-linked AI summary
Pseudo-likelihood methods for community detection in large sparse networks
Arash A. Amini, Aiyou Chen, Peter J. Bickel, Elizaveta Levina
TL;DR
Large and sparse networks challenge existing community-detection methods. This paper develops fast unconditional and degree-conditional pseudo-likelihood algorithms, uses perturbed spectral clustering for initialization, and establishes consistency under supported conditions for two communities.
Problem
Existing community-detection methods often do not scale to very large networks and can perform poorly on sparse networks.
Method
The paper develops fast pseudo-likelihood algorithms, including a degree-conditional variant, and spectral clustering with perturbations for initialization.
Results
The proposed algorithms provide fast and accurate community detection across settings including large and sparse networks, while pseudo-likelihood is consistent under a mild starting-value condition for two communities.
Takeaways & Limitations
Pseudo-likelihood offers a scalable approach to fitting block models, including networks with substantial degree variability and sparse structure.
Takeaways & Limitations
The consistency analysis was not extended to more than two communities, although the authors state that such an extension seems possible.
Abstract
from arXiv · showhide
Many algorithms have been proposed for fitting network models with communities, but most of them do not scale well to large networks, and often fail on sparse networks. Here we propose a new fast pseudo-likelihood method for fitting the stochastic block model for networks, as well as a variant that allows for an arbitrary degree distribution by conditioning on degrees. We show that the algorithms perform well under a range of settings, including on very sparse networks, and illustrate on the example of a network of political blogs. We also propose spectral clustering with perturbations, a method of independent interest, which works well on sparse networks where regular spectral clustering fails, and use it to provide an initial value for pseudo-likelihood. We prove that pseudo-likelihood provides consistent estimates of the communities under a mild condition on the starting value, for the case of a block model with two communities.
1. Introduction.
Community detection is a fundamental network-analysis problem, but existing model-based methods face computational and sparsity challenges. The paper introduces fast pseudo-likelihood algorithms, spectral clustering with perturbations, and a consistency analysis.
- Community detection seeks to infer node labels and typically estimate the block-model parameters π and P from the adjacency matrix.
- Existing fitting methods often scale to thousands but not millions of nodes, while some alternatives require computationally challenging graph-pattern counting.
- Standard consistency results generally require increasing average degree, with strong consistency needing λn to grow faster than log n and weak consistency requiring λn →∞.
- The paper proposes a fast pseudo-likelihood algorithm for the block model and a degree-conditional variant for networks with highly variable within-community degrees.
- Ignoring adjacency symmetry and compressing rows into block sums yields an approximation scalable to networks with tens of millions of nodes.
- Spectral clustering with perturbations is proposed for sparse networks, used to initialize pseudo-likelihood, alongside a consistency proof requiring an initial value with sufficient overlap.
2. Algorithms.
The algorithms approximate block-model likelihoods using block-sum statistics and EM, condition on degrees when degree variability is problematic, and perturb sparse networks before spectral initialization.
- An initial labeling partitions nodes into groups, after which block sums provide the statistics used by the pseudo-likelihood procedure.
- Conditional on labels, block sums are treated as independent Poisson variables, making each node’s vector a mixture of Poisson distributions.
- The pseudo-likelihood estimate is obtained by maximizing the mixture objective with EM, repeatedly updating label probabilities, parameters, and the partition.
- Conditioning pseudo-likelihood on observed node degrees prevents degree variability from dominating the fitted community structure.
- Regular spectral clustering can perform poorly when sparse graphs have expected degree λ < 5, as disconnected components collapse the spectral representation.
- Spectral clustering with perturbations adds low-weight links through a constant matrix, then applies the usual Laplacian, spectral representation, and K-means steps.
3. Consistency results.
The paper proves uniform consistency of one CPL iteration for two-community block models under specified assumptions, using a directed-model analysis coupled to the undirected case. The analysis requires informative initialization and shows that a key signal parameter must grow, while CPL behaves like neighborhood majority voting in the balanced case.
- Assumptions: The consistency analysis conditions on deterministic labels and focuses on two balanced communities, each containing m = n/2 nodes.The assumptions also set the estimated community proportions to 1/2.
- Proof strategy: The proof first analyzes a directed block model, where adjacency entries are independent, and then transfers the result to the undirected model through a coupling.The directed model is also the setting in which the pseudo-likelihood independence assumption holds.
- CPL iteration: CPL starts from parameter estimates and an initial labeling, then produces label estimates through an E-step based on the initial-label confusion matrix and estimated edge probabilities.The analysis requires the initial labeling to have at least a specified overlap with the truth, and seeks a uniform result over all such labelings.
- Scope: The theoretical result establishes weak consistency of labels, while the paper does not pursue asymptotic normality or a full parameter-consistency analysis.A separate remark notes that directed-model parameter estimates are also consistent as a consequence of the theorem, but further asymptotic results are left open.
- Consistency results: Under a ≠ b and the theorem’s growth conditions, the CPL estimate is uniformly consistent in both the directed and undirected settings.For the directed model, the theorem states consistency as n →∞ with u_n →∞; the undirected result additionally requires n,aγ →∞ with u_n,v_n →∞.
- Interpretation: In the general two-community case, τ^2_n is the key parameter that must grow for CPL to succeed.The balanced b = 0 case has a neighborhood-majority-voting interpretation: sparse graphs can spread incorrect labels, whereas dense graphs can reduce them.
4. Numerical results.
Simulations compare pseudo-likelihood, spectral, degree-based, and belief-propagation methods across community separation, sparsity, degree variation, and network size. Spectral clustering with perturbations is broadly effective, while pseudo-likelihood improves weak starts and supports scalable fitting.
- Experimental design: The simulations vary out-in-ratio β, average expected degree λ, degree heterogeneity, initialization, and network size across multiple community-detection methods.Performance is measured using normalized mutual information, whose value is 1 for a perfect match.
- Accuracy: Smaller β and larger λ generally make label estimation easier, while spectral clustering with perturbations performs very well across scenarios.Regular spectral clustering performs poorly with nonuniform community weights, whereas perturbations improve robustness.
- Accuracy: Pseudo-likelihood makes large gains over poor starting values, including uninformative degree clustering when w = (1,1,1).With spectral clustering with perturbations as initialization, pseudo-likelihood has less room to improve, although unconditional pseudo-likelihood remains highly competitive.
- Degree heterogeneity: Conditioning is necessary for unconditional pseudo-likelihood's difficult ρ = 0.9, w = (1,1,1) case when initialization is poor.A good starting value can overcome the regular block model's tendency to separate hub and low-degree nodes by degree.
- Runtime: Runtime comparisons exclude initialization time for UPL and CPL, which is reported separately; SCP generally provides a low-complexity starting value.For w = (1,5,10), spectral clustering takes considerably longer than the other methods, while SCP remains near its uniform-weight runtime.
- Comparison: Belief propagation scales with n at the same rate as the proposed methods but was about 10 times slower in the reported comparisons.Direct comparison is difficult because the implementations use different platforms and handle initial values differently.
5. Example: A political blogs network.
The political-blogs network has strongly heterogeneous degrees, making it a useful test of unconditional versus degree-conditioned pseudo-likelihood. Conditional pseudo-likelihood produces labels closest to the manually assigned liberal and conservative labels.
- Data: The largest connected component contains 1222 political blogs with average degree 27, median degree 13, and maximum degree 351.Edges are hyperlinks, directions are ignored, and manual liberal/conservative labels are treated as truth.
- Results: CPL produces the result closest to the true labels in this highly variable-degree network.Its result is also close to degree-corrected profile maximum likelihood and two modularity methods.
- Methods: Figure 5 compares true labels with UPL and CPL initialized by SCP, while node size represents log degree.The comparison directly displays how degree variation relates to the estimated communities.
- Results: UPL groups high-degree and low-degree nodes separately, closely matching the ordinary block-model solution.This differs from CPL's behavior in the degree-heterogeneous political-blogs example.
6. Proofs of consistency results.
The consistency analysis establishes concentration and error bounds for pseudo-likelihood estimates under a two-community block model, treating directed and undirected networks. The proof uses symmetry, tail bounds, and a coupling between directed and undirected adjacency matrices.
- Assumptions: The proof assumes, without loss of generality, γ ∈ (0, 1/2) and a > b, with label switching covering the other parameter orderings.These assumptions exploit community-label symmetry rather than restricting the substantive cases considered.
- Setup: The analysis partitions nodes according to the initial labeling and controls community-size and mismatch quantities under the event Eγ.Under Eγ, the relevant sets have equal cardinality m and prescribed proportions involving γ.
- Proof strategy: Bernstein inequalities provide tail bounds for the pseudo-likelihood score ξi(σ) and related counts used to control classification errors.The argument combines these bounds with symmetry and union bounds over candidate labelings.
- Undirected model: A deterministic coupling transfers the directed-case bounds to the undirected adjacency matrix by relating undirected edges to directed edge pairs.The proof notes that the undirected graph is obtained by removing directions and completes the argument with analogous tail bounds.
- Undirected model: Theorem 2 follows after bounding the additional undirected contributions and repeating the directed-case argument.The supplied proof passages identify the final step but do not state the theorem's full rate or parameter condition.
7. Discussion.
The discussion reports fast, accurate performance and a consistency result for a local pseudo-likelihood maximum. It also identifies limits involving community count, parameter estimation scope, and practical initialization.
- Conclusions: The algorithms provide fast and accurate community detection across large and sparse networks, while the theory establishes consistency and local uniqueness near the truth.The consistency result removes the need to assume that EM reaches the global maximum.
- Scope: The theoretical analysis extends to unbalanced two-community models, but extension beyond two communities was not pursued.The authors describe the multi-community extension as possible but requiring meticulous tracking of many terms.
- Scope: Parameter consistency is only partially addressed: the paper shows weak label consistency, while stronger parameter conclusions are discussed conditionally.The directed pseudo-likelihood is exactly the likelihood of the row-sum variables, and EM parameters converge to a local maximum.
- Practical limitations: Although reasonable initial values guarantee convergence in theory, initialization remains important in practice, and spectral clustering with perturbations needs further study.The authors specifically identify empirical tuning and theoretical analysis of this initializer as future work.
APPENDIX: POISSON-TYPE TAIL BOUND
The appendix states a Poisson-type tail-bound lemma for sums of independent Bernoulli variables and proves it using a direct Chernoff-bound argument. The resulting bound applies for u > 1/e.
- Lemma statement: Lemma 5 considers independent Bernoulli variables X_1,...,X_m with expectations p_i and sum S_m.It defines μ̄ = m^-1μ, with μ implied by the sum of the p_i.
- Proof: The proof compares S_m with a binomial variable S*_m ~ Bin(m, μ̄) using Hoeffding’s convex-order result.The comparison is applied to convex functions g, including g(x) = e^(βx).
- Poisson comparison: The resulting right-hand side is the Chernoff bound for a Poisson random variable with mean μ = Σ_i p_i.The bound is optimized for thresholds t > μ.
- Final bound: For t = e u μ with u > 1/e, the appendix obtains P(S_m > e u μ) ≤ (1/u)e u μ.The derivation also uses e^-μ ≤ 1 to reach the stated bound.
SUPPLEMENTARY MATERIAL
The supplementary material extends Theorem 1 to the case of unbalanced communities. It is provided as a separate PDF supplement.
- Scope: The supplement contains an extension of Theorem 1 to unbalanced communities.The extension addresses communities whose sizes are not balanced.
- Resource: The supplementary material is identified by DOI 10.1214/13-AOS1138SUPP.The passage labels this resource as a PDF supplement.
- Organization: The supplement is separate from the main paper and focuses specifically on the unbalanced-community extension.Its stated content is limited to extending Theorem 1 in that setting.