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

• arxiv url: http://arxiv.org/abs/2506.00533v4
• Date: Fri, 26 Sep 2025 02:01:49 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-29 14:23:57.416182
• Title: RsGCN: Subgraph-Based Rescaling Enhances Generalization of GCNs for Solving Traveling Salesman Problems
• Title（参考訳）: RsGCN: トラベリングセールスマン問題を解決するためのGCNの一般化を促進するサブグラフベース再スケーリング
• Authors: Junquan Huang, Zong-Gan Chen, Yuncheng Jiang, Zhi-Hui Zhan,
• Abstract要約: GCNベースの旅行セールスマン問題(TSP)は、TSPのクロススケール一般化の貧弱さと高いトレーニングコストの2つの重要な課題に直面している。 グラフ畳み込みネットワーク(RsGCN)を提案する。 統一された部分グラフの観点で、RsGCNは低コストで小規模のTSPからスケール一般化可能な表現を効率的に学習することができる。 RsGCN と RBS を併用したアーキテクチャにより,本手法は目覚ましい一般化と訓練コストの低減を実現している。
• 参考スコア（独自算出の注目度）: 10.605940576092507
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: GCN-based traveling salesman problem (TSP) solvers face two critical challenges: poor cross-scale generalization for TSPs and high training costs. To address these challenges, we propose a Subgraph-Based Rescaling Graph Convolutional Network (RsGCN). Focusing on the scale-dependent features (i.e., features varied with problem scales) related to nodes and edges, we design the subgraph-based rescaling to normalize edge lengths of subgraphs. Under a unified subgraph perspective, RsGCN can efficiently learn scale-generalizable representations from small-scale TSPs at low cost. To exploit and assess the heatmaps generated by RsGCN, we design a Reconstruction-Based Search (RBS), in which a reconstruction process based on adaptive weight is incorporated to help avoid local optima. Based on a combined architecture of RsGCN and RBS, our solver achieves remarkable generalization and low training cost: with only 3 epochs of training on a 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 advanced 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（参考訳）: GCNベースの旅行セールスマン問題(TSP)は、TSPのクロススケール一般化の貧弱さと高いトレーニングコストの2つの重要な課題に直面している。 これらの課題に対処するために、サブグラフベースのグラフ畳み込みネットワーク(RsGCN)を提案する。 ノードやエッジに関連するスケール依存的な特徴(すなわち問題スケールによって異なる特徴)に着目して、サブグラフのエッジ長を正規化するためのサブグラフベースの再スケーリングを設計する。 統一された部分グラフの観点で、RsGCNは低コストで小規模のTSPからスケール一般化可能な表現を効率的に学習することができる。 RsGCN が生成する熱マップを活用・評価するために,適応重みに基づく再構成処理を組み込んだリコンストラクションベースサーチ (RBS) を設計した。 RsGCN と RBS のアーキテクチャを組み合わせることで,最大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)
• Joint Edge-Model Sparse Learning is Provably Efficient for Graph Neural Networks [89.28881869440433]
  本稿では,グラフニューラルネットワーク(GNN)における結合エッジモデルスパース学習の理論的特徴について述べる。 解析学的には、重要なノードをサンプリングし、最小のマグニチュードでプルーニングニューロンをサンプリングすることで、サンプルの複雑さを減らし、テスト精度を損なうことなく収束を改善することができる。
  論文  参考訳（メタデータ） (2023-02-06T16:54:20Z)
• $\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)
• Temporal Attention-Augmented Graph Convolutional Network for Efficient Skeleton-Based Human Action Recognition [97.14064057840089]
  グラフネットワーク(GCN)はユークリッド以外のデータ構造をモデル化するのに非常に成功した。 ほとんどのGCNベースのアクション認識手法は、計算量の多いディープフィードフォワードネットワークを使用して、全てのスケルトンをアクションで処理する。 本稿では,骨格に基づく行動認識の効率を高めるための時間的アテンションモジュール(TAM)を提案する。
  論文  参考訳（メタデータ） (2020-10-23T08:01:55Z)

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

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