万物皆图：为什么我们需要图神经网络 / Everything is a Graph: Why We Need GNNs

第 1 章：万物皆图——为什么我们需要图神经网络

Chapter 1: Everything is a Graph — Why We Need GNNs

1.1 一个失败的实验：把分子塞进卷积神经网络

让我们从一个真实的工程事故开始。2021 年初，某药物发现团队（这里隐去公司名）尝试用 ResNet-50 预测分子毒性。他们把分子画成 2D 图像，每个原子对应一个像素，化学键对应一条短线。训练集上准确率 92%，看起来一切顺利。但当模型部署到真实候选分子上时，准确率骤降到 47%——几乎和随机猜测没区别。

事后分析，原因并不复杂。苯环里的碳原子在图像上排列成六边形，但吡啶环（一个氮原子替换一个碳原子）画出来几乎一模一样。CNN 的卷积核只能捕捉局部像素模式，它不知道"环"是一个拓扑概念。它看见了像素点，却看不见"六个原子首尾相连"这个关系。这不是模型的错，而是数据表示（data representation）的根本错配。

这个故事揭示了一个被很多工程师忽视的事实：世界上大量数据天然就是图（graph）。但我们过去十年最成功的深度学习模型——CNN、RNN、Transformer——都建立在非常规则的欧几里得结构（Euclidean structure）之上。它们擅长处理网格（图像）和序列（文本），却在图这种"任意连接"的数据上水土不服。

核心问题（Core Questions）：

• 图数据到底有什么独特性，让它和图像、文本如此不同？
• 传统深度学习为什么在图上频频失效？
• 图神经网络（Graph Neural Network, GNN）究竟做了什么，能克服这些困难？

这一章会逐一回答这些问题。我们会从直觉出发，走进数学，最终亲手用 Python 写出第一张图。

---

1.2 图：一种通用语言

1.2.1 什么是图？超越表格与序列的"第三种数据"

在计算机科学里，图（graph） 是由节点（node / vertex）和边（edge）组成的数据结构，记作 $G = (V, E)$。$V$ 是节点集合，$E \subseteq V \times V$ 是边集合。如果边有方向，称为有向图（directed graph）；否则称为无向图（undirected graph）。如果边上还有权重，称为加权图（weighted graph）。如果节点和边还附带额外信息（原子类型、关系类型、时间戳），则得到属性图（attributed graph）。

公式上看似简单，但图之所以"通用"，在于它不强制规定节点之间怎么连。表格要求每一行是同一种记录，每一列有固定的字段；序列要求元素有明确先后；网格要求行列对齐。图只规定"谁和谁相连"——这恰恰是大自然和人类社会最基本的组织方式。

我们来看几个直观的例子：

1) 社交网络（Social Networks）：节点是人，边是好友关系。Facebook 的"好友"是无向的，Twitter 的"关注"是有向的。节点上还可以附加属性：年龄、兴趣、所在地。

2) 分子结构（Molecules）：节点是原子，边是化学键。原子有类型（碳、氮、氧…），键有类型（单键、双键、芳香键）。分子的"形状"完全由这张图决定——乙醇的 C-C-O 链和苯环的六元环就是不同的图。

3) 推荐系统（Recommender Systems）：在用户-商品二部图（user-item bipartite graph）里，用户和商品都是节点，"购买""点击""收藏"是边。预测"用户会不会买某商品"等价于预测图中一条边是否会出现。

4) 知识图谱（Knowledge Graphs）：节点是实体（人、地点、概念），边是关系（出生于、位于、属于）。Google Knowledge Graph、Freebase、ConceptNet 都是这种结构。边通常带类型标签，称为 RDF 三元组（subject, predicate, object）。

5) 交通与基础设施：道路网、电网、互联网拓扑、地铁线路——全都是图。节点是路口或设备，边是连接。亚马逊的物流优化、滴滴的派单算法都在这些图上运行。

6) 金融与风控：信用卡交易构成一张大图，节点是账户，边是转账。欺诈者常常形成异常子图（高密度、短暂的连接模式），GNN 可以自动识别这些模式。

下面用一张图把这六个领域串起来，看清 GNN 的"应用全景"：

