論文の概要: Less Is More - On the Importance of Sparsification for Transformers and Graph Neural Networks for TSP

• arxiv url: http://arxiv.org/abs/2403.17159v1
• Date: Mon, 25 Mar 2024 20:16:16 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-27 19:36:07.878474
• Title: Less Is More - On the Importance of Sparsification for Transformers and Graph Neural Networks for TSP
• Title（参考訳）: より少ない - TSPのためのトランスフォーマーとグラフニューラルネットワークのスパーシフィケーションの重要性について
• Authors: Attila Lischka, Jiaming Wu, Rafael Basso, Morteza Haghir Chehreghani, Balázs Kulcsár,
• Abstract要約: 本稿では,旅行セールスマン問題(TSP)の最も関連性の高い部分のみにエンコーダを集中させるデータ前処理手法を提案する。 本稿では,GNNの適切なスパーシフィケーションとアンサンブルによって,アーキテクチャ全体の性能が大幅に向上することを示す。
• 参考スコア（独自算出の注目度）: 8.317022421446639
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Most of the recent studies tackling routing problems like the Traveling Salesman Problem (TSP) with machine learning use a transformer or Graph Neural Network (GNN) based encoder architecture. However, many of them apply these encoders naively by allowing them to aggregate information over the whole TSP instances. We, on the other hand, propose a data preprocessing method that allows the encoders to focus on the most relevant parts of the TSP instances only. In particular, we propose graph sparsification for TSP graph representations passed to GNNs and attention masking for TSP instances passed to transformers where the masks correspond to the adjacency matrices of the sparse TSP graph representations. Furthermore, we propose ensembles of different sparsification levels allowing models to focus on the most promising parts while also allowing information flow between all nodes of a TSP instance. In the experimental studies, we show that for GNNs appropriate sparsification and ensembles of different sparsification levels lead to substantial performance increases of the overall architecture. We also design a new, state-of-the-art transformer encoder with ensembles of attention masking. These transformers increase model performance from a gap of $0.16\%$ to $0.10\%$ for TSP instances of size 100 and from $0.02\%$ to $0.00\%$ for TSP instances of size 50.
• Abstract（参考訳）: 最近の研究の多くは、トランスフォーマーやグラフニューラルネットワーク(GNN)ベースのエンコーダアーキテクチャを使用して、機械学習によるTSP(Traking Salesman Problem)のようなルーティング問題に対処している。 しかし、それらの多くは、TSPインスタンス全体に情報を集約することで、これらのエンコーダを論理的に適用している。 一方、我々は、エンコーダがTSPインスタンスの最も関連性の高い部分のみに集中できるデータ前処理法を提案する。 特に、GNNに渡されるTSPグラフ表現のグラフスペーシングと、スパースTSPグラフ表現の隣接行列に対応する変換器に渡されるTSPインスタンスのアテンションマスキングを提案する。 さらに,モデルを最も有望な部分に集中させると同時に,TSPインスタンスの全ノード間の情報フローを可能とした,異なるスペーシングレベルのアンサンブルを提案する。 実験では,GNNが適切なスパーシフィケーションとアンサンブルの異なるスペーシフィケーションレベルを適切に組み合わせることで,アーキテクチャ全体の性能が大幅に向上することを示した。 我々はまた、注目マスキングのアンサンブルを備えた最先端のトランスフォーマーエンコーダを設計する。 これらの変換器はモデル性能を、サイズ100のTSPインスタンスでは0.16\%$から0.10\%$に、サイズ50のTSPインスタンスでは0.02\%$から0.00\%$に向上させる。

関連論文リスト

• Variable-size Symmetry-based Graph Fourier Transforms for image compression [65.7352685872625]
  可変サイズのグラフフーリエ変換を符号化フレームワークに導入する。 提案アルゴリズムは,ノード間の特定の対称接続を追加することにより,グリッド上の対称グラフを生成する。 実験により、SBGFTは、明示的な多重変換選択に統合された一次変換よりも優れていることが示された。
  論文  参考訳（メタデータ） (2024-11-24T13:00:44Z)
