The Paradigm of Graph-Structured Data: Motivation and Foundations

The digital age has witnessed an unprecedented explosion of data that is inherently relational and interconnected, defying the traditional grid-like structures that have dominated machine learning research for decades. From social networks capturing human interactions and communication patterns, to molecular structures encoding the intricate bonds between atoms, from knowledge graphs organizing vast repositories of human knowledge, to infrastructural systems modeling transportation and communication networks—graph-structured data serves as the fundamental abstraction for representing complex, interdependent relationships across virtually every domain of science, industry, and daily life. This ubiquity presents both an opportunity and a profound challenge: how can we develop computational methods that can effectively learn from, reason about, and make predictions on data whose essence lies not in isolated feature vectors, but in the rich tapestry of connections that bind entities together? Traditional machine learning approaches, built upon the assumption of independent and identically distributed (i.i.d.) data points in Euclidean space, fundamentally fail to capture the relational inductive biases inherent in graph-structured data. The emergence of Graph Neural Networks (GNNs) represents a paradigm shift—a move from treating entities as isolated points to embracing the principle that "the network is the data." This chapter establishes the foundational motivation for learning on graphs, formally defining graph structures and their properties, contrasting Euclidean and non-Euclidean data manifolds, and articulating why conventional deep learning architectures such as Convolutional Neural Networks (CNNs) and Recurrent Neural Networks (RNNs) are mathematically and computationally inadequate for graph data. We will systematically introduce the core challenges that any graph learning system must address: permutation invariance, variable-sized inputs, and complex, often irregular topological structures. The chapter culminates in a formal problem statement for graph representation learning and provides a comprehensive taxonomy of GNN architectures that will serve as the organizing framework for the remainder of this book.

Graphs, in their most general mathematical form, are structures consisting of a set of vertices (or nodes) and a set of edges connecting pairs of vertices. Formally, a graph $G$ is defined as $G = (\mathcal{V}, \mathcal{E})$, where $\mathcal{V}$ is the set of nodes and $\mathcal{E} \subseteq \mathcal{V} \times \mathcal{V}$ is the set of edges. This simple definition belies an extraordinary richness of possibilities. Graphs can be directed or undirected, weighted or unweighted, and may contain self-loops or multiple edges between the same pair of nodes (multigraphs). In a directed graph, edges have orientation, representing asymmetric relationships such as "follows" in social networks or "cites" in citation networks. Undirected graphs model symmetric relationships like "friendship" or "chemical bond." Weighted graphs assign real-valued strengths to edges, capturing relationship intensity, proximity, or capacity—think of connection strengths in neural networks or distances in transportation networks. Multigraphs allow multiple edges between nodes, useful for representing different relationship types or repeated interactions. These variations are not merely technical distinctions; they fundamentally encode different assumptions about the nature of relationships in the domain and consequently demand different architectural choices in GNN design.

The critical distinction that elevates graph learning from a niche concern to a central challenge in machine learning is the dichotomy between Euclidean and non-Euclidean data. Euclidean data—vectors, images, audio spectrograms—inhabit spaces where the familiar rules of geometry apply: distances are well-defined via the $L_2$ norm, angles have meaning, and operations like convolution have natural interpretations based on spatial locality. A $28 \times 28$ grayscale image, for instance, can be viewed as a point in $\mathbb{R}^{784}$, where neighboring pixels share similar coordinates and thus semantic similarity. This regularity enables CNNs to exploit translational invariance and local receptive fields through weight sharing across a grid. Non-Euclidean data, by contrast, exists on manifolds or discrete structures where the fundamental axioms of Euclidean geometry break down. Graphs are inherently non-Euclidean: there is no global coordinate system, the "distance" between nodes is defined by path length rather than vector difference, and the neighborhood structure is irregular and variable. Two nodes connected by an edge may be semantically distant in any latent feature space, while nodes far apart in path length may be closely related. This irregularity destroys the assumptions underlying classical deep learning models.

Consider why CNNs fail on graphs. The convolutional operation relies on two key properties of Euclidean grids: grid structure (regular connectivity pattern) and translation invariance (the same filter can slide across the entire input). On an image, neighboring pixels occupy fixed relative positions: a $3 \times 3$ filter always sees a local patch with a consistent spatial arrangement. On a graph, the "neighborhood" of a node has arbitrary size and unordered structure. Node A might have degree 2, node B degree 100. There is no inherent ordering of neighbors, and the connectivity pattern varies dramatically across nodes. Applying a fixed-weight filter that assumes a specific neighbor ordering would be meaningless. The very concept of a "local patch" becomes ill-defined without a coordinate system. Various attempts to adapt CNNs to graphs—such as treating them as grid-like by imposing a虚假 ordering or using spectral methods on the graph Laplacian—have met with limited success due to these fundamental mismatches.

Recurrent Neural Networks (RNNs) and their variants (LSTMs, GRUs) face analogous challenges. RNNs are designed for sequential data where elements follow a strict temporal or syntactic order. They process inputs step-by-step, maintaining a hidden state that captures information from previous elements. Graphs, however, are inherently permutation invariant in their node ordering. The semantic content of a graph does not depend on whether we list node 1 before node 2 or vice versa. An RNN that processes nodes in a fixed arbitrary order would produce different representations for the same graph depending on the input ordering—a catastrophic failure. While attention mechanisms and Transformers have shown some success with graphs by treating nodes as a set and using self-attention, they still struggle with the irregular connectivity and the need to incorporate structural information beyond pairwise attention.

This brings us to the three core challenges that define graph representation learning:

Permutation Invariance (or Equivariance): A graph representation must be invariant to permutations of node labels. Formally, let $\pi$ be a permutation of node indices. If we apply $\pi$ to the adjacency matrix $A$ and feature matrix $X$, the learned representation should satisfy certain consistency properties. For node-level tasks, we often desire permutation equivariance: if we permute the input nodes, the output node representations should be permuted in the same way. For graph-level tasks, we require permutation invariance: the graph representation must remain unchanged under node reordering. This constraint is not a nuisance but a fundamental inductive bias—the model should only capture structure, not arbitrary labeling.

Variable Size and Structure: Graphs come in all sizes, from a few nodes to billions. Traditional neural networks have fixed input dimensions. A GNN must handle graphs of arbitrary size and topology without retraining or architectural modifi