We propose a new regularization method for the sparse representation and denoising of seismic data. Our approach is based on a sparse data representation in a learned dictionary and a similarity measure for image patches that is evaluated using the Laplacian matrix of a graph. Dictionary learning methods aim to find a data-dependent basis or a frame that admits a sparse data representation while capturing the characteristics of the given data. Our algorithms for dictionary learning are based on clustering and singular value decomposition. We achieve very good denoising performance for seismic data, both in terms of peak signal-to-noise ratio values and visual estimation of weak event preservation.