Foundations of Graph Theory and Spectral Methods

Graphs provide a universal language for modeling relational data across domains as diverse as social networks, molecular chemistry, citation graphs, and recommendation systems. Their mathematical abstraction—a set of vertices connected by edges—captures the essence of pairwise interactions, making them the natural substrate for modern machine learning on non-Euclidean data. This chapter establishes the rigorous mathematical foundation upon which the entire edifice of graph neural networks (GNNs) is built. We will move from the discrete, combinatorial definitions of graphs to the continuous, spectral domain where convolution and signal processing operations acquire elegant algebraic interpretations. The core objective is to equip the reader with a precise understanding of graph Laplacians, their eigen-decompositions, and the resulting graph Fourier transform, which directly inspire the spectral graph convolutional networks that form the historical and conceptual bedrock of advanced GNNs. We will prove fundamental theorems, analyze the spectral implications of graph topology, and bridge theory to practice by addressing computational considerations, thereby setting a coherent stage for the architectural innovations explored in subsequent chapters.

**1.1 Basic Definitions and Matrix Representations**

A graph $G = (V, E)$ is defined as an ordered pair consisting of a finite set of vertices (or nodes) $V = \{v_1, v_2, \dots, v_n\}$ with $|V| = n$, and a set of edges $E \subseteq V \times V$. For an undirected graph, the edge set is symmetric: if $(v_i, v_j) \in E$, then $(v_j, v_i) \in E$. We primarily focus on undirected graphs without self-loops unless explicitly stated. A weighted graph associates a scalar weight $w_{ij} > 0$ with each edge $(v_i, v_j) \in E$; if no edge exists, $w_{ij} = 0$. The adjacency matrix $A \in \mathbb{R}^{n \times n}$ is the canonical matrix representation where $A_{ij} = w_{ij}$ if $(v_i, v_j) \in E$, and $A_{ij} = 0$ otherwise. For unweighted graphs, $A_{ij} \in \{0,1\}$. $A$ is symmetric for undirected graphs.

The degree of a vertex $v_i$, denoted $d_i$, is the sum of incident edge weights: $d_i = \sum_{j=1}^n A_{ij}$. The degree matrix $D \in \mathbb{R}^{n \times n}$ is a diagonal matrix where $D_{ii} = d_i$. The graph Laplacian (or combinatorial Laplacian) is defined as $L = D - A$. This seemingly simple matrix is the cornerstone of spectral graph theory. It is symmetric and positive semi-definite (PSD), a property we will prove shortly. An alternative, equally fundamental representation is the incidence matrix $B \in \mathbb{R}^{n \times m}$ (where $m = |E|$), which encodes the relationship between vertices and edges. For an undirected graph, each edge $e_k = (v_i, v_j)$ corresponds to a column in $B$ with $B_{ik} = 1$, $B_{jk} = -1$, and all other entries zero. A key identity reveals the Laplacian's geometric origin: $L = BB^\top$. This shows $L$ is PSD because for any vector $x \in \mathbb{R}^n$, $x^\top L x = x^\top BB^\top x = \|B^\top x\|^2_2 \geq 0$. The quantity $x^\top L x = \frac{1}{2} \sum_{i,j} A_{ij} (x_i - x_j)^2$ measures the "smoothness" of the function $x$ on the graph—it is small if connected vertices have similar values.

```mermaid graph LR A[Graph G = (V, E)] --> B[Adjacency Matrix A] A --> C[Degree Matrix D] B --> D[Laplacian L = D - A] C --> D D --> E[Spectral Decomposition<br/>L = UΛUᵀ] E --> F[Graph Fourier Transform<br/>f̂ = Uᵀf] F --> G[Spectral Graph Convolution<br/>(f * g)̂ = f̂ ⊙ ĝ] ```

*Figure 1.1: The conceptual pipeline from a graph to spectral operations. The Laplacian's eigen-decomposition defines the graph Fourier basis, transforming convolution into element-wise multiplication in the spectral domain.*

