Rank-constrained spectral clustering with flexible embedding

Zhihui Li, Feiping Nie, Xiaojun Chang, Liqiang Nie, Huaxiang Zhang, Yi Yang

Research output: Contribution to journalArticleResearchpeer-review

16 Citations (Scopus)

Abstract

Spectral clustering (SC) has been proven to be effective in various applications. However, the learning scheme of SC is suboptimal in that it learns the cluster indicator from a fixed graph structure, which usually requires a rounding procedure to further partition the data. Also, the obtained cluster number cannot reflect the ground truth number of connected components in the graph. To alleviate these drawbacks, we propose a rank-constrained SC with flexible embedding framework. Specifically, an adaptive probabilistic neighborhood learning process is employed to recover the block-diagonal affinity matrix of an ideal graph. Meanwhile, a flexible embedding scheme is learned to unravel the intrinsic cluster structure in low-dimensional subspace, where the irrelevant information and noise in high-dimensional data have been effectively suppressed. The proposed method is superior to previous SC methods in that: 1) the block-diagonal affinity matrix learned simultaneously with the adaptive graph construction process, more explicitly induces the cluster membership without further discretization; 2) the number of clusters is guaranteed to converge to the ground truth via a rank constraint on the Laplacian matrix; and 3) the mismatch between the embedded feature and the projected feature allows more freedom for finding the proper cluster structure in the low-dimensional subspace as well as learning the corresponding projection matrix. Experimental results on both synthetic and real-world data sets demonstrate the promising performance of the proposed algorithm.

Original languageEnglish
Article number8341858
Pages (from-to)6073-6082
Number of pages10
JournalIEEE Transactions on Neural Networks and Learning Systems
Volume29
Issue number12
DOIs
Publication statusPublished - Dec 2018
Externally publishedYes

Keywords

  • Flexible embedding
  • rank-constrained
  • spectral clustering (SC)

Cite this

Li, Zhihui ; Nie, Feiping ; Chang, Xiaojun ; Nie, Liqiang ; Zhang, Huaxiang ; Yang, Yi. / Rank-constrained spectral clustering with flexible embedding. In: IEEE Transactions on Neural Networks and Learning Systems. 2018 ; Vol. 29, No. 12. pp. 6073-6082.
@article{9595dbcf64d5490a9285913fb4f5e518,
title = "Rank-constrained spectral clustering with flexible embedding",
abstract = "Spectral clustering (SC) has been proven to be effective in various applications. However, the learning scheme of SC is suboptimal in that it learns the cluster indicator from a fixed graph structure, which usually requires a rounding procedure to further partition the data. Also, the obtained cluster number cannot reflect the ground truth number of connected components in the graph. To alleviate these drawbacks, we propose a rank-constrained SC with flexible embedding framework. Specifically, an adaptive probabilistic neighborhood learning process is employed to recover the block-diagonal affinity matrix of an ideal graph. Meanwhile, a flexible embedding scheme is learned to unravel the intrinsic cluster structure in low-dimensional subspace, where the irrelevant information and noise in high-dimensional data have been effectively suppressed. The proposed method is superior to previous SC methods in that: 1) the block-diagonal affinity matrix learned simultaneously with the adaptive graph construction process, more explicitly induces the cluster membership without further discretization; 2) the number of clusters is guaranteed to converge to the ground truth via a rank constraint on the Laplacian matrix; and 3) the mismatch between the embedded feature and the projected feature allows more freedom for finding the proper cluster structure in the low-dimensional subspace as well as learning the corresponding projection matrix. Experimental results on both synthetic and real-world data sets demonstrate the promising performance of the proposed algorithm.",
keywords = "Flexible embedding, rank-constrained, spectral clustering (SC)",
author = "Zhihui Li and Feiping Nie and Xiaojun Chang and Liqiang Nie and Huaxiang Zhang and Yi Yang",
year = "2018",
month = "12",
doi = "10.1109/TNNLS.2018.2817538",
language = "English",
volume = "29",
pages = "6073--6082",
journal = "IEEE Transactions on Neural Networks and Learning Systems",
issn = "2162-237X",
number = "12",

}

