FoSR: First-order spectral rewiring for addressing oversquashing in GNNs
FoSR: First-order spectral rewiring for addressing oversquashing in GNNs
复制标题
DOI：
10.48550/arxiv.2210.11790
复制
发表时间：
2022-10
期刊：
影响因子：
--
通讯作者：
Kedar Karhadkar;P. Banerjee;Guido Montúfar
中科院分区：
文献类型：
--
作者：
Kedar Karhadkar;P. Banerjee;Guido Montúfar
图神经网络（GNN）能够通过沿图的边缘传递消息来利用图数据的结构。虽然这使得 GNN 能够根据图结构学习特征，但对于某些图拓扑来说，它会导致信息传播效率低下以及被称为过度挤压的问题。最近这与图的曲率和光谱间隙有关。另一方面，向消息传递图添加边可能会导致节点表示越来越相似，并出现过度平滑的问题。我们提出了一种计算高效的算法，该算法通过基于谱扩展系统地向图添加边缘来防止过度挤压。我们将其与关系架构结合起来，让 GNN 保留原始图结构并可证明防止过度平滑。我们通过实验发现，我们的算法在几个图分类任务中优于现有的图重新布线方法。
Graph neural networks (GNNs) are able to leverage the structure of graph data by passing messages along the edges of the graph. While this allows GNNs to learn features depending on the graph structure, for certain graph topologies it leads to inefficient information propagation and a problem known as oversquashing. This has recently been linked with the curvature and spectral gap of the graph. On the other hand, adding edges to the message-passing graph can lead to increasingly similar node representations and a problem known as oversmoothing. We propose a computationally efficient algorithm that prevents oversquashing by systematically adding edges to the graph based on spectral expansion. We combine this with a relational architecture, which lets the GNN preserve the original graph structure and provably prevents oversmoothing. We find experimentally that our algorithm outperforms existing graph rewiring methods in several graph classification tasks.