ICMLMay, 2022

深入理解置换敏感的图神经网络

PDF
TL;DR本研究提出了一种通过置换组捕捉相邻节点间的成对相关性的高效置换敏感聚合机制，证明我们的方法比 2-WL 图同构测试更强大且不逊于 3-WL 测试，并证明我们的方法可以实现线性采样复杂度。多个数据集的综合实验证明了我们模型的优越性。
graph neural networkspermutation-sensitive aggregationweisfeiler-lehman testexpressivityneighboring nodes
发现论文，激发创造
  • 图同构测试与 GNN 函数逼近的等价性研究

    本研究通过引入 sigma 代数框架，将 GNN 的表现力和测试同构性的角度进行了比较，证明了不同类型的 GNN 的表现力在确定的条件下是等价的，提出了一种新的结构 Ring-GNN，该结构成功地区分了具有相同度数的非同构正则图，并在现实世界数据集上取得了良好的性能。

    May, 2019

  • 可证明强大图网络

    本文探讨了图同构、图神经网络的表达能力及其应用。作者提出了 k - 阶不变 / 本质等变图神经网络，并将此网络应用于图分类的任务中。实验表明，模型在数据集上表现的优异，证明了本文所提出的模型是有实用价值的。

    May, 2019

  • SwinGNN: 重新思考扩散模型中图的置换不变性问题

    本文提出了一种基于 SwinTransformers 的非不变扩散模型 SwinGNN，并识别出多种关键的训练和采样技术，显著提高了图像生成的样本质量；最后介绍了一种随机置换的后处理技巧，可将任何图生成模型转换为置换不变模型

    Jul, 2023

  • 近似等变图网络

    图神经网络 (GNNs) 和欧几里德卷积神经网络 (CNNs) 的等变性对称性不同，本篇论文侧重于探讨 GNNs 的主动对称性，通过对信号在固定图上的支持进行学习，将近似对称性形式化为图粗化，提出了一个偏差 - 方差公式来量化损失表达性与学习估计的规则性之间的权衡，实验证明，选择比图自同构群大但小于全排列群的适当大的群可以达到最佳泛化性能。

    Aug, 2023

  • 基于分数的生成模型生成置换不变的图

    本研究提出了一种置换不变的方法来建模图，并使用基于置换等变的多通道图神经网络来建模数据分布。 实验表明，该方法在学习离散图算法方面具有很好的能力，并在基准数据集上实现了比现有模型更好或相当的结果。

    Mar, 2020

  • 关于几何图神经网络表达能力的研究

    本研究提出了符合物理对称性的几何图卷积神经网络测试 GWL，并使用 GWL 研究了符合物理对称性的几何图卷积神经网络的表达能力，发现等变层扩展了局部邻域之外的几何信息，高阶张量和标量化使几何图卷积神经网络具有最大的表达能力。

    Jan, 2023

  • 不变层用于具有不同类型节点的图

    该论文研究了神经网络在输入排列不同时的不变性，针对异构图数据，提出了保留节点类型排列的线性层公式，实验表明该方法可以更有效地学习节点交互。并对张量层大小问题进行了探究，发现对于 $n$ 个节点的图数据，张量大小的上限为 $n$，优于之前的结果。

    Feb, 2023

  • 邻居间通信：面向强大和可扩展的图神经网络

    提出了一种基于 1-WL 和邻居之间的边缘考虑的 NC-1-WL 算法，实现了图同构测试，提高了图神经网络的可表达性；进一步提出了 NC-GNN 框架作为 NC-1-WL 的可微分神经版本，能够在各种基准测试中实现出色的性能。

    Jun, 2022

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

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

    Jun, 2020

  • 普适不变与等变图神经网络

    本文研究了一类具有单隐藏层的不变和等变网络，并证明了其新的普适性定理。首先，本文提出了一种以代数理论为基础的证明方式。其次，本文将这一结果扩展到等变网络中，该领域的理论研究相对较少。最后，本文的结果表明，相同的参数可以在具有不同规模的图上近似实现一定的函数。

    May, 2019