論文の概要: AGDN: Learning to Solve Traveling Salesman Problem with Anisotropic Graph Diffusion Network

• arxiv url: http://arxiv.org/abs/2606.19185v1
• Date: Wed, 17 Jun 2026 15:24:37 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-18 17:16:51.240011
• Title: AGDN: Learning to Solve Traveling Salesman Problem with Anisotropic Graph Diffusion Network
• Title（参考訳）: AGDN:異方性グラフ拡散ネットワークを用いたトラベリングセールスマン問題の解法
• Authors: Bolin Shen, Ziwei Huang, Zhiguang Cao, Yushun Dong,
• Abstract要約: Anisotropic Graph Diffusion Network (AGDN) はトラベリングセールスマン問題(TSP)を解決するために設計された新しいグラフニューラルネットワークフレームワークである。 提案手法は,1) 完全連結TSPグラフにおける情報的トポロジ的事前の欠如,2) グラフスペーシフィケーション手法により最適解における接続ノードの喪失,の2つの問題に対処する。 AGDNは、競争力を維持しながら、既存の手法を一貫して上回る。
• 参考スコア（独自算出の注目度）: 50.69521065962045
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Traveling Salesman Problem (TSP) is a cornerstone of combinatorial optimization and arises in many practical scenarios. Although graph-based learning approaches have been explored for TSP, the question of how to exploit graph structure more effectively remains open. We present the Anisotropic Graph Diffusion Network (AGDN), a new Graph Neural Network framework designed to solve TSP. Our method tackles two central difficulties: (1) the lack of informative topological prior in fully connected TSP graphs, and (2) losing connected nodes in the optimal solution after the commonly used graph sparsification techniques. To overcome these issues, we construct a MixScore transition matrix that merges node similarity with pairwise distance, and we develop an anisotropic graph diffusion strategy that supports efficient information exchange across multiple hops. Comprehensive experiments spanning diverse instance sizes and node distributions show that AGDN consistently outperforms existing methods while keeping computation time competitive. Furthermore, AGDN generalizes well to problem sizes and distributions beyond those seen during training. The implementation is publicly available at: https://github.com/LabRAI/AGDN.
• Abstract（参考訳）: トラベリングセールスマン問題(TSP)は組合せ最適化の基盤であり、多くの実践的なシナリオで発生する。 TSPのためにグラフベースの学習アプローチが検討されているが、グラフ構造をより効果的に活用する方法の問題は未解決のままである。 本稿では,TSP を解決するために設計された新しいグラフニューラルネットワークフレームワークである Anisotropic Graph Diffusion Network (AGDN) を提案する。 提案手法は,1) 完全連結TSPグラフにおける情報的トポロジ的事前の欠如,2) グラフスペーシフィケーション手法により最適解における接続ノードの喪失,の2つの問題に対処する。 これらの問題を克服するために、ノード類似性をペア距離にマージするMixScore遷移行列を構築し、複数のホップ間の効率的な情報交換を支援する異方性グラフ拡散戦略を開発する。 多様なインスタンスサイズとノード分布にまたがる包括的な実験により、AGDNは計算時間を競争力を維持しながら、既存のメソッドを一貫して上回ります。 さらに、AGDNはトレーニング中に見られるもの以上の問題のサイズや分布を一般化する。 実装は、https://github.com/LabRAI/AGDNで公開されている。

関連論文リスト

• Scalable Graph Compressed Convolutions [68.85227170390864]
  ユークリッド畳み込みのための入力グラフのキャリブレーションに置換を適用する微分可能手法を提案する。 グラフキャリブレーションに基づいて,階層型グラフ表現学習のための圧縮畳み込みネットワーク(CoCN)を提案する。
  論文  参考訳（メタデータ） (2024-07-26T03:14:13Z)
• T-GAE: Transferable Graph Autoencoder for Network Alignment [79.89704126746204]
  T-GAEはグラフオートエンコーダフレームワークで、GNNの転送性と安定性を活用して、再トレーニングなしに効率的なネットワークアライメントを実現する。 実験の結果、T-GAEは最先端の最適化手法と最高のGNN手法を最大38.7%、50.8%で上回っていることがわかった。
  論文  参考訳（メタデータ） (2023-10-05T02:58:29Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。 効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。 グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
  論文  参考訳（メタデータ） (2023-06-14T09:21:15Z)
• Learning Strong Graph Neural Networks with Weak Information [64.64996100343602]
  我々は、弱い情報(GLWI)を用いたグラフ学習問題に対する原則的アプローチを開発する。 非完全構造を持つ入力グラフ上で長距離情報伝搬を行うデュアルチャネルGNNフレームワークであるD$2$PTを提案するが、グローバルな意味的類似性を符号化するグローバルグラフも提案する。
  論文  参考訳（メタデータ） (2023-05-29T04:51:09Z)
• FeatureNorm: L2 Feature Normalization for Dynamic Graph Embedding [39.527059564775094]
  グラフ畳み込みネットワーク(GCN)は、非ユークリッドアプリケーションドメインで広く研究され、利用されている。 本稿では,まずノード埋め込み空間における縮小特性を解析し,単純で汎用的な手法を設計する。 実世界の4つの動的グラフデータセットと競合ベースラインモデルの比較実験により,提案手法の有効性が示された。
  論文  参考訳（メタデータ） (2021-02-27T09:13:47Z)
• Co-embedding of Nodes and Edges with Graph Neural Networks [13.020745622327894]
  グラフ埋め込みは、高次元および非ユークリッド特徴空間でデータ構造を変換しエンコードする方法である。 CensNetは一般的なグラフ埋め込みフレームワークで、ノードとエッジの両方を潜在機能空間に埋め込む。 提案手法は,4つのグラフ学習課題における最先端のパフォーマンスを達成または一致させる。
  論文  参考訳（メタデータ） (2020-10-25T22:39:31Z)
• A Generative Graph Method to Solve the Travelling Salesman Problem [1.552282932199974]
  我々は,旅行セールスマン問題(TSP)を概ね解決するために,生成的アプローチである新しいグラフ学習ネットワーク(GLN)を提案する。 GLNモデルは、トレーニングデータセットとしてTSPインスタンスのパターンを直接学習し、グラフプロパティをエンコードし、異なるノードの埋め込みをマージして、最適なツアーを出力する。
  論文  参考訳（メタデータ） (2020-07-09T17:23:55Z)
• Graph Representation Learning Network via Adaptive Sampling [4.996520403438455]
  Graph Attention Network(GAT)とGraphSAGEは、グラフ構造化データを操作するニューラルネットワークアーキテクチャである。 GraphSAGEが提起した課題のひとつは、グラフ構造に基づいた隣の機能をスマートに組み合わせる方法だ。 より効率的で,異なるエッジ型情報を組み込むことが可能な,これらの問題に対処する新しいアーキテクチャを提案する。
  論文  参考訳（メタデータ） (2020-06-08T14:36:20Z)

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

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