Foundations of Graph Representation Learning

Graph-structured data permeates our digital world: social networks encoding human interactions, molecular graphs representing chemical compounds, knowledge graphs storing relational facts, and transportation networks modeling traffic flows. Unlike tabular data where features are independent and identically distributed, graph data exhibits complex relational dependencies that defy traditional machine learning assumptions. This fundamental shift necessitates a new paradigm—graph representation learning—where the goal is to embed nodes, edges, or entire graphs into continuous vector spaces that preserve structural and semantic properties. As the inaugural chapter of this book, we establish the mathematical and conceptual bedrock upon which advanced Graph Neural Networks (GNNs) are built. We will formalize graph definitions across diverse types (directed, undirected, heterogeneous, dynamic), introduce spectral graph theory fundamentals that underlie many GNN architectures, and precisely formulate the representation learning objective. Crucially, we will contrast earlier feature-based embedding methods like Node2Vec and DeepWalk with modern neural approaches, highlighting the paradigm shift from shallow, indirect optimization to end-to-end, message-passing frameworks. The design of any GNN is constrained by fundamental principles of permutation invariance and equivariance, which we will derive and explain. Finally, we will critically analyze the expressive power of GNNs through the lens of the Weisfeiler-Lehman test, establishing theoretical boundaries on what graph structures can be distinguished. A hands-on Python tutorial using NetworkX and PyTorch Geometric will ground these concepts in practical implementation, completing the foundation for the advanced architectures explored in subsequent chapters.

Formal Definitions of Graphs and Their Variants

At its core, a graph is a mathematical structure used to model pairwise relations between objects. Formally, we define a graph as $G = (\mathcal{V}, \mathcal{E})$, where $\mathcal{V}$ is the set of $n = |\mathcal{V}|$ nodes (or vertices) and $\mathcal{E} \subseteq \mathcal{V} \times \mathcal{V}$ is the set of edges (or links) connecting pairs of nodes. Each node $v_i \in \mathcal{V}$ may have an associated feature vector $\mathbf{x}_i \in \mathbb{R}^d$, and each edge $(v_i, v_j) \in \mathcal{E}$ may have a weight $w_{ij}$ or a type in heterogeneous settings. This simple definition belies a rich taxonomy that captures the diversity of real-world data.

Undirected vs. Directed Graphs

The most basic distinction lies in edge directionality. In an undirected graph, edges are unordered pairs: $(v_i, v_j) \in \mathcal{E}$ implies $(v_j, v_i) \in \mathcal{E}$, and the relationship is symmetric. The adjacency matrix $\mathbf{A}$ is symmetric ($\mathbf{A} = \mathbf{A}^\top$). Friendship networks on Facebook or collaboration networks in academia are typically undirected—if Alice is friends with Bob, Bob is friends with Alice. In contrast, a directed graph (or digraph) features ordered edges: $(v_i, v_j) \in \mathcal{E}$ does not necessarily imply $(v_j, v_i) \in \mathcal{E}$. The adjacency matrix is generally asymmetric. Twitter's follower relationship is directional: Alice follows Bob, but Bob may not follow Alice. Web page hyperlinks are another canonical example. Directionality encodes asymmetry in relationships, which is crucial for modeling flow, influence, or precedence.

Weighted vs. Unweighted Graphs

Edges may carry weights $w_{ij} \in \mathbb{R}^+$ indicating strength, capacity, or distance. A weighted graph has $\mathbf{A} \in \mathbb{R}^{n \times n}$ with real-valued entries. In a social network, weight could represent interaction frequency; in a road network, weight could be travel time or distance. An unweighted graph assumes binary connections: $w_{ij} = 1$ if edge exists, $0$ otherwise. Many theoretical results assume unweighted graphs for simplicity, but practical GNNs almost always incorporate edge weights either explicitly or implicitly through attention mechanisms.

Heterogeneous Graphs

Real-world systems often involve multiple node and edge types. A heterogeneous graph (or heterograph) is defined as $G = (\mathcal{V}, \mathcal{E}, \mathcal{T}_V, \mathcal{T}_E, \phi_V, \phi_E)$, where $\mathcal{T}_V$ and $\mathcal{T}_E$ are sets of node and edge types, and $\phi_V: \mathcal{V} \rightarrow \mathcal{T}_V$, $\phi_E: \mathcal{E} \rightarrow \mathcal{T}_E$ are type mapping functions. Consider an academic graph: nodes include authors, papers, venues, and topics (multiple types); edges include "writes" (author→paper), "published_in" (paper→venue), "cites" (paper→paper), "has_topic" (paper→topic). Each type may have distinct feature spaces and semantic meanings. Modeling such graphs requires type-aware message passing, where transformation functions depend on source and destination node types as well as edge type. This heterogeneity introduces additional complexity but also richer semantics.

Dynamic Graphs

Many graphs evolve over time: new nodes and edges appear, existing ones disappear or change weights. A dynamic graph is a sequence of snapshots $G_1, G_2, \dots, G_T$ or a continuous-time event stream. Social networks grow as users join and friend; financial transaction networks change with each trade; traffic networks fluctuate with congestion. Dynamic graphs can be discrete-time (snapshots at regular intervals) or continuous-time (events with timestamps). The challenge lies in capturing temporal dependencies alongside structural ones—a node's future embedding may depend on its past neighborhood evolution. This temporal dimension adds a fourth aspect (time) to the traditional node-edge-feature triad.

Self-Loops and Multi-Edges

We may allow self-loops $(v_i, v_i) \in \mathcal{E}$, which are essential in many GNN architectures to include a node's own features in its updated representation. Multi-edges (multiple edges between the same node pair) occur in multigraphs, common in transportation (multiple parallel routes) or social interactions (multiple communication channels). Standard GNN formulations typically assume simple graphs (no self-loops, no multi-edges), but extensions exist.

Graph-Level Definitions

Beyond node-level, we may define graph-level properties:

• **Node degree**: $d_i = \sum_j \mathbf{A}_{ij}$ (for weighted graphs, sum of incident edge weights).
• **Degree distribution** $P(d)$: often heavy-tailed (scale-free) in real networks.
• **Path**: sequence of edges connecting nodes. **Shortest path** distance $dist(v_i, v_j)$.
• **Connected components**: maximal subgraphs where every node pair is connected by a path.
• **Diameter**: maximum shortest-path distance between any two nodes.
• **Clustering coefficient**: measures prevalence of triangles (triadic closures). For node $i$, local clustering coefficient is $C_i = \frac{2T_i}{d_i(d_i-1)}$, where $T_i$ is number of edges among neighbors of $i$.

These definitions, while elementary, are crucial for understanding graph statistics and diagnosing data before modeling.

Spectral Graph Theory: The Language of Graph Signals

Spectral graph theory provides the mathematical foundation for understanding graphs through the eigenvalues and eigenvectors of matrices associated with them, notably the Laplacian. This spectral viewpoint is not merely academic—it directly inspired the earliest GNNs via graph convolutional networks defined in the spectral domain. We introduce key concepts gradually, building intuition alongside formalism.

The Adjacency and Degree Matrices

Given a graph with $n$ nodes, the adjacency matrix $\mathbf{A} \in \mathbb{R}^{n \times n}$ encodes edge connections: $$ \mathbf{A}_{ij} = \begin{cases} w_{ij} & \text{if } (v_i, v_j) \in \mathcal{E} \\ 0 & \text{otherwise} \end{cases} $$ For undirected graphs, $\mathbf