PaperlayerView exact revision on arXiv

Source-linked AI summary

Exact Community Recovery in Bipartite Networks

Huan Qing

arXiv:2609.12445v1cs.SImath.STstat.MLstat.TH

TL;DR

Exact community recovery in bipartite networks remains an open question in important ScBM settings, especially with degree heterogeneity and growing or unbalanced communities. The paper uses diagonal-deleted Gram-matrix spectral clustering, with row normalization for DCScBM, and proves exact-recovery guarantees under stated conditions. These guarantees cover growing community counts and characterize trade-offs involving sparsity and balance.

  • Problem

    Whether algorithms can achieve exact recovery in ScBM and DCScBM remains unclear, despite prior results with narrower assumptions and scopes.

    Source: §1 · p. 2

  • Method

    The paper applies spectral clustering to a diagonal-deleted Gram matrix and uses row normalization in the degree-corrected model.

    Source: §1 · p. 3, §3.1 · p. 12

  • Results

    The methods provide exact-recovery guarantees for ScBM and DCScBM, including growing community counts and conditions that characterize sparsity and balance trade-offs.

    Source: §1 · p. 3, §2.2 · p. 8

  • Takeaways & Limitations

    The guarantees specify conditions for exact recovery in both models, with the DCScBM results reducing to ScBM when degree-correction parameters are equal.

    Source: §1 · p. 3

    The current proof technique does not establish a guarantee in the sparse regime discussed, where its sufficient perturbation conditions fail.

    Source: §2.3 · p. 10

Abstract

from arXiv · show

Community detection in bipartite networks is a fundamental problem in modern data analysis, with applications in recommendation systems, biological networks, and social network analysis. Unlike conventional unipartite graphs, bipartite networks consist of two distinct types of nodes with edges only connecting across types, so recovering latent communities requires estimating labels on the two node types. The stochastic co-blockmodel is a classical probabilistic framework for such networks, yet theoretical guarantees for exact community recovery in this setting remain limited, especially when the number of communities grows, the community sizes are unbalanced, or the degrees are heterogeneous. In this work, we prove that a simple spectral clustering algorithm based on the diagonal-deleted Gram matrix achieves exact recovery with high probability under mild conditions on sparsity, community balance, and the number of clusters. We further extend the result to the degree-corrected stochastic co-blockmodel, where each node carries its own degree heterogeneity parameter, and show that a row-normalized version of the same algorithm maintains the exact recovery guarantee. Extensive experiments validate our theoretical findings.

1. Introduction

Exact community recovery in bipartite networks remained unclear, particularly for degree-corrected models and mild conditions on sparsity, community balance, and cluster count. The paper develops spectral methods that provide exact recovery guarantees for the stochastic co-blockmodel and its degree-corrected extension.

1. Introduction

  • Bipartite networks have two distinct node types and cross-type edges; community detection partitions both sides into latent groups with similar connection patterns.The groups can reveal functional structure and support further modeling and inference.Source: §1 · pp. 1–2
  • ScBM models edge probabilities through the two nodes’ community memberships, while DCScBM adds individual node scale parameters to allow heterogeneous degrees..Source: §1 · p. 2
  • Although prior work established consistency and some exact-recovery results for ScBM, exact recovery remained unclear for DCScBM and under mild conditions on community count, sparsity, and balance.Earlier guarantees had narrower scopes, including recovery of one side or approximately balanced communities.Source: §1 · pp. 2–3
  • The proposed spectral methods establish exact recovery for ScBM and DCScBM, with conditions allowing growing community counts and characterizing trade-offs among sparsity, balance, and model parameters.For DCScBM, a row-normalized variant accommodates degree heterogeneity; equal degree-correction parameters reduce the guarantees to ScBM.Source: §1 · p. 3

2. Stochastic Co-Blockmodels

This section develops SCDD for stochastic co-blockmodels and gives conditions for exact recovery, including when community sizes are unbalanced or the number of communities grows. It also derives simpler balanced-regime implications and identifies settings beyond the current guarantee.

2.1. Model and Algorithm

  • SCDD removes the diagonal of the sample Gram matrix, then clusters rows of its leading eigenvectors; when Ky = Kz, the same procedure recovers column communities.The diagonal deletion removes noise-variance bias, and the population matrix differs from ΩΩ⊤ only by a spectrally negligible diagonal bias under the theorem conditions.Source: §2.1 · pp. 5–6

