Abstract
Affinity Propagation (AP) is a powerful clustering algorithm that identifies exemplars by passing messages between data points. However, its quadratic complexity $O(N^2)$ limits its application to large-scale datasets. This paper introduces ScaleAP, a novel algorithm that achieves nearly linear complexity while mathematically guaranteeing the exact same clustering results as the original AP. By utilizing deterministic message pruning and aggregated updates, ScaleAP provides up to two orders of magnitude speedup on massive real-world datasets.
The Challenge of Scaling Affinity Propagation
Affinity Propagation is highly regarded for its ability to handle arbitrary similarity measures and automatically determine the number of clusters. Unlike K-means, which requires a pre-specified $K$, AP identifies "exemplars" through an iterative process of exchanging "responsibility" and "availability" messages.
Despite its advantages, the standard AP algorithm requires every point to communicate with every other point, leading to $O(N^2)$ complexity per iteration. For a dataset of 100,000 points, this translates to 10 billion updates per round. Previous attempts to scale AP generally fell into two categories:
- Sampling methods: These approximate the similarity matrix to improve speed but sacrifice clustering accuracy.
- Bounding methods: These use mathematical bounds to prune updates but often revert to quadratic behavior in dense or large clusters.
Methods: Deterministic Message Pruning
ScaleAP introduces a property called deterministic message pruning. The core innovation lies in the theoretical proof that for the vast majority of data point pairs, messages are uniquely determined by their initial similarity values. If a pair is not a strong candidate for being an exemplar, its message does not need to be iteratively recalculated.
Key technical components include:
- Prunable Pairs: ScaleAP identifies pairs whose contributions to the clustering process remain static.
- Aggregated Message Updates: Instead of updating every pair individually, ScaleAP computes the contributions of prunable pairs directly from the similarity matrix in $O(1)$ time.
- Exactness Guarantee: Unlike approximation methods, ScaleAP is an "exact" algorithm. Theorem 2 in the paper proves that the pruning process does not alter the final clustering outcome.
By focusing only on "essential" pairs (exemplar candidates), the complexity is reduced from $O(N^2T)$ to $O((1+\epsilon)NT)$, where $\epsilon$ represents the average number of candidates—a value that remains small in most real-world scenarios.
Experimental Evaluation
The algorithm was tested on three diverse datasets from the UCI Machine Learning Repository:
- Human Activity Recognition: 10,299 objects (6 clusters).
- MoCap (Motion Capture): 78,095 objects (5 clusters).
- YouTube: 120,000 objects (31 clusters).
Key Results and Insights
ScaleAP demonstrates that speed and accuracy are not mutually exclusive. By exploiting the intrinsic redundancy in real-world data—where many points share similar relationships—ScaleAP achieves nearly linear scalability.
- Massive Speedups: ScaleAP outperformed standard AP and variants like GraphAP and F-AP by up to 100x.
- Handling Large Datasets: On the YouTube dataset (120k points), standard AP failed to finish (DNF) within 24 hours. ScaleAP completed the task in under 30 minutes.
- Efficiency: The algorithm reduced the total number of message updates by 95.4%.
- Perfect Accuracy: ScaleAP consistently achieved a perfect 1.0 score in NMI and F-measure relative to the original AP, whereas sampling-based competitors showed significant accuracy degradation.
Conclusion
ScaleAP effectively removes the quadratic bottleneck of Affinity Propagation, making it a viable tool for massive datasets. While its performance depends on the number of exemplar candidates ($\epsilon$) remaining small, it provides a robust, exact solution for high-quality clustering at scale. Future work may explore applying these aggregated update principles to other message-passing frameworks.
Summary updated