绪论：为何图是智能的天然载体 / Introduction: Why Graphs are Natural Carriers of Intelligence
智能，作为一种复杂的信息处理能力，其载体形式多样。在现实世界中，图结构无处不在：社交网络中人与人之间的关联、分子中原子与化学键的排列、知识图谱中实体与关系的交织、交通网络中城市与路径的连接——这些看似 disparate 的现象，共享着一种深刻的数学抽象：图。图以节点（nodes/vertices）和边（edges）的形式，天然地编码了实体及其关系，而这正是许多智能任务的核心：理解关系、推理因果、预测互动。传统神经网络，如卷积神经网络（CNN）和循环神经网络（RNN），在图像、语音、文本等欧几里得数据（Euclidean data）上取得了巨大成功，但它们依赖于规则的网格结构或序列顺序，难以直接处理图这种非欧几里得（non-Euclidean）数据。图神经网络（Graph Neural Networks, GNNs）应运而生，它通过消息传递（message passing）机制，让节点能够聚合邻居信息，从而学习到富含结构上下文的表示。本章将阐述图为何是智能的天然载体，对比传统神经网络与图神经网络的差异，并勾勒出本书的学习路径与核心价值，为后续深入技术细节奠定基础。
图结构：现实世界的骨架
图并非仅仅是数学家的玩具，而是宇宙的基本语言。从微观的粒子相互作用到宏观的星系分布，从生物体内的代谢通路到全球的经济贸易网络，图结构提供了描述复杂系统的高效框架。其普遍性源于一个简单事实：现实世界由实体及其关系构成。实体是节点，关系是有向或无向的边，边的权重可以表示强度、距离或概率。这种表达方式灵活且富有表现力，能够捕捉传统表格数据（如Excel）无法呈现的拓扑信息。
社交网络：人类关系的数字镜像
社交网络是最直观的图实例。以 Facebook 为例，其超过 30 亿月活跃用户构成一个庞大的图：每个用户是一个节点，好友关系是边。这个图不仅是社交图谱，更是信息传播、影响力扩散、社区形成的载体。研究显示，社交图中的“弱连接”（weak ties）往往是创新想法传播的关键路径，而“三度影响力原则”（three-degree influence rule）表明，一个人的情绪、行为甚至消费决策可以影响到其朋友的朋友的朋友。这种关系驱动的动态，使得基于图的分析成为理解社会行为的利器。
实践案例：好友推荐与社区检测 在好友推荐系统中，图算法（如共同邻居、Jaccard 相似度）可以计算节点间的接近度，而 GNN 能进一步学习用户和关系的嵌入表示，捕捉高阶关系。例如，PinSage（Pinterest 的图卷积系统）将用户-物品交互图与物品内容图结合，通过随机游走生成多跳邻居，使用图卷积聚合信息，实现了 30% 以上的推荐质量提升。社区检测（community detection）则试图发现图中紧密连接的子图，如使用模块度（modularity）优化或基于 GNN 的聚类方法，帮助平台识别兴趣群体，实现精准内容分发。
分子结构：化学与药物的图表示
在化学与药物发现领域，分子天然地表示为图：原子是节点，化学键是边。每个原子带有类型（碳、氧、氮等）和隐含属性（电负性、价态），边带有类型（单键、双键、三键、芳香键）和几何信息。这种图结构编码了分子的拓扑和电子特性，直接决定其物理化学性质（如溶解度、毒性）和生物活性（如与靶点蛋白的结合能力）。传统方法依赖手工特征（如分子指纹），而 GNN 能够自动从图结构中学习特征，端到端地预测分子性质，极大加速了药物筛选过程。
实践案例：分子性质预测与药物发现 ZINC 数据库包含数百万个购买可得分子的图结构，常用于基准测试。一个典型的 GNN 任务是根据分子图预测其 logP（辛醇-水分配系数，衡量疏水性）或 QM9 数据集中的量子力学性质（如 HOMO-LUMO 能隙）。使用消息传递神经网络（MPNN），每一轮迭代中，原子节点通过边接收邻居原子的消息，更新自身状态。经过若干层后，通过读出函数（readout function）聚合所有原子状态得到分子级预测。实验表明，经过适当设计的 GNN 可以达到与密度泛函理论（DFT）计算相当的精度，但速度快几个数量级。在工业界，GNN 已被用于生成新分子结构（图生成模型），例如在 COVID-19 药物重定位中，通过分析病毒-宿主蛋白交互图，快速筛选现有药物的潜在疗效。
知识图谱：结构化知识的网络
知识图谱（Knowledge Graph, KG）是实体及其关系的结构化表示，例如 Google 知识图谱包含数十亿实体（人物、地点、事物）和数万亿事实（如“出生于”、“导演了”）。知识图谱的典型表示是 RDF 三元组（头实体、关系、尾实体），这可以自然地看作是一个有向多重图：实体为节点，关系为带标签的边。知识图谱支持复杂的查询（如“爱因斯坦的学生的导师是谁？”）和推理（如通过关系路径推断新事实），是搜索引擎、推荐系统和问答系统的核心基础设施。
实践案例：知识图谱补全与问答 知识图谱往往不完整，知识图谱补全（Knowledge Graph Completion）旨在预测缺失的链接。传统方法如 TransE 将实体和关系嵌入到向量空间，满足 $h + r \approx t$（头实体向量 + 关系向量 ≈ 尾实体向量）。而 GNN 方法（如 R-GCN）在图结构上传播信息，考虑实体邻居的多样性关系，能更准确地编码上下文。例如，在 Freebase 数据集上，R-GCN 通过关系特定的图卷积，在链接预测任务上显著优于 TransE。对于知识图谱问答（KGQA），GNN 可以联合编码问题文本和子图，通过图上的推理路径找到答案，如将问题“《星际穿越》的导演是谁？”映射到从“星际穿越”节点通过“导演”关系到“克里斯托弗·诺兰”节点的路径。
其他领域：交通、推荐与科学
- **交通网络**：城市道路网是典型的图，交叉口为节点，道路为边。GNN 用于预测交通流量、估计旅行时间、优化信号灯控制。例如，DCRNN（扩散卷积递归神经网络）将交通流建模为图上的扩散过程，结合循环神经网络捕捉时间动态，在多个城市数据集上实现了 state-of-the-art 的预测精度。
- **推荐系统**：除了社交推荐，用户-物品交互本身可构成二部图（bipartite graph）。GNN 如 LightGCN 简化图卷积，仅在用户和物品节点上传播，在协同过滤任务中展现出强大性能，Netflix 等公司已探索将 GNN 用于个性化推荐。
- **科学发现**：在物理学中，粒子相互作用可表示为图；在神经科学，大脑功能连接图用于分析认知任务；在材料科学，晶体结构可视为周期性图，GNN 用于预测材料性质（如带隙、稳定性），加速新材料设计。
这些例子共同说明：当数据的内在结构是关系性的，图就是最自然、最信息丰富的表示形式。而智能，本质上是对这种关系结构的感知、学习和推理。
为何图是智能的天然载体
智能的核心能力之一是处理关系信息。人类认知心理学家认为，关系推理（relational reasoning）是高级智能的基石：我们理解“如果 A 在 B 的左边，且 B 在 C 的左边，那么 A 在 C 的左边”；我们学习类比“手之于人，如同鳍之于鱼”；我们构建知识网络，将概念联系起来。图结构直接对应于这种关系思维：节点代表概念或实体，边代表它们之间的关联。因此，图不仅是数据表示，更是认知的模型。
从计算角度看，图提供了几个关键优势： 1. 关系显式化：图将隐性的关系显式编码为边，使模型能够直接访问和操作关系信息，而非从原始数据中隐式学习。 2. 结构灵活性：图不要求节点顺序固定、度数一致或空间规则。社交图中有人缘极广的“网红”，也有仅有几个好友的普通人；分子图中原子连接千变万化。这种灵活性匹配了现实世界的多样性。 3. 组合 generality：图结构支持组合性（compositionality）：复杂系统由简单组件（节点）通过关系（边）组装而成。学习到的节点表示和聚合函数可以泛化到未见过的图结构，这是符号系统与学习系统结合的理想形式。 4. 动态适应性：图可以自然表示动态系统：节点和边随时间添加、删除或变化。例如，社交网络中新朋友连接、分子反应中键的断裂与形成。GNN 可以通过时间图神经网络（TGNN）建模这种演化。
反观传统机器学习方法：向量表示（如 Word2Vec）将实体映射为固定向量，但丢失了结构化关系；矩阵分解（如协同过滤）假设用户-物品交互是低秩的，但难以融入side信息（如用户属性、物品内容）。图嵌入（Graph Embedding）方法（如 DeepWalk、Node2Vec）通过随机游走生成节点序列，再应用 Word2Vec，虽然简单有效，但仅捕获结构相似性，无法端到端优化下游任务。GNN 则提供了统一的框架，将节点特征、边特征、全局图属性整合到一个可微分模型中，直接针对预测目标进行优化。
因此，图作为智能的载体，不仅因其普遍性，更因其关系本质与计算适配性。当我们要解决涉及关联、网络、结构的问题时，图神经网络便成为自然的选择。
传统神经网络的局限：欧几里得数据的霸权
要理解 GNN 的必要性，必须审视传统神经网络的成功与边界。过去十年，深度学习革命主要由两种架构驱动：卷积神经网络（CNN）处理图像等网格数据，循环神经网络（RNN）及其变体（LSTM、GRU）处理序列数据（文本、语音）。它们的成功建立在两个关键假设上：
- **平移不变性（Translation Invariance）**：CNN 的卷积核在输入空间滑动，共享权重，意味着特征检测器不依赖于位置。这适用于图像，其中猫的耳朵无论在左上角还是右下角都应被同样识别。
- **顺序性（Sequential Order）**：RNN 按时间步处理序列，隐藏状态传递历史信息，适用于文本，其中单词顺序决定语义。
然而，许多现实数据不满足这些假设。社交网络中的用户没有自然顺序；分子中的原子连接不规则；知识图谱中的关系类型多样且无固定拓扑。试图将这些数据“强行”塞入网格或序列框架，往往需要代价高昂且信息丢失的预处理：
- 将图转换为序列（如深度优先遍历）会破坏结构信息，且节点顺序任意导致模型需要学习置换不变性（permutation invariance），这本身是困难的。
- 将图投影到网格（如将分子表示为图像）会丢失精确的键信息，且图的大小可变，难以统一输入尺寸。
- 使用邻接矩阵作为输入，虽然直接，但矩阵大小随节点数变化，且传统全连接层不利用图的稀疏性，计算和参数效率低下。
更根本地，传统神经网络的设计隐含了欧几里得空间假设：数据点位于规则网格（如图像像素）或一维流形（如时间序列）上，距离和邻域有明确定义。而图数据位于非欧几里得空间，节点间距离由最短路径定义，邻域由边连接定义，且图可能具有复杂的拓扑（如小世界、无标度特性）。在这种空间上，卷积、池化等操作需要重新定义。GNN 正是为了在非欧几里得域上进行深度学习而诞生的。
图神经网络：消息传递的统一视角
图神经网络的核心思想是消息传递（Message Passing），也称为邻域聚合（neighborhood aggregation）。其基本流程可概括为：每个节点收集其邻居节点的信息，聚合后与自身状态结合，更新表示。经过多层传播，节点最终编码了多跳邻居的上下文，使得远距离节点也能相互影响。
消息传递的数学形式化
设图 $G = (\mathcal{V}, \mathcal{E})$，其中 $\mathcal{V}$ 为节点集，$|\mathcal{V}|=N$；$\mathcal{E}$ 为边集。每个节点 $v \in \mathcal{V}$ 有特征向量 $\mathbf{x}_v$。GNN 的目标是学习一个函数，输出节点级表示 $\mathbf{h}_v$、边级表示或图级表示。
最一般的消息传递框架（Gilmer et al., 2017）定义为： $$ \mathbf{m}_v^{(k+1)} = \sum_{u \in \mathcal{N}(v)} \text{MSG}^{(k)}(\mathbf{h}_u^{(k)}, \mathbf{h}_v^{(k)}, \mathbf{e}_{uv}) $$ $$ \mathbf{h}_v^{(k+1)} = \text{UPDATE}^{(k)}(\mathbf{h}_v^{(k)}, \mathbf{m}_v^{(k+1)}) $$ 其中：
- $\mathcal{N}(v)$ 是 $v$ 的邻居集合（可能包括 $v$ 自身）。
- $\text{MSG}^{(k)}$ 是第 $k$ 层的消息函数，通常为神经网络，输入源节点状态、目标节点状态和边特征 $\mathbf{e}_{uv}$，输出消息。
- $\mathbf{m}_v^{(k+1)}$ 是聚合后的消息，通常对邻居的消息求和（或均值、最大值等）。
- $\text{UPDATE}^{(k)}$ 是更新函数，结合节点旧状态和聚合消息，输出新状态 $\mathbf{h}_v^{(k+1)}$。
经过 $K$ 层后，节点 $v$ 的表示 $\mathbf{h}_v^{(K)}$ 捕获了其 $K$-跳邻居的信息。$K$ 通常较小（2-5），因为图直径可能很大，且过深层数会导致过平滑（over-smoothing）问题。
经典架构：GCN、GAT、GraphSAGE
上述通用框架催生了多种具体架构：
- **图卷积网络（GCN）**：Kipf & Welling (2017) 提出简化版，假设消息函数为线性变换，聚合为邻居的均值（归一化邻接矩阵），更新为非线性激活。一阶近似下，层传播公式为：
$$ \mathbf{H}^{(k+1)} = \sigma\left(\tilde{\mathbf{D}}^{-\frac{1}{2}}\tilde{\mathbf{A}}\tilde{\mathbf{D}}^{-\frac{1}{2}}\mathbf{H}^{(k)}\mathbf{W}^{(k)}\right) $$ 其中 $\tilde{\mathbf{A}} = \mathbf{A} + \mathbf{I}$ 为添加自环的邻接矩阵，$\tilde{\mathbf{D}}$ 为度矩阵，$\mathbf{H}^{(k)}$ 为节点表示矩阵，$\mathbf{W}^{(k)}$ 为可训练权重，$\sigma$ 为激活函数（如 ReLU）。GCN 高效且易于实现，但聚合方式固定（对称归一化），且依赖于全图邻接矩阵，不利于大规模图。
- **图注意力网络（GAT）**：Veličković et al. (2018) 引入注意力机制，使节点能够为不同邻居分配不同权重。消息函数计算注意力系数：
$$ \alpha_{uv} = \frac{\exp\left(\text{LeakyReLU}\left(\mathbf{a}^\top [\mathbf{W}\mathbf{h}_u^{(k)} \| \mathbf{W}\mathbf{h}_v^{(k)}]\right)\right)}{\sum_{w \in \mathcal{N}(v)} \exp\left(\text{LeakyReLU}\left(\mathbf{a}^\top [\mathbf{W}\mathbf{h}_w^{(k)} \| \mathbf{W}\mathbf{h}_v^{(k)}]\right)\right)} $$ 其中 $\mathbf{a}$ 为可学习注意力向量，$\|$ 表示拼接。然后聚合加权和：$\mathbf{m}_v = \sum_{u \in \mathcal{N}(v)} \alpha_{uv} \mathbf{W}\mathbf{h}_u$。GAT 允许模型关注重要邻居，尤其适用于异质图。
- **GraphSAGE**：Hamilton et al. (2017) 提出归纳式（inductive）学习，能够泛化到未见节点。它定义了多种聚合函数：均值聚合、LSTM 聚合、池化聚合。训练时，对每个节点采样固定数量的邻居，递归地聚合多跳信息。这使得模型可以处理动态变化的大图，如为数十亿用户生成嵌入。
消息传递的视角统一
从消息传递视角，GCN、GAT、GraphSAGE 的区别仅在于 $\text{MSG}$、聚合函数和 $\text{UPDATE}$ 的具体设计。这种统一性揭示了 GNN 的本质：通过迭代的邻居信息交换，使节点表示收敛到一种“平衡状态”，其中每个节点都知晓其局部结构上下文。这类似于物理学中的扩散过程或社会学中的谣言传播，最终每个节点都“听说”了周围发生的事。
传统神经网络与图神经网络的对比
下表从多个维度对比了 CNN、RNN 和 GNN，突显了 GNN 在处理图数据上的独特优势：
| 维度 | CNN | RNN/LSTM | GNN | |------|-----|----------|-----| | 输入数据结构 | 规则网格（如图像像素矩阵） | 序列（如单词列表、时间步） | 图（节点和边任意连接） | | 关键归纳偏置 | 平移不变性、局部性 | 时间顺序、长期依赖 | 置换不变性、关系结构 | | 核心操作 | 卷积（局部加权和）+ 池化（下采样） | 递归非线性变换（隐藏状态传递） | 消息传递（邻居聚合）+ 更新 | | 参数共享 | 卷积核在空间共享 | 循环权重在时间步共享 | 消息/更新函数在节点间共享 | | 输出灵活性 | 网格级（语义分割）、图像级（分类） | 序列级（情感分析）、时间点级（命名实体识别） | 节点级（分类）、边级（链接预测）、图级（性质预测） | | 计算复杂度 | $O(N)$（线性于像素数） | $O(T)$（线性于序列长度） | $O(|\mathcal{E}|)$ 每层（线性于边数，通常稀疏） | | 典型应用 | 计算机视觉、医学影像 | 自然语言处理、语音识别 | 社交网络分析、分子建模、推荐系统 | | 处理图数据的适配性 | 需将图转为规则图像（如邻接矩阵图像），丢失结构 | 需将图线性化（如DFS序列），顺序任意性导致训练不稳定 | 原生支持，直接利用图拓扑 |
关键洞察：GNN 的核心归纳偏置是置换不变性（permutation invariance）——节点的预测不应依赖于节点在输入中的顺序。这通过对称聚合函数（如求和、均值）实现。同时，GNN 通常具有置换等变性（permutation equivariance）——如果输入节点顺序改变，输出表示按相同方式重新排列。这些性质使 GNN 天然适合处理集合和关系数据。