We study the use of spectral techniques for graph partitioning. Let G=(V,E) be a graph whose vertex set has a ``latent'' partition V_1,...,V_k. Moreover, consider a ``density matrix'' E=(E_vw)_{v,w in V} such that for v in V_i and w in V_j the entry E_{vw} is the fraction of all possible V_i-V_j-edges that are actually present in G. We show that on input (G,k) the partition V_1,...,V_k can (almost) be recovered in polynomial time via spectral methods, provided (essentially) that E approximates the adjacency matrix of G sufficiently well. This result in particular applies to sparse graphs with bounded average degree as n=#V tends to infinity, and it yields interesting consequences on partitioning random graphs.