Definition
Affinity propagation (Frey & Dueck, 2007) clusters data by choosing a subset of the data points themselves as exemplars. Every point repeatedly sends two kinds of messages — responsibility ("how well would serve as my exemplar?") and availability ("how much support does have to be an exemplar?") — until a stable set of exemplars emerges. The number of clusters is not given; it falls out of a per-point preference for being an exemplar.
At a glance
- Task
- Clustering (unsupervised), exemplar-based
- Input → output
- an similarity matrix (any similarity, not necessarily metric) → a set of exemplars and a label per point
- Learns
- two message matrices (responsibility) and (availability); the exemplars are read off their diagonals
- Training
- time per iteration, typically 20–200 iterations; memory for , ,
- Prediction
- assign a new point to its most similar exemplar: similarities
- Hyperparameters
- preference (controls the number of clusters), damping λ, max iterations, convergence window
- Assumes
- a meaningful similarity; clusters are well represented by one of their own members; n small enough for an n × n matrix
The problem
k-means needs in advance, its centres are averages that may not be real data points, and it only works with squared Euclidean distance. k-medoids fixes the last two — the centres become actual points (medoids) and any dissimilarity works — but still needs , and its swap search can stop at a poor local optimum that depends on which points it started from.
Affinity propagation attacks both remaining problems at once. It considers every point as a potential exemplar simultaneously (no random initialisation), and replaces "choose " with "how much does it cost to open one more exemplar?" — a single number per point, the preference. Points then negotiate who represents whom.
Another way to avoid fixing is hierarchical clustering (see hierarchical clustering and agglomerative clustering), which builds a whole dendrogram and lets you cut it later; BIRCH summarises huge datasets into a tree of sub-clusters. Affinity propagation instead returns one flat clustering whose size is set by a cost, and its centres are always real points. For the objective it shares with k-medoids — total dissimilarity of points to their representatives — see the k-medoids article.
The idea
Picture an election in which every voter is also a candidate. Each point looks at all candidates and tells each one how much better it is than 's best other option — that is the responsibility. Each candidate collects the positive endorsements it received and reports back to every voter how plausible it is as an exemplar given everyone else's support — that is the availability. Voters update their opinions using the availabilities, candidates update using the responsibilities, and after a few dozen rounds a handful of candidates have strong support from both themselves and others. Those are the exemplars; every other point joins the exemplar it is most similar to.
Vocabulary
- Similarity s(i,k)
- how well would represent ; higher is better. The usual choice is the negative squared distance . It need not be symmetric.
- Exemplar
- a data point chosen to represent a cluster — like a medoid. Exemplar represents itself: .
- Preference s(k,k)
- the diagonal of the similarity matrix: how much "wants" to be an exemplar. Higher preference → more exemplars.
- Responsibility r(i,k)
- message from point to candidate : the evidence that should be 's exemplar, compared with 's best alternative.
- Availability a(i,k)
- message from candidate to point : the evidence that is a good exemplar, judged by the support gets from other points.
- Self-evidence
- ; point is an exemplar when this is positive.
- Damping λ
- each message is a mix of λ × old value and (1−λ) × new value; it stops the messages from oscillating.
- Net similarity
- the objective: total similarity of points to their exemplars plus the preferences of the exemplars.
The math
Let be the exemplar of point . Affinity propagation searches for the assignment that maximises the net similarity, subject to one consistency rule: if anyone picks as exemplar, must pick itself.
- index of the exemplar chosen by point
- similarity of to (); is the preference
- exemplar-consistency constraint: forbids choosing unless chooses itself
Each exemplar contributes , so the objective equals (sum of similarities of non-exemplars to their exemplars) when all preferences are equal to . Since in practice, each extra exemplar costs and is only opened if it raises the members' similarity by more than that. This is exactly the NP-hard facility-location / k-medoids objective with a price on instead of a fixed .
Exact maximisation is intractable, so AP runs max-sum belief propagation on the factor graph that has one variable per point and one constraint per candidate. Max-sum messages are differences of best achievable scores, and they simplify to two scalars per pair .
- responsibility: how much better is for than 's best competing candidate
- current availability of competitor to (all zero at the start)
Derivation of . Point 's variable receives a message from each constraint and contributes . The best total score achievable with is ; the best with is . The message sends to constraint is the score of "" minus the score of "", excluding 's own message (belief propagation never echoes a message back to its sender). That leaves exactly the formula above. On the diagonal, : 's preference minus how attractive its best alternative exemplar is.
- availability: how plausible is as an exemplar for , from 's self-responsibility and the positive support of others
- only positive endorsements count — a point that prefers another exemplar is simply not 's member
- caps availability at 0: strong support for cannot make more attractive to than "free"
Derivation of . Constraint compares two worlds for . If , then must be an exemplar, which earns , and every other point may join whenever that helps: . If , the constraint is free to choose whichever is better — an exemplar (same score) or not (score 0) — so it gets . The difference of the two is . For , "" means is an exemplar and collects positive support; "" forces nobody to choose , which scores 0. Hence no on the diagonal.
- the max-marginal belief that is 's exemplar
- self-evidence: positive means k is better off as an exemplar than not
- damping factor in ; scikit-learn's default is 0.5
- the values just computed by the update rules
What each hyperparameter does. The preference enters the objective once per exemplar, so it is literally the price of a cluster: raising toward 0 makes larger for every and more points cross the self-evidence threshold. The default gives a moderate number of clusters, a small number. Damping does not change the fixed points of the updates — only the path to them. Loopy max-sum on this graph tends to flip between "everyone is an exemplar" and "no one is"; averaging old and new messages turns that period-2 swing into a smooth approach, at the cost of more iterations.
Worked example: eight points, two exemplars
Eight points in 2-D, with similarity . The 56 off-diagonal similarities have median , so every preference is set to (scikit-learn's default). Damping .
| Point | x₁ | x₂ |
|---|---|---|
| A | 1 | 2 |
| B | 2 | 1 |
| C | 2 | 2 |
| D | 3 | 3 |
| E | 7 | 6 |
| F | 8 | 7 |
| G | 7 | 7 |
| H | 5 | 8 |
| s(i,k) | A | B | C | D | E | F | G | H |
|---|---|---|---|---|---|---|---|---|
| A | −30.5 | −2 | −1 | −5 | −52 | −74 | −61 | −52 |
| B | −2 | −30.5 | −1 | −5 | −50 | −72 | −61 | −58 |
| C | −1 | −1 | −30.5 | −2 | −41 | −61 | −50 | −45 |
| D | −5 | −5 | −2 | −30.5 | −25 | −41 | −32 | −29 |
| E | −52 | −50 | −41 | −25 | −30.5 | −2 | −1 | −8 |
| F | −74 | −72 | −61 | −41 | −2 | −30.5 | −1 | −10 |
| G | −61 | −61 | −50 | −32 | −1 | −1 | −30.5 | −5 |
| H | −52 | −58 | −45 | −29 | −8 | −10 | −5 | −30.5 |
Iteration 1 by hand (all messages start at 0)
- 1Responsibilities. With , . Row A's best candidate is C (), second best B (). So , and for every other : , e.g. .
- 2Row D: best C (), second A or B (), so . Row B gives . Row C itself: .
- 3Damping. : , , , .
- 4Availabilities for candidate C. Positive responsibilities into C come from A, B, D: . So and . After damping: , .
- 5Self-evidence. . Every point is still negative (G is also , H ), so after iteration 1 there are no exemplars.
- 6Keep iterating. Each round, C and G gather more support. At iteration 4 they become the first points with positive self-evidence ( and ) and the exemplar set then stays unchanged; after 15 unchanged iterations the run stops at iteration 19.
| k | iter 1 | iter 4 | iter 19 | exemplar? |
|---|---|---|---|---|
| A | −14.75 | −10.30 | −29.50 | no |
| B | −14.75 | −10.30 | −29.50 | no |
| C | −13.50 | 5.81 | 87.27 | yes |
| D | −14.25 | −12.99 | −28.50 | no |
| E | −14.75 | −10.15 | −29.50 | no |
| F | −14.75 | −11.93 | −29.50 | no |
| G | −13.50 | 6.18 | 84.30 | yes |
| H | −12.75 | −14.33 | −25.50 | no |
Reading off the clustering
- 1Labels. Each non-exemplar joins its most similar exemplar: A, B, D → C (similarities ); E, F, H → G ().
- 2Net similarity. . No other pair of exemplars does better: the best 2-point exemplar set by brute force is also with member similarity .
- 3Exemplars are data points. G represents although their mean is — AP never invents a centre.
- 4New point : squared distance 5 to C and 25 to G, so it is assigned to C's cluster.
Watch the messages
Iteration 19: exemplars C, G (self-evidence 87.27, 84.30). Converged: the exemplar set has not changed for 15 iterations.
The algorithm, step by step
AffinityPropagation(S, p, λ)
- 1Similarities. Build with for and set the diagonal to the preference (default: median off-diagonal similarity). Set .
- 2Responsibility update. For each row , find the largest and second-largest value of . Then , except in the argmax column, where the second largest is used. Damp: .
- 3Availability update. For each column , sum the positive responsibilities plus . Then off the diagonal and . Damp the same way.
- 4Exemplars. .
- 5Stop when has not changed for a window of iterations (15 by default) or after max_iter (200); otherwise go to step 2.
- 6Assign each point to its most similar exemplar; exemplars label themselves. New points are assigned the same way.
Complexity. Each update touches every pair once with the "largest / second-largest" and "column sum" tricks, so one iteration is time, and the run is . Memory is three dense float matrices: for that is bytes GB. With a sparse similarity graph (e.g. each point's nearest neighbours only), messages live only on the edges and the cost becomes .
Hyperparameters, variants and tuning
| Preference p | λ = 0 | λ = 0.5 | λ = 0.9 |
|---|---|---|---|
| −3 | C, G, H · 17 it | C, G, H · 18 it | C, G, H · 30 it |
| −30.5 (median) | oscillates, no convergence | C, G · 19 it | C, G · 38 it |
| −74 (min) | oscillates, no convergence | C, G · 19 it | C, G · 43 it |
| −140 | oscillates, no convergence | D · 21 it | D · 56 it |
Tuning guide
- preference
- the main knob. Median → moderate ; min → few clusters; scan a log-spaced grid between them and pick by silhouette score or by domain need. Per-point preferences let you favour some points as exemplars (e.g. known prototypes).
- damping
- 0.5–0.9 (scikit-learn requires ). Raise it when the run hits max_iter without converging or the exemplar count jumps around.
- convergence_iter / max_iter
- 15 / 200 by default. With high damping, messages move slowly — increase both, or AP can stop on a set that only looked stable.
- similarity
- negative squared Euclidean by default; with affinity="precomputed" you can pass any similarity: negative edit distance between strings, sequence-alignment scores, cosine similarity of embeddings, even non-symmetric ones.
- Scaling
- standardize features first when using Euclidean similarity; one large-range feature otherwise dominates every message.
Variants
- Sparse AP
- messages only on a k-nearest-neighbour graph; scales to far larger (the original paper ran it on such graphs).
- Adaptive AP
- scans the preference automatically and damps adaptively when oscillations are detected.
- Hierarchical AP
- stacks several AP layers so exemplars of one level are clustered again at the next.
- Soft-constraint AP
- relaxes the 'exemplar must choose itself' rule, allowing clusters that are not centred on a single point.
In code
1import numpy as np23def affinity_propagation(S, preference=None, damping=0.5, max_iter=200, convergence_iter=15):4 S = S.astype(float).copy()5 n = len(S)6 if preference is None:7 preference = np.median(S[~np.eye(n, dtype=bool)]) # median off-diagonal similarity8 np.fill_diagonal(S, preference)9 R = np.zeros((n, n)); A = np.zeros((n, n))10 rows = np.arange(n)11 last, stable = None, 012 for it in range(1, max_iter + 1):13 # responsibilities: r(i,k) = s(i,k) - max_{k' != k} [a(i,k') + s(i,k')]14 AS = A + S15 best = AS.argmax(1)16 first = AS[rows, best]17 AS[rows, best] = -np.inf18 second = AS.max(1)19 R_new = S - first[:, None]20 R_new[rows, best] = S[rows, best] - second21 R = damping * R + (1 - damping) * R_new22 # availabilities: a(i,k) = min(0, r(k,k) + sum_{i' not in {i,k}} max(0, r(i',k)))23 Rp = np.maximum(R, 0)24 np.fill_diagonal(Rp, R.diagonal())25 A_new = Rp.sum(0)[None, :] - Rp26 self_avail = A_new.diagonal().copy() # a(k,k) = sum_{i' != k} max(0, r(i',k))27 A_new = np.minimum(A_new, 0)28 np.fill_diagonal(A_new, self_avail)29 A = damping * A + (1 - damping) * A_new30 # exemplars: points whose self-evidence r(k,k) + a(k,k) is positive31 E = tuple(np.flatnonzero((R + A).diagonal() > 0))32 stable = stable + 1 if E == last else 033 last = E34 if E and stable >= convergence_iter:35 break36 E = np.array(last)37 labels = S[:, E].argmax(1)38 labels[E] = np.arange(len(E)) # each exemplar labels itself39 return E, labels, it4041X = np.array([[1, 2], [2, 1], [2, 2], [3, 3], [7, 6], [8, 7], [7, 7], [5, 8]], float)42S = -((X[:, None, :] - X[None, :, :]) ** 2).sum(-1) # negative squared distance43E, labels, it = affinity_propagation(S)44print("exemplars:", E, "->", X[E].tolist()) # [2 6] -> [[2.0, 2.0], [7.0, 7.0]]45print("labels: ", labels) # [0 0 0 0 1 1 1 1]46print("iterations:", it) # 1947new = np.array([4, 3])48print("new point (4,3) -> exemplar", E[np.argmax(-((X[E] - new) ** 2).sum(1))]) # 2 (= C)1import numpy as np2from sklearn.cluster import AffinityPropagation34X = np.array([[1, 2], [2, 1], [2, 2], [3, 3], [7, 6], [8, 7], [7, 7], [5, 8]])5ap = AffinityPropagation(damping=0.5, random_state=0).fit(X) # preference = median similarity6print("exemplars:", ap.cluster_centers_indices_, ap.cluster_centers_.tolist()) # [2 6] [[2, 2], [7, 7]]7print("labels: ", ap.labels_) # [0 0 0 0 1 1 1 1]8print("iterations:", ap.n_iter_) # 179print("predict (4,3):", ap.predict([[4, 3]])) # [0]1011for pref in [-3, -30.5, -74, -140]:12 m = AffinityPropagation(preference=pref, random_state=0).fit(X)13 print(f"preference {pref:>6}: exemplars {m.cluster_centers_indices_}")14# preference -3: exemplars [2 6 7]15# preference -30.5: exemplars [2 6]16# preference -74: exemplars [2 6]17# preference -140: exemplars [3]Use when
- +You do not know K and would rather set a price per cluster than a count.
- +Cluster centres must be real data points (a representative image, sentence, gene or customer).
- +Your similarity is non-metric or non-symmetric, so means make no sense.
- +n is in the hundreds to low thousands and you want a deterministic answer with no random restarts.
Avoid when
- − is large: memory and time per iteration rule it out beyond roughly points without sparsification.
- −Clusters are elongated or non-convex — one exemplar cannot represent a curved shape; use DBSCAN or spectral clustering.
- −You need exactly K clusters: hitting a given K means searching over the preference.
- −Data are noisy with many outliers: each outlier may become its own exemplar at high preferences.
Where it's used
Choosing representative images or faces
The original paper clustered face images and picked exemplar faces — real images that summarise each group.
Gene-expression and bioinformatics
Exemplar genes or protein sequences selected from alignment-score similarities, which are not Euclidean.
Text summarisation
Clustering sentences by embedding similarity and using each exemplar sentence in an extractive summary.
Facility and hub placement
Choosing which existing sites (airports, stores, sensors) should serve as hubs — the original paper's airline-travel example.
Check yourself
In the worked example (, ), what is after the first iteration?
Check yourself
You raise every preference from the median similarity toward 0. What happens?
Check yourself
In the example, one exemplar (D) gives net similarity and two (C, G) give . Below which preference does AP prefer a single cluster?
Check yourself
Point is declared an exemplar when…
Remember
- ✓Exemplars are real data points; every point is a candidate from the start, so there is no random initialisation.
- ✓Responsibility ; availability .
- ✓ is an exemplar when ; others join their most similar exemplar.
- ✓The preference is the price of a cluster: higher (closer to 0) → more clusters. Median and min of the similarities are the usual starting points.
- ✓Damping (0.5–0.9) stops the max-sum messages from oscillating; it changes the path, not the answer.
- ✓Cost is time per iteration and memory — fine for thousands of points, not millions.