Scalable and Robust Community Detection With Randomized Sketching

Mostafa Rahmani, Andre Beckus, Adel Karimian, George K. AtiaIEEE TSP 2020 · OpenReview

TL;DR

This paper introduces a novel framework for community detection in large, partially observed graphs by using randomized sketching. By clustering a smaller "sketch" of the graph instead of the whole thing, they achieve significant speedups while maintaining accuracy, even for graphs with highly unbalanced cluster sizes.

What Problem Does This Paper Address?

Community detection, the task of finding groups of nodes that are more densely connected within themselves than to the rest of the graph, is crucial for understanding complex networks in fields like social science and biology. However, many existing algorithms struggle with large graphs due to high computational costs and memory requirements. Furthermore, these algorithms often fail when communities (clusters) have vastly different sizes (unbalanced graphs). This paper tackles these challenges by proposing a scalable and robust method that can handle massive graphs and unbalanced community structures.

Methods

The core idea is to reduce the computational burden by applying a clustering algorithm to a smaller, representative "sketch" of the graph, rather than the full adjacency matrix. This sketch is created using randomized node sampling. The framework consists of three main steps:

  1. Node Sampling: This is where the novelty lies. Instead of just picking nodes randomly, the authors propose three methods:
  2. Uniform Random Sampling (URS): A baseline method that samples nodes with equal probability. It offers speedups but struggles with unbalanced graphs.
  3. Sparsity-based Sampling (SbS): A new method that samples nodes with a probability inversely proportional to their degree. This intelligently oversamples nodes from smaller clusters, leading to more balanced sketches and improved performance on unbalanced data.
  4. Spatial Random Sampling (SRS): Another novel method that samples nodes based on their spatial distribution in a projected space, aiming for a balanced sketch independent of population sizes.
  5. Subgraph Clustering: The chosen clustering algorithm (here, a convex clustering algorithm based on low-rank plus sparse matrix decomposition) is applied to the smaller sketch matrix.
  6. Full Data Clustering: The clusters identified in the sketch are then used to infer the clusters in the original, full graph through a correlation-based retrieval step.

Datasets

The paper uses synthetic data generated from the Stochastic Block Model (SBM) and its variants, including a version that incorporates partial observations. They also evaluate their framework on a real-world dataset: the Political Blogs dataset.

Key Insights and Ideas

  • Sketching for Scalability: The fundamental insight is that a smaller, representative sketch of a graph can capture its essential community structure, allowing for efficient clustering without sacrificing accuracy.
  • The Power of Degree-Based Sampling (SbS): The SbS method is a significant contribution. By intelligently sampling nodes based on their degree (or rather, inversely to it), the algorithm can create more balanced sketches, which is crucial for accurately detecting small communities in otherwise unbalanced graphs. This is a clever way to overcome a major limitation of many existing methods.
  • Spatial Sampling (SRS) for Independence: SRS offers an alternative approach to achieving balanced sketches, demonstrating that sampling strategies can be designed to be less dependent on the actual sizes of the communities.
  • Improved Phase Transitions: The proposed framework, especially with SbS and SRS, pushes the boundaries of what's achievable in community detection, allowing for successful clustering with smaller minimum cluster sizes and improved computational complexity, making it nearly "dimension-free" in certain regimes.

Key Results

  • Significant Speedups: The randomized sketching approach offers substantial computational speedups compared to full-scale clustering algorithms. For balanced graphs, URS can reduce runtime from seconds or minutes to milliseconds.
  • Robustness to Unbalanced Data: SbS and SRS demonstrate superior performance on unbalanced graphs, achieving high success rates even when existing full-scale algorithms fail. For instance, with N=5000 and unbalanced clusters, SbS achieved accurate clustering with only 200 samples (4% of total nodes) when the minimum cluster size was 200.
  • Competitive Accuracy: The proposed framework, particularly with SbS and SRS, achieves accuracy comparable to or even exceeding state-of-the-art methods, especially in challenging scenarios like low inter-cluster connectivity or unbalanced data.
  • Theoretical Guarantees: The paper provides rigorous theoretical analysis and sufficient conditions for exact recovery, demonstrating the provable scalability and robustness of their approach.

Limitations and Future Work

  • Algorithm Dependence: The performance of the framework is still dependent on the quality of the clustering algorithm used on the sketch. While they use a convex clustering method, other algorithms might yield different results.
  • Real-world Data Challenges: While the framework shows promise on real-world data, it acknowledges that real-world graphs with skewed degree distributions (like those captured by the Degree Corrected SBM) require heuristic modifications to sampling methods like SbS.
  • Future Work: The authors suggest exploring other sampling techniques and clustering algorithms within their framework. They also highlight the potential for further tightening theoretical bounds and investigating the performance on even more complex graph models.

Summary updated

Abstract

This article explores and analyzes the unsupervised clustering of large partially observed graphs. We propose a scalable and provable randomized framework for clustering graphs generated from the stochastic block model. The clustering is first applied to a sub-matrix of the graph's adjacency matrix associated with a reduced graph sketch constructed using random sampling. Then, the clusters of the full graph are inferred based on the clusters extracted from the sketch using a correlation-based retrieval step. Uniform random node sampling is shown to improve the computational complexity over clustering of the full graph when the cluster sizes are balanced. A new random degree-based node sampling algorithm is presented which significantly improves upon the performance of the clustering algorithm even when clusters are unbalanced. This framework improves the phase transitions for matrix-decomposition-based clustering with regard to computational complexity and minimum cluster size, which are shown to be nearly dimension-free in the low inter-cluster connectivity regime. A third sampling technique is shown to improve balance by randomly sampling nodes based on spatial distribution. We provide analysis and numerical results using a convex clustering algorithm based on matrix completion.
BibTeX
@article{rahmani2020scalable,
  author = {Mostafa Rahmani and Andre Beckus and Adel Karimian and George K. Atia},
  title = {{Scalable and Robust Community Detection With Randomized Sketching}},
  journal = {IEEE Trans. Signal Process.},
  year = {2020},
  url = {https://openreview.net/forum?id=wWLYPPhCGJ},
}
Figure