Geometric Affinity Propagation for Clustering with Network Knowledge
  Clustering data into meaningful subsets is a major task in scientific data
analysis. To date, various strategies ranging from model-based approaches to
data-driven schemes, have been devised for efficient and accurate clustering.
One important class of clustering methods that is of a particular interest is
the class of exemplar-based approaches. This interest primarily stems from the
amount of compressed information encoded in these exemplars that effectively
reflect the major characteristics of the respective clusters. Affinity
propagation (AP) has proven to be a powerful exemplar-based approach that
refines the set of optimal exemplars by iterative pairwise message updates.
However, a critical limitation is its inability to capitalize on known
networked relations between data points often available for various scientific
datasets. To mitigate this shortcoming, we propose geometric-AP, a novel
clustering algorithm that effectively extends AP to take advantage of the
network topology. Geometric-AP obeys network constraints and uses max-sum
belief propagation to leverage the available network topology for generating
smooth clusters over the network. Extensive performance assessment reveals a
significant enhancement in the quality of the clustering results when compared
to benchmark clustering schemes. Especially, we demonstrate that geometric-AP
performs extremely well even in cases where the original AP fails drastically.
