Lune

SODA2024Top-tier venue

Detecting Hidden Communities by Power Iterations with Connections to Vanilla Spectral Algorithms

Chandra Sekhar Mukherjee, Jiapeng Zhang

Abstract

Community detection in the stochastic block model is one of the central problems of graph clustering. Since its introduction by Holland, Laskey and Leinhardt (Social Networks, 1983), many subsequent papers have made great strides in solving and understanding this model. In this setup, spectral algorithms have been one of the most widely used frameworks for the design of clustering algorithms. However, despite the long history of study, there are still unsolved challenges. One of the main open problems is the design and analysis of "simple"(vanilla) spectral algorithms, especially when the number of communities is large.

In this paper, we provide two algorithms. The first one is based on the power-iteration method. This is a simple algorithm which only compares the rows of the powered adjacency matrix. Our algorithm performs optimally (up to logarithmic factors) compared to the best known bounds in the dense graph regime by Van Vu (Combinatorics Probability and Computing, 2018). Furthermore, our algorithm is also robust to the "small cluster barrier", recovering large clusters in the presence of an arbitrary number of small clusters. Then based on a connection between the powered adjacency matrix and eigenvectors, we provide a "vanilla" spectral algorithm for large number of communities in the balanced case. This answers an open question by Van Vu (Combinatorics Probability and Computing, 2018) in the balanced case. Our methods also partially solve technical barriers discussed by Abbe, Fan, Wang and Zhong (Annals of Statistics, 2020).

In the technical side, we introduce a random partition method to analyze each entry of a powered random matrix. This method can be viewed as an eigenvector version of Wigner's trace method. Recall that Wigner's trace method links the trace of powered matrix to eigenvalues.

Our method links the whole powered matrix to the span of eigenvectors. We expect our method to have more applications in random matrix theory.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

2 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Capturing the denoising effect of PCA via compression ratio cites On the Power of SVD in the Stochastic Block Model
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers2

  1. On the Power of SVD in the Stochastic Block ModelXinyu Mao, Jiapeng ZhangNeurIPS 2023 · 1 citation
  2. Capturing the denoising effect of PCA via compression ratioChandra Sekhar Mukherjee, Nikhil Deorkar, Jiapeng ZhangNeurIPS 2024

Builds on1

  1. Recovering Unbalanced Communities in the Stochastic Block Model with Application to Clustering with a Faulty OracleChandra Sekhar Mukherjee, Pan Peng, Jiapeng ZhangNeurIPS 2023 · 8 citations

Related papers

  1. A Nearly-Linear Time Algorithm for Exact Community Recovery in Stochastic Block ModelPeng Wang, Zirui Zhou, Anthony Man-Cho SoICML 2020 · 15 citations
  2. Optimal Non-Convex Exact Recovery in Stochastic Block Model via Projected Power MethodPeng Wang, Huikang Liu, Zirui Zhou, Anthony Man-Cho SoICML 2021 · 16 citations
  3. Spectral recovery of binary censored block modelsSouvik Dhara, Julia Gaudio, Elchanan Mossel, Colin SandonSODA 2022 · 12 citations
  4. Differentially private exact recovery for stochastic block modelsDung Nguyen, Anil Kumar S. VullikantiICML 2024 · 5 citations
  5. Sparse random hypergraphs: Non-backtracking spectra and community detectionLudovic Stephan, Yizhe ZhuFOCS 2022 · 8 citations
Dusk over the sea between two cliffs drawn in fine vertical lines