Affinity Propagation

Unlike K-Means which creates synthetic centroids, Affinity Propagation selects real data points as cluster centers. These exemplars are the most representative members of their clusters. In patient stratification, an exemplar might be a patient whose molecular profile best represents a specific disease endotype, providing clinicians with a tangible reference case rather than an abstract average.

The algorithm converges through two types of messages exchanged between data points:

• Responsibility (r): Sent from point i to candidate exemplar k, quantifying how well-suited k is to serve as the exemplar for i, accounting for other potential exemplars.
• Availability (a): Sent from candidate exemplar k to point i, reflecting the accumulated evidence that k would be a good exemplar, considering support from other points. This iterative process continues until cluster assignments stabilize.

The preference value s(k,k) is the single most critical hyperparameter. It represents the a priori suitability of point k to serve as an exemplar. A higher preference leads to more clusters; a lower preference yields fewer. A common heuristic is to set all preferences to the median of the input similarities, which typically produces a moderate number of clusters. This parameter effectively controls the granularity of patient subgroup discovery.

Affinity Propagation operates on a similarity matrix s(i,k) rather than raw feature vectors. The similarity s(i,k) indicates how well point k is suited to be the exemplar for point i. Common choices include:

• Negative squared Euclidean distance: s(i,k) = -||x_i - x_k||²
• Cosine similarity for high-dimensional omics data
• Correlation-based measures for gene expression profiles This abstraction allows the algorithm to cluster any data type where pairwise similarities can be defined.

To prevent numerical oscillations during message passing, a damping factor λ (typically between 0.5 and 0.9) is applied. Each new message is a weighted combination of the previous value and the newly computed value:

• r_new = λ·r_old + (1-λ)·r_current
• a_new = λ·a_old + (1-λ)·a_current Higher damping values increase stability but slow convergence. This is essential when clustering noisy clinical data where oscillations can prevent termination.

A defining advantage for exploratory biomarker discovery: the algorithm automatically determines the number of clusters based on the data structure and preference parameter. This is critical when the true number of disease subtypes is unknown. Unlike K-Means, which forces a predetermined k, Affinity Propagation lets the data reveal its natural granularity, making it ideal for unbiased endotype discovery in heterogeneous patient populations.

Unlike centroid-based methods like K-Means, Affinity Propagation identifies actual data points as exemplars to represent clusters. This is biologically intuitive for patient stratification, where an archetypal patient profile is more interpretable than a mathematical centroid. The algorithm simultaneously considers all points as potential exemplars, making it less sensitive to initialization but computationally intensive for large cohorts.

The preference value, set on the diagonal of the similarity matrix, is the critical hyperparameter. It controls how many clusters are formed:

• Higher preference: Each point is more likely to become an exemplar, resulting in many fine-grained clusters.
• Lower preference: Fewer points are chosen as exemplars, producing broader groupings. In biomarker discovery, this is often tuned using the Silhouette Score to balance granularity with clinical utility.

To prevent numerical oscillations during message passing, a damping factor (λ) between 0.5 and 1 is applied. This blends new messages with old ones: new_message = λ * old_message + (1 - λ) * calculated_message Higher damping ensures stability but slows convergence. In genomic datasets with high noise, a damping factor of 0.9 is often required to achieve a stable molecular taxonomy.

Affinity Propagation operates on a similarity matrix s(i,k) that quantifies how well point k serves as an exemplar for point i. Common metrics include:

• Negative Euclidean Distance: Standard for continuous clinical variables.
• Pearson Correlation: Robust for gene expression data.
• Jaccard Index: For binary mutation profiles. The choice of metric directly shapes the resulting patient similarity networks and downstream endotype discovery.

Affinity Propagation vs. K-Means: Does not require pre-specifying the number of clusters and is not sensitive to initial centroid placement. Affinity Propagation vs. DBSCAN: Does not require a density threshold (epsilon) and can handle non-globular clusters, but DBSCAN is better at explicitly identifying outlier patients as noise. Affinity Propagation vs. Hierarchical Clustering: Provides a flat, non-nested partition with exemplars, whereas hierarchical methods produce a dendrogram useful for visualizing nested disease subtypes.