Mathematical Foundations for Graph Representation Learning

The study of graph representation learning occupies a pivotal position at the intersection of geometric deep learning and spectral graph theory, representing one of the most significant theoretical and practical developments in modern machine learning. Graphs, as fundamental mathematical structures, provide a universal language for describing relational data across countless domains—from social networks where nodes represent individuals and edges capture friendship patterns, to molecular graphs where atoms and chemical bonds form the substrate of computational chemistry, to citation networks that map the intellectual dependencies within scientific literature. Understanding how to extract meaningful representations from such relational structures requires a deep command of both the underlying graph-theoretic principles and the mathematical machinery that enables their integration into learning systems. This chapter establishes the rigorous mathematical framework that underlies all subsequent discussions of graph neural network architectures, providing readers with the essential tools for understanding not only how these networks operate but why their mathematical foundations confer the representational properties that make them so powerful.

The importance of this mathematical foundation cannot be overstated. Unlike data residing in Euclidean spaces where familiar operations like convolution and Fourier transformation provide natural tools for feature extraction, graphs inhabit non-Euclidean topologies that demand more sophisticated analytical apparatus. The spectral properties of graph structures, captured through the eigenvalues and eigenvectors of matrices derived from the graph topology, provide the bridge between the discrete world of graph structure and the continuous spaces where neural networks operate. By developing a thorough understanding of these mathematical foundations, readers will be equipped to appreciate both the theoretical underpinnings and the practical implications of the architectural choices that characterize modern graph neural networks.

Linear Algebraic Foundations

The mathematical language of graph representation learning is predominantly linear algebraic, making it essential to establish firm foundations in the properties of vectors, matrices, and their transformations before proceeding to graph-specific constructions. A vector space $\mathcal{V}$ over a field $\mathbb{F}$ (typically $\mathbb{R}$ or $\mathbb{C}$) is defined as a set equipped with two operations—vector addition and scalar multiplication—that satisfy a collection of axioms including associativity, commutativity of addition, the existence of an additive identity (the zero vector), and the existence of additive inverses. Within the context of graph learning, we most frequently encounter finite-dimensional vector spaces $\mathbb{R}^n$, where $n$ denotes the dimensionality of the space.

Vector Spaces and Inner Products

The notion of an inner product extends the structure of a vector space to accommodate geometric concepts such as length, angle, and orthogonality. For a real vector space $\mathbb{R}^n$, the standard inner product between vectors $\mathbf{x}, \mathbf{y} \in \mathbb{R}^n$ is defined as:

$$\langle \mathbf{x}, \mathbf{y} \rangle = \mathbf{x}^\top \mathbf{y} = \sum_{i=1}^{n} x_i y_i$$

This inner product induces the Euclidean norm $\|\mathbf{x}\| = \sqrt{\langle \mathbf{x}, \mathbf{x} \rangle} = \sqrt{\sum_{i=1}^{n} x_i^2}$, which measures the length of a vector. Two vectors are orthogonal if their inner product equals zero: $\langle \mathbf{x}, \mathbf{y} \rangle = 0$. The concept of orthogonality plays a central role in spectral graph theory, where orthogonal bases facilitate the decomposition of signals into interpretable components.

An orthonormal basis of $\mathbb{R}^n$ consists of $n$ mutually orthogonal vectors, each of unit norm. The standard basis vectors $\mathbf{e}_1, \mathbf{e}_2, \ldots, \mathbf{e}_n$ form one such orthonormal basis, where $(\mathbf{e}_i)_j = 1$ if $i = j$ and $0$ otherwise. However, the choice of basis fundamentally affects the representation of vectors and linear transformations, and for graph-theoretic applications, bases constructed from the eigenvectors of graph-related matrices often prove more meaningful than the standard basis.

Matrix Operations and Properties

