第一章 图神经网络概述：从欧几里得数据到非欧几里得数据 / Chapter 1: Overview of Graph Neural Networks — From Euclidean to Non-Euclidean Data

第一章：图神经网络概述：从欧几里得到非欧几里得数据

Chapter 1: Overview of Graph Neural Networks — From Euclidean to Non-Euclidean Data

1.1 引言：深度学习时代的数据困境

为什么我们需要为图结构数据（graph-structured data）单独设计一类神经网络？这是本书试图回答的核心问题。要回答这个问题，必须从一个更基础的事实出发：现实世界的数据并非都以规则的网格形式存在。

过去十余年间，深度学习（Deep Learning, DL）在多个领域取得了突破性进展。卷积神经网络（Convolutional Neural Networks, CNN）在图像分类、目标检测、图像分割等任务中表现卓越；循环神经网络（Recurrent Neural Networks, RNN）及其变体长短期记忆网络（Long Short-Term Memory, LSTM）和门控循环单元（Gated Recurrent Unit, GRU）在机器翻译、文本生成、语音识别等序列任务上大放异彩；近年来，基于自注意力机制（self-attention mechanism）的 Transformer 模型更进一步统一了自然语言处理与计算机视觉的建模范式。然而，这些成就高度依赖于一个隐含假设：输入数据具有规则的结构（regular structure）。CNN 假设输入是位于二维或三维欧几里得网格（Euclidean grid）上的像素或体素，RNN 假设输入是按时间顺序排列的序列，Transformer 则假设输入可以被切分为可线性化的 token。

这一假设在很多场景下是成立的，但在另外一些同样重要、同样普遍的场景下则并不成立。我们只需要环顾四周，就能找到大量"非网格"的数据形态：社交网络中用户之间的好友关系、分子中原子之间的化学键、城市之间通过道路或航线形成的交通网络、论文之间的引用关系、蛋白质之间的相互作用、电商平台中用户与商品之间的购买行为……这些数据都有一个共同特征：它们天然地以"图"（graph）的形式存在，节点（node）之间通过边（edge）相连，呈现出不规则的拓扑结构（irregular topology）。

如果我们尝试用传统的深度学习方法直接处理这些图数据，立刻会遭遇一系列困难：图像的卷积核（convolutional filter）依赖于像素的固定邻域结构，但图中的节点邻居数量是可变的；RNN 假设严格的时序关系，但图中的连接可以是任意的、无序的；Transformer 假设输入 token 之间是全连接的或可线性化的，但图通常具有稀疏的局部连接结构。这些困难并非工程实现上的不便，而是反映了传统深度学习方法的归纳偏置（inductive bias）与图数据的本质特征之间存在根本性的不匹配。

正是在这样的背景下，图神经网络（Graph Neural Networks, GNN）应运而生。GNN 是一类专门为图结构数据设计的神经网络，其核心思想是通过消息传递（message passing）机制，让每个节点从其邻居处聚合信息，从而学习到包含局部结构信息的节点表示（node representation）。这一范式既保留了深度学习的强大表达能力，又能适应图的非欧几里得性质。

本章将围绕这一核心问题展开：图数据为什么无法被传统深度学习方法有效处理？GNN 的出现解决了哪些根本性问题？通过对欧几里得数据与非欧几里得数据本质区别的剖析，对图作为通用数据结构的展示，对传统模型局限性的分析，以及对 GNN 核心思想的初步介绍，本章将为读者建立起学习后续章节所需的统一概念框架。

In the past decade, deep learning has achieved remarkable breakthroughs across multiple domains. However, these achievements rely heavily on an implicit assumption: input data has a regular structure. This assumption holds in many scenarios, but fails in many equally important and equally common ones. Graph-structured data, with its irregular topology, variable neighborhood sizes, and permutation invariance requirements, exposes a fundamental mismatch with the inductive biases of CNN, RNN, and Transformer architectures. Graph Neural Networks (GNNs) emerged precisely to address this mismatch, and this chapter lays the conceptual foundation for understanding why and how.

