Analysis of spectral clustering algorithms for community detection: the general bipartite setting

1 Introduction

• The paper situates its analysis in renewed interest in spectral methods for network clustering and stochastic block models.It identifies prior consistency results and regularized adjacency and Laplacian concentration results as key inspirations.Source: §1 · pp. 1, 3
• The analysis treats spectral clustering as regularization and concentration, spectral truncation, and a k-means-type step whose variations yield different algorithms and consistency results.The final step need not solve the standard k-means problem; sufficient approximation conditions can also be met by other approaches.Source: §1 · p. 2
• The data-driven adjacency regularization avoids unknown maximum expected degrees and achieves the same concentration bound as its oracle counterpart under a general SBM.Regularization is motivated by restoring adjacency-matrix concentration in sparse networks, where average degree may be constant or grow very slowly.Source: §1 · p. 2
• Two alternative truncation algorithms have the same consistency behavior, distinct from the common top-k-eigenvector approach, when the k-means step is isometry invariant.The proposed third alternative combines benefits of the common approach and a denoising variant while improving computational complexity.Source: §1 · p. 2
• The results extend to general sub-Gaussian biclustering and inhomogeneous random graphs with approximate clusters, including graphon clustering.The paper also discusses bipartite-specific settings, including clusters on only one side or more clusters on one side than the rank of the expected adjacency matrix.Source: §1 · pp. 2–3
• SC-RR and SC-RRE consistency results can be expressed using SBM mean parameters, while SC-1 consistency is expressed differently.The paper presents SC-RRE as a more computationally efficient alternative with the same performance as SC-RR under a suitable k-means step.Source: §1 · p. 3

1.1 Notation

• An orthogonal matrix has orthonormal columns, so ZᵀZ = I_k for Z in O_n×k.The notation also treats matrices with fewer columns than rows as orthogonal.Source: §1.1 · p. 3
• A membership matrix encodes each node’s cluster label, and misclassification compares labels after the best permutation of cluster names.The paper also defines cluster-specific and maximum cluster-specific misclassification rates.Source: §1.1 · p. 4

2 Stochastic Block Model

• The bipartite SBM allows a not necessarily symmetric bi-adjacency matrix with independent Bernoulli entries and separate membership matrices for the two sides.The model also includes the symmetric SBM and directed SBM as special cases under additional restrictions.Source: §2 · p. 4
• The mean matrix P has rank at most k = min{k1, k2}, although either side may have as many as a constant fraction of its nodes in distinct communities.Cluster-size matrices record the number of nodes in each community on each side.Source: §2 · p. 5
• Under the stated sparse-graph scaling, stable normalized cluster proportions and Ψ keep B̄ stable while entries of B vanish as dimensions grow.In the symmetric case, average expected degree tracks Ψ, and slowly growing Ψ corresponds to sparse networks.Source: §2 · pp. 5–6
• The factorization P = Z̄1 B̄ Z̄2ᵀ yields a reduced SVD through the reduced SVD of B̄ and orthonormal normalized membership matrices.Reduced SVD removes columns for zero singular values and remains exact; truncated SVD additionally removes small nonzero singular values and is an approximation.Source: §2 · p. 5
• For bipartite networks, expected density is assessed using n = √(n1n2), and slowly growing ||Ψ||∞ relative to n corresponds to sparsity.The passage identifies the bipartite analogue of expected average degree through the cluster proportions and Ψ.Source: §2 · p. 6

3.1 Analysis sketch

• The analysis proceeds from a regularized adjacency matrix concentrating around its mean, through spectral perturbation, to k-means; orthogonal alignment does not affect row-wise clustering.The prototype consistency result requires a suitable cluster-balance condition and a k-means algorithm satisfying local quadratic continuity (LQC).Source: §3.1 · pp. 6–7
• When β1 ≍ 1 and σk ≍ d, the prototype bound gives Mis(K(Ẑ1), Z̄1) = O(d^-1), which vanishes as average degree d grows.The result is stated for the usual truncation and a k-means step satisfying local quadratic continuity, under the SBM assumptions and concentration bound.Source: §3.1 · pp. 7–8

3.2 SV truncation (Step 2)

• Symmetric dilation converts the bipartite matrix problem to a symmetric one, with a 2σk spectral gap that supports the usual truncation deviation bound up to orthogonal alignment.For symmetric SBMs, the results apply when eigenvalues are ordered by absolute value; selecting the top signed eigenvalues can behave differently.Source: §3.2 · p. 10

3.3 k-means algorithms (Step 3)

