NeurIPS 2022 | 利用子图和结点的对称性提升子图GNN

22天前 58 阅读 ID:483
机器学习算法与自然语言处理
机器学习算法与自然语言处理

论文标题:

Understanding and Extending Subgraph GNNs by Rethinking Their Symmetries

论文链接:

http://arxiv.org/abs/2206.11140

代码链接:

https://github.com/beabevi/SUN

1.『论文介绍』

子图 GNN 能够将图建模成为子图的集合。时至今日,对于子图 GNN 结构的设计和其性质的理论分析方向仍有待探索。本文研究了子图方法中最重要的部分——基于结点的子图选择策略,如 ego-network/node marketing/node deletion。本文将子图表达能力的上界界定为 3-WL,并设计了新的子图 GNN 模型,称之为 SUN,在理论上统一了之前的子图模型,并在多个数据集上取得了更优越的表现。

2.『动机』

目前已有许多工作,旨在提升 GNN 的表达性。其中另辟蹊径在子图领域进行的研究也不在少数。这些方法通常是从原始输入图中提取出子图集 (bags),并在子图集上进行聚合等一系列操作,目的是对原图进行有效的表示。

从原图中挑选并提取子图有许多策略,选择不同的策略对模型的时间开销和性能表现存在影响。

尽管子图 GNN 拥有广阔的发展前景,我们仍缺少对其系统理解与理论分析。首先,理论上子图方法能够严格超越 WL test,但其 expressive power 的上界仍未可知。其次,在实践上,各种模型之间采取的信息传递和聚合策略是有差别的,是否存在对于信息传递规则的一个通用理解?在这两方面之上,我们既需要对于各种模型表达能力上界进行合理的标定,又希望能够在之后设计出更强大的子图 GNN。

基于以上,本文提出并解决了两个问题:1)这些子图 GNN 方法的表达能力上界在哪里;2)在子图集上进行的等变信息传递层之间的内在联系是什么。

本文的贡献主要有以下两点:

1. 对在子图集上进行操作的对称性集合提出了新的分析;

2. 提出了 SUN,对之前基于结点的子图 GNN 进行了合理的泛化。

3.『方法』

3.1 Subgraph GNNs

子图 GNN 按如下公式计算图 G 的表示:

3.2 基于结点的子图选择策略的symmetries

3.3 SubGNNs的上界

在本节中,本文证明了子图 GNN 的上界是 3-WL,原因是能被 3-IGN “inplement”:

3.4 A design space for subGNNs

3.5 SUN

4.『实验』

人工数据集上的任务是对图中子结构进行计数,SUN 在 4 个任务中的 3 个上表现都最好;真实数据集采用 ZINC-12k,用 MAE 进行衡量,SUN 取得了 SOTA 的结果。

  本文测试了当采取训练数据的一小部分时,模型能否仍有效,即模型的泛化能力如何。

5.『总结』

本文的工作对现有子图 GNN 的工作进行了统一和拓展,并界定了这些方法的 expressive power 上界是 3-WL。通过对 expressive power 在 1 & 3-WL 之间的模型进行系统研究,提出了子图 GNN 这一类模型的通用理论。在实验部分,本文额外研究了这些模型的泛化能力,其中 SUN 表现最好。

免责声明:作者保留权利,不代表本站立场。如想了解更多和作者有关的信息可以查看页面右侧作者信息卡片。
反馈
to-top--btn