We propose a method for applying deep learning on problem domains which exhibit an irregular spatial topology. By utilizing a graph-based representation of the problem domain, we can define the spatial convolution operation in the spectral domain of the graph Laplacian. We also explore the graph construction methods for specific problem domains and the graph coarsening methods used as an analogy to the spatial pooling operators of conventional convolutional neural networks. We are exploring the application of such graph-based deep learning on a wide variety of problem domains, from sensor networks to human behavioral analysis.