論文の概要: Breaking the Limits of Message Passing Graph Neural Networks
- arxiv url: http://arxiv.org/abs/2106.04319v1
- Date: Tue, 8 Jun 2021 13:26:56 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-10 00:08:50.959708
- Title: Breaking the Limits of Message Passing Graph Neural Networks
- Title（参考訳）: メッセージパッシンググラフニューラルネットワークの限界を破る
- Authors: Muhammet Balcilar, Pierre H\'eroux, Benoit Ga\"uz\`ere, Pascal
Vasseur, S\'ebastien Adam, Paul Honeine
- Abstract要約: グラフニューラルネットワーク(MPNN)は、スパースグラフに適用する場合のノード数に関して線形複雑である。
本稿では, 固有値の非線形なカスタム関数により, グラフ畳み込みサポートがスペクトル領域で設計されている場合, MPNNは1-WLテストよりも理論的に強力であることを示す。
- 参考スコア（独自算出の注目度）: 6.175401630947573
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Since the Message Passing (Graph) Neural Networks (MPNNs) have a linear
complexity with respect to the number of nodes when applied to sparse graphs,
they have been widely implemented and still raise a lot of interest even though
their theoretical expressive power is limited to the first order
Weisfeiler-Lehman test (1-WL). In this paper, we show that if the graph
convolution supports are designed in spectral-domain by a non-linear custom
function of eigenvalues and masked with an arbitrary large receptive field, the
MPNN is theoretically more powerful than the 1-WL test and experimentally as
powerful as a 3-WL existing models, while remaining spatially localized.
Moreover, by designing custom filter functions, outputs can have various
frequency components that allow the convolution process to learn different
relationships between a given input graph signal and its associated properties.
So far, the best 3-WL equivalent graph neural networks have a computational
complexity in $\mathcal{O}(n^3)$ with memory usage in $\mathcal{O}(n^2)$,
consider non-local update mechanism and do not provide the spectral richness of
output profile. The proposed method overcomes all these aforementioned problems
and reaches state-of-the-art results in many downstream tasks.
- Abstract（参考訳）: メッセージパッシング(Graph)ニューラルネットワーク(MPNN)は、スパースグラフに適用されたノード数に関して線形複雑であるため、理論表現力は第1次Weisfeiler-Lehmanテスト(1-WL)に限定されているにもかかわらず、広く実装され、多くの関心を集めている。
本稿では,固有値の非線形なカスタム関数を用いてスペクトル領域でグラフ畳み込みを設計し,任意の大きな受容場をマスキングした場合,MPNNは理論上は1-WLテストよりも強力であり,既存の3-WLモデルと同じくらい強力であり,空間的局所化を保ったままであることを示す。
さらに、カスタムフィルタ関数を設計することにより、コンボリューションプロセスが与えられた入力グラフ信号とその関連する特性の間の異なる関係を学習できる様々な周波数成分を出力に持つことができる。
今のところ、最高の3WL等価グラフニューラルネットワークは$\mathcal{O}(n^3)$の計算複雑性を持ち、$\mathcal{O}(n^2)$のメモリ使用量では非局所的な更新機構を考慮し、出力プロファイルのスペクトルリッチ性を提供しない。
提案手法は上記の問題を全て克服し,多くのダウンストリームタスクで最先端に到達する。
関連論文リスト
- GrassNet: State Space Model Meets Graph Neural Network [57.62885438406724]
Graph State Space Network (GrassNet)は、任意のグラフスペクトルフィルタを設計するためのシンプルで効果的なスキームを提供する理論的なサポートを持つ、新しいグラフニューラルネットワークである。
我々の知る限り、我々の研究はグラフGNNスペクトルフィルタの設計にSSMを使った最初のものである。
9つの公開ベンチマークでの大規模な実験により、GrassNetは現実世界のグラフモデリングタスクにおいて優れたパフォーマンスを達成することが明らかになった。
論文 参考訳（メタデータ） (2024-08-16T07:33:58Z) - Non-convolutional Graph Neural Networks [46.79328529882998]
畳み込み演算子を完全に含まない単純なグラフ学習モジュールを設計し、RUMニューラルネットワークを用いたランダムウォークを作成した。
RUMは競合する性能を実現するが、より堅牢で、メモリ効率が高く、スケーラブルで、最も単純な畳み込みGNNよりも高速である。
論文 参考訳（メタデータ） (2024-07-31T21:29:26Z) - Scalable Graph Compressed Convolutions [68.85227170390864]
ユークリッド畳み込みのための入力グラフのキャリブレーションに置換を適用する微分可能手法を提案する。
グラフキャリブレーションに基づいて,階層型グラフ表現学習のための圧縮畳み込みネットワーク(CoCN)を提案する。
論文 参考訳（メタデータ） (2024-07-26T03:14:13Z) - Spatio-Spectral Graph Neural Networks [50.277959544420455]
比スペクトルグラフネットワーク(S$2$GNN)を提案する。
S$2$GNNは空間的およびスペクトル的にパラメータ化されたグラフフィルタを組み合わせる。
S$2$GNNsは、MPGNNsよりも厳密な近似理論誤差境界を生じる。
論文 参考訳（メタデータ） (2024-05-29T14:28:08Z) - Specformer: Spectral Graph Neural Networks Meet Transformers [51.644312964537356]
スペクトルグラフニューラルネットワーク(GNN)は、スペクトル領域グラフ畳み込みを通じてグラフ表現を学習する。
本稿では、全ての固有値の集合を効果的に符号化し、スペクトル領域で自己アテンションを行うSpecformerを紹介する。
複数のSpecformerレイヤを積み重ねることで、強力なスペクトルGNNを構築することができる。
論文 参考訳（メタデータ） (2023-03-02T07:36:23Z) - Higher-order Sparse Convolutions in Graph Neural Networks [17.647346486710514]
グラフ信号のソボレフノルムに基づく新しい高次スパース畳み込みを導入する。
S-SobGNNは、最先端のいくつかの手法と比較して、全てのアプリケーションで競合性能を示す。
論文 参考訳（メタデータ） (2023-02-21T08:08:18Z) - Exponentially Improving the Complexity of Simulating the
Weisfeiler-Lehman Test with Graph Neural Networks [22.36443060418036]
非同型グラフの識別におけるグラフニューラルネットワーク(GNN)の表現力は、Weisfeiler-Lehmanグラフテストと全く同じであることを示す。
本稿では,GNN 上での WL テストの高速化について述べる。
論文 参考訳（メタデータ） (2022-11-06T22:38:49Z) - From Local to Global: Spectral-Inspired Graph Neural Networks [28.858773653743075]
グラフニューラルネットワーク(GNN)は、非ユークリッドデータのための強力なディープラーニング手法である。
MPNNは、局所グラフ地区の信号を集約して結合するメッセージパッシングアルゴリズムである。
MPNNは、過密や過密といった問題に悩まされる可能性がある。
論文 参考訳（メタデータ） (2022-09-24T17:19:00Z) - 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) - Distance Encoding: Design Provably More Powerful Neural Networks for
Graph Representation Learning [63.97983530843762]
グラフニューラルネットワーク(GNN)はグラフ表現学習において大きな成功を収めている。
GNNは、実際には非常に異なるグラフ部分構造に対して同一の表現を生成する。
より強力なGNNは、最近高階試験を模倣して提案され、基礎となるグラフ構造を疎結合にできないため、非効率である。
本稿では,グラフ表現学習の新たなクラスとして距離分解(DE)を提案する。
論文 参考訳（メタデータ） (2020-08-31T23:15:40Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。