Spectral Graph Theory Fundamentals for GNNs

Spectral graph theory offers a method for analyzing graph properties by examining their frequency components. This approach is fundamental to comprehending the first generation of Graph Neural Networks, specifically spectral GNNs. It also delivers important information about graph structure and signal processing on graphs.

At the core of spectral graph theory lies the Graph Laplacian matrix. It's a matrix representation of a graph that captures essential structural information. There are several variants, but two are particularly relevant for GNNs:

1. Combinatorial Laplacian ($L$): Defined as $L = D - A$, where $D$ is the diagonal degree matrix ($D_{ii} = \text{degree}(v_i)$) and $A$ is the adjacency matrix.
2. Symmetric Normalized Laplacian ($L_{sym}$): Defined as $L_{sym} = D^{-1/2} L D^{-1/2} = I - D^{-1/2} A D^{-1/2}$, where $I$ is the identity matrix. This version is often preferred because its eigenvalues are bounded between 0 and 2, making analysis and learning more stable. $D^{-1/2}$ is the diagonal matrix with entries $(D^{-1/2})_{ii} = 1 / \sqrt{\text{degree}(v_i)}$. For isolated nodes (degree 0), we typically set the corresponding entry to 0.

The Laplacian matrix, particularly $L_{sym}$, is a real, symmetric, and positive semi-definite matrix. This means it has a full set of real, non-negative eigenvalues and corresponding orthogonal eigenvectors.

Eigen-decomposition of the Laplacian

The main insight from spectral graph theory is that we can decompose the normalized Laplacian $L_{sym}$ using its eigenvalues and eigenvectors:

$$L_{sym} = U \Lambda U^T$$

Let's break down these components for a graph with $N$ nodes:

• $\Lambda = \text{diag}(\lambda_1, \lambda_2, ..., \lambda_N)$ is the diagonal matrix containing the eigenvalues of $L_{sym}$. These are real and non-negative, typically sorted as $0 = \lambda_1 \le \lambda_2 \le ... \le \lambda_N \le 2$. The eigenvalues are often interpreted as the frequencies of the graph.
• $U = [\mathbf{u}_1, \mathbf{u}_2, ..., \mathbf{u}_N]$ is an orthogonal matrix ($U^T U = U U^T = I$) whose columns $\mathbf{u}_i$ are the corresponding eigenvectors. These eigenvectors form an orthonormal basis for $\mathbb{R}^N$. They are sometimes called the graph Fourier modes.

The eigenvectors represent fundamental patterns or modes of variation over the graph. Eigenvectors associated with small eigenvalues (low frequencies) vary smoothly across connected nodes, while eigenvectors associated with large eigenvalues (high frequencies) oscillate rapidly between neighboring nodes. The magnitude of the eigenvalue $\lambda_i$ quantifies the smoothness of the corresponding eigenvector $\mathbf{u}_i$ across the edges. Specifically, $\lambda_i = \mathbf{u}_i^T L_{sym} \mathbf{u}_i$ measures the variation of $\mathbf{u}_i$.

An example eigenvector for a cycle graph (C4). Node colors indicate the eigenvector values (e.g., red for negative, blue for positive). This eigenvector corresponds to a higher frequency ($\lambda=2$) and shows alternating values between neighbors. Eigenvectors for lower frequencies would exhibit smoother transitions.

The Graph Fourier Transform (GFT)

Just as the classical Fourier transform decomposes a signal into its frequency components using sine and cosine basis functions, the Graph Fourier Transform (GFT) decomposes a graph signal using the Laplacian eigenvectors as the basis.

A graph signal is simply a function defined on the nodes of the graph, represented as a vector $\mathbf{x} \in \mathbb{R}^N$, where $x_i$ is the value or feature associated with node $v_i$.

The GFT of a signal $\mathbf{x}$ is defined as its projection onto the eigenvectors $U$:

$$\hat{\mathbf{x}} = U^T \mathbf{x}$$

The resulting vector $\hat{\mathbf{x}}$ is the representation of the signal $\mathbf{x}$ in the graph spectral domain. Each component $\hat{x}_i = \mathbf{u}_i^T \mathbf{x}$ measures the strength of the $i$-th graph Fourier mode $\mathbf{u}_i$ within the signal $\mathbf{x}$.

