論文の概要: Can Graph Neural Networks Learn to Solve MaxSAT Problem?

• arxiv url: http://arxiv.org/abs/2111.07568v1
• Date: Mon, 15 Nov 2021 07:33:33 GMT
• ステータス: 処理完了
• システム内更新日: 2021-11-17 02:50:43.731299
• Title: Can Graph Neural Networks Learn to Solve MaxSAT Problem?
• Title（参考訳）: グラフニューラルネットワークはMaxSAT問題を解決することができるか?
• Authors: Minghao Liu, Fuqi Jia, Pei Huang, Fan Zhang, Yuchen Sun, Shaowei Cai, Feifei Ma, Jian Zhang
• Abstract要約: 我々は,理論的および実践的両面から,マックスサット問題の解法学習におけるGNNの能力について検討した。 我々はベンチマークからMaxSATインスタンスの解法を学ぶために2種類のGNNモデルを構築し、実験によりGNNがMaxSAT問題を解く魅力的な可能性を示す。 また,アルゴリズムアライメント理論に基づいて,GNN が MaxSAT 問題のある程度の解法を学習できるという理論的な説明も提示する。
• 参考スコア（独自算出の注目度）: 22.528432249712637
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: With the rapid development of deep learning techniques, various recent work has tried to apply graph neural networks (GNNs) to solve NP-hard problems such as Boolean Satisfiability (SAT), which shows the potential in bridging the gap between machine learning and symbolic reasoning. However, the quality of solutions predicted by GNNs has not been well investigated in the literature. In this paper, we study the capability of GNNs in learning to solve Maximum Satisfiability (MaxSAT) problem, both from theoretical and practical perspectives. We build two kinds of GNN models to learn the solution of MaxSAT instances from benchmarks, and show that GNNs have attractive potential to solve MaxSAT problem through experimental evaluation. We also present a theoretical explanation of the effect that GNNs can learn to solve MaxSAT problem to some extent for the first time, based on the algorithmic alignment theory.
• Abstract（参考訳）: ディープラーニング技術の急速な発展に伴い、最近の様々な研究がグラフニューラルネットワーク(GNN)を用いて、学習と象徴的推論のギャップを埋める可能性を示すBoolean Satisfiability(SAT)のようなNP難問を解決しようとしている。 しかし,gnnが予測する解の質は文献ではあまり研究されていない。 本稿では,学習におけるGNNの最大満足度(MaxSAT)問題を解決する能力について,理論的・実践的両面から検討する。 我々はベンチマークからMaxSATインスタンスの解法を学ぶために2種類のGNNモデルを構築し、実験によりGNNがMaxSAT問題を解く魅力的な可能性を示す。 また,アルゴリズムアライメント理論に基づいて,GNN が MaxSAT 問題のある程度の解法を学習できるという理論的な説明も提示する。

関連論文リスト

• LinSATNet: The Positive Linear Satisfiability Neural Networks [116.65291739666303]
  本稿では,ニューラルネットワークに人気の高い正の線形満足度を導入する方法について検討する。 本稿では,古典的なシンクホーンアルゴリズムを拡張し,複数の辺分布の集合を共同で符号化する,最初の微分可能満足層を提案する。
  論文  参考訳（メタデータ） (2024-07-18T22:05:21Z)
• Combinatorial Optimization with Automated Graph Neural Networks [28.19349828026972]
  NP-hard CO 問題,すなわち textbfAutoGNP を解決するために,textbfAUTOmated textbfGNN のクラスを新たに提案する。 AutoGNPの考え方は、グラフニューラルアーキテクチャ検索アルゴリズムを使用して、与えられたNPハード最適化問題に対して最適なGNNを自動的に見つけることである。
  論文  参考訳（メタデータ） (2024-06-05T02:43:41Z)
• torchmSAT: A GPU-Accelerated Approximation To The Maximum Satisfiability Problem [1.5850859526672516]
  最大満足度問題(MaxSAT)の解を近似できる単一の微分可能関数を導出する。 我々は,我々の微分可能な関数をモデル化する新しいニューラルネットワークアーキテクチャを提案し,バックプロパゲーションを用いてMaxSATを段階的に解く。
  論文  参考訳（メタデータ） (2024-02-06T02:33:00Z)