1.2 欧几里得数据与非欧几里得数据

要理解图数据为什么特殊，首先需要明确欧几里得数据（Euclidean data）与非欧几里得数据（non-Euclidean data）的本质区别。这一区别不仅是几何上的，更关系到数据所携带的归纳偏置与可用的算法工具。

1.2.1 欧几里得数据的形式化定义

在数学上，欧几里得空间（Euclidean space）$\mathbb{R}^n$ 是配备了标准内积与欧几里得距离的实数向量空间。当我们说"数据是欧几里得的"，我们指的是数据点可以自然地表示为 $\mathbb{R}^n$ 中的向量或张量，并且这些向量之间具有规则的邻域结构（regular neighborhood structure）。

具体来说，欧几里得数据通常具备以下三个关键性质：

1. 固定维度（Fixed Dimensionality） 一个图像无论尺寸如何，都可以表示为一个三维张量 $X \in \mathbb{R}^{H \times W \times C}$，其中 $H$ 是高度，$W$ 是宽度，$C$ 是通道数。一段文本可以被表示为 $\mathbb{R}^{T \times d}$ 的矩阵，其中 $T$ 是 token 数，$d$ 是嵌入维度。维度虽然在样本之间可以变化，但在数学处理上具有清晰的几何意义。

2. 平移不变性（Translation Invariance） 对图像的局部操作（如卷积）不依赖于该局部在图像中的绝对位置。一个 $3 \times 3$ 的卷积核，无论它作用在图像的左上角还是右下角，其计算方式完全相同。这种平移不变性是 CNN 能够通过权值共享（weight sharing） 大幅减少参数数量、并在不同位置提取相同模式特征的数学基础。

3. 规则的局部邻域（Regular Local Neighborhood） 欧几里得数据中，每个数据点（像素、token）都有固定数量、规则排列的邻居。例如，在二维图像中，每个内部像素恰好有 8 个邻居（上下左右加四个对角）；在文本序列中，每个 token 至少有两个邻居（前后）。这种规则性使得我们可以预先定义"卷积核"或"感受野（receptive field）"的形状与大小。

常见的欧几里得数据包括：一维信号（语音、心电图）、二维图像（照片、医学影像）、三维体素数据（CT、MRI 扫描）、以及可以被分词并线性化的文本序列。

1.2.2 非欧几里得数据的本质特征

与欧几里得数据相对，非欧几里得数据指的是其底层支撑结构（underlying support）不具有规则网格性质的数据。最典型的非欧几里得数据就是图（graph）——它由节点集合 $V$ 和边集合 $E$ 构成，记为 $G = (V, E)$。此外，流形（manifold）和网格（mesh）也属于非欧几里得数据的范畴。

图数据具有以下几项根本不同于欧几里得数据的特征：

1. 可变的拓扑结构（Variable Topology） 不同图之间的节点数量、边的数量、连通性、密度都可以有巨大差异。同一张图中，不同节点的度（degree，即邻居数量）也可以相差悬殊。例如，在社交网络中存在少数"意见领袖"拥有数百万粉丝，而绝大多数普通用户只有几百个朋友。这种度分布的不均匀性（degree heterogeneity） 是图数据的普遍特征。

2. 节点的无序性（No Canonical Ordering） 图像的像素有天然的位置坐标（左上角是 $(0,0)$），文本的 token 有天然的时间顺序（第一个字出现在最前面）。但图的节点没有这样的先验顺序（a priori ordering）。我们可以任意地对节点重新编号，只要保持边的连接关系不变，图本身没有任何改变。

3. 复杂的依赖关系（Complex Dependencies） 图中节点之间的依赖关系由边显式编码，并且这种依赖可以是远距离的、非局部的。例如，在引文网络中，论文 A 引用论文 B，B 又引用 C，A 与 C 之间可能存在一条隐含的"信息流动"路径。这种长程依赖（long-range dependency） 与序列数据中的依赖关系有本质区别，因为图中的路径不唯一且可以形成环。

