图神经网络概述：为何需要图结构建模

第1章 图神经网络概述：为何需要图结构建模

数据形态的演变与新的挑战

过去十余年间，深度学习技术在计算机视觉、自然语言处理、语音识别等领域取得了举世瞩目的成就。从2012年AlexNet在ImageNet图像分类挑战中取得突破性进展开始，卷积神经网络便以其卓越的特征提取能力和端到端学习能力，彻底改变了人们对人工智能系统的认知。此后，循环神经网络、Transformer架构、生成对抗网络等模型相继问世，不断拓展着深度学习的应用边界。这些成功的背后，隐藏着一个共同的前提假设：数据可以被映射到规则的欧几里得空间中进行处理。

然而，当我们审视现实世界的真实数据形态时，会发现一个不容忽视的事实：大量复杂系统的内部结构并非规整的网格或有序的序列，而是以图（Graph）的形式呈现。社交网络中人与人之间的关注与互动关系、分子化合物中原子之间的化学键连接、互联网中网页之间的链接结构、交通系统中城市之间的道路网络——这些数据都具有一个共同的特点：它们的拓扑结构是不规则的、非欧几里得的，每个节点的邻居数量可能不同，节点之间的连接关系错综复杂。

传统深度学习方法在处理这类结构化数据时面临严峻挑战。当我们将图像数据送入卷积神经网络时，数据的规则网格结构使得卷积操作可以自然地进行平移权重共享；但对于社交网络这样的图结构数据，传统的卷积操作失去了定义的基础——我们无法确定一个统一大小的卷积核应该作用于哪些邻居节点，因为每个节点的邻居数量和连接模式都可能完全不同。这种数据结构的不规则性，催生了对新型深度学习模型的需求，图神经网络（Graph Neural Network，GNN）正是在这样的背景下应运而生。

本章将系统性地探讨图神经网络产生的时代背景与研究动机，深入分析传统深度学习方法在处理图结构数据时的局限性，阐述图结构数据在各个领域的普遍性及其建模价值。通过对典型应用场景的案例分析，展示图神经网络在各类图机器学习任务上的独特优势。在此基础上，本章还将为读者梳理本书的知识体系架构与学习路径建议，帮助读者建立对图神经网络领域的整体认知框架。

图结构数据的普遍性与本质特征

从欧几里得到非欧几里得空间

要理解图神经网络的重要性，首先需要厘清欧几里得空间与非欧几里得空间在数据结构层面的本质差异。欧几里得空间是我们在日常生活中最熟悉的空间类型，二维图像和三维视频都可以被理解为该空间中的规则数据。图像可以表示为像素点阵，每个像素的位置由整数坐标$(x,y)$确定，其邻域结构是固定的——每个像素恰好有8个邻居（在考虑对角线的情况下），这种规则的拓扑结构使得卷积操作可以定义在统一的滑动窗口上。

然而，现实世界中存在大量无法嵌入欧几里得空间进行描述的复杂系统。社交网络中的用户节点通过关注、好友、点赞等关系相互连接，但每个用户的社交圈子大小差异巨大——普通用户可能只有几十上百个好友，而明星用户可能拥有数百万粉丝。分子化合物中的原子通过化学键相连，但不同原子的化合价决定了它们可以连接的原子数量各不相同。即便是同一类分子，其同分异构体的空间结构也可能截然不同。这种节点度数可变、拓扑结构不规则的数据，正是非欧几里得空间的典型代表。

图作为描述这类复杂关系的数学抽象，由节点集合和边集合组成。一个图$G$可以形式化地表示为$G = (V, E)$，其中$V = \{v_1, v_2, ..., v_n\}$表示节点集合，$E \subseteq V \times V$表示边集合。每条边$(v_i, v_j)$代表节点$v_i$和$v_j$之间存在某种关系。根据边是否有方向，图可以分为无向图和有向图；根据边是否带有权重，图可以分为无权图和加权图；根据图中是否包含不同类型的节点或边，图可以分为同构图和异构图。这种灵活性使得图结构能够精确地建模现实世界中各种复杂的关联关系。

