Mar, 2024

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

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

    对图神经网络进行研究，通过看其在无穷大层神经元的情况下的渐进行为，探讨了 GCNs 的表达能力，发现 GCNs 的表达能力与其底层图的拓扑信息相关，提供了一种基于权值归一化的方法，增强了真实数据下 GCNs 的性能。

    May, 2019

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

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

    May, 2023

  • 灵活表示多模块图神经网络以实现更好的泛化

    本文研究了图神经网络的可扩展性和推广性，并提出了灵活的 GNNs 框架，通过多种节点更新函数和内部循环优化，使网络能够灵活适应新图并在多项推理任务中提高泛化能力。

    Sep, 2022

  • 图神经网络的稳定性属性

    研究了拓扑结构变化对图神经网络输出的影响，证明了使用积分 Lipschitz 过滤器的图卷积与相应非线性混合效应的组合可以实现稳定性和高频信息的判别力，解释了 GNNs 卓越性能的原因。

    May, 2019

  • 使用近似梯度下降学习图神经网络

    该论文提供了第一个针对具有一个隐层节点信息卷积的图神经网络（GNN）的可证明有效的学习算法，并开发了一种综合性框架来设计和分析 GNN 训练算法的收敛性。提出的算法适用于各种激活函数，包括 ReLU，Leaky ReLU，Sigmoid，Softplus 和 Swish，并对样本复杂度进行了特征化。数值实验进一步验证了理论分析。

    Dec, 2020

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

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

    Dec, 2018

  • 图神经网络在不必要的情况下使用图

    图神经网络在图数据上学习的支配方法中，普遍存在过拟合图结构的现象，本研究通过对不同图分布进行分析，提出了一种理论解释和图编辑方法，以减轻图神经网络对应该被忽略的图结构的过拟合问题，并在多个基准测试中验证了该方法的有效性。

    Sep, 2023

  • 使用循环图神经网络学习图算法

    针对图状数据的学习问题，该研究提出了一种基于递归架构的图神经网络算法，其关键在于使用跳过连接、状态规则化和边缘卷积等三种技术以实现对小型图问题的端到端学习及大规模图问题的推广。实验证明该算法具有较高的推广能力。

    Dec, 2022

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

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

    Dec, 2022

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

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

    Oct, 2018