# Affinity propagation

> Points exchange responsibility and availability messages until a set of exemplars emerges — no k required.

Source: https://www.mlfoundry.in/learn/affinity-propagation  
Section: ML Algorithms › Unsupervised · Clustering  
Level: advanced · 17 min read · updated 2026-10-07

**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 $k$ serve as my exemplar?") and *availability* ("how much support does $k$ 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.

- **Task:** Clustering (unsupervised), exemplar-based
- **Input → output:** an $n\times n$ similarity matrix $s(i,k)$ (any similarity, not necessarily metric) → a set of exemplars and a label per point
- **Learns:** two $n\times n$ message matrices $R$ (responsibility) and $A$ (availability); the exemplars are read off their diagonals
- **Training:** $O(n^2)$ time per iteration, typically 20–200 iterations; $O(n^2)$ memory for $S$, $R$, $A$
- **Prediction:** assign a new point to its most similar exemplar: $O(K)$ 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 $k$ 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 $k$, 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 $k$" 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 $k$ 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 $i$ looks at all candidates $k$ and tells each one how much better it is than $i$'s best *other* option — that is the **responsibility**. Each candidate $k$ 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 $k$ would represent $i$; higher is better. The usual choice is the negative squared distance $-\lVert x_i-x_k\rVert^2$. It need not be symmetric.
- **Exemplar:** a data point chosen to represent a cluster — like a medoid. Exemplar $k$ represents itself: $c_k=k$.
- **Preference s(k,k):** the diagonal of the similarity matrix: how much $k$ "wants" to be an exemplar. Higher preference → more exemplars.
- **Responsibility r(i,k):** message from point $i$ to candidate $k$: the evidence that $k$ should be $i$'s exemplar, compared with $i$'s best alternative.
- **Availability a(i,k):** message from candidate $k$ to point $i$: the evidence that $k$ is a good exemplar, judged by the support $k$ gets from *other* points.
- **Self-evidence:** $r(k,k)+a(k,k)$; point $k$ 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 $c_i$ be the exemplar of point $i$. Affinity propagation searches for the assignment $c=(c_1,\dots,c_n)$ that maximises the **net similarity**, subject to one consistency rule: if anyone picks $k$ as exemplar, $k$ must pick itself.

$$
\max_{c}\; \sum_{i=1}^{n} s(i,c_i) \;+\; \sum_{k=1}^{n}\delta_k(c),\qquad \delta_k(c)=\begin{cases}-\infty & \text{if } c_k\ne k \text{ but } \exists i: c_i=k\\ 0 & \text{otherwise}\end{cases}
$$

- $c_i$: index of the exemplar chosen by point $i$
- $s(i,k)$: similarity of $i$ to $k$ ($i\ne k$); $s(k,k)$ is the preference $p_k$
- $\delta_k(c)$: exemplar-consistency constraint: forbids choosing $k$ unless $k$ chooses itself

Each exemplar contributes $s(k,k)=p_k$, so the objective equals (sum of similarities of non-exemplars to their exemplars) $+\;p\cdot K$ when all preferences are equal to $p$. Since $p<0$ in practice, **each extra exemplar costs $|p|$** 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 $K$ instead of a fixed $K$.

Exact maximisation is intractable, so AP runs **max-sum belief propagation** on the factor graph that has one variable $c_i$ per point and one constraint $\delta_k$ per candidate. Max-sum messages are differences of best achievable scores, and they simplify to two scalars per pair $(i,k)$.

$$
r(i,k)\;\leftarrow\; s(i,k)\;-\;\max_{k'\ne k}\big[\,a(i,k')+s(i,k')\,\big]
$$

- $r(i,k)$: responsibility: how much better $k$ is for $i$ than $i$'s best competing candidate
- $a(i,k')$: current availability of competitor $k'$ to $i$ (all zero at the start)

**Derivation of $r$.** Point $i$'s variable $c_i$ receives a message $a(i,k)$ from each constraint and contributes $s(i,c_i)$. The best total score achievable with $c_i=k$ is $s(i,k)+a(i,k)$; the best with $c_i\ne k$ is $\max_{k'\ne k}[s(i,k')+a(i,k')]$. The message $i$ sends to constraint $k$ is the score of "$c_i=k$" minus the score of "$c_i\ne k$", **excluding $k$'s own message** $a(i,k)$ (belief propagation never echoes a message back to its sender). That leaves exactly the formula above. On the diagonal, $r(k,k)=p_k-\max_{k'\ne k}[a(k,k')+s(k,k')]$: $k$'s preference minus how attractive its best alternative exemplar is.

