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

• arxiv url: http://arxiv.org/abs/2609.25149v1
• Date: Mon, 21 Sep 2026 07:24:38 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-23 18:04:04.045785
• Title: Dual-GNN Multilevel Coarsening for Maximum Independent Set
• Title（参考訳）: 最大独立集合に対するデュアルGNN多重レベル粗大化
• Abstract要約: トラベリングセールスマン問題(TSP)の大規模インスタンスの解決は、まさにコストがかかる。 本稿では,Euclidean TSPの学習に基づくスカラー化手法であるGraph Edge Sparsification (GES)を提案する。 提案手法は,異なるインスタンスに対するスペーシフィケーショングラフを適応的に生成し,グラフサイズを大幅に削減し,解法を高速化する。 実験の結果,提案手法はMATILDAデータセット上で最大95%のエッジを創出し,解のギャップを最適値の1%に抑えることができた。
• 参考スコア（独自算出の注目度）: 0.8670873561640903
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Solving large-scale instances of the Traveling Salesman Problem (TSP) exactly is computationally expensive. Researchers often employ graph sparsification methods to improve computational efficiency. Traditional sparsification methods typically rely on fixed heuristics and fail to fully exploit instance-specific structural information. In this paper, we propose Graph Edge Sparsification (GES), a learning-based sparsification approach for Euclidean TSP. By incorporating geometric structural information and combinatorial optimization technology, our proposed method adaptively generates a sparsification graph for different instances, significantly reducing the graph size and accelerating the solving process. Experimental results demonstrate that our sparsification method can prune up to 95\% of edges on the MATILDA dataset, while keeping the solution gap within 1\% of the optimal value. Moreover, our approach exhibits strong generalization capability on the TSPLIB benchmark.In some large-scale instances, the pruning rate exceeds 99\%, while the optimality gap remains below 1\%.
• Abstract（参考訳）: トラベリングセールスマン問題(TSP)の大規模インスタンスの解決には計算コストがかかる。 研究者はしばしば計算効率を改善するためにグラフスペーシフィケーション法を用いる。 従来のスパーシフィケーション手法は一般に固定ヒューリスティックに依存しており、インスタンス固有の構造情報を完全に活用できない。 本稿では,Euclidean TSPの学習に基づくスカラー化手法であるGraph Edge Sparsification (GES)を提案する。 幾何構造情報と組合せ最適化技術を組み合わせることにより,提案手法は異なるインスタンスに対してスペーシフィケーショングラフを適応的に生成し,グラフサイズを大幅に削減し,解法を高速化する。 実験結果から,本手法は最適値の1/%以内の解ギャップを維持しながら,MATILDAデータセット上で最大95%のエッジを創出できることがわかった。 さらに, TSPLIBベンチマークでは, プルーニング率が 99 % を超え, 最適性ギャップが 1 % 以下である場合も少なくない。

関連論文リスト

• 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)

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

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