Dual Rooted-Diffusions for Clustering and Classification on Manifolds

We introduce a new similarity measure between data points suited for clustering and classification on smooth manifolds. The proposed measure is constructed from a dual rooted graph diffusion over the feature vector space, obtained by growing dual rooted minimum spanning trees (MST) between data points. This diffusion model for pairwise affinities naturally accommodates the case where the feature distribution is supported on a lower dimensional manifold. When this affinity measure is combined with labeled data, a semi-supervised classifier can be defined that handles both labeled and unlabeled data in a seamless manner. We will illustrate our method for both simulated ground truth and real partially labeled data sets.