绪论：图数据与智能计算的新范式

在我们生活的数字世界中，一种古老而强大的数据结构——图，正在以前所未有的方式驱动着智能计算的变革。从社交网络中人与人之间错综复杂的关系，到分子结构中原子间的化学键；从互联网上网页之间的超链接，到知识库中实体间的语义关联；从交通网络中站点与路线的连接，到大脑神经元之间的突触连接——图结构数据无处不在，构成了我们理解复杂系统关系本质的核心语言。然而，传统的机器学习方法，尤其是深度学习中大放异彩的卷积神经网络（CNN）和循环神经网络（RNN），其设计初衷都建立在欧氏空间数据（如图像的像素网格、文本的序列）的假设之上。当面对图这种非欧氏、不规则、具有复杂拓扑结构的数据时，这些经典方法便显得力不从心：如何在一个节点数量可变、连接关系无固定顺序的图上进行有效的特征学习？如何让模型同时捕捉节点的自身属性与它们之间的拓扑依赖？如何设计一种能够泛化到不同规模、不同结构的图数据的计算范式？

正是这些挑战催生了图神经网络（Graph Neural Networks, GNNs） 的蓬勃发展。图神经网络是一类专门用于处理图结构数据的深度学习模型，其核心目标是为图中的节点、边乃至整个图学习到有意义的、低维的向量表示（Embedding），这些表示能够编码结构信息与属性信息，从而服务于下游任务，如节点分类、链接预测、图分类等。自21世纪初的概念萌芽，到2013年图卷积网络（GCN）的提出标志着现代GNN研究的复兴，再到如今图注意力网络（GAT）、图同构网络（GIN）、图生成模型等分支的百花齐放，GNN已经成长为一个内涵丰富、应用广泛的研究领域，并持续推动着人工智能在化学、生物、社交网络、推荐系统、自然语言处理乃至程序分析等领域的范式革新。

本章作为全书的总纲，旨在为读者构建一个关于图数据与图神经网络的宏观认知框架。我们将首先深入探讨图结构数据在现实世界中的普遍性与重要性，系统性地分析传统机器学习在处理图数据时面临的根本性挑战。在此基础上，我们将正式界定图神经网络的研究范畴，阐明其“学习图表示”的核心目标，并梳理其从诞生到繁荣的关键发展脉络与里程碑工作。随后，本章将概览GNN的主要研究分支，包括基于空间与基于谱的图卷积、引入注意力机制的图注意力网络、以及新兴的图生成与图Transformer等模型，帮助读者理解这个领域的核心技术版图。最后，我们将通过一系列生动具体的应用实例，展示GNN如何解决真实世界的复杂问题，并介绍本书的完整章节结构与学习路径，为读者的深度学习之旅提供清晰的导航。

---

一、图数据：现实世界的拓扑语言

1.1 什么是图？一个普适的抽象模型

从数学和计算机科学的角度看，图（Graph） 是一种由顶点（Vertex/Node） 集合和连接顶点的边（Edge） 集合组成的数据结构，通常形式化定义为 $G = (V, E)$，其中 $V$ 是节点集合，$E \subseteq V \times V$ 是边集合。这一定义极其简洁，却具有惊人的表达能力和普适性。其核心威力在于能够用统一的方式刻画实体（Entities） 与它们之间的关系（Relations）。一个节点可以代表任何实体：一个人、一个分子、一个单词、一个网页、一个传感器；一条边可以代表任何关系：朋友关系、化学键、语法依赖、超链接、物理连接。正是这种“实体-关系”的抽象，使得图成为描述复杂系统内在关联的天然语言。

为了更精确地描述现实，图模型可以引入多种属性：

• **有向与无向**：边是否有方向，如社交网络的“关注”关系是有向的，而“好友”关系通常是无向的。
• **加权与无权**：边是否带有权重，表示关系的强度、距离或容量，如交通网络中道路的通行时间、社交网络中互动的频率。
• **同构图与异构图**：图中节点类型是否唯一（同构），或存在多种类型的节点和边（异构），如学术知识图谱中包含论文、作者、会议、关键词等多种实体和“撰写”、“发表”、“属于”等多种关系。
• **静态图与时态图**：图结构本身是否随时间动态变化，如社交网络中新好友的添加、分子在化学反应中的键的断裂与形成。

1.2 无处不在的图：来自各领域的实例

图结构数据的普遍性远超一般认知，它构成了众多科学与工程领域数据的底层骨架。

社交网络是最直观的图实例。以Facebook或Twitter为例，用户是节点，好友关系或关注关系是有向边。研究社交网络涉及社区发现（识别紧密连接的群体）、影响力最大化（找到关键传播者）、链接预测（预测未来可能建立的关系）等核心问题。这些问题的解决，离不开对图拓扑结构和用户属性的联合建模。

