Sep, 2023

G4SATBench：使用图神经网络对 SAT 求解进行基准测试和推进

PDF
TL;DR通过建立一个全面的评估框架，我们提出了第一个用于 GNN-based SAT solvers 的基准研究，对各种预测任务、训练目标和推理算法的广泛范围的 GNN 模型进行了基准测试，结果展示了 GNN-based SAT solvers 的性能以及现有模型在学习策略方面的局限性。
graph neural networksboolean satisfiability problembenchmark studygnn-based sat solverslearning abilities
发现论文，激发创造
  • GraSS: 将图神经网络与专家知识结合，用于 SAT 求解器选择

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

    May, 2024

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

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

    Sep, 2023

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

    本研究将自我注意的图神经网络应用于基于 BP 的计数问题，成功地在产生概率接近于技术先进的问题解决器的解的同时，保证了模型性能的扩展性。

    May, 2022

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

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

    Apr, 2023

  • G2SAT：学习生成 SAT 公式

    本研究提出了 G2SAT 这一深度生成式框架，可以学习从输入公式集生成满足真实世界 SAT 实例特征的 SAT 公式，旨在扩展现有的数据集，为 SAT 求解器的性能提供优化方案。

    Oct, 2019

  • 能否通过 Graph Networks 的 Q-Learning 学习适用于 SAT Solver 的可推广分支启发式策略？

    本文介绍了使用图神经网络进行函数逼近的增强学习的 Graph-Q-SAT 分支启发式算法，该算法可用于解决 SAT 问题，并且在使用 MiniSat 求解器进行交互时可以减少解决 SAT 问题所需的迭代次数 2-3 倍。

    Sep, 2019

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

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

    Nov, 2022

  • 图神经网络基准测试

    本文介绍了 Graph Neural Networks (GNNs) 领域关于基准测试框架的应用，通过该框架，可对模型进行比较，并且探索新的 GNN 设计和洞见，其中，图形位置编码 (PE) 是该基准测试框架中引入的重要设计之一。

    Mar, 2020

  • 训练更深层次图神经网络的技巧：一项综合基准研究

    本研究提供了第一个公平、可重复的基准测试，重点研究了训练深度图神经网络中的技巧，并利用该测试在数十个代表性图数据集上进行了全面评估，证明了初始连接、标识映射、分组和批量归一化的有机组合实现了深度 GNN 在大型数据集上的最新成果。

    Aug, 2021

  • 大规模图训练的全面研究：基准测试和重新思考

    本文通过提供大规模图训练不同的架构和贴切的评估方法，在分析它们的优点和缺点后，介绍了一个名为 EnGCN 的新的集成训练方式。

    Oct, 2022