Stability of Laplacian Fourier basis on irregular graphs

[pinkfloyd06]

Hello @mdeff ,

MNIST data are defined on 2D grid. Hence, we build graph on MNIST by supposing that each pixel is a node and the max number edges per node is 8. Hence, we have a regular and fixed graphs.

The Fourier basis is obtained by computing the Laplacian of the graph. Since the graphs are regulars, you pick at random a graph encoding an exemple of MNIST and compute its laplacian. This latter is used as the Fourier basis of MNIST.

1. Why we don't compute the laplacian of each training exemple ?
2. How do you explain that taking any Laplacian of MNIST example represents the Fourier Basis of the whole data ? Is there any effect on the stability of the Fourier Basis ? Does it apply also to irrigular graphs ?

Thank you for your answer.

[mdeff]

All Laplacians are the same as every MNIST image is supported by the same 28x28 grid graph. For learned filters to generalize across different graphs/Laplacians, you make the hypothesis that the graphs are sampled from the same underlying continuous space.