第 1 章　图与深度学习的交汇：为何需要图神经网络 / The Convergence of Graphs and Deep Learning: Why GNNs?

第 1 章　图与深度学习的交汇：为何需要图神经网络

The Convergence of Graphs and Deep Learning: Why GNNs?

关系型数据普遍存在于现实世界之中，而传统的深度学习模型——卷积神经网络（CNN）、循环神经网络（RNN）乃至 Transformer——几乎都是为欧几里得空间中的规则数据设计的。当数据呈现出复杂的关联结构、动态的拓扑以及不规则的邻居数量时，这些模型便面临根本性的适配困难。图神经网络（Graph Neural Network, GNN）的崛起，正是深度学习从规则网格迈向关系结构的关键一步。本章将系统回答三个核心问题：什么是图数据？为什么传统深度学习难以直接处理图结构？图神经网络的核心思想是什么？

1.1 图作为通用数据结构：现实世界的关系图景 / Graphs as Universal Data Structures: The Relational Landscape of Reality

要理解图神经网络的价值，首先必须理解"图"这一数据结构本身的普遍性与独特性。图（Graph）在数学上由节点（node / vertex）和边（edge）构成，可形式化表示为 $G = (V, E)$，其中 $V$ 是节点的有限集合，$E \subseteq V \times V$ 是边的集合。如果边附带方向，则称为有向图（directed graph）；若边附带权重，则称为加权图（weighted graph）；若两个节点之间允许多种关系，则称为多重图（multigraph）。这些看似简单的定义，却足以刻画现实世界中绝大多数复杂系统的骨架。

图在现实世界中的存在远比多数人直觉所感知的更加广泛。在社交网络（social network）中，用户是节点，关注、好友、转发等交互构成边；在分子结构（molecular structure）中，原子是节点，化学键是边；在交通网络（transportation network）中，城市或路口是节点，道路或航线是边；在推荐系统（recommender system）中，用户与商品是节点，交互行为构成二部图（bipartite graph）；在知识图谱（knowledge graph）中，实体是节点，关系是带有语义标签的边。可以说，几乎所有"实体 + 关系"构成的系统，都可以用图来建模。

图数据的独特性体现在三个方面：关系依赖（relational dependency）、拓扑结构（topology）与不规则性（irregularity）。关系依赖意味着节点的属性往往受到其邻居的强烈影响——朋友的态度会影响你的判断，原子的成键环境决定分子的性质。拓扑结构指节点之间的连接模式本身携带信息，例如社交网络中的社区结构、分子中的环状子结构、电网中的关键枢纽节点。不规则性则指节点邻居数量可变、节点排列无固定顺序、图规模差异巨大等特点。这三点共同构成了图数据与传统表格、图像、文本数据的本质区别，也正是这种区别使得图成为一个独立的数据类型，需要专门的学习方法。

以一个具体例子来说明：考虑一个拥有 1000 名用户的社交网络。用户 A 关注了 B、C、D 三人，用户 B 关注了 A、E 两人。如果我们要预测 A 是否会购买某产品，仅凭 A 的历史行为信息显然不够——还必须考虑 A 的关注对象（B、C、D）的偏好，因为社交影响（social influence）会显著改变用户决策。这就是图数据中典型的"邻居驱动"现象：节点的标签、行为甚至身份，都部分由其在图中的位置所决定。

理解图数据普遍性的另一关键视角是，许多看似非图的数据都可以转化为图的形式。例如，图像可以被视为像素构成的规则图，每个像素连接其邻域像素；文本可以被视为单词按顺序连接的链状图（chain graph）；分子可以被视为原子与化学键的图结构。这种"图视角的统一性"（unifying view of graphs）正是 GNN 能够成为通用机器学习工具的理论基础。

1.2 欧几里得空间与非欧几里得空间的本质差异 / The Essential Difference Between Euclidean and Non-Euclidean Spaces

要回答"为何传统深度学习难以处理图"，必须先理解一个更深层的问题：数据的几何性质（geometric property）。深度学习的几大支柱——CNN、RNN、Transformer——都对数据的几何结构做出了明确的假设。这些假设在欧几里得空间中成立，却无法迁移到图所在的非欧几里得空间。