图结构数据的典型应用领域

图结构数据的普遍性可以从以下几个关键领域得到充分体现，这些领域的数据特性和建模需求共同构成了图神经网络发展的原动力。

社交网络是图结构数据最为典型的应用场景之一。在Facebook、Twitter、微博、微信等社交平台上，用户构成节点，用户之间的好友关系、关注关系、互动行为构成边。社交网络的规模极其庞大——Facebook拥有近30亿活跃用户，Twitter的月活跃用户数超过5亿，这些平台上的用户关系构成了规模空前的社交图谱。社交网络分析涉及众多核心任务：基于用户特征和行为模式的好友推荐、基于社交圈子的用户聚类、谣言和虚假信息的传播路径追踪、社交影响力的量化评估等。这些任务的共同特点是：它们都高度依赖于用户之间的关系网络结构，孤立地将每个用户视为独立样本的做法会丢失关键信息。

分子化学与药物发现领域同样是图结构数据的天然应用场。在分子图中，节点代表原子，边代表化学键。一个药物分子可以看作是由原子（节点）和化学键（边）构成的图结构，不同原子的特性、键的类型、分子的拓扑结构共同决定了分子的化学性质和生物活性。基于图结构进行分子性质预测、药物-靶点相互作用预测、分子生成等任务，对于加速新药研发流程具有重要意义。据统计，一款新药的研发平均需要投入数十亿美元并耗时十余年，而利用深度学习方法辅助药物设计，有望显著缩短这一周期。近年来，基于图神经网络的分子建模方法在溶解度预测、毒性分析、药物-蛋白结合亲和力估计等任务上取得了显著进展。

知识图谱以结构化的方式表示人类知识，将实体作为节点、实体间的关系作为边，构建起大规模的知识网络。Freebase、WordNet、DBpedia、WikiData等都是知名的知识图谱项目，而工业界的知识图谱应用更是无处不在——搜索引擎的知识卡片、推荐系统的用户-物品画像、智能问答系统的背景知识库，背后都有知识图谱的支撑。知识图谱中的链接预测任务旨在推断两个实体之间可能存在的关系，边分类任务需要识别关系的类型，实体分类和对齐任务则涉及节点的语义理解。由于知识图谱具有典型的异构图结构，包含多种类型的节点和边，如何有效地建模这种异质性是知识图谱研究的核心问题之一。

推荐系统中的用户-物品交互数据天然具有二分图的结构。在典型的推荐场景中，用户和物品分别构成两类节点，用户对物品的点击、购买、评分等行为构成边。传统的协同过滤方法虽然能够捕捉用户和物品之间的相似性，但往往忽略了交互行为的上下文信息和交互序列中的时序依赖。图神经网络能够同时建模用户和物品的特征以及它们之间的交互关系，从而提供更加精准的个性化推荐。阿里巴巴、京东、抖音等互联网平台已经在实际业务中大规模部署了基于图神经网络的推荐系统。

交通网络分析是图结构数据在时空维度上的延伸。道路网络可以建模为图结构，其中节点表示路口或地标，边表示道路段，边的权重可能代表道路长度、通行时间或拥堵程度。更加复杂的交通图还会引入时间维度，形成时空图结构，其中同一道路在不同时间段的交通状况构成了时序信号。基于图神经网络的方法被广泛应用于交通流量预测、路径规划、异常检测等任务。智慧城市建设的推进为这类应用提供了广阔的发展空间。

生物信息学领域同样离不开图结构建模。蛋白质相互作用网络描述了蛋白质之间的物理交互关系，基因调控网络刻画了基因之间的上下游调控关系，神经元连接图谱记录了大脑中神经元之间的突触连接。这些生物网络的研究对于理解生命活动的分子机制、揭示疾病的产生机理、开发新的治疗策略都具有重要价值。图神经网络已经成为生物信息学研究中的重要工具，在蛋白质功能预测、药物靶点发现、疾病基因识别等任务中展现出优异性能。

