論文の概要: RsGCN: Rescaling Enhances Generalization of GCNs for Solving Scalable Traveling Salesman Problems

• arxiv url: http://arxiv.org/abs/2506.00533v1
• Date: Sat, 31 May 2025 12:40:02 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-04 21:47:33.182617
• Title: RsGCN: Rescaling Enhances Generalization of GCNs for Solving Scalable Traveling Salesman Problems
• Title（参考訳）: RsGCN: スケーラブルなトラベリングセールスマン問題を解決するためにGCNの一般化を促進する
• Authors: Junquan Huang, Zong-Gan Chen, Yuncheng Jiang, Zhi-Hui Zhan,
• Abstract要約: 本稿では、スケーラブルなニューラル走行セールスマン問題(TSP)解決のための新しいRescaling Graph Convolutional Network(RsGCN)を提案する。 RsGCNは、(1)隣接ノードを再スケーリングして、各ノードに対する隣接ノード数の均一なサブグラフを構築することにより、機能一般化を強化する。 さらに、RsGCNでは、混合スケールデータセットと双方向ロスによる効率的なトレーニング戦略が使用される。 RsGCN と Re2Opt を併用したアーキテクチャを基礎として,我々の解法は目覚ましい一般化と訓練コストの低減を実現している。
• 参考スコア（独自算出の注目度）: 11.276725259527005
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Neural traveling salesman problem (TSP) solvers face two critical challenges: poor generalization for scalable TSPs and high training costs. To address these challenges, we propose a new Rescaling Graph Convolutional Network (RsGCN). Focusing on the scale-dependent features (i.e., features varied with problem scales) related to nodes and edges that influence the sensitivity of GCNs to the problem scales, a Rescaling Mechanism in RsGCN enhances the generalization capability by (1) rescaling adjacent nodes to construct a subgraph with a uniform number of adjacent nodes for each node across various scales of TSPs, which stabilizes the graph message aggregation; (2) rescaling subgraph edges to adjust the lengths of subgraph edges to the same magnitude, which maintains numerical consistency. In addition, an efficient training strategy with a mixed-scale dataset and bidirectional loss is used in RsGCN. To fully exploit the heatmaps generated by RsGCN, we design an efficient post-search algorithm termed Re2Opt, in which a reconstruction process based on adaptive weight is incorporated to help avoid local optima. Based on a combined architecture of RsGCN and Re2Opt, our solver achieves remarkable generalization and low training cost: with only 3 epochs of training on the mixed-scale dataset containing instances with up to 100 nodes, it can be generalized successfully to 10K-node instances without any fine-tuning. Extensive experiments demonstrate our state-of-the-art performance across uniform distribution instances of 9 different scales from 20 to 10K nodes and 78 real-world instances from TSPLIB, while requiring the fewest learnable parameters and training epochs among neural competitors.
• Abstract（参考訳）: ニューラルトラベルセールスマン問題(TSP)は2つの重要な課題に直面している。 これらの課題に対処するために、新しいRescaling Graph Convolutional Network (RsGCN)を提案する。 問題スケールに対するGCNの感度に影響を与えるノードやエッジに関連するスケール依存的な特徴(すなわち、問題スケールによって変化する特徴)に注目して、RsGCNにおける再スケーリングメカニズムは、(1)隣接ノードをリスケーリングして、グラフメッセージの集約を安定化するTSPの様々なスケールにまたがる各ノードの隣接ノード数の均一なサブグラフを構築することにより、一般化能力を向上し、(2)サブグラフエッジをリスケーリングして、サブグラフエッジの長さを同じ大きさに調整し、数値的一貫性を維持する。 さらに、RsGCNでは、混合スケールデータセットと双方向ロスによる効率的なトレーニング戦略が使用される。 RsGCN が生成する熱マップを完全に活用するために,Re2Opt と呼ばれる効率的なポストサーチアルゴリズムを設計した。 RsGCNとRe2Optのアーキテクチャを組み合わせることで,最大100ノードのインスタンスを含む混合スケールデータセット上でのトレーニングの3エポックで,微調整をせずに10Kノードインスタンスに最適化できるという,目覚ましい一般化と低トレーニングコストを実現した。 大規模な実験では、20から10Kノードから78の現実世界インスタンスまで、9つの異なるスケールの分散インスタンスにまたがって、最先端のパフォーマンスを実証しています。

関連論文リスト

• TSC: A Simple Two-Sided Constraint against Over-Smoothing [17.274727377858873]
  グラフ畳み込みニューラルネットワーク(GCN)のための単純な2次元制約(TSC)を導入する。 ランダムマスキングは、隣人からの情報の集約の度合いを調整するために、表現行列の列に作用する。 表現行列の行に適用される対照的な制約は、ノードの識別可能性を高める。
  論文  参考訳（メタデータ） (2024-08-06T12:52:03Z)
• 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)
• $\rm A^2Q$: Aggregation-Aware Quantization for Graph Neural Networks [18.772128348519566]
  グラフニューラルネットワーク(GNN)のための集約型混合精度量子化(rm A2Q$)を提案する。 本手法は,ノードレベルのタスクとグラフレベルのタスクで最大11.4%,9.5%の精度向上を実現し,専用ハードウェアアクセラレータで最大2倍の高速化を実現する。
  論文  参考訳（メタデータ） (2023-02-01T02:54:35Z)
• Binary Graph Convolutional Network with Capacity Exploration [58.99478502486377]
  ネットワークパラメータと入力ノード属性の両方を二項化するバイナリグラフ畳み込みネットワーク(Bi-GCN)を提案する。 我々のBi-GCNは、ネットワークパラメータと入力データの両方で平均31倍のメモリ消費を削減でき、推論速度を平均51倍に加速できる。
  論文  参考訳（メタデータ） (2022-10-24T12:05:17Z)
• Comprehensive Graph Gradual Pruning for Sparse Training in Graph Neural Networks [52.566735716983956]
  本稿では,CGPと呼ばれるグラフの段階的プルーニングフレームワークを動的にGNNに提案する。 LTHに基づく手法とは異なり、提案手法では再学習を必要とせず、計算コストを大幅に削減する。 提案手法は,既存の手法の精度を一致させたり,あるいは超えたりしながら,トレーニングと推論の効率を大幅に向上させる。
  論文  参考訳（メタデータ） (2022-07-18T14:23:31Z)
• Non-Recursive Graph Convolutional Networks [33.459371861932574]
  非再帰グラフ畳み込みネットワーク(NRGCN)と呼ばれる新しいアーキテクチャを提案し、GCNのトレーニング効率と学習パフォーマンスの両方を改善します。 NRGCNは、内部層凝集と層非依存サンプリングに基づいて、各ノードの隣人のホップを表す。 このようにして、各ノードは、隣人の各ホップから独立して抽出された情報を連結することで直接表現することができる。
  論文  参考訳（メタデータ） (2021-05-09T08:12:18Z)
• MG-GCN: Fast and Effective Learning with Mix-grained Aggregators for Training Large Graph Convolutional Networks [20.07942308916373]
  グラフ畳み込みネットワーク(GCN)は、隣人層の情報を層ごとに集約することでノードの埋め込みを生成する。 GCNの高計算とメモリコストにより、大きなグラフのトレーニングが不可能になる。 MG-GCNと呼ばれる新しいモデルでは、精度、トレーニング速度、収束速度、メモリコストの点で最先端のパフォーマンスを実現している。
  論文  参考訳（メタデータ） (2020-11-17T14:51:57Z)

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

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