論文の概要: Polynormer: Polynomial-Expressive Graph Transformer in Linear Time

• arxiv url: http://arxiv.org/abs/2403.01232v3
• Date: Sat, 6 Apr 2024 23:26:26 GMT
• ステータス: 処理完了
• システム内更新日: 2024-04-10 00:56:58.623658
• Title: Polynormer: Polynomial-Expressive Graph Transformer in Linear Time
• Title（参考訳）: Polynormer: 線形時間における多項式圧縮グラフ変換器
• Authors: Chenhui Deng, Zichao Yue, Zhiru Zhang,
• Abstract要約: グラフトランスフォーマー(GT)は、メッセージパッシンググラフニューラルネットワーク(GNN)よりも理論的に表現力のある、有望なアーキテクチャとして登場した。 典型的なGTモデルは少なくとも2次複雑さを持つので、大きなグラフにスケールすることはできない。 線形複雑性を持つ線形GTモデルであるPolynormerを提案する。 実験の結果,Polynormerは,ほとんどのデータセットにおいて,最先端のGNNおよびGTベースラインよりも優れていることがわかった。
• 参考スコア（独自算出の注目度）: 9.21955649907066
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Graph transformers (GTs) have emerged as a promising architecture that is theoretically more expressive than message-passing graph neural networks (GNNs). However, typical GT models have at least quadratic complexity and thus cannot scale to large graphs. While there are several linear GTs recently proposed, they still lag behind GNN counterparts on several popular graph datasets, which poses a critical concern on their practical expressivity. To balance the trade-off between expressivity and scalability of GTs, we propose Polynormer, a polynomial-expressive GT model with linear complexity. Polynormer is built upon a novel base model that learns a high-degree polynomial on input features. To enable the base model permutation equivariant, we integrate it with graph topology and node features separately, resulting in local and global equivariant attention models. Consequently, Polynormer adopts a linear local-to-global attention scheme to learn high-degree equivariant polynomials whose coefficients are controlled by attention scores. Polynormer has been evaluated on $13$ homophilic and heterophilic datasets, including large graphs with millions of nodes. Our extensive experiment results show that Polynormer outperforms state-of-the-art GNN and GT baselines on most datasets, even without the use of nonlinear activation functions.
• Abstract（参考訳）: グラフトランスフォーマー(GT)は、メッセージパッシンググラフニューラルネットワーク(GNN)よりも理論的に表現力のある、有望なアーキテクチャとして登場した。 しかし、典型的なGTモデルは少なくとも2次複雑性を持つので、大きなグラフにスケールすることはできない。 最近提案された線形GTはいくつかあるが、GNNのグラフデータセットにはまだ遅れている。 GTの表現性とスケーラビリティのトレードオフのバランスをとるために,多項式表現型GTモデルであるPolynormerを提案する。 Polynormerは入力特徴の高次多項式を学習する新しいベースモデルの上に構築されている。 基本モデル置換同変を可能にするため、グラフトポロジーとノード特徴を別々に統合し、局所的および大域的等変アテンションモデルを作成する。 その結果、ポリノーマーは線形局所-言語的アテンションスキームを採用し、アテンションスコアによって係数が制御される高次同変多項式を学習する。 ポリノーマーは、数百万のノードを持つ大きなグラフを含む、13$のホモフィルとヘテロフィルのデータセットで評価されている。 我々の広範な実験結果から,Polynormerは,非線形アクティベーション関数を使わずとも,ほとんどのデータセットにおいて,最先端のGNNとGTのベースラインよりも優れていることが示された。

関連論文リスト

• Generalization of Graph Neural Networks is Robust to Model Mismatch [84.01980526069075]
  グラフニューラルネットワーク(GNN)は、その一般化能力によってサポートされている様々なタスクにおいて、その効果を実証している。 本稿では,多様体モデルから生成される幾何グラフで動作するGNNについて検討する。 本稿では,そのようなモデルミスマッチの存在下でのGNN一般化の堅牢性を明らかにする。
  論文  参考訳（メタデータ） (2024-08-25T16:00:44Z)
• Elevating Spectral GNNs through Enhanced Band-pass Filter Approximation [26.79625547648669]
  まず,バンドパスグラフフィルタの近似性が向上したポリGNNが,グラフ学習タスクにおいて優れた性能を発揮することを示す。 この知見は、既存のポリGNNの重要な問題、すなわち、これらのポリGNNはバンドパスグラフフィルタの近似において自明な性能を達成する。 この問題に対処するために,バンドパスグラフフィルタの近似における先行的な性能を実現する,TrigoNetという新しいポリGNNを提案する。
  論文  参考訳（メタデータ） (2024-04-15T11:35:32Z)
