論文の概要: Dual-GNN Multilevel Coarsening for Maximum Independent Set

• arxiv url: http://arxiv.org/abs/2609.25149v2
• Date: Wed, 23 Sep 2026 03:00:15 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-25 00:05:17.671722
• Title: Dual-GNN Multilevel Coarsening for Maximum Independent Set
• Title（参考訳）: 最大独立集合に対するデュアルGNN多重レベル粗大化
• Abstract要約: 最大独立集合 (MIS) 問題は、スケジューリング、リソース割り当て、ネットワーク解析の応用におけるNP-ハード最適化の基本的な問題である。 厳密な解法は高品質な解法や最適性を提供できるが、計算コストはグラフのサイズによって急速に増大する。 学習ベースの手法は、グラフインスタンスにまたがる構造パターンを活用するという代替手段を提供する。
• 参考スコア（独自算出の注目度）: 0.8670873561640903
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The maximum independent set (MIS) problem is a fundamental NP-hard combinatorial optimization problem with applications in scheduling, resource allocation, and network analysis. Exact solvers can provide high-quality solutions or optimality certificates, but their computational cost grows rapidly with graph size, while hand-crafted heuristics improve scalability at the expense of guarantees. Learning-based methods offer an alternative by exploiting structural patterns across graph instances, yet directly predicting independent sets can make global coordination difficult on large graphs. We instead use learning to guide multilevel graph coarsening while retaining combinatorial search for final decision making. Our Dual-GNN Multilevel Coarsening framework uses a Partition GNN to score candidate contractions and a Representative GNN to select top-k local independent-set states for each final cluster. Experiments on Erdős--Rényi graphs with up to 2,000 vertices demonstrate a favorable quality--runtime trade-off. On 500-vertex instances with certified optima, our method achieves an average independent-set size of 19.20, corresponding to 99.5\% of the optimal value of 19.30, while reducing the mean wall-clock time from 643.57 seconds for exact solving to 3.41 seconds, yielding an approximately 189$\times$ speedup. On larger graphs with 1,000 and 2,000 vertices, our method achieves the best mean solution quality among all evaluated methods. Moreover, although trained only on Erdős--Rényi graphs with edge probability $p=0.35$, the learned coarsening policy generalizes effectively across both unseen graph densities and structurally different graph families.
• Abstract（参考訳）: 最大独立集合 (MIS) 問題は、スケジューリング、資源割り当て、ネットワーク解析などの応用におけるNPハード組合せ最適化の基本的な問題である。 厳密な解法は高品質な解法や最適性証明を提供するが、計算コストはグラフのサイズとともに急速に増加し、手作りのヒューリスティックは保証を犠牲にしてスケーラビリティを向上させる。 学習ベースの手法は、グラフインスタンスにまたがる構造パターンを活用することで代替手段を提供するが、独立セットを直接予測することは、大きなグラフ上でのグローバルなコーディネーションを難しくする。 その代わりに、学習を用いて、最終決定のための組合せ探索を維持しながら、マルチレベルグラフの粗大化をガイドします。 我々のDual-GNN Multilevel Coarsening frameworkは、パーティションGNNを使用して候補契約をスコアし、代表GNNは最終クラスタごとにトップkのローカル独立セット状態を選択する。 2,000の頂点を持つエルデシュ-レーニグラフの実験は、良好な品質-実行時のトレードオフを示す。 最適値が19.30の99.5\%に相当する平均独立セットサイズ19.20の500頂点インスタンスに対して,平均壁時計時間を643.57秒から3.41秒に短縮し,約189$\times$スピードアップを実現した。 本手法は,1000頂点と2,000頂点の大きいグラフに対して,評価されたすべての方法の中で最高の平均解品質を達成できる。 さらに、エッジ確率$p=0.35$のエルデシュ-レーニグラフのみを訓練するが、学習された粗いポリシーは、目に見えないグラフ密度と構造的に異なるグラフ族の両方にわたって効果的に一般化する。

関連論文リスト

• GES-TSP: Graph Edge Sparsification for TSP [0.8670873561640903]
  Graph Edge Sparsification (GES) はユークリッド旅行セールスマン問題(TSP)の学習に基づくスペーシフィケーション手法である 提案手法は,異なるインスタンスに対するスペーシフィケーショングラフを適応的に生成し,グラフサイズを大幅に削減し,解法を高速化する。 実験の結果,提案手法はMATILDAデータセット上で最大95%のエッジを創出し,解のギャップを最適値の1%に抑えることができた。
  論文  参考訳（メタデータ） (2026-06-23T11:13:29Z)
