論文の概要: What Improves the Generalization of Graph Transformers? A Theoretical Dive into the Self-attention and Positional Encoding

• arxiv url: http://arxiv.org/abs/2406.01977v1
• Date: Tue, 4 Jun 2024 05:30:16 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-05 17:50:34.164751
• Title: What Improves the Generalization of Graph Transformers? A Theoretical Dive into the Self-attention and Positional Encoding
• Title（参考訳）: グラフ変換器の一般化を改善するものは何か? : 自己注意と位置エンコーディングへの理論的考察
• Authors: Hongkang Li, Meng Wang, Tengfei Ma, Sijia Liu, Zaixi Zhang, Pin-Yu Chen,
• Abstract要約: 自己アテンションと位置エンコーディングを組み込んだグラフトランスフォーマーは、さまざまなグラフ学習タスクのための強力なアーキテクチャとして登場した。 本稿では,半教師付き分類のための浅いグラフ変換器の理論的検討について紹介する。
• 参考スコア（独自算出の注目度）: 67.59552859593985
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Graph Transformers, which incorporate self-attention and positional encoding, have recently emerged as a powerful architecture for various graph learning tasks. Despite their impressive performance, the complex non-convex interactions across layers and the recursive graph structure have made it challenging to establish a theoretical foundation for learning and generalization. This study introduces the first theoretical investigation of a shallow Graph Transformer for semi-supervised node classification, comprising a self-attention layer with relative positional encoding and a two-layer perceptron. Focusing on a graph data model with discriminative nodes that determine node labels and non-discriminative nodes that are class-irrelevant, we characterize the sample complexity required to achieve a desirable generalization error by training with stochastic gradient descent (SGD). This paper provides the quantitative characterization of the sample complexity and number of iterations for convergence dependent on the fraction of discriminative nodes, the dominant patterns, and the initial model errors. Furthermore, we demonstrate that self-attention and positional encoding enhance generalization by making the attention map sparse and promoting the core neighborhood during training, which explains the superior feature representation of Graph Transformers. Our theoretical results are supported by empirical experiments on synthetic and real-world benchmarks.
• Abstract（参考訳）: 自己アテンションと位置エンコーディングを組み込んだグラフトランスフォーマーは、最近、さまざまなグラフ学習タスクのための強力なアーキテクチャとして登場した。 その印象的な性能にもかかわらず、層間の複雑な非凸相互作用と再帰的なグラフ構造は、学習と一般化の理論的基盤を確立することを困難にしている。 本研究では,半教師付きノード分類のための浅層グラフ変換器について,相対的な位置エンコーディングと2層パーセプトロンを備えた自己アテンション層を含む理論的検討を行った。 ノードラベルと非識別ノードを識別する識別ノードを持つグラフデータモデルに着目し,確率勾配降下法(SGD)を訓練することにより,望ましい一般化誤差を達成するために必要なサンプルの複雑さを特徴付ける。 本稿では,識別ノードの分数,支配的パターン,初期モデル誤差に依存する収束の複雑さと回数を定量的に評価する。 さらに,注意マップのスパース化と学習中のコアエリアの促進により,自己注意と位置エンコーディングが一般化を促進することを示し,グラフ変換器の優れた特徴表現を説明する。 我々の理論結果は、合成および実世界のベンチマークに関する実証実験によって支持されている。

関連論文リスト

• Unitary convolutions for learning on graphs and groups [0.9899763598214121]
  我々は、訓練中により安定したより深いネットワークを可能にするユニタリグループ畳み込みについて研究する。 論文の主な焦点はグラフニューラルネットワークであり、ユニタリグラフの畳み込みがオーバー・スムーシングを確実に回避していることを示す。 実験結果から,ベンチマークデータセット上でのユニタリグラフ畳み込みネットワークの競合性能が確認できた。
  論文  参考訳（メタデータ） (2024-10-07T21:09:14Z)
• Gradformer: Graph Transformer with Exponential Decay [69.50738015412189]
  グラフ変換器(GT)の自己保持機構は、グラフの帰納バイアス、特に構造に関するバイアスを見落としている。 本稿では,GTと本質的帰納バイアスを革新的に統合するGradformerを提案する。 GradformerはグラフニューラルネットワークやGTベースラインモデルよりも、さまざまなグラフ分類や回帰タスクにおいて一貫して優れています。
  論文  参考訳（メタデータ） (2024-04-24T08:37:13Z)
• Deep Contrastive Graph Learning with Clustering-Oriented Guidance [61.103996105756394]
  グラフ畳み込みネットワーク(GCN)は、グラフベースのクラスタリングを改善する上で大きな可能性を秘めている。 モデルはGCNを適用するために初期グラフを事前に推定する。 一般的なデータクラスタリングには,Deep Contrastive Graph Learning (DCGL)モデルが提案されている。
  論文  参考訳（メタデータ） (2024-02-25T07:03:37Z)
• Topology-Informed Graph Transformer [7.857955053895979]
  グラフアイソモーフィズムの検出における識別力とグラフ変換器全体の性能を両立させる新しい変換器である「トポロジーインフォーマグラフ変換器(TIGT)」について検討した。 TIGTは4つの構成要素から構成される: 非同型普遍被覆を用いた位相的位置埋め込み層はグラフの巡回部分グラフに基づいて一意なグラフ表現を保証する。 TIGTは、グラフの同型クラスを識別することを目的とした合成データセットの分類において、従来のグラフ変換器よりも優れている。
  論文  参考訳（メタデータ） (2024-02-03T03:17:44Z)
• Isomorphic-Consistent Variational Graph Auto-Encoders for Multi-Level Graph Representation Learning [9.039193854524763]
  本稿では,タスク非依存グラフ表現学習のためのアイソモルフィック-一貫性VGAE(IsoC-VGAE)を提案する。 まず、同型整合性を維持する理論的保証を提供するための復号法を考案する。 次に,逆グラフニューラルネットワーク(Inv-GNN)デコーダを直感的な実現法として提案する。
  論文  参考訳（メタデータ） (2023-12-09T10:16:53Z)
• Advective Diffusion Transformers for Topological Generalization in Graph Learning [69.2894350228753]
  グラフ拡散方程式は、様々なグラフトポロジーの存在下で、どのように外挿して一般化するかを示す。 本稿では,新たなグラフエンコーダのバックボーンであるAdvective Diffusion Transformer (ADiT)を提案する。
  論文  参考訳（メタデータ） (2023-10-10T08:40:47Z)
• A Theoretical Understanding of Shallow Vision Transformers: Learning, Generalization, and Sample Complexity [71.11795737362459]
  自己注意モジュールを持つViTは、最近多くのタスクで経験的な成功を収めた。 しかし、理論学習の一般化分析は、ほとんどノイズが多く、解答的である。 本稿では,分類タスクのための浅いViTの理論的解析を行った。
  論文  参考訳（メタデータ） (2023-02-12T22:12:35Z)
• Optimal Propagation for Graph Neural Networks [51.08426265813481]
  最適グラフ構造を学習するための二段階最適化手法を提案する。 また、時間的複雑さをさらに軽減するために、低ランク近似モデルについても検討する。
  論文  参考訳（メタデータ） (2022-05-06T03:37:00Z)

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

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