As I understand, there are two major methods of constructing wavelets on graphs. Spectral wavelets, from David K Hammond et. al, and diffusive wavelets from Coifman and Maggioni. I can't quite parse out any advantage one construction has over the other, which applications each is more suited for etc.

The Hammond paper states:

The largest difference between their (refering to Coifman) work and ours is that the diffusion wavelets are designed to be orthonormal. This is achieved by running a localized orthogonalization procedure after applying dyadic powers of T at each scale to yield nested approximation spaces, wavelets are then produced by locally orthogonalizing vectors spanning the difference of these approximation spaces. While an orthogonal transform is desirable for many applications, notably operator and signal compression,the use of the orthogonalization procedure complicates the construction of the transform, and somewhat obscures the relation between the diffusion operator T and the resulting wavelets.

But this feels like a very fuzzy and unclear argument. I'd be curious if anyone has experience working with either one and can speak to advantages/disadvantages for graph signal processing (ie whole graph classification, node feature regression, graph generation, etc).


EDIT: Perhaps one way to analyse this is via the difference between a graph Fourier transform and a random walk? Afiak, computing a full fourier transform of a graph is expensive, since it requires diagonalising the normalized graph laplacian. So, we instead use a first order approximation with Chebychev polynomials (ie David K Hammond et. al). Then, instead of using what are essentially Fourier features, we could use features derived from a random walk (ie Coifman and Maggioni), along the lines of something like node2vec.

Is boiling down the difference between these two methods to Fourier features vs random walk a valid interpretation/understanding?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.