I have read this article https://pdfs.semanticscholar.org/65d6/1afd9c35b0a75d9de77c2a4a2428af0f7f7b.pdf about Big Data analysis in Graph Signal Processing

I have a couple of questions :

first of all, consider a big dataset which is given to us, it has 150 rows and 365 columns which are sensor measurements and days of one year respectively($D$).

In Example Application section it tries to represent the big dataset in the product of two graphs (the article introduces 3 types of products but I think the dataset have been tested on the Cartesian product). It breake the data set into two graphs (time series($T$) with 365 nodes and the sensor network($A$) with 150 nodes).

Because there was no tag named Graph signal processing, I could not mention it.

the article has represented this two graph in FIG1 a,b.

Now my question :

if I correctly understand!

if there was no time we just need to decompose the sensor matrix ($A$) and after that, we could take Fourier transform, now during the time we just have more samples from our sensors so why we should eig-decompose our product($T \cdot A$) instead of sensor network($A$). I mean how increasing the number of sensor data from our sensors, represents itself in graph product.

or why matrix $D$ can be broken to ${T, A}$?(and definitely ${T,A}$ can be processed parallelly)

I would appreciate your solutions.


1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.