第1章 引言：图与深度学习的交汇 / Chapter 1 Introduction: The Convergence of Graphs and Deep Learning

第 1 章 引言：图与深度学习的交汇

Chapter 1 Introduction: The Convergence of Graphs and Deep Learning

当我们把现实世界抽象为数据，遇到的最普遍也最棘手的形态往往不是图像、不是语音、也不是文本序列，而是一种由离散节点与关系编织而成的结构——图（Graph）。从社交平台上亿用户之间的关注与转发，到制药实验室中由原子与化学键构成的分子；从推荐系统中"用户—商品—标签"共同编织的异构网络，到搜索引擎背后由实体与语义关系堆砌的知识图谱——图无处不在。然而，自 2012 年 AlexNet 引爆深度学习浪潮以来，卷积神经网络（CNN）与循环神经网络（RNN）的辉煌成就，几乎全部建立在欧几里得数据（Euclidean data）之上：图像是规则像素网格，文本是线性词序列，语音是沿时间轴展开的一维信号——它们都被卷积或循环算子天然兼容；而图，是非欧几里得（non-Euclidean）的：节点数不固定，邻居数量因节点而异，节点之间不存在任何先验的全局排序。当我们试图将图像领域的成功经验平移到图数据上时，会遭遇三个看似不可调和的困难——邻域结构可变、节点无序、特征与拓扑必须联合建模。这正是本书试图回答的根本问题：如何为图数据构造专属的神经网络？

本章作为全书的开篇，将依次完成四项任务：（一）阐明图数据的普遍性与非欧几里得特性，并形式化为统一的数学对象；（二）剖析传统 CNN/RNN 为何难以直接处理图，提炼三个本质挑战；（三）梳理图神经网络从 Scarselli 2008 到 Kipf 2017 的演化脉络，勾勒出现代 GNN 家族的研究图谱；（四）预告全书的三条核心主线——图卷积、图注意力与知识图谱表示学习——并给出章节路线图。在实践部分，我们使用 Python 的 NetworkX 库可视化一个 6 节点的社交网络，并演示邻接矩阵的稀疏结构与度分布的不均匀性，奠定后续所有章节的工程直觉。

1.1 图数据的普遍性与非欧几里得特性

1.1.1 现实世界的图回声：从社交网络到分子

Graphs Are Everywhere。在动手设计算法之前，让我们先用四个具体的应用场景，回答一个朴素的问题——究竟哪些现实问题在本质上应该用图来表达？

场景一：社交网络（Social Networks）。在 Twitter、微博、Facebook 这类平台上，每个用户是一个节点（vertex / node），用户之间的关注、好友、转发构成边（edge）。一个用户的特征（年龄、兴趣、历史发文）与其所处的社交圈（neighborhood）共同决定其后续行为。预测用户是否会转化、识别虚假账号、推荐潜在好友，本质上都需要同时利用节点属性与拓扑信息。

场景二：分子与蛋白质结构（Molecules and Proteins）。在药物发现与计算化学领域，一个分子可以视为一张以原子为节点、化学键为边的图。以阿司匹林（Aspirin, C₉H₈O₄）为例：21 个原子通过单键、双键、氢键构成的复杂三维拓扑，决定了分子的化学性质、毒性与生物活性。这一观察催生了 AlphaFold 等变革性工作——它们无一例外地建立在图神经网络之上。

场景三：推荐系统（Recommender Systems）。现代推荐系统的核心数据结构是异构信息网络（heterogeneous information network）或二部图（bipartite graph）。用户—商品、商品—标签、用户—场景之间的多种关系协同决定了推荐质量。仅依赖内容特征会陷入"相似却无惊喜"的窠臼；引入图结构后，系统才能捕捉到"购买过此商品的用户也购买了……"这种协同信号。

场景四：知识图谱（Knowledge Graphs, KG）。以 Google Knowledge Graph、WikiData、Freebase 为代表的大规模语义网络，将世界建模为"实体—关系—实体"的三元组集合（triples）。在 KG 中，节点既可能是具体实体（"北京"），也可能是抽象概念（"首都"），边承载语义关系（"是……的首都"、"邻国"）。基于图的推理——例如从"北京—是首都—中国"与"中国—邻国—印度"推导出"北京与印度存在间接外交语义关联"——正是知识图谱表示学习要解决的任务。

