Large-scale spectral clustering based on pairwise constraints

• We face the real-world problem of having a limited set of pairwise constraints.
• Using pairwise constraints connected components (CC) are generated.
• The points’ local neighborhoods of the same CC are dynamically adapted.
• Constraints propagation to CC neighborhoods to increase the clustering accuracy.
• Scalability is ensured by following a landmark strategy.

In this paper, we present an efficient spectral clustering method for large-scale data sets, given a set of pairwise constraints. Our contribution is threefold: (a) clustering accuracy is increased by injecting prior knowledge of the data points’ constraints to a small affinity submatrix; (b) connected components are identified automatically based on the data points’ pairwise constraints, generating thus isolated “islands” of points; furthermore, local neighborhoods of points of the same connected component are adapted dynamically, and constraints propagation is performed so as to further increase the clustering accuracy; finally (c) the complexity is preserved low, by following a sparse coding strategy of a landmark spectral clustering. In our experiments with three benchmark shape, face and handwritten digit image data sets, we show that the proposed method outperforms competitive spectral clustering methods that either follow semi-supervised or scalable strategies.