論文の概要: A Non-Asymptotic Analysis of Oversmoothing in Graph Neural Networks
- arxiv url: http://arxiv.org/abs/2212.10701v1
- Date: Wed, 21 Dec 2022 00:33:59 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-22 15:50:50.389822
- Title: A Non-Asymptotic Analysis of Oversmoothing in Graph Neural Networks
- Title（参考訳）: グラフニューラルネットワークにおけるオーバースムーシングの非漸近的解析
- Authors: Xinyi Wu, Zhengdao Chen, William Wang, Ali Jadbabaie
- Abstract要約: 非漸近解析により,この現象の背後にあるメカニズムを特徴づける。
混合効果がデノナイジング効果を支配し始めると,過スムージングが生じることを示す。
以上の結果から,PPRは深い層での過度なスムース化を緩和するが,PPRベースのアーキテクチャは依然として浅い深さで最高の性能を発揮することが示唆された。
- 参考スコア（独自算出の注目度）: 33.35609077417775
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: A central challenge of building more powerful Graph Neural Networks (GNNs) is
the oversmoothing phenomenon, where increasing the network depth leads to
homogeneous node representations and thus worse classification performance.
While previous works have only demonstrated that oversmoothing is inevitable
when the number of graph convolutions tends to infinity, in this paper, we
precisely characterize the mechanism behind the phenomenon via a non-asymptotic
analysis. Specifically, we distinguish between two different effects when
applying graph convolutions -- an undesirable mixing effect that homogenizes
node representations in different classes, and a desirable denoising effect
that homogenizes node representations in the same class. By quantifying these
two effects on random graphs sampled from the Contextual Stochastic Block Model
(CSBM), we show that oversmoothing happens once the mixing effect starts to
dominate the denoising effect, and the number of layers required for this
transition is $O(\log N/\log (\log N))$ for sufficiently dense graphs with $N$
nodes. We also extend our analysis to study the effects of Personalized
PageRank (PPR) on oversmoothing. Our results suggest that while PPR mitigates
oversmoothing at deeper layers, PPR-based architectures still achieve their
best performance at a shallow depth and are outperformed by the graph
convolution approach on certain graphs. Finally, we support our theoretical
results with numerical experiments, which further suggest that the
oversmoothing phenomenon observed in practice may be exacerbated by the
difficulty of optimizing deep GNN models.
- Abstract（参考訳）: より強力なグラフニューラルネットワーク(GNN)を構築する上での中心的な課題は、ネットワーク深度の増加が均質なノード表現につながり、分類性能が悪化するオーバースムーシング現象である。
従来の研究では,グラフ畳み込みの数が無限大になる傾向にある場合にのみ,過度なスムース化が必然的であることが示されているが,本論文では,非漸近解析により,現象の背後にあるメカニズムを正確に特徴づける。
具体的には、異なるクラスでノード表現を均質化する望ましくない混合効果と、同じクラスでノード表現を均質化する望ましい分母効果であるグラフ畳み込みを適用する際の2つの異なる効果を区別する。
CSBM(Contextual Stochastic Block Model)からサンプリングされたランダムグラフに対するこれらの2つの効果を定量化することにより、混合効果がデノナイジング効果を支配下に置くと過スムース化が起こり、この遷移に必要な層数は$O(\log N/\log (\log N))$である。
パーソナライズされたPPR(Personalized PageRank)が過度なスムージングに与える影響について検討する。
以上の結果から,PPRは深い層での過度なスムーシングを緩和するが,PPRアーキテクチャは依然として浅い深さで最高の性能を達成し,グラフの畳み込み手法により性能が向上することが示唆された。
最後に, 数値実験による理論的結果を支持し, さらに, 深部GNNモデルの最適化が困難であることから, 実際に観測された過密現象が悪化することが示唆された。
関連論文リスト
- Unifying over-smoothing and over-squashing in graph neural networks: A
physics informed approach and beyond [45.370565281567984]
グラフニューラルネットワーク(GNN)は、グラフ構造化データの機械学習における主要なアプローチの1つである。
過密化、過密化、限られた表現力といった重要な計算課題は、GNNの性能に影響を与え続けている。
本稿では,マルチスケールヒートカーネルベースGNN (MHKG) を導入し,多様なフィルタ関数がノード特性に与える影響について検討する。
論文 参考訳（メタデータ） (2023-09-06T06:22:18Z) - Explaining and Adapting Graph Conditional Shift [28.532526595793364]
グラフニューラルネットワーク(GNN)は,グラフ構造化データに対して顕著な性能を示した。
最近の実証研究により、GNNは分布シフトに非常に敏感であることが示唆されている。
論文 参考訳（メタデータ） (2023-06-05T21:17:48Z) - Dynamic Causal Explanation Based Diffusion-Variational Graph Neural
Network for Spatio-temporal Forecasting [60.03169701753824]
時間予測のための動的拡散型グラフニューラルネットワーク(DVGNN)を提案する。
提案したDVGNNモデルは最先端のアプローチよりも優れ,Root Mean Squared Errorの結果が優れている。
論文 参考訳（メタデータ） (2023-05-16T11:38:19Z) - Addressing Heterophily in Node Classification with Graph Echo State
Networks [11.52174067809364]
ノード分類のためのグラフエコー状態ネットワーク(GESN)を用いた異種グラフの課題に対処する。
GESNはグラフのための貯水池計算モデルであり、ノードの埋め込みは訓練されていないメッセージパッシング関数によって計算される。
実験の結果, 貯水池モデルでは, ほぼ完全に訓練された深層モデルに対して, より優れた精度あるいは同等の精度が得られることがわかった。
論文 参考訳（メタデータ） (2023-05-14T19:42:31Z) - Resisting Graph Adversarial Attack via Cooperative Homophilous
Augmentation [60.50994154879244]
最近の研究では、グラフニューラルネットワークは弱く、小さな摂動によって簡単に騙されることが示されている。
本研究では,グラフインジェクションアタック(Graph Injection Attack)という,新興だが重要な攻撃に焦点を当てる。
本稿では,グラフデータとモデルの協調的同好性増強によるGIAに対する汎用防衛フレームワークCHAGNNを提案する。
論文 参考訳（メタデータ） (2022-11-15T11:44:31Z) - Effects of Graph Convolutions in Deep Networks [8.937905773981702]
多層ネットワークにおけるグラフ畳み込みの効果に関する厳密な理論的理解を示す。
単一のグラフ畳み込みは、多層ネットワークがデータを分類できる手段間の距離のレギュレーションを拡大することを示す。
ネットワーク層間の異なる組み合わせに配置されたグラフ畳み込みの性能に関する理論的および実証的な知見を提供する。
論文 参考訳（メタデータ） (2022-04-20T08:24:43Z) - SkipNode: On Alleviating Performance Degradation for Deep Graph
Convolutional Networks [84.30721808557871]
我々は,深いGCNにおける性能劣化の根本的な原因を探るため,理論的および実験的解析を行う。
我々は,深いGCNの性能劣化を克服するために,シンプルで効果的なプラグイン・アンド・プレイモジュールであるSkipnodeを提案する。
論文 参考訳（メタデータ） (2021-12-22T02:18:31Z) - Unrolling of Deep Graph Total Variation for Image Denoising [106.93258903150702]
本稿では,従来のグラフ信号フィルタリングと深い特徴学習を併用して,競合するハイブリッド設計を提案する。
解釈可能な低パスグラフフィルタを用い、最先端のDL復調方式DnCNNよりも80%少ないネットワークパラメータを用いる。
論文 参考訳（メタデータ） (2020-10-21T20:04:22Z) - Towards Deeper Graph Neural Networks [63.46470695525957]
グラフ畳み込みは近傍の集約を行い、最も重要なグラフ操作の1つである。
いくつかの最近の研究で、この性能劣化は過度に滑らかな問題に起因している。
本研究では,大きな受容領域からの情報を適応的に組み込むディープ適応グラフニューラルネットワーク(DAGNN)を提案する。
論文 参考訳（メタデータ） (2020-07-18T01:11:14Z) - Graph Ordering: Towards the Optimal by Learning [69.72656588714155]
グラフ表現学習は、ノード分類、予測、コミュニティ検出など、多くのグラフベースのアプリケーションで顕著な成功を収めている。
しかし,グラフ圧縮やエッジ分割などのグラフアプリケーションでは,グラフ表現学習タスクに還元することは極めて困難である。
本稿では,このようなアプリケーションの背後にあるグラフ順序付け問題に対して,新しい学習手法を用いて対処することを提案する。
論文 参考訳（メタデータ） (2020-01-18T09:14:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。