高阶图神经网络（Higher-Order GNNs）与效率的结合：稀疏Sobolev图神经网络（Sparse Sobolev Graph Neural Networks）

《IEEE Transactions on Signal and Information Processing over Networks》：Higher-Order GNNs Meet Efficiency: Sparse Sobolev Graph Neural Networks

　　本文提出基于稀疏索伯夫范数的S2-GNN，通过哈达玛德积保持图稀疏性，级联过滤器捕捉高阶关系，理论验证稳定性，并在节点分类、半监督学习等任务中表现优于现有GNNs。

　　

摘要：

图神经网络（GNNs）在模拟图中节点之间的关系方面展现出了巨大潜力，但对于大规模网络来说，捕捉更高阶的关系仍然是一个挑战。以往的研究主要尝试利用图中更高阶邻居的信息，这涉及到引入位移算子的幂次，如图拉普拉斯矩阵或邻接矩阵。这种方法在计算和内存需求方面存在权衡。基于图谱理论，我们发现了一个基本事实：拉普拉斯矩阵的正规化和哈达玛幂次在谱域中的表现相似。这一发现对于在GNNs中捕捉更高阶信息具有重要的意义，适用于节点分类和半监督学习等多种任务。因此，我们提出了一种基于图信号稀疏Sobolev范数的新型图卷积算子。我们的方法称为稀疏Sobolev GNN（S2-GNN），它通过使用矩阵之间的哈达玛积来保持图表示的稀疏性。S2-GNN利用具有递增哈达玛幂次的滤波器级联来生成多样化的函数集。我们从理论上分析了S2-GNN的稳定性，以证明该模型对可能的图扰动的鲁棒性。我们还对S2-GNN在图挖掘、半监督节点分类和计算机视觉任务中的表现进行了全面评估。在特定的用例中，我们的算法在性能和运行时间方面与最先进的GNNs相比表现出了竞争力。

引言

近年来，图表示学习及其应用受到了广泛关注[1]、[2]、[3]、[4]、[5]。值得注意的是，图神经网络（GNNs）作为卷积神经网络（CNNs）的强大扩展，已被成功应用于包括半监督学习[3]、聚类[6]、点云语义分割[7]、错误信息检测[8]和分子建模[9]等多个领域。