编辑推荐:
现有图神经网络(Graph Neural Networks,GNNs)通常仅能处理这样一类图:其中每个顶点由一个向量或单一数值表示,因此其对复杂对象的表征能力受到限制。本文提出了一种新型图神经网络,称为图中图神经网络(Graph in Graph Neural
现有图神经网络(Graph Neural Networks,GNNs)通常仅能处理这样一类图:其中每个顶点由一个向量或单一数值表示,因此其对复杂对象的表征能力受到限制。本文提出了一种新型图神经网络,称为图中图神经网络(Graph in Graph Neural,GIG Network),可处理一种图式数据(称为GIG样本),其顶点本身进一步由图表示。给定一组图,或一个其组成部分可由一组图表示的数据样本(称为多图数据样本),该GIG网络首先通过GIG样本生成(GIG Sample Generation,GSG)模块将输入编码为一个GIG样本,其中每个GIG顶点都包含一个图。随后,研究人员堆叠一组GIG隐藏层,每个隐藏层由以下两部分构成:(1)GIG顶点级更新(GIG Vertex-level Updating,GVU)模块,用于基于每个GIG顶点内部信息,独立更新其中的图;以及(2)全局级GIG样本更新(Global-level GIG sample Updating,GGU)模块,用于基于各GIG顶点之间的关系更新所有GIG顶点中的图,从而使更新后的GIG顶点具备全局上下文感知能力。通过这种方式,既能够利用每个GIG顶点所含图内部的线索,也能够利用GIG顶点之间的关系,以服务于下游任务。实验结果表明,该GIG网络不仅能够良好泛化至多种通用图分析任务,也适用于真实世界多图数据分析(例如,基于人体骨架视频的动作识别),并在16个评测数据集中的15个上取得了新的最优结果。代码已公开发布于 https://github.com/wangjs96/Graph-in-Graph-Neural-Network。
该研究发表于《INTERNATIONAL JOURNAL OF COMPUTER VISION》,核心目标是突破传统图神经网络(Graph Neural Networks,GNNs)在顶点表示层面的固有限制。既有GNN通常假定图中每个顶点仅由固定维度向量或单一标量表示,因此虽然它们已经在图分类、节点分类、链路预测、分子建模、行为理解等任务中取得广泛成功,但对于“对象本身具有复杂内部结构”的场景,其表达能力仍然不足。论文指出,在许多真实问题中,单个数据样本往往天然包含多个相互关联的复杂对象,而这些对象本身更适合以图而非向量表示。例如,人体骨架视频中每一帧骨架本身就是由关节和骨骼构成的空间图;交通预测中每个时刻的全局交通状态可以建模为传感器之间具有空间联系的图,而不同时刻之间又存在时间依赖;分子系统中每个分子可视作图,分子间相互作用又形成更高层级关系。传统GNN若将这些复杂对象压缩成向量作为顶点,容易丢失对象内部的空间、结构或语义线索,因此有必要发展一种能够直接处理“顶点中嵌套图”的新型图学习框架。
围绕这一问题,研究人员提出图中图神经网络(Graph in Graph Neural Network,GIG)。该模型将输入数据统一编码为GIG样本(GIG sample):高层图的每个GIG顶点内部都包含一个普通图,同时不同GIG顶点之间再通过GIG边建立联系。与现有子图GNN不同,本文不是将一个大图拆解为多个子图,而是把多个图,或一个数据样本中的多个图式组成部分,联合组织成一个更高层级的图结构进行建模。为此,作者设计了两级更新机制:一方面通过GIG顶点级更新模块(GVU)在每个GIG顶点内部提取局部图结构信息,另一方面通过全局级GIG样本更新模块(GGU)在不同GIG顶点之间传播信息,使各局部图获得全局上下文感知能力。论文的主要结论是:该框架能够同时利用图内关系与图间关系,在16个数据集中的15个达到最优性能,说明“图作为顶点表示”的建模范式具有显著的有效性与普适性。
从方法上看,研究人员首先利用GIG样本生成模块(GSG)将输入构造成由多个GIG顶点组成的高层图,每个GIG顶点包含一个图,并为其引入局部代理顶点(local proxy vertex)与全局代理顶点(global proxy vertex)以实现高效消息交换。随后,GVU模块先更新每个GIG顶点内部的图边、图顶点及局部代理顶点;GGU模块再通过GIG边在不同GIG顶点间传播由局部代理汇聚的表示,并将全局上下文反馈至图顶点。实验覆盖12个通用图数据集与4个天然多图数据集,其中真实样本来源包括PeMSD7交通传感器网络与NTU RGB+D人体骨架动作数据集。模型可灵活继承GatedGCN、GAT、GCN、DeeperGCN、STGCN、CTR-GCN等更新函数。
研究结果部分可概括如下。
1 Introduction
引言部分系统阐明了研究动机。首先,现有GNN虽在顶点和边更新机制上不断进步,但几乎都默认顶点由向量或标量表示,这限制了其对复杂对象的建模能力。其次,许多真实数据天然符合“图中图”结构:如多分子系统、交通监测网络、电力配电网络、骨架视频序列等。再次,在通用图分析任务中,不同图样本之间的关系也可能为表示学习提供补充信息,而既有对比学习方法通常只能借助手工定义损失建模某种特定图间关系,表达能力有限。基于此,作者提出GIG网络,试图显式联合建模图内关系与图间关系。
2 Related Work
相关工作部分分为两条主线。其一是图神经网络发展脉络,论文回顾了消息传递型GNN(MPNNs)与Weisfeiler-Lehman型GNN(WLGNNs),指出前者偏重局部邻域传播,后者强化高阶结构辨识,但均未改变顶点表示的基本假设。其二是图顶点表示学习,作者梳理了图像、视频、音频、文本等领域中“将复杂对象压缩为顶点向量”的常见做法,并指出这种预先向量化会丢失对象内部关系。作者还比较了少量可联合处理多个集合元素的排列等变网络,认为这些方法既非专门的GNN,也无法像GIG那样显式交互多个图。
3 Preliminaries
预备知识部分首先给出了标准消息传递GNN的形式化定义,包括边更新函数、顶点消息聚合函数以及顶点更新方式。该部分的作用在于为后续GIG框架提供统一的数学接口:GIG并非抛弃原有GNN,而是在更高层级上扩展其适用对象,使已有边更新、点更新函数能够嵌入新框架中继续使用。
4 Graph in Graph Neural Network
这一部分是全文核心。
4.1 GIG sample generation (GSG) layer
研究人员首先定义GIG样本。一个GIG样本由一组GIG顶点、GIG边、局部代理顶点、全局代理顶点以及代理边组成。每个GIG顶点内部包含一个图 \(\mathcal {S}^{i}(V_S^i,E_S^i)\)。局部代理顶点 \(P_l^i\) 用于汇聚该内部图的局部信息,全局代理顶点 \(P_g^i\) 用于接收来自其他GIG顶点的上下文信息。GSG层的关键结论是:任意输入——无论是一批图样本,还是可分解为多个图组成部分的多图数据样本——都能被统一编码为GIG样本。作者进一步提出通过余弦相似度选择与代理顶点连接的图顶点,并通过不同策略建立GIG边,实验表明混合连接策略效果最好。
4.2 GIG hidden layer
每个GIG隐藏层由GVU与GGU两部分构成,形成“先局部、后全局”的双阶段更新流程。
4.2.1 GIG Vertex Updating (GVU) module
通过该模块,研究人员在每个GIG顶点内部独立执行图更新。首先更新图边特征,再基于邻域聚合更新图顶点;之后更新从图顶点指向局部代理顶点的代理边,并由这些代理边把局部图信息汇聚到局部代理顶点。由此得出的结论是:GVU能够在不依赖其他GIG顶点的情况下充分编码每个内部图的结构与属性信息,为后续跨图交互奠定局部表示基础。
4.2.2 Global-level GIG Sample Updating (GGU) Module
GGU负责在不同GIG顶点之间交换信息。局部代理顶点先经由GIG边向相邻GIG顶点的全局代理顶点发送消息,全局代理顶点聚合这些外部信息后,再通过另一组代理边将全局上下文反馈给其内部图中的部分图顶点。该模块得出的结论是:通过代理顶点和GIG边的中介机制,模型能够显式建模图间关系,并使每个内部图获得全局上下文感知能力,而无需在不同图之间直接建立大规模稠密连接。
4.3 GIG output layer
输出层延续GVU+GGU的结构,但进一步对图边与未直接连接全局代理顶点的图顶点进行补充更新,使最终输出的每个内部图同时融合局部结构信息与跨图上下文信息。作者强调,该层使所有图顶点和图边都完成局部—全局联合更新。
4.4 Model complexity analysis
复杂度分析表明,GSG层的主要开销来自代理顶点初始化、余弦相似度计算与GIG边构建;而隐藏层与输出层的复杂度取决于所继承的具体GNN更新函数。作者指出,尽管GIG结构更复杂,但其运行代价在实践中并未显著高于同类标准GNN。
5 Experiment
实验部分从真实多图数据与通用图分析两方面验证模型有效性。
5.1 Datasets
论文共评测16个数据集,其中包括12个图基准数据集与4个天然GIG数据集。前者覆盖图分类、图回归、节点分类与链路预测任务;后者包括PeMSD7(M)、PeMSD7(L)交通预测,以及NTU RGB+D的X-Sub、X-View骨架动作识别。
5.2 Implementation details
实验中,作者分别以GatedGCN、GAT、GCN、DeeperGCN、STGCN、CTR-GCN等模型作为GVU与GGU中的基础更新器,说明GIG具有良好的可插拔性与兼容性。各任务沿用原始基线的训练配置与评价指标,以保证比较公平。
5.3 Comparison with state-of-the-art methods
该部分给出了核心实验结论。首先,在相同边/点更新函数下,GIG版本系统性优于原始GNN,说明性能提升主要来自“图作为顶点表示”和“图间关系建模”,而非仅仅来自参数增加。其次,特征可视化结果显示,GIG学到的表示具有更好的类间分离性。
5.3.1 Evaluation on real-world datasets
在交通预测任务上,GIG-STGCN与GIG-CTR-GCN在PeMSD7(M)和PeMSD7(L)上于15、30、45分钟预测范围内均获得最佳或次佳表现,相比原始STGCN和CTR-GCN取得显著误差下降,说明GIG能够同时捕获每个时间片内部的空间依赖与时间片之间的复杂时序关系。
在人体骨架动作识别任务上,GIG-ST-GCN相对ST-GCN在两个子集均有明显提升,GIG-CTR-GCN则进一步刷新结果。可视化显示,GIG更能将注意力分配到动作判别相关的关键关节,并兼顾各帧整体动态,表明其更有效地建模了帧内骨架结构与帧间长期关系。
5.3.2 Evaluation on the generic graph analysis datasets
在12个通用图分析任务上,多样本设定下的GIG在11/12个数据集上达到最优;单样本设定下也在9/12个数据集上取得最优,并持续明显优于对应基线。作者据此认为,即使在普通图任务中,将多个图组成GIG样本并显式学习图间关系,也能带来可观收益。
5.4 Ablation Studies
消融研究进一步验证了各组成模块的必要性。
在模块作用分析中,同时使用GVU与GGU的完整模型优于仅使用单一模块的变体,也优于将所有顶点和边简单合并为一个大图直接处理的方案,表明局部—全局双阶段设计优于朴素整图建模。
在代理边数量、代理边连接策略、GIG边构造策略、本地代理初始化策略、GIG隐藏层数量、GVU与GGU先后顺序、每个GIG样本中GIG顶点数量、测试阶段图分组策略等实验中,模型性能总体稳定,说明GIG对超参数与构图方式具有较强鲁棒性。尤其是图分组与批大小变化对性能影响较小,证明模型并不依赖某种特定输入组织形式。
讨论部分指出,本研究的重要意义在于提出了一种新的图学习范式:不再将复杂对象预先压缩为向量顶点,而是允许顶点本身携带图结构,从而把图神经网络的建模层级向上扩展一级。该设计既能服务于天然多图场景,也能增强通用图分析任务中的跨样本关系建模能力。实验结果显示,该框架在不同任务、不同基础GNN、不同构图策略下都具有稳定增益,因此兼具理论新意与方法通用性。
研究结论可译为:本文提出了一种新型GIG网络,可处理顶点由图而非向量或单一数值表示的图式数据(即GIG样本),从而能够有效分析真实世界多图数据或一批图样本。该框架还允许从现有GNN中灵活定制顶点/边更新函数。实验结果表明:(i)GIG在16个基准数据集中的15个上取得了最先进性能;(ii)该方法对其主要变量具有鲁棒性,例如代理边连接策略、GIG边连接策略、代理顶点初始化策略以及GIG隐藏层数量等,这验证并强调了其泛化能力,即GIG较易部署;(iii)所提出的GVU与GGU模块能够有效学习每个图内部与图间关系中的任务相关互补信息;(iv)为每个局部代理顶点连接更多图顶点、为每个全局代理顶点纳入更多GIG顶点,或增加更多GIG层,并不保证性能绝对提升,说明GIG性能在较大程度上并不依赖模型复杂度;(v)当改变GVU与GGU的执行顺序时,GIG的性能总体保持稳定。论文同时指出,其主要局限在于GSG层仍需要额外的任务/数据依赖型图表示转换步骤,以将真实数据中的多个非图对象或帧转化为一组GIG顶点;此外,尽管实际运行时间并未明显高于标准GNN,但更优性能仍伴随着相对较高的计算复杂度。未来工作将聚焦于开发更通用的图表示学习模块以替代额外转换步骤、降低模型复杂度,并在更多相关任务与数据上验证GIG。