May, 2024

具有实数和浮点数的循环图神经网络的逻辑特征

PDF
TL;DR对于具有浮点数和实数的循环图神经网络，我们给出了两种情况下的精确逻辑特征，对于浮点数，与循环 GNN 匹配的形式是一种具有计数的基于规则的模态逻辑，而对于实数，我们使用适当的无限模态逻辑，也带有计数。此外，相对于在单调二阶逻辑（MSO）中定义的图属性，我们的无限和基于规则的逻辑的表达力是相等的，这意味着具有实数和浮点数的循环 GNN 在 MSO 可定义的属性上具有相同的表达力，并且说明对于这样的属性，实数循环 GNN 也是由（有限的！）基于规则的模态逻辑来特征化的。
graph neural networksrecurrent gnnsmodal logicfloating-point numbersexpressive power
发现论文，激发创造
  • 图神经网络中的逻辑推理能力评估

    本研究探讨使用关系学习算法如何进行逻辑推理，在设计了一套基于一阶逻辑的基准测试套件 GraphLog 后，我们使用图神经网络 (GNN) 来进行评估，并发现模型的泛化和适应能力强度受到训练中遇到的不同逻辑规则的多样性的影响。

    Mar, 2020

  • 关于聚合组合图神经网络推理的逻辑

    提出了一种模态逻辑，在其中计数模态出现在线性不等式中。将每个公式转换为等价的图神经网络（GNN）。证明了广泛类别的 GNN 可以高效地转换为公式，从而明显改进了关于 GNN 的逻辑表达能力的文献。证明了可满足性问题的 PSPACE 完备性。这些结果将常规逻辑方法和 GNN 及其属性的推理前景结合起来，尤其适用于 GNN 查询、等价性检查等应用。证明了这种自然问题可以在多项式空间内解决。

    Apr, 2024

  • 图神经网络在知识图谱推理中的逻辑表现力

    本文从逻辑表达式的角度对图神经网络进行了理论分析，实验结果验证了我们提出的实体标记方法的有效性，并揭示了基于标记技巧的最先进的方法为什么很有效。

    Mar, 2023

  • 图神经网络的逻辑

    本文旨在阐述图神经网络的表达能力可以通过组合 Weisfeiler-Leman 算法和有限变量计数逻辑来精确描述，这种对应关系甚至导致了高阶图神经网络与高维 WL 算法的相应。

    Apr, 2021

  • 校准和提升多关系和时间图上 GNN 的逻辑表达能力

    在这篇论文中，我们研究了图神经网络的逻辑表达能力，特别是其作为多关系图上的布尔节点分类器的能力，并提出了一种简单的图转换技术来增强图神经网络的表达能力。我们还将研究扩展到了时间图上，并通过实验证明了我们的发现。

    Nov, 2023

  • 多项式激活函数的图神经网络具有有限表达性

    图神经网络的表达能力可以完全用合适的一阶逻辑片段来描述。本文通过证明 GC2 查询不能由具有多项式激活函数的图神经网络表示，证明了多项式和流行的非多项式激活函数之间存在分离关系。

    Oct, 2023

  • 一种用于解释某些图神经网络的模态逻辑

    该论文提出了一种包含线性不等式中计数模态的模态逻辑，证明了每个公式可以转化为等价的图神经网络（GNN），也证明了每个 GNN 可以转化为公式，说明可满足性问题是可判定的，并讨论了一些 PSPACE 内的变种。

    Jul, 2023

  • 图神经网络的逻辑精炼

    我们提出了一种基于逻辑的可解释模型，用于学习图形，并通过图神经网络（GNN）提炼该模型的算法。我们通过决策树模型以及扩展的二阶逻辑（C2）从 GNN 中提炼可解释的逻辑分类器，测试结果表明在可被 C2 表达的情况下，我们的方法优于 GNN。

    Jun, 2024

  • 基于图神经网络的高效概率逻辑推理

    本研究探讨了 Markov 逻辑网络和图神经网络的组合，并使用图神经网络进行 MLN 中的变分推理。研究提出了一种名为 ExpressGNN 的 GNN 变体，并通过多个基准数据集的广泛实验表明，ExpressGNN 在有效和高效的概率逻辑推理方面具有领先优势。

    Jan, 2020

  • 关于单调最大求和 GNN 和 Datalog 的关系

    本文主要研究基于图神经网络（GNN）的数据转换，并且分析了 GNN 的表达能力，提出一个处理 GNN 的标准编码，并且针对单调的最大 - 总和 GNN 和最大 GNN，证明了它们具有一定的表达能力，这些发现可以为进一步研究提供重要理论指导。

    May, 2023