把上述场景抽象出来，可以得到统一的数学对象：图 $G = (V, E)$。其中 $V = \{v_1, v_2, \dots, v_N\}$ 是节点集合（vertex set），$E \subseteq V \times V$ 是边集合（edge set），通常用邻接矩阵（adjacency matrix） $A \in \mathbb{R}^{N \times N}$ 表示，其中 $A_{ij} = 1$ 当且仅当 $(v_i, v_j) \in E$。每个节点可附带一个 $d$ 维特征向量 $x_v \in \mathbb{R}^d$，整张图堆叠为特征矩阵 $X \in \mathbb{R}^{N \times d}$；每条边在带权图中附带权重 $w_{ij}$；在异构图中还可附带类型、时间戳等额外元数据。

1.1.2 非欧几里得性的三层含义

Why Graphs Are Non-Euclidean。当我们说图像是欧几里得的，是指它能被嵌入到规则的低维网格（grid）中：每个像素有固定位置 $(i, j)$，每个像素的邻域（neighborhood）结构是恒定的——左、右、上、下四个方向，卷积核 $\mathbf{K}$ 在图中滑动时，相对位置关系不因位置不同而改变。这种平移不变性（translation invariance）与局部连通性（local connectivity）是 CNN 成功的几何基础。

图数据打破了这两条隐含假设。具体而言，图具有三层非欧几里得性（non-Euclidean property）：

第一层：节点邻域大小可变（variable neighborhood size）。图像中每个像素的邻居数量是常数（4-邻域或 8-邻域）；但在图中，节点 $v$ 的度（degree） $|N(v)|$ 可从 1 到任意大。一个孤立节点的邻居为空集，而一个"枢纽（hub）"节点可能拥有成千上万的邻居。这使得固定大小的卷积核无法直接套用。

第二层：节点无序（no canonical ordering）。图像的像素天然具有 $(i, j)$ 坐标；文本的字符具有从左到右的下标；但图中的节点仅以集合 $\{v_1, \dots, v_N\}$ 的形式存在，任何一种排序都只是某一时刻的偶然选择。换言之，处理图的算子必须满足置换不变性（permutation invariance）：将邻接矩阵 $A$ 的行（列）按任意置换 $P$ 重排后，输出应与原始输出对应同一置换的版本，而不是改变数值。这意味着传统 CNN 中"卷积核权重滑动"这种位置耦合的设计思路不再适用。

第三层：拓扑与特征必须联合编码（joint topology–feature encoding）。图像中拓扑结构是固定网格，而我们要学习的主要是像素值；图中节点特征 $X$ 与连接 $A$ 是同等重要的两个维度，且彼此耦合。例如，引文网络中论文的特征向量（标题、摘要、关键词）与其引用网络（哪些论文引用了它）共同决定了引用次数预测结果；任何只关注其中一方的模型都会损失关键信息。这种耦合使得深度学习模型必须双通道同时输入且能自适应地融合两路信号。

1.1.3 图学习任务的四种典型问题

Tasks of Graph Learning。在 GNN 文献中，下游任务被精炼为四大类，本书后续章节将反复与之呼应：

• **节点级任务（node-level tasks）**：如节点分类、节点回归。例如预测论文学科类别、引文网络中作者科研领域。这是 GCN、GAT 的代表任务。
• **边级任务（edge-level tasks）**：如**链接预测（link prediction）**、边分类。例如预测两个用户是否会成好友、识别知识图谱中缺失的关系。这是知识图谱嵌入的核心任务。
• **图级任务（graph-level tasks）**：如图分类、图回归。例如分子属性预测、蛋白质功能分类。需将整图压缩为一个向量，常用**图池化（graph pooling）**技术。
• **图生成（graph generation）**：生成与给定数据集分布相似的新图。例如药物设计中的新分子生成。本书仅作概念性介绍。

理解上述任务谱系，有助于我们在后续章节中始终保持"模型 → 任务"的对应意识——图神经网络往往为某一类任务量身定制，但具备良好的可迁移性。

1.2 传统深度学习为何难以直接处理图

1.2.1 CNN 假设的网格结构不复存在

