論文の概要: Hypergraph Neural Networks Accelerate MUS Enumeration

• arxiv url: http://arxiv.org/abs/2604.09001v1
• Date: Fri, 10 Apr 2026 06:13:41 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-13 17:57:53.713881
• Title: Hypergraph Neural Networks Accelerate MUS Enumeration
• Title（参考訳）: ハイパーグラフニューラルネットワークによるMUS列挙の高速化
• Authors: Hiroya Ijima, Koichiro Yawata,
• Abstract要約: 本稿では,ハイパーグラフニューラルネットワーク(HGNN)を用いたMUS列挙を高速化するためのドメインに依存しない手法を提案する。 実験により,MUS列挙を高速化する手法の有効性が示され,本手法は従来手法と比較して,満足度チェックの予算内でより多くのMUSを列挙できることが示された。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Enumerating Minimal Unsatisfiable Subsets (MUSes) is a fundamental task in constraint satisfaction problems (CSPs). Its major challenge is the exponential growth of the search space, which becomes particularly severe when satisfiability checks are expensive. Recent machine learning approaches reduce this cost for Boolean satisfiability problems but rely on explicit variable-constraint relationships, limiting their application domains. This paper proposes a domain-agnostic method to accelerate MUS enumeration using Hypergraph Neural Networks (HGNNs). The proposed method incrementally builds a hypergraph with constraints as vertices and MUSes enumerated until the current step as hyperedges, and employs an HGNN-based agent trained via reinforcement learning to minimize the number of satisfiability checks required to obtain an MUS. Experimental results demonstrate the effectiveness of our approach in accelerating MUS enumeration, showing that our method can enumerate more MUSes within the same satisfiability check budget compared to conventional methods.
• Abstract（参考訳）: MUS(Minimum Unsatisfiable Subsets)を列挙することは、制約満足度問題(CSP)の基本的な課題である。 その大きな課題は、検索スペースの指数的な成長であり、満足度チェックが高価になると特に深刻になる。 最近の機械学習アプローチは、ブール適合性問題に対するこのコストを削減するが、明示的な変数制約関係に依存し、アプリケーションドメインを制限している。 本稿では,ハイパーグラフニューラルネットワーク(HGNN)を用いたMUS列挙を高速化するドメインに依存しない手法を提案する。 提案手法では,提案手法は, 頂点やMUSが現在の段階までハイパーエッジとして列挙した制約付きハイパーグラフを段階的に構築し, 強化学習によって訓練されたHGNNベースのエージェントを用いて, MUSを得るために必要な満足度チェック数を最小化する。 実験により,MUS列挙を高速化する手法の有効性が示され,本手法は従来手法と比較して,満足度チェックの予算内により多くのMUSを列挙できることが示された。

関連論文リスト

• Provably Explaining Neural Additive Models [13.941535361737728]
  証明可能な保証を持つ説明を得るための主要なアプローチは、入力特徴の基数最小部分集合を特定することである。 標準的なニューラルネットワークの場合、このタスクは最悪の指数的な数の検証クエリを必要とするため、しばしば計算不可能である。 近年のニューラルネットワークファミリーであるニューラル・アダプティブ・モデル(NAM)では、そのような保証によって効率的に説明を生成できることが示されている。
  論文  参考訳（メタデータ） (2026-02-19T16:42:29Z)
• Clip-and-Verify: Linear Constraint-Driven Domain Clipping for Accelerating Neural Network Verification [9.733843486234878]
  最先端ニューラルネットワーク(NN)検証は、分岐とバウンド(BaB)の手順を高速なバウンディング技術で適用することが、多くの挑戦的な検証特性に対処する上で重要な役割を果たしていることを示す。 本稿では,NN検証の有効性を高めるために,スケーラブルで効率的な手法のクラスである線形制約駆動型クリッピングフレームワークを紹介する。
  論文  参考訳（メタデータ） (2025-12-11T19:59:37Z)
• Exact Verification of Graph Neural Networks with Incremental Constraint Solving [17.378319742808856]
  グラフニューラルネットワーク(GNN)は、不正検出や医療といった高度なアプリケーションにますます採用されているが、敵の攻撃の影響を受けやすい。 我々は,GNNに対して,属性や構造的摂動に対する保証を計算するための,正確な(健全で完全な)検証手法を開発した。 我々は、メッセージパッシングニューラルネットワークのための汎用的な解法であるGNNevを実装し、合計、最大、平均の3つのアグリゲーション機能をサポートしている。
  論文  参考訳（メタデータ） (2025-08-12T20:10:31Z)
• Kolmogorov Arnold Networks in Fraud Detection: Bridging the Gap Between Theory and Practice [3.692410936160711]
  本研究では,コルモゴロフ・アルノルドネットワーク(KAN)の不正検出への適用性を検討した。 そこで本研究では,PCA(Principal Component Analysis, 主成分分析)を用いて,データをスプラインを用いて2次元に分割する手法を提案する。
  論文  参考訳（メタデータ） (2024-08-15T18:58:21Z)
• Graph Pruning for Enumeration of Minimal Unsatisfiable Subsets [4.59143974279554]
  バイナリ制約の最小不満足な部分集合(MUS)を見つけることは、過剰制約されたシステムの不適合性解析において一般的な問題である。 MUS列挙を高速化するために,学習モデルを用いて公式をプルーする手法を提案する。
  論文  参考訳（メタデータ） (2024-02-19T20:03:45Z)
• Achieving Constraints in Neural Networks: A Stochastic Augmented Lagrangian Approach [49.1574468325115]
  DNN(Deep Neural Networks)の正規化は、一般化性の向上とオーバーフィッティングの防止に不可欠である。 制約付き最適化問題としてトレーニングプロセスのフレーミングによるDNN正規化に対する新しいアプローチを提案する。 我々はAugmented Lagrangian (SAL) 法を用いて、より柔軟で効率的な正規化機構を実現する。
  論文  参考訳（メタデータ） (2023-10-25T13:55:35Z)
• The #DNN-Verification Problem: Counting Unsafe Inputs for Deep Neural Networks [94.63547069706459]
  #DNN-Verification問題は、DNNの入力構成の数を数えることによって安全性に反する結果となる。 違反の正確な数を返す新しい手法を提案する。 安全クリティカルなベンチマークのセットに関する実験結果を示す。
  論文  参考訳（メタデータ） (2023-01-17T18:32:01Z)
• Global Optimization of Objective Functions Represented by ReLU Networks [77.55969359556032]
  ニューラルネットワークは複雑で非敵対的な関数を学ぶことができ、安全クリティカルな文脈でそれらの正しい振る舞いを保証することは困難である。 ネットワーク内の障害を見つけるための多くのアプローチ(例えば、敵の例)があるが、これらは障害の欠如を保証できない。 本稿では,最適化プロセスを検証手順に統合し,本手法よりも優れた性能を実現する手法を提案する。
  論文  参考訳（メタデータ） (2020-10-07T08:19:48Z)

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

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