2.2. Exact Recovery Guarantee

  • Under explicit model and incoherence conditions, SCDD recovers the true row communities exactly with probability at least 1 − O(N^-10).The guarantee permits a growing number of communities and unbalanced community sizes.Source: §2.2 · pp. 7–8
  • When Ky < Kz, the row communities remain the exact-recovery target because the observed signal provides only a Ky-dimensional projection of the column structure.The model parameters remain identifiable, but exact recovery of all column labels is impossible in this case.Source: §2.1 · p. 4, §2.2 · p. 8

2.3. Implications in the Balanced Regime

  • In the dense regime, when ρ = O(1), exact row recovery holds provided the stated condition is met; under that same condition, column recovery also holds whenever Ky = Kz.Exact recovery is guaranteed when K = o(log^(ε/2) N), even when the average degree grows only polylogarithmically faster than the logarithmic order log N.Source: §2.3 · pp. 9–10
  • In the balanced regime, the nine theorem conditions reduce to two inequalities trading off community growth, network size, and sparsity.When the stated balanced-setting quantities are O(1), exact recovery is guaranteed if both inequalities hold.Source: §2.3 · pp. 9–10
  • The stated sufficient conditions do not cover the sparse regime ρ = c log N/n, where condition (9) fails.The authors attribute this boundary to the current perturbation analysis, not necessarily to an algorithmic limitation.Source: §2.3 · pp. 9–10

3. Degree-Corrected Stochastic Co-Blockmodels

The paper extends spectral co-clustering to degree-corrected bipartite networks by row-normalizing singular vectors before clustering. Under stated conditions, the method achieves exact row recovery, with balanced-regime scaling unchanged apart from constants for degree heterogeneity and minimum degree.

3. Degree-Corrected Stochastic Co-Blockmodels

  • DCScBM assigns nodes individual connectivity scales, while ηy and ηz summarize the spread of degree parameters on each side.Source: §3 · p. 11, §3.1 · p. 12

3.1. Model and Algorithm

  • NSCDD removes the Gram matrix diagonal bias, then row-normalizes estimated singular vectors and clusters their rows with k-means.The row-normalization is motivated by the result that normalized singular-vector rows are constant within communities.Source: §3.1 · p. 12

3.2. Theoretical Guarantees

  • Under Theorem 2’s conditions, NSCDD exactly recovers row labels with probability at least 1−O(N^-10).Source: §3.2 · p. 13
  • Theorem 2 conditions jointly constrain sparsity, degree heterogeneity, community balance, and cluster count, with each of six nonredundant assumptions controlling a separate proof error term.For ρ = c log N/n, the sufficient conditions fail, so the theorem does not guarantee exact recovery.Source: §3.2 · pp. 13–14
  • When degree parameters are equal, DCScBM reduces to ScBM and Theorem 2 reduces exactly to Theorem 1.Source: §3.2 · p. 13
  • When Ky = Kz, the theorem also gives exact column recovery under conditions with the row and column roles interchanged.Source: §3.2 · p. 13
  • In balanced settings, degree correction leaves the fundamental exact-recovery scaling unchanged; heterogeneity parameters and minimum degree affect only constants.Source: §3.2 · p. 14

4. Numerical Experiments

The experiments evaluate exact recovery of both node types across ScBM and DCScBM settings, including changes in community count, sparsity, network size, and balance. They compare the proposed methods with spectral baselines and report recovery thresholds consistent with the theoretical conditions.

4. Numerical Experiments

  • Across 100 data sets per configuration, exact recovery means perfect labels on both sides; under the balanced setting, the theorems reduce to two dominant requirements, with condition (20) governing phase transitions.The experiments choose n and K so condition (19) is satisfied and focus on condition (20).Source: §4 · pp. 14–15

4.1. Data Generation and Competing Methods

  • The experiments use a bounded, full-rank, non-symmetric connectivity matrix; DCScBM adds node-specific scales, and the proposed algorithms are compared with four representative spectral baselines.BiSC is the primary ScBM baseline; DI-SIM, D-SCORE, and nBiSC are primary DCScBM baselines.Source: §4.1 · pp. 15–16

