What Is Affinity Propagation?

Affinity propagation is a clustering algorithm that identifies a set of representative data points, called exemplars, by exchanging real-valued messages between all pairs of points until a stable assignment emerges. It was introduced by Brendan Frey and Delbert Dueck in the 2007 Science paper Clustering by Passing Messages Between Data Points, which framed exemplar selection as inference on a factor graph and solved it with a variant of belief propagation. The method differs from k-means and its relatives in two respects that matter in practice: the number of clusters is an outcome rather than an input, and every cluster center is an actual observed data point rather than a computed average.

Because the algorithm operates on a matrix of pairwise similarities, it does not require the data to live in a vector space. Any symmetric or asymmetric similarity measure works, including negative squared Euclidean distance, edit distance between strings, or a domain-specific score, which makes the method applicable to sequences, graphs, and other non-numeric objects.

Similarities, Preferences, and Exemplars

The input is a similarity matrix whose off-diagonal entries indicate how well one point would serve as the exemplar for another. The diagonal entries are treated differently: each is a preference expressing the prior suitability of that point to be an exemplar at all. Raising the preferences produces more clusters and lowering them produces fewer, so the preference value takes the place of the cluster count that partitional methods demand in advance. Setting all preferences to the median of the input similarities is the common default, and a shared preference implies no prior bias toward any particular point.

Responsibility and Availability Messages

Two message types circulate. The responsibility sent from a point to a candidate exemplar reflects how well suited that candidate is compared with all competing candidates for the same point. The availability sent from a candidate back to a point reflects how appropriate it would be for that point to choose the candidate, given the support the candidate has already accumulated from others. The updates are computed from simple max-sum expressions over the similarity matrix and the incoming messages of the other type, and they are iterated until the exemplar decisions stop changing. Because raw updates oscillate, implementations apply a damping factor, usually between 0.5 and 0.9, that mixes each new message with the previous one. Computation and memory both scale with the square of the number of points, which is the main barrier to applying the method to large datasets without sparsification.

Evaluation and Extensions

The original paper reported results on face image clustering, identification of putative exons in mouse microarray data, selection of representative sentences from a manuscript, and the choice of airline hub cities, with lower squared error than repeated k-medoids runs at comparable computational cost. That comparison drew a published Comment in Science arguing that established exemplar-based heuristics, given equivalent computation, match or exceed the reported performance on some benchmarks, and the exchange remains a useful reference point on how clustering methods should be benchmarked. Subsequent variants relax the hard one-exemplar constraint, as in soft-constraint affinity propagation applied to gene expression data, or adapt the message updates to datasets containing regions of differing density, as in an extended affinity propagation method based on data density types.

Applications

Affinity propagation has applications in a range of fields, including:

• Computational biology, for grouping gene expression profiles and protein sequences
• Computer vision, for face and image exemplar selection
• Text summarization and representative sentence extraction
• Network analysis and community detection
• Facility location and transportation hub planning