图神经网络能计算子结构吗？

Feb, 2020

Can Graph Neural Networks Count Substructures?

Zhengdao Chen, Lei Chen, Soledad Villar, Joan Bruna

TL;DR本文研究了一种基于图神经网络的图形子结构计数方法，探讨了各种常见图神经网络的表达能力和局限性，提出了一种新的本地化关系池化模型并在分子预测任务上取得了有竞争力的性能。

Abstract

The ability to detect and count certain substructures in graphs is important for solving many tasks on graph-structured data, especially in the contexts of computational chemistry and biology as well as social network analysis. Inspired by this, we propose to study the expressive power of graph neural networks (GNNs) via their ability to count attributed gra

graph neural networks substructure counting message passing neural networks 2-weisfeiler-lehman local relational pooling

发现论文，激发创造

通过子图同构计数提高图神经网络的表达能力

本论文提出了一种基于子结构编码的、具有拓扑感知的信息传递方案 —— Graph Substructure Networks，并通过理论分析和实验评估证明其优于 Weisfeiler-Leman 测试，并在分子图和社交网络等多个领域取得了最先进的结果。

Jun, 2020

使用图神经网络学习同构计数

本研究提出了一种名为 Count-GNN 的新型图神经网络模型，采用边为中心的消息传递方案和在图级别上进行的表示修正来解决子图同构计数问题，并在多个基准数据集上进行了广泛的实验证明其优越性能。

Feb, 2023

联合子图神经网络

本文提出了一种名为 Union Subgraph Neural Network 的图神经网络模型，通过注入从新类型的子结构中提取的邻居连接信息以有效地编码高阶连接性，该模型被证明在区分非同构图方面比 1-WL 更强大，并且在 17 个基准测试中表现出优异的性能，尤其是在现有模型的局部编码的基础上注入我们的局部编码，可以最多提高 11.09% 的性能。

May, 2023

有序子图聚合网络

本文提供了一种统一的方法来研究增强次图 GNN 的架构，包括理论框架和对子图增强 GNN 可表达性的已知结果进行扩展，同时研究了三种用于学习采样子图的方法，通过实验证明了数据驱动架构可以提高标准基准数据集的预测精度，同时减少计算时间。

Jun, 2022

嵌套图神经网络

这篇论文提出了 Nested Graph Neural Networks (NGNNs) 框架，通过将节点表示编码为子图而不是子树来表示整个图，从而比 1-WL 更强大地区分几乎所有 r 正则图，并且在基准数据集上表现出高度竞争性表现。

Oct, 2021

两层图神经网络

我们提出了一种被称为 Two-level GNN 的新型 GNN 框架，通过将子图级别信息与节点级别信息合并来克服现有 GNN 的局部置换不变性问题，并提出了一个基于动态规划算法的子图计数方法，实验证明 TL-GNN 优于现有 GNN，并实现了最先进的性能。

Jan, 2022

从星际到子图：运用局部结构意识提升任何 GNN

本文提出了一种称为 GNN-AK 的框架，旨在将任何 MPNN 提升为具有更高表达能力的模型，通过扩展 MPNN 中的局部聚合算法到更一般的子图模式，以提高实用性能，同时维持可扩展性；这种方法被证明比常见的 Weisfeiler-Lehman 同构测试更具表达能力，可以用于多个图机器学习任务中.

Oct, 2021

通过匿名行走图核函数理论上提升图神经网络性能

本文提出基于匿名行走和图核映射的 GSKN 图神经网络模型，理论证明其在区分图结构方面有更强的能力，并在实验证明了其胜过多个基线模型。

Apr, 2021

通过注入上下文化的子结构信息来提升 K - 跳消息传递 GNNs 的表现力

本研究探讨了基于图神经网络的 K-hop 传递模型的局限性，并提出了子结构编码函数，以提升其表达能力，并注入情境化子结构信息增强表达能力。实证结果表明，该方法在多个数据集上取得了新的最优表现或可比较的性能。

Jun, 2024

图神经网络的表达能力与对抗鲁棒性的视角

我们进行了第一个敌对鲁棒性研究，针对比传统的消息传递神经网络（MPNNs）更强大的图神经网络（GNNs）。具体而言，我们使用敌对鲁棒性作为一种工具，揭示了它们在理论上可能的表达能力与实际达到的表达能力之间的显著差距，并针对 GNNs 计算特定子图模式的能力，这是一种已建立的表达能力度量，将敌对鲁棒性的概念扩展到了该任务上。基于此，我们开发了有效的对抗攻击子图计数，并表明更强大的 GNNs 甚至无法适应对图结构的轻微扰动。此外，我们还展示了这种架构在超出分布的图上也无法计算子结构。

Aug, 2023