混合图上的消息传递网络的泛化界限
研究了 MPNN 在图分类和回归中的泛化误差,表明 MPNN 的复杂度越高,泛化差距越大;同时,不仅训练样本数,而且图中平均节点数对泛化差距也有影响。从统一收敛结果导出泛化界限,表明在图上应用 MPNN 可以逼近离散化的几何模型上的 MPNN。
Feb, 2022
本文基于 PAC-Bayesian 方法推导出了两种主要的图神经网络(GCNs 和 MPGNNs)的泛化界,进一步显示节点最大度数和权重的谱范数支配了这两种模型的泛化界。
Dec, 2020
本研究关注图神经网络的本质问题:无法仅仅依靠局部信息计算多个重要的图形特征;同时提出了信息传递图神经网络的第一个数据相关泛化界限,这一分析专门考虑了 GNN 局部置换不变性,该边界比现有的基于 VC 维度的 GNN 保证要紧密,与循环神经网络的 Rademacher 界限相当。
Feb, 2020
本文将图上定义的神经网络呈现为信息传递神经网络(MPNN),通过研究不同类别的这些模型的区别能力,探讨它们的识别能力,研究传统的图神经网络和卷积图神经网络对顶点进行特征标注的能力的界限,并使用 Weisfeiler-Lehman 算法对 MPNNs 的区分能力进行了上下界的研究。
Apr, 2020
该研究提供了一个理论框架,用于评估图神经网络在过度参数化阶段中进行图分类任务的泛化误差,其中参数数量超过数据点数量。我们探索了两种广泛使用的图神经网络类型:图卷积神经网络和消息传递图神经网络。在该研究之前,过度参数化阶段对泛化误差的现有界限不具信息性,限制了我们对过度参数化网络性能的理解。我们的新方法涉及在平均场阶段内导出上界,用于评估这些图神经网络的泛化误差。我们建立了收敛速度为 $O (1/n)$ 的上界,其中 $n$ 为图样本数量。这些上界在具有挑战性的过度参数化阶段为网络在未知数据上的性能提供了理论保证,并且总体上有助于我们对它们性能的理解。
Feb, 2024
本文研究了随机图模型上信息传递图神经网络收敛于其连续对应物的情况,我们扩展了聚合函数的类别,并利用 McDiarmid 不等式提供了高概率的非渐进上界,最终得到了定量的收敛结论。
Apr, 2023
本文研究了图神经网络的可扩展性和推广性,并提出了灵活的 GNNs 框架,通过多种节点更新函数和内部循环优化,使网络能够灵活适应新图并在多项推理任务中提高泛化能力。
Sep, 2022
本文针对以往工作的不足,引入了一种有意义的图信号相似度度量,提出了一种称为图信号切割距离的相似度度量,证明了 MPNN 可以在图信号度量空间中满足收敛性并得出了二次元情况下相似度度量的性质,进而提出了 MPNN 的泛化界和稳定性。
May, 2023
本文研究了基于图传递的神经网络(MPNNs),通过在频域设计非线性的自定义滤波器函数并使用任意大的感受野进行掩膜,其理论上比 1-WL 测试显得更加强大,且实际上具有与现有 3-WL 模型同样的性能,同时仍保持局部化。通过本方法可以实现 LOD 更新机制和输出谱复杂性,从而在许多下游任务中达到先进水平。
Jun, 2021