Joint Optimization for Pairwise Constraint Propagation

Yuheng JIA, Wenhui WU, Ran WANG, Junhui HOU, Sam KWONG

Research output: Journal PublicationsJournal Article (refereed)peer-review

14 Citations (Scopus)


Constrained spectral clustering (SC) based on pairwise constraint propagation has attracted much attention due to the good performance. All the existing methods could be generally cast as the following two steps, i.e., a small number of pairwise constraints are first propagated to the whole data under the guidance of a predefined affinity matrix, and the affinity matrix is then refined in accordance with the resulting propagation and finally adopted for SC. Such a stepwise manner, however, overlooks the fact that the two steps indeed depend on each other, i.e., the two steps form a "chicken-egg'' problem, leading to suboptimal performance. To this end, we propose a joint PCP model for constrained SC by simultaneously learning a propagation matrix and an affinity matrix. Especially, it is formulated as a bounded symmetric graph regularized low-rank matrix completion problem. We also show that the optimized affinity matrix by our model exhibits an ideal appearance under some conditions. Extensive experimental results in terms of constrained SC, semisupervised classification, and propagation behavior validate the superior performance of our model compared with state-of-the-art methods.
Original languageEnglish
Pages (from-to)3168-3180
Number of pages13
JournalIEEE Transactions on Neural Networks and Learning Systems
Issue number7
Early online date3 Aug 2020
Publication statusPublished - Jul 2021
Externally publishedYes

Bibliographical note

This work was supported in part by the Natural Science Foundation of China under Grant 61871342, Grant 61772344, Grant 61732011, and Grant 61672443, in part by the Hong Kong Research Grants Council (RGC) General Research Funds under Grant 9042820 (CityU 11219019), Grant 9042489 (CityU 11206317), Grant 9042322 (CityU 11200116), Grant 9042816 (CityU 11209819), and Grant 9048123 (CityU 21211518), in part by the Key Project of Science and Technology Innovation 2030 supported by the Ministry of Science and Technology of China under Grant 2018AAA0101301, and in part by the Interdisciplinary Innovation Team of Shenzhen University.


  • Constrained spectral clustering (SC)
  • pairwise constraint propagation (PCP)
  • semisupervised learning


Dive into the research topics of 'Joint Optimization for Pairwise Constraint Propagation'. Together they form a unique fingerprint.

Cite this