論文の概要: MILP-SAT-GNN: Yet Another Neural SAT Solver
- arxiv url: http://arxiv.org/abs/2507.01825v1
- Date: Wed, 02 Jul 2025 15:39:45 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-07-03 14:23:00.361688
- Title: MILP-SAT-GNN: Yet Another Neural SAT Solver
- Title(参考訳): MILP-SAT-GNN: もう1つのニューラルSATソルバー
- Authors: Franco Alberto Cardillo, Hamza Khyari, Umberto Straccia,
- Abstract要約: 混合線形計画法(MILP)にGNNを適用した手法を利用して,グラフニューラルネットワーク(GNN)によるSAT問題の解法を提案する。
具体的には、k-CNFの公式をMILP問題にマッピングし、重み付き二部グラフとしてエンコードし、トレーニングとテストのためにGNNに入力する。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We proposes a novel method that enables Graph Neural Networks (GNNs) to solve SAT problems by leveraging a technique developed for applying GNNs to Mixed Integer Linear Programming (MILP). Specifically, k-CNF formulae are mapped into MILP problems, which are then encoded as weighted bipartite graphs and subsequently fed into a GNN for training and testing. From a theoretical perspective: (i) we establish permutation and equivalence invariance results, demonstrating that the method produces outputs that are stable under reordering of clauses and variables; (ii) we identify a theoretical limitation, showing that for a class of formulae called foldable formulae, standard GNNs cannot always distinguish satisfiable from unsatisfiable instances; (iii) we prove a universal approximation theorem, establishing that with Random Node Initialization (RNI), the method can approximate SAT solving to arbitrary precision on finite datasets, that is, the GNN becomes approximately sound and complete on such datasets. Furthermore, we show that for unfoldable formulae, the same approximation guarantee can be achieved without the need for RNI. Finally, we conduct an experimental evaluation of our approach, which show that, despite the simplicity of the neural architecture, the method achieves promising results.
- Abstract(参考訳): 混合整数線形計画法(MILP)にGNNを適用する手法を応用して,グラフニューラルネットワーク(GNN)によるSAT問題の解法を提案する。
具体的には、k-CNFの公式をMILP問題にマッピングし、重み付き二部グラフとしてエンコードし、訓練と試験のためにGNNに入力する。
理論的観点から
一 変分及び同値不変性を定め、その方法が節や変数の再順序付けの下で安定な出力を生成することを実証する。
(ii) 折りたたみ式(foldable formulae)と呼ばれる式に対して、標準のGNNは、常に満足できないインスタンスと満足できないインスタンスを区別できないことを示す理論的な制限を識別する。
3) 一般化近似定理を証明し,ランダムノード初期化(RNI)を用いることで,SAT解を有限データセット上で任意の精度で近似できることを確認した。
さらに、展開可能な公式に対しては、RNIを必要とせずに、同じ近似保証を実現できることを示す。
最後に,ニューラルネットワークの単純さにもかかわらず,提案手法が有望な結果をもたらすことを示す手法を実験的に評価する。
関連論文リスト
- Scalable Graph Compressed Convolutions [68.85227170390864]
ユークリッド畳み込みのための入力グラフのキャリブレーションに置換を適用する微分可能手法を提案する。
グラフキャリブレーションに基づいて,階層型グラフ表現学習のための圧縮畳み込みネットワーク(CoCN)を提案する。
論文 参考訳(メタデータ) (2024-07-26T03:14:13Z) - CoRMF: Criticality-Ordered Recurrent Mean Field Ising Solver [4.364088891019632]
我々は、RNNに基づく効率的なIsingモデル解法、Criticality-ordered Recurrent Mean Field (CoRMF)を提案する。
基礎となるIsingグラフの近似木構造を利用することで、新しく得られた臨界度順序は、変動平均場とRNNの統一を可能にする。
CoRFMはデータ/証拠のない自己学習方式でIsing問題を解き、RNNから直接サンプリングすることで推論タスクを実行することができる。
論文 参考訳(メタデータ) (2024-03-05T16:55:06Z) - On Neural Networks as Infinite Tree-Structured Probabilistic Graphical Models [44.676210493587256]
本稿では,ニューラルネットワークに対応する無限木構造PGMを構築することにより,革新的な解を提案する。
我々の研究は、DNNが前方伝播中に、この代替のPGM構造において正確であるPGMの近似を実行することを明らかにした。
論文 参考訳(メタデータ) (2023-05-27T21:32:28Z) - AskewSGD : An Annealed interval-constrained Optimisation method to train
Quantized Neural Networks [12.229154524476405]
我々は、深層ニューラルネットワーク(DNN)を量子化重みでトレーニングするための新しいアルゴリズム、Annealed Skewed SGD - AskewSGDを開発した。
アクティブなセットと実行可能な方向を持つアルゴリズムとは異なり、AskewSGDは実行可能な全セットの下でのプロジェクションや最適化を避けている。
実験結果から,AskewSGDアルゴリズムは古典的ベンチマークの手法と同等以上の性能を示した。
論文 参考訳(メタデータ) (2022-11-07T18:13:44Z) - Framing RNN as a kernel method: A neural ODE approach [11.374487003189468]
我々は,RNNの解を,入力シーケンスの特定の特徴集合の線形関数と見なせることを示す。
我々は,大規模なリカレントネットワークの一般化と安定性に関する理論的保証を得る。
論文 参考訳(メタデータ) (2021-06-02T14:46:40Z) - Learning Graph Neural Networks with Approximate Gradient Descent [24.49427608361397]
ラベルがノードまたはグラフに添付されているかどうかに応じて、2種類のグラフニューラルネットワーク(GNN)が調査されます。
gnnトレーニングアルゴリズムの設計と解析のための包括的なフレームワークを開発した。
提案アルゴリズムは,GNNの根底にある真のパラメータに対する線形収束率を保証する。
論文 参考訳(メタデータ) (2020-12-07T02:54:48Z) - The Surprising Power of Graph Neural Networks with Random Node
Initialization [54.4101931234922]
グラフニューラルネットワーク(GNN)は、関係データ上での表現学習に有効なモデルである。
標準 GNN はその表現力に制限があり、Weisfeiler-Leman グラフ同型(英語版)の能力以外の区別はできない。
本研究では,ランダムノード(RNI)を用いたGNNの表現力の解析を行う。
我々はこれらのモデルが普遍的であることを証明し、GNNが高次特性の計算に頼らない最初の結果である。
論文 参考訳(メタデータ) (2020-10-02T19:53:05Z) - Fast Learning of Graph Neural Networks with Guaranteed Generalizability:
One-hidden-layer Case [93.37576644429578]
グラフニューラルネットワーク(GNN)は、グラフ構造化データから実際に学習する上で、近年大きな進歩を遂げている。
回帰問題と二項分類問題の両方に隠れ層を持つGNNの理論的に基底的な一般化可能性解析を行う。
論文 参考訳(メタデータ) (2020-06-25T00:45:52Z) - Multipole Graph Neural Operator for Parametric Partial Differential
Equations [57.90284928158383]
物理系をシミュレーションするためのディープラーニングベースの手法を使用する際の大きな課題の1つは、物理ベースのデータの定式化である。
線形複雑度のみを用いて、あらゆる範囲の相互作用をキャプチャする、新しいマルチレベルグラフニューラルネットワークフレームワークを提案する。
実験により, 離散化不変解演算子をPDEに学習し, 線形時間で評価できることを確認した。
論文 参考訳(メタデータ) (2020-06-16T21:56:22Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。