提出统一框架，量化GNN计数同态的能力。
Fine-Grained Expressive Power of Weisfeiler-Leman: A Homomorphism Counting Perspective
- 设计通用图神经网络框架GFWL，支持灵活表达。
- 可算法化判断任意GNN类的同态计数能力。
- 适合研究模型表达力或自动化设计GNN者。
图神经网络（GNN）计数同态的能力被视作衡量其表达力的精细指标。尽管已有研究探讨特定GNN族的同态计数能力，但缺乏一个简洁统一的分析框架。本文首先提出广义民间韦斯费勒-莱曼（GFWL）算法作为强大GNN的灵活设计基础，进而构建理论框架，可算法化确定任意GNN类别在GFWL设计空间内的同态计数能力。由于该设计空间足够大，涵盖几乎所有已知强大的GNN，本成果大幅扩展了现有工作，有望应用于GNN模型设计的自动化。
原文摘要 · Abstract (English)
The ability of graph neural networks (GNNs) to count homomorphisms has recently been proposed as a practical and fine-grained measure of their expressive power. Although several existing works have investigated the homomorphism counting power of certain GNN families, a simple and unified framework for analyzing the problem is absent. In this paper, we first propose \emph{generalized folklore Weisfeiler-Leman (GFWL)} algorithms as a flexible design basis for expressive GNNs, and then provide a theoretical framework to algorithmically determine the homomorphism counting power of an arbitrary class of GNN within the GFWL design space. As the considered design space is large enough to accommodate almost all known powerful GNNs, our result greatly extends all existing works, and may find its application in the automation of GNN model design.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。