論文の概要: On the Hardness of Learning GNN-based SAT Solvers: The Role of Graph Ricci Curvature

• arxiv url: http://arxiv.org/abs/2508.21513v1
• Date: Fri, 29 Aug 2025 10:54:19 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-01 19:45:11.017108
• Title: On the Hardness of Learning GNN-based SAT Solvers: The Role of Graph Ricci Curvature
• Title（参考訳）: GNNベースのSATソルバの学習困難性について:グラフリッチ曲率の役割
• Authors: Geri Skenderi,
• Abstract要約: 本稿では,局所的な接続ボトルネックを定量化するRicci Curvature (RC) のレンズによる幾何学的説明を行う。 ランダムな k-SAT の公式から導かれる二部グラフは本質的に負の曲線であり、この曲がりは例の難易度とともに減少することを示す。 これに基づいて、GNNベースのSATソルバは、長距離依存が一定長の表現に圧縮できない現象であるオーバースカッシングによって影響を受けることを示す。
• 参考スコア（独自算出の注目度）: 3.4265828682659705
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Graph Neural Networks (GNNs) have recently shown promise as solvers for Boolean Satisfiability Problems (SATs) by operating on graph representations of logical formulas. However, their performance degrades sharply on harder instances, raising the question of whether this reflects fundamental architectural limitations. In this work, we provide a geometric explanation through the lens of graph Ricci Curvature (RC), which quantifies local connectivity bottlenecks. We prove that bipartite graphs derived from random k-SAT formulas are inherently negatively curved, and that this curvature decreases with instance difficulty. Building on this, we show that GNN-based SAT solvers are affected by oversquashing, a phenomenon where long-range dependencies become impossible to compress into fixed-length representations. We validate our claims empirically across different SAT benchmarks and confirm that curvature is both a strong indicator of problem complexity and can be used to predict performance. Finally, we connect our findings to design principles of existing solvers and outline promising directions for future work.
• Abstract（参考訳）: グラフニューラルネットワーク(GNN)は、論理式のグラフ表現を操作することで、ブール満足度問題(SAT)の解法として最近約束されている。 しかし、そのパフォーマンスは厳しいインスタンスで大幅に低下し、これが基本的なアーキテクチャ上の制約を反映しているかどうかという疑問が持ち上がった。 本研究では,局所的な接続ボトルネックを定量化するRicci Curvature (RC) のレンズによる幾何学的説明を行う。 ランダムな k-SAT の公式から導かれる二部グラフは本質的に負の曲線であり、この曲がりは例の難易度とともに減少することを示す。 これに基づいて、GNNベースのSATソルバは、長距離依存が一定長の表現に圧縮できない現象であるオーバースカッシングによって影響を受けることを示す。 我々は,様々なSATベンチマークで経験的にクレームを検証し,曲率が問題複雑性の強い指標であり,性能予測に使用できることを確認した。 最後に,既存の解法の設計原則に知見を結びつけるとともに,今後の研究に向けての有望な方向性を概説する。

関連論文リスト

• On Vanishing Gradients, Over-Smoothing, and Over-Squashing in GNNs: Bridging Recurrent and Graph Learning [15.409865070022951]
  グラフニューラルネットワーク(GNN)は、グラフ構造を利用してノード間で情報を伝達するモデルである。 GNNの単純な状態空間の定式化は、余分な訓練可能なパラメータコストを伴わずに、過度な平滑化と過度なスキャッシングを効果的に軽減できることを示す。
  論文  参考訳（メタデータ） (2025-02-15T14:43:41Z)
• Rethinking GNN Expressive Power from a Distributed Computational Model Perspective [21.723600297533835]
  事前処理と後処理を明確に指定した修正 CONGEST モデルなど,明確に定義された計算モデルを使用することによって,GNN 表現性を分析するためのより健全なフレームワークが提供される,と我々は主張する。 制約のない事前処理を許可したり、外部に計算された機能を組み込んだりすることは、これらの事前計算によって表現性が向上し、時には問題を引き起こす可能性があることを示す。 これらの否定的な結果にもかかわらず、計算モデルの観点から仮想ノードとエッジの効果を特徴付ける肯定的な結果も提示する。
  論文  参考訳（メタデータ） (2024-10-02T08:01:50Z)
