Affinity Propagation (AP) has emerged as a robust, exemplar-based clustering method that uses message passing on a factor graph to identify representative data points. While powerful in unsupervised settings, many real-world applications—such as interactive image segmentation—benefit from small amounts of "side information" provided by a user. This paper, originally presented at AISTATS 2009, introduces Semi-Supervised Affinity Propagation (SSAP), a principled extension that integrates instance-level constraints directly into the underlying probabilistic framework.
The Challenge of Constrained Clustering
In traditional clustering, the algorithm operates solely on feature similarities. However, a user might know that two specific regions belong to the same object (must-link) or different objects (cannot-link). Standard AP lacks a native mechanism to respect these constraints. Previous approaches often relied on modifying distance metrics or forcing hard labels, which frequently failed to propagate information effectively across the feature space or were too restrictive for complex datasets.
Methodology: Factor Graph Integration
The core innovation of SSAP is the structural modification of the AP factor graph to include Meta-Points (MTPs) and Constraint (CL) nodes.
- Must-Link Constraints: The algorithm computes the transitive closure of all must-link pairs. Each resulting group is represented by a single Meta-Point. All points within a must-link group are constrained to choose their assigned MTP as their exemplar, ensuring they are clustered together.
- Cannot-Link Constraints: These are handled by adding CL nodes to the graph. If two groups (or MTPs) are marked as "cannot-link," these nodes ensure they cannot select the same exemplar.
- Space-Level Propagation: By integrating these constraints into the message-passing framework, the influence of a few constrained points propagates to their unconstrained neighbors. This allows the algorithm to "guess" the correct clusters for the rest of the dataset based on sparse feedback.
Experimental Evaluation
The authors evaluated SSAP on an interactive image segmentation task using a dataset of 23 images. Each image was preprocessed into approximately 200 superpixels, with similarities calculated based on spatial distance and color coordinates in Cielab space. The goal was to recover ground-truth segmentations (ranging from 2 to 11 labels per image) using varying percentages of constrained data.
Performance was measured using the Modified Rand Index, which quantifies the agreement between the algorithm's clustering and the ground truth.
Key Results
SSAP demonstrated significant improvements over both standard AP and Constrained EM (CEM), a common baseline for semi-supervised clustering.
- Superior Accuracy: As shown in the performance plots, SSAP consistently maintained a higher Rand Index than CEM across various levels of constraint density.
- Efficiency with Sparse Data: The most notable gains occurred when very little side information was available (e.g., 5-10% constrained data). SSAP's ability to propagate constraints through the factor graph allowed it to outperform methods that treat constraints as simple filters.
Conclusion
SSAP transforms Affinity Propagation from a purely unsupervised method into a flexible semi-supervised tool. By treating constraints as structural priors rather than post-processing filters, the algorithm effectively leverages sparse user feedback to improve clustering accuracy in complex tasks like image segmentation. Future work may explore extending this framework to hierarchical clustering, allowing for interactive multi-level data exploration.
Summary updated