4. 边与节点可以携带属性（Edge and Node Attributes） 图的边可以有权重（weight）、方向（direction）、类型（type）。例如，在知识图谱中，边表示"出生于""工作于"等不同语义关系；在交通网络中，边权重可以表示道路长度或通行时间。节点本身也可以携带丰富的属性特征。

1.2.3 形式化对比

为了更清晰地展示两类数据的差异，我们用以下对比表说明：

| 特征 / Feature | 欧几里得数据 | 非欧几里得数据（图） | |---|---|---| | 支撑空间 | $\mathbb{R}^n$（规则网格） | 离散拓扑结构 | | 维度 | 固定 | 可变 | | 节点邻居数 | 固定且规则 | 可变且不规则 | | 平移不变性 | 成立 | 不成立 | | 排列不变性 | 弱（坐标有物理意义） | 强（节点无序） | | 典型操作 | 卷积、池化 | 消息传递、聚合 |

这种对比并不只是抽象的概念区分，它直接影响着可用的算法工具。在欧几里得空间中，我们可以借助傅里叶变换（fourier transform）将卷积转换为频域乘法；可以在网格上定义稳定的上采样与下采样算子；可以利用数据的平移对称性实现参数共享。但在图上，这些工具要么不存在，要么需要重新设计。

下图从数据结构的角度展示了欧几里得数据与非欧几里得数据的差异，以及深度学习方法的演进路径：

```mermaid flowchart TD A[Real-World Data] --> B{Structural Type} B --> C[Euclidean Data] B --> D[Non-Euclidean Data] C --> E[Images, Text, Audio] E --> F[CNN / RNN / Transformer] F --> G[Mature Toolkits and Theory] D --> H[Graphs, Manifolds, Meshes] H --> I[Classical Graph Methods] I --> J[Limited Expressive Power] H --> K[Graph Neural Networks] K --> L[Unified Representation Learning] ```

1.2.4 为什么这一区别至关重要

理解欧几里得与非欧几里得数据的区别，关键在于认识到：深度学习并非"放之四海而皆准"的通用工具，而是一类高度依赖数据先验结构的方法。当我们说"CNN 适用于图像"时，我们其实在说"图像的平移不变性和局部相关性这两个归纳偏置，恰好被 CNN 的架构设计所匹配"。一旦数据不再具备这些偏置，传统深度学习方法的性能就会显著下降。

这正是图神经网络研究的起点：与其把图强行塞进现有架构，不如为图量身定制一类新方法。这并不是说图数据无法用任何深度学习方法处理，而是说需要发展新的归纳偏置、新的运算定义、新的理论分析框架。

1.3 图：一种通用的数据结构

图并非仅仅是计算机科学中的一个抽象概念，它是描述实体间关系的最通用语言。在深入讨论图神经网络之前，有必要先理解图为何如此普遍，以及它如何用数学语言精确刻画。

1.3.1 图的数学定义

一个图（graph）由两个集合组成：节点集（vertex set）$V$ 和边集（edge set）$E$。形式化地记为 $G = (V, E)$，其中 $V = \{v_1, v_2, \ldots, v_n\}$，$E \subseteq V \times V$。节点的数量记为 $|V| = n$，边的数量记为 $|E| = m$。

根据边是否有方向，图可分为有向图（directed graph）和无向图（undirected graph）。根据边上是否带有权重，可分为加权图（weighted graph）和无权图（unweighted graph）。根据节点和边是否携带类型信息，可分为同构图（homogeneous graph）和异构图（heterogeneous graph）。本书在第二章会系统介绍这些变体。

1.3.2 邻接矩阵与度矩阵

对于一个包含 $n$ 个节点的图 $G$，我们可以用一个 $n \times n$ 的矩阵完整地描述其拓扑结构，这个矩阵称为邻接矩阵（adjacency matrix），记为 $A$：

