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

arXiv: https://arxiv.org/abs/1803.04547 · HTML: https://mlsanity.com/paper/1803.04547/

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Mar 2018.

## Built on by (most cited first, 20 of 20)

- [FedGCN: Convergence-Communication Tradeoffs in Federated Training of Graph Convolutional Networks](https://mlsanity.com/paper/2201.12433/) (2022)
- [Leave-one-out Singular Subspace Perturbation Analysis for Spectral Clustering](https://mlsanity.com/paper/2205.14855/) (2022)
- [Community detection for weighted bipartite networks](https://mlsanity.com/paper/2109.10319/) (2021)
- [Learning Low-Dimensional Nonlinear Structures from High-Dimensional Noisy Data: An Integral Operator Approach](https://mlsanity.com/paper/2203.00126/) (2022)
- [Bipartite mixed membership distribution-free model. A novel model for community detection in overlapping bipartite weighted networks](https://mlsanity.com/paper/2211.00912/) (2022)
- [A useful criterion on studying consistent estimation in community detection](https://mlsanity.com/paper/2109.14950/) (2021)
- [Spectral learning of multivariate extremes](https://mlsanity.com/paper/2111.07799/) (2021)
- [Directed mixed membership stochastic blockmodel](https://mlsanity.com/paper/2101.02307/) (2021)
- [A simpler spectral approach for clustering in directed networks](https://mlsanity.com/paper/2102.03188/) (2021)
- [Mixed membership distribution-free model](https://mlsanity.com/paper/2112.04389/) (2021)
- [Graphon Estimation in bipartite graphs with observable edge labels and unobservable node labels](https://mlsanity.com/paper/2304.03590/) (2023)
- [Sparse Partial Least Squares for Coarse Noisy Graph Alignment](https://mlsanity.com/paper/2104.02810/) (2021)
- [A graph representation based on fluid diffusion model for data analysis: theoretical aspects and enhanced community detection](https://mlsanity.com/paper/2112.04388/) (2021)
- [Latent class analysis by regularized spectral clustering](https://mlsanity.com/paper/2310.18727/) (2023)
- [Overlapping and nonoverlapping models](https://mlsanity.com/paper/2111.01392/) (2021)
- [Latent class analysis with weighted responses](https://mlsanity.com/paper/2310.10984/) (2023)
- [Latent class analysis for multi-layer categorical data](https://mlsanity.com/paper/2408.05535/) (2024)
- [Variational Estimators for Node Popularity Models](https://mlsanity.com/paper/2511.17783/) (2025)
- [How many asymmetric communities are there in multi-layer directed networks?](https://mlsanity.com/paper/2602.21569/) (2026)
- [Exact Community Recovery in Bipartite Networks](https://mlsanity.com/paper/2609.12445/) (2026)

## Abstract (arXiv)

We consider spectral clustering algorithms for community detection under a general bipartite stochastic block model (SBM). A modern spectral clustering algorithm consists of three steps: (1) regularization of an appropriate adjacency or Laplacian matrix (2) a form of spectral truncation and (3) a k-means type algorithm in the reduced spectral domain. We focus on the adjacency-based spectral clustering and for the first step, propose a new data-driven regularization that can restore the concentration of the adjacency matrix even for the sparse networks. This result is based on recent work on regularization of random binary matrices, but avoids using unknown population level parameters, and instead estimates the necessary quantities from the data. We also propose and study a novel variation of the spectral truncation step and show how this variation changes the nature of the misclassification rate in a general SBM. We then show how the consistency results can be extended to models beyond SBMs, such as inhomogeneous random graph models with approximate clusters, including a graphon clustering problem, as well as general sub-Gaussian biclustering. A theme of the paper is providing a better understanding of the analysis of spectral methods for community detection and establishing consistency results, under fairly general clustering models and for a wide regime of degree growths, including sparse cases where the average expected degree grows arbitrarily slowly.