绪论：从图数据到图智能

我们生活在一个由关系编织的世界中。从社交网络中人与人之间的纽带，到互联网上网页与网页之间的超链接；从生物体内蛋白质与蛋白质之间的相互作用，到物流网络中城市与城市之间的运输路线——连接与关系构成了这个复杂世界的基础架构。这种以“节点”代表实体、以“边”代表关系的数据结构，在计算机科学中被抽象为图（Graph）。图数据不仅无处不在，而且蕴含着关于系统结构、功能和动态的深刻洞见。然而，如何让机器理解、推理并利用这些图结构中的信息，长期以来是人工智能与机器学习领域面临的核心挑战之一。传统机器学习方法，尤其是那些在欧几里得空间数据（如图像、文本、序列）上取得巨大成功的模型，在处理图这种非欧几里得、不规则的数据结构时，往往显得力不从心。正是这种需求与局限之间的张力，催生了一类全新的深度学习架构——图神经网络。图神经网络通过设计专门的消息传递与聚合机制，使神经网络能够直接在图结构上进行学习，从而开启了从“图数据”到“图智能”的范式转换。本章作为全书的开篇，旨在为读者构建关于图数据与图智能的宏观认知框架。我们将首先阐述图数据的普遍性及其在现实世界中的核心地位，进而剖析传统机器学习方法在处理图数据时遭遇的根本性障碍。在此基础上，本章将正式引出图神经网络作为解决这些问题的核心范式，概述其发展历程、主要技术分支（包括图卷积网络、图注意力网络以及知识图谱表示学习），并展示其在社交网络分析、推荐系统、生物信息学等关键领域的革命性应用前景。最后，本章将勾勒全书的整体结构，为读者规划一条从理论到实践、从基础到前沿的系统学习路径。

图数据的普遍性与核心地位

图，作为一种描述实体及其之间关系的数据结构，其历史可追溯至数学中的图论。1736年，欧拉通过解决柯尼斯堡七桥问题，开创了图论研究的先河。然而，直到计算机科学和互联网的兴起，图才从纯数学对象转变为一种基础性的数据表示范式。今天，图数据已经渗透到科学技术与日常生活的方方面面，成为描述复杂系统不可或缺的工具。

现实世界中的图实例

社交网络是最直观的图数据实例。以Facebook、Twitter、微信等平台为例，用户是图中的节点，用户之间的关注、好友、互动关系构成边。这些社交图谱的规模极其庞大：截至2023年，Facebook的月度活跃用户超过30亿，构成了一个拥有数十亿节点和数百亿边的巨型图。分析这样的社交图可以揭示社区结构、识别意见领袖、预测信息传播路径，甚至影响选举结果。

信息网络同样以图的形式组织。万维网（WWW）是一个巨大的 directed graph，其中网页是节点，超链接是边。Google的PageRank算法正是基于这个链接图，通过计算节点的“重要性” ranking，奠定了现代搜索引擎的核心。学术引用网络（如Microsoft Academic Graph或OpenAlex）将论文作为节点，引用关系作为边，用于分析科学合作模式、追踪研究前沿、评估学术影响力。

生物信息学与化学领域充满了复杂的图结构。在分子层面，原子是节点，化学键是边，构成了分子图。预测分子的性质（如毒性、溶解度、药物活性）是计算化学的核心任务，传统方法依赖于手工设计的分子描述符，而图神经网络可以直接从分子图结构中学习，在药物发现中展现出巨大潜力。在细胞层面，蛋白质-蛋白质相互作用网络（PPI）将蛋白质作为节点，物理相互作用作为边，用于理解细胞功能、疾病机制和识别药物靶点。

基础设施与物理网络也是典型的图。交通网络（道路、航线、铁路）中，交叉口或机场是节点，路段或航线是边；电力网络中，变电站或发电机是节点，输电线路是边。优化这些网络的流量、提高韧性、规划新线路是图分析的重要应用。

知识图谱是近年来兴起的一种特殊图结构，它以结构化的方式存储人类知识。在知识图谱中，节点代表实体（如“莎士比亚”、“《哈姆雷特》”），边代表实体间的关系（如“作者”、“创作于”）。Google的知识图谱于2012年推出，用于增强搜索结果；企业知识图谱用于智能客服、风险管理和决策支持。诸如DBpedia、Wikidata、CN-DBpedia等大规模开放知识图谱，包含了数千万实体和数十亿事实，是人工智能实现“可解释推理”的关键基础设施。

这些实例揭示了一个关键特征：图数据天然编码了关系信息。在社交网络中，一个人的影响力不仅取决于其自身属性，更取决于其所在的位置及其与谁相连；在分子图中，一个原子的化学活性由其局部化学环境决定；在引文中，一篇论文的重要性由其被谁引用所决定。这种“关系即信息”的哲学，是图数据分析的理论基石。