4.2. Experimental Setup

  • ScBM methods attain perfect recovery for K≤7, with only marginal decline at K=8; all DCScBM algorithms reach 100% for K≤4 before substantial drops at K≥5.The paper attributes the earlier DCScBM transition to its weaker effective signal, θmin = ρ/9, and says the threshold shift matches the theoretical condition.Source: §4.2 · p. 16, Figure 1 · p. 17
  • All ScBM methods recover perfectly at ρ≥0.20, versus ρ≥0.35 for every DCScBM algorithm; performance falls slightly short at ρ=0.15 and ρ=0.30, respectively.The paper links the higher DCScBM threshold to its weaker effective signal, θmin = ρ/9.Source: §4.2 · pp. 16–17, Figure 2 · p. 17
  • ScBM methods achieve perfect recovery for n≥300, whereas DCScBM algorithms do so for n≥700; both fall short at the preceding tested sizes.At n=200, ScBM recovery is very close to 100%; at n=600, DCScBM approaches exact recovery without reaching it.Source: §4.2 · pp. 17–18, Figure 3 · p. 18
  • In ScBM, all methods recover perfectly for β≥0.6; in DCScBM, NSCDD, DI-SIM, and nBiSC do so for β≥0.5, while SCDD, D-SCORE, and BiSC require larger β.The selected DCScBM methods are near-perfect but not exact at β=0.4; all ScBM methods are close to 100% but not exact at β=0.5.Source: §4.2 · pp. 18–19, Figure 4 · p. 19

5. Conclusion

The paper concludes that diagonal-deleted Gram-matrix spectral methods, with row normalization for DCScBM, have exact recovery guarantees under explicit conditions. It also identifies sparse regimes and several network settings as unresolved extensions.

5. Conclusion

  • SCDD and NSCDD use a diagonal-deleted Gram matrix, leading eigenvectors, and k-means; row normalization is optional for DCScBM.The stated guarantees recover true row and column communities exactly with high probability under conditions on sparsity, community count, connectivity, and balance.Source: §5 · p. 19
  • Weighted and multi-layer bipartite networks are identified as directions for extending the analysis.The paper describes these settings as involving edge weights, multiple relations, or temporal snapshots.Source: §5 · pp. 19–20
  • The analysis requires average degree to grow at least polylogarithmically; exact recovery under sparser conditions remains unexamined.The paper says resolving sparser conditions may require a different proof technique.Source: §5 · p. 20
  • Whether Laplacian-based spectral methods can achieve exact recovery under ScBM and DCScBM remains unresolved.The paper cites the lack of diagonal deletion and dependencies from normalization as difficulties for the existing analysis.Source: §5 · p. 20

Appendix A. Technical proofs under ScBM

The proof represents the singular vectors of the expected adjacency matrix through community membership matrices, then establishes properties of the associated transformations. These structural facts support the separation argument for recovery.

Appendix A.1. Proof of Lemma 1

  • The left and right singular vectors are represented as linear combinations of the row and column membership matrices, respectively.The proof writes U = YX and V = ZW, with W having full column rank.Source: Appendix A.1 · p. 21
  • The proof establishes that X is invertible by using the determinant relation derived from the orthonormality identity.It then inverts that identity to derive a relation between X and Dy.Source: Appendix A.1 · p. 21
  • For distinct row communities, the proof evaluates the difference between their basis vectors through XX⊤ and Dy^-1, using positive diagonal entries to establish separation.The proof treats k and l as distinct indices and invokes positivity before taking square roots.Source: Appendix A.1 · p. 22

Appendix A.2. Proof of Theorem 1

The proof applies a matrix perturbation theorem to the observed bi-adjacency matrix after checking its required conditions. The resulting singular-vector proximity supports exact recovery by k-means.

Appendix A.2. Proof of Theorem 1

  • The proof applies Theorem 1 of Cai et al. (2021) to the bi-adjacency matrix as a noisy observation of Ω, verifying three conditions and Assumption 2.It identifies the dimensions, rank, and full-observation sampling parameter used in the theorem.Source: Appendix A.2 · pp. 22–23
  • The noise matrix is described as independent, zero-mean, bounded, and with variance at most ρ; model conditions are used to verify the theorem's noise bounds.The proof checks diagonal bias, quadratic noise, and linear noise terms.Source: Appendix A.2 · pp. 23–24
  • Once every estimated row is closer to its own class centroid, k-means recovers the true row labels exactly, up to label permutation.The proof notes that an orthogonal transformation only permutes labels.Source: Appendix A.2 · p. 24

Appendix A.3. Proof of Corollary 1

The column-community proof applies the row-recovery argument symmetrically to a diagonal-deleted Gram matrix, then uses centroid separation to obtain exact recovery.

