Foundations of Graph Machine Learning

Graph machine learning represents a paradigm shift from traditional feature-based learning toward relational reasoning, where the structure of data itself becomes a primary source of information. This chapter establishes the rigorous mathematical and conceptual foundation upon which modern graph neural networks (GNNs) are built. We begin with the formal definitions of graphs and their algebraic representations, proceed to essential spectral graph theory that reveals the intrinsic geometric properties of graphs, and then examine classical graph representation learning methods. These classical approaches, while ingenious, highlight the limitations of shallow, multi-stage pipelines and motivate the need for end-to-end differentiable architectures that can directly learn from graph-structured data. The central challenge—designing functions that are both permutation-invariant to respect the unordered nature of graphs and differentiable to enable gradient-based learning—leads us to the formal definition of the GNN learning problem. This chapter concludes with a preview of the message-passing paradigm, the unifying computational framework that underpins nearly all contemporary GNN architectures.

1.1 Mathematical Foundations: Graphs and Their Representations

At its core, a graph is a mathematical abstraction for modeling pairwise relations between discrete entities. Formally, we define an undirected graph as $\mathcal{G} = (\mathcal{V}, \mathcal{E})$, where $\mathcal{V} = \{v_1, v_2, \dots, v_n\}$ is the set of $n = |\mathcal{V}|$ nodes (or vertices) and $\mathcal{E} \subseteq \mathcal{V} \times \mathcal{V}$ is the set of edges. Each edge $e_{ij} = (v_i, v_j) \in \mathcal{E}$ indicates a connection between nodes $v_i$ and $v_j$. In many real-world scenarios, edges carry weights $w_{ij} \in \mathbb{R}^+$ representing the strength or capacity of the connection, leading to a weighted graph. Furthermore, nodes and edges are often associated with features: a node feature matrix $\mathbf{X} \in \mathbb{R}^{n \times d}$ where each row $\mathbf{x}_i$ is a $d$-dimensional feature vector for node $v_i$, and an edge feature matrix $\mathbf{E} \in \mathbb{R}^{m \times c}$ for $m = |\mathcal{E}|$ edges. A directed graph relaxes the symmetry constraint on edges, where $(v_i, v_j) \in \mathcal{E}$ does not necessarily imply $(v_j, v_i) \in \mathcal{E}$. Heterogeneous graphs extend this further with multiple node and edge types, common in knowledge graphs. For clarity, our primary focus will be on undirected, attributed, homogeneous graphs unless otherwise specified.

The power of graph theory lies in its algebraic representations, which allow us to apply linear algebra tools. The most fundamental is the adjacency matrix $\mathbf{A} \in \{0,1\}^{n \times n}$ (or $\mathbb{R}^{n \times n}$ for weighted graphs), defined as: $$ A_{ij} = \begin{cases} w_{ij} & \text{if } (v_i, v_j) \in \mathcal{E} \\ 0 & \text{otherwise} \end{cases} $$ For undirected graphs, $\mathbf{A}$ is symmetric. The adjacency matrix compactly encodes the graph's connectivity. Its $(i,j)$-th entry directly indicates the presence (and weight) of an edge. The degree of node $v_i$, denoted $\deg(v_i)$ or $d_i$, is the sum of its edge weights: $d_i = \sum_{j=1}^n A_{ij}$. This leads to the degree matrix $\mathbf{D} \in \mathbb{R}^{n \times n}$, a diagonal matrix where $D_{ii} = d_i$. From $\mathbf{A}$ and $\mathbf{D}$, we derive the graph Laplacian, a central object in spectral graph theory. The combinatorial Laplacian is defined as $\mathbf{L} = \mathbf{D} - \mathbf{A}$. It is symmetric and positive semi-definite (PSD), with eigenvalues satisfying $0 = \lambda_1 \leq \lambda_2 \leq \dots \leq \lambda_n$. The normalized Laplacian $\mathcal{L} = \mathbf{I} - \mathbf{D}^{-1/2}\mathbf{A}\mathbf{D}^{-1/2}$ (for connected graphs with no isolated nodes) also PSD and its eigenvalues lie in $[0,2]$. The random walk Laplacian $\mathbf{L}_{rw} = \mathbf{I} - \mathbf{D}^{-1}\mathbf{A}$ is row-stochastic and closely related to random walks on graphs. These variants offer different interpretations but share the same eigenvectors (up to scaling) and capture the graph's smoothness properties.

