Improving the Expressiveness of $K$-hop Message-Passing GNNs by Injecting Contextualized Substructure Information

图神经网络（GNN）已成为图形表示学习的事实标准，并在许多与图相关的任务中实现了最先进的性能；然而，已经证明标准GNN的表达能力最多等同于一维Weisfeiler-Lehman（1-WL）测试。最近，有一系列工作旨在增强图神经网络的表达能力。其中一系列工作旨在开发$K$-跳消息传递GNN，其中节点表示通过聚合来自节点不仅直接相邻而且在节点的$K$-跳内的所有邻居的信息来更新。另一系列工作利用子图信息增强表达能力，这被证明比1-WL测试更强大。在这项工作中，我们讨论了$K$-跳消息传递GNN的局限性，并提出了“子结构编码函数”，以提高任何$K$-跳消息传递GNN的表达能力。我们进一步注入了上下文化的子结构信息，以增强$K$-跳消息传递GNN的表达能力。我们的方法在$K$-跳图神经网络和1-WL子图GNN上的性能比以前的方法更强大，1-WL子图GNN是一种特定类型的基于子图的GNN模型，而且不比3-WL弱。从实证上来看，我们提出的方法为各种数据集设置了新的最先进性能或实现了可比较的性能。我们的代码可在\url{https://github.com/tianyao-aka/Expresive_K_hop_GNNs}上找到。

提升图神经网络的表达能力

通过引入子结构编码函数和上下文化子结构信息，提升K-hop消息传递图神经网络的表达能力

论文提出的方法在多个数据集上实现了新的最优性能，代码已经公开，可以进一步研究

当前有一些相关的工作，如K-hop消息传递图神经网络和1-WL子图GNN，但本文提出的方法被证明比之更有表达能力，不亚于3-WL