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

May, 2019

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

On the equivalence between graph isomorphism testing and function approximation with GNNs

Zhengdao Chen, Soledad Villar, Lei Chen, Joan Bruna

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

Abstract

graph neural networks (GNNs) have achieved much success on graph-structured data. In light of this, there have been increasing interests in studying their expressive power. One line of work studies the capability

graph neural networks expressive power permutation-invariant functions graph isomorphism ring-gnn

发现论文，激发创造

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

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

Jun, 2020

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

本研究提出了一种通过置换组捕捉相邻节点间的成对相关性的高效置换敏感聚合机制，证明我们的方法比 2-WL 图同构测试更强大且不逊于 3-WL 测试，并证明我们的方法可以实现线性采样复杂度。多个数据集的综合实验证明了我们模型的优越性。

May, 2022

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

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

May, 2019

近似等变图网络

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

Aug, 2023

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

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

Jan, 2023

通过图分割提升图神经网络的表达能力

图分区神经网络（GPNNs）是一种新颖的 GNN 架构，通过对图进行分区以及顶点集和子图之间的结构相互作用的探索，提高了 GNN 的表达能力，并在各种图基准任务中展示了超越现有 GNN 模型的卓越性能。

Dec, 2023

图神经网络与图增强型多层感知机比较

本文比较了多层图神经网络和一种被称为图增强多层感知器的简化替代品之间的表现，其中后者首先通过图上的某些多跳算子增强节点特征，然后以节点方式应用 MLP；并证明了 GA-MLP 具备适当算子的情况下，能像 Weifeiler-Lehman（WL）测试一样，理论和数值上能够区分几乎所有非同构图，但是 GA-MLP 与 GNN 之间在表达能力方面的差距随着深度呈指数增长，并且 GA-MLP 不能计算属性步行的数量，表明 GA-MLP 受其操作符族的选择限制比拥有更高学习灵活性的 GNN 更为受限，这在社区检测实验中也得到了证明。

Oct, 2020

图神经网络的细粒度表达能力

该研究探讨了基于图神经网络的表达能力，提出了一种连续化的方法来反映图之间的相似程度并给出了各种拓扑特征的理论框架来描述基于树距离的图表达能力。

Jun, 2023

可证明强大图网络

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

May, 2019

图神经网络在推荐领域的表现力如何？

本文提供了关于图神经网络在推荐系统中表达能力的全面理论分析，考虑了图同构、节点自同构和拓扑接近度等三个层面的表达能力指标，并引入了拓扑接近度指标来评估图神经网络对节点之间结构距离的捕捉能力，从而更好地满足推荐任务的目标。为了验证这一新指标对推荐性能评估的有效性，我们介绍了一种适用于该指标的无学习图神经网络算法，并进行了广泛的实验证明其可解释性在推荐任务中的表现，代码可在给出的链接中获得。

Aug, 2023