Affinity Propagation

April 4, 2008

A little over one year ago, Frey and Dueck published a paper in Science where they describe an algorithm called affinity propagation which clusters data points via passing messages between the points. In their paper they first describe the algorithm and then apply it to a few different examples of clustering problems from diverse fields.

Input consists of a collection of real-valued similarities between data points. These are represented by s(i,k) which describes how well data point k is suited to be exemplar for data point i. In addition, each data point is supplied with a preference value s(k,k) which specifies apriori how likely each data point is to be an exemplar. This preference value can be set to something uninformative, allowing the clustering procedure to learn from the data an appropriate number of clusters. Alternative preference information can be utilized to minimize clusters or infuse the system with prior information.

There are two kinds of messages exchanged between data points, responsibilities and availabilities:

Responsibilities r(i,k) reflect the accumulated evidence for how well-suited point k is to serve as the exemplar for point i, taking into account other potential exemplars for point i. Responsibilities are sent from point i to candidate exemplar k.

Availability a(i,k) reflect accumulated evidence for how appropriate it would be for point i to choose k as its exemplar, taking into account the support from other points that point k should be an exemplar. Availabilities are sent from candidate exemplar k to data point i. Availabilities are initially zero.

In general the algorithm works in three steps:

  1. Update responsibilities given availabilities. Initially this is a data driven update, and over time lets candidate exemplars competition for ownership of the data.
  2. Update availabilities given the responsibilities. This gathers evidence from data points as to whether a candidate exemplar is a good exemplar.
  3. Monitor exemplar decisions by combining availabilities and responsibilities. Terminate if reach a stopping point (e.g. insufficient change). The update rules require simple local computations and messages are exchanged between pairs of points with known similarities.

Given this algorithm, they then explore a number of example applications. The first is a simple illustrative example of how the algorithm works (Figure 1). A more typical example is given in an example of clustering images of faces (Figure 2). They use the problem of clustering exons to find genes as an example demonstrating behavior in a sparsely related system (Figure 3). Their final example is uses airline connectivity data to identify well connected cities (Figure 4). They finish the paper with a couple paragraphs on comparisons of affinity propagation to related techniques.

As Marc Mézard notes in his commentary, message passing algorithms are remarkably efficient even on hard problems. In many cases they are the best available algorithms, hence affinity propagation promises to be broadly applicable to many problems. Mézard gives a anthropomorphic explanation for how message passing works which complements Frey and Dueck’s paper nicely.

For those interested in the nitty gritty details, the Frey paper has a detailed supplemental description of their MATLAB implementation.

Frey, B.J., Dueck, D. (2007). Clustering by Passing Messages Between Data Points. Science, 315(5814), 972-976. DOI: 10.1126/science.1136800

Mézard, M. (2007). COMPUTER SCIENCE: Where Are the Exemplars?. Science, 315(5814), 949-951. DOI: 10.1126/science.1139678


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: