Incremental Method for Spectral Clustering of Increasing Orders

Abstract

The smallest eigenvalues and the associated eigenvectors (i.e., eigenpairs) of a graph Laplacian matrix have been widely used for spectral clustering and community detection. However, in real-life applications the number of clusters or communities (say, $K$) is generally unknown a-priori. Consequently, the majority of the existing methods either choose $K$ heuristically or they repeat the clustering method with different choices of $K$ and accept the best clustering result. The first option, more often, yields suboptimal result, while the second option is computationally expensive. In this work, we propose an incremental method for constructing the eigenspectrum of the graph Laplacian matrix. This method leverages the eigenstructure of graph Laplacian matrix to obtain the $K$-th eigenpairs of the Laplacian matrix given a collection of all the $K-1$ smallest eigenpairs. Our proposed method adapts the Laplacian matrix such that the batch eigenvalue decomposition problem transforms into an efficient sequential leading eigenpair computation problem. As a practical application, we consider user-guided spectral clustering. Specifically, we demonstrate that users can utilize the proposed incremental method for effective eigenpair computation and determining the desired number of clusters based on multiple clustering metrics.

in KDD workshop on mining and learning graph, 2016 http://www.mlgworkshop.org/2016/

References in corpus (5)

• The Emerging Field of Signal Processing on Graphs: Extending High-Dimensional Data Analysis to Networks and Other Irregular Domains
• Abrupt transition in the structural formation of interconnected networks
• Deep Community Detection
• Phase Transitions in Spectral Community Detection
• A Model-Based Approach to Rounding in Spectral Clustering

Cited by in corpus (7)

• Phase Transitions and a Model Order Selection Criterion for Spectral Graph Clustering
• Multilayer Spectral Graph Clustering via Convex Layer Aggregation: Theory and Algorithms
• Dynamic Node Embeddings from Edge Streams
• Bayesian Non-Exhaustive Classification A Case Study: Online Name Disambiguation using Temporal Record Streams
• Revisiting Spectral Graph Clustering with Generative Community Models
• Leveraging Social Signal to Improve Item Recommendation for Matrix Factorization
• Incremental Eigenpair Computation for Graph Laplacian Matrices: Theory and Applications