Foundations of Graph Representation Learning

Graph representation learning has fundamentally transformed our ability to extract meaningful patterns from interconnected data, moving beyond hand-crafted features to automatically learned dense vector spaces that preserve structural and semantic properties. This chapter establishes the rigorous mathematical and conceptual foundation for the field, defining the core problems, formalizing the principles that bind diverse architectures, and critically contextualizing the evolution from shallow embedding methods to modern graph neural networks. We begin by formalizing the graph as a mathematical object, introducing the essential algebraic representations—adjacency and Laplacian matrices—that serve as the lingua franca for spectral analysis. The central problem of representation learning is then framed: learning a mapping from nodes, edges, or entire graphs to continuous vector spaces that facilitate downstream tasks. The message-passing paradigm is presented as the unifying computational engine for virtually all contemporary graph neural networks (GNNs), a framework we will dissect in detail. We articulate the key desiderata for any graph embedding scheme—permutation invariance, injectivity, and scalability—and examine the inherent trade-offs. Essential mathematical tools from spectral graph theory and functional analysis are introduced not as abstract diversions but as practical instruments for understanding graph signals and designing architectures. Finally, we provide a critical overview of pre-GNN embedding techniques (e.g., DeepWalk, node2vec), highlighting their ingenious reliance on random walks and the paradigm shift they precipitated, while also exposing the limitations that motivated the development of parametric, end-to-end learnable message-passing frameworks. This chapter does not merely list definitions; it constructs a cohesive narrative that explains *why* the field coalesced around message passing and sets the precise stage for the architectural deep dives to follow.

Mathematical Foundations: Graphs and Their Algebraic Representations

At its core, a graph $\mathcal{G}$ is a tuple $(\mathcal{V}, \mathcal{E})$, where $\mathcal{V} = \{v_1, v_2, ..., v_n\}$ is a set of $n$ nodes (or vertices) and $\mathcal{E} \subseteq \mathcal{V} \times \mathcal{V}$ is a set of edges (or links) connecting pairs of nodes. This simple definition belies a rich taxonomy. Graphs can be undirected, where $(v_i, v_j) \in \mathcal{E}$ implies $(v_j, v_i) \in \mathcal{E}$, or directed (digraphs), where edge direction matters. They can be weighted, with each edge $e_{ij}$ carrying a scalar weight $w_{ij} > 0$, or unweighted (binary). They can contain self-loops ($v_i$ connected to itself) and multi-edges (multiple edges between the same node pair). The choice of graph type is not merely semantic; it dictates the appropriate mathematical tools and the semantics of learned representations. For instance, a social network with symmetric "friendship" relations is naturally modeled as an undirected graph, while a financial transaction network is inherently directed and weighted.

The primary vehicle for algebraic and spectral manipulation is the adjacency matrix $\mathbf{A} \in \mathbb{R}^{n \times n}$. For an undirected, unweighted graph without self-loops, $\mathbf{A}$ is symmetric and binary: $$ \mathbf{A}_{ij} = \begin{cases} 1 & \text{if } (v_i, v_j) \in \mathcal{E} \\ 0 & \text{otherwise} \end{cases} $$ For weighted graphs, $\mathbf{A}_{ij} = w_{ij}$. For directed graphs, $\mathbf{A}$ is generally asymmetric. The adjacency matrix compactly encodes the graph's connectivity pattern. Its powers, $\mathbf{A}^k$, have a profound interpretation: $(\mathbf{A}^k)_{ij}$ counts the number of walks of length $k$ from node $v_i$ to node $v_j$. This walk-counting perspective is central to understanding early embedding methods like DeepWalk.

