Landmark selection for spectral clustering based on Weighted PageRank

• Published in: Future generation computer systems 2017-03, Vol.68, p.465-472
• Main Authors: Rafailidis, D., Constantinou, E., Manolopoulos, Y.
• Format: Article
• Language: English
• Subjects: Sparse coding; Spectral clustering
• ISSN: 0167-739X; 1872-7115
• DOI: 10.1016/j.future.2016.03.006

Spectral clustering methods have various real-world applications, such as face recognition, community detection, protein sequences clustering etc. Although spectral clustering methods can detect arbitrary shaped clusters, resulting thus in high clustering accuracy, the heavy computational cost limits their scalability. In this paper, we propose an accelerated spectral clustering method based on landmark selection. According to the Weighted PageRank algorithm, the most important nodes of the data affinity graph are selected as landmarks. Furthermore, the selected landmarks are provided to a landmark spectral clustering technique to achieve scalable and accurate clustering. In our experiments, by using two benchmark face and shape image data sets, we examine several landmark selection strategies for scalable spectral clustering that either ignore or consider the topological properties of the data in the affinity graph. Also, we show that the proposed method outperforms baseline and accelerated spectral clustering methods, in terms of computational cost and clustering accuracy, respectively. Finally, we provide future directions in spectral clustering. •We select representative landmarks with weighted PageRank for spectral clustering.•Scalability in spectral clustering is ensured by following a landmark strategy.•We examine several landmark selection strategies for spectral clustering.•We experimentally show the superiority of the proposed method over competitors.•We provide future directions in spectral clustering.