Wavelets on Graphs via Spectral Graph Theory

We propose a novel method for constructing wavelet transforms of functions defined on the vertices of an arbitrary finite graph. We define a notion of scaling using the graph analogue of the Fourier domain, namely the space of eigenfunctions forming the spectral decomposition of the discrete graph Laplacian $\L$. Given an arbitrary measurable function g, the spectral decomposition allows one to define the operator $T_g=g(\L)$. Scaling by $t$ may then be defined by $T_g^t = g(t\L)$. Our graph wavelets $W_{t,j}$ at scale $t$ and $j$ are produced by localizing this operator to the vertex $j$ by $W_{t,j}=g(t\L)\delta_j$, where $\delta_j$ is the indicator function for the vertex $j$. We explore the localization properties of the wavelets in the limit of fine scales, and show that the scale can be discretized to yield a frame. We give an example of this construction applied to a cortical connection graph, yielding "cortical graph wavelets".