Mathematical Foundations of Graph Theory and Spectral Analysis

Graph Neural Networks (GNNs) have revolutionized the processing of graph-structured data, enabling end-to-end learning of node, edge, and graph-level representations. The cornerstone of many GNN architectures is the graph convolution operation, an adaptation of classical convolution to non-Euclidean domains. Defining such an operation requires a rigorous mathematical foundation rooted in spectral graph theory, which bridges algebraic properties of graphs with signal processing concepts. This chapter provides that foundation, revisiting essential constructs—graph Laplacians, spectral decomposition, and the graph Fourier transform—and deriving continuous and discrete graph convolution operators from first principles. We meticulously elucidate how the spectral characteristics of a graph dictate the behavior of graph-based filters, establishing a theoretical framework that underpins both classical spectral methods and modern GNNs. This treatment assumes familiarity with linear algebra and basic probability but develops all graph-specific concepts systematically.

Graph Representations: From Adjacency to Laplacians

A graph $\mathcal{G} = (\mathcal{V}, \mathcal{E})$ comprises a set of $\mathbf{N}$ nodes $\mathcal{V} = \{v_1, \dots, v_N\}$ and edges $\mathcal{E} \subseteq \mathcal{V} \times \mathcal{V}$. Graphs may be undirected or directed, weighted or unweighted, with or without self-loops. The most fundamental representation is the adjacency matrix $\mathbf{A} \in \mathbb{R}^{N \times N}$, where $A_{ij} = w_{ij}$ if edge $(v_i, v_j)$ exists with weight $w_{ij}$, and $0$ otherwise. For undirected graphs, $\mathbf{A}$ is symmetric. The degree matrix $\mathbf{D} \in \mathbb{R}^{N \times N}$ is diagonal with $D_{ii} = \sum_j A_{ij}$, the sum of incident edge weights (including self-loops if present). These matrices encode the graph’s connectivity but have limitations: $\mathbf{A}$ does not directly reflect node degrees, and both matrices are not necessarily positive semi-definite (PSD), complicating spectral analysis.

The graph Laplacian addresses these issues. The (combinatorial) Laplacian is defined as: $$ \mathbf{L} = \mathbf{D} - \mathbf{A}. $$ $\mathbf{L}$ is symmetric for undirected graphs, singular (has a zero eigenvalue) with eigenvector $\mathbf{1}$ (all-ones vector), and positive semi-definite. Its off-diagonal entries are non-positive, and row sums are zero. These properties make $\mathbf{L}$ a discrete analogue of the continuous Laplace-Beltrami operator on manifolds, measuring smoothness of functions over the graph.

Variants of the Graph Laplacian

Several normalized variants exist, each with distinct interpretations:

1. Symmetric normalized Laplacian: $$ \mathbf{L}_{\text{sym}} = \mathbf{D}^{-1/2} \mathbf{L} \mathbf{D}^{-1/2} = \mathbf{I} - \mathbf{D}^{-1/2} \mathbf{A} \mathbf{D}^{-1/2}. $$ $\mathbf{L}_{\text{sym}}$ is symmetric, PSD, and has eigenvalues in $[0, 2]$. It arises naturally from the normalized graph cut objective and random walk analysis when symmetrizing the transition matrix.

2. Random walk Laplacian: $$ \mathbf{L}_{\text{rw}} = \mathbf{D}^{-1} \mathbf{L} = \mathbf{I} - \mathbf{D}^{-1} \mathbf{A}. $$ $\mathbf{L}_{\text{rw}}$ is not symmetric in general but is row-stochastic ($\mathbf{L}_{\text{rw}} \mathbf{1} = \mathbf{0}$). It corresponds to the generator of a random walk: $\mathbf{P} = \mathbf{D}^{-1} \mathbf{A}$ is the transition matrix, and $\mathbf{L}_{\text{rw}} = \mathbf{I} - \mathbf{P}$.

3. Generalized Laplacian: For directed graphs, one may use the Magical Laplacian $\mathbf{L}_{\text{mag}} = (\mathbf{D}^+ + \mathbf{D}^{+\top})/2 - (\mathbf{A} + \mathbf{A}^\top)/2$, where $\mathbf{D}^+$ is the out-degree matrix, or employ symmetrization techniques like $\mathbf{L}_{\text{sym}} = \mathbf{D}_{\text{out}}^{-1/2} \mathbf{A} \mathbf{D}_{\text{in}}^{-1/2}$ followed by $\mathbf{I} - \mathbf{L}_{\text{sym}}$.