Example 1.1 (Path Graph). Consider an unweighted path graph $P_4$ with 4 vertices: $V = \{1,2,3,4\}$ and edges $E = \{(1,2), (2,3), (3,4)\}$. Its adjacency and Laplacian matrices are: $$ A = \begin{bmatrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{bmatrix}, \quad D = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 2 & 0 & 0 \\ 0 & 0 & 2 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}, \quad L = D - A = \begin{bmatrix} 1 & -1 & 0 & 0 \\ -1 & 2 & -1 & 0 \\ 0 & -1 & 2 & -1 \\ 0 & 0 & -1 & 1 \end{bmatrix}. $$ The eigenvalues of $L$ are $\lambda_k = 2 - 2\cos\left(\frac{\pi k}{4}\right)$ for $k=0,1,2,3$, yielding $\{0, 0.5858, 2, 3.4142\}$. The corresponding eigenvectors are discrete cosine basis functions, illustrating the deep connection between path graphs and the classical discrete cosine transform (DCT).

**1.2 Spectral Properties and the Graph Laplacian**

The spectrum of a matrix is the set of its eigenvalues. For the Laplacian $L$, several fundamental properties govern this spectrum. Since $L$ is real symmetric, it is orthogonally diagonalizable: $L = U \Lambda U^\top$, where $U = [u_1, u_2, \dots, u_n]$ is an orthogonal matrix of eigenvectors ($U^\top U = I$), and $\Lambda = \text{diag}(\lambda_1, \lambda_2, \dots, \lambda_n)$ is a diagonal matrix of real eigenvalues ordered as $0 = \lambda_1 \leq \lambda_2 \leq \dots \leq \lambda_n \leq 2\max_i d_i$ (for unweighted graphs, $\lambda_n \leq n$). The smallest eigenvalue is always $\lambda_1 = 0$, with the corresponding eigenvector $u_1 = \frac{1}{\sqrt{n}} \mathbf{1}$ (the constant vector), because $L\mathbf{1} = (D-A)\mathbf{1} = d - d = 0$, where $d$ is the vector of degrees.

The multiplicity of the zero eigenvalue equals the number of connected components in the graph. This is a cornerstone result: $L$ is positive definite on the subspace orthogonal to $\mathbf{1}$ if and only if the graph is connected. The algebraic connectivity (or Fiedler value) $\lambda_2$ is the second-smallest eigenvalue. Its value is positive precisely when the graph is connected, and its magnitude is a measure of how well-connected the graph is—larger $\lambda_2$ indicates a more robustly connected graph. The eigenvector associated with $\lambda_2$ is the Fiedler vector, whose components can be used for graph partitioning via spectral clustering.

Proof Sketch (Zero Eigenvalue Multiplicity). Let $G$ have $c$ connected components. For each component $C_i$, define the indicator vector $x^{(i)}$ where $(x^{(i)})_v = 1$ if $v \in C_i$, and $0$ otherwise. Then $L x^{(i)} = 0$ because within a component, the sum of weighted differences is zero, and there are no edges to other components. These $c$ vectors are linearly independent and all correspond to eigenvalue $0$. Conversely, if $Lx = 0$, then $x^\top L x = \frac{1}{2}\sum_{i,j} A_{ij}(x_i - x_j)^2 = 0$ implies $x_i = x_j$ for all $(i,j) \in E$. Thus, $x$ is constant on each connected component, so its support lies in the span of the $c$ indicator vectors. Hence, $\dim(\ker(L)) = c$.

The Courant-Fischer minimax theorem provides a variational characterization of the eigenvalues, crucial for understanding their behavior under graph perturbations: $$ \lambda_k = \min_{\substack{S \subseteq \mathbb{R}^n \\ \dim(S) = k}} \ \max_{x \in S, x \neq 0} \ \frac{x^\top L x}{x^\top x}. $$ Equivalently, $\lambda_k = \max_{\substack{S \subseteq \mathbb{R}^n \\ \dim(S) = n-k+1}} \ \min_{x \in S, x \neq 0} \ \frac{x^\top L x}{x^\top x}$. This states that $\lambda_k$ is the minimum over all $k$-dimensional subspaces of the maximum Rayleigh quotient attained on that subspace. It implies that eigenvalues are monotonic under edge addition: adding edges (or increasing weights) can only increase $\lambda_2, \dots, \lambda_n$ and decrease $\lambda_1$ (which remains zero). This monotonicity is fundamental for understanding how graph topology shapes the spectrum.

**1.3 Normalized Graph Laplacians and Random Walks**

The combinatorial Laplacian $L$ is sensitive to vertex degrees, which can skew spectral interpretations when degrees vary widely (e.g., in power-law graphs). Two normalized variants address this:

1.