論文の概要: On Structural Expressive Power of Graph Transformers
- arxiv url: http://arxiv.org/abs/2305.13987v1
- Date: Tue, 23 May 2023 12:12:21 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-24 16:39:26.938501
- Title: On Structural Expressive Power of Graph Transformers
- Title（参考訳）: グラフ変換器の構造表現力について
- Authors: Wenhao Zhu, Tianyu Wen, Guojie Song, Liang Wang, Bo Zheng
- Abstract要約: 一般化グラフ同型テストアルゴリズムである textbfSEG-WL test (textbfStructural textbfEncoding enhanced textbfWeisfeiler-textbfLehman test) を導入する。
構造符号化の設計により,グラフ変換器の表現力がどのように決定されるかを示す。
- 参考スコア（独自算出の注目度）: 26.84413369075598
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Graph Transformer has recently received wide attention in the research
community with its outstanding performance, yet its structural expressive power
has not been well analyzed. Inspired by the connections between
Weisfeiler-Lehman (WL) graph isomorphism test and graph neural network (GNN),
we introduce \textbf{SEG-WL test} (\textbf{S}tructural \textbf{E}ncoding
enhanced \textbf{G}lobal \textbf{W}eisfeiler-\textbf{L}ehman test), a
generalized graph isomorphism test algorithm as a powerful theoretical tool for
exploring the structural discriminative power of graph Transformers. We
theoretically prove that the SEG-WL test is an expressivity upper bound on a
wide range of graph Transformers, and the representational power of SEG-WL test
can be approximated by a simple Transformer network arbitrarily under certain
conditions. With the SEG-WL test, we show how graph Transformers' expressive
power is determined by the design of structural encodings, and present
conditions that make the expressivity of graph Transformers beyond WL test and
GNNs. Moreover, motivated by the popular shortest path distance encoding, we
follow the theory-oriented principles and develop a provably stronger
structural encoding method, Shortest Path Induced Subgraph (\textit{SPIS})
encoding. Our theoretical findings provide a novel and practical paradigm for
investigating the expressive power of graph Transformers, and extensive
synthetic and real-world experiments empirically verify the strengths of our
proposed methods.
- Abstract（参考訳）: グラフトランスフォーマーは最近、優れた性能で研究コミュニティで注目を集めているが、その構造的表現力は十分に分析されていない。
Wesfeiler-Lehman (WL) グラフ同型テストとグラフニューラルネットワーク (GNN) の接続にインスパイアされ、グラフ変換器の構造的識別力を探索するための強力な理論的ツールとして、一般化されたグラフ同型テストアルゴリズムである \textbf{SEG-WL test} (\textbf{S}tructural \textbf{E}ncoding enhanced \textbf{G}lobal \textbf{W}eisfeiler-\textbf{L}ehman test) を導入する。
理論上、seg-wlテストは幅広いグラフ変換器上での表現率上限であり、seg-wlテストの表現力は特定の条件下で任意に単純なトランスフォーマネットワークによって近似できることを示した。
SEG-WL テストでは,グラフ変換器の表現力は構造符号化の設計によって決定されることを示すとともに,WL テストや GNN 以外のグラフ変換器の表現性を示す条件を示す。
さらに, 最短経路距離符号化に動機付けられ, 理論指向の原理を踏襲し, より強力な構造符号化法であるショート・パス誘導サブグラフ (\textit{SPIS}) の符号化を開発する。
本理論はグラフトランスフォーマの表現力を調べるための新しい実用的なパラダイムを提供し,提案手法の強みを実証的に検証した。
関連論文リスト
- What Improves the Generalization of Graph Transformers? A Theoretical Dive into the Self-attention and Positional Encoding [67.59552859593985]
自己アテンションと位置エンコーディングを組み込んだグラフトランスフォーマーは、さまざまなグラフ学習タスクのための強力なアーキテクチャとして登場した。
本稿では,半教師付き分類のための浅いグラフ変換器の理論的検討について紹介する。
論文 参考訳（メタデータ） (2024-06-04T05:30:16Z) - Automatic Graph Topology-Aware Transformer [50.2807041149784]
マイクロレベルおよびマクロレベルの設計による包括的グラフトランスフォーマー検索空間を構築した。
EGTASはマクロレベルでのグラフトランスフォーマートポロジとマイクロレベルでのグラフ認識戦略を進化させる。
グラフレベルおよびノードレベルのタスクに対して,EGTASの有効性を示す。
論文 参考訳（メタデータ） (2024-05-30T07:44:31Z) - On the Theoretical Expressive Power and the Design Space of Higher-Order Graph Transformers [20.73012427295352]
次数-k$グラフ変圧器とスパース変圧器の理論表現力について検討する。
自然近傍に基づくスパースオーダー-$k$変換モデルは,計算効率だけでなく,表現性も高いことを示す。
論文 参考訳（メタデータ） (2024-04-04T11:26:51Z) - Graph Transformers without Positional Encodings [0.7252027234425334]
グラフのラプラシアンスペクトルを認識する新しいスペクトル対応アテンション機構を用いたグラフ変換器であるEigenformerを紹介する。
我々は,多数の標準GNNベンチマークにおいて,SOTAグラフ変換器の性能向上を実証的に示す。
論文 参考訳（メタデータ） (2024-01-31T12:33:31Z) - Towards Principled Graph Transformers [8.897857788525629]
k次元Weisfeiler-Leman(k-WL)階層に基づくグラフ学習アーキテクチャは、理論的によく理解された表現力を提供する。
提案するEdge Transformerは,ノードではなくノードペアで動作するグローバルアテンションモデルであり,少なくとも3WLの表現力を持つことを示す。
論文 参考訳（メタデータ） (2024-01-18T16:50:55Z) - Are More Layers Beneficial to Graph Transformers? [97.05661983225603]
現在のグラフ変換器は、深さの増大によるパフォーマンス向上のボトルネックに悩まされている。
ディープグラフ変換器は、グローバルな注目の消滅能力によって制限されている。
本稿では,符号化表現に部分構造トークンを明示的に用いたDeepGraphという新しいグラフトランスフォーマーモデルを提案する。
論文 参考訳（メタデータ） (2023-03-01T15:22:40Z) - Pure Transformers are Powerful Graph Learners [51.36884247453605]
グラフ固有の修正のない標準変換器は、理論と実践の両方において、グラフ学習において有望な結果をもたらす可能性があることを示す。
このアプローチは、理論的には、同変線形層からなる不変グラフネットワーク(2-IGN)と同程度に表現可能であることを証明している。
提案手法は,Tokenized Graph Transformer (TokenGT) を作成した。
論文 参考訳（メタデータ） (2022-07-06T08:13:06Z) - Deformable Graph Transformer [31.254872949603982]
本稿では動的にサンプリングされたキーと値のペアでスパースアテンションを行うDeformable Graph Transformer (DGT)を提案する。
実験により、我々の新しいグラフトランスフォーマーは既存のトランスフォーマーベースモデルより一貫して優れていることが示された。
論文 参考訳（メタデータ） (2022-06-29T00:23:25Z) - Do Transformers Really Perform Bad for Graph Representation? [62.68420868623308]
標準の Transformer アーキテクチャをベースに構築された Graphormer について述べる。
グラフでTransformerを利用する上で重要な洞察は、グラフの構造情報をモデルに効果的にエンコードする必要があることである。
論文 参考訳（メタデータ） (2021-06-09T17:18:52Z) - Improving Graph Neural Network Expressivity via Subgraph Isomorphism
Counting [63.04999833264299]
グラフサブストラクチャネットワーク(GSN)は,サブストラクチャエンコーディングに基づくトポロジ的に認識可能なメッセージパッシング方式である。
Wesfeiler-Leman (WL) グラフ同型テストよりも厳密に表現可能であることを示す。
グラフ分類と回帰タスクについて広範囲に評価を行い、様々な実世界の環境において最先端の結果を得る。
論文 参考訳（メタデータ） (2020-06-16T15:30:31Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。