Introduction to Graph Neural Networks | 图神经网络导论

Introduction to Graph Neural Networks | 图神经网络导论

1.1 The Era of Graph-Structured Data | 图结构数据的时代

The past decade has witnessed remarkable breakthroughs in deep learning, particularly in domains where data possesses regular, grid-like structures. Convolutional Neural Networks (CNNs) have revolutionized computer vision by learning hierarchical representations from pixel arrays, while Recurrent Neural Networks (RNNs) and Transformers have achieved unprecedented success in processing sequential data such as text and speech. These architectures excel because their input data—images, sentences, audio spectrograms—live in the Euclidean space, where familiar operations like convolution, pooling, and attention can be naturally defined and efficiently computed.

过去十年见证了深度学习的显著突破，尤其是在数据具有规则网格状结构的领域。卷积神经网络（CNN）通过从像素数组中学习层次化表示，彻底改变了计算机视觉领域；而循环神经网络（RNN）和 Transformer 则在处理文本、语音等序列数据方面取得了前所未有的成功。这些架构之所以表现出色，是因为它们的输入数据——图像、句子、音频频谱图——都存在于欧几里得空间中，在其中可以自然地定义并高效计算卷积、池化和注意力等熟悉操作。

However, the real world is far more diverse and complex than these structured datasets suggest. Beyond the realm of Euclidean data lies a vast universe of non-Euclidean structured data, where relationships between entities are irregular, heterogeneous, and inherently relational. Social networks connect billions of users through friendship, following, and interaction patterns. Molecular graphs represent chemical compounds as atoms (nodes) connected by chemical bonds (edges). Transportation systems form intricate networks of roads, stations, and routes. Knowledge graphs encode semantic relationships between concepts. The common thread connecting these diverse domains is the graph—a mathematical abstraction that captures the complex relational structure underlying real-world phenomena.

然而，现实世界远比这些结构化数据集所呈现的更加多样化且复杂。在欧几里得数据领域之外，存在着一个广袤的非欧几里得结构数据宇宙，其中实体之间的关系是不规则的、异构的，且本质上具有关系性。社交网络通过友谊、关注和互动模式将数十亿用户连接在一起。分子图将化合物表示为由化学键（边）连接的原子（节点）。交通系统形成了由道路、站点和路线组成的复杂网络。知识图谱编码了概念之间的语义关系。连接这些多样化领域的关键线索是图——一种数学抽象，用于捕捉现实世界现象背后复杂的结构关系。

This is precisely where traditional deep learning approaches fall short. When we attempt to apply standard CNNs to graph-structured data, we immediately encounter fundamental limitations. Images have a fixed local neighborhood structure—each pixel is connected to exactly 8 neighbors (or 4 in the orthogonal sense). This spatial regularity enables the definition of convolutional filters that slide across the entire image in a translation-invariant manner. Graphs, in contrast, possess no such regularity. Each node may have a different number of neighbors, and the connectivity pattern itself carries crucial semantic information. A node with 1,000 connections in a social network carries very different significance than a node with just 5 connections, yet a standard CNN would process their "patches" identically.

这正是传统深度学习方法所欠缺的领域。当我们尝试将标准 CNN 应用于图结构数据时，会立即遇到根本性限制。图像具有固定的局部邻域结构——每个像素恰好与8个邻域像素相连（在正交意义上为4个）。这种空间规律性使得卷积滤波器能够以平移不变的方式在整幅图像上滑动。然而，图则恰恰相反，不具有这种规律性。每个节点可能拥有不同数量的邻域节点，而连接模式本身就携带着关键的语义信息。在社交网络中，拥有1000个连接的节点与只有5个连接的节点具有截然不同的意义，但标准 CNN 会以相同方式处理它们的"图像块"。

The dimensionality crisis further compounds this challenge. In Euclidean spaces, the dimensionality of data is typically fixed and low (2D images, 1D sequences). The representation of a pixel depends on its coordinates, but once those coordinates are established, the intrinsic dimension of the space is constant. Graphs, however, present a fundamentally different scenario. The effective dimensionality of a node's neighborhood depends on the graph's structure—nodes in dense regions experience "higher-dimensional" neighborhoods compared to nodes in sparse regions. This structural variability makes it impossible to apply fixed-dimensional convolution operators without carefully accounting for the graph's topology.

维度危机进一步加剧了这一挑战。在欧几里得空间中，数据的维度通常是固定的且较低（2D 图像、1D 序列）。像素的表示取决于其坐标，但一旦确定了坐标，空间的内蕴维度就是恒定的。然而，图呈现出截然不同的情况。节点邻域的有效维度取决于图的结构——密集区域中的节点与稀疏区域中的节点相比，经历着"更高维度"的邻域。这种结构变异性使得在不考虑图拓扑的情况下应用固定维度的卷积算子成为不可能。

