正交基提升等变图神经网络表达能力

摘要

图神经网络（GNN）模型已广泛应用于图结构数据学习。由于图学习任务需满足置换不变性要求，不变和等变线性层成为图神经网络的基本组件。先前研究（某机构等，2019b）提出了最大规模的不变与等变线性层集合，并开发了称为k-IGN的简单深度学习模型处理定义在k元节点组上的图数据。研究表明k-IGN在图表同构测试中的表达能力至少与k-Weisfeiler-Leman（WL）算法相当。然而不变层和等变层的维度分别达到第k个和第2k个贝尔数，这种高复杂度使得k≥3的k-IGN模型在计算上不可行。

本文证明采用更小维度的线性层即可实现相同表达能力。研究提出两组正交基构建线性层，每组仅需3(2^k-1)-k个基元素。基于这些线性层，开发了GNN-a和GNN-b神经网络模型，证明对于定义在k元组数据上的图数据，GNN-a和GNN-b在图表同构测试中分别实现k-WL算法和(k+1)-WL算法的表达能力。在基准数据集的分子预测任务中，采用所提出线性层的低阶神经网络模型展现出优于其他神经网络的性能。特别值得注意的是，二阶GNN-b和三阶GNN-a均具备3-WL表达能力，但使用的基集规模更小，计算时间显著少于已知神经网络模型。

[摘要][PDF][文献引用]