論文の概要: Unsat Core Prediction through Polarity-Aware Representation Learning over Clause-Literal Hypergraphs

• arxiv url: http://arxiv.org/abs/2605.04819v1
• Date: Wed, 06 May 2026 12:08:24 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-07 18:41:07.803488
• Title: Unsat Core Prediction through Polarity-Aware Representation Learning over Clause-Literal Hypergraphs
• Title（参考訳）: クロース・リテラルハイパーグラフを用いた極性認識表現学習による不飽和コア予測
• Abstract要約: SAT式から構造情報を学習するための極性認識型表現学習フレームワークを提案する。 変数表現を極性不変成分と同変成分に分離する極性認識機構を導入する。 複数のSATデータセットに対する実験結果から,提案手法の有効性が示された。
• 参考スコア（独自算出の注目度）: 28.407066721598337
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Graph neural networks have been widely used in Boolean satisfiability (SAT) tasks to learn structural information from SAT formulas. The goal of these studies is to solve SAT instances or to enhance SAT solvers, including tasks such as unsat-core prediction. However, most existing approaches model a SAT formula as a bipartite graph or a directed acyclic graph, which are less expressive in capturing higher-order interactions among literals and clauses. Moreover, these approaches are limited in modeling intrinsic polarity-related properties of SAT, such as the complementary relationship between the positive and negative literals of a variable. To address these limitations, we propose a polarity-aware representation learning framework over clause-literal hypergraphs. We model SAT formulas as clause-literal hypergraphs augmented with a clause incidence graph to capture higher-order structural interactions. We then introduce a polarity-aware decomposed mechanism that separates variable representations into polarity invariant and equivariant components, explicitly modeling the relationship between positive and negative literals, with the resulting literal representations propagated along the hypergraph structure. We further incorporate a polarity-inversion consistency regularization to reinforce polarity-consistent representations during training. Experimental results on multiple SAT datasets demonstrate the effectiveness of the proposed approach.
• Abstract（参考訳）: グラフニューラルネットワークは、SAT式から構造情報を学習するために、Boolean satisfiability (SAT)タスクで広く使われている。 これらの研究の目的は、SATインスタンスの解決や、未満足なコア予測などのタスクを含むSATソルバの強化である。 しかし、既存のほとんどのアプローチはSAT公式を二部グラフや有向非巡回グラフとしてモデル化しており、リテラルや節間の高次相互作用を捉えることにはあまり表現力がない。 さらに、これらのアプローチは、変数の正リテラルと負リテラルの間の相補関係のようなSATの固有極性関連特性のモデル化において制限される。 これらの制約に対処するため,節文ハイパーグラフ上での極性を考慮した表現学習フレームワークを提案する。 SAT の公式を節出現グラフで拡張した節リテラルハイパーグラフとしてモデル化し,高次構造相互作用を捉える。 次に、変数表現を極性不変成分と同変成分に分離する極性対応分解機構を導入し、正と負のリテラルの関係を明示的にモデル化し、結果として得られるリテラル表現をハイパーグラフ構造に沿って伝播させる。 さらに、極性-反転整合性正規化を導入し、訓練中に極性-一貫性表現を強化する。 複数のSATデータセットに対する実験結果から,提案手法の有効性が示された。

関連論文リスト

• Directed Graph Topology Inference via Graph Filter Identification [54.541275287889164]
  本稿では,グラフ畳み込みフィルタが生成するノイズ測定から有向ネットワークを推定する問題に対処する。 また、上記のステップを交互に交互に組み合わせて、サンプルの複雑さを向上する結合グラフフィルタとトポロジー同定アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2026-06-25T18:25:57Z)
• Conditional Distribution Learning on Graphs [15.730933577970687]
  半教師付きグラフ分類のためのグラフ構造化データからグラフ表現を学習する条件分布学習(CDL)法を提案する。 具体的には、元の特徴に対して弱機能および強拡張機能の条件分布を整列するエンドツーエンドグラフ表現学習モデルを提案する。
  論文  参考訳（メタデータ） (2024-11-20T07:26:36Z)