从 CNN 的核心算子——二维卷积——谈起。设输入图像 $X \in \mathbb{R}^{H \times W \times C}$，卷积核 $\mathbf{K} \in \mathbb{R}^{h \times w \times C}$，则输出特征图为：

$$Y_{i,j,k} = \sum_{u=0}^{h-1} \sum_{v=0}^{w-1} \sum_{c=0}^{C-1} X_{i+u,\, j+v,\, c} \cdot K_{u,v,c,k}$$

此算子依赖三个隐式前提：（i）输入尺寸固定或可对齐——所有图像要么缩放到同一分辨率，要么使用全卷积网络处理任意尺寸；（ii）邻接像素的位置关系是固定模式——相对偏移 $(u, v)$ 对所有像素 $(i, j)$ 都一致；（iii）通道数 $C$ 与特征维度可设计但非拓扑。这些前提在规则网格（欧几里得空间）上成立，在图上则同时失效。

设想我们有 5 个节点的图，$v_1$ 有 2 个邻居，$v_2$ 有 4 个邻居。我们能为它们定义一个统一大小的卷积核吗？答案是不行——除非引入补零（padding）或者为每个节点单独学习一个核，但这两种做法都无法保证置换不变性，且会显著增加参数。

1.2.2 RNN 假设的序列依赖不成立

再看循环神经网络（RNN）。设时间步 $t$ 的隐藏状态为 $h_t$，则典型更新规则为：

$$h_t = f_W(h_{t-1}, x_t)$$

这一算子假设输入具有全序（total order）：节点之间存在前后（temporal）顺序，且该顺序对任务至关重要。但在图中，节点之间的连接是无序（unordered）、多向（multi-way）、变长（variable-length）的。我们既不知道该先处理哪个节点，也无法定义"前后"关系。如果强行将图节点按某种方式排序（例如按节点编号），则结果将对排序方式高度敏感——这违反了置换不变性原则。

更糟糕的是，RNN 的链式结构天然适合一维序列；而图是网状结构，每个节点有多条入边与出边。要将 RNN 推广到图，Scarselli 等人在 2008 年提出的循环图神经网络（RecGNN）采用了"迭代收敛"思路——每个节点维持一个状态，经若干轮消息交换后达到一个不动点（fixed point）。这是 GNN 的起点，但训练效率不高，难以扩展到现代深度学习栈。

1.2.3 三个本质挑战的总结

Limitations Summarized。综合以上分析，传统深度学习难以直接处理图数据，可归结为三个本质挑战：

1. 置换方差（permutation variance）问题：节点的输入顺序不应影响最终学习结果，但 CNN、RNN 的输入层都敏感于输入顺序。GNN 必须显式嵌入置换等变性（permutation equivariance）——即对 $G$ 施加任意节点置换 $\pi$，输出特征向量对应地置换 $h_{\pi(v)} = \pi(h_v)$。 2. 邻居大小可变（variable neighborhood size）问题：CNN 卷积核大小固定，RNN 输入长度固定。GNN 必须设计一种自适应聚合算子，对任意大小的邻居集合都有效。 3. 拓扑结构未编码（unencoded topology）问题：CNN 假设拓扑是规则网格，RNN 假设拓扑是线性链。GNN 必须将邻接矩阵 $A$（或其变体）作为一等公民纳入计算图，使其与节点特征 $X$ 共同参与梯度学习。

这三个挑战构成了 GNN 设计的"不可能三角"——任何 GNN 方案都要在这三者之间做出精巧的平衡。这也解释了为什么 2008 至 2016 年间，大量研究者尝试了递归神经网络、信念传播、图核等思路，却只有当卷积思想被巧妙改造后（Gori 2005、Bruna 2013、Defferrard 2016、Kipf 2017），领域才真正起飞。

1.3 图神经网络的演化历程：从 Scarselli 到 Kipf

1.3.1 前深度学习时代的种子：循环图神经网络（RecGNN）

RecGNN。图神经网络并非 2017 年凭空出现，其思想可以追溯到更早。图灵奖得主 Judea Pearl 在 1980 年代发展了信念传播（Belief Propagation, BP）算法——一种在图模型（graphical model）上进行概率推理的消息传递（message passing）机制。其核心思想是：每个节点与其邻居交换"信念"消息，迭代若干轮后达到收敛。该算法虽未直接催生现代 GNN，但是消息传递这一核心抽象的原点。