Rank-constrained spectral clustering with flexible embedding. / Li, Zhihui; Nie, Feiping; Chang, Xiaojun; Nie, Liqiang; Zhang, Huaxiang; Yang, Yi.

In: IEEE Transactions on Neural Networks and Learning Systems, Vol. 29, No. 12, 8341858, 12.2018, p. 6073-6082.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - Rank-constrained spectral clustering with flexible embedding

AU - Li, Zhihui

AU - Nie, Feiping

AU - Chang, Xiaojun

AU - Nie, Liqiang

AU - Zhang, Huaxiang

AU - Yang, Yi

PY - 2018/12

Y1 - 2018/12

N2 - Spectral clustering (SC) has been proven to be effective in various applications. However, the learning scheme of SC is suboptimal in that it learns the cluster indicator from a fixed graph structure, which usually requires a rounding procedure to further partition the data. Also, the obtained cluster number cannot reflect the ground truth number of connected components in the graph. To alleviate these drawbacks, we propose a rank-constrained SC with flexible embedding framework. Specifically, an adaptive probabilistic neighborhood learning process is employed to recover the block-diagonal affinity matrix of an ideal graph. Meanwhile, a flexible embedding scheme is learned to unravel the intrinsic cluster structure in low-dimensional subspace, where the irrelevant information and noise in high-dimensional data have been effectively suppressed. The proposed method is superior to previous SC methods in that: 1) the block-diagonal affinity matrix learned simultaneously with the adaptive graph construction process, more explicitly induces the cluster membership without further discretization; 2) the number of clusters is guaranteed to converge to the ground truth via a rank constraint on the Laplacian matrix; and 3) the mismatch between the embedded feature and the projected feature allows more freedom for finding the proper cluster structure in the low-dimensional subspace as well as learning the corresponding projection matrix. Experimental results on both synthetic and real-world data sets demonstrate the promising performance of the proposed algorithm.

AB - Spectral clustering (SC) has been proven to be effective in various applications. However, the learning scheme of SC is suboptimal in that it learns the cluster indicator from a fixed graph structure, which usually requires a rounding procedure to further partition the data. Also, the obtained cluster number cannot reflect the ground truth number of connected components in the graph. To alleviate these drawbacks, we propose a rank-constrained SC with flexible embedding framework. Specifically, an adaptive probabilistic neighborhood learning process is employed to recover the block-diagonal affinity matrix of an ideal graph. Meanwhile, a flexible embedding scheme is learned to unravel the intrinsic cluster structure in low-dimensional subspace, where the irrelevant information and noise in high-dimensional data have been effectively suppressed. The proposed method is superior to previous SC methods in that: 1) the block-diagonal affinity matrix learned simultaneously with the adaptive graph construction process, more explicitly induces the cluster membership without further discretization; 2) the number of clusters is guaranteed to converge to the ground truth via a rank constraint on the Laplacian matrix; and 3) the mismatch between the embedded feature and the projected feature allows more freedom for finding the proper cluster structure in the low-dimensional subspace as well as learning the corresponding projection matrix. Experimental results on both synthetic and real-world data sets demonstrate the promising performance of the proposed algorithm.

KW - Flexible embedding

KW - rank-constrained

KW - spectral clustering (SC)

UR - http://www.scopus.com/inward/record.url?scp=85045729645&partnerID=8YFLogxK

U2 - 10.1109/TNNLS.2018.2817538

DO - 10.1109/TNNLS.2018.2817538

M3 - Article

C2 - 29993916

AN - SCOPUS:85045729645

VL - 29

SP - 6073

EP - 6082

JO - IEEE Transactions on Neural Networks and Learning Systems

JF - IEEE Transactions on Neural Networks and Learning Systems

SN - 2162-237X

IS - 12

M1 - 8341858

ER -