paperbot · PL 论文追踪

全部论文 待读 收藏

P2 The Logic of Graph Neural Networks

图神经网络的逻辑
LICS 2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)2021匹配度 1/10 · 该论文研究图神经网络的逻辑刻画与表达能力（有限变量计数逻辑、Weisfeiler-Leman 算法），属于逻辑与机器学习理论交叉，但未涉及静态分析、程序分析、LLM/Agent、浮点程序分析或贝叶斯程序分析等用户核心方向。引用 6 inbox
Martin Grohe
逻辑与自动机
crossref: 2026-09-12

AI 速览

一句话：用有限变量计数逻辑与 Weisfeiler-Leman 算法精确刻画图神经网络的表达能力。

本文探讨图神经网络（GNN）的表达能力刻画问题。GNN 是面向图上机器学习任务的深度学习架构。近期研究表明，GNN 的表达能力可被组合 Weisfeiler-Leman（WL）算法和有限变量计数逻辑精确刻画；这种对应关系还催生了与高维 WL 算法对应的高阶 GNN。本文旨在解释这些关于 GNN 的描述性刻画，阐明逻辑、WL 算法与 GNN 之间的深层联系，并说明高阶 GNN 如何从该理论框架中导出。文章属于理论阐释性工作，不涉及新的实验评估。

问题
如何精确刻画图神经网络（GNN）在图上机器学习任务中的表达能力。
方法
从描述复杂性视角，利用 Weisfeiler-Leman 算法与有限变量计数逻辑解释 GNN 的表达能力刻画，并讨论对应高阶 WL 的高阶 GNN。
评估
本文为理论解释性论文，不涉及实验评估，主要基于已有理论结果进行阐述。
原文摘要（Abstract）

Graph neural networks (GNNs) are deep learning architectures for machine learning problems on graphs. It has recently been shown that the expressiveness of GNNs can be characterised precisely by the combinatorial Weisfeiler-Leman algorithms and by finite variable counting logics. The correspondence has even led to new, higher-order GNNs corresponding to the WL algorithm in higher dimensions.The purpose of this paper is to explain these descriptive characterisations of GNNs.

链接与引用

DOI 原文 · PDF（开放获取） ·

BibTeX 
@inproceedings{paperbot6173,
  title = {The Logic of Graph Neural Networks},
  author = {Martin Grohe},
  booktitle = {LICS},
  year = {2021},
  doi = {10.1109/lics52264.2021.9470677}
}