May, 2022

命题模型计数的图神经网络

PDF
TL;DR本研究将自我注意的图神经网络应用于基于 BP 的计数问题，成功地在产生概率接近于技术先进的问题解决器的解的同时，保证了模型性能的扩展性。
graph neural networkslogical reasoningpropositional model countingbelief propagationself-attentive gnn
发现论文，激发创造
  • G4SATBench：使用图神经网络对 SAT 求解进行基准测试和推进

    通过建立一个全面的评估框架，我们提出了第一个用于 GNN-based SAT solvers 的基准研究，对各种预测任务、训练目标和推理算法的广泛范围的 GNN 模型进行了基准测试，结果展示了 GNN-based SAT solvers 的性能以及现有模型在学习策略方面的局限性。

    Sep, 2023

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

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

    Apr, 2024

  • 信念传播神经网络

    介绍了一种参数化的运算符 BPNN，它可以操作因子图和广义 BP。通过训练 BPNN，可以比原始的 BP 更好地完成一些复杂的计数问题，并且可以更快地收敛于 Ising 模型。

    Jul, 2020

  • NSNet: 一个通用的神经概率框架用于可满足性问题

    介绍了一种名为 NSNet 的神经网络模型，通过使用一种新型的图神经网络 (GNN) 在潜在空间中对 BP 进行参数化，可以灵活配置以解决 SAT 和 #SAT 问题。

    Nov, 2022

  • 置信传播计数

    本文介绍了一种名为计数 BP 的新型 BP 算法，它利用了图模型中存在的对称性，通过构建压缩图模型的方式实现更高效的模型推理，在包括动态关系模型和布尔模型计数等多种人工智能任务中取得显著的效率提升。

    May, 2012

  • 基于图神经网络的概率图模型推理

    使用图神经网络作为一种有利于推断任务的推送算法，对于在循环密集的概率有向图上显著优于置信传播算法

    Mar, 2018

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

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

    Jan, 2020

  • 利用深度学习构建带性能界限的随机局部搜索 SAT 求解器

    利用图神经网络训练适用于布尔可满足性问题的 SLS 求解器，可显著提高性能，平均解决比例更高、步骤更少，具有性能保证。

    Sep, 2023

  • GraSS: 将图神经网络与专家知识结合，用于 SAT 求解器选择

    通过三分图表示的实例和异构图神经网络模型，我们提出了一种基于 GraSS 的自动 SAT 求解器选择方法，该方法使用了特定领域决策，如新的节点特征设计、图中子句的位置编码、针对三分图的 GNN 架构以及运行时间敏感的损失函数，通过广泛的实验，我们证明了这种组合对于七种最先进的求解器来说在回路设计基准测试和 2022 SAT 大赛 20 年纪念赛道的实例中都能提高运行时间。

    May, 2024

  • 基于 GNN 的 SAT 求解中的变量依赖问题解决

    AsymSAT 是一种基于 GNN 的架构，能够扩展 GNN-based 方法的解题能力，改善 SAT 问题求解的性能，并通过使用生成的相关预测来维护变量之间的依赖关系。

    Apr, 2023