論文の概要: HyperSAT: Unsupervised Hypergraph Neural Networks for Weighted MaxSAT Problems

• arxiv url: http://arxiv.org/abs/2504.11885v1
• Date: Wed, 16 Apr 2025 09:11:16 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-17 14:38:59.472507
• Title: HyperSAT: Unsupervised Hypergraph Neural Networks for Weighted MaxSAT Problems
• Title（参考訳）: HyperSAT: MaxSAT問題に対する教師なしハイパーグラフニューラルネットワーク
• Authors: Qiyue Chen, Shaolin Tan, Suixiang Gao, Jinhu Lü,
• Abstract要約: グラフニューラルネットワーク(GNN)は,Boolean satisfiability(SAT)とMaxSAT(Maximum Satisfiability)の両問題を解決する上で,有望なパフォーマンスを示している。 Weighted MaxSAT問題を解決するために,教師なしハイパーグラフニューラルネットワークモデルを用いた新しいニューラルアプローチであるHyperSATを提案する。
• 参考スコア（独自算出の注目度）: 6.888911557760833
• License:
• Abstract: Graph neural networks (GNNs) have shown promising performance in solving both Boolean satisfiability (SAT) and Maximum Satisfiability (MaxSAT) problems due to their ability to efficiently model and capture the structural dependencies between literals and clauses. However, GNN methods for solving Weighted MaxSAT problems remain underdeveloped. The challenges arise from the non-linear dependency and sensitive objective function, which are caused by the non-uniform distribution of weights across clauses. In this paper, we present HyperSAT, a novel neural approach that employs an unsupervised hypergraph neural network model to solve Weighted MaxSAT problems. We propose a hypergraph representation for Weighted MaxSAT instances and design a cross-attention mechanism along with a shared representation constraint loss function to capture the logical interactions between positive and negative literal nodes in the hypergraph. Extensive experiments on various Weighted MaxSAT datasets demonstrate that HyperSAT achieves better performance than state-of-the-art competitors.
• Abstract（参考訳）: グラフニューラルネットワーク(GNN)は、リテラルと節間の構造的依存関係を効率的にモデル化し、キャプチャする能力により、Boolean satisfiability(SAT)とMaxSAT(Maximum Satisfiability)の2つの問題を解決する上で、有望なパフォーマンスを示している。 しかし、重み付きMaxSAT問題を解くためのGNN法はまだ未開発である。 課題は、節間の重みの非一様分布によって生じる非線形依存と敏感な客観関数から生じる。 本稿では、教師なしハイパーグラフニューラルネットワークモデルを用いて、重み付きMaxSAT問題の解法であるHyperSATを提案する。 Weighted MaxSAT インスタンスのハイパーグラフ表現を提案し、ハイパーグラフ内の正負負負のリテラルノード間の論理的相互作用を捉えるための共有表現制約損失関数とともに、クロスアテンション機構を設計する。 さまざまなWeighted MaxSATデータセットに関する大規模な実験は、HyperSATが最先端の競合製品よりも優れたパフォーマンスを実現していることを示している。

関連論文リスト

• LinSATNet: The Positive Linear Satisfiability Neural Networks [116.65291739666303]
  本稿では,ニューラルネットワークに人気の高い正の線形満足度を導入する方法について検討する。 本稿では,古典的なシンクホーンアルゴリズムを拡張し,複数の辺分布の集合を共同で符号化する,最初の微分可能満足層を提案する。
  論文  参考訳（メタデータ） (2024-07-18T22:05:21Z)
• torchmSAT: A GPU-Accelerated Approximation To The Maximum Satisfiability Problem [1.5850859526672516]
  最大満足度問題(MaxSAT)の解を近似できる単一の微分可能関数を導出する。 我々は,我々の微分可能な関数をモデル化する新しいニューラルネットワークアーキテクチャを提案し,バックプロパゲーションを用いてMaxSATを段階的に解く。
  論文  参考訳（メタデータ） (2024-02-06T02:33:00Z)
• Equivariant Hypergraph Diffusion Neural Operators [81.32770440890303]
  ハイパーグラフを符号化するためにニューラルネットワークを使用するハイパーグラフニューラルネットワーク(HNN)は、データの高次関係をモデル化する有望な方法を提供する。 本研究ではED-HNNと呼ばれる新しいHNNアーキテクチャを提案する。 実世界の9つのハイパーグラフデータセットのノード分類におけるED-HNNの評価を行った。
  論文  参考訳（メタデータ） (2022-07-14T06:17:00Z)
