通过图二连通性重新思考 GNN 的表达能力

ICLRJan, 2023

通过图二连通性重新思考 GNN 的表达能力

Rethinking the Expressive Power of GNNs via Graph Biconnectivity

Bohang Zhang, Shengjie Luo, Liwei Wang, Di He

TL;DR本文提出了一种基于图双连通性的表达能力度量方法，发现大多数常见 GNN 架构在此度量下缺乏表达能力，但 ESAN 框架具有可证明的表达能力。作者进一步引入 GD-WL 模型，该模型可通过 Transformer 与 Weisfeiler-Lehman 算法相结合来计算表达能力，并通过实验表明其在绝大多数数据集上效果显著优于现有 GNN 架构。

Abstract

Designing expressive graph neural networks (GNNs) is a central topic in learning graph-structured data. While numerous approaches have been proposed to improve GNNs in terms of the Weisfeiler-Lehman (WL) test, generally there is still a lack of deep understanding of what additional pow

graph neural networks expressive power biconnectivity metrics esan framework generalized distance weisfeiler-lehman

发现论文，激发创造

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

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

Jan, 2023

Weisfeiler--Lehman goes Dynamic: 分析图神经网络在属性和动态图上的表现能力

本文对静态无向同质图和动态图、属性图等不同类型的图中图神经网络（GNNs）的表达能力进行了理论分析，提出了适当的 1-WL 测试，并证明了 GNNs 与 1-WL 测试在区分动态图和属性图上具有相同的能力，且 GNNs 可以模拟 1-WL 测试，包括大多数实际应用中使用的静态无向同质图（SAUHGs）等。

Oct, 2022

关于图神经网络的表达能力

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

Jan, 2024

图神经网络的能力超出我们的想象

本研究提出一种使用特殊算法和线性代数工具来分析图神经网络 (GNNs) 的表征能力的方法，证明 NNG 可以优于 Weisfeiler-Lehman 算法，同时在图同构和图分类等数据集上进行充分实验证明了这种新型的 GNN 架构更具表达力的特点。

May, 2022

图神经网络的表达能力和逼近性质

使用张量语言以及 Weisfeiler-Leman 测试为模型分析提供了一种优雅的方法，通过索引和求和嵌套深度的简单分析得到了对 GNN 的分离能力的边界和某些类的普适性结果，并提供了一些提高 GNN 分离能力的见解。

Apr, 2022

超越 Weisfeiler-Lehman: 一个用于 GNN 表达能力的定量框架

基于同态表示的图神经网络（Graph Neural Networks）的表达能力及其在子图计数等实际需求方面的量化研究。

Jan, 2024

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

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

Jun, 2023

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

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

Aug, 2023

图形神经网络扩展的理论比较

本文研究和比较了不同的图神经网络扩展方法，包括基于更高阶 Weisfeiler-Leman 方法、对图中小子结构进行预处理、对图进行局部预处理和计算嵌入等方法，并通过一系列实例构造比较了这些方法的表达能力。

Jan, 2022

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

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

Aug, 2023