  Affinity propagation is an exemplar-based clustering algorithm that finds a
set of data-points that best exemplify the data, and associates each datapoint
with one exemplar. We extend affinity propagation in a principled way to solve
the hierarchical clustering problem, which arises in a variety of domains
including biology, sensor networks and decision making in operational research.
We derive an inference algorithm that operates by propagating information up
and down the hierarchy, and is efficient despite the high-order potentials
required for the graphical model formulation. We demonstrate that our method
outperforms greedy techniques that cluster one layer at a time. We show that on
an artificial dataset designed to mimic the HIV-strain mutation dynamics, our
method outperforms related methods. For real HIV sequences, where the ground
truth is not available, we show our method achieves better results, in terms of
the underlying objective function, and show the results correspond meaningfully
to geographical location and strain subtypes. Finally we report results on
using the method for the analysis of mass spectra, showing it performs
favorably compared to state-of-the-art methods.