• G4SATBench: Benchmarking and Advancing SAT Solving with Graph Neural Networks [7.951021955925275]
  グラフニューラルネットワーク(GNN)は、ブール満足度問題(SAT)を解決するための有望なアプローチとして登場した。 G4SATBenchは、GNNベースのSATソルバの包括的な評価フレームワークを確立する最初のベンチマーク研究である。 本結果は,GNNベースのSATソルバの性能に関する貴重な知見を提供する。
  論文  参考訳（メタデータ） (2023-09-29T02:50:57Z)
• Cracking nuts with a sledgehammer: when modern graph neural networks do worse than classical greedy algorithms [2.436681150766912]
  ほぼ線形時間で実行される単純なグリージーアルゴリズムは、GNNよりもはるかに優れた品質のMIS問題の解を見つけることができることを示す。 これらのGNNでMISを解く理由や、ハンマーを使ってナッツを割る理由がよく分からない。
  論文  参考訳（メタデータ） (2022-06-27T11:54:01Z)
• Graph Neural Networks for Propositional Model Counting [1.0152838128195467]
  グラフネットワーク(GNN)は最近、論理的推論タスクの解決に活用されている。 本稿では, 自覚的GNNによって拡張され, #SAT 問題を大まかに解くために訓練された, Kuch 等の信念伝播のための GNN フレームワークに基づくアーキテクチャを提案する。
  論文  参考訳（メタデータ） (2022-05-09T17:03:13Z)
• Transformer-based Machine Learning for Fast SAT Solvers and Logic Synthesis [63.53283025435107]
  CNFベースのSATとMaxSATは論理合成と検証システムの中心である。 そこで本研究では,Transformerアーキテクチャから派生したワンショットモデルを用いて,MaxSAT問題の解法を提案する。
  論文  参考訳（メタデータ） (2021-07-15T04:47:35Z)
• Fast Learning of Graph Neural Networks with Guaranteed Generalizability: One-hidden-layer Case [93.37576644429578]
  グラフニューラルネットワーク(GNN)は、グラフ構造化データから実際に学習する上で、近年大きな進歩を遂げている。 回帰問題と二項分類問題の両方に隠れ層を持つGNNの理論的に基底的な一般化可能性解析を行う。
  論文  参考訳（メタデータ） (2020-06-25T00:45:52Z)
• Optimization and Generalization Analysis of Transduction through Gradient Boosting and Application to Multi-scale Graph Neural Networks [60.22494363676747]
  現在のグラフニューラルネットワーク(GNN)は、オーバースムーシング(over-smoothing)と呼ばれる問題のため、自分自身を深くするのは難しいことが知られている。 マルチスケールGNNは、オーバースムーシング問題を緩和するための有望なアプローチである。 マルチスケールGNNを含むトランスダクティブ学習アルゴリズムの最適化と一般化を保証する。
  論文  参考訳（メタデータ） (2020-06-15T17:06:17Z)
• Graph Neural Networks for Motion Planning [108.51253840181677]
  低次元問題に対する高密度固定グラフ上のGNNと高次元問題に対するサンプリングベースGNNの2つの手法を提案する。 RRT(Rapidly-Exploring Random Trees)におけるクリティカルノードの特定やサンプリング分布の学習といった計画上の問題にGNNが取り組む能力について検討する。 臨界サンプリング、振り子、6つのDoFロボットアームによる実験では、GNNは従来の分析手法の改善だけでなく、完全に接続されたニューラルネットワークや畳み込みニューラルネットワークを用いた学習アプローチも示している。
  論文  参考訳（メタデータ） (2020-06-11T08:19:06Z)
• Efficient Probabilistic Logic Reasoning with Graph Neural Networks [63.099999467118245]
  マルコフ論理ネットワーク(MLN)は、多くの知識グラフ問題に対処するために用いられる。 MLNの推論は計算集約的であり、MLNの産業規模での応用は非常に困難である。 本稿では,表現力とモデルの単純さとのバランスのよいグラフニューラルネット(GNN)モデルであるExpressGNNを提案する。
  論文  参考訳（メタデータ） (2020-01-29T23:34:36Z)

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

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