ICLR2021 | 初探GNN的表示能力

多种图神经网络(GNN)在图结构数据的广泛应用。本文作者提出了一个理论框架实现比较这些 GNN 架构的表达能力。首次证明了GNN 的函数逼近保证，为更好地理解其泛化能力铺平了道路。论文的理论结果针对两类 GNN 框架：一类是不变图神经网络(invariant GNNs)，用于计算图级别嵌入，输入图的节点的排列变化不影响输出结果；另一类是同变图神经网络(equivariant GNNs)，用来计算节点嵌入，输入的排列变化会影响输出；论文表明FGNN 是迄今为止对给定阶数张量提出的表达能力最强的架构。实验在二次分配问题上验证了效果，达到比现有算法更好的平均性能。