論文の概要: Machine Learning for Two-Stage Graph Sparsification for the Travelling Salesman Problem

• arxiv url: http://arxiv.org/abs/2604.20236v1
• Date: Wed, 22 Apr 2026 06:40:05 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-23 15:36:10.993129
• Title: Machine Learning for Two-Stage Graph Sparsification for the Travelling Salesman Problem
• Title（参考訳）: トラベルセールスマン問題に対する2段階グラフスパーシフィケーションのための機械学習
• Authors: Bo-Cheng Lin, Yi Mei, Mengjie Zhang,
• Abstract要約: グラフのスパーシフィケーションは簡単ではありません – エッジの数が多過ぎると時間の無駄になるのです。 2つの主要な解法、$-Nearest と POPMUSIC は、高品質な候補グラフを生成するが、すべてのインスタンスサイズと分布に疎結合で信頼性のあるものは存在しない。 そこで我々は2段階グラフスペーシフィケーション手法を提案する。Stage1は$$-NearestとPOPMUSICを統合してリコールを最大化する。
• 参考スコア（独自算出の注目度）: 4.184504903540304
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: High-performance TSP solvers like LKH search within a sparsified candidate graph rather than over all possible edges. Graph sparsification is non-trivial: keep too many edges and the solver wastes time; cut too many and it loses edges that belong to the optimal tour. The two leading heuristic methods, $α$-Nearest and POPMUSIC, produce high-quality candidate graphs, but no single heuristic is both sparse and reliable across all instance sizes and distributions. Machine learning methods can potentially learn better sparsification models. However, existing approaches operate on the complete graph, which is expensive and mostly restricted to Euclidean distances. To address this issue, we propose a two-stage graph sparsification approach: Stage~1 takes the union of $α$-Nearest and POPMUSIC to maximise recall; Stage~2 trains a single model to reduce density. We conducted experiments across four TSPLIB distance types, five spatial distributions, and problem sizes from 50 to 500. The two-stage approach substantially reduces candidate-graph density while retaining high coverage, generalises across distance types and distributions, outperforms recent neural sparsification methods that are restricted to Euclidean distances, and becomes increasingly valuable at larger scales where single-stage heuristics degrade.
• Abstract（参考訳）: LKHのような高性能なTSPソルバは、可能なすべてのエッジではなく、疎化候補グラフ内を探索する。 グラフのスパーシフィケーションは簡単ではありません – エッジが多過ぎるとソルバが時間の無駄になるのです。 二つの主要なヒューリスティックな方法、$α$-Nearest と POPMUSIC は、高品質な候補グラフを生成するが、すべてのインスタンスサイズと分布において、単一のヒューリスティックはスパースかつ信頼性がない。 機械学習の手法は、より良いスパーシフィケーションモデルを学ぶことができる。 しかし、既存のアプローチは、コストが高く、主にユークリッド距離に制限される完全グラフで機能する。 この問題に対処するために、Stage~1は$α$-NearestとPOPMUSICを結合してリコールを最大化し、Stage~2は密度を減らすために単一のモデルを訓練する。 我々は,4種類のTSPLIB距離タイプ,5つの空間分布,50から500までの問題サイズについて実験を行った。 2段階のアプローチは、高いカバレッジを維持しながら、候補グラフ密度を大幅に減少させ、距離のタイプや分布を一般化し、ユークリッド距離に制限された最近のニューラルスパーシフィケーション法を上回り、シングルステージヒューリスティックが劣化する大規模ではますます価値が増している。

関連論文リスト

• Graph Sparsification via Mixture of Graphs [67.40204130771967]
  そこで我々はMixture-of-Graphs (MoG)を導入し、各ノードに対して動的に調整されたプルーニングソリューションを選択する。 MoGには複数のスパシファイアの専門家が組み込まれており、それぞれが独自のスパーシリティレベルとプルーニング基準によって特徴付けられ、各ノードに対して適切な専門家を選択する。 5つのGNNを備えた4つの大規模OGBデータセットと2つのスーパーピクセルデータセットの実験により、MoGはより高い空間レベルのサブグラフを識別することを示した。
  論文  参考訳（メタデータ） (2024-05-23T07:40:21Z)
• Probabilistic Routing for Graph-Based Approximate Nearest Neighbor Search [3.934351369702082]
  高次元空間における近似近接探索(ANNS)は、機械学習分野における重要な課題である。 本稿では,グラフ内のノードの近傍を探索する際の確率的保証を提供する手法を提案する。 次に,グラフ内のどの近傍が正確な距離計算を行うべきかを効率的に同定する新しい手法PEOを紹介する。
  論文  参考訳（メタデータ） (2024-02-17T18:08:37Z)
• Two Heads Are Better Than One: Boosting Graph Sparse Training via Semantic and Topological Awareness [80.87683145376305]
  グラフニューラルネットワーク(GNN)は、様々なグラフ学習タスクに優れるが、大規模グラフに適用した場合、計算上の課題に直面している。 データレベルで空間を動的に操作するグラフスパーストレーニング(GST)を提案する。 GSTは、最大位相整合性と性能劣化のないスパースグラフを生成する。
  論文  参考訳（メタデータ） (2024-02-02T09:10:35Z)
• LeNSE: Learning To Navigate Subgraph Embeddings for Large-Scale Combinatorial Optimisation [6.316693022958222]
  ユークリッド部分グラフの埋め込みを地図として用いて,可能な部分グラフの空間をナビゲートする方法を学習する強化学習アルゴリズムを提案する。 LeNSEは、グラフ全体への埋め込みの実行によって見いだされたソリューションに匹敵するソリューションをもたらす小さなサブグラフを識別するが、全体の実行時間のごく一部にはならない。
  論文  参考訳（メタデータ） (2022-05-20T11:54:03Z)
• Near-Optimal Sparse Allreduce for Distributed Deep Learning [23.62360119212958]
  コミュニケーションのオーバーヘッドは、大規模なディープラーニングモデルを大規模にトレーニングする上で、大きな障害のひとつです。 本稿では,スパース勾配を用いた分散トレーニング手法であるO$k$-Top$k$を提案する。
  論文  参考訳（メタデータ） (2022-01-19T13:56:57Z)
• Effective Model Sparsification by Scheduled Grow-and-Prune Methods [73.03533268740605]
  本稿では,高密度モデルの事前学習を伴わない新規なGrow-and-prune(GaP)手法を提案する。 実験により、そのようなモデルは様々なタスクにおいて80%の間隔で高度に最適化された高密度モデルの品質に適合または打ち勝つことができることが示された。
  論文  参考訳（メタデータ） (2021-06-18T01:03:13Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  我々は高密度サブグラフ発見のための新しい学習問題を導入する。 まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。 そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-06-24T11:37:33Z)
• Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model [50.38446482252857]
  本稿では、生成モデル(シミュレータ)へのアクセスを想定して、強化学習のサンプル効率について検討する。 最初に$gamma$-discounted infinite-horizon Markov decision process (MDPs) with state space $mathcalS$ and action space $mathcalA$を考える。 対象の精度を考慮すれば,モデルに基づく計画アルゴリズムが最小限のサンプルの複雑さを実現するのに十分であることを示す。
  論文  参考訳（メタデータ） (2020-05-26T17:53:18Z)

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

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