图数据的形式化定义

在深入技术细节之前，我们给出图数据的标准形式化定义。一个图 $G$ 通常定义为一个元组 $G = (\mathcal{V}, \mathcal{E})$，其中：

• $\mathcal{V}$ 是节点（Vertex/Node）集合，大小为 $|\mathcal{V}| = N$。每个节点 $v \in \mathcal{V}$ 通常关联一个**特征向量** $\mathbf{x}_v \in \mathbb{R}^d$，描述节点的属性（如用户的年龄、兴趣；分子的原子类型）。
• $\mathcal{E} \subseteq \mathcal{V} \times \mathcal{V}$ 是边（Edge）集合，大小为 $|\mathcal{E}| = M$。每条边 $(u, v) \in \mathcal{E}$ 表示节点 $u$ 和 $v$ 之间存在关系。边可以是**无向的**（关系对称，如Facebook好友）或**有向的**（关系不对称，如Twitter关注、网页超链接）。边也可以携带**特征** $\mathbf{e}_{uv}$（如关系的类型、强度、时间戳）。
• 图可以是**同质的**（所有节点和边属于同一类型，如社交网络）或**异质的**（包含多种节点和边类型，如学术知识图谱包含论文、作者、会议、机构等节点类型，以及“写作”、“隶属于”、“发表于”等边类型）。

此外，图可以附加一个全局标签 $y_G$（如图的类别：社交图 vs. 分子图），或节点级标签 $y_v$（如用户的性别、分子的活性标签），或边级标签（如链接预测中预测边是否存在）。图学习任务的目标，就是根据图的拓扑结构（$\mathcal{V}, \mathcal{E}$）、节点/边特征以及（部分）标签，去预测未知的标签或生成新的图结构。

图数据分析的核心价值

为什么图数据如此重要？其价值根植于几个核心特性：

1. 关系推理的天然载体：许多现实世界问题的本质是关系性的。推荐系统的核心是“喜欢物品A的用户也喜欢物品B”的协同过滤思想；知识推理的核心是“如果A是B的父亲，B是C的父亲，那么A是C的祖父”的传递闭包；社交影响分析的核心是“朋友的态度会影响个人的观点”。图结构将这种关系显式化，为进行显式的关系推理提供了基础。

2. 对非欧几里得数据的直接建模：图像数据位于规则的网格上（像素矩阵），文本数据位于序列中（词向量序列），它们都存在于欧几里得空间，具有平移不变性等性质。而图结构没有固定的顺序，节点的邻居数量可变，不存在全局的坐标系统。这种不规则性和置换不变性（节点的排列顺序不影响图的语义）使得传统为欧几里得数据设计的模型（如卷积神经网络CNN、循环神经网络RNN）难以直接应用。

3. 复杂系统涌现行为的分析工具：复杂系统（如大脑、生态系统、经济系统）的宏观行为往往由微观个体间的简单交互涌现而来。图是描述这些个体（节点）和交互（边）的自然语言。通过分析图的结构特性（如度分布、聚类系数、路径长度）和动态演化，可以洞察系统的稳健性、脆弱性、传播动力学等宏观特性。

因此，掌握图数据分析技术，意味着获得了一把解锁众多科学与工程领域核心问题的钥匙。然而，这把钥匙并非传统机器学习工具箱中的常规工具，其设计需要全新的思想。

传统机器学习方法处理图数据的局限性

在深度学习崛起之前，图分析主要依赖于图挖掘和网络科学领域的经典算法，如社区发现（如Louvain方法）、节点中心性度量（如度中心性、介数中心性）、链接预测（如Jaccard系数、Adamic-Adar指数）等。这些方法通常基于手工设计的特征或启发式规则，在特定任务上表现良好，但缺乏学习能力和泛化能力，难以处理复杂的节点/边特征，也无法在一个统一的框架下解决节点分类、链接预测、图分类等多种任务。

随着深度学习的成功，研究者自然尝试将强大的神经网络应用于图数据。然而，直接将为图像或序列设计的模型套用于图结构，会遇到根本性的障碍。

卷积神经网络在图像上的成功与在图上的困境

CNN在计算机视觉领域的成功很大程度上归功于卷积操作的两个关键设计： 1. 局部连接：卷积核只与输入的一个局部区域（如3x3像素）相连，利用图像的平移不变性和局部相关性。 2. 参数共享：同一个卷积核在整个图像上滑动使用，大幅减少参数量，并使得模型对物体位置具有不变性。

这些设计依赖于输入数据的网格状规则结构。图像可以视为一个二维网格图，其中每个像素与其上、下、左、右的邻居有固定连接。这种规则的邻接关系使得“局部区域”的定义变得明确且一致。