图结构数据的本质特征

深入理解图结构数据，需要把握以下几个本质特征，这些特征决定了图神经网络的设计原则和技术路线。

结构信息的重要性是图数据区别于独立样本集合的关键所在。在传统机器学习任务中，每个样本通常被视为独立同分布的个体，模型关注的是样本自身的特征。但在图数据中，节点之间的关系往往携带着与节点自身特征同等重要甚至更加重要的信息。一个社交网络用户的政治倾向不仅受到其个人属性的影响，更受到其朋友圈子的显著影响；一个分子的化学性质不仅取决于组成它的原子种类，还取决于这些原子之间的连接方式。这种结构依赖性意味着，我们需要设计能够同时利用节点特征和拓扑结构的模型。

邻居节点的异质性是非规则图结构的直观体现。在规则的欧几里得空间数据中，每个位置的所有邻居都在空间中占据固定的位置，其几何关系是确定性的。但在图结构中，每个节点的邻居数量、邻居的语义角色、邻居之间的相互关系都可能各不相同。考虑一个论文引用网络：一篇学术论文可能被数十篇甚至数千篇其他论文引用，这些引用论文的主题、质量、时效性差异巨大；同样，这篇论文引用的参考文献也反映了作者的研究背景和知识来源。如何恰当地聚合这些异质的邻居信息，是图神经网络面临的核心挑战。

图结构的动态演化特性为建模增添了时间维度。许多现实世界的图结构并非静态不变，而是随着时间不断演化。社交网络中用户会建立新的好友关系或取消关注，道路交通网络中会涌现新的拥堵节点，知识图谱中会不断添加新的实体和关系。这种动态性要求模型能够处理图结构的时变特性，既要考虑结构的历史演变，也要预测未来的发展趋势。动态图建模已经成为图神经网络研究的一个重要方向。

大规模图数据的可扩展性挑战在实际应用中不容忽视。一个包含数十亿节点和数万亿边的工业级图数据对计算资源提出了极高要求。传统的图处理算法往往难以在这样的规模下高效运行，如何设计能够处理大规模图数据的可扩展算法是图神经网络从学术研究走向工业应用必须解决的问题。

传统深度学习方法的局限性分析

卷积神经网络在图结构上的困境

卷积神经网络在处理图像、语音、文本等规整数据时取得的巨大成功，很大程度上归功于卷积操作的两个关键特性：权重共享和局部感受野。权重共享机制使得网络能够以少量的参数学习到跨越整个输入空间的平移不变特征；局部感受野则通过层级式的信息聚合，让网络能够逐步捕获从局部细节到全局模式的各类特征。这两个特性的结合，赋予了卷积神经网络强大的特征学习能力。

然而，当我们尝试将卷积操作迁移到图结构数据时，首先遇到的问题是如何定义“卷积”。在图像上，卷积核可以沿着规则的像素网格滑动，每次处理一个固定大小的邻域块。邻域块中的像素在空间位置上是有序且连续的，这种有序性使得我们可以将邻域展开为向量并进行线性变换。但在图结构中，节点的邻居没有自然的空间顺序——对于一个有$k$个邻居的节点，这$k$个邻居之间不存在类似“左上”“右下”的空间关系，我们无法将它们的特征向量按照某种确定的方式拼接成卷积核所需的输入格式。

更根本的问题在于邻居数量的可变性。在图像中，每个位置周围的像素数量是固定的（边界情况除外），这使得我们可以使用固定大小的卷积核。但在社交网络中，一个普通用户可能只有十几个好友，而一个名人可能拥有数百万粉丝。使用固定大小的卷积核无法同时适配这两种截然不同的情况：若按小邻居数设计，会丢失大度数节点的邻居信息；若按大邻居数设计，对于小度数节点会产生大量冗余计算。

循环神经网络处理图结构的不足

