On constrained spectral clustering and its applications

By Xiang Wang, Buyue Qian, Ian N. Davidson. 2012

210 citations recorded by the source corpus.

Constrained clustering has been well-studied for algorithms such as K-means and hierarchical clustering. However, how to satisfy many constraints in these algorithmic settings has been shown to be intractable. One alternative to encode many constraints is to use spectral clustering, which remains a developing area. In this paper, we propose a flexible framework for constrained spectral clustering. In contrast to some previous efforts that implicitly encode Must-Link (ML) and Cannot-Link (CL) constraints by modifying the graph Laplacian or constraining the underlying eigenspace, we present a more natural and principled formulation, which explicitly encodes the constraints as part of a constrained optimization problem. Our method offers several practical advantages: it can encode the degree of belief in ML and CL constraints; it guarantees to lower-bound how well the given constraints are satisfied using a user-specified threshold; it can be solved deterministically in polynomial time through generalized eigendecomposition. Furthermore, by inheriting the objective function from spectral clustering and encoding the constraints explicitly, much of the existing analysis of unconstrained spectral clustering techniques remains valid for our formulation. We validate the effectiveness of our approach by empirical results on both artificial and real datasets. We also demonstrate an innovative use of encoding large number of constraints: transfer learning via constraints.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Media Technology

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

In Computer Vision and Pattern Recognition

In Media Technology

Citations in the corpus

Learning to cluster in order to Transfer across domains and tasks (2017, methodology): “In the case of unknown number of clusters, where we set K = 100 , the algorithms that use constraints to optimize clustering loss have better robustness, for example, CSP and CCN.”
Deep Amortized Clustering (2019, unknown): “(Cai et al., 2009) 0.372 0.498 LSC (Chen & Cai, 2011) 0.376 0.500 CSP (Wang et al., 2014) 0.812 0.812 MPCK-means (Bilenko et al., 2004) 0.871 0.816 KCL (Hsu et al., 2017) 0.889 0.874 MCL (Hsu et al., 2019) 0.897 0.893 While the metrics for DAC were computed after at most 100 forward passes,…”
Multi-class Classification without Multi-class Labels (2019, methodology): “CSP (Wang et al., 2014) and COSC (Rangapuram & Hein, 2012) use this strategy.”
Learning Concept Embeddings with Combined Human-Machine Expertise (2015, methodology): “We compare against other semi-supervised learning and constrained clustering systems: Label Propagation [4], the multiclass version of the Constrained Spectral Clustering KMeans (CSPKmeans) method described in [36], and Metric PairwiseConstrained KMeans (MPCKmeans) [5].”