GraphFourierTransformation

The graph Fourier transform (GFT) is a generalization of the classical Fourier transform for signals defined on the nodes of a graph. It represents a graph signal in a spectral domain determined by the eigenvectors of a graph Laplacian or a related operator. Given a graph G with n nodes, a signal x in R^n, and the Laplacian L with eigen-decomposition L = UΛU^T, the GFT is defined as x̂ = U^T x, and the inverse transform is x = U x̂.

Common choices of Laplacians include the unnormalized L = D − A and the symmetric normalized L_sym = I − D^−1/2 A D^−1/2, where A is the adjacency matrix and D is the degree matrix. The eigenvalues Λ form a spectrum that plays the role of frequencies: small eigenvalues correspond to smooth variations across edges, while large eigenvalues reflect rapid changes. The GFT coefficients x̂ describe the signal’s content at each graph frequency, and the set of eigenvectors U provides the basis for reconstruction and analysis.

In practice, computing the full eigen-decomposition is costly for large graphs, so methods based on polynomial approximations (for example, Chebyshev polynomials) or iterative solvers are used. When L is symmetric, the transform is unitary and energy is preserved (Parseval’s theorem); the inverse transform is stable under appropriate conditions.

Applications of the GFT span graph signal processing, including denoising, compression, and semi-supervised learning, as well as the spectral foundations of graph neural networks. Extensions exist for directed or weighted graphs, and alternative operators can be employed to tailor the transform to specific graph structures or domains.

Foundational work establishing the GFT includes the development of spectral graph theory and its use in graph signal processing, notably the contributions by Shuman, Narang, Frossard, Ortega, and Vandergheynst (2013) and related developments such as Hammond, Vandergheynst, and Gribonval (2011) on related spectral concepts.