循环神经网络及其变体（如LSTM、GRU）在处理序列数据方面表现出色。序列数据天然具有时间维度的有序性，每个时间步的输出取决于当前输入和隐藏状态，而隐藏状态则编码了历史序列的信息。这种时序建模能力使得循环神经网络成为自然语言处理、时间序列预测等领域的主流模型。

然而，将循环神经网络应用于图结构数据存在本质性的困难。循环神经网络要求数据具有明确的序列顺序——文本中的词语顺序、语音中的时间序列、视频中的帧顺序。这种顺序性为信息的传递提供了唯一确定的方向。但在图结构中，信息的流动可以是双向甚至多向的：在一个社交网络中，用户A关注用户B和用户B关注用户A代表两种不同的关系，但这种关系并非简单的时序先后；在一个化学分子中，信息的传递需要考虑所有相邻化学键的贡献，而非单一的传播方向。

虽然可以通过为图中的节点分配任意顺序来强行将图数据转化为序列，但这会导致两个严重问题。其一是排序的随意性——不同的排序方式可能产生完全不同的序列，从而影响模型的输出，导致模型缺乏良好的定义；其二是顺序信息的虚假性——强制赋予图的边以人为的顺序，可能误导模型学习到并不存在的依赖关系。真正有效的图建模方法需要尊重图结构本身的拓扑性质，而非简单地将其约减为序列问题。

传统特征工程方法的局限

在深度学习兴起之前，图机器学习主要依赖人工设计的特征来描述节点、边或整张图的属性。节点级别的特征工程包括节点的度数、邻居的统计信息、聚类系数、介数中心性等拓扑指标，以及节点在网络中的各种中心性度量（如特征向量中心性、PageRank等）。图级别的特征则包括图的直径、平均路径长度、连通分量数量、子图模式计数等全局统计量。

这些传统方法虽然在某些简单任务上取得了一定效果，但存在明显的局限性。首先，人工设计特征需要领域专家的参与和大量的特征工程工作，且设计出的特征往往是针对特定任务和特定类型图的，难以泛化到新任务和新场景。其次，传统特征往往只捕获图的浅层拓扑信息，无法刻画节点之间的高阶依赖关系。再者，在特征维度很高或样本数量很大的情况下，基于特征工程的方法可能面临维度灾难和计算效率的问题。

深度学习方法的核心优势在于能够从数据中自动学习到任务相关的特征表示，无需人工设计。这种端到端的学习范式已经在图像、语音、自然语言处理等领域证明了自己的有效性。图神经网络正是将这种自动特征学习能力引入图结构数据处理的结果，它继承了深度学习的表示学习优势，同时针对图结构数据的特殊性进行了有针对性的设计。

图神经网络的兴起与技术演进

从图神经网络到图卷积网络

图神经网络的概念最早可以追溯到21世纪初。Gori等人于2005年首次提出了图神经网络的正式定义，旨在将神经网络技术推广到图结构数据的处理中。Scarselli等人进一步发展了这一框架，提出了基于收缩空间（Contractive Space）和迭代不动点机制的图神经网络模型。这些早期工作虽然奠定了图神经网络的基本思想，但由于其计算复杂度高、难以训练等问题，并未在当时的机器学习社区引起广泛关注。

2013年，Bruna等人发表了具有里程碑意义的论文《Spectral Networks and Locally Connected Networks on Graphs》，首次将卷积操作从欧几里得空间推广到图结构数据。他们利用图拉普拉斯矩阵的谱分解来定义图的卷积操作，从而在频域中实现了图的卷积滤波。这一工作开创了图卷积网络的谱方法流派，为后续研究奠定了理论基础。

然而，谱方法的计算复杂度较高，且依赖于图结构的谱分解，难以处理大规模的动态图。针对这些问题，研究者们开始探索在空间域直接定义卷积操作的方法。2015年，Duvenaud等人提出了基于节点邻居特征聚合的图卷积方法；2016年，Atwood和Towsley发表了扩散卷积神经网络（DCNN），将图上的信息传播建模为扩散过程；同年，Niepert等人提出了将图邻域规整化为固定大小序列的邻域采样方法。

