Scalable and Robust Community Detection with Randomized Sketching
arXiv:1805.10927 · doi:10.1109/TSP.2020.2965818
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.
References in corpus (15)
- Community detection in graphs
- Finding community structure in very large networks
- Stochastic blockmodels and community structure in networks
- Community detection in networks: A user guide
- Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
- Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices
- Clustering Partially Observed Graphs via Convex Optimization
- Robust and computationally feasible community detection in the presence of arbitrary outlier nodes
- High Dimensional Low Rank plus Sparse Matrix Decomposition
- Randomized Robust Subspace Recovery for High Dimensional Data Matrices
- Identifying Outliers in Large Matrices via Randomized Adaptive Compressive Sampling
- Improved Graph Clustering
- Semidefinite Programs for Exact Recovery of a Hidden Community
- Spatial Random Sampling: A Structure-Preserving Data Sketching Tool
- Efficient Clustering with Limited Distance Information