• Graph as Point Set [31.448841287258116]
  本稿では,相互接続ノードを独立点の集合に変換するグラフ・ツー・セット変換法を提案する。 これにより、セットエンコーダを使用してグラフから学習することが可能になり、グラフニューラルネットワークの設計空間が大幅に拡張される。 提案手法の有効性を示すために,グラフから変換された点集合を入力として受け入れる変換器アーキテクチャであるPoint Set Transformer (PST)を導入する。
  論文  参考訳（メタデータ） (2024-05-05T02:29:41Z)
• CT-MVSNet: Efficient Multi-View Stereo with Cross-scale Transformer [8.962657021133925]
  クロススケールトランス(CT)プロセスは、追加計算なしで異なる段階の表現を特徴付ける。 複数のスケールで異なる対話型アテンションの組み合わせを利用する適応型マッチング認識変換器(AMT)を導入する。 また、より細かなコストボリューム構成に大まかにグローバルな意味情報を埋め込む2機能ガイドアグリゲーション(DFGA)も提案する。
  論文  参考訳（メタデータ） (2023-12-14T01:33:18Z)
• SGFormer: Simplifying and Empowering Transformers for Large-Graph Representations [75.71298846760303]
  ノード特性予測ベンチマークにおいて,一層注意が驚くほど高い性能を示すことを示す。 提案手法をSGFormer (Simplified Graph Transformer) と呼ぶ。 提案手法は,大きなグラフ上にトランスフォーマーを構築する上で,独立性のある新たな技術パスを啓蒙するものである。
  論文  参考訳（メタデータ） (2023-06-19T08:03:25Z)
• Pointerformer: Deep Reinforced Multi-Pointer Transformer for the Traveling Salesman Problem [67.32731657297377]
  トラベリングセールスマン問題(TSP)は、もともと輸送と物流の領域で発生した古典的な経路最適化問題である。 近年, 深層強化学習は高い推論効率のため, TSP の解法として採用されている。 本稿では,多点変換器をベースとした新しいエンドツーエンドDRL手法であるPointerformerを提案する。
  論文  参考訳（メタデータ） (2023-04-19T03:48:32Z)
• Dynamic Graph Message Passing Networks for Visual Recognition [112.49513303433606]
  長距離依存のモデリングは、コンピュータビジョンにおけるシーン理解タスクに不可欠である。 完全連結グラフはそのようなモデリングには有益であるが、計算オーバーヘッドは禁じられている。 本稿では,計算複雑性を大幅に低減する動的グラフメッセージパッシングネットワークを提案する。
  論文  参考訳（メタデータ） (2022-09-20T14:41:37Z)
• Is Attention All NeRF Needs? [103.51023982774599]
  Generalizable NeRF Transformer (GNT) は、ソースビューから高速にNeRF(Neural Radiance Fields)を効率的に再構築する、純粋で統一されたトランスフォーマーベースのアーキテクチャである。 GNTは、2つのトランスフォーマーベースのステージをカプセル化することにより、一般化可能なニューラルシーン表現とレンダリングを実現する。
  論文  参考訳（メタデータ） (2022-07-27T05:09:54Z)
• FQ-ViT: Fully Quantized Vision Transformer without Retraining [13.82845665713633]
  本稿では,量子変換器の性能劣化と推論の複雑さを低減するための系統的手法を提案する。 完全に量子化された視覚変換器上で、我々は初めて精度の劣化(1%)を達成した。
  論文  参考訳（メタデータ） (2021-11-27T06:20:53Z)
• Pruning Self-attentions into Convolutional Layers in Single Path [89.55361659622305]
  ビジョントランスフォーマー(ViT)は、様々なコンピュータビジョンタスクに対して印象的なパフォーマンスを実現している。 トレーニング済みのViTを効率よく自動圧縮するSPViT(Single-Path Vision Transformer pruning)を提案する。 われわれのSPViTはDeiT-Bで52.0%のFLOPをトリミングできる。
  論文  参考訳（メタデータ） (2021-11-23T11:35:54Z)

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

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