Constrained spectral clustering via exhaustive and efficient constraint propagation

Research output: Chapters, Conference Papers, Creative and Literary Works (RGC: 12, 32, 41, 45)32_Refereed conference paper (with ISBN/ISSN)Not applicablepeer-review

37 Scopus Citations
View graph of relations

Author(s)

Detail(s)

Original languageEnglish
Title of host publicationComputer Vision, ECCV 2010
Subtitle of host publication11th European Conference on Computer Vision, Proceedings
PublisherSpringer Verlag
Pages1-14
Volume6316 LNCS
EditionPART 6
ISBN (Print)3642155669, 9783642155666
Publication statusPublished - 2010

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6316 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Title11th European Conference on Computer Vision, ECCV 2010
PlaceGreece
CityHeraklion, Crete
Period5 - 11 September 2010

Abstract

This paper presents an exhaustive and efficient constraint propagation approach to exploiting pairwise constraints for spectral clustering. Since traditional label propagation techniques cannot be readily generalized to propagate pairwise constraints, we tackle the constraint propagation problem inversely by decomposing it to a set of independent label propagation subproblems which are further solved in quadratic time using semi-supervised learning based on k-nearest neighbors graphs. Since this time complexity is proportional to the number of all possible pairwise constraints, our approach gives a computationally efficient solution for exhaustively propagating pairwise constraint throughout the entire dataset. The resulting exhaustive set of propagated pairwise constraints are then used to adjust the weight (or similarity) matrix for spectral clustering. It is worth noting that this paper first clearly shows how pairwise constraints are propagated independently and then accumulated into a conciliatory closed-form solution. Experimental results on real-life datasets demonstrate that our approach to constrained spectral clustering outperforms the state-of-the-art techniques. © 2010 Springer-Verlag.

Citation Format(s)

Constrained spectral clustering via exhaustive and efficient constraint propagation. / Lu, Zhiwu; Ip, Horace H. S.

Computer Vision, ECCV 2010: 11th European Conference on Computer Vision, Proceedings. Vol. 6316 LNCS PART 6. ed. Springer Verlag, 2010. p. 1-14 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6316 LNCS).

Research output: Chapters, Conference Papers, Creative and Literary Works (RGC: 12, 32, 41, 45)32_Refereed conference paper (with ISBN/ISSN)Not applicablepeer-review