Feb, 2024

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

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

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

    Aug, 2023

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

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

    Feb, 2023

  • 基于同态性的图神经网络泛化

    通过分析图同态性的熵，我们提出了一种新的视角来研究图神经网络的泛化能力，并通过将图同态性与信息论度量联系起来，得出了适用于图和节点分类的泛化界限。通过我们提出的界限，能够捕捉到各种图结构的细微差别，包括但不限于路径、环和完全子图。通过图同态性，我们呈现了一个统一的框架，能够揭示广谱 GNN 模型的特性。通过在真实世界和人工合成数据集上观察到的泛化差距，我们验证了理论发现的实际可应用性。

    Mar, 2024

  • 同态映射是计算小子图的好基础

    介绍一类称为 Graph Motif Parameters 的图参数，介绍如何根据这个框架更快地计算固定大小的子图在大图中的个数，以及针对一类这样的参数进行问题的复杂度二分，其中包括用于颜色保留的子图计数。

    May, 2017

  • 利用同态性挖掘网络中的模式

    该研究提出了一种使用子图同态挖掘网络中的树模式的替代方法，具有良好的时间复杂度，同时解决了子图同构中的两个特殊问题。

    Oct, 2011

  • 神经子图同构计数

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

    Dec, 2019

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

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

    Jan, 2024

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

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

    Feb, 2020

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

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

    Jun, 2020

  • 图神经网络中超越同构性：现有限制与有效设计

    该研究通过节约和邻居嵌入、高阶邻居和中间表示的结合，设计出一种草图神经网络（H2GCN），并通过实验表明其在半监督节点分类任务下，具有比传统模型更高的预测准确率，尤其对于异质性网络（即一对连接的节点可能具有不同的类别标签和不同的特征）表现更出色。

    Jun, 2020