Closely allied to $\mathbf{A}$ is the degree matrix $\mathbf{D} \in \mathbb{R}^{n \times n}$, a diagonal matrix where $\mathbf{D}_{ii} = d_i = \sum_{j=1}^n \mathbf{A}_{ij}$ is the degree (or weighted degree) of node $v_i$. The degree matrix captures local connectivity density. The interplay between $\mathbf{A}$ and $\mathbf{D}$ gives rise to the graph Laplacian, a cornerstone of spectral graph theory. The most common form is the combinatorial Laplacian: $$ \mathbf{L} = \mathbf{D} - \mathbf{A}. $$ $\mathbf{L}$ is symmetric positive semi-definite (PSD) for undirected graphs, ensuring all its eigenvalues are real and non-negative. Its quadratic form $\mathbf{x}^\top \mathbf{L} \mathbf{x} = \frac{1}{2} \sum_{i,j} \mathbf{A}_{ij} (x_i - x_j)^2$ reveals its connection to graph smoothness: it penalizes differences in values $x_i$ across connected nodes. This makes $\mathbf{L}$ a discrete analogue of the continuous Laplacian operator from calculus, measuring the "roughness" of a signal defined on the graph nodes.

The normalized Laplacian is often preferred for its improved spectral properties: $$ \mathcal{L} = \mathbf{I} - \mathbf{D}^{-1/2} \mathbf{A} \mathbf{D}^{-1/2}, $$ where $\mathbf{D}^{-1/2}$ sets $\mathbf{D}_{ii}^{-1/2} = 1/\sqrt{d_i}$ for nodes with $d_i > 0$. Its eigenvalues lie in $[0, 2]$. The random walk normalized Laplacian $\mathbf{L}_{\text{rw}} = \mathbf{I} - \mathbf{D}^{-1}\mathbf{A}$ is also common, directly relating to the transition matrix of a random walk $\mathbf{P} = \mathbf{D}^{-1}\mathbf{A}$.

These matrices are not mere notational conveniences; they are the foundation for spectral clustering, graph signal processing, and, crucially, for understanding the theoretical properties of graph convolutions in the Fourier domain. The eigenvalue decomposition $\mathbf{L} = \mathbf{U} \mathbf{\Lambda} \mathbf{U}^\top$, where $\mathbf{U}$ is the matrix of orthonormal eigenvectors and $\mathbf{\Lambda}$ is the diagonal matrix of eigenvalues, defines the graph Fourier basis. The eigenvectors corresponding to the smallest eigenvalues vary slowly across the graph (low-frequency signals), while those for large eigenvalues oscillate rapidly (high-frequency signals). This spectral viewpoint allows us to define graph convolutions as element-wise products in the Fourier domain, a concept we will revisit when discussing spectral GNNs.

The Representation Learning Problem: Mapping Graphs to Vectors

Given a graph $\mathcal{G}$, the goal of graph representation learning is to learn a function $f_\theta: \mathcal{G} \mapsto \mathbb{R}^d$ (or $f_\theta: v_i \mapsto \mathbb{R}^d$ for nodes, $f_\theta: e_{ij} \mapsto \mathbb{R}^d$ for edges) that maps structural entities into a low-dimensional, dense, continuous vector space. The dimensionality $d$ is a hyperparameter, typically $d \ll n$. The learned embeddings should capture properties relevant to downstream tasks—node classification, link prediction, graph classification, etc.—without requiring task-specific re-engineering for each new application. This is the promise of *representation* learning: generic, transferable knowledge.

Formally, for node-level tasks, we seek an embedding function $\mathbf{h}_i = f_\theta(v_i, \mathcal{G})$ such that the vector $\mathbf{h}_i \in \mathbb{R}^d$ encodes both the attributes of node $v_i$ (if any) and its structural role within $\mathcal{G}$. For graph-level tasks, we seek $\mathbf{h}_\mathcal{G} = f_\theta(\mathcal{G}) \in \mathbb{R}^d$ that summarizes the entire graph. The challenge is defining $f_\theta$ such that it is permutation invariant to the ordering of nodes (since graphs have no canonical node ordering), differentiable to allow gradient-based learning, and scalable to large graphs.

The learning objective is typically self-supervised or unsupervised, as labeled graph data is often scarce. The embedding function is trained to preserve certain graph properties, which act as a proxy for semantic similarity. Common objectives include:

• **Proximity preservati