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

AAAIFeb, 2023

Learning to Count Isomorphisms with Graph Neural Networks

Xingtong Yu, Zemin Liu, Yuan Fang, Xinming Zhang

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

Abstract

subgraph isomorphism counting is an important problem on graphs, as many graph-based tasks exploit recurring subgraph patterns. Classical methods usually boil down to a backtracking framework that needs to navigate a huge search space with prohibitive computational costs. Some recent s

subgraph isomorphism counting graph neural networks edge-centric message passing graph adaptation benchmark datasets

发现论文，激发创造

神经子图同构计数

本文研究了一个新的图学习问题：学习计算子图同构，提出了一种学习框架，通过增加不同的表示学习架构和迭代地注意图案和目标数据图来记住全局计数的子图同构，通过实验结果表明，基于学习的子图同构计数可以在线性时间内计算大型模式和数据图，而且与传统算法 VF2 相比，可以将速度提高 10-1,000 倍。

Dec, 2019

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

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

Jun, 2020

使用双重信息传递的图卷积网络进行子图同构计数和匹配

本文提出一种基于边 - 顶点转换和对偶图同构性质的双重消息传递神经网络 (DMPNNs) 模型，用于在异步方式下加强子结构表示学习，适用于子图同构计数和匹配以及无监督节点分类任务。大量实验在合成和真实异构图中展示了 DMPNNs 结合节点和边表示学习的鲁棒性能，代码可在给出的网址中获取。

Dec, 2021

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

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

Feb, 2020

基于图核的子图同构计数方法研究

利用表示学习技术，我们研究了图内同构数量计算问题并探索了图核心技术在此问题中的潜力，通过综合分析，我们提升了图核心算法的效果，并展示了广泛实验的结果。

May, 2024

图神经网络的同态计数：基础方面的研究

图神经网络是一种用于学习图上不变函数的架构。本研究证明了现有方法中存在的不足，并提出了一种更精细化的方法，通过整合目标模式中所有结构的同构计数，实现了更加具有表达能力的架构，而不增加额外的计算复杂度。我们在标准基准数据集上进行了一系列理论和实证验证。

Feb, 2024

IsoNN: 图表示学习与分类的同构神经网络

本文提出了一种名为同构神经网络（IsoNN）的新型模型，通过提取输入图与模板之间的图匹配同构特征来学习图表示，以消除节点顺序约束，并在广泛的基准数据集上进行了实验证明其在图分类任务中的有效性。

Jul, 2019

具有同态计数的结构节点嵌入

基于图同态计数的嵌入方法为机器学习提供了可解释性，通过捕捉局部结构信息创建强大的结构嵌入，可以用于各种下游任务，同时在实际应用中也具备计算高效性。

Aug, 2023

两层图神经网络

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

Jan, 2022

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

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

May, 2019