Clustering by transitive propagation
This work addresses clustering challenges in scenarios with pairwise relationship data, such as mutational sequencing, but appears incremental as it builds on existing optimization and transitivity concepts.
The paper tackles the problem of clustering data using pairwise likelihood ratios by introducing a global optimization algorithm that enforces transitivity constraints, resulting in an O(N^3) algorithm based on max-sum message passing.
We present a global optimization algorithm for clustering data given the ratio of likelihoods that each pair of data points is in the same cluster or in different clusters. To define a clustering solution in terms of pairwise relationships, a necessary and sufficient condition is that belonging to the same cluster satisfies transitivity. We define a global objective function based on pairwise likelihood ratios and a transitivity constraint over all triples, assigning an equal prior probability to all clustering solutions. We maximize the objective function by implementing max-sum message passing on the corresponding factor graph to arrive at an O(N^3) algorithm. Lastly, we demonstrate an application inspired by mutational sequencing for decoding random binary words transmitted through a noisy channel.