論文の概要: Transformers Generalize DeepSets and Can be Extended to Graphs and Hypergraphs

• arxiv url: http://arxiv.org/abs/2110.14416v1
• Date: Wed, 27 Oct 2021 13:20:05 GMT
• ステータス: 処理完了
• システム内更新日: 2021-10-28 21:19:38.723413
• Title: Transformers Generalize DeepSets and Can be Extended to Graphs and Hypergraphs
• Title（参考訳）: TransformerはDeepSetsを一般化し、グラフとハイパーグラフに拡張できる
• Authors: Jinwoo Kim, Saeyoon Oh, Seunghoon Hong
• Abstract要約: 我々は、任意の順序置換不変データ(集合、グラフ、ハイパーグラフ)への変換器の一般化を提案する。 特に,カーネルアテンションを持つスパース2階変圧器は,メッセージパッシング操作よりも理論的に表現力が高いことを示す。 我々のモデルは、大規模グラフ回帰および集合-to-(ハイパー)グラフ予測タスクにおいて、不変性やメッセージパスグラフニューラルネットワークよりも大幅に改善されている。
• 参考スコア（独自算出の注目度）: 15.844680924751984
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We present a generalization of Transformers to any-order permutation invariant data (sets, graphs, and hypergraphs). We begin by observing that Transformers generalize DeepSets, or first-order (set-input) permutation invariant MLPs. Then, based on recently characterized higher-order invariant MLPs, we extend the concept of self-attention to higher orders and propose higher-order Transformers for order-$k$ data ($k=2$ for graphs and $k>2$ for hypergraphs). Unfortunately, higher-order Transformers turn out to have prohibitive complexity $\mathcal{O}(n^{2k})$ to the number of input nodes $n$. To address this problem, we present sparse higher-order Transformers that have quadratic complexity to the number of input hyperedges, and further adopt the kernel attention approach to reduce the complexity to linear. In particular, we show that the sparse second-order Transformers with kernel attention are theoretically more expressive than message passing operations while having an asymptotically identical complexity. Our models achieve significant performance improvement over invariant MLPs and message-passing graph neural networks in large-scale graph regression and set-to-(hyper)graph prediction tasks. Our implementation is available at https://github.com/jw9730/hot.
• Abstract（参考訳）: 本稿では,任意の順序置換不変データ(集合,グラフ,ハイパーグラフ)に対する変換器の一般化を提案する。 まず、トランスフォーマーがdeepsetまたはfirst-order (set-input) permutation invariant mlpを一般化することを観察する。 そして、最近特徴付けられた高次不変MPPに基づいて、高次への自己アテンションの概念を拡張し、高次変換器をオーダー$k$データ(グラフはk=2$、ハイパーグラフは$k>2$)に提案する。 残念ながら、高階変換器は、入力ノード数$n$に対して$\mathcal{O}(n^{2k})$が禁じられていることが判明した。 この問題に対処するために,入力ハイパーエッジ数に2次複雑性を持つ低次高次変換器を提案し,さらにカーネルアテンションアプローチを採用して,複雑性を線形に低減する。 特に,カーネルに注意を向けた疎二階トランスは,漸近的に同一の複雑性を持ちながら,理論的にメッセージパッシング操作よりも表現力が高いことを示す。 本モデルでは,大規模グラフ回帰およびセット・トゥ・(ハイパー)グラフ予測タスクにおいて,不変mlpおよびメッセージパッシンググラフニューラルネットワークの性能向上を実現する。 私たちの実装はhttps://github.com/jw9730/hotで利用可能です。

関連論文リスト

• Learning Graph Quantized Tokenizers for Transformers [28.79505338383552]
  グラフトランスフォーマー(GT)は、さまざまなグラフ学習タスクにおいて、グラフニューラルネットワーク(GNN)よりも優れた、ディープラーニングのリードモデルとして登場した。 GQT (textbfGraph textbfQuantized textbfTokenizer) を導入した。 GQTとトークン変調を組み合わせることで、Transformerエンコーダは18のベンチマークのうち16の最先端のパフォーマンスを達成する。
  論文  参考訳（メタデータ） (2024-10-17T17:38:24Z)
• Masked Graph Transformer for Large-Scale Recommendation [56.37903431721977]
  本稿では, MGFormer という名前の効率的な Masked Graph Transformer を提案する。 実験の結果,単一注意層でもMGFormerの優れた性能が得られた。
  論文  参考訳（メタデータ） (2024-05-07T06:00:47Z)
• Chain of Thought Empowers Transformers to Solve Inherently Serial Problems [57.58801785642868]
  思考の連鎖(CoT)は、算術や記号的推論タスクにおいて、大きな言語モデル(LLM)の精度を向上させるための非常に効果的な方法である。 この研究は、表現性のレンズを通してデコーダのみの変換器に対するCoTのパワーを理論的に理解する。
  論文  参考訳（メタデータ） (2024-02-20T10:11:03Z)
• Pure Transformers are Powerful Graph Learners [51.36884247453605]
  グラフ固有の修正のない標準変換器は、理論と実践の両方において、グラフ学習において有望な結果をもたらす可能性があることを示す。 このアプローチは、理論的には、同変線形層からなる不変グラフネットワーク(2-IGN)と同程度に表現可能であることを証明している。 提案手法は,Tokenized Graph Transformer (TokenGT) を作成した。
  論文  参考訳（メタデータ） (2022-07-06T08:13:06Z)
• What Dense Graph Do You Need for Self-Attention? [73.82686008622596]
  我々はハイパーキューブにおけるトークンインタラクションをモデル化し、バニラ変換器と同等あるいはそれ以上の結果を示すスパーストランスフォーマーHypercube Transformerを提案する。 様々なシーケンス長を必要とするタスクの実験は、グラフ関数の検証をうまく行いました。
  論文  参考訳（メタデータ） (2022-05-27T14:36:55Z)
• Stable, Fast and Accurate: Kernelized Attention with Relative Positional Encoding [63.539333383965726]
  相対的位置符号化(RPE)を用いた変換器の注意計算を高速化する新しい手法を提案する。 相対的な位置符号化がToeplitz行列を形成するという観測に基づいて、Fast Fourier Transform (FFT) を用いて、RPEによるカーネル化された注意を効率的に計算できることを数学的に示す。
  論文  参考訳（メタデータ） (2021-06-23T17:51:26Z)
• Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention [22.228028613802174]
  トランスフォーマーは、いくつかのタスクで顕著なパフォーマンスを達成するが、その二次的な複雑さのため、非常に長いシーケンスでは明らかに遅い。 我々は行列積の連想性を利用して複雑さを$mathcalOleft(N2right)$から$mathcalOleft(Nright)$に減らし、$N$はシーケンス長である。 線形変圧器はバニラ変圧器と同等の性能を示し、非常に長いシーケンスの自己回帰予測では最大4000倍高速である。
  論文  参考訳（メタデータ） (2020-06-29T17:55:38Z)
• $O(n)$ Connections are Expressive Enough: Universal Approximability of Sparse Transformers [71.31712741938837]
  注意層ごとに$O(n)$接続しか持たないスパース変換器は、$n2$接続を持つ高密度モデルと同じ関数クラスを近似できることを示す。 また、標準NLPタスクにおいて、異なるパターン・レベルの違いを比較検討する。
  論文  参考訳（メタデータ） (2020-06-08T18:30:12Z)

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

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