Perhaps most critically, the permutation invariance of graph representations poses challenges for standard neural network architectures. The nodes in a graph have no natural ordering—they are identified by their identities and relationships, not by their positions in a list or grid. When we feed an image into a CNN, the spatial arrangement of pixels conveys crucial information. When we feed a graph into a standard neural network, we must first impose an arbitrary ordering on the nodes, and this ordering introduces artificial asymmetries that the network must learn to ignore.

也许最为关键的是，图表示的排列不变性对标准神经网络架构构成了挑战。图的节点没有自然的顺序——它们通过身份和关系来标识，而非通过列表或网格中的位置来标识。当我们将图像输入 CNN 时，像素的空间排列传达了关键信息。当我们将图输入标准神经网络时，必须首先对节点施加一个任意顺序，而这种顺序会引入人为的不对称性，网络必须学会忽略它们。

These challenges have motivated the development of a new class of neural network architectures specifically designed to operate on graph-structured data: Graph Neural Networks (GNNs). Unlike their Euclidean counterparts, GNNs are built from the ground up to respect the fundamental properties of graphs—irregular connectivity, variable neighborhood sizes, and permutation invariance. By treating the graph structure as a first-class citizen, GNNs can learn powerful representations that capture both node features and topological relationships simultaneously.

这些挑战促使了专门设计用于处理图结构数据的新型神经网络架构的发展：图神经网络（GNNs）。与欧几里得空间中的对应架构不同，GNN 从根本上尊重图的基本属性——不规则连通性、可变邻域大小和排列不变性。通过将图结构作为一等公民来对待，GNN 可以学习强大的表示，同时捕获节点特征和拓扑关系。

1.2 The Fundamental Challenge: Learning on Non-Euclidean Data | 基本挑战：非欧几里得数据上的学习

To truly appreciate the significance of GNNs, we must first understand why learning on graphs is fundamentally different from learning on Euclidean data. This section delves into the mathematical foundations that distinguish these two domains and explains why conventional deep learning tools are insufficient for graph-structured data.

为了真正理解 GNN 的重要性，我们必须首先理解为什么在图上学习与在欧几里得数据上学习有着根本的不同。本节深入探讨区分这两个领域的数学基础，并解释为什么传统的深度学习工具不足以处理图结构数据。

1.2.1 Euclidean Data and the Success of Convolution | 欧几里得数据与卷积的成功

Euclidean data derives its name from Euclidean space—the familiar n-dimensional space where geometric intuitions about distance, angles, and continuity apply naturally. Images live in a 2D Euclidean space, videos extend this to 3D (adding time), and text sequences can be viewed as samples from a 1D Euclidean space. The success of deep learning in these domains rests on several key properties of Euclidean spaces.

欧几里得数据得名于欧几里得空间——在这种熟悉的 n 维空间中，关于距离、角度和连续性的几何直觉可以自然应用。图像存在于 2D 欧几里得空间中，视频将其扩展到 3D（添加时间维度），文本序列可以被视为来自 1D 欧几里得空间的样本。深度学习在这些领域的成功建立在欧几里得空间的几个关键属性之上。

Translation Invariance stands as perhaps the most crucial property enabling deep learning on images. A cat in the upper-left corner of an image should be recognized identically to a cat in the lower-right corner. CNNs achieve this through weight sharing—convolution filters slide across the image, applying the same transformation at every position. The filter "looks for" the same patterns (edges, textures, shapes) regardless of where they appear, and this invariance to translation is hardcoded into the architecture.

平移不变性可能是使深度学习在图像上取得成功的最关键属性。图像左上角的猫应该与右下角的猫被相同识别。CNN 通过权重共享实现这一目标——卷积滤波器在图像上滑动，在每个位置应用相同的变换。滤波器"寻找"相同的模式（边缘、纹理、形状），无论它们出现在哪里，而这种对平移的不变性被硬编码到架构中。

Local Stationarity complements translation invariance. In natural images, statistical properties are locally consistent—a small patch taken from any region of an image contains similar visual primitives (edges, corners, textures) regardless of the patch's global location. This property, sometimes called local homogeneity, allows CNNs to learn meaningful features from small local receptive fields and compose them hierarchically into larger, more complex patterns.

局部平稳性与平移不变性相辅相成。在自然图像中，统计属性是局部一致的——从图像任何区域获取的小块包含相似的视觉基元（边缘、角落、纹理），无论其全局位置如何。这一属性（有时称为局部同质性）允许 CNN 从小的局部感受野中学习有意义的特征，并将它们层次化地组合成更大、更复杂的模式。

The combination of these properties enables CNNs to achieve