```mermaid flowchart TD A[图数据 Graph Data] --> B[社交网络<br/>Social Networks] A --> C[分子与化学<br/>Molecules and Chemistry] A --> D[推荐系统<br/>Recommender Systems] A --> E[知识图谱<br/>Knowledge Graphs] A --> F[交通与基础设施<br/>Transportation & Infrastructure] A --> G[金融风控<br/>Financial Risk Control] B --> H[节点分类<br/>Node Classification] C --> I[分子性质预测<br/>Property Prediction] D --> J[链接预测 / 协同过滤<br/>Link Prediction] E --> K[实体对齐 / 关系抽取<br/>Entity Alignment] F --> L[路径规划 / 流量预测<br/>Path Planning] G --> M[欺诈检测 / 反洗钱<br/>Fraud Detection] ```

这个全景图说明了一件事：只要数据里存在"实体 + 关系"，就存在一张图；只要存在图，GNN 就有用武之地。

1.2.2 节点、边、邻接矩阵：图的三种视角

数学上描述图有三种等价方式，我们都会用到：

1) 集合表示（Set Representation）： $$G = (V, E)$$ 其中 $V = \{v_1, v_2, \dots, v_N\}$，$E = \{(v_i, v_j) \mid v_i, v_j \in V\}$。

2) 邻接矩阵（Adjacency Matrix）： $$\mathbf{A} \in \mathbb{R}^{N \times N}, \quad \mathbf{A}_{ij} = \begin{cases} 1, & \text{if } (v_i, v_j) \in E \\ 0, & \text{otherwise} \end{cases}$$ 对于加权图，$\mathbf{A}_{ij}$ 取权重；对于无向图，$\mathbf{A}$ 是对称的。

3) 邻接表（Adjacency List）： 每个节点维护一个列表，存放它的邻居。对于稀疏图，邻接表比邻接矩阵节省空间。

为什么这三种视角都重要？因为不同 GNN 实现会选择不同的"视角"。GCN（Graph Convolutional Network）用邻接矩阵做谱分解，GraphSAGE 用邻接表采样邻居，GAT（Graph Attention Network）则在边上做注意力计算。我们会在后续章节逐一展开。

1.2.3 节点的度、路径、子图：图的"局部信息"

理解图还需要一些基本量：

• **度（Degree）**：节点 $v_i$ 的邻居数，记作 $\deg(v_i) = \sum_j \mathbf{A}_{ij}$。在社交网络里，度就是"好友数"。
• **路径（Path）**：从 $v_i$ 到 $v_j$ 的一条边的序列。**最短路径长度** 称为距离 $d(v_i, v_j)$。
• **子图（Subgraph）**：由节点子集 $V' \subseteq V$ 和它们之间的边 $E'$ 组成的图。例如一个分子的官能团（functional group）就是子图。
• **连通分量（Connected Component）**：没有孤立节点的子图。判断一张图有几个"岛屿"就是找连通分量。
• **同构（Isomorphism）**：两张图 $G_1$ 和 $G_2$ 如果存在节点的双射保持边关系，则它们同构。判断同构是图论里著名的计算难题（至今没有已知的多项式时间算法）。

这些概念在 GNN 中会以各种形式出现。例如，GNN 的"消息传递"本质上是在路径上传播信息；GNN 学到的"图级表示"（graph-level embedding）是对整个子图特征的汇总。

---

1.3 欧几里得 vs 非欧几里得：CNN/RNN 为何失灵

1.3.1 什么是欧几里得结构

欧几里得数据（Euclidean data） 指的是可以嵌入到 $d$ 维欧几里得空间 $\mathbb{R}^d$ 中的数据。它有三大特征：

1. 规则的几何结构（Regular Geometric Structure）：图像是规则的网格（grid），每个像素有固定的 4 或 8 邻居。文本是规则的一维序列，每个 token 有左右邻居。 2. 固定的邻居数（Fixed Number of Neighbors）：图像里 3×3 卷积核只看 9 个邻居；文本里循环单元只看 1 个前驱。 3. 全局一致的坐标系（Global Consistent Coordinates）：图像的第 (10, 10) 像素在所有图像中都在大致相同的位置；文本的第 5 个词就在第 5 个槽位。