Example 1.1 (Path graph). Consider a path graph with $N=5$ nodes and unit weights. Its adjacency and Laplacian are: $$ \mathbf{A} = \begin{bmatrix} 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 \end{bmatrix},\quad \mathbf{L} = \begin{bmatrix} 1 & -1 & 0 & 0 & 0 \\ -1 & 2 & -1 & 0 & 0 \\ 0 & -1 & 2 & -1 & 0 \\ 0 & 0 & -1 & 2 & -1 \\ 0 & 0 & 0 & -1 & 1 \end{bmatrix}. $$ $\mathbf{L}$ has eigenvalues $2(1 - \cos(\frac{k\pi}{N}))$ for $k=0,\dots,N-1$, and eigenvectors are discrete sine/cosine waves. This spectral pattern mirrors the continuous Laplacian on an interval.

Physical Interpretations

The Laplacian quantifies smoothness: for a signal $\mathbf{f} \in \mathbb{R}^N$ (node features), the quadratic form $$ \mathbf{f}^\top \mathbf{L} \mathbf{f} = \frac{1}{2} \sum_{i,j} A_{ij} (f_i - f_j)^2 $$ measures total variation—penalizing differences across edges. Thus, $\mathbf{L}$ is the generator of a diffusion process: $\frac{\partial \mathbf{f}}{\partial t} = -\mathbf{L} \mathbf{f}$ smooths $\mathbf{f}$ over time. The normalized Laplacians correspond to normalized diffusion: $\mathbf{L}_{\text{sym}}$ yields $\frac{\partial \mathbf{f}}{\partial t} = -\mathbf{L}_{\text{sym}} \mathbf{f}$, while $\mathbf{L}_{\text{rw}}$ corresponds to $\frac{\partial \mathbf{f}}{\partial t} = -\mathbf{L}_{\text{rw}} \mathbf{f}$, which is a random walk smoothing.

Spectral Decomposition and Graph Fourier Transform

Since $\mathbf{L}$ (or its normalized variants) is symmetric PSD, it admits an eigen-decomposition: $$ \mathbf{L} = \mathbf{U} \mathbf{\Lambda} \mathbf{U}^\top, $$ where $\mathbf{U} = [\mathbf{u}_0, \dots, \mathbf{u}_{N-1}]$ is an orthogonal matrix of eigenvectors, and $\mathbf{\Lambda} = \text{diag}(\lambda_0, \dots, \lambda_{N-1})$ with $0 = \lambda_0 \le \lambda_1 \le \dots \le \lambda_{N-1}$. The eigenvalues reflect graph connectivity: $\lambda_1 > 0$ iff the graph is connected; the multiplicity of $\lambda_0$ equals the number of connected components. The spectral gap $\lambda_1$ measures algebraic connectivity (Fiedler value). The eigenvectors $\mathbf{u}_k$ are orthogonal bases on $\mathbb{R}^N$, generalizing the complex exponentials in classical Fourier analysis.

This decomposition enables the graph Fourier transform (GFT). For a graph signal $\mathbf{f} : \mathcal{V} \to \mathbb{R}$, its GFT is: $$ \hat{\mathbf{f}} = \mathbf{U}^\top \mathbf{f}. $$ Thus, $\hat{f}_k = \langle \mathbf{f}, \mathbf{u}_k \rangle$ is the coefficient of $\mathbf{f}$ along eigenvector $\mathbf{u}_k$. The inverse GFT is $\mathbf{f} = \mathbf{U} \hat{\mathbf{f}}$. The eigenvectors $\mathbf{u}_k$ are interpreted as “graph frequencies”: low-frequency eigenvectors vary slowly over the graph (smooth), while high-frequency ones oscillate rapidly. For a path graph, $\mathbf{u}_k$ are sinusoids; for a ring, they are complex exponentials; for irregular graphs, they reflect community structure.

Example 1.2 (Karate club network). Zachary’s karate club graph has 34 nodes. Its $\mathbf{L}_{\text{sym}}$ eigenvalues show a clear spectral gap after the second eigenvalue, indicating two clusters (the two factions). The Fiedler vector $\mathbf{u}_1$ (corresponding to $\lambda_1$) takes positive values on one cluster and negative on the other, providing a spectral embedding for bipartition.

Spectral Theorem and Filtering

The spectral theorem allows diagonalizing any symmetric PSD matrix $\mathbf{S}$ as $\mathbf{S} = \mathbf{U} \mathbf{\Sigma} \mathbf{U}^\top$. A matrix function $g(\mathbf{S})$ is defined via spectral mapping: $$ g(\mathbf{S}) = \mathbf{U} \, g(\mathbf{\Sigma}) \, \mathbf{U}^\top, $$ where $g(\mathbf{\Sigma}) = \text{diag}(g(\sigma_0), \dots, g(\sigma_{N-1}))$. This is the foundation for graph filtering: a filter $g$ applied to signal $\mathbf{f}$ is $\mathbf{g}(\mathbf{L}) \mathbf{f} = \mathbf{U} \, g(\mathbf{\Lambda}) \, \mathbf{U}^\top \mathbf{f} = \mathbf{U} (g(\mathbf{\Lambda}) \odot \hat{\mathbf{f}