Semi-supervised Clustering with Pairwise Constraints: A Discriminative Approach

Zhengdong LuAISTATS 2007

Introduction

Clustering is traditionally an unsupervised task, yet in many practical applications, we possess fragmentary "side information." This information typically comes in the form of pairwise constraints: "must-link" (two points belong to the same cluster) or "cannot-link" (two points belong to different clusters). While traditional generative models like constrained K-means or Gaussian Mixture Models (GMMs) attempt to incorporate this data, they often require a high density of constraints to be effective and struggle with complex, non-Gaussian data distributions such as interlocking spirals.

This paper introduces the Semi-supervised Pairwise Gaussian Process (SPGP), a discriminative framework designed to overcome these limitations. By focusing on cluster boundaries rather than internal distributions, SPGP leverages the underlying manifold structure of the data to propagate sparse information across the entire dataset.

Figure 1: Illustration of how just two pairwise relations (must-link and cannot-link) can guide the clustering of a complex dataset.

The SPGP Framework

The SPGP extends the standard Gaussian Process Classifier (GPC) to handle pairwise relations instead of absolute labels. The model is built on three pillars:

  1. Pairwise Likelihood: Instead of direct labels, the model defines likelihood based on the probability that a configuration of labels satisfies the given constraints. A Gibbs distribution is employed to model this, allowing for "soft" constraints where weights reflect the confidence in each link.
  2. Semi-supervised Graph Kernels: To ensure that sparse constraints influence the entire dataset, the authors utilize kernels based on the Graph Laplacian (e.g., Heat Diffusion or Lazy-Random-Walk kernels). These kernels act as a bridge, ensuring that points in dense regions share similar latent classification values.
  3. MAP Estimation for Symmetry Breaking: A unique challenge in pairwise clustering is symmetry; if points A and B are must-linked, they could both be in Class +1 or both in Class -1. In a standard Bayesian integration, this leads to a perfectly ambiguous mean of 0.5. The authors solve this by using Maximum a Posteriori (MAP) estimation to select the most likely cluster orientation.
Figure 4: (a) A graph of pairwise relations with associated weights. (b) Scatter plots showing the relationship between the log-likelihood and the objective function, demonstrating the effectiveness of the MAP approach.

Key Insights and Results

Discriminative Power and Non-Linearity

Unlike K-means, which assumes spherical clusters, SPGP can identify highly non-linear boundaries. In tests on "Two-Spirals" and "Doughnut" datasets, SPGP achieved near-perfect accuracy with minimal constraints, whereas traditional methods failed due to their bias toward globular shapes.

Performance on Real-World Data

The model was evaluated on several benchmarks, including UCI datasets (Balance-Scale, Pima) and text datasets (Mac-Windows). SPGP consistently outperformed state-of-the-art competitors. For instance, on the Balance dataset, SPGP reached ~95% accuracy with only 60 relations, while other methods hovered between 65-80%.

Robustness to Noise

By utilizing "soft" relations, the SPGP variant remains stable even when some constraints are intentionally incorrect. This robustness makes it particularly suitable for real-world scenarios where side information might be derived from noisy sources or crowdsourcing.

Conclusion and Future Work

The SPGP framework represents a significant step forward in semi-supervised clustering by providing a discriminative alternative to generative models. While highly effective, the current formulation requires at least one "cannot-link" constraint to avoid trivial solutions where all points are assigned to a single cluster. Future research will focus on adding balancing terms to handle cases with only "must-link" data and scaling the approach to multi-class problems.

Summary updated

BibTeX
@article{lu2007semi,
  author = {Zhengdong Lu},
  title = {{Semi-supervised Clustering with Pairwise Constraints: A Discriminative Approach}},
  journal = {AISTATS},
  year = {2007},
}
Figure