In recent years graph-based methods have seen success in different machine learning applications, including clustering, dimensionality reduction and semi-supervised learning. In these methods a graph is associated to a data set, after which certain aspects of the graph are used for various machine learning tasks. It is, however, important to observe that such graphs are empirical objects corresponding to a randomly chosen set of data points. In my talk I will discuss some of our work on using spectral graph methods for dimensionality reduction and semi-supervised learning and certain theoretical aspects of these methods, in particular, when data is sampled from a low-dimensional manifold.