Analysis of spectral clustering algorithms for community detection: the general bipartite setting
arXiv:1803.04547
Abstract
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.
References in corpus (15)
- Stochastic blockmodels and community structure in networks
- Spectral redemption: clustering sparse networks
- Consistency of spectral clustering
- Fast community detection by SCORE
- A General Formalism for Inhomogeneous Random Graphs
- Regularized Spectral Clustering under the Degree-Corrected Stochastic Blockmodel
- Rate-optimal graphon estimation
- Sharp nonasymptotic bounds on the norm of random matrices with independent entries
- Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices
- Network histograms and universality of blockmodel approximation
- Stochastic blockmodel approximation of a graphon: Theory and consistent estimation
- Accurate Community Detection in the Stochastic Block Model via Spectral Algorithms
- Co-clustering for directed graphs: the Stochastic co-Blockmodel and spectral algorithm Di-Sim
- Impact of regularization on Spectral Clustering
- Optimal Bipartite Network Clustering