• W2SAT: Learning to generate SAT instances from Weighted Literal Incidence Graphs [11.139131079925113]
  W2SATは、現実世界/産業インスタンスから固有の構造と特性を学ぶことによってSAT式を生成するフレームワークである。 Weighted Literal Incidence Graph (WLIG)と呼ばれる新しいSAT表現を導入する。 WLIGからSAT問題への復号化は、新しい丘登り最適化法で重なり合う斜角を見つけることをモデル化する。
  論文  参考訳（メタデータ） (2023-02-01T06:30:41Z)
• STERLING: Synergistic Representation Learning on Bipartite Graphs [78.86064828220613]
  二部グラフ表現学習の基本的な課題は、ノードの埋め込みを抽出する方法である。 最近の二部グラフSSL法は、正ノード対と負ノード対を識別することによって埋め込みを学習する対照的な学習に基づいている。 負のノードペアを持たないノード埋め込みを学習するための新しい相乗的表現学習モデル(STERling)を提案する。
  論文  参考訳（メタデータ） (2023-01-25T03:21:42Z)
• Mutual Exclusivity Training and Primitive Augmentation to Induce Compositionality [84.94877848357896]
  最近のデータセットは、標準的なシーケンス・ツー・シーケンスモデルにおける体系的な一般化能力の欠如を露呈している。 本稿では,セq2seqモデルの振る舞いを分析し,相互排他バイアスの欠如と全例を記憶する傾向の2つの要因を同定する。 広範に使用されている2つの構成性データセット上で、標準的なシーケンス・ツー・シーケンスモデルを用いて、経験的改善を示す。
  論文  参考訳（メタデータ） (2022-11-28T17:36:41Z)
• Graph Neural Networks with Adaptive Readouts [5.575293536755126]
  異なる領域とグラフ特性にまたがる40以上のデータセットに対して,ニューラルネットワークによる読み出しの有効性を示す。 我々は、近隣の集約数と異なる畳み込み演算子の数に対して、標準読み出しよりも一貫した改善を観察する。
  論文  参考訳（メタデータ） (2022-11-09T15:21:09Z)
• DeepSAT: An EDA-Driven Learning Framework for SAT [9.111341161918375]
  We present DeepSAT, a novel-to-end learning framework for the Boolean satisfiability (SAT) problem。 DeepSATは最先端の学習ベースSATソリューションに対して,大幅な精度向上を実現している。
  論文  参考訳（メタデータ） (2022-05-27T03:20:42Z)
• Transformer-based Machine Learning for Fast SAT Solvers and Logic Synthesis [63.53283025435107]
  CNFベースのSATとMaxSATは論理合成と検証システムの中心である。 そこで本研究では,Transformerアーキテクチャから派生したワンショットモデルを用いて,MaxSAT問題の解法を提案する。
  論文  参考訳（メタデータ） (2021-07-15T04:47:35Z)
• Prototypical Graph Contrastive Learning [141.30842113683775]
  本稿では,有意なサンプリングバイアスを緩和するために,プロトタイプグラフコントラスト学習(PGCL)手法を提案する。 具体的には、PGCLは、グラフデータの基盤となる意味構造を、意味論的に類似したグラフを同じグループにクラスタリングすることでモデル化し、同時に、同じグラフの異なる拡張に対するクラスタリング一貫性を奨励する。 クエリのために、PGCLはさらに、プロトタイプ(クラスタセントロイド)とクエリプロトタイプの間の距離に基づいて、負のサンプルを再重み付けする。
  論文  参考訳（メタデータ） (2021-06-17T16:45:31Z)
• RatE: Relation-Adaptive Translating Embedding for Knowledge Graph Completion [51.64061146389754]
  複素空間における新たな重み付き積の上に構築された関係適応変換関数を提案する。 次に、関係適応型翻訳埋め込み(RatE)アプローチを示し、各グラフを3倍にスコアする。
  論文  参考訳（メタデータ） (2020-10-10T01:30:30Z)

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

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