論文の概要: On the Theoretical Expressive Power and the Design Space of Higher-Order Graph Transformers

• arxiv url: http://arxiv.org/abs/2404.03380v1
• Date: Thu, 4 Apr 2024 11:26:51 GMT
• ステータス: 処理完了
• システム内更新日: 2024-04-05 15:01:15.956037
• Title: On the Theoretical Expressive Power and the Design Space of Higher-Order Graph Transformers
• Title（参考訳）: 高次グラフ変換器の理論的表現力と設計空間について
• Authors: Cai Zhou, Rose Yu, Yusu Wang,
• Abstract要約: 次数-k$グラフ変圧器とスパース変圧器の理論表現力について検討する。 自然近傍に基づくスパースオーダー-$k$変換モデルは,計算効率だけでなく,表現性も高いことを示す。
• 参考スコア（独自算出の注目度）: 20.73012427295352
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Graph transformers have recently received significant attention in graph learning, partly due to their ability to capture more global interaction via self-attention. Nevertheless, while higher-order graph neural networks have been reasonably well studied, the exploration of extending graph transformers to higher-order variants is just starting. Both theoretical understanding and empirical results are limited. In this paper, we provide a systematic study of the theoretical expressive power of order-$k$ graph transformers and sparse variants. We first show that, an order-$k$ graph transformer without additional structural information is less expressive than the $k$-Weisfeiler Lehman ($k$-WL) test despite its high computational cost. We then explore strategies to both sparsify and enhance the higher-order graph transformers, aiming to improve both their efficiency and expressiveness. Indeed, sparsification based on neighborhood information can enhance the expressive power, as it provides additional information about input graph structures. In particular, we show that a natural neighborhood-based sparse order-$k$ transformer model is not only computationally efficient, but also expressive -- as expressive as $k$-WL test. We further study several other sparse graph attention models that are computationally efficient and provide their expressiveness analysis. Finally, we provide experimental results to show the effectiveness of the different sparsification strategies.
• Abstract（参考訳）: グラフトランスフォーマーは最近、グラフ学習において大きな注目を集めている。 しかしながら、高階グラフニューラルネットワークは合理的に研究されているものの、高階変種へのグラフトランスフォーマーの拡張の探索は始まったばかりである。 理論的な理解と経験的な結果の両方が限られている。 本稿では,次数k$のグラフ変換器とスパース変種の理論的表現力に関する体系的研究を行う。 まず、計算コストが高いにもかかわらず、追加構造情報を持たないオーダー-$k$グラフ変換器は、$k$-Weisfeiler Lehman(k$-WL)テストよりも表現力が少ないことを示す。 次に,高階グラフ変換器の分散化と拡張を両立させ,その効率性と表現性の向上を図る。 実際、周辺情報に基づくスパーシフィケーションは、入力グラフ構造に関する追加情報を提供するため、表現力を高めることができる。 特に、自然近傍に基づくスパース次数-$k$変換モデルは、計算効率だけでなく、k$-WLテストのような表現力も有することを示す。 さらに、計算効率が良く、表現性解析を提供するスパースグラフアテンションモデルについても検討する。 最後に,異なるスペーシフィケーション戦略の有効性を示す実験結果を示す。

関連論文リスト

• Through the Dual-Prism: A Spectral Perspective on Graph Data Augmentation for Graph Classification [71.36575018271405]
  本稿では,DP-NoiseとDP-Maskを組み合わせたDual-Prism(DP)拡張手法を提案する。 低周波固有値の変動を保ちながら、拡張グラフを生成する際に、臨界特性を大規模に保存できることが判明した。
  論文  参考訳（メタデータ） (2024-01-18T12:58:53Z)
• Deep Prompt Tuning for Graph Transformers [55.2480439325792]
  ファインチューニングはリソース集約型であり、大きなモデルのコピーを複数保存する必要がある。 ファインチューニングの代替として,ディープグラフプロンプトチューニングと呼ばれる新しい手法を提案する。 事前学習したパラメータを凍結し、追加したトークンのみを更新することにより、フリーパラメータの数を減らし、複数のモデルコピーを不要にする。
  論文  参考訳（メタデータ） (2023-09-18T20:12:17Z)
• Are More Layers Beneficial to Graph Transformers? [97.05661983225603]
  現在のグラフ変換器は、深さの増大によるパフォーマンス向上のボトルネックに悩まされている。 ディープグラフ変換器は、グローバルな注目の消滅能力によって制限されている。 本稿では,符号化表現に部分構造トークンを明示的に用いたDeepGraphという新しいグラフトランスフォーマーモデルを提案する。
  論文  参考訳（メタデータ） (2023-03-01T15:22:40Z)
• Transformers over Directed Acyclic Graphs [6.263470141349622]
  有向非巡回グラフ(DAG)上の変換器について検討し,DAGに適したアーキテクチャ適応を提案する。 グラフトランスフォーマーは、DAGに適したグラフニューラルネットワークを概ね上回り、品質と効率の両面でSOTAグラフトランスフォーマーの性能を向上させるのに有効であることを示す。
  論文  参考訳（メタデータ） (2022-10-24T12:04:52Z)
• Pure Transformers are Powerful Graph Learners [51.36884247453605]
  グラフ固有の修正のない標準変換器は、理論と実践の両方において、グラフ学習において有望な結果をもたらす可能性があることを示す。 このアプローチは、理論的には、同変線形層からなる不変グラフネットワーク(2-IGN)と同程度に表現可能であることを証明している。 提案手法は,Tokenized Graph Transformer (TokenGT) を作成した。
  論文  参考訳（メタデータ） (2022-07-06T08:13:06Z)
• Latent Augmentation For Better Graph Self-Supervised Learning [20.082614919182692]
  我々は、潜在的な拡張と強力なデコーダを備えた予測モデルは、対照的なモデルよりも同等またはそれ以上の表現力を達成することができると論じている。 Wiener Graph Deconvolutional Networkと呼ばれる新しいグラフデコーダは、拡張潜在表現から情報再構成を行うように設計されている。
  論文  参考訳（メタデータ） (2022-06-26T17:41:59Z)
• What Dense Graph Do You Need for Self-Attention? [73.82686008622596]
  我々はハイパーキューブにおけるトークンインタラクションをモデル化し、バニラ変換器と同等あるいはそれ以上の結果を示すスパーストランスフォーマーHypercube Transformerを提案する。 様々なシーケンス長を必要とするタスクの実験は、グラフ関数の検証をうまく行いました。
  論文  参考訳（メタデータ） (2022-05-27T14:36:55Z)
• Dynamic Graph Representation Learning via Graph Transformer Networks [41.570839291138114]
  動的グラフ変換器 (DGT) を用いた動的グラフ学習手法を提案する。 DGTは、グラフトポロジを効果的に学習し、暗黙のリンクをキャプチャするための時空間符号化を持つ。 DGTはいくつかの最先端のベースラインと比較して優れた性能を示す。
  論文  参考訳（メタデータ） (2021-11-19T21:44:23Z)
• Do Transformers Really Perform Bad for Graph Representation? [62.68420868623308]
  標準の Transformer アーキテクチャをベースに構築された Graphormer について述べる。 グラフでTransformerを利用する上で重要な洞察は、グラフの構造情報をモデルに効果的にエンコードする必要があることである。
  論文  参考訳（メタデータ） (2021-06-09T17:18:52Z)

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

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