ICDE 2021 | 可微图神经网络架构搜索

点击上方“视学算法”，选择加"星标"或“置顶”

重磅干货，第一时间送达

作者 | 赵欢、姚权铭、涂威威

近年来GNN (Graph Neural Network)受到了很大的关注，越来越多GNN方法应用在节点分类(node classification)[1]，推荐系统(recommendation)[2]，欺诈检测(fraud dection)[3]等。不同的GNN方法最大的差别，在于邻居聚合函数 (neighbor aggregation, 又叫message passing)。但是面对多样的数据集和任务，没有任何一个方法能够取得SOTA方法。最近，斯坦福大学Jure教授团队在NeurIPS 2020的工作上也指出了这一点[4]。

基于此，我们结合自动化机器学习(AutoML) 来获取任务自适应的图神经网络。具体来说就是，设计了算法SANE来自动设计GNN中邻居聚合函数，在取得SOTA表现的同时解决了现有自动化设计GNN方案中的效率问题。

该论文已经被国际顶级数据挖掘会议ICDE 2021接收，大会于2021.4.19-2021.4.22召开，论文作者团队将在北京时间2021.4.21 23:00在线上做口头报告，欢迎大家届时关注。如有任何问题，欢迎联系zhaohuan@4paradigm.com。

论文地址：https://arxiv.org/abs/2104.06608

代码地址：https://github.com/AutoML-4Paradigm/SANE

1

背景介绍

GNN可以用信息交换(message passing)框架来统一[5]，如图1中(a)(b)所示，通过不断聚合邻居的消息来更新自身信息，不同的GNN方案之间最大的差距在聚合函数(aggregation function)，即下述公式中的。

现有的GNN方案，比如GCN[1]，GAT[6]，GIN[7]等，设计了不同的聚合函数来更新节点信息，JKNet[8]额外用了跳跃连接(skip-connection)来整合所有层的计算结果，从而增强节点信息的表达力。

现有的GNN结合神经网络结构搜索(neural architecture search，简记为NAS)的方案有GraphNAS[9]，Auto-GNN[10]等，都是基于强化学习的方案，耗时长效率低，并且这两者搜索空间(search space)极其相似。基于上述，如何快速高效搜索一个更具表达力的GNN模型就是一个大的挑战。

2

本次工作的方法

为了解决上述的问题，我们提出了新的解决方案SANE(Search to Aggregate NEighborhood)，其中包括一个小而精的搜索空间和一个可微搜索算法。

搜索空间的设计需要有足够的表达能力，同时考虑到计算资源，它需要小而精，基于此，SANE关注于搜索节点聚合函数(node aggregator) 和层聚合函数(layer aggregator)。如图1所示，以三层GNN为例，在每一层搜索节点聚合函数，并且搜索前三层和最后一层之间的跳跃连接及最后一层的层聚合函数。节点聚合函数，跳跃连接，层聚合函数的操作集合见表1。

图1：SANE算法示意图

表1：搜索空间

为了高效搜索，我们使用了可微的搜索算法。SANE的搜索空间可以构建成如图1(c)所示的有向无环图，首先使用softmax函数将离散空间松弛为连续空间

基于这个连续的搜索空间，节点v的信息过程可以记为:

基于节点v的信息，可以计算交叉熵并更新这个模型。

如下列公式所示，SANE需要更新网络结构 (network architecture)和网络权重(network weights)。具体更新过程见算法1

算法1：SANE的更新算法

该工作的贡献点在于：

1. 我们设计了基于NAS的SANE方法来设计GNN的结构，SANE提供的小而精的搜索空间可以覆盖现有的GNN的方案。
2. 为了解决现有的搜索GNN结构中遇到的效率问题，我们使用了可微的搜索算法，搜索效率相比现有的基于强化学习的方法提高两个数量级。
3. 我们在5个数据集上来验证了SANE的有效性和高效率，具体实验在下。
   
   

4

实验

该工作在四个常见的节点分类数据集和一个常用的数据库数据集上做了验证。

SANE的实验效果

