Foundations of Graph-Structured Data

Graph-structured data represents one of the most pervasive and complex forms of information in the modern world, underlying social networks, molecular chemistry, transportation systems, and knowledge graphs. Unlike traditional Euclidean data such as images or text sequences, which reside on regular grids or sequences, graph data exists in a non-Euclidean domain where the underlying topology is irregular, unordered, and often dynamically evolving. This fundamental shift in data structure necessitates novel computational paradigms beyond the conventional deep learning architectures that have achieved remarkable success on grid-like and sequential data. Graph Neural Networks (GNNs) have emerged as a powerful framework for learning representations on graph-structured data, effectively capturing both the structural dependencies and node/edge features through message passing mechanisms. However, to fully appreciate the design and capabilities of GNNs, one must first establish a solid foundation in graph theory and understand the unique characteristics of graph data. This chapter lays this essential groundwork by introducing the core concepts of graph theory, algebraic representations, structural properties, and the taxonomy of graph learning tasks that will serve as the bedrock for the subsequent chapters.

Graph Fundamentals: Definitions and Representations

At its core, a graph $\mathcal{G}$ is a mathematical structure consisting of a set of nodes (or vertices) $\mathcal{V}$ and a set of edges $\mathcal{E}$ that connect pairs of nodes. Formally, we define a graph as $\mathcal{G} = (\mathcal{V}, \mathcal{E})$, where $|\mathcal{V}| = n$ denotes the number of nodes and $|\mathcal{E}| = m$ denotes the number of edges. Graphs can be classified along several dimensions that fundamentally impact their analysis and the design of learning algorithms.

Directed versus Undirected Graphs: In an undirected graph, edges have no orientation; the relationship between nodes $u$ and $v$ is symmetric, i.e., $(u, v) \in \mathcal{E}$ implies $(v, u) \in \mathcal{E}$. This symmetry models mutual relationships such as friendships in social networks (though real-world friendships may not be perfectly symmetric) or undirected connections in molecular structures. In contrast, a directed graph (or digraph) assigns a direction to each edge, so $(u, v) \in \mathcal{E}$ does not necessarily imply $(v, u) \in \mathcal{E}$. Directed edges capture asymmetric relationships like follower links on Twitter, hyperlinks between web pages, or information flow in citation networks. The distinction is critical because many GNN architectures assume undirected graphs for simplicity, while directed graphs require specialized treatments to preserve directional information, such as separating in-edges and out-edges or using antisymmetric aggregation functions.

Weighted versus Unweighted Graphs: When edges carry numerical values representing strength, capacity, or similarity, the graph is weighted. Formally, a weighted graph associates a weight function $w: \mathcal{E} \rightarrow \mathbb{R}$ with each edge. For example, in a transportation network, edge weights might represent travel time or distance; in a co-purchasing network, weights could indicate the frequency of joint purchases. Unweighted graphs treat all edges equally, which is a special case where $w(e) = 1$ for all $e \in \mathcal{E}$. Weighted graphs introduce additional complexity but also richer information; GNNs must incorporate edge weights into message passing, typically by scaling messages or using them as attention coefficients.

Homogeneous versus Heterogeneous Graphs: A homogeneous graph has a single node type and a single edge type. Most introductory GNN literature focuses on homogeneous graphs for clarity. However, many real-world systems are heterogeneous, containing multiple node types (e.g., users, items, and categories in an e-commerce network) and multiple edge types (e.g., "purchased," "viewed," "belongs-to"). Heterogeneous graphs require more expressive models that can distinguish type-specific behaviors, often through type-specific transformation matrices or meta-path-based aggregation. The increased expressivity comes at the cost of higher computational overhead and more complex parameterization.

Attributed Graphs: Beyond structure, nodes and edges often carry feature vectors. An attributed graph assigns a feature matrix $\mathbf{X} \in \mathbb{R}^{n \times d}$, where each row $\mathbf{x}_i \in \mathbb{R}^d$ represents the $d$-dimensional feature vector of node $i$. Similarly, edge features $\mathbf{Z} \in \mathbb{R}^{m \times p}$ may exist. These attributes are crucial for GNNs, as they provide the initial signals that are refined through neighborhood aggregation. For instance, in a molecular graph, node features might include atom type, electronegativity, and valence, while edge features could represent bond type (single, double, triple) or distance.

The choice of graph representation directly influences both the computational complexity and the representational capacity of subsequent learning algorithms. A common pitfall in applied work is to naively convert rich heterogeneous data into a homogeneous graph without considering information loss, or to ignore edge weights when they carry significant signal. Careful modeling of these graph properties is therefore not merely a theoretical exercise but a practical necessity for effective GNN design.

Algebraic Representations: Adjacency, Degree, and Laplacian Matrices

To perform computations on graphs, we must translate their topological structure into algebraic objects amenable to linear algebra operations. The primary representation is the adjacency matrix $\mathbf{A} \in \mathbb{R}^{n \times n}$, defined as:

$$ \mathbf{A}_{ij} = \begin{cases} w_{ij} & \text{if } (i, j) \in \mathcal{E} \\ 0 & \text{otherwise} \end{cases} $$

For undirected graphs, $\mathbf{A}$ is symmetric ($\mathbf{A} = \mathbf{A}^\top$). The adjacency matrix encodes the immediate connectivity pattern: the $(i,j)$-th entry indicates the weight of the edge from node $i$ to node $j$. However, $\mathbf{A}$ alone does not capture the degree of nodes, which is essential for normalization in many GNNs.

The degree matrix $\mathbf{D} \in \mathbb{R}^{n \times n}$ is a diagonal matrix where $\mathbf{D}_{ii} = \sum_{j=1}^{n} \mathbf{A}_{ij}$ for unweighted graphs, or $\mathbf{D}_{ii} = \sum_{j=1}^{n} \mathbf{A}_{ij}$ (sum of incident edge weights) for weighted graphs. The degree represents the number (or total weight) of edges incident to a node. High-degree nodes (hubs) often play central roles in networks, while low-degree nodes may be peripheral. The degree distribution of real-world graphs typically follows a heavy-tailed distribution, with a few hubs having many connections and many nodes having few—a property known as the power-law degree distribution, characteristic of scale-free networks.

From $\mathbf{A}$ and $\mathbf{D}$, we derive the graph Laplacian $\mathbf{L}$, a fundamental operator in spectral graph theory:

$$ \mathbf{L} = \mathbf{D} - \mathbf{A} $$

The Laplacian matrix is symmetric positive semi-definite for undirected graphs, and its eigenvalues $\lambda_1 \leq \lambda_2 \leq \dots \leq \lambda_n$ provide insights into graph connectivity. Specifically, the number of zero eigenvalues equals the number of connected components in the graph. The second smallest eigenvalue $\lambda_2$, known as the algebraic connectivity, measures how well-connected the graph is: larger $\lambda_2$ indicates a more robustly connected graph.

To facilitate normalization in GNNs, we often use the symmetrically normalized Laplacian:

$$ \mathbf{L}_{\text{sym}} = \mathbf{D}^{-1/2} \mathbf{L} \mathbf{D}^{-1/2} = \mathbf{I} - \mathbf{D}^{-1/2} \mathbf{A} \mathbf{D}^{-1/2} $$

where $\mathbf{D}^{-1/2}$ is the diagonal matrix with entries $1/\sqrt{\mathbf{D}_{ii}}$ (