The inverse GFT allows us to reconstruct the original signal from its spectral representation:

$$\mathbf{x} = U \hat{\mathbf{x}} = U U^T \mathbf{x}$$

This establishes a direct analogy between classical Fourier analysis and signal processing on graphs.

Spectral Convolution on Graphs

The concept of convolution is fundamental in classical signal processing, often used for filtering. The Convolution Theorem states that convolution in the spatial (or time) domain is equivalent to element-wise multiplication in the frequency (or spectral) domain.

We can define an analogous operation for graphs using the GFT. Let $\mathbf{x}$ be a graph signal and $\mathbf{g}$ be a filter signal. Their spectral convolution $*_{\mathcal{G}}$ is defined as performing multiplication in the spectral domain and then transforming back using the inverse GFT:

$$\mathbf{g} *_{\mathcal{G}} \mathbf{x} = U ( (U^T \mathbf{g}) \odot (U^T \mathbf{x}) ) = U (\hat{\mathbf{g}} \odot \hat{\mathbf{x}})$$

Here, $\odot$ represents the element-wise Hadamard product.

In the context of GNNs, we are typically interested in applying a learnable filter to the node features (our graph signal). Instead of defining the filter $\mathbf{g}$ directly in the spatial domain, spectral GNNs define the filter in the spectral domain through a function $g_\theta(\cdot)$ parameterized by learnable weights $\theta$. This function operates directly on the graph frequencies (eigenvalues).

We define the spectral filter as $\hat{\mathbf{g}}_\theta = g_\theta(\Lambda)$, which is a diagonal matrix where the function $g_\theta$ is applied to each eigenvalue: $\text{diag}(g_\theta(\lambda_1), g_\theta(\lambda_2), ..., g_\theta(\lambda_N))$.

Applying this filter $g_\theta(\Lambda)$ to a signal $\mathbf{x}$ via spectral convolution yields:

$$g_\theta(\Lambda) *_{\mathcal{G}} \mathbf{x} = U g_\theta(\Lambda) \hat{\mathbf{x}} = U g_\theta(\Lambda) U^T \mathbf{x}$$

The expression $U g_\theta(\Lambda) U^T$ represents the filter's action in the spatial domain.

Role in Spectral GNNs

This formulation is the foundation of spectral GNNs. A spectral GNN layer essentially applies a parameterized filter $g_\theta(\Lambda)$ to the input node features $\mathbf{H}^{(k-1)}$ (which are graph signals) in the spectral domain:

$$\mathbf{H}^{(k)} = \sigma \left( U g_\theta^{(k)}(\Lambda) U^T \mathbf{H}^{(k-1)} \right)$$

where $\sigma$ is a non-linear activation function. The network learns the parameters $\theta$ of the filter function $g_\theta$.

However, this direct spectral approach faces significant practical challenges:

1. Computational Cost: Calculating the eigen-decomposition $U \Lambda U^T$ is computationally expensive, typically scaling as $O(N^3)$, which is prohibitive for large graphs. The multiplications involving $U$ and $U^T$ also cost $O(N^2)$ per layer.
2. Non-Localization: The learned filters $g_\theta(\Lambda)$ depend on the global structure of the graph (encoded in $U$ and $\Lambda$) and are not localized in the vertex domain. This means a change in a distant part of the graph could affect the filter's output at a specific node.
3. Transferability: The basis $U$ is specific to a given graph structure. A filter learned on one graph cannot be directly applied to another graph with a different size or connectivity, as their Laplacian eigenvectors will differ.

These limitations motivated the development of spatial GNNs (like the message passing models discussed earlier) and approximations to spectral convolutions (like GCN, ChebNet) that operate more efficiently in the spatial domain, which we will explore in the next chapter.

Understanding the spectral perspective, however, remains valuable. It provides a theoretical grounding for graph convolutions, helps interpret GNN operations in terms of frequency filtering, and connects GNNs to the broader field of graph signal processing. It forms the basis upon which many subsequent advancements, aiming to overcome its limitations while retaining its desirable properties, were built.