論文の概要: How Powerful are Spectral Graph Neural Networks
- arxiv url: http://arxiv.org/abs/2205.11172v1
- Date: Mon, 23 May 2022 10:22:12 GMT
- ステータス: 処理完了
- システム内更新日: 2022-05-25 09:24:58.905473
- Title: How Powerful are Spectral Graph Neural Networks
- Title（参考訳）: スペクトルグラフニューラルネットワークはいかに強力か
- Authors: Xiyuan Wang, Muhan Zhang
- Abstract要約: スペクトルグラフニューラルネットワーク(Spectral Graph Neural Network)は、グラフ信号フィルタに基づくグラフニューラルネットワークの一種である。
まず、非線形性のないスペクトルGNNでさえ任意のグラフ信号を生成することを証明した。
また、スペクトルGNNの表現力とグラフアイソモーフィズム(GI)テストの関連性を確立する。
- 参考スコア（独自算出の注目度）: 9.594432031144715
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Spectral Graph Neural Network is a kind of Graph Neural Network (GNN) based
on graph signal filters, and some models able to learn arbitrary spectral
filters have emerged recently. However, few works analyze the expressive power
of spectral GNNs. This paper studies spectral GNNs' expressive power
theoretically. We first prove that even spectral GNNs without nonlinearity can
produce arbitrary graph signals and give two conditions for reaching
universality. They are: 1) no multiple eigenvalues of graph Laplacian, and 2)
no missing frequency components in node features. We also establish a
connection between the expressive power of spectral GNNs and Graph Isomorphism
(GI) testing which is often used to characterize spatial GNNs' expressive
power. Moreover, we study the difference in empirical performance among
different spectral GNNs with the same expressive power from an optimization
perspective, and motivate the use of an orthogonal basis whose weight function
corresponds to the graph signal density in the spectrum. Inspired by the
analysis, we propose JacobiConv, which uses Jacobi polynomial basis due to
their orthogonality and flexibility to adapt to a wide range of weight
functions. JacobiConv deserts nonlinearity while outperforming all baselines on
both synthetic and real-world datasets.
- Abstract（参考訳）: スペクトルグラフニューラルネットワーク(Spectral Graph Neural Network)は、グラフ信号フィルタに基づくグラフニューラルネットワーク(GNN)の一種で、任意のスペクトルフィルタを学習できるモデルが最近出現している。
しかし、スペクトルGNNの表現力を分析する研究はほとんどない。
本稿では,GNNの表現力を理論的に研究する。
まず、非線形性のないスペクトルGNNでさえ任意のグラフ信号を生成し、普遍性に到達するための2つの条件を与えることを証明した。
その通りです
1)グラフラプラシアンの多重固有値がなく、
2)ノードの特徴に欠落する周波数成分はない。
また、スペクトルgnnの表現力と、空間gnnの表現力を表すためによく用いられるグラフ同型(gi)テストとの関係も確立する。
さらに、最適化の観点から、同じ表現力を持つ異なるスペクトルGNN間の経験的性能の差について検討し、重み関数がスペクトルのグラフ信号密度に対応する直交基底の使用を動機づける。
解析に着想を得たjacobiconvは,多岐にわたる重み関数に適応するための直交性と柔軟性のためにヤコビ多項式基底を用いる。
JacobiConvは、合成データセットと実世界のデータセットの両方で全てのベースラインを上回りながら、非線形性を放棄する。
関連論文リスト
- GrassNet: State Space Model Meets Graph Neural Network [57.62885438406724]
Graph State Space Network (GrassNet)は、任意のグラフスペクトルフィルタを設計するためのシンプルで効果的なスキームを提供する理論的なサポートを持つ、新しいグラフニューラルネットワークである。
我々の知る限り、我々の研究はグラフGNNスペクトルフィルタの設計にSSMを使った最初のものである。
9つの公開ベンチマークでの大規模な実験により、GrassNetは現実世界のグラフモデリングタスクにおいて優れたパフォーマンスを達成することが明らかになった。
論文 参考訳（メタデータ） (2024-08-16T07:33:58Z) - A Manifold Perspective on the Statistical Generalization of Graph Neural Networks [84.01980526069075]
我々は、スペクトル領域の多様体からサンプリングされたグラフ上のGNNの統計的一般化理論を確立するために多様体の視点を取る。
我々はGNNの一般化境界が対数スケールのグラフのサイズとともに線形に減少し、フィルタ関数のスペクトル連続定数とともに線形的に増加することを証明した。
論文 参考訳（メタデータ） (2024-06-07T19:25:02Z) - Spectral Greedy Coresets for Graph Neural Networks [61.24300262316091]
ノード分類タスクにおける大規模グラフの利用は、グラフニューラルネットワーク(GNN)の現実的な応用を妨げる
本稿では,GNNのグラフコアセットについて検討し,スペクトル埋め込みに基づくエゴグラフの選択により相互依存の問題を回避する。
我々のスペクトルグレディグラフコアセット(SGGC)は、数百万のノードを持つグラフにスケールし、モデル事前学習の必要性を排除し、低ホモフィリーグラフに適用する。
論文 参考訳（メタデータ） (2024-05-27T17:52:12Z) - Uplifting the Expressive Power of Graph Neural Networks through Graph
Partitioning [3.236774847052122]
グラフ分割のレンズによるグラフニューラルネットワークの表現力について検討する。
我々は新しいGNNアーキテクチャ、すなわちグラフ分割ニューラルネットワーク(GPNN)を導入する。
論文 参考訳（メタデータ） (2023-12-14T06:08:35Z) - Specformer: Spectral Graph Neural Networks Meet Transformers [51.644312964537356]
スペクトルグラフニューラルネットワーク(GNN)は、スペクトル領域グラフ畳み込みを通じてグラフ表現を学習する。
本稿では、全ての固有値の集合を効果的に符号化し、スペクトル領域で自己アテンションを行うSpecformerを紹介する。
複数のSpecformerレイヤを積み重ねることで、強力なスペクトルGNNを構築することができる。
論文 参考訳（メタデータ） (2023-03-02T07:36:23Z) - Representation Power of Graph Neural Networks: Improved Expressivity via
Algebraic Analysis [124.97061497512804]
標準グラフニューラルネットワーク (GNN) はWeisfeiler-Lehman (WL) アルゴリズムよりも差別的な表現を生成する。
また、白い入力を持つ単純な畳み込みアーキテクチャは、グラフの閉経路をカウントする同変の特徴を生じさせることを示した。
論文 参考訳（メタデータ） (2022-05-19T18:40:25Z) - Improving Spectral Graph Convolution for Learning Graph-level
Representation [27.76697047602983]
グラフ全体の表現を学習するためには,ノード間の基本的な関係を特徴付けるため,位相的距離が必要と考えられる。
グラフフィルタの制限を取り除くことで、新たなアーキテクチャによってグラフ表現の学習のパフォーマンスが大幅に向上する。
これは、よく知られたスペクトル/ローパスフィルタと比較して、入力信号に対するスペクトルの影響を定量的に測定する理解として機能する。
論文 参考訳（メタデータ） (2021-12-14T04:50:46Z) - Graphon Pooling in Graph Neural Networks [169.09536309161314]
グラフニューラルネットワーク(GNN)は、グラフによってモデル化された不規則構造上の信号の処理を含む様々なアプリケーションで効果的に使用されている。
本稿では,グラフのスペクトル特性を保存したグラフオンを用いて,GNNのプールとサンプリングを行う新しい手法を提案する。
論文 参考訳（メタデータ） (2020-03-03T21:04:20Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。