How Affinity Propagation Passes Messages for AI Clustering

This article explains the mechanics of Affinity Propagation, an unsupervised machine learning clustering algorithm that identifies representative data points called exemplars. Unlike traditional clustering methods that require specifying the number of clusters in advance, Affinity Propagation simultaneously considers all data points as potential exemplars. It achieves clustering by iteratively passing two types of real-valued messages—responsibility and availability—between pairs of data points until a high-quality set of exemplars and corresponding clusters emerges.

The Foundation: Similarity Matrix

Before any messages are passed, Affinity Propagation establishes a baseline using a similarity matrix. For every pair of data points, \(i\) and \(k\), the algorithm calculates a similarity score, \(s(i, k)\), which reflects how well data point \(k\) is suited to be the exemplar for data point \(i\). Typically, this is calculated using the negative squared Euclidean distance between the two points.

The diagonal of this matrix contains the "self-similarities," \(s(k, k)\), also known as preferences. The preference value dictates the likelihood of a specific data point \(k\) becoming an exemplar. Higher preference values result in a larger number of final clusters, while lower values yield fewer clusters.

Message 1: Responsibility

Responsibility, denoted as \(r(i, k)\), is a message sent from data point \(i\) to candidate exemplar \(k\). It reflects the accumulated evidence of how well-suited point \(k\) is to serve as the exemplar for point \(i\), taking into account other potential exemplars for point \(i\).

In each iteration, the responsibility is updated using the following logic:

  1. Point \(i\) looks at its similarity to candidate \(k\), which is \(s(i, k)\).
  2. It subtracts the maximum value of the sum of availabilities and similarities of all other candidate exemplars \(k'\).
  3. The mathematical formula is: \(r(i, k) = s(i, k) - \max_{k' \neq k} \{a(i, k') + s(i, k')\}\).

In plain terms, a data point \(i\) tells candidate \(k\): "You are my best option for an exemplar by this specific margin, compared to my next best option." If another point \(k'\) becomes more available or is more similar to \(i\), the responsibility \(r(i, k)\) decreases.

Message 2: Availability

Availability, denoted as \(a(i, k)\), is a message sent from candidate exemplar \(k\) back to data point \(i\). It reflects the accumulated evidence of how appropriate it would be for point \(i\) to choose point \(k\) as its exemplar, taking into account the support provided by other data points that also want \(k\) as their exemplar.

Availability is updated in two distinct ways depending on whether \(i\) and \(k\) are the same point:

  • Standard Availability (\(i \neq k\)): Candidate \(k\) sums its self-responsibility \(r(k, k)\) and all the positive responsibilities it receives from other points \(i'\) (excluding \(i\)). The sum is capped at zero so that availability cannot be positive, preventing runaway feedback loops. The formula is: \(a(i, k) = \min(0, r(k, k) + \sum_{i' \notin \{i, k\}} \max(0, r(i', k)))\).
  • Self-Availability (\(i = k\)): The availability of a point to itself is simply the sum of all positive responsibilities it receives from other points: \(a(k, k) = \sum_{i' \neq k} \max(0, r(i', k))\).

In plain terms, candidate \(k\) tells data point \(i\): "Based on how much I want to be an exemplar and how many other points are voting for me, here is how available I am to lead your cluster." By only summing positive responsibilities, candidate \(k\) only cares about points that actively prefer it over other candidates.

Selecting the Exemplars

The message-passing process is iterative. Initially, all availabilities are set to zero, and responsibilities are calculated. Then, availabilities are updated using the new responsibilities.

To prevent numerical oscillations—where points endlessly flip-flop between choosing different exemplars—a damping factor (\(\lambda\), typically between 0.5 and 0.9) is applied at each step. Each new message is set to \(\lambda\) times the message from the previous iteration plus \((1 - \lambda)\) times the newly calculated message.

At any point during or at the end of the iterations, responsibilities and availabilities are combined to identify the exemplars. For a specific data point \(i\), the value of \(k\) that maximizes the sum \(a(i, k) + r(i, k)\) identifies point \(i\)'s exemplar.

  • If \(k = i\), then data point \(i\) is selected as an exemplar itself.
  • If \(k \neq i\), then data point \(i\) belongs to the cluster represented by exemplar \(k\).

The algorithm terminates when the chosen exemplars remain constant for a specified number of iterations, or when the changes in the messages fall below a predefined threshold, locking in the final clusters.