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 data set. When each individual data object carries structural details, the correspondence relations between these structures provide additional information that can be leveraged for studying the data set using the graph. We generalize Diffusion Maps (DM) in manifold learning and introduce the framework of Horizontal Diffusion Maps (HDM). We model a data set with pairwise structural correspondences as a fibre bundle equipped with a connection. We further 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 data sets, and provides a nonparametric learning framework for data sets with structural correspondences.