提出分层节点个性化GNN，能更好区分图结构，逼近同构判别极限。
Logical Expressiveness of Graph Neural Networks with Hierarchical Node Individualization
- 基于分层节点个性化机制，逐步增强模型表达能力。
- 在有界度图上，表达力等价于分级混合逻辑，可区分所有非同构图。
- 实验验证有效，优于传统GNN，尤其在含局部同态计数特征时。
我们提出并研究了分层邻域图神经网络（HEGNN），这是一种受图同构检测中个体化-细化范式启发的图神经网络（GNN）表达性扩展。HEGNNs推广了子图-GNN，并构成一系列越来越强的模型层级，在极限情况下可区分所有图的同构性。我们证明，在有界度图上，HEGNN节点分类器的区分能力等价于分级混合逻辑。这一刻画使我们能够将HEGNN的区分能力与高阶GNN、引入局部同态计数特征的GNN以及基于个体化-细化的着色精炼算法相联系。实验结果证实了HEGNN的可行性，并显示其在性能上优于传统GNN架构，无论是否包含局部同态计数特征。
原文摘要 · Abstract (English)
We propose and study Hierarchical Ego Graph Neural Networks (HEGNNs), an expressive extension of graph neural networks (GNNs) with hierarchical node individualization, inspired by the Individualization-Refinement paradigm for isomorphism testing. HEGNNs generalize subgraph-GNNs and form a hierarchy of increasingly expressive models that, in the limit, distinguish graphs up to isomorphism. We show that, over graphs of bounded degree, the separating power of HEGNN node classifiers equals that of graded hybrid logic. This characterization enables us to relate the separating power of HEGNNs to that of higher-order GNNs, GNNs enriched with local homomorphism count features, and color refinement algorithms based on Individualization-Refinement. Our experimental results confirm the practical feasibility of HEGNNs and show benefits in comparison with traditional GNN architectures, both with and without local homomorphism count features.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。