欧几里得数据（Euclidean data）指的是可以在规则网格上采样的数据，典型代表是图像和文本。一张 $H \times W$ 的彩色图像具有三维张量结构 $X \in \mathbb{R}^{H \times W \times C}$，其中 $H$ 和 $W$ 是空间维度，$C$ 是通道数。每个像素有固定的二维坐标 $(i, j)$，其邻居（如上下左右四个像素）数量恒定且易于索引。文本序列则是一维链式结构，每个 token（词元）有固定的前后邻居。这种"规则性"（regularity）正是 CNN 与 RNN 得以高效运作的基础。

CNN 的核心操作——卷积（convolution）——依赖于一个关键的归纳偏置（inductive bias）：平移等变性（translation equivariance）。这意味着无论特征出现在图像的哪个位置，卷积核都能以相同的方式检测它。这种偏置之所以强大，是因为图像中物体的位置可以变化但语义保持稳定。然而，图的节点并没有像图像那样固定的位置——两个节点是否"相邻"取决于边的存在，而不是坐标的接近程度。换言之，图上的"平移"概念本身就没有清晰定义。

RNN 的核心操作——循环（recurrence）——则假设数据存在天然的线性顺序。无论是 LSTM 还是 GRU，它们都按时间步（time step）依次处理序列，每个时间步的隐藏状态仅依赖于前一时间步。这种假设对于文本是合理的，但对于图则完全失效：图中的节点并无"先后顺序"，从节点 A 出发到达节点 B 可以经过任意路径，路径选择本身携带信息。

那么，非欧几里得数据（non-Euclidean data）究竟有何本质特征？数学上，欧几里得空间 $\mathbb{R}^n$ 具有平移不变性与完备的线性结构，可以定义距离、角度、坐标系等概念。而图所栖居的空间是一个流形（manifold）或组合结构（combinatorial structure），其本质特征包括：

1. 邻居数量可变（variable neighborhood size）：在图像中，每个像素都有恰好 4 个或 8 个邻居；在文本中，每个词元都有恰好 1 个前驱和 1 个后继（除端点外）。但在图中，节点的度（degree）可以是从 0 到任意正整数的任何值。例如，在一个社交网络中，普通用户可能有几十个朋友，而明星用户可能有数千万粉丝。这种"度分布"的极端不均衡使得 CNN 的固定大小卷积核完全失效。

2. 排列不变性（permutation invariance）：图没有"自然的"节点顺序。同一个图可以通过任意置换矩阵 $P$ 重排节点而保持结构不变：$P A P^\top$ 与 $A$ 表示同一图（这里 $A$ 是邻接矩阵）。这意味着任何图上的函数都必须满足 $f(P A P^\top) = f(A)$。但传统的向量输入则不具备这一性质——改变输入向量的元素顺序会改变输出。

3. 拓扑不规则（irregular topology）：欧几里得空间是连续的、平坦的；而图是离散的、可能有任意连接模式。两个节点之间的"距离"通过跳数（hop count）而非欧氏距离度量，图的直径（diameter）可能极小（如完全图）或极大（如链状图）。

4. 异质性（heterogeneity）：真实世界的图常常是异质的——节点有多种类型，边有多种关系，属性维度不一致。这种异质性比图像（像素类型一致）或文本（词元类型一致）复杂得多。

这四点共同构成图数据的"非欧几里得性质"，也是传统深度学习难以直接迁移的根本原因。理解这些性质，比记住任何具体 GNN 模型都更为重要——它构成了所有 GNN 设计背后的"为什么"。

1.3 GNN 的核心思想：邻居聚合的诞生 / The Core Idea of GNNs: The Birth of Neighborhood Aggregation

面对图数据的非欧几里得特性，研究者需要找到一种既保留深度学习强大表示能力，又能尊重图结构约束的学习范式。这一范式的核心思想可以凝练为一句话：通过迭代地聚合邻居信息来学习节点的表示（learning node representations by iteratively aggregating neighborhood information）。这就是图神经网络最核心、最根本的设计哲学。

