提出统一框架提升图神经网络表达能力，可涵盖多种现有模型。
Unifying approach to uniform expressivity of graph neural networks
- 用模板嵌入聚合构建通用图神经网络框架
- 证明该框架与特定逻辑表达力等价，理论更统一
- 适合研究图神经网络表达力的学者和算法设计者
图神经网络（GNN）的表达能力常通过与Weisfeiler-Leman（WL）算法及一阶逻辑片段的对应关系来分析。标准GNN仅能对邻域或全局信息进行聚合。为增强表达力，近年工作尝试引入子结构信息（如环计数、子图属性）。本文通过引入模板图神经网络（T-GNNs），形式化这一架构趋势：节点特征通过在指定图模板集合中有效模板嵌入上进行聚合来更新。我们提出对应的格状模板模态逻辑（GML(T)），以及基于模板的双模拟和广义WL算法。建立T-GNNs与GML(T)之间的表达力等价性，并提供统一分析GNN表达力的方法：证明标准AC-GNN及其近期变体均可视为T-GNNs的特例。
原文摘要 · Abstract (English)
The expressive power of Graph Neural Networks (GNNs) is often analysed via correspondence to the Weisfeiler-Leman (WL) algorithm and fragments of first-order logic. Standard GNNs are limited to performing aggregation over immediate neighbourhoods or over global read-outs. To increase their expressivity, recent attempts have been made to incorporate substructural information (e.g. cycle counts and subgraph properties). In this paper, we formalize this architectural trend by introducing Template GNNs (T-GNNs), a generalized framework where node features are updated by aggregating over valid template embeddings from a specified set of graph templates. We propose a corresponding logic, Graded template modal logic (GML(T)), and generalized notions of template-based bisimulation and WL algorithm. We establish an equivalence between the expressive power of T-GNNs and GML(T), and provide a unifying approach for analysing GNN expressivity: we show how standard AC-GNNs and its recent variants can be interpreted as instantiations of T-GNNs.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。