論文の概要: On the Expressive Power of Spectral Invariant Graph Neural Networks
- arxiv url: http://arxiv.org/abs/2406.04336v1
- Date: Thu, 6 Jun 2024 17:59:41 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-07 13:11:04.288584
- Title: On the Expressive Power of Spectral Invariant Graph Neural Networks
- Title（参考訳）: スペクトル不変グラフニューラルネットワークの表現力について
- Authors: Bohang Zhang, Lingxiao Zhao, Haggai Maron,
- Abstract要約: Eigenspace Projection GNN(EPNN)と呼ばれるスペクトル不変GNNを設計するための統一メッセージパッシングフレームワークを導入する。
EPNNは、従来のスペクトル不変アーキテクチャをすべて統一し、それらが厳密に表現されにくいか、EPNNと同値であることを示す。
より表現力の高いGNNと組み合わせることで、スペクトル特徴を用いることで表現性が向上するかどうかを論じる。
- 参考スコア（独自算出の注目度）: 28.557550571187253
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Incorporating spectral information to enhance Graph Neural Networks (GNNs) has shown promising results but raises a fundamental challenge due to the inherent ambiguity of eigenvectors. Various architectures have been proposed to address this ambiguity, referred to as spectral invariant architectures. Notable examples include GNNs and Graph Transformers that use spectral distances, spectral projection matrices, or other invariant spectral features. However, the potential expressive power of these spectral invariant architectures remains largely unclear. The goal of this work is to gain a deep theoretical understanding of the expressive power obtainable when using spectral features. We first introduce a unified message-passing framework for designing spectral invariant GNNs, called Eigenspace Projection GNN (EPNN). A comprehensive analysis shows that EPNN essentially unifies all prior spectral invariant architectures, in that they are either strictly less expressive or equivalent to EPNN. A fine-grained expressiveness hierarchy among different architectures is also established. On the other hand, we prove that EPNN itself is bounded by a recently proposed class of Subgraph GNNs, implying that all these spectral invariant architectures are strictly less expressive than 3-WL. Finally, we discuss whether using spectral features can gain additional expressiveness when combined with more expressive GNNs.
- Abstract（参考訳）: グラフニューラルネットワーク(GNN)を強化するためにスペクトル情報を組み込むことは、有望な結果を示しているが、固有ベクトルの本質的な曖昧さのため、根本的な課題を提起している。
このあいまいさに対処する様々なアーキテクチャが提案され、スペクトル不変アーキテクチャと呼ばれる。
注目すべき例としては、スペクトル距離、スペクトル投影行列、その他の不変スペクトル特徴を使用するGNNやグラフ変換がある。
しかし、これらのスペクトル不変アーキテクチャの潜在的な表現力はほとんど不明である。
本研究の目的はスペクトル特徴を用いた場合の表現力の深い理論的理解を得ることである。
まず、スペクトル不変GNNを設計するための統一メッセージパッシングフレームワーク、Eigenspace Projection GNN(EPNN)を紹介する。
包括的分析により、EPNNは基本的にすべての以前のスペクトル不変アーキテクチャを統一し、それらが厳密に表現的でないかEPNNと同値であることを示している。
異なるアーキテクチャ間のきめ細かい表現性階層も確立されている。
一方、EPNN自体が最近提案されたサブグラフGNNのクラスに束縛されていることを証明し、これらのスペクトル不変アーキテクチャは3WLよりも厳密に表現できないことを示唆する。
最後に、より表現力のあるGNNと組み合わせることで、スペクトル特徴を用いることで表現性が向上するかどうかについて議論する。
関連論文リスト
- GrassNet: State Space Model Meets Graph Neural Network [57.62885438406724]
Graph State Space Network (GrassNet)は、任意のグラフスペクトルフィルタを設計するためのシンプルで効果的なスキームを提供する理論的なサポートを持つ、新しいグラフニューラルネットワークである。
我々の知る限り、我々の研究はグラフGNNスペクトルフィルタの設計にSSMを使った最初のものである。
9つの公開ベンチマークでの大規模な実験により、GrassNetは現実世界のグラフモデリングタスクにおいて優れたパフォーマンスを達成することが明らかになった。
論文 参考訳（メタデータ） (2024-08-16T07:33:58Z) - Rethinking Spectral Graph Neural Networks with Spatially Adaptive Filtering [31.595664867365322]
スペクトルグラフニューラルネットワーク(GNN)はスペクトル領域において十分に確立されているが、近似への実際の依存は空間領域への深いリンクを意味する。
スペクトルと空間アグリゲーションの間に理論的な関係を確立し、スペクトルが元のグラフを適応した新しいグラフに暗黙的に導く本質的な相互作用を明らかにする。
本稿では,非局所的な補助的なアグリゲーションのためのスペクトルフィルタリングにより適応された新しいグラフを利用する空間適応フィルタリング(SAF)フレームワークを提案する。
論文 参考訳（メタデータ） (2024-01-17T09:12:31Z) - HoloNets: Spectral Convolutions do extend to Directed Graphs [59.851175771106625]
従来の知恵は、スペクトル畳み込みネットワークは無向グラフ上にしか展開できないと規定している。
ここでは、このグラフフーリエ変換への伝統的な依存が超フルであることを示す。
本稿では,新たに開発されたフィルタの周波数応答解釈を行い,フィルタ表現に使用するベースの影響を調査し,ネットワークを基盤とする特性演算子との相互作用について議論する。
論文 参考訳（メタデータ） (2023-10-03T17:42:09Z) - Specformer: Spectral Graph Neural Networks Meet Transformers [51.644312964537356]
スペクトルグラフニューラルネットワーク(GNN)は、スペクトル領域グラフ畳み込みを通じてグラフ表現を学習する。
本稿では、全ての固有値の集合を効果的に符号化し、スペクトル領域で自己アテンションを行うSpecformerを紹介する。
複数のSpecformerレイヤを積み重ねることで、強力なスペクトルGNNを構築することができる。
論文 参考訳（メタデータ） (2023-03-02T07:36:23Z) - Equivariant Polynomials for Graph Neural Networks [38.15983687193912]
グラフネットワーク(GNN)は本質的に表現力に制限がある。
本稿では、GNNがある程度の同変を計算する能力に基づく代替パワー階層を提案する。
これらの強化されたGNNは、複数のグラフ学習ベンチマークの実験において最先端の結果を示す。
論文 参考訳（メタデータ） (2023-02-22T18:53:38Z) - Equivariant Transduction through Invariant Alignment [71.45263447328374]
グループ内ハードアライメント機構を組み込んだ,新しいグループ同変アーキテクチャを提案する。
我々のネットワーク構造は、既存のグループ同変アプローチよりも強い同変特性を発達させることができる。
また、SCANタスクにおいて、従来のグループ同変ネットワークよりも経験的に優れていたことが判明した。
論文 参考訳（メタデータ） (2022-09-22T11:19:45Z) - How Powerful are Spectral Graph Neural Networks [9.594432031144715]
スペクトルグラフニューラルネットワーク(Spectral Graph Neural Network)は、グラフ信号フィルタに基づくグラフニューラルネットワークの一種である。
まず、非線形性のないスペクトルGNNでさえ任意のグラフ信号を生成することを証明した。
また、スペクトルGNNの表現力とグラフアイソモーフィズム(GI)テストの関連性を確立する。
論文 参考訳（メタデータ） (2022-05-23T10:22:12Z) - Representation Power of Graph Neural Networks: Improved Expressivity via
Algebraic Analysis [124.97061497512804]
標準グラフニューラルネットワーク (GNN) はWeisfeiler-Lehman (WL) アルゴリズムよりも差別的な表現を生成する。
また、白い入力を持つ単純な畳み込みアーキテクチャは、グラフの閉経路をカウントする同変の特徴を生じさせることを示した。
論文 参考訳（メタデータ） (2022-05-19T18:40:25Z) - Equivariant Subgraph Aggregation Networks [23.26140936226352]
本稿では,この問題に対処するためのEquivariant Subgraph Aggregation Networks (ESAN) という新しいフレームワークを提案する。
2つのグラフはMPNNでは区別できないかもしれないが、しばしば区別可能な部分グラフを含む。
グラフ同型に対する1次元Weisfeiler-Leman(1-WL)テストの新しい変種を開発し、ESANの表現性に対する下界を証明した。
サブグラフ選択ポリシーや同変ニューラルアーキテクチャといった設計選択がアーキテクチャの表現力にどのように影響するかを記述する理論的結果を提供する。
論文 参考訳（メタデータ） (2021-10-06T16:45:07Z) - Spectral-Spatial Global Graph Reasoning for Hyperspectral Image
Classification [50.899576891296235]
畳み込みニューラルネットワークは、ハイパースペクトル画像分類に広く応用されている。
近年の手法は空間トポロジのグラフ畳み込みによってこの問題に対処しようとしている。
論文 参考訳（メタデータ） (2021-06-26T06:24:51Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。