Graph Wavelets are localized, multi-scale basis functions defined on graphs that enable simultaneous localization in both the vertex (spatial) domain and the spectral (frequency) domain — overcoming the fundamental limitation of the Graph Fourier Transform, which provides perfect frequency localization but zero spatial localization, enabling targeted analysis of graph signals at specific locations and specific scales.

What Are Graph Wavelets?

• Definition: Graph wavelets are constructed by scaling and localizing a mother wavelet function on the graph using the spectral domain. The Spectral Graph Wavelet Transform (SGWT) defines wavelet coefficients at node $n$ and scale $s$ as: $W_f(s, n) = sum_{l=0}^{N-1} g(slambda_l) hat{f}(lambda_l) u_l(n)$, where $g$ is a band-pass kernel, $lambda_l$ and $u_l$ are the Laplacian eigenvalues and eigenvectors, and $hat{f}$ is the graph Fourier transform of the signal.
• Spatial-Spectral Trade-off: The Graph Fourier Transform decomposes a signal into global frequency components — the $k$-th eigenvector oscillates across the entire graph, providing no spatial localization. Graph wavelets achieve a balanced trade-off: at large scales, they capture smooth, community-level variations; at small scales, they detect sharp local features — all centered around a specific vertex.
• Multi-Scale Analysis: Just as classical wavelets decompose a time series into coarse (low-frequency) and fine (high-frequency) components, graph wavelets decompose a graph signal across multiple scales — revealing hierarchical structure from the global community level down to individual node anomalies.

Why Graph Wavelets Matter

• Anomaly Detection: Graph Fourier analysis detects that a high-frequency component exists but cannot tell you where on the graph it occurs. Graph wavelets pinpoint both the frequency and the location — "there is a high-frequency anomaly at Node 42" — enabling targeted investigation of local irregularities in sensor networks, financial transaction graphs, and social networks.
• Signal Denoising: Classical wavelet denoising (thresholding small coefficients) extends naturally to graph signals through graph wavelets. Noise manifests as small-magnitude high-frequency wavelet coefficients — zeroing them out removes noise while preserving the signal's large-scale structure, outperforming simple Laplacian smoothing which cannot distinguish signal from noise at specific scales.
• Graph Neural Network Design: Graph wavelet-based neural networks (GraphWave, GWNN) use wavelet coefficients as node features or define wavelet-domain convolution — providing multi-scale receptive fields without stacking many message-passing layers. A single wavelet convolution layer captures information at multiple scales simultaneously, whereas standard GNNs require $K$ layers to capture $K$-hop information.
• Community Boundary Detection: Large-scale wavelet coefficients are large at nodes on community boundaries — where the signal transitions sharply between groups. This provides a principled method for edge detection on graphs, complementing spectral clustering (which identifies communities) with boundary identification (which identifies transition zones).

Graph Wavelets vs. Graph Fourier

Graph Wavelets are local zoom lenses for networks — enabling targeted multi-scale analysis at specific graph locations and specific frequency bands, providing the spatial-spectral resolution that global Fourier methods fundamentally cannot achieve.