2017年是图神经网络发展的一个重要节点。Kipf和Welling提出了名为GCN（图卷积网络）的简化模型，该模型通过一阶切比雪夫多项式近似谱域卷积，将计算复杂度降低到与边数成线性关系的水平。GCN以其简洁的数学形式和优异的性能迅速成为图神经网络领域最具影响力的模型之一，被广泛应用于各种图机器学习任务。同年，Hamilton等人提出了GraphSAGE模型，创新性地引入邻居采样和聚合函数可学习的设计，使得图神经网络能够处理大规模归纳学习任务，即对训练时未见过的节点进行预测。

图注意力网络与异构图神经网络

2018年，Velickovic等人提出了图注意力网络（Graph Attention Network，GAT），将注意力机制引入图神经网络的设计。GAT通过学习不同邻居节点的注意力权重，使模型能够自动地为重要的邻居分配更高的贡献度。这一设计不仅提升了模型的表达能力，还增强了模型对异质邻居关系的建模能力。GAT的提出标志着图神经网络在处理复杂拓扑结构方面迈出了重要一步。

随着图神经网络技术的不断成熟，研究者们开始关注更加复杂的图结构类型。异构图包含多种类型的节点和边，其建模需要考虑节点和边的异质性。Han等人提出的HAN（Heterogeneous Graph Attention Network）和Wang等人提出的MAGNN（Heterogeneous Graph Neural Network）是处理异构图的两个代表性工作，它们通过设计针对异构性的特殊聚合机制，有效利用了异构图中的丰富语义信息。

图Transformer是近年来兴起的一个新方向，它将Transformer架构中的自注意力机制应用于图结构数据。与图注意力网络类似，图Transformer通过自注意力来学习节点之间的关系，但它的设计更加接近自然语言处理中的Transformer，能够更好地捕获长距离的节点依赖关系。同时，图Transformer还需要解决如何将图的结构信息编码到模型中的问题，这是一个活跃的研究领域。

关键技术创新与代表性模型

图神经网络的发展历程中涌现出众多创新性的技术方案，这些方案从不同角度解决了图结构数据建模中的关键问题。

消息传递机制是现代图神经网络的核心抽象框架。Gilmer等人于2017年提出的消息传递神经网络（Message Passing Neural Network，MPNN）框架，将图神经网络的计算过程分解为消息传递和状态更新两个阶段。在每一层，每个节点会从其邻居节点接收消息（message），根据接收到的消息更新自己的隐藏状态。这一抽象框架统一了许多之前提出的图神经网络模型，使得研究者可以更加系统地理解和设计新的模型变体。

邻居采样技术解决了大图上的可扩展性问题。GraphSAGE模型提出了三种基本的邻居聚合函数：Mean aggregator（均值聚合）、LSTM aggregator（长短期记忆聚合）和Pooling aggregator（池化聚合）。其中，均值聚合器直接对邻居节点的表示取平均，实现简单且效果稳健；LSTM聚合器利用LSTM网络对邻居序列进行处理，能够捕获邻居之间的复杂交互；池化聚合器则先对每个邻居进行独立的线性变换，然后应用最大池化操作。这些聚合函数的设计为后续研究提供了重要的参考。

图采样策略是处理超大规模图的关键技术。GraphSAGE通过随机采样固定数量的邻居来控制每个节点的聚合计算量。Cluster-GCN和GraphSAINT等方法则采用图聚类或随机游走的方式对整个图进行采样，生成若干子图，然后在子图上进行训练。这些采样策略使得图神经网络能够应用于包含数十亿节点的大规模图数据。

位置编码与结构编码技术为图神经网络提供了额外的结构信息。由于图结构本身缺乏像自然语言中的词序那样的自然顺序，研究者们尝试引入额外的编码来表示节点在图中的位置。拉普拉斯位置编码、随机游走位置编码等方法被用于为每个节点生成一个位置向量，将其与节点的语义特