分子结构与化学是图模型应用的经典领域。在计算化学与药物发现中，一个分子可以自然地表示为一张图：原子是节点，化学键是边。节点特征包括原子类型（碳、氧、氮等）、电负性、成键能力等；边特征包括键的类型（单键、双键、芳香键等）、键长等。预测分子的性质（如毒性、溶解度、生物活性）或进行虚拟筛选，本质上是学习一种从分子图到目标属性的映射函数。图神经网络通过直接操作分子图，能够捕捉到决定化学性质的关键局部结构模式（如官能团）和全局拓扑。

知识图谱是人工智能实现常识推理和可解释决策的关键基础设施。Google的知识图谱、企业级的知识库（如阿里云的知识图谱）都是典型的异构图。节点是实体（如“阿尔伯特·爱因斯坦”、“相对论”），边是关系（如“职业是”、“提出”）。知识图谱的补全（预测缺失的头实体、尾实体或关系）、问答系统（从自然语言问题到知识图谱子图的查询）、实体对齐（跨知识图谱的实体匹配）等任务，都依赖于对实体和关系进行高质量的分布式表示学习，而GNN正是实现这一目标的核心工具。

推荐系统长期面临“用户-物品”交互数据的稀疏性与冷启动问题。现代推荐系统早已超越简单的协同过滤，将用户、物品、上下文（时间、地点）以及丰富的辅助信息（物品的描述、类别，用户的画像、社交关系）全部纳入一个庞大的异构图中。例如，用户A购买了物品B，这形成一条边；物品B属于类别C，又形成一条边；用户A关注了用户D，也形成一条边。通过GNN在这个异构图上的信息传播，可以为用户和物品生成融合了多源异构信息的嵌入表示，从而显著提升推荐的准确性和多样性。

交通与城市规划中，道路网络、公共交通系统、城市设施分布都是图。节点是路口、车站、POI（兴趣点），边是道路、线路。预测交通流量、估计行程时间、优化公交线路、识别城市功能分区，都需要对图结构进行建模。例如，结合路网拓扑、POI分布和历史流量数据，GNN可以更精准地预测某个路口在未来时刻的拥堵情况。

自然语言处理（NLP） 中的句法分析树、语义依存图都是图结构。虽然文本序列本身是一维的，但词语间的语法依赖关系构成了树或图。利用GNN在依存图上操作，可以更好地捕捉长距离依赖和短语结构，提升机器翻译、情感分析、信息抽取等任务的性能。此外，文档级别的图，如基于实体共现构建的文档图，也被用于文档分类和摘要。

程序分析与代码理解是GNN一个新兴且极具价值的应用领域。源代码可以被抽象为抽象语法树（AST，一种树状图）、控制流图（CFG）、数据流图（DFG）或多种图的组合。节点代表变量、语句、函数，边代表语法、控制或数据依赖。利用GNN学习代码图的表示，可以用于代码缺陷检测、代码相似度计算、函数推荐、程序翻译等，对提升软件开发自动化水平具有重要意义。

生物信息学与药物发现中，蛋白质结构（原子图）、蛋白质-蛋白质相互作用网络、基因调控网络等都是核心研究对象。利用GNN预测蛋白质功能、识别药物靶点、分析基因突变影响，正在成为计算生物学的前沿方向。

1.3 传统机器学习的“图困境”

在GNN出现之前，处理图数据的主流方法依赖于各种启发式特征工程或试图将图“压平”以适应传统模型，但这些方法都存在根本性的局限。

1.3.1 基于特征工程的方法 早期方法首先为每个节点或整个图手工设计一组特征（如节点的度、聚类系数、PageRank值；图的节点数、边数、直径等），然后将这些特征输入到传统的机器学习模型（如支持向量机、随机森林、梯度提升树）中进行训练。这种方法严重依赖于领域专家的先验知识，特征设计的好坏直接决定模型上限。更重要的是，这些手工特征往往只能捕捉图的一些浅层、全局统计属性，而无法有效编码图中丰富的、多尺度的局部拓扑结构信息。例如，两个节点可能具有相同的度，但它们在图中的角色可能天差地别（一个是枢纽，一个是叶子节点），手工特征难以区分。

1.3.2 基于核函数的方法 图核（Graph Kernels）试图通过定义一个衡量两个图相似度的核函数，将图映射到希尔伯特空间，从而在保留图结构信息的前提下，使支持向量机等核方法能够处理图数据。经典的图核如随机游走核、最短路径核、图let核等。然而，图核的计算复杂度通常很高（尤其是对于大规模图），且其设计本身也蕴含了特定的结构假设，缺乏学习的灵活性，无法根据具体任务自动调整对结构的敏感度。

