ICLRJul, 2019

图神经网络无法学习的内容：深度与宽度

PDF
TL;DR该论文研究了图神经网络的表达能力，发现了其在深度和宽度受限时可能会失去很大一部分功效，同时提出了一种使分布式计算的经典结果得以重用的新技术，给出了各种图论问题的下界。
发现论文，激发创造
  • 图神经网络的泛化和表征限制

    本研究关注图神经网络的本质问题：无法仅仅依靠局部信息计算多个重要的图形特征；同时提出了信息传递图神经网络的第一个数据相关泛化界限，这一分析专门考虑了 GNN 局部置换不变性，该边界比现有的基于 VC 维度的 GNN 保证要紧密，与循环神经网络的 Rademacher 界限相当。

    Feb, 2020

  • 消息传递神经网络中过度压缩的影响：宽度、深度和拓扑的影响

    通过理论分析，证明神经网络节点宽度可以缓解过度压缩问题，而神经网络深度则无法解决此问题。节点距离越远的高通勤时间节点之间出现过度压缩现象，而图形改写属于解决此问题的一类方法。

    Feb, 2023

  • 神经网络的表达能力：基于宽度的视角

    本文研究神经网络的宽度对其表达能力的影响，证明了 width-$(n+4)$ ReLU 神经网络是一种通用逼近器，同时存在一些无法用宽度为 $n$ 的神经网络进行逼近的函数，表现出相变现象，结果展示了深度对 ReLU 网络的表达能力比宽度更为有效。

    Sep, 2017

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

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

    Jan, 2024

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

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

    Jun, 2023

  • 图神经网络的细粒度表达能力

    该研究探讨了基于图神经网络的表达能力，提出了一种连续化的方法来反映图之间的相似程度并给出了各种拓扑特征的理论框架来描述基于树距离的图表达能力。

    Jun, 2023

  • 让我们达成一致：比较基于消息传递框架下的图卷积网络

    本文将图上定义的神经网络呈现为信息传递神经网络（MPNN），通过研究不同类别的这些模型的区别能力，探讨它们的识别能力，研究传统的图神经网络和卷积图神经网络对顶点进行特征标注的能力的界限，并使用 Weisfeiler-Lehman 算法对 MPNNs 的区分能力进行了上下界的研究。

    Apr, 2020

  • 图神经网络中池化的表达能力

    本文研究图神经网络中的池化操作的表现力问题，并介绍了一种可以全面维持 message-passing 层的表现力的池化操作设计原则，进而通过实验验证其在图同构检测上的效果。

    Apr, 2023

  • 图神经网络是内在良好的泛化器：通过建立 GNN 和 MLP 之间的联系进行深入探究

    本文通过引入中间模型 PMLP，揭示了 GNN 的性能提升主要源于其本质上的泛化能力，而非原理层面上的增强表现力。同时，本文发现 PMLP 表现与 GNN 相当，但训练效率更高。该发现为解析 GNN 相关问题提供了新的视角。

    Dec, 2022

  • 图形算法的神经执行

    通过在算法空间中训练 Graph Neural Networks 来解决基于图结构的问题，使用基于最大化的信息传递神经网络来实现离散决策，同时实现了任务迁移并提升学习效果。

    Oct, 2019