The Constrained Laplacian Rank Algorithm for Graph-Based Clustering

By Feiping Nie, Xiaoqian Wang, Michael I. Jordan, Heng Huang. AAAI Conference on Artificial Intelligence, 2016

874 citations recorded by the source corpus.

Graph-based clustering methods perform clustering on a fixed input data graph. If this initial construction is of low quality then the resulting clustering may also be of low quality. Moreover, existing graph-based clustering methods require post-processing on the data graph to extract the clustering indicators. We address both of these drawbacks by allowing the data graph itself to be adjusted as part of the clustering procedure. In particular, our Constrained Laplacian Rank (CLR) method learns a graph with exactly k connected components (where k is the number of clusters). We develop two versions of this method, based upon the L1-norm and the L2-norm, which yield two new graph-based clustering objectives. We derive optimization algorithms to solve these objectives. Experimental results on synthetic datasets and real-world benchmark datasets exhibit the effectiveness of this new graph-based clustering method.

Subfields: Artificial Intelligence, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/fb25566db4ff4d676dc4aec99a0122966e3e90b0

How researchers see this paper

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

In Artificial Intelligence

1. Bing Liu
2. 刘晗
3. Xuelong Li
4. Feiping Nie
5. Xiaotong Zhang
6. Hao Wang
7. Xianchao Zhang
8. Yan Yang

In Statistical and Nonlinear Physics

1. Xuelong Li
2. Feiping Nie
3. Jing Li
4. Wei Zhu
5. Heng Huang
6. Xianchao Zhang
7. Xuemin Lin
8. Jiebo Luo

Citations in the corpus

• Saliency Detection via a Multiple Self-Weighted Graph-Based Manifold Ranking (2020, neutral): “(cid:2) The first term v d v S − A v (cid:6) 2 F is applied in order to measure the difference between S and the original affinity matrixes [46], which ensures that S is similar to A v .”
• Self-weighted Multiview Clustering with Multiple Graphs (2017, methodology): “We avert this trouble by extending an existing single graph learning approach [Nie et al., 2016b] to multiview domain.”
• Incomplete Multiview Spectral Clustering With Adaptive Graph Learning (2020, background): “The optimal solution to problem (20) is as follows [45]:”
• Parameter-Free Auto-Weighted Multiple Graph Learning: A Framework for Multiview Clustering and Semi-Supervised Classification (2016, methodology): “In this paper, a new graph construction approach introduced in [Nie et al., 2016] is adopted in our methods.”
• Deep Clustering via Joint Convolutional Autoencoder Embedding and Relative Entropy Minimization (2017, background): “There is a large number of clustering algorithms in literature, which can be grouped into different perspectives, such as hierarchical [9, 51], centroid-based [20, 3, 27], graphbased [38, 28, 48, 25], sequential (temporal) [11, 37, 66], regression model based [7, 47], and subspace clustering models ”
• Multi-Task Clustering with Model Relation Learning (2018, methodology): “…meth-ods k -means, symmetric nonnegative matrix factorization (SNMF) [Kuang et al. , 2012], constrained Laplacian rank graph-based clustering (CLR) [Nie et al. , 2016] and symmetric nonnegative matrix factorization with linear regression model (SNMF+LR), which is a single-task version of MTCMRL…”
• Multiview Spectral Clustering via Structured Low-Rank Matrix Factorization (2017, methodology): “Besides, the latest non-parametric graph construction model [ Nie et al. , 2016b ] will also be incorporated for multi-view spectral clustering.”
• Capped Lp-Norm Graph Embedding for Photo Clustering (2016, methodology): “We use the following Constrained Laplacian Rank method [13] to generate initial graph for the proposed model. min where w i is the i -th row of similarity matrix W .”
• GMC: Graph-Based Multi-View Clustering (2020, methodology): “According to [52], the initial solution to s vij in S v is shown below (See the details in Appendix B) where , and k is the number of neighbours.”
• Unsupervised Large Graph Embedding (2017, methodology): “The neighbor assignment for the i-th sample can be seen as solving following problem (Nie et al. 2016) min zTi 1=1,zi≥0 m∑ j=1 h(xi, uj)zij + γ m∑ j=1 z2ij , (16) where Z ∈ Rn×m denotes the similarity between the i-th sample and the j-th anchor, h(xi, uj) is the distance between the i-th sample and…”
• Contrastive Clustering (2021, result): “Although some promising results have been achieved recently (Nie et al. 2011; Liu et al. 2016; Nie et al. 2016; Liu, Shen, and Tsang 2017; Wang et al. 2020), most of the algorithms would produce undesirable results due to the over-high complexity in real-world datasets.”