直觉上，节点的"语义"由两部分构成：自身属性（feature）和它在图中的位置（structural role）。CNN 在图像中通过卷积融合像素邻域的信息，类比到图中，GNN 通过邻居聚合（neighborhood aggregation）将每个节点的邻居特征融合进自身的表示。这一想法可以追溯到一个朴素但深刻的观察：节点的含义由其邻居决定（a node is known by the company it keeps）。在社交网络中，一个用户的兴趣很大程度上由其关注的人所塑造；在分子中，一个原子的化学性质由其成键的邻居所决定；在引文网络中，一篇论文的主题由其引用的文献所暗示。

形式化地，GNN 的每一层都执行以下操作：对于每个节点 $v$，将其第 $k$ 层的隐藏表示 $\mathbf{h}_v^{(k)}$ 通过邻居的特征与自身的特征共同更新。这一过程可以用一个抽象的"消息传递"（message passing）框架描述：

$$ \mathbf{m}_{\mathcal{N}(v)}^{(k)} = \text{AGGREGATE}^{(k)}\left(\{\mathbf{h}_u^{(k-1)} : u \in \mathcal{N}(v)\}\right) $$

$$ \mathbf{h}_v^{(k)} = \text{UPDATE}^{(k)}\left(\mathbf{h}_v^{(k-1)}, \mathbf{m}_{\mathcal{N}(v)}^{(k)}\right) $$

其中 $\mathcal{N}(v)$ 是节点 $v$ 的邻居集合，$\text{AGGREGATE}$ 与 $\text{UPDATE}$ 是可学习的函数（通常为神经网络），$\mathbf{m}_{\mathcal{N}(v)}^{(k)}$ 是从邻居聚合得到的消息。通过堆叠 $K$ 层这样的聚合，每个节点的最终表示 $\mathbf{h}_v^{(K)}$ 就编码了其 $K$ 跳邻居的信息。

这一设计天然满足图数据的关键性质：

• **排列不变性**（permutation invariance）：只要 AGGREGATE 函数对输入集合的顺序不敏感（例如求和、求平均、取最大值），最终的节点表示就与邻居的访问顺序无关。
• **邻居数量可变**（variable neighborhood size）：AGGREGATE 函数可以处理任意大小的邻居集合，无需固定大小。
• **参数共享**（parameter sharing）：同一套 AGGREGATE 与 UPDATE 参数被图中的所有节点共享，符合深度学习的归纳学习精神。
• **局部性**（locality）：每层聚合仅考虑一跳邻居，深度 $K$ 则对应 $K$ 跳感受野，与 CNN 的局部卷积异曲同工。

值得注意的是，邻居聚合并非凭空出现——它有深刻的历史渊源。早在 2005 年，Google 的 PageRank 算法本质上就是邻居聚合的一种特例：每个节点的 PageRank 值是其邻居贡献的递归加权和。2008 年 Scarselli 等人提出的初代 GNN 则将这一思想推广到通用神经网络框架。然而，邻居聚合真正成为深度学习的主流范式，要等到 2017 年 Kipf 和 Welling 提出的 GCN（Graph Convolutional Network）以及 Hamilton 等人提出的 GraphSAGE。

理解邻居聚合这一核心思想之所以重要，是因为几乎所有现代 GNN 变体——GCN、GraphSAGE、GAT（Graph Attention Network）、GIN（Graph Isomorphism Network）——都可以被视为这一框架的不同实例化。它们的区别仅在于 AGGREGATE 的具体形式（求和？平均？注意力加权？）、UPDATE 的实现（拼接？相加？LSTM？）以及是否引入残差连接与归一化。抓住"邻居聚合"这一主线，再去理解各种 GNN 变体就如同理解同一首歌的不同改编版——旋律一致，和声各异。

1.4 从谱方法到空间方法：GNN 的发展简史 / From Spectral Methods to Spatial Methods: A Brief History of GNN Development

图神经网络并非一夜崛起。它的演进经历了从理论铺垫到工程突破的多个阶段，每一步都凝聚着研究者对"图上的学习"这一问题的深入思考。回顾这段历史不仅有助于理解现有模型的设计动机，也能帮助我们预见未来可能的发展方向。