1.3.3 “压平”与序列化方法 一种直观的想法是将图数据转换成序列或网格形式，以便使用RNN或CNN。

• **基于序列的方法**：如将图视为一系列节点遍历序列（如深度优先搜索序列），然后用RNN处理。但节点的顺序是任意的，不同的遍历顺序会产生不同的序列，导致模型对输入顺序敏感，且难以有效聚合来自不同邻居的信息。
• **基于网格的方法**：尝试将图“铺”到一个规则的网格上（如将图嵌入到二维空间），然后用CNN处理。这种方法对于稀疏、不规则的图几乎不可行，会引入大量噪声和虚假连接，严重扭曲原始拓扑。
• **基于树的方法**：将图分解为树结构（如生成树），然后用树神经网络处理。这丢失了图中大量的环状结构和跨分支依赖。

1.3.4 核心挑战总结 传统方法面临的共同困境可以归结为以下几点： 1. 置换不变性（Permutation Invariance）：图的节点没有天然的顺序。一个有效的图学习模型，其输出（如节点嵌入）不应随节点标签的随机重排而改变。传统模型（如全连接层、RNN）的输入顺序敏感性与这一要求相悖。 2. 变量尺寸与不规则性：图的大小（节点数）可变，每个节点的邻居数量也各不相同。CNN的固定卷积核和RNN的固定时间步难以直接处理这种动态结构。 3. 信息聚合的复杂性：要学习一个节点的表示，需要聚合其邻居的信息。但邻居的集合本身也是一个无序、可变大小的集合。如何设计一个参数共享的、对邻居集合置换不变的聚合函数，是核心难题。 4. 结构信息的深度利用：不仅需要直接邻居的信息，往往还需要多跳（multi-hop）邻居的信息来捕获更广泛的图上下文。如何有效地、渐进式地传播和聚合信息，是设计深层图模型的关键。

这些挑战表明，我们需要一种全新的、原生为图结构设计的神经网络架构，它能够自然地处理置换不变性、变量尺寸和复杂聚合，这正是图神经网络所追求的。

---

二、图神经网络：定义、核心目标与发展简史

2.1 图神经网络的定义与核心目标

图神经网络（GNN） 是一个模型家族的总称，其共同特点是直接在图上定义神经网络层，通过消息传递（Message Passing）或聚合（Aggregation）机制，迭代地更新节点、边或整个图的表示。

一个GNN模型通常遵循一个递归 neighborhood aggregation（邻域聚合） 或 message passing（消息传递） 的范式。其核心思想是：每个节点的表示，是其自身特征与其邻居节点表示的某种组合。通过堆叠多个这样的层，一个节点的最终表示可以捕获其多跳邻居的信息，从而融入图的全局结构上下文。

更形式化地，一个典型的GNN层可以描述为： 1. 消息函数（Message Function） $m_{uv}^{(l)} = \text{MSG}^{(l)}(h_u^{(l-1)}, h_v^{(l-1)}, e_{uv})$：对于每条边 $(u, v)$，计算从源节点 $u$ 传递到目标节点 $v$ 的“消息”。消息可以依赖于源节点特征 $h_u$、目标节点特征 $h_v$ 以及边特征 $e_{uv}$。 2. 聚合函数（Aggregation Function） $M_v^{(l)} = \text{AGG}^{(l)}(\{ m_{uv}^{(l)} | u \in \mathcal{N}(v) \})$：对于目标节点 $v$，将所有来自其邻居 $u \in \mathcal{N}(v)$ 的消息聚合成一个集合表示 $M_v$。聚合函数必须对输入集合的顺序不变，常用操作有求和（Sum）、均值（Mean）、最大值（Max）等。 3. 更新函数（Update Function） $h_v^{(l)} = \text{UPD}^{(l)}(h_v^{(l-1)}, M_v^{(l)})$：结合节点自身的上一轮表示 $h_v^{(l-1)}$ 和聚合后的邻居信息 $M_v^{(l)}$，生成节点 $v$ 在第 $l$ 层的新表示 $h_v^{(l)}$。

经过 $L$ 层传播后，每个节点 $v$ 的最终表示 $h_v^{(L)}$ 理论上编码了以 $v$ 为中心的 $L$ 跳子图的结构与特征信息。这些节点表示随后可以用于各种下游任务：

• **节点级任务**：如节点分类（预测节点类别）、节点回归（预测节点属性），直接使用 $h_v^{(L)}$。
• **边级任务**：如链接预测（预测边是否存在），通常将两个端点的表示拼接后通过一个分类器。
• **图级任务**：如图分类（预测整个图的类别）、图回归，需要对所有节点的表示进行全局池化（Global Pooling，如Sum、Mean、Max），得到一个图表示 $h_G$。

