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.
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:
- 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.
- 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.
- 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.
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