論文の概要: Structure based SAT dataset for analysing GNN generalisation

• arxiv url: http://arxiv.org/abs/2502.11410v1
• Date: Mon, 17 Feb 2025 03:49:25 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-18 14:09:46.958610
• Title: Structure based SAT dataset for analysing GNN generalisation
• Title（参考訳）: GNN一般化解析のための構造ベースSATデータセット
• Authors: Yi Fu, Anthony Tompkins, Yang Song, Maurice Pagnucco,
• Abstract要約: StructureSAT: 新しいサンプルを生成するためのコードとともに、キュレートされたデータセットを提供します。 我々は,構造グラフ特性の知識を活用することで,既存のGNN SATソルバにおける問題一般化の説明を支援することを目的とする。 我々は、GNNベースのSAT解法の研究者がより効果的で一般化可能なSAT解法を開発するのに役立つ、複数の今後の方向性を結論付けている。
• 参考スコア（独自算出の注目度）: 13.394698965947622
• License:
• Abstract: Satisfiability (SAT) solvers based on techniques such as conflict driven clause learning (CDCL) have produced excellent performance on both synthetic and real world industrial problems. While these CDCL solvers only operate on a per-problem basis, graph neural network (GNN) based solvers bring new benefits to the field by allowing practitioners to exploit knowledge gained from solved problems to expedite solving of new SAT problems. However, one specific area that is often studied in the context of CDCL solvers, but largely overlooked in GNN solvers, is the relationship between graph theoretic measure of structure in SAT problems and the generalisation ability of GNN solvers. To bridge the gap between structural graph properties (e.g., modularity, self-similarity) and the generalisability (or lack thereof) of GNN based SAT solvers, we present StructureSAT: a curated dataset, along with code to further generate novel examples, containing a diverse set of SAT problems from well known problem domains. Furthermore, we utilise a novel splitting method that focuses on deconstructing the families into more detailed hierarchies based on their structural properties. With the new dataset, we aim to help explain problematic generalisation in existing GNN SAT solvers by exploiting knowledge of structural graph properties. We conclude with multiple future directions that can help researchers in GNN based SAT solving develop more effective and generalisable SAT solvers.
• Abstract（参考訳）: コンフリクト駆動節学習(CDCL)のような技術に基づくSAT(Satifiability)解決法は,合成と実世界の両分野において優れた性能を発揮している。 これらのCDCLソルバはプロブレムベースでのみ動作するが、グラフニューラルネットワーク(GNN)ベースのソルバは、問題解決問題から得られた知識を活用して、新たなSAT問題の解決を迅速化することにより、この分野に新たなメリットをもたらす。 しかし、CDCLソルバの文脈でしばしば研究される特定の領域は、主にGNNソルバで見落とされ、SAT問題の構造のグラフ理論測度とGNNソルバの一般化能力の関係がある。 構造グラフ特性(モジュラリティ,自己相似性)とGNNベースのSATソルバの一般性(あるいはその欠如)とのギャップを埋めるために,構造化データセットであるStructureSATと,既知の問題領域からのSAT問題の多様な集合を含む新たなサンプルを生成するコードを提案する。 さらに,家族を構造的特性に基づいてより詳細な階層に分解することに焦点を当てた,斬新な分割手法を利用する。 新しいデータセットでは,構造グラフ特性の知識を活用することで,既存のGNN SATソルバにおける問題一般化の解明を支援することを目的としている。 我々は、GNNベースのSAT解法の研究者がより効果的で一般化可能なSAT解法を開発するのに役立つ、複数の今後の方向性を結論付けている。

関連論文リスト

• Self-Satisfied: An end-to-end framework for SAT generation and prediction [0.7340017786387768]
  高速SAT問題生成のためのハードウェアアクセラレーションアルゴリズムと幾何SAT符号化を導入する。 これらの進歩により、何千もの変数と数万の節でSAT問題へのアプローチをスケールできます。 私たちの研究の基本的な側面は、SATデータの本質と、機械学習モデルのトレーニングに適合する可能性に関するものです。
  論文  参考訳（メタデータ） (2024-10-18T22:25:54Z)
