Abstract
Affinity Propagation (AP) is a powerful clustering technique that identifies real data points as exemplars, offering high interpretability compared to centroid-based methods like K-Means. However, its quadratic complexity ($O(N^2)$) in time and memory limits its utility for large-scale datasets. This paper introduces Patch Affinity Propagation (PAP), a method that processes data in sequential "patches" to achieve linear time complexity ($O(N)$) and constant memory requirements. By incorporating a multiplicity mechanism to weight previous exemplars, PAP maintains the core benefits of AP while enabling the analysis of massive biomedical datasets. Evaluation on chromosome and bacterial datasets demonstrates that PAP can match standard AP performance in well-separated data, though a performance trade-off exists in noisier environments.
Introduction
Affinity Propagation has become a staple in clustering tasks where interpretability is paramount. Unlike methods that create synthetic centroids, AP finds exemplars—actual representative data points from the dataset. In fields like bioinformatics, this allows researchers to point to a specific DNA sequence or protein structure as the cluster representative. Despite its advantages, AP's $O(N^2)$ scaling makes it computationally prohibitive for modern high-throughput data.
To address this, Patch Affinity Propagation (PAP) is proposed as a scalable alternative. PAP processes data in sequential chunks, treating previous cluster representatives as weighted points in subsequent batches. This approach brings the interpretability of exemplar-based clustering to datasets previously too large for standard AP.
Methodology
The core innovation of PAP is a "rolling" process that maintains a memory of previous clusters without requiring the full similarity matrix to be stored in memory. The process follows four key steps:
- Chunking: The dataset is partitioned into manageable patches of size $m$.
- Multiplicity Assignment: When a patch is clustered, the resulting exemplars are assigned a "multiplicity" score representing the number of data points they represent.
- Integration: In subsequent patches, the algorithm processes new data alongside the weighted exemplars from the previous patch.
- Convergence Optimization: Standard AP often fails to converge when encountering identical data points. PAP resolves this by modifying the AP cost function to handle multiplicities directly, mathematically weighting the responsibilities and preferences to ensure numerical stability.
This architecture transforms a quadratic problem into a linear one ($O(N)$), provided the patch size remains constant, making it suitable for streaming data or massive static datasets.
Experimental Results
The researchers evaluated PAP on two distinct biomedical benchmarks: the Copenhagen Chromosomes dataset (4,200 human chromosome images) and the Vibrio Bacteria dataset (1,100 mass spectra samples). These datasets represent complex, high-dimensional data where exemplar identification is critical.
As shown in Table 1, the performance of PAP varies based on the underlying data structure:
- Vibrio Dataset: PAP achieved an accuracy of 0.999, perfectly matching the performance of the full AP algorithm. This indicates that for well-separated, multimodal data, the patch approximation loses virtually no information.
- Chromosomes Dataset: PAP reached 0.755 accuracy, a notable decrease from the original AP's 0.895. This performance gap is attributed to the "noisy" nature of the chromosome data; when clusters overlap significantly, the greedy nature of the patch approach can lead to premature commitment to suboptimal exemplars.
Discussion and Conclusion
The primary technical contribution of PAP is the adaptation of AP's update equations to handle multiplicities, allowing the algorithm to treat a single exemplar as a proxy for many points without instability. This makes the algorithm highly memory-efficient, as the footprint remains flat regardless of total dataset growth. Additionally, the method is naturally suited for non-I.I.D. (independent and identically distributed) data, as it carries compressed information forward through the patches.
While PAP offers a significant leap in scalability, the accuracy trade-off in noisy datasets remains a limitation. Future work should focus on refining the integration of patches to mitigate error propagation in overlapping clusters. Nevertheless, PAP stands as a robust tool for researchers requiring interpretable, exemplar-based clustering at a massive scale.
Summary updated