2005 年，Gori、Monfardini 与 Scarselli 首次提出"图神经网络（Graph Neural Network）"一词，并提出基于 RNN 思想的早期模型：

$$h_v^{(t+1)} = f_{\theta}\left( x_v, \sum_{u \in N(v)} g_{\theta}(x_v, x_u, x_{vu}) \right)$$

其中 $f_{\theta}, g_{\theta}$ 为可学习参数。该更新在若干轮迭代后会收敛到一个不动点，再以监督信号训练。

2008 至 2009 年，Scarselli 等人在 IEEE Transactions on Neural Networks 上发表两篇奠基性论文，将这一思路形式化为端到端可训练模型：状态更新通过反复运行"过渡函数（transition function）"直到收敛，再通过输出函数得到最终预测。这一类模型后来被称为循环图神经网络（Recurrent GNN, RecGNN）。其优点是理论上可逼近任何在图上定义的函数；缺点是计算缓慢、难以并行、难以堆叠多层——这正是彼时主流深度学习框架极力避免的痛点。

1.3.2 卷积图神经网络的崛起：频域与空域的分岔

ConvGNN。当深度学习在 2012 年因 AlexNet 改变计算机视觉格局时，研究者开始思考：能否将"卷积"这一优雅操作带入图的世界？

2013 年，Bruna、Zaremba、Szlam 与 LeCun 在 ICLR 发表第一篇真正意义上的谱图卷积网络（Spectral GCN）——他们将图上的卷积定义为图傅里叶变换（Graph Fourier Transform）后的逐元素相乘。具体地，利用归一化拉普拉斯矩阵（normalized Laplacian）：

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

其特征分解 $L = U \Lambda U^{\top}$ 给出图傅里叶基（graph Fourier basis）。在此基础上，谱卷积定义为：

$$X *_G \mathbf{K} = U \left( U^{\top} X \odot U^{\top} \mathbf{K} \right)$$

其中 $\odot$ 表示逐元素乘积。这一公式虽数学优美，但有三个问题：（i）特征分解 $O(N^3)$ 的复杂度对大图不友好；（ii）依赖固定图结构，对新节点不具推广能力；（iii）不同图上的滤波器参数不可迁移。

2016 年，Defferrard、Bresson 与 Vandergheynst 提出 ChebNet，利用切比雪夫多项式（Chebyshev polynomial）展开将谱卷积近似为局部聚合：

$$X *_G \mathbf{K} \approx \sum_{k=0}^{K-1} \theta_k T_k(\tilde{L}) X$$

其中 $T_k$ 为切比雪夫多项式，$\tilde{L}$ 为放缩后的拉普拉斯矩阵。这一改动将计算复杂度降低至 $O(K \cdot |E|)$，且滤波器具有空间局部性。

2017 年，Kipf 与 Welling 在 ICLR 发表 GCN（Graph Convolutional Network）——这是迄今为止最具影响力的 GNN 工作。他们将切比雪夫多项式截断到 $K=1$，并加上重归一化技巧：

$$H^{(l+1)} = \sigma\left( \tilde{D}^{-1/2} \tilde{A} \tilde{D}^{-1/2} H^{(l)} W^{(l)} \right)$$

其中 $\tilde{A} = A + I$ 是加自环的邻接矩阵，$\tilde{D}$ 为对应度矩阵，$\sigma$ 为激活函数。这个看似简洁的公式揭示了一个深刻事实：节点的新特征是其邻居（包含自身）特征的加权平均，再经过线性变换与激活。这一公式后来被无数后续工作继承、改造、扩展，催生了整个 GNN 生态系统。

同年，Hamilton、Ying 与 Leskovec 在 NeurIPS 提出 GraphSAGE（SAmple and aggreGatE）——它从空域（spatial domain）视角出发，强调邻居采样（neighbor sampling）与多种聚合函数（aggregation functions），使模型可以高效地推广到推理时未见的新节点。

2018 年，Veličković 等人在 ICML 发表 GAT（Graph Attention Network），将注意力机制（attention mechanism）引入图聚合：每个邻居的权重由其与中心节点的特征相似度动态决定，而非预先由拓扑结构固化：

$$\alpha_{ij} = \