By transforming data into a new domain, techniques from statistics and signal processing such as principle components analysis and Fourier, wavelet, time-frequency, and curvelet transforms can sparsely represent and reveal relevant structural properties of time series, audio signals, images, and other data that live on regular Euclidean spaces. Such transform methods prove useful in compression, denoising, inpainting, pattern recognition, classification, and other signal processing and machine learning tasks. Unfortunately, naively applying these “classical” techniques to data on graphs would ignore key dependencies arising from irregularities in the graph data domain, and result in less informative and less sparse representations of the data. A key challenge in graph signal processing is therefore to incorporate the graph structure of the underlying data domain into dictionary designs, while still leveraging intuition from classical computational harmonic analysis techniques. In this talk, I will motivate the dictionary design problem for graph signals, examine some recently proposed dictionaries for graph signals, and discuss open issues and challenges.