ICLR 2022｜基于子图到节点转换的子图表示学习

作者 | 李万相

审核 | 付海涛

今天给大家介绍韩国科学技术研究所Alice Oh教授团队发布在ICLR上的文章，《EFFICIENT REPRESENTATION LEARNING OF SUBGRAPHS BY SUBGRAPH-TO-NODE TRANSLATION》。本文提出了子图到节点（S2N）转换，这是一种有效学习子图表示的新方法。具体来说，给定全局图中的一组子图，通过将子图粗略地转换为节点来构造一个新图，并通过这种转换将子图级任务作为节点级任务执行，可以显著降低训练和推理中的内存和计算成本。实验表明，具有 S2N 转换模型更有效，而且不会显著降低性能。

1.摘要

目前已经开发了图神经网络(GNN)来学习节点、边和图的表示，最近提出的SubGNN是一种用于学习子图表示的专门架构，这种架构优于以前的模型；然而，它需要大量的内存和计算来学习子图中的结构和各种属性。

本文提出了“子图到节点（S2N）”转换，这是一种创建数据结构以有效解决子图级预测任务的新方法。S2N转换构造了一个新图，其节点是原始子图，其边是子图之间的关系，并使用GNN模型对转换图中的节点表示进行编码，通过从这些节点表示中执行节点级任务来获得子图级任务的结果。

例如，在一个知识图中，子图是疾病，节点是症状，边是基于医学领域知识的症状之间的关系，诊断任务的目标是预测疾病的类型。使用S2N转换可以制作一个新的疾病图，节点是疾病，边缘是它们之间的关系。

首先，S2N转换提供了一个小而粗的图，其中节点的数量减少到原始子图的数量，使得可以在GPU上加载大批量的子图并并行化训练和推理。其次，在编码转换图时有更广泛的模型可供选择，即使是简单的DeepSets和GCN也可以胜过最先进的模型。

本文对四个真实世界的数据集进行了实验，以评估S2N转换的性能和效率，证明了具有S2N转换的模型比现有方法更有效率，而没有显著的性能下降，甚至某些模型在四个数据集中的三个数据集中的表现都优于基线。

2.模型介绍

S2N转换模型如上图所示

2.1 S2N转换概述

S2N转换通过构建一个将原始子图概括为节点的新图来降低模型训练和推理中的内存和计算成本。如上图a所示，对于全局图G中的每个子图，在转换后的图中创建一个节点；对于G中两个闭合子图的所有对，在中的对应节点之间创建一条边。Tv和Te是中的节点和边的函数。S2N 转换图定义为：

2.2 S2N转换的详细设计

本文选择了直接的Tv和Te设计，使得转换成本可以忽略不计。对于Tv，本文使用了忽略子图内部结构的函数，将节点视为一个集合。对于Te，如果两个子图Si和Sj之间至少有一个公共节点，就建立一条边。它们定义如下：

在某些情况下，这种特殊的转换为现实世界的问题提供了比子图形式更直观的描述。例如对于健身社交网络（子图：用户，节点：锻炼，边：是否多个用户完成锻炼），如果他们完成相同的锻炼，它将被转换为连接的用户网络。该图直接表达了用户之间的关系，并遵循传统的方法来表达以用户为节点的社交网络。

2.3 S2N 转换图的模型

本文为S2N转换图提出了简单但强大的模型管道。由于节点是Si中的一组原始节点，首先使用集合编码器，其中F是表示的维度，以中的一组节点特征作为输入，生成的表示，即：

然后，给定节点表示，应用图编码器得到向量。对于的输入和输出，本文使用矩阵和：

对于，可以采用任何在节点之间执行消息传递的GNN，这种在转换图上的节点级消息传递类似于SubGNN中子图级的消息传递。

3.实验

3.1 数据集

本文使用了四个真实数据集，PPI-BP、HPO-Neuro、HPO-Metab和EM-User。任务是子图分类，其中节点V、边A和子图S在数据集中给出。

3.2 基线模型

本文使用当前最先进的子图分类模型作为基线：Sub2Vec、Graph-level GIN和SubGNN。 

3.3 实验结果

3.3.1 S2N转换图分析

上表总结了S2N转换前后的数据集统计数据，包括节点和边的同质性。除了HPO-Neuro，转换后的图的节点数和边数比原始图少。对于HPO-Neuro，它的边数是原始图的两倍，但节点数减少了。作者还发现它们是非同质的（低同质性），这意味着有许多不同类的连接节点。

本文为多标签数据集（HPO-Neuro）提出了多标签节点和边缘同质性：

3.3.2 S2N转换图结果

上表展示了了十次运行本文模型和基线模型的micro-F1得分的平均值和标准差。众所周知，LINKX-I和FAGCN在非同质图中表现良好，在16个案例中有12个的表现与最佳基线相当或更好。对于PPI-BP和HPO-Metab，一些模型甚至在统计显著性方面优于SubGNN。值得注意的是，所有S2N模型在PPI-BP中都优于SubGNN，后者具有相对较高的同质性。在大多数实验中，GCN和GAT的表现不如LINKX-I和FAGCN。

3.3.3 S2N转换效率

上图中展示了S2N模型和SubGNN在HPO-Neuro、HPO-Metab和EM-User上的参数数量、吞吐量（每秒子图）和延迟（每次前向传递的秒数）。首先，S2N 模型使用更少的参数并且比SubGNN更快地处理更多样本（即更高的吞吐量和更低的延迟），特别是在吞吐量方面，S2N模型在相同的时间内可以处理比 SubGNN多8到300倍的样本。其次，训练吞吐量高于S2N模型中的推理吞吐量，通常，与在SubGNN中一样，在推理步骤中吞吐量会增加，这不需要梯度计算，这是因为S2N模型在训练和推理样本之间使用消息传递，因此，他们计算训练和推理样本，推理阶段需要更多计算。最后，作为一般趋势的一个例外，GAT在HPO-Metab上的训练延迟高于SubGNN。

4.总结

本文提出了子图到节点（S2N）转换，这是一种有效学习子图表示的新方法。使用S2N创建了一个新图，其中节点是原始子图，边是子图之间的关系，并将子图级任务作为节点级任务执行。S2N转换显著降低了内存和计算成本，而不会降低性能。

该研究存在一定的局限性。首先，本文使用了简单的翻译函数，并没有深入研究它们，如何在翻译后的图中定义聚合特征和结构？其次，还不知道影响S2N转换性能的子图的属性，转换后可以学习子图的哪些属性？这些将作为未来的研究方向。

参考文献

https://openreview.net/forum?id=BgLaE-k6gc

--------- End ---------

感兴趣的读者，可以添加小邦微信（zhiyaobang2020）加入读者实名讨论微信群。添加时请主动注明姓名-企业-职位/岗位 或

姓名-学校-职务/研究方向。

- 历史文章推荐 -

【分子生成】

●深度学习在分子生成和分子性质预测中的应用