Matrices represent linear transformations between vector spaces, and the properties of these transformations encode crucial information about graph structure. An $n \times n$ matrix $\mathbf{A}$ maps vectors from $\mathbb{R}^n$ to $\mathbb{R}^n$ through the linear transformation $\mathbf{y} = \mathbf{A}\mathbf{x}$. The elements of $\mathbf{A}$ are denoted $A_{ij}$, where $i$ indexes the row and $j$ indexes the column.

Several matrix operations prove particularly relevant to graph representation learning. The transpose $\mathbf{A}^\top$ swaps rows and columns such that $(\mathbf{A}^\top)_{ij} = A_{ji}$. A symmetric matrix satisfies $\mathbf{A} = \mathbf{A}^\top$, implying $A_{ij} = A_{ji}$ for all $i, j$. Most matrices derived from undirected graphs are symmetric, a property that guarantees the existence of a complete set of orthogonal eigenvectors and real eigenvalues. The conjugate transpose $\mathbf{A}^*$ extends the transpose to complex matrices by additionally taking the complex conjugate of each entry.

The trace of a matrix, $\text{tr}(\mathbf{A}) = \sum_{i=1}^{n} A_{ii}$, equals the sum of its diagonal elements. For any matrix, the trace remains invariant under cyclic permutations: $\text{tr}(\mathbf{A}\mathbf{B}\mathbf{C}) = \text{tr}(\mathbf{C}\mathbf{A}\mathbf{B}) = \text{tr}(\mathbf{B}\mathbf{C}\mathbf{A})$. This property proves useful in various derivations involving graph-related matrices.

The determinant $\det(\mathbf{A})$ of a square matrix encodes information about the matrix's invertibility—a matrix is invertible if and only if its determinant is nonzero. For graph Laplacian matrices, the determinant is always zero because the all-ones vector lies in the null space, reflecting the connectivity properties of the underlying graph.

Eigenvalue Decomposition and Spectral Theory

Eigenvalue decomposition forms the mathematical cornerstone of spectral graph theory and, by extension, graph neural network theory. For a symmetric matrix $\mathbf{A} \in \mathbb{R}^{n \times n}$, the eigenvalue decomposition expresses the matrix as:

$$\mathbf{A} = \mathbf{V} \mathbf{\Lambda} \mathbf{V}^\top$$

where $\mathbf{\Lambda} = \text{diag}(\lambda_1, \lambda_2, \ldots, \lambda_n)$ is a diagonal matrix containing the eigenvalues $\lambda_1 \leq \lambda_2 \leq \cdots \leq \lambda_n$, and $\mathbf{V} = [\mathbf{v}_1, \mathbf{v}_2, \ldots, \mathbf{v}_n]$ is an orthogonal matrix whose columns are the corresponding eigenvectors satisfying $\mathbf{A}\mathbf{v}_i = \lambda_i \mathbf{v}_i$. The orthogonality of eigenvectors means $\mathbf{v}_i^\top \mathbf{v}_j = \delta_{ij}$, where $\delta_{ij}$ is the Kronecker delta.

The eigenvalues of a symmetric matrix are guaranteed to be real, a property that distinguishes symmetric matrices from general matrices whose eigenvalues may be complex. This reality of eigenvalues proves essential for graph signal processing, where real-valued frequencies enable intuitive interpretation.

The spectral theorem extends to Hermitian matrices (symmetric matrices in the real case), and the Rayleigh quotient provides a mechanism for understanding eigenvalues in terms of optimization:

$$\lambda_i = \min_{\mathbf{x} \perp \{\mathbf{v}_1, \ldots, \mathbf{v}_{i-1}\}} \frac{\mathbf{x}^\top \mathbf{A} \mathbf{x}}{\mathbf{x}^\top \mathbf{x}}$$

This formulation connects eigenvalue analysis to quadratic forms and optimization problems, establishing foundations for understanding graph cuts and other combinatorial objectives through continuous optimization.

For non-symmetric matrices, the singular value decomposition (SVD