論文の概要: ReHub: Linear Complexity Graph Transformers with Adaptive Hub-Spoke Reassignment

• arxiv url: http://arxiv.org/abs/2412.01519v1
• Date: Mon, 02 Dec 2024 14:10:23 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-04 15:43:28.431519
• Title: ReHub: Linear Complexity Graph Transformers with Adaptive Hub-Spoke Reassignment
• Title（参考訳）: ReHub: 適応的なハブ-スポーク再割り当てを備えた線形複素グラフ変換器
• Authors: Tomer Borreda, Daniel Freedman, Or Litany,
• Abstract要約: 本稿では,効率的な再割り当て手法により線形複雑化を実現するグラフトランスフォーマーアーキテクチャReHubを提案する。 ReHubは航空会社のハブアンドスポークモデルからインスピレーションを得ており、フライトは固定数の仮想ノードに割り当てられている。 LRGB実験では,線形複雑度を維持しつつ,ベース手法であるNeural Atomsよりも一貫した改善が見られた。
• 参考スコア（独自算出の注目度）: 19.220112461156145
• License:
• Abstract: We present ReHub, a novel graph transformer architecture that achieves linear complexity through an efficient reassignment technique between nodes and virtual nodes. Graph transformers have become increasingly important in graph learning for their ability to utilize long-range node communication explicitly, addressing limitations such as oversmoothing and oversquashing found in message-passing graph networks. However, their dense attention mechanism scales quadratically with the number of nodes, limiting their applicability to large-scale graphs. ReHub draws inspiration from the airline industry's hub-and-spoke model, where flights are assigned to optimize operational efficiency. In our approach, graph nodes (spokes) are dynamically reassigned to a fixed number of virtual nodes (hubs) at each model layer. Recent work, Neural Atoms (Li et al., 2024), has demonstrated impressive and consistent improvements over GNN baselines by utilizing such virtual nodes; their findings suggest that the number of hubs strongly influences performance. However, increasing the number of hubs typically raises complexity, requiring a trade-off to maintain linear complexity. Our key insight is that each node only needs to interact with a small subset of hubs to achieve linear complexity, even when the total number of hubs is large. To leverage all hubs without incurring additional computational costs, we propose a simple yet effective adaptive reassignment technique based on hub-hub similarity scores, eliminating the need for expensive node-hub computations. Our experiments on LRGB indicate a consistent improvement in results over the base method, Neural Atoms, while maintaining a linear complexity. Remarkably, our sparse model achieves performance on par with its non-sparse counterpart. Furthermore, ReHub outperforms competitive baselines and consistently ranks among top performers across various benchmarks.
• Abstract（参考訳）: 本稿では,ノードと仮想ノード間の効率的な再割り当て手法により,線形複雑化を実現する新しいグラフトランスフォーマアーキテクチャReHubを提案する。 グラフトランスフォーマーは、メッセージパスグラフネットワークに見られるオーバースムーシングやオーバースキャッシングといった制限に対処しながら、長距離ノード通信を明示的に活用する能力のために、グラフ学習においてますます重要になっている。 しかし、その高密度な注意機構はノード数と2次的にスケールし、大規模グラフの適用性を制限する。 ReHubは航空会社のハブ・アンド・スポーク(ハブ・アンド・スポーク)モデルからインスピレーションを得ている。 提案手法では,グラフノード(スポークス)を,各モデル層における固定数の仮想ノード(ハブ)に動的に割り当てる。 最近の研究であるNeural Atoms (Li et al , 2024)は、そのような仮想ノードを利用することで、GNNベースラインよりも印象的で一貫した改善を実証している。 しかし、ハブの数を増やすと、通常は複雑さが増し、線形複雑性を維持するためにトレードオフが必要になる。 私たちのキーとなる洞察は、各ノードは、ハブの総数が大きければ、線形複雑性を達成するために、ハブの小さなサブセットとのみ対話する必要があるということです。 計算コストを増大させることなく、全てのハブを活用するために、ハブ-ハブ類似度スコアに基づく簡単な適応的再割り当て手法を提案し、高価なノード-ハブ計算の必要性を排除した。 LRGB実験では,線形複雑度を維持しながら,ベース手法であるNeural Atomsよりも一貫した改善が見られた。 注目すべきは、スパースモデルが非スパースモデルと同等の性能を達成することだ。 さらに、ReHubは競争のベースラインを上回り、さまざまなベンチマークで常にトップパフォーマーにランクインしている。