• GraSS: Combining Graph Neural Networks with Expert Knowledge for SAT Solver Selection [45.222591894755105]
  インスタンスの3部グラフ表現に基づくSATソルバ自動選択のための新しいアプローチであるGraSSを提案する。 我々は、新しいノードの特徴設計のようなドメイン固有の決定でグラフ表現を豊かにします。 生の表現とドメイン固有の選択の組み合わせが実行時の改善につながることを実証する。
  論文  参考訳（メタデータ） (2024-05-17T18:00:50Z)
• G4SATBench: Benchmarking and Advancing SAT Solving with Graph Neural Networks [7.951021955925275]
  グラフニューラルネットワーク(GNN)は、ブール満足度問題(SAT)を解決するための有望なアプローチとして登場した。 G4SATBenchは、GNNベースのSATソルバの包括的な評価フレームワークを確立する最初のベンチマーク研究である。 本結果は,GNNベースのSATソルバの性能に関する貴重な知見を提供する。
  論文  参考訳（メタデータ） (2023-09-29T02:50:57Z)
• Using deep learning to construct stochastic local search SAT solvers with performance bounds [0.0]
  グラフニューラルネットワークを用いてオーラクルを訓練し、2つのSLSソルバ上で、様々な難易度を持つランダムSATインスタンス上でそれらを評価する。 GNNベースのオラクルへのアクセスは,両者のパフォーマンスを著しく向上させることがわかった。
  論文  参考訳（メタデータ） (2023-09-20T16:27:52Z)
• Addressing Variable Dependency in GNN-based SAT Solving [19.38746341365531]
  本稿では、繰り返しニューラルネットワークを統合したGNNベースのアーキテクチャであるAsymSATを提案し、可変代入に対する依存予測を生成する。 実験結果から,大規模テストセット上でのSATインスタンスの解数を改善することにより,依存変数予測がGNN方式の解解能力を拡張できることが示唆された。
  論文  参考訳（メタデータ） (2023-04-18T05:33:33Z)
• Rethinking Complex Queries on Knowledge Graphs with Neural Link Predictors [58.340159346749964]
  本稿では,証明可能な推論能力を備えた複雑なクエリを用いたエンドツーエンド学習を支援するニューラルシンボリック手法を提案する。 これまでに検討されていない10種類の新しいクエリを含む新しいデータセットを開発する。 提案手法は,新しいデータセットにおいて先行手法を著しく上回り,既存データセットにおける先行手法を同時に上回っている。
  論文  参考訳（メタデータ） (2023-04-14T11:35:35Z)
• A Comprehensive Study on Large-Scale Graph Training: Benchmarking and Rethinking [124.21408098724551]
  グラフニューラルネットワーク(GNN)の大規模グラフトレーニングは、非常に難しい問題である 本稿では,既存の問題に対処するため,EnGCNという新たなアンサンブルトレーニング手法を提案する。 提案手法は,大規模データセット上でのSOTA(State-of-the-art)の性能向上を実現している。
  論文  参考訳（メタデータ） (2022-10-14T03:43:05Z)
• Machine Learning Methods in Solving the Boolean Satisfiability Problem [72.21206588430645]
  本論文は, Boolean satisfiability problem (SAT) を機械学習技術で解くことに関する最近の文献をレビューする。 ML-SATソルバを手作り特徴を持つナイーブ分類器からNeuroSATのような新たなエンド・ツー・エンドSATソルバまで,進化するML-SATソルバについて検討する。
  論文  参考訳（メタデータ） (2022-03-02T05:14:12Z)
• Transformer-based Machine Learning for Fast SAT Solvers and Logic Synthesis [63.53283025435107]
  CNFベースのSATとMaxSATは論理合成と検証システムの中心である。 そこで本研究では,Transformerアーキテクチャから派生したワンショットモデルを用いて,MaxSAT問題の解法を提案する。
  論文  参考訳（メタデータ） (2021-07-15T04:47:35Z)
• Evaluating Logical Generalization in Graph Neural Networks [59.70452462833374]
  グラフニューラルネットワーク(GNN)を用いた論理一般化の課題について検討する。 ベンチマークスイートであるGraphLogでは、学習アルゴリズムが異なる合成論理でルール誘導を実行する必要がある。 モデルが一般化し適応する能力は、トレーニング中に遭遇する論理規則の多様性によって強く決定される。
  論文  参考訳（メタデータ） (2020-03-14T05:45:55Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。