然而，图结构是不规则的：

• **邻居数量可变**：一个节点的度（邻居数）可以从1到数千不等（如社交网络中的名人节点）。CNN的卷积核大小是固定的（如3x3），无法适配这种可变性。
• **邻居无序**：节点的邻居集合没有内在的顺序。而CNN的卷积操作隐式地假设了输入局部区域有固定的空间顺序（如左上、右上、左下、右下）。对邻居集合进行任意排列，CNN的输出会改变，但图的语义不应改变（**置换不变性**要求）。
• **缺乏全局坐标**：图像中像素的位置由行列索引固定，而图中节点没有这样的全局坐标。无法定义“上”、“下”、“左”、“右”这样的方向。

因此，直接将在图像上定义的卷积核（如3x3）应用于图，首先面临的问题是：对于一个度不为4的节点，如何定义它的“3x3邻域”？即使强行定义一个固定大小的邻居采样集合，如何对采样的邻居进行排序以匹配卷积核的输入顺序？这种排序是任意的，会导致模型不稳定且违背置换不变性。

循环神经网络处理序列与处理图的错配

RNN及其变体（LSTM、GRU）擅长处理序列数据，其核心是维护一个随时间步演化的隐状态，并利用当前输入和上一时刻隐状态计算当前隐状态。序列数据具有天然的顺序性（时间步或词序）。

将RNN直接应用于图的一种朴素思路是：对图进行随机游走，生成节点序列，然后用RNN处理这个序列。这种方法（如DeepWalk、node2vec）确实产生了强大的图嵌入方法，为每个节点学习到一个低维向量表示。然而，这种序列化方法存在根本局限： 1. 信息丢失：随机游走只能捕捉到局部邻域信息，难以有效捕获图中长距离依赖或全局结构。一个节点可能通过多条不同路径与另一个节点相连，随机游走只能捕获其中一条路径。 2. 任务不匹配：生成的节点嵌入是静态的，通常用于后续的节点级任务（如分类）。但对于需要动态消息传递的任务（如推理随时间演化的图），或需要同时考虑节点和边信息的任务，序列化方法力不从心。 3. 无法端到端优化：随机游走过程通常是预训练、与下游任务分离的，无法根据最终任务目标（如分类准确率）来优化游走策略和嵌入学习。

图核方法与手工特征的瓶颈