$$ A_{ij} = \begin{cases} 1, & \text{if } (v_i, v_j) \in E \\ 0, & \text{otherwise} \end{cases} $$

对于无向图，$A$ 是对称矩阵，即 $A_{ij} = A_{ji}$。对于加权图，$A_{ij}$ 可以是任意非负实数，表示边 $(v_i, v_j)$ 的权重。注意对角线元素 $A_{ii}$ 通常为 0（除非显式定义自环）。

与邻接矩阵密切相关的另一个矩阵是度矩阵（degree matrix） $D$，它是一个对角矩阵：

$$ D_{ii} = \sum_{j=1}^{n} A_{ij} = d(v_i) $$

其中 $d(v_i)$ 是节点 $v_i$ 的度（degree），即与该节点相连的边的数量。

拉普拉斯矩阵（Laplacian matrix） $L$ 是图论与图信号处理中的核心工具，定义为：

$$ L = D - A $$

拉普拉斯矩阵有许多优美的性质：它的每一行之和为零（$L \mathbf{1} = \mathbf{0}$，其中 $\mathbf{1}$ 是全一向量）；它是半正定的（positive semi-definite）；它的特征值与特征向量携带了丰富的图结构信息。对称归一化拉普拉斯（symmetric normalized Laplacian） 进一步定义为：

$$ L_{sym} = I - D^{-1/2} A D^{-1/2} $$

这一归一化形式在图卷积网络（Graph Convolutional Network, GCN）等模型中扮演着关键角色。

1.3.3 节点特征矩阵

除了拓扑结构，现实世界中的图节点和边通常还携带属性信息（attributes）。我们用一个节点特征矩阵（node feature matrix） $X \in \mathbb{R}^{n \times d}$ 来表示所有节点的特征，其中 $X_i \in \mathbb{R}^d$ 是节点 $v_i$ 的 $d$ 维特征向量。

例如，在引文网络中，每个节点代表一篇论文，其特征可以是该论文的词袋（bag-of-words）向量或 TF-IDF 向量；在分子图中，每个节点代表一个原子，其特征可以包括原子序数、化合价、电负性等化学属性。图的完整表示通常需要同时编码拓扑结构 $A$ 和节点特征 $X$，二者缺一不可。

1.3.4 图在现实世界中的普遍存在

图的普遍性怎么强调都不过分。以下是几个典型的应用领域：

1. 社交网络（Social Networks） Facebook、Twitter、微信、微博等社交平台的本质是大型社交图。用户是节点，好友关系或关注关系是边，用户的个人资料、发布的帖子可以视为节点特征。基于社交图谱可以完成好友推荐、社区发现、影响力最大化、虚假账号检测等任务。社交图谱通常具有小世界（small-world） 特性：平均路径长度很短，但聚类系数很高。

2. 分子与蛋白质结构（Molecular and Protein Structures） 分子可以自然地表示为原子为节点、化学键为边的图。例如，水分子（H₂O）是一个包含两个氢原子和一个氧原子的图，氧与每个氢之间各有一条边。蛋白质是更复杂的图，氨基酸是节点，它们之间的肽键和空间相互作用构成边。深度学习在分子领域的应用包括分子性质预测（molecular property prediction）、药物-靶点亲和力预测（drug-target affinity prediction）、蛋白质结构预测（如 AlphaFold 系列）以及药物发现（drug discovery）。图神经网络已经在这些任务上取得显著成果，部分原因在于分子的图表示直接对应化学家的认知方式。

3. 交通网络（Transportation Networks） 城市地图是图，路网交叉口是节点，道路是边，道路长度、通行能力是边权重。航班网络是图，机场是节点，航线是边。地铁网络、铁路网络、公路网络都属于这一类。基于交通图，可以进行最短路径规划（shortest path planning）、交通流量预测（traffic flow forecasting）、路径推荐（route recommendation）。许多城市智能交通系统的核心算法都