論文の概要: 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は、合成データセットと実世界のデータセットの両方で全てのベースラインを上回りながら、非線形性を放棄する。
関連論文リスト
- Uplifting the Expressive Power of Graph Neural Networks through Graph
Partitioning [3.236774847052122]
グラフ分割のレンズによるグラフニューラルネットワークの表現力について検討する。
我々は新しいGNNアーキテクチャ、すなわちグラフ分割ニューラルネットワーク(GPNN)を導入する。
論文 参考訳(メタデータ) (2023-12-14T06:08:35Z) - Graph Condensation via Eigenbasis Matching [48.99164820872498]
グラフ凝縮は、実際の大きなグラフをはるかに小さな合成グラフで置き換えることを目的としている。
既存のGCメソッドは、一般化が貧弱なため、同じ合成グラフ上で訓練された異なるGNNは明らかに性能差がある。
本稿では、2つの重要なステップを持つGCEMと呼ばれるスペクトルフリーグラフ凝縮に対する固有基底マッチングを提案する。
論文 参考訳(メタデータ) (2023-10-13T15:48:12Z) - HoloNets: Spectral Convolutions do extend to Directed Graphs [59.851175771106625]
従来の知恵は、スペクトル畳み込みネットワークは無向グラフ上にしか展開できないと規定している。
ここでは、このグラフフーリエ変換への伝統的な依存が超フルであることを示す。
本稿では,新たに開発されたフィルタの周波数応答解釈を行い,フィルタ表現に使用するベースの影響を調査し,ネットワークを基盤とする特性演算子との相互作用について議論する。
論文 参考訳(メタデータ) (2023-10-03T17:42:09Z) - Spectral Heterogeneous Graph Convolutions via Positive Noncommutative
Polynomials [25.980101817751937]
正の非可換空間に基づく新しい異種畳み込みネットワークであるPSHGCNを提案する。
PSHGCNは、多種多様な異種グラフ畳み込みを学習し、ノード分類タスクにおいて優れた性能を達成することができる。
論文 参考訳(メタデータ) (2023-05-31T14:09:42Z) - 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) - Graph Neural Networks with Adaptive Frequency Response Filter [55.626174910206046]
適応周波数応答フィルタを用いたグラフニューラルネットワークフレームワークAdaGNNを開発した。
提案手法の有効性を,様々なベンチマークデータセット上で実証的に検証した。
論文 参考訳(メタデータ) (2021-04-26T19:31:21Z) - Bridging the Gap Between Spectral and Spatial Domains in Graph Neural
Networks [8.563354084119062]
空間領域やスペクトル領域におけるグラフ畳み込み過程の等価性を示す。
提案フレームワークは、空間領域に適用しながら、独自の周波数プロファイルを持つスペクトル領域の新しい畳み込みを設計するために使用される。
論文 参考訳(メタデータ) (2020-03-26T01:49:24Z) - Graphon Pooling in Graph Neural Networks [169.09536309161314]
グラフニューラルネットワーク(GNN)は、グラフによってモデル化された不規則構造上の信号の処理を含む様々なアプリケーションで効果的に使用されている。
本稿では,グラフのスペクトル特性を保存したグラフオンを用いて,GNNのプールとサンプリングを行う新しい手法を提案する。
論文 参考訳(メタデータ) (2020-03-03T21:04:20Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。