研究节点标识符如何影响图神经网络的表达能力。
How Expressive Are Graph Neural Networks in the Presence of Node Identifiers?
- 引入关键不变性概念，分析带唯一标识的图上可表达的结构查询
- 证明不同局部聚合方式的GNN在标识符存在时表达力提升
- 为理解实际应用中GNN的推理能力提供理论依据
图神经网络（GNNs）是处理图结构数据的主流机器学习模型，基于邻居的局部聚合机制。GNNs与逻辑系统密切相关，其表达能力与模态逻辑及带计数的有界变量逻辑相关。在许多实际场景中，图的节点特征充当唯一标识符。本文研究此类标识符对GNN表达能力的影响。我们提出了关键不变性表达力的新视角，受有限模型论中顺序无关可定义性启发：在具有唯一节点标识符的图上，哪些仅依赖于图结构的节点查询能被GNN表达？我们针对采用局部最大值或求和聚合的多种GNN类别给出了答案。
原文摘要 · Abstract (English)
Graph neural networks (GNNs) are a widely used class of machine learning models for graph-structured data, based on local aggregation over neighbors. GNNs have close connections to logic. In particular, their expressive power is linked to that of modal logics and bounded-variable logics with counting. In many practical scenarios, graphs processed by GNNs have node features that act as unique identifiers. In this work, we study how such identifiers affect the expressive power of GNNs. We initiate a study of the key-invariant expressive power of GNNs, inspired by the notion of order-invariant definability in finite model theory: which node queries that depend only on the underlying graph structure can GNNs express on graphs with unique node identifiers? We provide answers for various classes of GNNs with local max- or sum-aggregation.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。