大规模随机图上消息传递神经网络的泛化分析

Feb, 2022

大规模随机图上消息传递神经网络的泛化分析

Generalization Analysis of Message Passing Neural Networks on Large Random Graphs

Sohir Maskey, Ron Levie, Yunseok Lee, Gitta Kutyniok

TL;DR研究了 MPNN 在图分类和回归中的泛化误差，表明 MPNN 的复杂度越高，泛化差距越大；同时，不仅训练样本数，而且图中平均节点数对泛化差距也有影响。从统一收敛结果导出泛化界限，表明在图上应用 MPNN 可以逼近离散化的几何模型上的 MPNN。

Abstract

message passing neural networks (MPNN) have seen a steep rise in popularity since their introduction as generalizations of convolutional neural networks to graph-structured data, and are now considered state-of-the-art tools for solving a large variety of graph-focused problems. We stu

message passing neural networks mpnns graph classification graph regression generalization error

发现论文，激发创造

混合图上的消息传递网络的泛化界限

研究了消息传递神经网络（MPNNs）的泛化能力，并给出了具体适用于具有规范化求和和平均聚合的 MPNNs 的泛化边界。在更现实和具有挑战性的情境下，通过分析简单的随机图、扰动的图标和稀疏图，得出结论表明，只要图形足够大，比训练集的大小复杂，MPNNs 仍然可以有效地泛化。

Apr, 2024

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

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

Apr, 2020

图神经网络的泛化和表征限制

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

Feb, 2020

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

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

Dec, 2022

图神经网络在均场区域的泛化误差

该研究提供了一个理论框架，用于评估图神经网络在过度参数化阶段中进行图分类任务的泛化误差，其中参数数量超过数据点数量。我们探索了两种广泛使用的图神经网络类型：图卷积神经网络和消息传递图神经网络。在该研究之前，过度参数化阶段对泛化误差的现有界限不具信息性，限制了我们对过度参数化网络性能的理解。我们的新方法涉及在平均场阶段内导出上界，用于评估这些图神经网络的泛化误差。我们建立了收敛速度为 $O (1/n)$ 的上界，其中 $n$ 为图样本数量。这些上界在具有挑战性的过度参数化阶段为网络在未知数据上的性能提供了理论保证，并且总体上有助于我们对它们性能的理解。

Feb, 2024

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

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

May, 2023

图神经网络的从局部到全局视角

该论文从局部到全局的角度，介绍了图神经网络的两种类型 —— 局部信息传递神经网络和全局图变换器，并对不变图网络的收敛特性进行了研究；连接局部信息传递神经网络和全局图变换器；使用局部信息传递神经网络实现了图缩减等全局建模中常用的子程序。

Jun, 2023

突破消息传递图神经网络的限制

本文研究了基于图传递的神经网络（MPNNs），通过在频域设计非线性的自定义滤波器函数并使用任意大的感受野进行掩膜，其理论上比 1-WL 测试显得更加强大，且实际上具有与现有 3-WL 模型同样的性能，同时仍保持局部化。通过本方法可以实现 LOD 更新机制和输出谱复杂性，从而在许多下游任务中达到先进水平。

Jun, 2021

一种基于 PAC-Bayesian 方法的图神经网络泛化界的研究

本文基于 PAC-Bayesian 方法推导出了两种主要的图神经网络（GCNs 和 MPGNNs）的泛化界，进一步显示节点最大度数和权重的谱范数支配了这两种模型的泛化界。

Dec, 2020

图神经网络在统计泛化中的多样视角

通过流形理论，分析在由流形样本构造的图上操作的图神经网络的统计泛化差距，研究了图神经网络在节点级和图级任务上的泛化差距。在训练图中节点数量增加时，泛化差距减小，从而保证图神经网络对流形上的未见点的泛化性能。通过多个真实世界数据集验证了我们的理论结果。

Jun, 2024