論文の概要: Target-Aware Data Augmentation for SAT Prediction

• arxiv url: http://arxiv.org/abs/2605.06931v1
• Date: Thu, 07 May 2026 20:45:08 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-11 19:43:38.613828
• Title: Target-Aware Data Augmentation for SAT Prediction
• Title（参考訳）: SAT予測のためのターゲット対応データ拡張
• Authors: Eshed Gal, Uri Ascher, Eldad Haber,
• Abstract要約: Boolean satisfiability (SAT)のようなドメインでは、標準的なパイプラインはサーボ・イン・ザ・ループ・ラベリングに依存している。 このボトルネックは、難しい問題の構造を捉えるために機械学習を活用するという、より広範な目標を妨げます。 本研究では,SAT と UNSAT を正しくラベル付けした SAT と UNSAT インスタンスを構築により生成する SAT のターゲットアウェア,ソルバフリーなデータ生成フレームワークを提案する。
• 参考スコア（独自算出の注目度）: 5.288977149942441
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Learning-based approaches to NP-hard problems have shown increasing promise, but their progress is fundamentally constrained by the high cost of generating labeled training data. In domains such as Boolean satisfiability (SAT), standard pipelines rely on solver-in-the-loop labeling, which scales poorly with problem size and limits the amount of usable supervision. This bottleneck hinders the broader goal of leveraging machine learning to capture structure in hard combinatorial problems. In this work, we propose a target-aware, solver-free data generation framework for SAT that produces correctly labeled SAT and UNSAT instances by construction, eliminating the need for expensive solver calls. Our method aligns generated instances with the structural properties of a target benchmark, making synthetic data effective for downstream learning. We further develop a linear-programming-aware graph neural network (LPGNN) architecture that incorporates constraint-violation residuals into message passing, enabling the model to exploit underlying optimization structure. Together, these contributions support a data-centric paradigm for learning on NP-hard problems, where scalable, task-aligned data generation is as critical as model design. Our approach yields orders-of-magnitude speedups in data generation, demonstrating that benchmark-aligned synthetic data can effectively augment solver-labeled datasets for GNN-based SAT prediction.
• Abstract（参考訳）: NP-hard問題に対する学習ベースのアプローチは、将来性を示しているが、その進歩はラベル付きトレーニングデータを生成するコストが高いため、基本的に制限されている。 Boolean satisfiability (SAT)のようなドメインでは、標準的なパイプラインはソルバ・イン・ザ・ループのラベリングに依存している。 このボトルネックは、複雑な組合せ問題における構造を捉えるために機械学習を活用するという、より広範な目標を妨げます。 本研究では,SAT と UNSAT のインスタンスを構築により正確にラベル付けした SAT と UNSAT のインスタンスを生成する SAT のターゲットアウェアでソルバフリーなデータ生成フレームワークを提案する。 提案手法は,生成したインスタンスを目標ベンチマークの構造特性と整合させることにより,下流学習に有効な合成データを実現する。 さらに,制約違反残差をメッセージパッシングに組み込んだ線形プログラミング対応グラフニューラルネットワーク(LPGNN)アーキテクチャを開発し,その基盤となる最適化構造を利用する。 これらのコントリビューションは、NPハードな問題を学ぶためのデータ中心のパラダイムをサポートします。 提案手法は,GNNベースのSAT予測のために,ベンチマークに適合した合成データにより,解法ラベル付きデータセットを効果的に拡張できることを実証する。

関連論文リスト

• Towards Neural Graph Data Management [48.66793294452754]
  NGDBenchは5つの異なる領域にわたるニューラルグラフデータベース機能を評価するための統一ベンチマークである。 NGDBenchは完全なCypherクエリ言語をサポートし、複雑なパターンマッチング、可変長パス、数値集約を可能にする。 現状のLCMとRAG法の評価では, 構造的推論, 雑音の頑健性, 解析的精度に重大な制限が認められる。
  論文  参考訳（メタデータ） (2026-02-27T08:59:25Z)
