We begin with a well known algorithm, Laplacian Eigenmaps, and then proceed to extend it in two independent directions. First, we generalize this algorithm to allow for the use of partially labeled data, and establish the theoretical foundation of the resulting semi-supervised learning method. Second, we consider two ways of accelerating the most computationally intensive step of Laplacian Eigenmaps, the construction of an adjacency graph. Both of them produce high quality approximations, and we conclude by showing that they work well together to achieve a dramatic reduction in computational time.