$$
a(i,k)\;\leftarrow\;\min\Big(0,\; r(k,k)+\!\!\sum_{i'\notin\{i,k\}}\!\!\max\big(0,\,r(i',k)\big)\Big)\quad (i\ne k),\qquad a(k,k)\;\leftarrow\;\sum_{i'\ne k}\max\big(0,\,r(i',k)\big)
$$

- $a(i,k)$: availability: how plausible $k$ is as an exemplar for $i$, from $k$'s self-responsibility and the positive support of others
- $\max(0,r(i',k))$: only positive endorsements count — a point that prefers another exemplar is simply not $k$'s member
- $\min(0,\cdot)$: caps availability at 0: strong support for $k$ cannot make $k$ more attractive to $i$ than "free"

**Derivation of $a$.** Constraint $\delta_k$ compares two worlds for $c_i$. If $c_i=k$, then $k$ *must* be an exemplar, which earns $r(k,k)$, and every other point $i'$ may join $k$ whenever that helps: $\sum_{i'}\max(0,r(i',k))$. If $c_i\ne k$, the constraint is free to choose whichever is better — $k$ an exemplar (same score) or not (score 0) — so it gets $\max(0,\text{that score})$. The difference of the two is $\text{score}-\max(0,\text{score})=\min(0,\text{score})$. For $a(k,k)$, "$c_k=k$" means $k$ is an exemplar and collects positive support; "$c_k\ne k$" forces nobody to choose $k$, which scores 0. Hence no $\min$ on the diagonal.

$$
c_i=\arg\max_{k}\big[a(i,k)+r(i,k)\big],\qquad k\text{ is an exemplar}\iff r(k,k)+a(k,k)>0
$$

- $a(i,k)+r(i,k)$: the max-marginal belief that $k$ is $i$'s exemplar
- $r(k,k)+a(k,k)$: self-evidence: positive means k is better off as an exemplar than not

$$
R\;\leftarrow\;\lambda R+(1-\lambda)R^{\text{new}},\qquad A\;\leftarrow\;\lambda A+(1-\lambda)A^{\text{new}}
$$

- $\lambda$: damping factor in $[0.5,1)$; scikit-learn's default is 0.5
- $R^{\text{new}},A^{\text{new}}$: the values just computed by the update rules

**What each hyperparameter does.** The **preference** $p$ enters the objective once per exemplar, so it is literally the price of a cluster: raising $p$ toward 0 makes $r(k,k)$ larger for every $k$ and more points cross the self-evidence threshold. The default $p=\text{median}(s)$ gives a moderate number of clusters, $p=\min(s)$ 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.

> **The preference is a price, and you can compute where it bites:** Because the objective is "member similarity $+\;pK$", the value of $p$ at which AP switches from $K$ to $K+1$ clusters is where the extra member similarity gained equals $|p|$. In the worked example below, one exemplar earns $-139+p$ and two earn $-11+2p$: they tie at $p=-128$, and that is exactly where the number of clusters jumps in the figure.

## Worked example: eight points, two exemplars

Eight points in 2-D, with similarity $s(i,k)=-\lVert x_i-x_k\rVert^2$. The 56 off-diagonal similarities have median $-30.5$, so every preference is set to $p=-30.5$ (scikit-learn's default). Damping $\lambda=0.5$.

The data. Highlighted: the two points that become exemplars.

| 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 |

Similarity matrix s(i,k) = −squared distance; the diagonal holds the preference p = −30.5.

| 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)**

1. **Responsibilities.** With $A=0$, $r^{\text{new}}(i,k)=s(i,k)-\max_{k'\ne k}s(i,k')$. Row A's best candidate is C ($-1$), second best B ($-2$). So $r^{\text{new}}(A,C)=-1-(-2)=1$, and for every other $k$: $r^{\text{new}}(A,k)=s(A,k)-(-1)$, e.g. $r^{\text{new}}(A,A)=-30.5+1=-29.5$.
2. Row D: best C ($-2$), second A or B ($-5$), so $r^{\text{new}}(D,C)=3$. Row B gives $r^{\text{new}}(B,C)=1$. Row C itself: $r^{\text{new}}(C,C)=-30.5-(-1)=-29.5$.
3. **Damping.** $R=0.5\cdot 0+0.5\,R^{\text{new}}$: $r(A,C)=0.5$, $r(B,C)=0.5$, $r(D,C)=1.5$, $r(C,C)=-14.75$.
4. **Availabilities for candidate C.** Positive responsibilities into C come from A, B, D: $0.5+0.5+1.5=2.5$. So $a^{\text{new}}(C,C)=2.5$ and $a^{\text{new}}(A,C)=\min(0,\,-14.75+0.5+1.5)=-12.75$. After damping: $a(C,C)=1.25$, $a(A,C)=-6.375$.
5. **Self-evidence.** $r(C,C)+a(C,C)=-14.75+1.25=-13.5<0$. Every point is still negative (G is also $-13.5$, H $-12.75$), so after iteration 1 there are **no exemplars**.
6. **Keep iterating.** Each round, C and G gather more support. At iteration 4 they become the first points with positive self-evidence ($5.81$ and $6.18$) and the exemplar set $\{C,G\}$ then stays unchanged; after 15 unchanged iterations the run stops at iteration 19.

Self-evidence r(k,k) + a(k,k) at iterations 1, 4 and 19 (converged). Only C and G end positive.

| 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**

1. **Labels.** Each non-exemplar joins its most similar exemplar: A, B, D → C (similarities $-1,-1,-2$); E, F, H → G ($-1,-1,-5$).
2. **Net similarity.** $(-1-1-2)+(-1-1-5)+2\times(-30.5)=-11-61=-72$. No other pair of exemplars does better: the best 2-point exemplar set by brute force is also $\{C,G\}$ with member similarity $-11$.
3. **Exemplars are data points.** G $=(7,7)$ represents $\{E,F,G,H\}$ although their mean is $(6.75,7)$ — AP never invents a centre.
4. **New point** $(4,3)$: squared distance 5 to C and 25 to G, so it is assigned to **C's cluster**.

## Watch the messages

> Figure: The worked example, live. Arrows show the candidate each point currently prefers (argmax of a + r); rings mark exemplars; the matrix shows r, a or a + r for the selected iteration; the bottom-left chart traces every point's self-evidence. At the default preference (median, −30.5) and λ = 0.5, C and G cross zero at iteration 4 and the run converges at iteration 19 with net similarity −72. Drag the preference: the bottom-right curve shows 3 exemplars for p ≥ −5, 2 for −127 ≤ p ≤ −6 and 1 (point D) below. Set λ = 0 to see the undamped messages flip between all-exemplars and none for 200 iterations; λ = 0.9 converges to the same answer but needs 38 iterations. Drag any point to re-run everything.

> **What to try in the figure:** Scrub to iteration 1 and switch the matrix to *r*: row A has its only positive entry in column C, exactly as computed by hand. Then push the preference up to $-3$: H, the loose point at $(5,8)$, gets its own exemplar, because joining G costs it $-5$ while opening a cluster costs only $3$. Push it down to $-140$ and a single exemplar, D $=(3,3)$, the point most similar to everyone (column sum $-139$), represents all eight.

## The algorithm, step by step

**AffinityPropagation(S, p, λ)**

1. **Similarities.** Build $S$ with $s(i,k)$ for $i\ne k$ and set the diagonal to the preference (default: median off-diagonal similarity). Set $R=A=0$.
2. **Responsibility update.** For each row $i$, find the largest and second-largest value of $a(i,k)+s(i,k)$. Then $r^{\text{new}}(i,k)=s(i,k)-\text{largest}$, except in the argmax column, where the second largest is used. Damp: $R\leftarrow\lambda R+(1-\lambda)R^{\text{new}}$.
3. **Availability update.** For each column $k$, sum the positive responsibilities $\max(0,r(i',k))$ plus $r(k,k)$. Then $a^{\text{new}}(i,k)=\min(0,\text{column sum}-\max(0,r(i,k)))$ off the diagonal and $a^{\text{new}}(k,k)=\text{column sum}-r(k,k)$. Damp $A$ the same way.
4. **Exemplars.** $E=\{k: r(k,k)+a(k,k)>0\}$.
5. **Stop** when $E$ has not changed for a window of iterations (15 by default) or after max_iter (200); otherwise go to step 2.
6. **Assign** 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 $O(n^2)$ time, and the run is $O(Tn^2)$. Memory is three dense $n\times n$ float matrices: for $n=10{,}000$ that is $3\times10^8\times 8$ bytes $=2.4$ GB. With a **sparse** similarity graph (e.g. each point's nearest neighbours only), messages live only on the edges and the cost becomes $O(T\cdot|\text{edges}|)$.

## Hyperparameters, variants and tuning

Effect of preference and damping on the worked example (our implementation; every run checked against scikit-learn's exemplars).

| 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 $K$; 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 $\ge 0.5$). 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 $n$ (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

```python
import numpy as np

def affinity_propagation(S, preference=None, damping=0.5, max_iter=200, convergence_iter=15):
    S = S.astype(float).copy()
    n = len(S)
    if preference is None:
        preference = np.median(S[~np.eye(n, dtype=bool)])    # median off-diagonal similarity
    np.fill_diagonal(S, preference)
    R = np.zeros((n, n)); A = np.zeros((n, n))
    rows = np.arange(n)
    last, stable = None, 0
    for it in range(1, max_iter + 1):
        # responsibilities: r(i,k) = s(i,k) - max_{k' != k} [a(i,k') + s(i,k')]
        AS = A + S
        best = AS.argmax(1)
        first = AS[rows, best]
        AS[rows, best] = -np.inf
        second = AS.max(1)
        R_new = S - first[:, None]
        R_new[rows, best] = S[rows, best] - second
        R = damping * R + (1 - damping) * R_new
        # availabilities: a(i,k) = min(0, r(k,k) + sum_{i' not in {i,k}} max(0, r(i',k)))
        Rp = np.maximum(R, 0)
        np.fill_diagonal(Rp, R.diagonal())
        A_new = Rp.sum(0)[None, :] - Rp
        self_avail = A_new.diagonal().copy()               # a(k,k) = sum_{i' != k} max(0, r(i',k))
        A_new = np.minimum(A_new, 0)
        np.fill_diagonal(A_new, self_avail)
        A = damping * A + (1 - damping) * A_new
        # exemplars: points whose self-evidence r(k,k) + a(k,k) is positive
        E = tuple(np.flatnonzero((R + A).diagonal() > 0))
        stable = stable + 1 if E == last else 0
        last = E
        if E and stable >= convergence_iter:
            break
    E = np.array(last)
    labels = S[:, E].argmax(1)
    labels[E] = np.arange(len(E))                          # each exemplar labels itself
    return E, labels, it

X = np.array([[1, 2], [2, 1], [2, 2], [3, 3], [7, 6], [8, 7], [7, 7], [5, 8]], float)
S = -((X[:, None, :] - X[None, :, :]) ** 2).sum(-1)       # negative squared distance
E, labels, it = affinity_propagation(S)
print("exemplars:", E, "->", X[E].tolist())               # [2 6] -> [[2.0, 2.0], [7.0, 7.0]]
print("labels:   ", labels)                               # [0 0 0 0 1 1 1 1]
print("iterations:", it)                                  # 19
new = np.array([4, 3])
print("new point (4,3) -> exemplar", E[np.argmax(-((X[E] - new) ** 2).sum(1))])   # 2 (= C)
```

From scratch in NumPy, vectorised updates. Prints exemplars [2 6] (C and G), labels [0 0 0 0 1 1 1 1], 19 iterations, and assigns (4, 3) to exemplar 2.

```python
import numpy as np
from sklearn.cluster import AffinityPropagation

X = np.array([[1, 2], [2, 1], [2, 2], [3, 3], [7, 6], [8, 7], [7, 7], [5, 8]])
ap = AffinityPropagation(damping=0.5, random_state=0).fit(X)   # preference = median similarity
print("exemplars:", ap.cluster_centers_indices_, ap.cluster_centers_.tolist())  # [2 6] [[2, 2], [7, 7]]
print("labels:   ", ap.labels_)                                # [0 0 0 0 1 1 1 1]
print("iterations:", ap.n_iter_)                               # 17
print("predict (4,3):", ap.predict([[4, 3]]))                  # [0]

for pref in [-3, -30.5, -74, -140]:
    m = AffinityPropagation(preference=pref, random_state=0).fit(X)
    print(f"preference {pref:>6}: exemplars {m.cluster_centers_indices_}")
# preference     -3: exemplars [2 6 7]
# preference  -30.5: exemplars [2 6]
# preference    -74: exemplars [2 6]
# preference   -140: exemplars [3]
```

scikit-learn on the same data. Same exemplars and labels; scikit-learn reports n_iter_ = 17 because it counts its convergence window slightly differently and adds tiny noise to S to break ties.

> **Any similarity, via precomputed:** Pass `affinity="precomputed"` and an n × n matrix of similarities (higher = more similar) to cluster strings, graphs or embeddings. Remember to negate distances, and to set `preference` on the same scale as your similarities.

**Strengths**

- 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.

**Limitations**

- $n$ is large: $O(n^2)$ memory and time per iteration rule it out beyond roughly $10^4$ 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.

- **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.

> **Undamped messages oscillate:** With $\lambda=0$ the worked example never converges: the messages flip between "all 8 points are exemplars" and "none are" on alternate iterations, for all 200 iterations. If a run hits max_iter, scikit-learn raises a *did not converge* ConvergenceWarning and returns whatever exemplars the last iteration had — possibly degenerate, or label $-1$ for every point if none emerged. Raise damping toward 0.9 and increase max_iter rather than ignoring the warning.

> **The preference is on the similarity scale:** A preference of $-30.5$ is meaningful only relative to these similarities. Rescale the features, or change from squared to plain distance, and the same number gives a different K. Set the preference from the data (median, min, or quantiles of $s$), never as a fixed constant copied from another project.

> **Stable is not the same as converged:** AP stops when the exemplar set is unchanged for convergence_iter iterations. With heavy damping (0.95) or a preference near the largest similarities, messages move so slowly that an early, wrong exemplar set can stay unchanged for 15 iterations and the run stops on it. Increase convergence_iter when you raise damping.

**Question:** In the worked example ($p=-30.5$, $\lambda=0.5$), what is $r(D,C)$ after the first iteration?

- A. 3
- B. 1.5
- C. −2
- D. −14.75

**Answer:** B. 1.5 — With $A=0$: D's best candidate is C ($-2$), second best A or B ($-5$), so $r^{\text{new}}(D,C)=-2-(-5)=3$. Damping gives $0.5\cdot0+0.5\cdot3=1.5$.

**Question:** You raise every preference from the median similarity toward 0. What happens?

- A. Fewer clusters
- B. More clusters
- C. The same clusters, faster
- D. The exemplars move to the cluster means

**Answer:** B. More clusters — The preference is what each exemplar contributes to the objective. A less negative value makes opening an exemplar cheaper and raises every $r(k,k)$, so more points reach positive self-evidence. In the example, $p=-3$ gives 3 exemplars instead of 2.

**Question:** In the example, one exemplar (D) gives net similarity $-139+p$ and two (C, G) give $-11+2p$. Below which preference does AP prefer a single cluster?

- A. −11
- B. −30.5
- C. −74
- D. −128

**Answer:** D. −128 — $-139+p>-11+2p \iff p<-128$. The figure's sweep confirms it: 2 exemplars down to $p=-127$, one exemplar from $-128$.

**Question:** Point $k$ is declared an exemplar when…

- A. $a(k,k)>0$
- B. $r(k,k)+a(k,k)>0$
- C. it is closest to its cluster's mean
- D. $s(k,k)$ is the largest value in its row

**Answer:** B. $r(k,k)+a(k,k)>0$ — The self-evidence $r(k,k)+a(k,k)$ is the max-sum belief that $k$ is better off choosing itself. $a(k,k)$ alone only measures support from others, which is never negative.

**Key points**

- Exemplars are real data points; every point is a candidate from the start, so there is no random initialisation.
- Responsibility $r(i,k)=s(i,k)-\max_{k'\ne k}[a(i,k')+s(i,k')]$; availability $a(i,k)=\min(0,r(k,k)+\sum_{i'\notin\{i,k\}}\max(0,r(i',k)))$.
- $k$ is an exemplar when $r(k,k)+a(k,k)>0$; 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 $O(n^2)$ time per iteration and $O(n^2)$ memory — fine for thousands of points, not millions.

---

From MLFoundry (https://www.mlfoundry.in). The web page adds interactive figures and diagrams.