• Simple Multigraph Convolution Networks [49.19906483875984]
  既存のマルチグラフ畳み込み法では、複数のグラフ間のクロスビューの相互作用を無視するか、あるいは標準的なクロスビュー演算子によって非常に高い計算コストが生じる。 本稿では,まずエッジレベルやサブグラフレベルのトポロジを含むマルチグラフから一貫したクロスビュートポロジを抽出し,その後,生のマルチグラフと一貫したトポロジに基づいて拡張を行う,シンプルなマルチ畳み込みネットワーク(SMGCN)を提案する。 理論上、SMGCNは標準的なクロスビュー拡張ではなく、一貫した拡張のトポロジを利用して、信頼性の高いクロスビュー空間メッセージパッシングを行い、標準拡張の複雑さを効果的に低減する。
  論文  参考訳（メタデータ） (2024-03-08T03:27:58Z)
• Graph Ladling: Shockingly Simple Parallel GNN Training without Intermediate Communication [100.51884192970499]
  GNNは、グラフを学習するニューラルネットワークの強力なファミリーである。 GNNのスケーリングは、肥大化または拡大によって、不健康な勾配、過度なスムースメント、情報のスカッシングといった問題に悩まされる。 本稿では,現在のGNNの深層化や拡張ではなく,GNNに適したモデルスープをデータ中心の視点で表現することを提案する。
  論文  参考訳（メタデータ） (2023-06-18T03:33:46Z)
• Equivariant Polynomials for Graph Neural Networks [38.15983687193912]
  グラフネットワーク(GNN)は本質的に表現力に制限がある。 本稿では、GNNがある程度の同変を計算する能力に基づく代替パワー階層を提案する。 これらの強化されたGNNは、複数のグラフ学習ベンチマークの実験において最先端の結果を示す。
  論文  参考訳（メタデータ） (2023-02-22T18:53:38Z)
• Graph Generative Model for Benchmarking Graph Neural Networks [73.11514658000547]
  本稿では,プライバシ制御により実世界のグラフの分布を学習し,再現する新しいグラフ生成モデルを提案する。 我々のモデルは、GNNモデルのベンチマークに効果的に使用できる大規模な実世界のグラフの、プライバシ制御された合成代用をうまく生成することができる。
  論文  参考訳（メタデータ） (2022-07-10T06:42:02Z)
• Simplified Graph Convolution with Heterophily [25.7577503312319]
  単純グラフ畳み込み(SGC)は異種グラフ(非同種グラフ)には有効でないことを示す。 本稿では、同好性グラフ構造と異好性グラフ構造の両方に適応できる適応的単純グラフ畳み込み(ASGC)を提案する。
  論文  参考訳（メタデータ） (2022-02-08T20:52:08Z)
• MGNN: Graph Neural Networks Inspired by Distance Geometry Problem [28.789684784093048]
  グラフニューラルネットワーク(GNN)は、機械学習分野における顕著な研究トピックとして現れている。 本稿では,GNNの分類段階における分類器の親近性に着想を得たGNNモデルを提案する。 合成および実世界の両方のデータセットを用いて実験を行い,本モデルの有効性を広範囲に評価した。
  論文  参考訳（メタデータ） (2022-01-31T04:15:42Z)
• A Unified Lottery Ticket Hypothesis for Graph Neural Networks [82.31087406264437]
  本稿では,グラフ隣接行列とモデルの重み付けを同時に行う統一GNNスペーシフィケーション(UGS)フレームワークを提案する。 グラフ宝くじ(GLT)をコアサブデータセットとスパースサブネットワークのペアとして定義することにより、人気のある宝くじチケット仮説を初めてGNNsにさらに一般化します。
  論文  参考訳（メタデータ） (2021-02-12T21:52:43Z)
• Nonlinear State-Space Generalizations of Graph Convolutional Neural Networks [172.18295279061607]
  グラフ畳み込みニューラルネットワーク(GCNN)は、線形グラフ畳み込みを非線形にネストすることで、ネットワークデータから構成表現を学習する。 本稿では,GCNNを状態空間の観点からアプローチし,グラフ畳み込みモジュールが最小値線形状態空間モデルであることを明らかにする。 この状態更新は、非パラメトリックであり、グラフスペクトルによって爆発または消滅する可能性があるため、問題となる可能性がある。 本稿では,非線形な状態空間パラメトリック方式でノード特徴を階層内に集約し,よりよいトレードオフを実現するという,新しい結節集合規則を提案する。
  論文  参考訳（メタデータ） (2020-10-27T19:48:56Z)
• Rethinking Graph Regularization for Graph Neural Networks [21.32758655943999]
  グラフラプラシア正規化は既存のグラフニューラルネットワーク(GNN)にほとんど恩恵を与えないことを示す。 我々は、伝播正則化(P-reg)と呼ばれるグラフラプラシア正則化の単純だが非自明な変種を提案する。 我々はP-regがノードレベルのタスクとグラフレベルのタスクの両方において既存のGNNモデルの性能を効果的に向上できることを実証した。
  論文  参考訳（メタデータ） (2020-09-04T07:04:51Z)

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

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