Appendix A.3. Proof of Corollary 1

  • The proof applies Cai et al. (2021)'s theorem to Gz = Poff−diag(A⊤A), viewed as a noisy observation of Poff−diag(Ω⊤Ω).It verifies the theorem's conditions by interchanging the two node types and their balance parameters.Source: Appendix A.3 · p. 24
  • The left singular vectors of Ω⊤ encode the column-community structure, so the row-side argument transfers by symmetry.The proof uses Ky = Kz and swaps y with z and µ1 with µ2.Source: Appendix A.3 · p. 24
  • An eigenvector approximation error of o(δc,min), together with the nearest-centroid rule, yields exact column recovery.Here δc,min is the minimum distance between distinct column community centers.Source: Appendix A.3 · p. 24

Appendix A.4. Proof of Corollary 2

The appendix reduces the balanced-regime conditions, establishes auxiliary spectral and embedding properties under ScBM, and uses symmetry to relate row and column community embeddings.

Appendix A.4. Proof of Corollary 2

  • Under the balanced setting and O(1) regularity conditions, the nine theorem conditions reduce to K log² N = o(n) and ρn ≫ K² log N.For ρ = c log N/n, the second condition fails for growing K; for ρ = O(1), the corollary gives exact row recovery, with column recovery when Ky = Kz.Source: Appendix A.4 · pp. 24–25

Appendix A.5. Auxiliary lemmas under ScBM

  • The non-zero singular values of Ω equal ρ times those of the normalized connectivity matrix eB, so their ratio cancels the common factor ρ.The rank condition makes the Ky-th singular value the smallest positive singular value in both matrices.Source: Appendix A.5 · p. 25
  • Under the stated ScBM balance and connectivity assumptions, the incoherence parameters satisfy µ = O(1).The proof establishes upper bounds for µ0, µ1, and µ2.Source: Appendix A.5 · pp. 27–28

Appendix B.1. Proof of Lemma 2

  • For row nodes, the spectral embedding assigns each community a centroid, with distinct centroids separated by distance 2.The proof states that the column result follows by symmetry when Ky = Kz.Source: Appendix B.1 · pp. 29–30

Appendix B.2. Proof of Theorem 2

The proof controls the approximation error of the degree-corrected spectral embedding under stated conditions and uses centroid separation to establish exact row recovery.

Appendix B.2. Proof of Theorem 2

  • The proof applies Cai et al. (2021)'s theorem to A as a noisy observation of Ω = ΘyYBZ⊤Θz under DCScBM.It bounds a diagonal-bias term and a quadratic-noise term in the embedding error.Source: Appendix B.2 · pp. 30, 32, 33
  • Conditions (16), (17), and (18) imply that the right-hand sides of Equations (B.6), (B.7), and (B.8), respectively, are o(1).Source: Appendix B.2 · pp. 32–33
  • ℓ(ŷ, y) = 0 with probability at least 1 − O(N^-10), by the nearest-centroid rule.The proof first shows the embedding error is o(1) and invokes the separation of the true centroids.Source: Appendix B.2 · p. 33

Appendix B.3. Proof of Corollary 3

The corollary obtains column recovery by transposing the degree-corrected model and applying the row-recovery result.

Appendix B.3. Proof of Corollary 3

  • Transposing A swaps the row and column communities, connectivity matrix, and degree parameters.The resulting model has row communities Z and column communities Y.Source: Appendix B.3 · p. 33
  • The transposed-model algorithm forms Gz = Poff−diag(A⊤A), row-normalizes its leading eigenvectors, and applies k-means.This is the column-recovery step in Algorithm 2.Source: Appendix B.3 · p. 33
  • The theorem's conditions for the transposed model yield exact recovery of the column labels.Source: Appendix B.3 · p. 33

Appendix B.4. Proof of Corollary 4

The Corollary 4 proof reduces its recovery conditions to two asymptotic requirements. The DCScBM auxiliary lemmas establish structural and conditioning bounds used in the analysis.

Appendix B.4. Proof of Corollary 4

  • The corollary’s proof yields K log^2 N = o(n) and θ_min n ≫ K^2 log N, with sparse and dense regimes following as in Corollary 2.Source: Appendix B.4 · p. 33

Appendix B.5. Auxiliary lemmas under DCScBMs

  • Since eY and eZ have orthonormal columns, Ω and eB have the same nonzero singular values, so κΩ = κeB.Source: Appendix B.5 · p. 34
  • The rank condition rank(B) = Ky implies rank(Ω) = Ky and col(Ω) = col(ΘyY) = col(eU), whose columns are orthonormal.Source: Appendix B.5 · p. 35
  • Under the stated DCScBM bounds, Lemma 11 gives μ = O(1).Source: Appendix B.5 · p. 37
Loading 2609.12445v1…