CNN、RNN、Transformer 都利用了这些性质。CNN 的卷积核利用平移不变性（translation invariance），在图像上滑动时参数共享；RNN 的隐藏状态利用时间步对齐，循环应用同一组权重；Transformer 的位置编码利用 token 的固定编号。

1.3.2 图的三大"反欧几里得"特征

图是非欧几里得数据（non-Euclidean data） 的代表。它有三大"反常"特征，直接挑战了传统深度学习的核心假设：

挑战 1：节点无序（Permutation Invariance）

图像有"第 3 行第 5 列"这种绝对位置；文本有"第 7 个字"这种顺序。但图没有自然的节点编号。一个 5 个人的社交网络，你可以给 5 个节点任意编号，它们代表的还是同一张图。

这意味着任何图上的函数 $f(G)$ 必须满足置换不变性（permutation invariance）： $$f(\mathbf{P} \mathbf{A} \mathbf{P}^\top) = f(\mathbf{A})$$ 其中 $\mathbf{P}$ 是任意置换矩阵（permutation matrix）。这听起来理所当然，但对深度学习来说却是个大麻烦——矩阵乘法天然依赖行/列的顺序。

举例：用全连接网络（MLP）处理邻接矩阵？如果输入节点顺序打乱，输出会完全不同。这不是 bug，而是 MLP 的本质：它把邻接矩阵当作"普通表格"，根本不识别图结构。

挑战 2：邻居数量可变（Variable Neighborhood Size）

图像里每个像素固定有 4 或 8 个邻居。但图中节点的度（degree）可以变化。一个社交网络里，普通用户可能只有 50 个好友，而明星有几千万。固定大小的卷积核在度数为 1 亿的节点上根本无法直接套用。

这迫使 GNN 必须设计自适应邻居数量的聚合方式。GraphSAGE 通过随机采样固定数量的邻居解决，GAT 通过注意力权重"软聚合"解决。

挑战 3：拓扑动态（Dynamic Topology）

图像一旦生成，拓扑就固定了。但图会随时间演化：社交网络里人会加好友、删好友；分子在反应中会断键成键；交易图里新交易不断发生。CNN/RNN 假设输入形状固定，但图的邻接矩阵大小和结构都在变化。

这要求 GNN 必须支持动态图（dynamic graph）——节点可以增删，边可以更新。TGN（Temporal Graph Network）和 EvolveGCN 等模型专门处理这种情况。

1.3.3 一个直观的对比实验

为了让差异更具体，我们来做一个思想实验。

场景：判断一个分子是否有毒。

方法 A：基于图像的 CNN： 1. 把分子画成 200×200 像素的 2D 图像。 2. ResNet 提取特征。 3. 二分类输出。

问题：苯和吡啶画出来几乎一样，但毒性不同（吡啶有氮原子，可能参与不同的代谢路径）。CNN 看见的是"像素"，看不见"原子之间的连接关系"。如果训练集里吡啶样本少，模型就完全分不清。

方法 B：基于 SMILES 字符串的 RNN/Transformer： 1. 把分子写成 SMILES 序列（例如 `c1ccccc1` 是苯，`c1ccncc1` 是吡啶）。 2. Transformer 编码。 3. 二分类输出。

问题：SMILES 字符串的"语法"和分子结构不是一一对应的。同一个分子可以写成多种 SMILES（`c1ccccc1` 和 `C1=CC=CC=C1` 是同一个苯），但 RNN 的 token 序列敏感。RNN 看到的"字符流"和"分子形状"之间隔了好几层抽象。

方法 C：基于图的 GNN（GCN / GAT）： 1. 把分子表示为图：原子是节点，化学键是边，原子/键类型是属性。 2. GNN 通过消息传递聚合每个原子邻居的信息。 3. 用图级池化（graph pooling）得到整张分子图表示。 4. 二分类输出。

优势：GNN 天然捕捉了"原子-键"关系，不会被 SMILES 的不同写法误导。它也能识别"环""官能团"等子结构模式——因为这些在图里就是子图。