因此，图神经网络的核心目标可以精确定义为：设计可学习的参数化函数（消息、聚合、更新函数），使得模型能够为图中的节点、边或整个图生成低维、稠密、信息丰富的向量表示，这些表示能够有效捕获图的结构拓扑与节点/边属性，并最大化地对下游任务有用。

2.2 发展简史：从萌芽到繁荣

GNN的思想源头可以追溯到21世纪初，其发展历程大致可分为几个阶段：

萌芽期（2005-2013）：2005年，M. Gori等人提出了图神经网络（Graph Neural Networks, GNN） 的原始概念，使用递归神经网络在图上传播状态，直到收敛。2009年，F. Scarselli等人发表了具有里程碑意义的论文《Graph Neural Networks》，正式确立了该领域的基本框架，提出了基于图结构的递归状态更新方程。这一时期的工作奠定了“在图上迭代更新节点表示”的核心思想，但受限于计算资源和数据，并未引起广泛关注。

复兴与奠基期（2013-2017）：2013年，J. Bruna等人将卷积神经网络的思想引入图结构，提出了谱图卷积（Spectral Graph Convolution），利用图的拉普拉斯矩阵的特征分解来定义卷积操作。2016年，Kipf与Welling在其经典论文《Semi-Supervised Classification with Graph Convolutional Networks》中，提出了图卷积网络（Graph Convolutional Networks, GCN）。GCN对谱方法进行了关键简化，将卷积操作近似为邻接矩阵与节点特征的简单变换，其形式简洁、效果显著、易于实现，迅速成为GNN领域的“Hello World”模型，极大地推动了研究热潮。同期，基于空间（Spatial）方法的GNN也开始兴起，如GraphSAGE（2017）提出了归纳式的邻域采样与聚合框架，使得GNN能够处理大规模图。

爆发与分化期（2017-2020）：GCN的成功引发了海量研究。此阶段的主要趋势是模型架构的深化与多样化：

• **注意力机制的引入**：2018年，V. Velickovic等人提出**图注意力网络（Graph Attention Networks, GAT）**，在聚合邻居信息时引入可学习的注意力权重，让模型能够自适应地为不同邻居分配不同的重要性，显著提升了表达能力和可解释性。
• **表达能力的理论探索**：研究者开始从图同构测试等理论角度分析GNN的表达能力上限。2019年，K. Xu等人提出**图同构网络（Graph Isomorphism Network, GIN）**，证明了其具有与Weisfeiler-Lehman测试同等的最大表达能力，推动了模型设计向更强表达能力方向发展。
• **跳跃连接与深层网络**：受ResNet启发，研究者引入残差连接、密集连接等，以缓解GNN在加深时出现的过平滑（Over-smoothing）问题。
• **图池化与读出函数**：如何从节点表示生成高质量的图表示成为研究热点，出现了多种图池化（Pooling）层，如DiffPool、SAGPool等。

成熟与拓展期（2020-至今）：GNN已成为机器学习的主流范式之一，研究进入深水区，呈现与其他范式融合、向更大规模与更复杂任务拓展的特点：

• **图Transformer**：将自然语言处理中成功的Transformer架构适配到图结构，通过完全基于注意力（无需预定义邻接矩阵）的方式建模节点间关系，如Graphormer、GTN等。
• **自监督与预训练**：为克服图标注数据稀缺的问题，大量自监督学习范式被提出，如对比学习（GraphCL、MVGRL）、预测任务（如边预测、子图预测）等，旨在学习通用的图表示。
• **可扩展性**：针对超大规模图（数十亿节点），出现了基于聚类、子图采样、分布式训练等方向的优化工作。
• **跨领域融合**：GNN与计算机视觉（如图像的超级像素图）、强化学习（用于组合优化）、科学计算（用于偏微分方程求解）等领域的结合日益紧密。
• **因果推断与鲁棒性**：研究GNN模型的公平性、可解释性、对抗鲁棒性，以及如何将因果推理融入图学习。

---

三、GNN的主要研究分支：技术版图概览

根据信息传递与聚合方式的不同，现代GNN主要形成了以下几个相互关联的技术分支。

3.1 基于卷积的图神经网络

这是最主流的分支，又可细分为基于谱的方法和基于空间的方法。

基于谱的方法 从图信号处理的角度出发，将图卷积定义为图拉普拉斯矩阵（或其变体）在频域的操作。GCN是其最著名的简化形式。其核心推导基于图傅里叶变换：将节点特征视为图上的信号，图的拉普拉斯矩阵 $\mathcal{L} = D - A$（$D$ 为度矩阵，$A$ 为邻接矩阵）的特征向量构成傅里叶基。谱卷积定义为：$g_\t