A windowed graph Fourier transform (2012) | Hacker News Reader

A windowed graph Fourier transform (2012)

ieeexplore.ieee.org

65 pointsteleforce6 comments

Open articleView on HN

A similar and more recent example of graph decomposition is the fast graphlet transform:

https://github.com/fcdimitr/fglt

This algorithm has a nice Algebraic formulation recently implemented with the GraphBLAS in LAGraph:

https://github.com/GraphBLAS/LAGraph/blob/stable/experimenta...

Sidestepping Signin:

https://sci-hub.ru/10.1109/SSP.2012.6319640

https://sci-hub.st/10.1109/SSP.2012.6319640

.. and for something not quite completely different:

    Wavelet theory has its origin in several disciplines; the types of functions that are now called wavelets were studied in quantum field theory, signal analysis, and function space theory. In all these areas, wavelet-like algorithms replaced the classical Fourier-type expansion of a function. It was not until the mid-1980s that these, at first, seemingly different notions were described in a unified manner. Because of the restricted scope of this monograph, we will not be able to address some ramifications of wavelet bases for so-called wavelet frames.

    The wavelet transform is an alternative to the classical windowed Fourier transform.

    [ ... ]

https://www.sciencedirect.com/science/article/abs/pii/B97801...

I'm unclear on why I would want to "translate" a "signal" on an arbitrary weighted graph such as the Minnesota road map example, in the same sense that I might multiply a time-domain signal by a complex exponential to translate it to a higher or lower frequency in the frequency domain. The latter is an everyday operation in signal processing but what does it mean in other contexts?

Are there any good concrete examples of what such a translation would accomplish?

It is related to spectral graph theory where associations between graph theory and linear algebra are being made where typically power iteration algoritm is then applied not unlike the venerable PageRank algorithm [1].

[1] The Power Iteration Algorithm in Practice:

https://scicoding.com/the-power-iteration-algorithm-in-pract...

That's interesting, but it doesn't answer my question. I think I'm missing too many prereqs on this one, unfortunately.

If you are familiar with conventional spectral analysis, there are higher order spectral analysis. For example before feeding data to your machine learning or AI pipeline, you want transform the waveforms (EM, sound, etc) raw data into higher order spectral to provide more features hence better accuracy. You can use the raw data by simply using the scalar values namely amplitude, time and frequency but the accuracy is much better if you can use the higher order analysis of tine-frequency for examples short time Fourier Transform or spectogram (linear time-frequency), wavelet (time-scale) or the non-linear Cohen class (bilinear time-frequency e.g Wigner-Ville) [1].

But if your data is not a waveform but network (road traffic network, Internet network, sensor networks, etc), similarly you probably better off with higher order graph or hypergraph [2]. In this paper it proposed a linear transformation of graph networks using a new windowed graph Fourier Transform analogous to spectogram, but the spectral in graph here is not the waveform spectrum but the eigenvalues for the matrix representation of the graph. There were discussions few months back in HN on higher order graph or hypergraph approach for analyzing big data [3].

[1] Higher-order spectra analysis : a nonlinear signal processing framework:

https://www.semanticscholar.org/paper/Higher-order-spectra-a...

[2] Hypergraph:

https://en.m.wikipedia.org/wiki/Hypergraph

[3] How big data carried graph theory into new dimensions:

https://news.ycombinator.com/item?id=38120497

Reply on news.ycombinator.com