这就是为什么 AlphaFold 之后的分子建模、几乎所有 SOTA 的药物筛选模型，都转向了 GNN。

---

1.4 GNN 的核心思想：邻居聚合与消息传递

1.4.1 直觉：你就是你朋友的"加权平均"

GNN 的核心思想朴素得令人惊讶：每个节点的表示（embedding），由它的邻居和它自己共同决定。用一句话概括：

> "Tell me who your friends are, and I'll tell you who you are." >（告诉我你的朋友是谁，我就知道你是谁。）

形式上，对于节点 $v$，经过一次 GNN 层后： $$\mathbf{h}_v^{(l+1)} = \text{UPDATE}\left(\mathbf{h}_v^{(l)}, \text{AGGREGATE}\left(\{\mathbf{h}_u^{(l)} \mid u \in \mathcal{N}(v)\}\right)\right)$$

其中：

• $\mathbf{h}_v^{(l)} \in \mathbb{R}^d$ 是节点 $v$ 在第 $l$ 层的表示。
• $\mathcal{N}(v)$ 是 $v$ 的邻居集合。
• $\text{AGGREGATE}$ 是一个**置换不变函数**（permutation-invariant function），例如求和（sum）、平均（mean）、最大值（max）。
• $\text{UPDATE}$ 通常是一个小型神经网络（MLP）。

这个公式叫做消息传递神经网络（Message Passing Neural Network, MPNN） 的通用框架，由 Gilmer et al. 在 2017 年提出。它统一了 GCN、GAT、GraphSAGE 等多种 GNN 模型。

1.4.2 一个具体例子：空手道俱乐部

让我们用著名的 Zachary's Karate Club 数据集来直观理解 GNN 在做什么。

背景：1970 年代，社会学家 Zachary 观察了一个美国大学空手道俱乐部 34 名成员，记录了他们的友谊关系。由于内部纠纷，俱乐部后来分裂成两个派系。问题是：根据友谊图，能不能预测每个成员加入哪个派系？

步骤 1：建图。 节点 = 34 个成员，边 = 成员之间的友谊。共 78 条边。节点度从 1 到 17 不等。

步骤 2：初始化。 每个节点 $v$ 有一个初始表示 $\mathbf{h}_v^{(0)}$。最简单的做法是用 one-hot 编码或随机向量。

步骤 3：第一层聚合。 对于每个节点 $v$，把它自己和它的所有邻居的特征"混合"在一起。公式化： $$\mathbf{h}_v^{(1)} = \sigma\left(\mathbf{W} \cdot \text{MEAN}\left(\{\mathbf{h}_u^{(0)} \mid u \in \{v\} \cup \mathcal{N}(v)\}\right)\right)$$

直觉：经过这一层，每个节点都"知道"了它的直接好友是谁。

步骤 4：多层叠加。 再叠加一层，节点就"知道"了好友的好友是谁——即 2 跳邻居（2-hop neighbors）。层数 $L$ 决定了 GNN 的"感受野"（receptive field）：$L$ 层后，每个节点的表示整合了 $L$ 跳邻居的信息。

步骤 5：分类。 用最终的 $\mathbf{h}_v^{(L)}$ 喂入一个 softmax 分类器，预测每个成员加入哪个派系。

结果：一个简单的 2 层 GCN 就能达到 90% 以上的准确率。空手道俱乐部问题是图机器学习的"Hello World"。

1.4.3 为什么"聚合"是关键

聚合函数的设计直接决定了 GNN 的能力。常见的选择有：

1) 求和聚合（Sum Aggregation）： $$\text{AGGREGATE} = \sum_{u \in \mathcal{N}(v)} \mathbf{h}_u$$ 优点：保留邻居的数量信息。缺点：度大的节点表示的"幅度"会很大，需要归一化。

2) 平均聚合（Mean Aggregation）： $$\text{AGGREGATE} = \frac{1}{|\mathcal{N}(v)|} \sum_{u \in \mathcal{N}(v)} \mathbf{h}_u$$ 优点：度归一化，数值稳定。缺点：丢失"度"信息（5 个弱连接 vs 1 个强连接，聚合后可能一样）。

**3) 最大值