Sep, 2023

限制距离的民间传说 Weisfeiler-Leman GNNs 具备可证明的循环计数能力

PDF
TL;DR我们提出了一种新的 GNN 模型，$d$-DRFWL (2) GNNs，通过在原始图中对限制距离的节点对进行信息传递，避免了子图 GNN 模型中昂贵的子图提取操作，从而降低了时间和空间复杂度。实验证实了我们的理论，我们的模型在计算 3、4、5、6 环等循环结构时是迄今为止效率最高的 GNN 模型。
graph neural networkssubgraph gnns$d$-distance-restricted fwl(2) gnnscycle counting powermolecular tasks
发现论文，激发创造
  • 通过重新思考 Weisfeiler-Lehman 传说走向在 $O (n^2)$ 空间内任意表达的 GNNs

    本文提出了一种新的图神经网络的框架 $k$-FWL+，并探究其表达能力及其设计空间的灵活性，使用此框架设计的 N2-GNN 在 ZINC-Subset 和 ZINC-Full 两个数据集上显示了比之前最先进的结果更好的性能。

    Jun, 2023

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

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

    Feb, 2020

  • 邻居间通信：面向强大和可扩展的图神经网络

    提出了一种基于 1-WL 和邻居之间的边缘考虑的 NC-1-WL 算法，实现了图同构测试，提高了图神经网络的可表达性；进一步提出了 NC-GNN 框架作为 NC-1-WL 的可微分神经版本，能够在各种基准测试中实现出色的性能。

    Jun, 2022

  • Weisfeiler 和 Leman 的循环：图形表示学习的新层次结构

    介绍了一种新的图同构测试层次结构和相应的 GNN 框架，可以计算长度为 r+2 的环的数量，并且能够计算仙人掌图的同态数量，实验证明该框架在多个合成数据集上具有表达能力和计数能力，并在多个真实数据集上取得了最先进的预测性能。

    Mar, 2024

  • 关于 Weisfeiler-Leman 测试对图形模体参数的能力

    本文研究了图神经网络的表达能力与 Weisfeiler-Leman 测试的关联，提出了 WL 维度的精确特征，并给出了子图计数问题的 WL 维度的多项式时间算法，回答了之前的研究中的一个开放问题。

    Sep, 2023

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

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

    Jan, 2023

  • 可证明强大图网络

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

    May, 2019

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

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

    Jan, 2023

  • 技术报告：图神经网络进入语法领域

    本文提出一种新的 GNN 设计策略，利用无上下文语法生成矩阵语言 MATLANG，从而确保 WL 表达能力，子结构计数能力和谱属性。根据该策略，设计了语法图神经网络 G$^2$N$^2$，证明了其在边级上计算长度为 6 的环并能够达到带通滤波器，实验结果证实了理论结果。

    Mar, 2023

  • 有序子图聚合网络

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

    Jun, 2022