在深度学习之前，图核方法（Graph Kernels）是处理图分类任务的主流方法。其思路是：设计一个函数 $k(G_i, G_i')$ 来计算两个图之间的相似度，然后结合SVM等核方法进行分类。图核通常通过计数图中特定的子结构（如walks、subtrees、graphlets）来定义图特征。例如，随机游走核计算两条随机游走序列相同的概率。

图核方法的局限性显而易见：

• **手工设计**：子结构模式是人工预先定义的，可能无法捕捉到对任务真正重要的复杂结构模式。
• **计算昂贵**：精确计算某些图核（如图let核）是#P-难问题，通常需要近似或采样，在大图上不 scalable。
• **缺乏层次化表示学习**：它们学习的是图级别的相似度度量，而不是一种**分层、分布式**的节点/图表示。无法像深度学习那样，从低层特征自动组合出高层抽象。

核心矛盾：图的不规则性与神经网络固定结构的冲突

综上所述，传统方法（包括早期神经网络尝试）处理图数据的根本困境，可归结为图的不规则性、可变性、无序性与神经网络设计的固定性、规则性、有序性假设之间的深刻矛盾。神经网络层通常期望输入具有固定的维度（如图像的HxWxC）和某种空间/时序顺序。而图数据天然打破了这些假设。

解决这一矛盾的关键，在于重新思考神经网络层应该如何定义，才能使其天然地接纳图结构作为输入，并尊重图的置换不变性。也就是说，我们需要一种新的神经网络计算范式，其计算过程依赖于图的拓扑连接关系，而非输入张量的固定几何结构。这正是图神经网络的核心思想：消息传递神经网络。

图神经网络：核心范式与思想起源

图神经网络是一类专门为处理图结构数据而设计的深度学习模型。其核心思想可以追溯到消息传递机制：图中的每个节点通过从其邻居收集（聚合）消息，并更新自己的状态，从而逐步融合其多跳邻居的信息。这个过程在数学上被形式化为消息传递神经网络框架。

消息传递机制：图神经网络的统一视图

目前绝大多数GNN模型都可以在消息传递的统一框架下理解。该框架定义了一个节点状态随时间（或层）演化的迭代过程。在每一层 $k$（$k = 0, 1, 2, ...$），每个节点 $v$ 执行以下两步：

1. 消息函数（Message Function） $m_{u \to v}^{(k)} = \text{MSG}^{(k)}(\mathbf{h}_u^{(k-1)}, \mathbf{h}_v^{(k-1)}, \mathbf{e}_{uv})$：对于每条边 $(u, v)$，节点 $u$（源节点）根据其上一时刻的状态 $\mathbf{h}_u^{(k-1)}$、目标节点 $v$ 的状态 $\mathbf{h}_v^{(k-1)}$（可选）以及边的特征 $\mathbf{e}_{uv}$，生成一条发送给 $v$ 的消息 $\mathbf{m}_{u \to v}^{(k)}$。这个函数定义了“邻居如何向中心节点传递信息”。

2. 聚合函数（Aggregation Function） $\mathbf{m}_v^{(k)} = \text{AGG}^{(k)}(\{ m_{u \to v}^{(k)} | u \in \mathcal{N}(v) \})$：节点 $v$ 收集所有邻居 $u \in \mathcal{N}(v)$ 发送来的消息，并通过一个置换不变的函数（如求和、平均值、最大值）进行聚合，得到聚合后的消息 $\mathbf{m}_v^{(k)}$。置换不变性是关键：无论邻居的顺序如何，聚合结果必须相同，这保证了模型对节点排列的不变性。

3. 更新函数（Update Function） $\mathbf{h}_v^{(k)} = \text{UPD}^{(k)}(\mathbf{h}_v^{(k-1)}, \mathbf{m}_v^{(k)})$：节点 $v$ 结合其上一时刻的状态 $\mathbf{h}_v^{(k-1)}$ 和聚合得到的消息 $\mathbf{m}_v^{(k)}$，通过一个更新函数（通常是一个神经网络，如MLP）生成其新的状态 $\mathbf{h}_v^{(k)}$。这个新状态编码了 $v$ 的 $k$-跳邻居范围内的结构信息。

经过 $K$ 层传播后，每个节点 $v$ 的最终状态 $\mathbf{h}_v^{(K)}$ 理论上包含了其 $K$ 跳内邻居的子图结构信息。这个节点表示 $\mathbf{h}_v^{(K)}$ 可以用于下游任务：

• **节点级任务**：直接使用 $\mathbf{h}_v^{(K)}$ 预测节点标签 $y_v$。
• **边级任务**：将两个节点的表示拼接或交互（如 $\mathbf{h}_u^{(K)} \oplus \mathbf{h}_v^{(K)}$）后预测边标签 $y_{uv}$。
• **图级任务**：对所有节点表示进行**全局池化**（如求和、平均、最大池化），或使用特殊的[虚拟]节点，生成整个图的表示 $\mathbf{h}_G$，用于预测图标签 $y_G$。

这个框架的优美之处在于其通用性和灵活性：通过选择不同的消息函数、聚合函数和更新函数，可以衍生出种类繁多的GNN模型。它从根本上解决了图的不规则性问题：计算是按边定义的，天然适应可变邻居数；聚合函数保证了置换不变性；整个计算过程完全由图的邻接关系驱动。

从图嵌入到图神经网络的演进

在GNN概念成熟之前，研究者已经发展了多种图嵌入方法，旨在将图中的节点（或整个图）映射到低维连续向量空间，同时保留图的某些结构特性。这些方法为GNN的诞生奠定了重要思想基础。

• **基于矩阵分解的方法**：如Laplacian Eigenmaps、LLE等，利用图的拉普拉斯矩阵，通过谱分解学习嵌入，旨在保持图中邻近节点的相似性。这些方法本质上是线性的，难以扩展到大规模图，且无法利用节点特征。
• **基于随机游走的方法**：DeepWalk（2014）将图上的随机游走视为“句子”，游走经过的节点视为“词”，借用词嵌入模型Word2Vec（Skip-gram）来学习节点嵌入。后续的node2vec（2016）通过调整随机游走的策略（在BFS和DFS之间权衡），在保留同质性和结构性之间取得平衡。这些方法成功地将自然语言处理中的嵌入思想引入图领域，但它们**将图结构转化为序列**，损失了图的全局结构信息，且嵌入过程与下游任务解耦。

图神经网络的真正突破发生在2016-2017年。关键里程碑包括：

• **谱图卷积网络**：Bruna等人在2013年提出将卷积操作从欧几里得空间推广到图，利用图的拉普拉斯矩阵的谱分解定义图卷积。然而，其计算涉及完整的拉普拉斯矩阵，计算复杂度高且不适用于动态图。Defferrard等人（2016）使用切比雪夫多项式近似，降低了计算成本。
• **空域图卷积网络**：与谱方法不同，**空域方法**直接在图的节点邻域上定义卷积，不依赖于全局图拉普拉斯。Kipf & Welling（2017）提出的**GCN**是里程碑式的工作。他们简化了谱方法中的切比雪夫近似，提出了一个简单而有效的层传播规则：

$$\ma