如表2和3，SANE比现有的GNN方案和NAS方案的效果更好，并且图2展示了不同数据集上搜索出来的结构各不相同，这也说明了搜索针对每个数据集搜索GNN以及设计合理的搜索空间的重要性。

表2：SANE和基线方案的表现对比

表3：数据库任务

图2：SANE在不同数据集上搜索的GNN结构

如图3所示，相比较于现有的基于强化学习的方案和传统的基于随机搜索和贝叶斯搜索的方案，SANE用到的可微的搜索算法可以更快的搜索到高表现力的GNN模型。

图3：不同搜索算法的效率对比

消融实验（Ablation Study）

为了充分验证SANE设计的搜索空间和搜索算法，我们设计了一系列的消融实验：

如图4(a)所示，给搜索算法中加入一定的随机性，随着随机性的增长，效果在降低，这也验证了SANE使用的可微搜索算法除了带来高效性，也带来了效果的提升。

如图4(b)所示，SANE的实验都是基于三层的GNN，不同层的GNN搜索结果显示三层GNN是一个不错的选择。

图4：(a)随机性对准确率的影响；(b)不同GNN层数对准确率的影响

为了验证SANE的小而精的搜索空间，我们和GraphNAS的搜索空间做了一个对比。如表4，在使用同样的基于强化学习的搜索算法的情况下，使用SANE的搜索空间会取得更好的效果。

表4：比较GraphNAS和SANE的搜索空间对准确率的影响

最后SANE验证了多层线性感知机 (MultiLayer Perception，简记为MLP)作为节点聚合函数的影响，在每层GNN中，搜索MLP的层数和宽度(width, 即hidden size)，实验结果显示基于现有的节点聚合函数来搜索是必要的，MLP作为聚合函数会更有难度。

表5：将MLP作为节点聚合函数对准确率的影响

5

结语

本文提出了一种自动设计GNN结构的方法SANE，搜索空间包含节点和层的聚合函数两部分，这个小而精的搜索空间可以涵盖现有的GNN方案；可微的搜索算法提供了比现有搜索GNN方案更高效的搜索。我们设计了充分的实验来验证搜索空间和搜索算法这两部分，结果显示SANE比现有的GNN方案和搜索GNN的方案效果更好。

6

未来工作

在未来的工作中，我们打算深入探索NAS的其他算法在GNN中的应用，包括但不限于：不同搜索算法带来的效果提升，更多数据集和更多任务上的尝试。

致谢

感谢公司的支持，同时也感谢实习生卫岚宁参与baseline的实现。

引用文献

[1] Semi-supervised classification with graph convolutional networks. ICLR 2016.

[2] Graph convolutional neural networks for web-scale recommender systems. KDD 2018.

[3] Fakedetector: Effective fake news detection with deep diffusive neural network. ICDE 2020.

[4] Design Space for Graph Neural Networks. NeurIPS 2020.

[5] Neural message passing for quantum chemistry. ICML 2017.

[6] Graph attention networks. ICLR 2018.

[7] How powerful are graph neural networks?. ICLR 2019.

[8] Representation learning on graphs with jumping knowledge networks. ICML 2018.

[9] Graph neural architecture search. IJCAI 2020.

[10] Auto-GNN: Neural architecture search of graph neural networks. arXiv 2019.

[11] Simplifying Architecture Search for Graph Neural Network. CIKM-CSSA 2020

本组其他相关工作

本文探索了NAS在GNN聚合函数中的应用，除此之外，本组还有以下新工作：

• AutoSF: Searching scoring functions for knowledge graph embedding. ICDE 2020. (AutoSF)

• Simplifying Architecture Search for Graph Neural Network. CIKM-CSSA 2020

• Interstellar: Searching Recurrent Architecture for Knowledge Graph Embedding. NeurIPS 2020. (Interstellar)

• Efficient Relation-aware Scoring Function Search for Knowledge Graph Embedding. ICDE 2021. (ERAS)

• Role-Aware Modeling for N-ary Relational Knowledge Bases. WWW 2021. (RAM)

• Searching to Sparsify Tensor Decomposition for N-ary relational data. WWW 2021. (S2S)

点个在看 paper不断！