  Kernel-based non-linear dimensionality reduction methods, such as Local
Linear Embedding (LLE) and Laplacian Eigenmaps, rely heavily upon pairwise
distances or similarity scores, with which one can construct and study a
weighted graph associated with the dataset. When each individual data object
carries additional structural details, however, the correspondence relations
between these structures provide extra information that can be leveraged for
studying the dataset using the graph. Based on this observation, we generalize
Diffusion Maps (DM) in manifold learning and introduce the framework of
Horizontal Diffusion Maps (HDM). We model a dataset with pairwise structural
correspondences as a fibre bundle equipped with a connection. We demonstrate
the advantage of incorporating such additional information and study the
asymptotic behavior of HDM on general fibre bundles. In a broader context, HDM
reveals the sub-Riemannian structure of high-dimensional datasets, and provides
a nonparametric learning framework for datasets with structural
correspondences.
