Large Scale Spectral Clustering with Landmark-Based Representation

By Xinlei Chen, Deng Cai. 2011

412 citations recorded by the source corpus.

Spectral clustering is one of the most popular clustering approaches. Despite its good performance, it is limited in its applicability to large-scale problems due to its high computational complexity. Recently, many approaches have been proposed to accelerate the spectral clustering. Unfortunately, these methods usually sacrifice quite a lot information of the original data, thus result in a degradation of performance. In this paper, we propose a novel approach, called Landmark-based Spectral Clustering (LSC), for large scale clustering problems. Specifically, we select $p\ (\ll n)$ representative data points as the landmarks and represent the original data points as the linear combinations of these landmarks. The spectral embedding of the data can then be efficiently computed with the landmark-based representation. The proposed algorithm scales linearly with the problem size. Extensive experiments show the effectiveness and efficiency of our approach comparing to the state-of-the-art methods.

Subfields: Computer Vision and Pattern Recognition, Media Technology, Urban Studies

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Vision and Pattern Recognition

In Media Technology

In Urban Studies

Citations in the corpus

Learning to cluster in order to Transfer across domains and tasks (2017, methodology): “Since the number of pairs is high and it is not feasible to feed them into other constrained clustering algorithms, we compare CCN with K-means, LSC(Chen & Cai, 2011), and LPNMF (Cai et al., 2009).”
Joint Unsupervised Learning of Deep Representations and Image Clusters (2016, methodology): “We compare our approach with 12 clustering algorithms, including K-means [36], NJW spectral clustering (SCNJW) [40], self-tuning spectral clustering (SC-ST)[61], large-scale spectral clustering (SC-LS) [3], agglomerative clustering with average linkage (AC-Link)[24], Zeta function based agglomerativ”
Deep Clustering via Joint Convolutional Autoencoder Embedding and Relative Entropy Minimization (2017, methodology): “Alternative Models : We compare our clustering model, DEPICT , with several baseline and state-of-the-art clustering algorithms, including K -means , normalized cuts ( N-Cuts ) [41], self-tuning spectral clustering ( SC-ST ) [64], large-scale spectral clustering ( SC-LS ) [6], graph degree linkage-b”
Spectral Graph Reduction for Efficient Image and Streaming Video Segmentation (2014, background): “Elsewhere, [30, 5] approximate the graph by representative points (aka landmarks).”
Efficient kNN classification algorithm for big data (2016, methodology): “To this end, we used the Landmark-based Spectral Clustering (LSC) [4] in this paper.”
Unsupervised Joint Mining of Deep Features and Image Labels for Large-Scale Radiology Image Categorization and Scene Recognition (2017, methodology): “We compare the LDPO scene recognition performance to those of several popular clustering methods, such as KM [57]: k-means; LSC [4]; AC [22]: Agglomerative clustering; EP [10]: Ensemble Projection + kmeans; and MDPM [34]: Midlevel Discriminative Patch Mining + kmeans.”
Scalable Multi-view Subspace Clustering with Unified Anchors (2021, background): “According to the conclusion drawn from [1, 6, 11], the left singular vector of the anchor graph Z equals to that of complete graph S = Z⊤Z.”
Large-scale Multi-view Subspace Clustering in Linear Time (2019, methodology): “In this paper, relying on proposition 1 (Chen and Cai 2011; Affeldt, Labiod, and Nadif 2019), we present an alternative approach to compute the k left singular vectors of the concatenated matrix ¯ Z ∈ R n × mv , Since mv n , using ¯ Z instead of ¯ S naturally reduces the computational cost of Q .”
Multi-class Classification without Multi-class Labels (2019, positive): “The second setting is having an unknown C , which is closer to a clustering (Cai et al., 2009) 22.2% 16.3% 0.372 0.498 LSC (Chen & Cai, 2011) 23.6% 18.0% 0.376 0.500 ITML (Davis et al., 2007) 56.7% 47.2% 0.674 0.727 SKKm (Anand et al., 2014) 62.4% 46.9% 0.770 0.781 SKLR (Amid et al., 2016) 66.9%…”
Large-Scale Multi-View Spectral Clustering via Bipartite Graph (2015, background): “2011), (Chen and Cai 2011).”
Deep Image Category Discovery using a Transferred Similarity Function (2016, methodology): “To show that positive transfer happened while transferring the similarity prediction, we compare our clustering algorithm with different state-of-the-art unsupervised clustering approaches: K-means [17], N-Cuts [22], SC-LS [3], NMF-LP [2], JULE[27] and DEC[26].”
Scalable Semi-Supervised Learning by Efficient Anchor Graph Regularization (2016, methodology): “As a result, the anchor graph model has been applied to clustering [5], [44], hashing [23], manifold ranking [43], multi-graph learning [9], and tracking [41].”
Binary Multi-View Clustering (2019, methodology): “[1], SC [2], LSC-K [10] and two existing binary clustering methods (i.”
Structured Graph Learning for Scalable Subspace Clustering: From Single View to Multiview (2021, positive): “Anchors or landmarks were previously used in scalable spectral clustering [23].”
Learning without Human Scores for Blind Image Quality Assessment (2013, methodology): “For the clustering, we use the spectrum clustering in [2], which is efficient to solve Eq.”
Linear cross-modal hashing for efficient multimedia search (2013, methodology): “It has been shown that k centroids have a strong representation power to adequately cover large-scale datasets [5].”
Residual Tuning: Toward Novel Category Discovery Without Labels (2022, positive): “The core idea for tackling NCD is learning optimal clustering objectives [31]–[36], so as to make the unlabeled images discriminative in feature space.”