• Not All Neighbors Matter: Understanding the Impact of Graph Sparsification on GNN Pipelines [4.381143313862113]
  グラフスペーサー化(Graph Sparsification)は、エッジを縮小してスペーサー地区を生成するテクニックである。 GNNのトレーニングとスペーサー付きグラフの推論に関する最初の総合的研究を行う。 以上の結果から,K-Neighborスペーサーは製品グラフ上のモデルサービス性能を0.7%の精度で11.7倍改善することがわかった。
  論文  参考訳（メタデータ） (2026-03-07T00:02:33Z)
• Closing the Generalization Gap in Parameter-efficient Federated Edge Learning [43.00634399799955]
  フェデレーションエッジラーニング(FEEL)は人工知能(AI)のための有望な基盤を提供する 限定的で異種なローカルデータセット、およびリソース制限されたデプロイメントは、モデル一般化とリソース利用の両方を著しく低下させる。 本稿では,モデル最小化と一般化選択を併用して,このような課題に対処するフレームワークを提案する。
  論文  参考訳（メタデータ） (2025-11-28T15:34:09Z)
• Lighter-X: An Efficient and Plug-and-play Strategy for Graph-based Recommendation through Decoupled Propagation [49.865020394064096]
  我々は,既存のGNNベースのレコメンデータアーキテクチャとシームレスに統合可能な,効率的かつモジュール化されたフレームワークである textbfLighter-X を提案する。 提案手法は,基本モデルの理論的保証と経験的性能を保ちながら,パラメータサイズと計算複雑性を大幅に低減する。 実験の結果、Lighter-Xはパラメータが大幅に少ないベースラインモデルに匹敵するパフォーマンスを実現している。
  論文  参考訳（メタデータ） (2025-10-11T08:33:08Z)
• GDSG: Graph Diffusion-based Solution Generator for Optimization Problems in MEC Networks [109.17835015018532]
  グラフ拡散型ソリューション生成(GDSG)法を提案する。 このアプローチは、おそらく最適な解に収束しながら、最適以下のデータセットを扱うように設計されている。 グラフニューラルネットワーク(GNN)を用いたマルチタスク拡散モデルとしてGDSGを構築し,高品質な解の分布を求める。
  論文  参考訳（メタデータ） (2024-12-11T11:13:43Z)
• Stochastic Re-weighted Gradient Descent via Distributionally Robust Optimization [14.23697277904244]
  Reweighted Gradient Descent (RGD) は、動的サンプル再重み付けによりディープニューラルネットワークの性能を向上させる新しい最適化手法である。 本稿では,教師付き学習,メタラーニング,ドメイン外一般化など,様々な学習課題におけるRGDの有効性を示す。
  論文  参考訳（メタデータ） (2023-06-15T15:58:04Z)
• Learning to Optimize Permutation Flow Shop Scheduling via Graph-based Imitation Learning [70.65666982566655]
  置換フローショップスケジューリング(PFSS)は製造業で広く使われている。 我々は,より安定かつ正確に収束を加速する専門家主導の模倣学習を通じてモデルを訓練することを提案する。 我々のモデルのネットワークパラメータはわずか37%に減少し、エキスパートソリューションに対する我々のモデルの解のギャップは平均6.8%から1.3%に減少する。
  論文  参考訳（メタデータ） (2022-10-31T09:46:26Z)
• Condensing Graphs via One-Step Gradient Matching [50.07587238142548]
  ネットワーク重みを訓練せずに1ステップのみの勾配マッチングを行う1ステップ勾配マッチング方式を提案する。 我々の理論的分析は、この戦略が実際のグラフの分類損失を減少させる合成グラフを生成することができることを示している。 特に、元のパフォーマンスの最大98%を近似しながら、データセットサイズを90%削減することが可能です。
  論文  参考訳（メタデータ） (2022-06-15T18:20:01Z)
• Learning to Sparsify Travelling Salesman Problem Instances [0.5985204759362747]
  プルーニングマシンラーニングを前処理のステップとして使用し、旅行セールスマンの問題をスパーシャライズするために正確なプログラミングアプローチを行います。 私たちの学習アプローチは、非常に少ないトレーニングデータを必要とし、数学的分析に適応可能です。
  論文  参考訳（メタデータ） (2021-04-19T14:35:14Z)

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

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