图神经网络与算术电路

Feb, 2024

Graph Neural Networks and Arithmetic Circuits

Timon Barlag, Vivian Holzapfel, Laura Strieker, Jonni Virtema, Heribert Vollmer

TL;DR神经网络的计算能力与图神经网络 (GNN) 结构相对应，不仅局限于聚合 - 合并的 GNN 或其他特定类型，我们通过多样的激活函数与实数上的算术电路之间建立了精确的对应关系。在我们的结果中，网络的激活函数变成了电路中的门类型。我们的结果适用于常定深度电路和网络的各种常用激活函数，在统一和非统一的情况下都成立。

Abstract

We characterize the computational power of neural networks that follow the graph neural network (GNN) architecture, not restricted to aggregate-combine GNNs or other particular types. We establish an exact corres

neural networks graph neural network expressivity activation functions arithmetic circuits

发现论文，激发创造

多项式激活函数的图神经网络具有有限表达性

图神经网络的表达能力可以完全用合适的一阶逻辑片段来描述。本文通过证明 GC2 查询不能由具有多项式激活函数的图神经网络表示，证明了多项式和流行的非多项式激活函数之间存在分离关系。

Oct, 2023

关于图神经网络的能力与激活函数的作用

活动函数不同，图神经网络在两层迭代中可以区分两个非同构树的根节点，但是若网络的大小被限制，其区分能力将受到限制。

Jul, 2023

图神经网络的逻辑

本文旨在阐述图神经网络的表达能力可以通过组合 Weisfeiler-Leman 算法和有限变量计数逻辑来精确描述，这种对应关系甚至导致了高阶图神经网络与高维 WL 算法的相应。

Apr, 2021

关于图神经网络的表达能力

该论文概述了图神经网络的 “表达能力” 概念，并就图神经网络的设计选择提供了有价值的见解。

Jan, 2024

图神经网络的能力超出我们的想象

本研究提出一种使用特殊算法和线性代数工具来分析图神经网络 (GNNs) 的表征能力的方法，证明 NNG 可以优于 Weisfeiler-Lehman 算法，同时在图同构和图分类等数据集上进行充分实验证明了这种新型的 GNN 架构更具表达力的特点。

May, 2022

图神经网络与神经符号计算的结合：调查和展望

本文综述了图神经网络作为神经符号计算模型的应用现状和在多个领域中的关系，这反映了对改进人工智能系统的可解释性、解释性和信任度的需求。

Feb, 2020

图神经网络：方法和应用综述

本文介绍了图神经网络（GNNs）的设计管道，详细讨论了其各个组成部分的变体，对其应用进行了系统分类，并提出了四个开放性问题供未来研究。

Dec, 2018

图神经网络的能力有多强？

本文提出了一种理论框架来分析图神经网络的表达能力和限制，并阐述了如何有效地捕捉不同的图结构。通过提出的一个简单的架构，实验验证了理论的发现，并取得了最先进的性能。

Oct, 2018

计算机视觉中的图神经网络 —— 架构、数据集和常见方法

该研究整理并总结了关于应用于计算机视觉的基于图神经网络（GNNs）及其派生物（如 GAT、GCN 和 GRN）的方法的论文，从网络结构、数据集、以及与其他领域的关联等三个方面进行了详细阐述。

Dec, 2022

图神经网络输出几乎肯定是渐近常数

图神经网络（GNN）是用于各种图学习任务的主要架构。我们通过研究 GNN 概率分类器在从某个随机图模型中抽取的较大图上应用时的预测如何演变来呈现 GNN 表达能力的新视角。我们展示了输出收敛为常函数的现象，这个常函数上界了这些分类器能够统一表达的内容。这种收敛现象适用于包括最先进模型在内的广泛类别的 GNN，其中包括均值聚合和图转换器中的基于注意力的机制。我们的结果适用于包括（稀疏的）Erdős-Rényi 模型和随机块模型在内的广泛类别的随机图模型。我们通过实证验证了这些发现，并观察到即使在相对较小的图上，收敛现象已经显现出来。

Mar, 2024