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

Oct, 2018

How Powerful are Graph Neural Networks?

Keyulu Xu, Weihua Hu, Jure Leskovec, Stefanie Jegelka

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

Abstract

graph neural networks (GNNs) are an effective framework for representation learning of graphs. GNNs follow a neighborhood aggregation scheme, where the representation vector of a node is computed by recursively aggregating and transforming representation vectors of its neighboring node

graph neural networks representation learning expressive power graph classification discriminative power

发现论文，激发创造

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

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

May, 2022

图神经网络表达能力调查

本综述通过介绍图神经网络及其理论局限性，全面概述了图神经网络模型的表现能力及其改进版。

Mar, 2020

图神经网络的表达能力：综述

为了填补这一重要方向的空白，我们首次对不同形式定义下增强表达能力的模型进行了综述，具体而言，我们根据三个类别（即图特性增强、图拓扑增强和图神经网络架构增强）对这些模型进行了回顾。

Aug, 2023

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

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

Jan, 2024

GNNs 究竟学习了什么？探究其表征

本文研究了四种流行的图神经网络模型，探究了在没有节点属性可用的情况下这些模型所学习的节点表示中纯粹编码的图的哪些属性，并表明其中两个将所有节点嵌入同一特征向量中，而另外两个生成与输入图上的行走数量有关的表示。值得注意的是，在图的某一层 $k>1$，结构不相似的节点如果具有相同长度的行走次数，则可以具有相似的表示。我们在真实数据集上经验证实了我们的理论发现。

Apr, 2023

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

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

Dec, 2018

不变和等变图神经网络的表现能力

本文提出了一个理论框架，可以比较图神经网络架构的表达能力，证明了实用 GNN 的第一近似保证，FGNN 被证明是最具表现力的架构之一，在 Quadratic Assignment Problem 中的应用表明 FGNN 能够比现有的基于谱、SDP 或其他 GNN 架构的算法表现得更好。

Jun, 2020

路径神经网络：表现力强且准确的图神经网络

本文引入 Path Neural Network 模型来提高图表达的表达能力，实验证明该模型比 1-WL 算法更加强大，且在图分类和图回归任务中表现良好。

Jun, 2023

探索图神经网络的泛化理解

研究了图神经网络在泛化上的机制，建立了高概率边界和其对泛化差距和梯度的影响，得出结论和实验证据相符的新认识。

May, 2023

图表，卷积和神经网络：从图滤波器到图神经网络

本文利用图信号处理来表征图神经网络（GNNs）的表征空间，讨论了图卷积滤波器在 GNNs 中的作用，并展示了这类滤波器所建立的任何架构都具有置换等变性和对网络拓扑的稳定性的基本属性。然后，我们讨论了扩展了边变量和自回归移动平均图滤波器的 GNNs 以及它们的属性，并最终研究了在推荐系统和学习机器人群体的分散式控制器中使用 GNNs 的相关研究。

Mar, 2020