We have developed a new regularization method for the sparse representation and denoising of seismic data. Our approach is based on two components: 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 (DL) 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. We have developed two algorithms for DL based on clustering and singular-value decomposition, called the first and second dictionary constructions. Besides using an adapted dictionary, we also consider a similarity measure for the local geometric structures of the seismic data using the Laplacian matrix of a graph. Our method achieves better denoising performance than existing denoising methods, in terms of peak signal-to-noise ratio values and visual estimation of weak-event preservation. Comparisons of experimental results on field data using traditional - deconvolution (FX-Decon) and curvelet thresholding methods are also provided.