第一阶段：理论萌芽期（2005–2012）。这一时期的核心成就是确立了"图上的学习"这一研究问题本身。2005 年，Gori、Monfardini 与 Scarselli 提出了图神经网络的初步构想（被部分文献追溯为最早的 GNN 雏形）。2008 年，Scarselli 等人在 IEEE TNN 上发表的论文 *The Graph Neural Network Model* 正式确立了初代 GNN 框架：基于递归的状态转移，每个节点通过迭代地吸收邻居信息直至收敛到一个不动点（fixed point），然后再用于下游任务。这一框架是状态机式的而非前馈式的，训练过程依赖 Almeida-Pineda 算法，效率较低，但确立了"通过图结构传播信息"这一核心思想。这一阶段的另一重要线索是图嵌入（graph embedding）领域的发展——DeepWalk（2014）、LINE（2015）、node2vec（2016）等方法通过随机游走与 Skip-gram 思想将节点映射到向量空间，为后续的 GNN 提供了概念基础。

第二阶段：谱方法时代（2013–2016）。这一阶段的标志性工作来自 Bruna 等人 2013 年发表于 ICLR 的论文 *Spectral Networks and Locally Connected Networks on Graphs*。作者从图信号处理（graph signal processing）的角度出发，将传统卷积神经网络中的卷积操作推广到图上。其核心思想是：图上的卷积可以通过图傅里叶变换（graph Fourier transform）在谱域（spectral domain）实现。具体地，对图拉普拉斯矩阵 $L = D - A$（其中 $D$ 是度矩阵，$A$ 是邻接矩阵）进行特征分解 $L = U \Lambda U^\top$，图的卷积可定义为对角化滤波器 $g_\theta(\Lambda)$ 作用于频谱系数：

$$ g_\theta \star x = U g_\theta(\Lambda) U^\top x $$

这一方法理论优美，但存在三个根本问题：（1）需要对 $L$ 进行特征分解，计算复杂度为 $O(n^3)$，对大规模图不可行；（2）滤波器依赖图的全局结构，难以泛化到不同大小的图；（3）滤波器在空间域缺乏局部性。2016 年，Defferrard、Bruna 和 Vandergheynst 提出的 ChebNet 通过使用切比雪夫多项式（Chebyshev polynomial）逼近滤波器，将计算复杂度降低到 $O(|E|)$，并赋予滤波器空间局部性，但仍未彻底解决泛化性问题。

第三阶段：空间方法崛起与 GCN 时代（2017–2019）。2017 年是图神经网络发展的关键转折点。Kipf 和 Welling 在 ICLR 发表的 *Semi-Supervised Classification with Graph Convolutional Networks* 提出了著名的 GCN 模型，通过两个关键简化实现了突破：（1）将切比雪夫多项式截断到一阶，相当于仅使用最近的邻居信息；（2）引入对称归一化的邻接矩阵 $\hat{A} = \tilde{D}^{-1/2} \tilde{A} \tilde{D}^{-1/2}$（其中 $\tilde{A} = A + I$ 添加自环，$\tilde{D}$ 是相应的度矩阵）。最终 GCN 的逐层传播规则异常简洁：

$$ H^{(l+1)} = \sigma\left(\hat{A} H^{(l)} W^{(l)}\right) $$

其中 $H^{(l)}$ 是第 $l$ 层的节点表示矩阵，$W^{(l)}$ 是可学习参数，$\sigma$ 是激活函数。这一公式的美妙之处在于：它同时具备空间局部性（每次更新仅聚合直接邻居）、参数高效（每层仅 $W^{(l)}$ 一个权重矩阵）和可扩展性（通过稀疏矩阵乘法在 $O(|E|)$ 时间内计算）。GCN 一经提出便迅速成为节点分类、链接预测等任务的主流基线，并激发了后续大量变体。

同年，Hamilton、Ying 和 Leskovec 提出的 GraphSAGE（SAmple and aggreGatE）从另一角度突破：它通过采样固定大小的邻居而非使用全部邻居，使模型可以扩展到大规模图；并提出了三种聚合器——均值（mean）、池化（pool）和 LSTM——为后续研究者提供了清晰的模板。2018 年，Velickovic 等人提出的 GAT（Graph Attention Network）将注意力机制（attention mechanism）引入邻居聚合，让模型自适应地学习邻居的重要性权重，进一步提升了表达能力。

第四阶段：多样化与深度化（2019 至今）。2019 年后，GNN 研究进入"百花齐放"阶段。在表达能力（expressive power）方面，Xu 等人的 **GIN