Source-linked AI summary
Consistent adjacency-spectral partitioning for the stochastic block model when the model parameters are unknown
Donniell E. Fishkind, Daniel L. Sussman, Minh Tang, Joshua T. Vogelstein, Carey E. Priebe
TL;DR
Consistent spectral partitioning in stochastic block models has previously required knowing both the number of blocks and the communication matrix rank. This paper modifies adjacency-spectral partitioning to use only a rank upper bound and proves consistency, including when the rank is overestimated, for directed or undirected graphs and multiple modalities.
Problem
Existing normalized-Laplacian and adjacency-spectral procedures require K and rank(M) to be known, despite other model parameters being unknown.
Source: §1 · p. 2Method
The paper modifies adjacency-spectral partitioning to require only an upper bound on rank(M), and extends it to estimate K and handle directed or undirected graphs and multiple modalities.
Source: §1 · p. 2, §2.3 · p. 8Results
The modified procedure remains consistent when rank(M) is overestimated, and its guarantee covers directed or undirected graphs and one or multiple modalities.
Source: §1 · p. 2, §2.3 · p. 8Takeaways & Limitations
An overestimate of rank(M) does not destroy consistency, supporting adjacency-spectral partitioning when the exact rank is unknown.
Source: §1 · p. 2The procedure still assumes a known upper bound on rank(M).
Source: §7 · p. 20
Abstract
from arXiv · showhide
For random graphs distributed according to a stochastic block model, we consider the inferential task of partioning vertices into blocks using spectral techniques. Spectral partioning using the normalized Laplacian and the adjacency matrix have both been shown to be consistent as the number of vertices tend to infinity. Importantly, both procedures require that the number of blocks and the rank of the communication probability matrix are known, even as the rest of the parameters may be unknown. In this article, we prove that the (suitably modified) adjacency-spectral partitioning procedure, requiring only an upper bound on the rank of the communication probability matrix, is consistent. Indeed, this result demonstrates a robustness to model mis-specification; an overestimate of the rank may impose a moderate performance penalty, but the procedure is still consistent. Furthermore, we extend this procedure to the setting where adjacencies may have multiple modalities and we allow for either directed or undirected graphs.
1 Background and overview
The paper studies consistent vertex partitioning in stochastic block models when block memberships and edge probabilities are unobserved. It modifies adjacency-spectral partitioning to require only an upper bound on the communication matrix rank, and extends the analysis to directed graphs and multiple adjacency modalities.
1 Background and overview
- Consistency means the fraction of misassigned vertices converges almost surely to zero as the number of vertices grows.The realized adjacencies are observed, but the realized partition and Bernoulli trial parameters are not.Source: §1 · p. 2
- The modified adjacency-spectral procedure remains consistent when given only an upper bound on rank(M), so overestimating the rank does not destroy consistency.Earlier normalized-Laplacian and adjacency procedures required both K and rank(M) to be known, although other model parameters could be unknown.Source: §1 · p. 2
- The analysis covers directed and undirected graphs and multiple adjacency modalities, including dependent communications across modalities when each block pair is discernable in at least one mode.The discernability condition is specified as an assumption for the multi-modal setting.Source: §1 · pp. 2–3
- The paper frames this robustness as a step toward principled spectral analysis when stochastic block model assumptions do not strictly hold.The authors anticipate further consistency work for spectral partitioning in nonparametric models.Source: §1 · p. 4
2 The model, the adjacency-spectral partitioning procedure, and its consistency
The paper defines a stochastic block model with unknown memberships and applies adjacency-spectral clustering using a known rank upper bound. Its procedure has a consistency guarantee across directed or undirected graphs and one or multiple communication modalities.
2.1 The stochastic block model
- The model assigns vertices independently to K blocks and generates edges according to block-pair probabilities, with both directed and undirected graphs covered.For multiple modalities, each has its own probability matrix and adjacency matrix; dependence across modalities is allowed.Source: §2.1 · pp. 5–6
2.2 The adjacency-spectral partitioning procedure
- Adjacency-spectral partitioning takes a rank-bounded singular value decomposition, forms vertex representations, and clusters their rows into at most K groups.The procedure selects left, right, or combined representations according to whether probability-matrix rows or columns are known to be distinct; the multi-modal version applies the procedure across modalities.Source: §2.2 · pp. 6–7
2.3 Consistency of the adjacency-spectral partitioning of Section 2.2
- Theorem 1 states that adjacency-spectral partitioning has almost always fewer than nϵ misassignments and applies to directed or undirected graphs, with one or multiple communication modalities.For R = rankM, Sussman et al. [24] showed an almost-always bound below a constant times log n; the present result says misassignments remain negligible if rankM is overestimated.Source: §2.3 · pp. 7–8
3 Ancillary results
The analysis represents block memberships through latent vectors derived from the communication matrix, then establishes spectral bounds that support consistency. These bounds also explain why using an upper bound on the matrix rank preserves the procedure’s consistency.
3.1 Latent vectors and constants from the model parameters
- The proof uses constants α, β, and γ to bound block proportions, separate distinct latent vectors, and lower-bound eigenvalues of the factor matrices.These quantities support the analysis, but are not needed to run the procedure or invoke its consistency result.Source: §3.1 · pp. 8–9
- The communication matrix is factored as M = µν^T, and the resulting left and right latent vectors encode edge probabilities through inner products.The vectors are associated with vertices by their block memberships, but are not observed.Source: §3.1 · p. 9
3.2 Bounds
- The adjacency matrix’s rank-M singular value is bounded below while its (rank M + 1)th singular value is bounded above, separating signal from residual spectral components.The stated bounds are αγn below and 3^(1/4)n^(3/4) log^(1/4)n above, respectively.Source: §3.2 · p. 11
- The analysis targets robustness to overestimating rank M: the procedure remains consistent when supplied rank upper bound R exceeds the true rank.The section notes that a threshold on adjacency singular values can also consistently estimate rank M.Source: §3.2 · p. 12
- Distinct latent-vector rows remain separated after transformation to singular-vector rows, supporting the later recovery of block membership from the spectral embedding.The bounds cover left and right vectors and their scaled forms under orthogonal transformations.Source: §3.2 · p. 12
4 Proof of Theorem 1, consistency of the adjacency-
The proof compares a fitted matrix with a transformed spectral embedding and uses separation between block representations to control assignment errors. It extends to multiple modalities and cases where block probability rows are not known to be distinct.
spectral procedure of Section 2.2
- For any fixed ε > 3/4, the procedure’s number of misassignments is almost always less than n^ε when block probability rows are pairwise distinct in the single-modality case.The fitted matrix C approximates the transformed spectral embedding, and separated block representations let the procedure associate each block with one distinct row.Source: spectral procedure of Section 2.2 · pp. 15–16
- The proof controls the Frobenius error between C and the padded transformed embedding by n^ξ, for fixed ξ > 3/8.It combines bounds on the embedding approximation and the residual spectral component.Source: spectral procedure of Section 2.2 · p. 15
- The argument extends to multiple modalities and to cases where the rows of M are not known to be pairwise distinct, with relevant bounds changing by at most a constant factor.The proof substitutes modality-specific embeddings or their concatenations for the single-modality matrices.Source: spectral procedure of Section 2.2 · p. 16
5 Consistent estimation for the number of blocks K
The section estimates the unknown number of blocks by testing candidate partition counts against a Frobenius-error threshold. The resulting estimator almost always equals the true number of blocks.
5 Consistent estimation for the number of blocks K
- The analysis simplifies to one communication modality and pairwise distinct rows of M, while the authors state it generalizes to the broader case.The stated simplifications do not affect the results.Source: §5 · p. 16
- Using the spectral procedure from Section 2.2 with K′ parts, the Frobenius error ∥C −X∥F is almost always at most nξ when K′ = K, and greater than nξ when K′ < K.Source: §5 · p. 17
- Almost always, the estimator ˆK equals K when R is a known upper bound on rank M.The estimator selects the least candidate count whose fitted matrix has Frobenius error at most n^ξ.Source: §5 · pp. 16–17
6 The extended adjacency-spectral partitioning procedure
The extended procedure removes the requirement that K be known, retaining only a known upper bound on rank M. It successively tests candidate part counts and returns a consistent partition.
6 The extended adjacency-spectral partitioning procedure
- The extended adjacency-spectral procedure assumes a known integer R ≥ rank M but does not require K to be known.The earlier procedure assumed both the rank upper bound and known K.Source: §6 · p. 18
- It increases K′ from 1 and stops at the first candidate whose fitted matrix has Frobenius error at most n^ξ, returning that partition.The threshold uses fixed 1/8 < ξ < 1/2.Source: §6 · p. 18
- For any fixed ε > 3/4, the extended procedure’s number of misassignments is almost always less than n^ε.The result follows because its selected count almost always equals K, after which Theorem 1 applies.Source: §6 · p. 18
7 Another consistent estimator for K
This section presents a second consistent estimator for K, using minimum part size and centroid separation to distinguish the true block count from overpartitioning. Its consistency comes with additional known-parameter requirements beyond those for the earlier estimator.
7 Another consistent estimator for K
- With K′=K, the procedure has large parts and separated centroids; when K′>K, the size and separation criteria cannot both hold.The theorem contrasts these behaviors to distinguish the correct number of parts from an overestimate.Source: §7 · p. 19
- This estimator requires known ζ and ϑ satisfying stated lower-bound conditions, plus an upper bound on rankM; the earlier ˆK needs fewer assumptions.The paper notes that ˆK is used for the extended procedure because it requires fewer assumptions.Source: §7 · pp. 19–20
- ˇK selects the greatest tested K′ whose minimum part size exceeds ϑn and whose centroid separation is at least ζ.The procedure uses the adjacency-spectral partition with K′ parts and checks these two criteria.Source: §7 · pp. 18–20
- Almost always, the second estimator ˇK equals the true block count K.Theorem 14 establishes consistency for this estimator.Source: §7 · p. 20
- When the required lower bounds are known, checking whether ˆK=ˇK for one n can increase confidence that their shared value is K.Source: §7 · p. 20
8 A simulated example and discussion
Simulations examine adjacency-spectral partitioning with correct, excessive, and insufficient rank bounds, and test an estimator for K. Overestimating rank performs well in the partitioning example, while the block-count estimator’s behavior depends on sample size and its tuning threshold.
8 A simulated example and discussion
- The partitioning experiment used 2500 replications for n=100 to 1400, with K=3 and rank bounds R=1, 2, 3, 10, and 25.R=1 was deliberately chosen not to be an upper bound on rankM.Source: §8 · p. 20
- At n=1600, R=2 gives effectively zero misassignments; R=10 and 25 perform very well, while invalid R=1 is almost chance (Figure 1).Source: Figure 1 · p. 21, §8 · p. 21
- At n=6400, ˆK is a good estimate for R=3 near ξ=3/8 and equals the true K for R=6 near that threshold; smaller n selects too few blocks.For larger ξ, ˆK tends to be smaller; for smaller ξ, it tends to be larger.Source: Figure 2 · p. 22, §8 · p. 22
- The K-estimation experiment compared log_n(∥C_K′−X∥_F) for K′=2, 3, 4, using R=3 or 6 across 50 replications.Figure 2 reports the statistic’s mean and standard deviation across replicates for each R, K′, and n.Source: §8 · pp. 21–22
9 Discussion
The discussion reports promising K-estimation performance under selected moderate-size settings and identifies proof-method, scalability, missing-data, and spectral-choice questions for future work. It also notes practical implementation choices and possible inference improvements from diagonal imputation.
9 Discussion
- Good performance is possible for estimating K at moderate n under certain parameter selections.The authors suggest this estimator may serve as a stepping stone toward more effective estimators.Source: §9 · p. 22
- Different proof methods may allow ξ to be as small as 1/4, an operator-norm question left for further investigation.The authors identify operator-norm bounds as an important area for future work on spectral inference for random graphs.Source: §9 · p. 23
- The first simulation uses k-means because minimizing ∥C − X∥F is computationally unfeasible; approximate SVD methods remain a prospect for larger graphs.Fast SVD methods are cited as supporting use on quite large graphs.Source: §9 · p. 23
- Extending the method to a growing number of blocks may be possible, but consistency of the K estimator would require careful analysis.Source: §9 · p. 23
- Uniformly random missing edges preserve the block structure, while other forms of missing data warrant further study.Source: §9 · p. 23
- With no self-loops, the adjacency diagonal is zero; cited imputation methods have been shown to improve inference in practice.The authors cite Marchette et al. and Scheinerman and Tucker for diagonal-imputation methods.Source: §9 · p. 23
- Which performs better, adjacency- or Laplacian-based partitioning, appears to depend on stochastic block model parameters; the criterion remains open.The discussion also identifies formal results for spectral partitioning beyond block-model assumptions as a future direction.Source: §9 · p. 23