• Generalization of Graph Neural Networks is Robust to Model Mismatch [84.01980526069075]
  グラフニューラルネットワーク(GNN)は、その一般化能力によってサポートされている様々なタスクにおいて、その効果を実証している。 本稿では,多様体モデルから生成される幾何グラフで動作するGNNについて検討する。 本稿では,そのようなモデルミスマッチの存在下でのGNN一般化の堅牢性を明らかにする。
  論文  参考訳（メタデータ） (2024-08-25T16:00:44Z)
• DeepRicci: Self-supervised Graph Structure-Feature Co-Refinement for Alleviating Over-squashing [72.70197960100677]
  グラフ構造学習(GSL)はグラフニューラルネットワーク(GNN)を改良したグラフで強化する上で重要な役割を果たしている。 GSLソリューションは、通常、タスク固有の監督(ノード分類)による構造改善に焦点を当てるか、GNN自体の固有の弱点を見落としている。 本稿では,典型的なGNNにおけるオーバー・スカッシングの問題を効果的に緩和する,自己教師付きグラフ構造-機能共分法について検討する。
  論文  参考訳（メタデータ） (2024-01-23T14:06:08Z)
• Learning to Reweight for Graph Neural Network [63.978102332612906]
  グラフニューラルネットワーク(GNN)は、グラフタスクに対して有望な結果を示す。 既存のGNNの一般化能力は、テストとトレーニンググラフデータの間に分散シフトが存在する場合に低下する。 本稿では,分布外一般化能力を大幅に向上させる非線形グラフデコリレーション法を提案する。
  論文  参考訳（メタデータ） (2023-12-19T12:25:10Z)
• Stable and Transferable Hyper-Graph Neural Networks [95.07035704188984]
  グラフニューラルネットワーク(GNN)を用いたハイパーグラフでサポートする信号処理アーキテクチャを提案する。 スペクトル類似性により任意のグラフにまたがってGNNの安定性と転送可能性の誤差をバウンドするフレームワークを提供する。
  論文  参考訳（メタデータ） (2022-11-11T23:44:20Z)
• Graph Neural Networks for Propositional Model Counting [1.0152838128195467]
  グラフネットワーク(GNN)は最近、論理的推論タスクの解決に活用されている。 本稿では, 自覚的GNNによって拡張され, #SAT 問題を大まかに解くために訓練された, Kuch 等の信念伝播のための GNN フレームワークに基づくアーキテクチャを提案する。
  論文  参考訳（メタデータ） (2022-05-09T17:03:13Z)
• Generalizing Graph Neural Networks on Out-Of-Distribution Graphs [51.33152272781324]
  トレーニンググラフとテストグラフの分散シフトを考慮せずにグラフニューラルネットワーク(GNN)を提案する。 このような環境では、GNNは、たとえ素早い相関であるとしても、予測のためのトレーニングセットに存在する微妙な統計的相関を利用する傾向がある。 本稿では,スプリアス相関の影響を排除するため,StableGNNと呼ばれる一般的な因果表現フレームワークを提案する。
  論文  参考訳（メタデータ） (2021-11-20T18:57:18Z)
• A Thorough View of Exact Inference in Graphs from the Degree-4 Sum-of-Squares Hierarchy [37.34153902687548]
  各エッジの1つの破損した観測からノードの未知の接地型バイナリラベリングを正確に回収する問題に取り組む。 この問題に対して、和の平方階層と呼ばれるリラクゼーションの階層を適用します。 我々は、緩和問題の双対の解がジョンソングラフとクネーサーグラフのエッジウェイトを見つけることに関連していることを示した。
  論文  参考訳（メタデータ） (2021-02-16T08:36:19Z)
• Implicit Graph Neural Networks [46.0589136729616]
  Indicit Graph Neural Networks (IGNN) と呼ばれるグラフ学習フレームワークを提案する。 IGNNは一貫して長距離依存を捉え、最先端のGNNモデルより優れている。
  論文  参考訳（メタデータ） (2020-09-14T06:04:55Z)

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

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