関連論文リスト

• Graph as a feature: improving node classification with non-neural graph-aware logistic regression [2.952177779219163]
  Graph-aware Logistic Regression (GLR) はノード分類タスク用に設計された非神経モデルである。 GNNにアクセスできる情報のごく一部しか使わない従来のグラフアルゴリズムとは異なり、提案モデルではノードの特徴とエンティティ間の関係を同時に活用する。
  論文  参考訳（メタデータ） (2024-11-19T08:32:14Z)
• Graph Transformers for Large Graphs [57.19338459218758]
  この研究は、モデルの特徴と重要な設計制約を識別することに焦点を当てた、単一の大規模グラフでの表現学習を前進させる。 この研究の重要な革新は、局所的な注意機構と組み合わされた高速な近傍サンプリング技術の作成である。 ogbn-products と snap-patents の3倍の高速化と16.8%の性能向上を報告し、ogbn-100M で LargeGT を5.9% の性能改善で拡張した。
  論文  参考訳（メタデータ） (2023-12-18T11:19:23Z)
• Degree-based stratification of nodes in Graph Neural Networks [66.17149106033126]
  グラフニューラルネットワーク(GNN)アーキテクチャを変更して,各グループのノードに対して,重み行列を個別に学習する。 このシンプルな実装変更により、データセットとGNNメソッドのパフォーマンスが改善されているようだ。
  論文  参考訳（メタデータ） (2023-12-16T14:09:23Z)
• 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)
• LSGNN: Towards General Graph Neural Network in Node Classification by Local Similarity [59.41119013018377]
  本稿では,ローカル類似性(LocalSim)を用いて,プラグイン・アンド・プレイモジュールとしても機能するノードレベルの重み付き融合を学習する。 そこで本研究では,より情報性の高いマルチホップ情報を抽出するための,新規かつ効率的な初期残留差分接続(IRDC)を提案する。 提案手法,すなわちローカル類似グラフニューラルネットワーク(LSGNN)は,ホモ親和性グラフとヘテロ親和性グラフの両方において,同等あるいは優れた最先端性能を提供できる。
  論文  参考訳（メタデータ） (2023-05-07T09:06:11Z)
• $\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)
• Dynamic Graph Message Passing Networks for Visual Recognition [112.49513303433606]
  長距離依存のモデリングは、コンピュータビジョンにおけるシーン理解タスクに不可欠である。 完全連結グラフはそのようなモデリングには有益であるが、計算オーバーヘッドは禁じられている。 本稿では,計算複雑性を大幅に低減する動的グラフメッセージパッシングネットワークを提案する。
  論文  参考訳（メタデータ） (2022-09-20T14:41:37Z)
• Position-based Hash Embeddings For Scaling Graph Neural Networks [8.87527266373087]
  グラフニューラルネットワーク(GNN)は、ノードのエゴネットワークのトポロジとエゴネットワークのノードの特徴を考慮したノード表現を演算する。 ノードが高品質な機能を持っていない場合、GNNはノードの埋め込みを計算するために埋め込み層を学び、それらを入力機能として使用する。 この埋め込みレイヤに関連するメモリを削減するため、NLPやレコメンダシステムのようなアプリケーションで一般的に使用されるハッシュベースのアプローチが利用可能である。 本稿では,グラフ内のノードの位置を利用して,必要なメモリを大幅に削減する手法を提案する。
  論文  参考訳（メタデータ） (2021-08-31T22:42:25Z)

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

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