• DPMS: An ADD-Based Symbolic Approach for Generalized MaxSAT Solving [45.21499915442282]
  本稿では,ハイブリッド制約を用いた一般化MaxSAT問題の解法について,新しい動的プログラミング手法を提案する。 我々の汎用フレームワークは、MaxSAT、Min-MaxSAT、MinSATといったCNF-MaxSATの多くの一般化をハイブリッド制約で認めている。 実験の結果、DPMSは様々な手法に基づく他のアルゴリズムがすべて失敗し、特定の問題を迅速に解決できることがわかった。
  論文  参考訳（メタデータ） (2022-05-08T00:31:53Z)
• Can Graph Neural Networks Learn to Solve MaxSAT Problem? [22.528432249712637]
  我々は,理論的および実践的両面から,マックスサット問題の解法学習におけるGNNの能力について検討した。 我々はベンチマークからMaxSATインスタンスの解法を学ぶために2種類のGNNモデルを構築し、実験によりGNNがMaxSAT問題を解く魅力的な可能性を示す。 また,アルゴリズムアライメント理論に基づいて,GNN が MaxSAT 問題のある程度の解法を学習できるという理論的な説明も提示する。
  論文  参考訳（メタデータ） (2021-11-15T07:33:33Z)
• Generalization of Neural Combinatorial Solvers Through the Lens of Adversarial Robustness [68.97830259849086]
  ほとんどのデータセットは単純なサブプロブレムのみをキャプチャし、おそらくは突発的な特徴に悩まされる。 本研究では, 局所的な一般化特性である対向ロバスト性について検討し, 厳密でモデル固有な例と突発的な特徴を明らかにする。 他のアプリケーションとは異なり、摂動モデルは知覚できないという主観的な概念に基づいて設計されているため、摂動モデルは効率的かつ健全である。 驚くべきことに、そのような摂動によって、十分に表現力のあるニューラルソルバは、教師あり学習で共通する正確さと悪質さのトレードオフの限界に悩まされない。
  論文  参考訳（メタデータ） (2021-10-21T07:28:11Z)
• Transformer-based Machine Learning for Fast SAT Solvers and Logic Synthesis [63.53283025435107]
  CNFベースのSATとMaxSATは論理合成と検証システムの中心である。 そこで本研究では,Transformerアーキテクチャから派生したワンショットモデルを用いて,MaxSAT問題の解法を提案する。
  論文  参考訳（メタデータ） (2021-07-15T04:47:35Z)
• Goal-Aware Neural SAT Solver [2.609784101826762]
  現代のニューラルネットワークは問題に関する情報を取得し、入力値からのみ出力を算出する。 我々は、必ずしも最適ではなく、クエリメカニズムで拡張することで、ネットワークの性能を大幅に改善できると主張している。 本稿では、QuerySATと呼ばれるクエリ機構を備えたニューラルSATソルバを提案し、幅広いSATタスクにおいてニューラルベースラインよりも優れていることを示す。
  論文  参考訳（メタデータ） (2021-06-14T04:51:24Z)
• Incomplete MaxSAT Approaches for Combinatorial Testing [0.0]
  本稿では,最小長の制約付き混合被覆アレイを構築するためのSAT(Satifiability)に基づくアプローチを提案する。 この問題はシステム障害検出のためのコンビネータテストの中心である。
  論文  参考訳（メタデータ） (2021-05-26T14:00:56Z)
• A Biased Graph Neural Network Sampler with Near-Optimal Regret [57.70126763759996]
  グラフニューラルネットワーク(GNN)は、グラフおよびリレーショナルデータにディープネットワークアーキテクチャを適用する手段として登場した。 本論文では,既存の作業に基づいて,GNN近傍サンプリングをマルチアームバンディット問題として扱う。 そこで本研究では,分散を低減し,不安定かつ非限定的な支払いを回避すべく設計されたバイアスをある程度導入した報酬関数を提案する。
  論文  参考訳（メタデータ） (2021-03-01T15:55:58Z)

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

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