• K-means matrices encode both cluster labels and centers, and approximate k-means solutions inherit small misclassification error when the target clusters are separated and the input is close.The paper establishes LQC for constant-factor approximate k-means under stated cluster and separation conditions.Source: §3.3 · pp. 11–13
• Constant-factor k-means approximations satisfy LQC and are polynomial-time computable, while Lloyd’s kmeans++ gives a κ ≲log k approximation.The analysis draws on and establishes LQC uniformly for any input matrix rather than analyzing specific algorithms; Algorithm 6 also satisfies LQC nonprobabilistically. The approximation guarantees hold with constant probability, so downstream “w.h.p.” means high constant probability; random-initialized Lloyd can achieve near-optimal misclassification in certain models [LZ16].Source: §3.3 · p. 13

4 Regularization and concentration

• Theorem 2 extends regularized-adjacency concentration to the rectangular setting without requiring expected degree to exceed a logarithmic threshold.Its regularization requires a known upper bound on the maximum expected degree.Source: §4 · p. 14

4.1 Data-driven regularization

• Algorithm 1 estimates degree thresholds from observed row and column degrees, reducing degrees roughly above D(α) with τ = 3.The stated regularization can reduce rows and columns in either order.Source: §4.1 · p. 15
• The data-driven guarantee relies on regularity conditions under which degree order statistics proxy the maximum and average degrees.The paper notes that balanced clusters satisfy the stated cluster-size condition with β = 1; in a specified regime, d may grow slower than n1 and faster than max{k1, k2}.Source: §4.1 · pp. 15–16
• Under assumption (A2), Algorithm 1 achieves the same concentration guarantee as Theorem 2 without knowing the upper bound d.The paper characterizes (A2) as mild and states that the guarantee holds with τ = 3.Source: §4.1 · pp. 16–17

5 Consistency results

• The SC-1 bound is vacuous when B is rank deficient, whereas a reduced-rank variant can resolve this issue by clustering the rank-k approximation.Source: §5.1 · p. 17

5.1 Reduced-rank SC

• For the balanced planted partition model, SC-1 and SC-RR both achieve average misclassification O(k^2a/(a-b)^2) when k^3a/(a-b)^2 is sufficiently small.Source: §5.1 · p. 19
• SC-RR can have a clear advantage over SC-1 when the two smallest nonzero singular values are widely separated; the figure shows improvement across a range of b.As the relevant diagonal entries become closer, the figure reports similar performance for both algorithms.Source: §5.1 · pp. 20–21, Figure 1 · p. 20
• For rank-one connectivity, SC-RR remains consistent under conditions including distinct coordinates of u, similarly growing entries of u and v, and k = O(1).Source: §5.1 · p. 21

5.2 Efficient reduced-rank SC

• SC-RRE matches SC-RR's misclassification performance while running k-means in R^k rather than R^n.The paper also reports that SC-1 and SC-RRE require fewer assumptions than the compared existing works.Source: §5.2 · pp. 21–22

5.3 Results in terms of mean parameters

• The section gives consistency results in terms of SBM row-mean parameters, and the same result holds for SC-RRE when its k-means algorithm is isometry-invariant.Source: §5.3 · pp. 22–23

6.1 Clusters on one side only

• When only one side has clusters, setting k1 = n1 places the problem within the SBM framework, so the paper’s consistency results continue to hold.Source: §6.1 · p. 23

6.2 More clusters than rank

• For k1 > k, SC-1 incurs an asymmetry factor k/(k1ρ1), while SC-RR(E) retains the same consistency theorems as when k1 = k.The paper notes that the larger-cluster case is reflected implicitly through reduced Ψ²_{1,∧} and eΨ²_{1,∧}.Source: §6.2 · pp. 23–24

6.3 General sub-Gaussian case

• For general sub-Gaussian similarity matrices, Algorithm 5 is consistent in the typical fixed-cluster, fixed-separation case when σ²/n̄ = o(1).The entries need only be independent and sub-Gaussian; they need not share a distribution or sub-Gaussian norm within blocks.Source: §6.3 · pp. 24–25

6.4 Inhomogeneous random graphs

• For an inhomogeneous random graph whose mean is approximately block-constant and meets the stated deviation condition, the paper’s consistency results extend using the corresponding approximate-SBM quantities.Proposition 2 supplies the concentration bound around the approximate block mean needed for this extension.Source: §6.4 · pp. 25–26

6.4.1 Graphon clustering

• In graphon clustering, the underlying clusters are identifiable and consistently recoverable under the stated approximation condition, without a smoothness assumption or a lower bound on d.For typical cases, the SC-1 misclassification rate is at most O(d/σ²_k), and when σ²_k ≍ d² this is O(1/d).Source: §6.4.1 · p. 27

• The simulations vary n0 with k1 = 3 and k2 = 4, and compare τ = 1, 1.2, 1.4, and ∞, where ∞ means no regularization.Clustering performance is measured by NMI, which lies in [0, 1] and increases monotonically with clustering accuracy.Source: §7 · p. 28
• Regularization considerably boosts SC-RRE clustering performance on the simulated SBM, as measured by NMI.Source: §7 · p. 28
• The relative operator norm error is improved by regularization, and data-driven truncation closely follows oracle truncation across τ values.The concentration comparison uses n0 = 500 and averages three replicates.Source: §7 · p. 29

