ICLRJun, 2020

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

PDF
TL;DR本文提出了一个理论框架，可以比较图神经网络架构的表达能力，证明了实用 GNN 的第一近似保证，FGNN 被证明是最具表现力的架构之一，在 Quadratic Assignment Problem 中的应用表明 FGNN 能够比现有的基于谱、SDP 或其他 GNN 架构的算法表现得更好。
graph neural networksexpressive powergeneralizationfolklore graph neural networksquadratic assignment problem
发现论文，激发创造
  • 关于图神经网络的表达能力

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

    Jan, 2024

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

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

    May, 2019

  • 图神经网络的表达能力：综述

    为了填补这一重要方向的空白，我们首次对不同形式定义下增强表达能力的模型进行了综述，具体而言，我们根据三个类别（即图特性增强、图拓扑增强和图神经网络架构增强）对这些模型进行了回顾。

    Aug, 2023

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

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

    Jan, 2023

  • 谱不变图神经网络的表达能力研究

    使用光谱特征的图神经网络（GNNs）已显示出有希望的结果，但由于特征向量的固有模棱两可性，这提出了一项基本挑战。已经提出了几种架构来解决这种模棱两可性，被称为光谱不变架构。其中几个著名的例子包括使用光谱距离、光谱投影矩阵或其他不变光谱特征的 GNNs 和图变换器。然而，这些光谱不变架构的潜在表达能力仍然不太清楚。本研究的目标是在使用光谱特征时获得深入的理论理解可获得的表达能力。我们首先介绍了一种用于设计光谱不变 GNNs 的统一传递信息框架，称为特征空间投影 GNN（EPNN）。全面的分析表明，EPNN 本质上统一了所有先前的光谱不变架构，因为它们要么严格不可表达，要么与 EPNN 等价。还建立了不同架构之间的细粒度表达层次结构。另一方面，我们证明了 EPNN 本身被一种最近提出的子图 GNNs 类所约束，这意味着所有这些光谱不变架构严格不可表达 3-WL。最后，我们讨论了结合更具表达能力的 GNNs 时是否可以通过使用光谱特征来获得额外的表达能力。

    Jun, 2024

  • 近似等变图网络

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

    Aug, 2023

  • 不变量和等变量的经典与量子图神经网络比较

    机器学习算法、图神经网络、量子计算、等变图神经网络和二元分类任务是本文的关键词和研究主题。

    Nov, 2023

  • 图神经网络的等变多项式

    本研究介绍了一种基于图神经网络 (GNN) 计算等变多项式的表达能力层级方法，并提出了一种新的具有更具体指导意义的算法工具来评估 GNN 表达能力。同时，通过增加多项式特征或其他操作 / 聚合的方法，提高了 GNN 架构的表达能力，实现了在多个图形学习基准中的最新结果。

    Feb, 2023

  • 图神经网络表达能力调查

    本综述通过介绍图神经网络及其理论局限性，全面概述了图神经网络模型的表现能力及其改进版。

    Mar, 2020

  • 图同构测试与 GNN 函数逼近的等价性研究

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

    May, 2019