論文の概要: From Local to Global: Spectral-Inspired Graph Neural Networks
- arxiv url: http://arxiv.org/abs/2209.12054v1
- Date: Sat, 24 Sep 2022 17:19:00 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-27 14:46:30.405550
- Title: From Local to Global: Spectral-Inspired Graph Neural Networks
- Title(参考訳): ローカルからグローバルへ:スペクトルにインスパイアされたグラフニューラルネットワーク
- Authors: Ningyuan Huang, Soledad Villar, Carey E. Priebe, Da Zheng, Chengyue
Huang, Lin Yang, Vladimir Braverman
- Abstract要約: グラフニューラルネットワーク(GNN)は、非ユークリッドデータのための強力なディープラーニング手法である。
MPNNは、局所グラフ地区の信号を集約して結合するメッセージパッシングアルゴリズムである。
MPNNは、過密や過密といった問題に悩まされる可能性がある。
- 参考スコア(独自算出の注目度): 28.858773653743075
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Graph Neural Networks (GNNs) are powerful deep learning methods for
Non-Euclidean data. Popular GNNs are message-passing algorithms (MPNNs) that
aggregate and combine signals in a local graph neighborhood. However, shallow
MPNNs tend to miss long-range signals and perform poorly on some heterophilous
graphs, while deep MPNNs can suffer from issues like over-smoothing or
over-squashing. To mitigate such issues, existing works typically borrow
normalization techniques from training neural networks on Euclidean data or
modify the graph structures. Yet these approaches are not well-understood
theoretically and could increase the overall computational complexity. In this
work, we draw inspirations from spectral graph embedding and propose
$\texttt{PowerEmbed}$ -- a simple layer-wise normalization technique to boost
MPNNs. We show $\texttt{PowerEmbed}$ can provably express the top-$k$ leading
eigenvectors of the graph operator, which prevents over-smoothing and is
agnostic to the graph topology; meanwhile, it produces a list of
representations ranging from local features to global signals, which avoids
over-squashing. We apply $\texttt{PowerEmbed}$ in a wide range of simulated and
real graphs and demonstrate its competitive performance, particularly for
heterophilous graphs.
- Abstract(参考訳): グラフニューラルネットワーク(GNN)は、非ユークリッドデータのための強力なディープラーニング手法である。
一般的なGNNはメッセージパッシングアルゴリズム(MPNN)で、局所グラフ地区の信号を集約して結合する。
しかし、浅いMPNNは長距離信号を見逃し、不均一なグラフでは性能が悪く、深いMPNNは過度なスムースや過剰なスキャッシングといった問題に悩まされる。
このような問題を緩和するため、既存の研究は通常、ユークリッドデータのニューラルネットワークのトレーニングやグラフ構造の変更から正規化技術を借りる。
しかし、これらのアプローチは理論的には十分に理解されておらず、全体的な計算複雑性を増大させる可能性がある。
本稿では、スペクトルグラフの埋め込みからインスピレーションを得て、MPNNを強化するための単純なレイヤワイド正規化手法である$\texttt{PowerEmbed}$を提案する。
例えば、$\texttt{PowerEmbed}$はグラフ演算子の先頭の固有ベクトルのトップ$kを確実に表現することができ、これは過剰なスムーシングを防ぎ、グラフトポロジに非依存である。
我々は、幅広いシミュレーションおよび実グラフに$\texttt{powerembed}$を適用し、その競合性能、特に不均一グラフについて実証する。
関連論文リスト
- On the Expressive Power of Subgraph Graph Neural Networks for Graphs with Bounded Cycles [17.29046077604317]
この研究は、最大$k$までの距離を持つ隣人からの情報を集約する$k$-hopサブグラフGNNを調査します。
我々は、$k$ホップ部分グラフ GNN がグラフ上の置換不変/同変連続関数を任意の誤差許容範囲内で2k+1$以上のサイクルなしで近似できることを証明した。
論文 参考訳(メタデータ) (2025-02-06T01:25:22Z) - Spatio-Spectral Graph Neural Networks [50.277959544420455]
比スペクトルグラフネットワーク(S$2$GNN)を提案する。
S$2$GNNは空間的およびスペクトル的にパラメータ化されたグラフフィルタを組み合わせる。
S$2$GNNsは、MPGNNsよりも厳密な近似理論誤差境界を生じる。
論文 参考訳(メタデータ) (2024-05-29T14:28:08Z) - T-GAE: Transferable Graph Autoencoder for Network Alignment [79.89704126746204]
T-GAEはグラフオートエンコーダフレームワークで、GNNの転送性と安定性を活用して、再トレーニングなしに効率的なネットワークアライメントを実現する。
実験の結果、T-GAEは最先端の最適化手法と最高のGNN手法を最大38.7%、50.8%で上回っていることがわかった。
論文 参考訳(メタデータ) (2023-10-05T02:58:29Z) - Training Graph Neural Networks on Growing Stochastic Graphs [114.75710379125412]
グラフニューラルネットワーク(GNN)は、ネットワーク化されたデータの意味のあるパターンを活用するために、グラフ畳み込みに依存している。
我々は,成長するグラフ列の極限オブジェクトであるグラフオンを利用して,非常に大きなグラフ上のGNNを学習することを提案する。
論文 参考訳(メタデータ) (2022-10-27T16:00:45Z) - FoSR: First-order spectral rewiring for addressing oversquashing in GNNs [0.0]
グラフニューラルネットワーク(GNN)は、グラフのエッジに沿ってメッセージを渡すことによって、グラフデータの構造を活用することができる。
本稿では,グラフにエッジを体系的に付加することで過疎化を防止する計算効率のよいアルゴリズムを提案する。
提案アルゴリズムは,いくつかのグラフ分類タスクにおいて,既存のグラフリウィリング手法よりも優れていることを示す。
論文 参考訳(メタデータ) (2022-10-21T07:58:03Z) - Expander Graph Propagation [0.0]
本稿では,拡張グラフ上での情報伝達に基づくエレガントなアプローチを提案する。
EGPは、セットアップに最小限の労力を要しながら、上記の懸念に対処できることを示します。
我々の分析は、GNNの過剰な監視に対処する、スケーラブルな方法の新たなクラスへの道を開くものだと信じています。
論文 参考訳(メタデータ) (2022-10-06T15:36:37Z) - VQ-GNN: A Universal Framework to Scale up Graph Neural Networks using
Vector Quantization [70.8567058758375]
VQ-GNNは、Vector Quantization(VQ)を使用して、パフォーマンスを損なうことなく、畳み込みベースのGNNをスケールアップするための普遍的なフレームワークである。
我々のフレームワークは,グラフ畳み込み行列の低ランク版と組み合わせた量子化表現を用いて,GNNの「隣の爆発」問題を回避する。
論文 参考訳(メタデータ) (2021-10-27T11:48:50Z) - Graph Neural Networks with Local Graph Parameters [1.8600631687568656]
ローカルグラフパラメータは、任意のグラフニューラルネットワーク(GNN)アーキテクチャに追加することができる。
我々の結果は、有限モデル理論と有限変数論理の深い結果とGNNを結びつける。
論文 参考訳(メタデータ) (2021-06-12T07:43:51Z) - Distance Encoding: Design Provably More Powerful Neural Networks for
Graph Representation Learning [63.97983530843762]
グラフニューラルネットワーク(GNN)はグラフ表現学習において大きな成功を収めている。
GNNは、実際には非常に異なるグラフ部分構造に対して同一の表現を生成する。
より強力なGNNは、最近高階試験を模倣して提案され、基礎となるグラフ構造を疎結合にできないため、非効率である。
本稿では,グラフ表現学習の新たなクラスとして距離分解(DE)を提案する。
論文 参考訳(メタデータ) (2020-08-31T23:15:40Z) - XGNN: Towards Model-Level Explanations of Graph Neural Networks [113.51160387804484]
グラフニューラルネットワーク(GNN)は、隣の情報を集約して組み合わせることでノードの特徴を学習する。
GNNはブラックボックスとして扱われ、人間の知的な説明が欠けている。
我々はモデルレベルでGNNを解釈する新しい手法 XGNN を提案する。
論文 参考訳(メタデータ) (2020-06-03T23:52:43Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。