Electroencephalography (EEG) data entail a complex spatiotemporal structure that reflects ongoing organization of brain activity. Characterization of the spatial patterns is an indispensable step in numerous EEG processing pipelines. We present a novel method for transforming EEG data into a spectral representation. First, we learn subject-specific graphs from each subject’s EEG data. Second, by eigendecomposition of the normalized Laplacian matrix of each subject’s graph, an orthonormal basis is obtained using which any given EEG map of the subject can be decomposed, providing a spectral representation of the data. We show that energy of EEG maps is strongly associated with low frequency components of the learned basis, reflecting the smooth topography of EEG maps. As a proof-of-concept for this alternative view of EEG data, we consider the task of decoding two-class motor imagery (MI) data. To this aim, the spectral representations are first mapped into a discriminative subspace for differentiating two-class data using a projection matrix obtained by the Fukunaga–Koontz transform (FKT). An SVM classifier is then trained and tested on the resulting features to differentiate MI classes. The method is benchmarked against features extracted from a subject-specific functional connectivity matrix as well as four alternative MI-decoding methods on Dataset IVa of BCI Competition III. Experimental results show the superiority of the proposed method over alternative approaches in differentiating MI classes, reflecting the added benefit of (i) decomposing EEG data using data-driven, subject-specific harmonic bases, and (ii) accounting for class-specific temporal variations in spectral profiles.