• The proof translates the operator-norm bound on spectral projections into a Frobenius bound, using the rank bound on their difference to obtain √k scaling.Source: §A.1 · p. 32
• An orthogonal alignment of the estimated and population spectral bases is bounded by the Frobenius distance between their projection operators.Source: §A.1 · p. 32
• Combining the projection comparison with the earlier operator-norm control yields the desired result.Source: §A.1 · pp. 32–33

• The lower-tail argument controls nodes with degree below dmax/2 using q = exp(−dmax/10), under a sufficiently large dmax condition.Source: §A.2 · p. 33
• For the upper tail, the proof bounds indicators for degrees exceeding 3dmax/2 using the same exponential probability bound q.Source: §A.2 · p. 34
• The remaining terms are bounded exponentially, with the proof reporting bounds e^(−n1/80) and e^(−n1/5).Source: §A.2 · p. 34

A.3 Proofs of Section 3.3

• If the embedding error is at most (1 + κ)ε, Corollary 1 applies to the κ-approximate k-means output.This follows by applying Proposition 1 with (1 + κ)ε in place of ε.Source: §A.3 · p. 36
• Each true cluster has a nonempty set of points close to its center, and these sets receive distinct labels under the estimated clustering.The proof uses the separation condition to rule out a shared label across different sets, then uses the k-label constraint to ensure each set has one label.Source: §A.3 · p. 36
• Within each close-point set, the estimated labels agree with the true clustering, so misclassified points in a cluster lie among its remaining points.The clusterwise misclassification rate is bounded by |S_r|/|C_r|.Source: §A.3 · p. 36

A.4 Proofs of Section 5

• Rank-k truncation loses at most a constant in operator-norm deviation while improving the Frobenius-norm deviation bound.The proof contrasts the full-rank matrix's dimension-dependent Frobenius bound with the truncated matrix's rank-k structure.Source: §A.4 · p. 37
• Theorem 4 obtains a misclassification bound of 4(1 + κ)^2ε^2/(n1δ^2(P)) under assumption (37).The proof uses ε^2 = 8C^2kd and checks the condition needed to apply Corollary 1.Source: §A.4 · pp. 36–37
• Theorem 6 transfers the clustering result to the k-truncated SVD because the compared embeddings have identical pairwise row distances.The orthogonal factor preserves distances, giving zero misclassification distance between the two k-means matrices; Theorem 5 then supplies the result.Source: §A.4 · pp. 37–38
• Corollary 4 verifies that its stated condition suffices for (37), allowing the same k-means bound with c = 4(1 + κ)^2.The proof then follows the argument for Theorem 1.Source: §A.4 · pp. 36, 38

A.5 Proof of Theorem 7

• Theorem 7 verifies the Corollary 1 condition for its embedding so that the κ-approximate k-means operator satisfies bound (10).The proof uses c = 4(1 + κ)^2 for the k-means step.Source: §A.5 · pp. 38–39

A.6 Proof of Theorem 8

• With probability at least 1 − 2e^−(n1+n2), the sub-Gaussian matrix deviation is at most 2Cσ(√n1 + √n2).This supplies the concentration bound used for Theorem 8.Source: §A.6 · p. 39
• Theorem 8 follows by applying Theorem 5 with d bounded by 4σ^2(n1 + n2) and replacing the stated Ψ quantities with the corresponding B quantities.The proof uses the sub-Gaussian concentration result to make these substitutions.Source: §A.6 · p. 39

A.7 Proofs of Section 6.4

• The Section 6.4 proof bounds its first term using Theorem 2 and concludes with assumption (52).The proof identifies d′ = d = n2∥P∥∞ for that bound.Source: §A.7 · p. 39

B Alternative algorithm for the k-means step

• Algorithm 6 recursively forms clusters from pairwise distances and a radius, without necessarily optimizing the k-means objective.The stated guarantee also applies to data points in any metric space.Source: B Alternative algorithm for the… · p. 40
• For ρ ≥ αδ∧ with α < 1/3, Algorithm 6 bounds misclassification by cαε^2/(nδ∧^2), where cα = 8/α^2.With a suitable radius, the algorithm satisfies the required k-means-step bound (10).Source: B Alternative algorithm for the… · pp. 40–41
• A cluster becomes depleted when a selected radius-neighborhood covers it or a large fraction of it; the size conditions keep depleted clusters from being revisited while intact clusters remain.This argument underlies the procedure's progression through the k clusters.Source: B Alternative algorithm for the… · p. 42

C Auxiliary lemmas

• For orthonormal matrices Z and Y, the squared Frobenius distance between their projection operators equals k minus the squared Frobenius norm of Z^T Y.The lemma expresses projection distance through the singular values of Z^T Y.Source: C Auxiliary lemmas · p. 43