Revisiting Spectral Graph Clustering with Generative Community Models
arXiv:1709.04594
Abstract
The methodology of community detection can be divided into two principles: imposing a network model on a given graph, or optimizing a designed objective function. The former provides guarantees on theoretical detectability but falls short when the graph is inconsistent with the underlying model. The latter is model-free but fails to provide quality assurance for the detected communities. In this paper, we propose a novel unified framework to combine the advantages of these two principles. The presented method, SGC-GEN, not only considers the detection error caused by the corresponding model mismatch to a given graph, but also yields a theoretical guarantee on community detectability by analyzing Spectral Graph Clustering (SGC) under GENerative community models (GCMs). SGC-GEN incorporates the predictability on correct community detection with a measure of community fitness to GCMs. It resembles the formulation of supervised learning problems by enabling various community detection loss functions and model mismatch metrics. We further establish a theoretical condition for correct community detection using the normalized graph Laplacian matrix under a GCM, which provides a novel data-driven loss function for SGC-GEN. In addition, we present an effective algorithm to implement SGC-GEN, and show that the computational complexity of SGC-GEN is comparable to the baseline methods. Our experiments on 18 real-world datasets demonstrate that SGC-GEN possesses superior and robust performance compared to 6 baseline methods under 7 representative clustering metrics.
Accepted by IEEE International Conference on Data Mining (ICDM) 2017 as a regular paper - full paper with supplementary material
References in corpus (24)
- Fast unfolding of communities in large networks
- Modularity and community structure in networks
- Community detection in graphs
- Fast algorithm for detecting community structure in networks
- Finding community structure in networks using the eigenvectors of matrices
- Stochastic blockmodels and community structure in networks
- Spectral redemption: clustering sparse networks
- Phase transition in the detection of modules in sparse networks
- Graph spectra and the detectability of community structure in networks
- Empirical Comparison of Algorithms for Network Community Detection
- Eigenvalue Spectra of Modular Networks
- Community detection in general stochastic block models: fundamental limits and efficient recovery algorithms
- Detectability of communities in heterogeneous networks
- Deep Community Detection
- Phase Transitions in Spectral Community Detection
- Estimating the Trace of the Matrix Inverse by Interpolating from the Diagonal of an Approximate Inverse
- Universal Phase Transition in Community Detectability under a Stochastic Block Model
- Estimating network edge probabilities by neighborhood smoothing
- Accelerated Distributed Dual Averaging over Evolving Networks of Growing Connectivity
- Bias-Variance Tradeoff of Graph Laplacian Regularizer
- Incremental Method for Spectral Clustering of Increasing Orders
- Community Detection in Degree-Corrected Block Models
- Phase Transitions and a Model Order Selection Criterion for Spectral Graph Clustering
- PRIMME_SVDS: A High-Performance Preconditioned SVD Solver for Accurate Large-Scale Computations