  Manifold learning methods play a prominent role in nonlinear dimensionality
reduction and other tasks involving high-dimensional data sets with low
intrinsic dimensionality. Many of these methods are graph-based: they associate
a vertex with each data point and a weighted edge between each pair of close
points. Existing theory shows, under certain conditions, that the Laplacian
matrix of the constructed graph converges to the Laplace-Beltrami operator of
the data manifold. However, this result assumes the Euclidean norm is used for
measuring distances. In this paper, we determine the limiting differential
operator for graph Laplacians constructed using $\textit{any}$ norm. The proof
involves a subtle interplay between the second fundamental form of the
underlying manifold and the convex geometry of the norm's unit ball. To
motivate the use of non-Euclidean norms, we show in a numerical simulation that
manifold learning based on Earthmover's distances outperforms the standard
Euclidean variant for learning molecular shape spaces, in terms of both sample
complexity and computational complexity.
