摘要
近年来，图神经网络（GNNs）作为一种强大的神经架构，能够在监督的端到端方式下学习节点和图的向量表示。迄今为止，图神经网络仅通过经验评估进行了测试——显示出有希望的结果。本文从理论角度研究了图神经网络，并将其与一维韦斯费勒-莱曼图同构启发式算法（$1$-WL）进行了关联。我们证明了图神经网络在区分非同构（子）图方面具有与$1$-WL相同的表达能力。因此，这两种算法也存在相同的不足之处。基于此，我们提出了一种图神经网络的泛化形式，即$k$-维图神经网络（$k$-GNNs），该方法可以考虑多尺度下的高阶图结构。这些高阶结构在社交网络和分子图的特征描述中起着至关重要的作用。我们的实验评估不仅验证了我们的理论发现，还证实了高阶信息在图分类和回归任务中的有效性。
代码仓库
chrsmrrs/k-gnn
官方
pytorch
GitHub 中提及
基准测试
| 基准 | 方法 | 指标 |
|---|---|---|
| graph-classification-on-imdb-b | k-GNN | Accuracy: 74.2% |
| graph-classification-on-imdb-b | 3-WL Kernel | Accuracy: 73.5% |
| graph-classification-on-imdb-m | 1-WL Kernel | Accuracy: 51.5% |
| graph-classification-on-imdb-m | k-GNN | Accuracy: 49.5% |
| graph-classification-on-mutag | k-GNN | Accuracy: 86.1% |
| graph-classification-on-mutag | Graphlet Kernel | Accuracy: 87.7% |
| graph-classification-on-nci1 | k-GNN | Accuracy: 76.2% |
| graph-classification-on-nci1 | WL-OA Kernel | Accuracy: 86.1% |
| graph-classification-on-proteins | Shortest-Path Kernel | Accuracy: 76.4% |
| graph-classification-on-proteins | k-GNN | Accuracy: 75.9% |