• Unlocking Symbol-Level Precoding Efficiency Through Tensor Equivariant Neural Network [84.22115118596741]
  シンボルレベルのプリコーディングにおいて,推論の複雑さの低いエンドツーエンドディープラーニング(DL)フレームワークを提案する。 提案手法は,従来の手法よりも約80倍の高速化を実現しつつ,SLPの大幅な性能向上を達成できることを示す。
  論文  参考訳（メタデータ） (2025-10-02T15:15:50Z)
• RV-Syn: Rational and Verifiable Mathematical Reasoning Data Synthesis based on Structured Function Library [58.404895570822184]
  RV-Synは、新しい数学的合成手法である。 このライブラリからPython形式の関数を組み合わせることで、グラフをソリューションとして生成する。 構築したグラフに基づいて,解誘導論理認識問題生成を実現する。
  論文  参考訳（メタデータ） (2025-04-29T04:42:02Z)
• DPFAGA-Dynamic Power Flow Analysis and Fault Characteristics: A Graph Attention Neural Network [0.19439126568870457]
  本稿では, 動的潮流解析と断層特性を考慮した共同グラフ注意ニューラルネットワーク(GAT)とアダプティブ隣人(CAN)によるクラスタリングを提案する。 次に、スマートグリッドのユースケースアプリケーションで提案したフレームワークを評価し、既存の手法と公正に比較する。
  論文  参考訳（メタデータ） (2025-03-19T03:17:11Z)
• DFA-GNN: Forward Learning of Graph Neural Networks by Direct Feedback Alignment [57.62885438406724]
  グラフニューラルネットワークは、様々なアプリケーションにまたがる強力なパフォーマンスで認識されている。 BPには、その生物学的妥当性に挑戦する制限があり、グラフベースのタスクのためのトレーニングニューラルネットワークの効率、スケーラビリティ、並列性に影響を与える。 半教師付き学習のケーススタディを用いて,GNNに適した新しい前方学習フレームワークであるDFA-GNNを提案する。
  論文  参考訳（メタデータ） (2024-06-04T07:24:51Z)
• EPIC: Effective Prompting for Imbalanced-Class Data Synthesis in Tabular Data Classification via Large Language Models [39.347666307218006]
  大規模言語モデル (LLM) は、多様なアプリケーションにまたがるテキスト内学習能力を示す。 バランスの取れたデータサンプルと一貫したフォーマットと独自の変数マッピングを併用した新しい手法であるEPICを導入し、不均衡なデータセットであっても、全てのクラスで正確な合成データを生成するのにLLMをガイドする。
  論文  参考訳（メタデータ） (2024-04-15T17:49:16Z)
• Quadratic Binary Optimization with Graph Neural Networks [20.497024298986883]
  グラフニューラルネットワーク(GNN)と擬似非制約バイナリ最適化(QUBO)の相関について検討する。 本稿では,グラフ表現学習技術とQUBO認識機能を統合するアーキテクチャであるQUBO-GNNを提案する。
  論文  参考訳（メタデータ） (2024-04-07T08:38:35Z)
• Adaptive Anomaly Detection for Internet of Things in Hierarchical Edge Computing: A Contextual-Bandit Approach [81.5261621619557]
  階層エッジコンピューティング(HEC)を用いた適応型異常検出手法を提案する。 まず,複雑性を増した複数のDNNモデルを構築し,それぞれを対応するHEC層に関連付ける。 そこで我々は、文脈帯域問題として定式化され、強化学習ポリシーネットワークを用いて解決される適応モデル選択スキームを設計する。
  論文  参考訳（メタデータ） (2021-08-09T08:45:47Z)
• Transformer-based Machine Learning for Fast SAT Solvers and Logic Synthesis [63.53283025435107]
  CNFベースのSATとMaxSATは論理合成と検証システムの中心である。 そこで本研究では,Transformerアーキテクチャから派生したワンショットモデルを用いて,MaxSAT問題の解法を提案する。
  論文  参考訳（メタデータ） (2021-07-15T04:47:35Z)

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

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