how can we represent a Big Data set in Graph Signals. (Big Data in Graph signal Processing)
Just read it myself.  The justification for using the term, "Fourier Transform" comes from the idea that for a discrete time periodic time series, convolution reduces to a sequence of circulant shifts and inner products.  The "filters' correspond to diagonal matrices, so when he forms his data structures, the matrix eigendecomposition  is "equivalent" to a DFT.  The circulant shift matrix is the justification for using the word "Fourier".  When I was reading through the paper, I recalled that there is something called spectral graph theory where you do SVD (or orthogonal decompositions) on adjacency matrices, and the singular values (or eigenvalues) have some sort of significance.  This paper appears to show how graph products where one of the graphs corresponds to periodic sequences has meaningful Fourier interpretation. There are papers on graph polynomials as well.  

The example didn't particularly enthuse me with a burning desire to master the subject, but I have notices a growing literature associated with anomaly detection. I have a tendency toward cynicism which is often misguided.

To answer the question that I think you asked:

You can do an orthogonal decomposition on any adjacency matrix ( directed, undirected, acyclic, and with cycles) but to be a proper DFT abstraction, you need a cyclic matrix (graph) someplace.  

The only concern I had with the paper (other than my partial understanding) was with the efficiency claims associated with sparse matrices.  Sparse matrices involve a lot pointer chasing and modern parallel vector processors that do dense linear algebra very well are not that great with sparse linear algebra.  Thread based architectures like GPU's seem better.