Example 1.1: Molecular Graph Representation. Consider the molecule benzene (C₆H₆). We can construct a graph where atoms are nodes and chemical bonds are edges. Node features might include atomic number, electronegativity, or learned embeddings; edge features could indicate bond type (single, double, aromatic). The adjacency matrix $\mathbf{A}$ encodes which atoms are bonded. This representation transforms a chemical structure into a mathematical object amenable to machine learning, a cornerstone of computational drug discovery.

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

This diagram illustrates the pipeline from a graph to its spectral decomposition and the definition of convolution via the graph Fourier transform.

1.2 Spectral Graph Theory: Eigenvalues, Graph Fourier Transform, and Convolution

Spectral graph theory studies the properties of a graph through the eigenvalues and eigenvectors of its matrices, particularly the Laplacian. The spectral decomposition of the symmetric Laplacian $\mathbf{L}$ yields $\mathbf{L} = \mathbf{U}\mathbf{\Lambda}\mathbf{U}^\top$, where $\mathbf{U} = [\mathbf{u}_1, \dots, \mathbf{u}_n]$ is an orthonormal matrix of eigenvectors and $\mathbf{\Lambda} = \text{diag}(\lambda_1, \dots, \lambda_n)$ contains the corresponding eigenvalues. The eigenvector $\mathbf{u}_1$ associated with the smallest eigenvalue $\lambda_1=0$ is constant (proportional to $\mathbf{1}$) for a connected graph; its multiplicity equals the number of connected components. The second eigenvalue $\lambda_2$ (the Fiedler value) and its eigenvector (the Fiedler vector) are crucial: $\lambda_2 > 0$ iff the graph is connected, and the Fiedler vector is often used for graph partitioning (spectral clustering). Intuitively, eigenvalues measure the graph's connectivity: small eigenvalues correspond to global, slowly varying patterns over the graph, while large eigenvalues correspond to local, high-frequency variations.

This spectral decomposition enables a Fourier transform on graphs. For a graph signal $\mathbf{f} \in \mathbb{R}^n$ (a scalar value assigned to each node, e.g., temperature at each city), its graph Fourier transform is $\hat{\mathbf{f}} = \mathbf{U}^\top \mathbf{f}$. The coefficients $\hat{f}_i = \mathbf{u}_i^\top \mathbf{f}$ represent the projection of $\mathbf{f}$ onto the eigenvector basis $\mathbf{u}_i$, analogous to Fourier coefficients in classical signal processing. The basis vectors $\mathbf{u}_i$ are orthogonal and can be interpreted as "graph frequencies": low-frequency eigenvectors are smooth over the graph (similar values on connected nodes), while high-frequency eigenvectors oscillate rapidly between adjacent nodes. The inverse transform is $\mathbf{f} = \mathbf{U}\hat{\mathbf{f}}$.

This analogy leads to the definition of graph convolution. In classical signal processing, convolution in the time domain corresponds to pointwise multiplication in the frequency domain (Convolution Theorem). On graphs, we define the convolution of a filter $\mathbf{g}$ with signal $\mathbf{f}$ as: $$ \mathbf{f} * \mathbf{g} = \mathbf{U} \left( (\mathbf{U}^\top \mathbf{g}) \odot (\mathbf{U}^\top \mathbf{f}) \right) = \mathbf{U} \left( \hat{\mathbf{g}} \odot \hat{\mathbf{f}} \right) $$ where $\odot$ denotes element-wise (Hadamard) product. This operation is linear and shift-invariant in the sense that the filter's response depends on the graph structure via $\mathbf{U}$, but it is not shift-invar