論文の概要: Analysis of Graph Neural Networks with Theory of Markov Chains
- arxiv url: http://arxiv.org/abs/2211.06605v1
- Date: Sat, 12 Nov 2022 08:03:57 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-15 18:59:15.069161
- Title: Analysis of Graph Neural Networks with Theory of Markov Chains
- Title(参考訳): マルコフ連鎖理論を用いたグラフニューラルネットワークの解析
- Authors: Weichen Zhao, Chenguang Wang, Congying Han, Tiande Guo
- Abstract要約: 我々は,GNN研究において重要な問題であるエンフェーバー平滑化について研究する。
演算子一貫性GNNはマルコフ的意味で指数速度で過度に平滑化を回避できないという結論を下す。
ニューラルネットワークのトレーニングに柔軟に追加できる正規化項を提案する。
- 参考スコア(独自算出の注目度): 2.017675281820044
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: In this paper, we provide a theoretical tool for the interpretation and
analysis of \emph{graph neural networks} (GNNs). We use Markov chains on graphs
to mathematically model the forward propagation processes of GNNs. The graph
neural networks are divided into two classes of operator-consistent and
operator-inconsistent based on whether the Markov chains are time-homogeneous.
Based on this, we study \emph{over-smoothing} which is an important problem in
GNN research. We attribute the over-smoothing problem to the convergence of an
arbitrary initial distribution to a stationary distribution. We prove the
effectiveness of the previous methods for alleviating the over-smoothing
problem. Further, we give the conclusion that operator-consistent GNN cannot
avoid over-smoothing at an exponential rate in the Markovian sense. For
operator-inconsistent GNN, we theoretically give a sufficient condition for
avoiding over-smoothing. Based on this condition, we propose a regularization
term which can be flexibly added to the training of the neural network.
Finally, we design experiments to verify the effectiveness of this condition.
Results show that our proposed sufficient condition not only improves the
performance but also alleviates the over-smoothing phenomenon.
- Abstract(参考訳): 本稿では,emph{graph neural network} (GNN) の解釈と解析のための理論的ツールを提供する。
グラフ上のマルコフ連鎖を用いてGNNの前方伝播過程を数学的にモデル化する。
グラフニューラルネットワークは、マルコフ連鎖が時間的均一であるかどうかに基づいて、演算子一貫性とオペレータ一貫性の2つのクラスに分けられる。
そこで我々は,GNN研究において重要な問題であるemph{over-smoothing}について検討する。
我々は, 任意の初期分布を定常分布に収束させることで, オーバースムーシング問題を解決した。
オーバースムーシング問題を緩和するための従来の手法の有効性を実証する。
さらに、演算子一貫性GNNはマルコフの指数速度での過度な平滑化を回避できないという結論を与える。
演算子不整合GNNの場合、理論的には過剰なスムーシングを避けるのに十分な条件を与える。
この条件に基づき、ニューラルネットワークのトレーニングに柔軟に追加できる正規化項を提案する。
最後に,この条件の有効性を検証する実験を設計する。
その結果,提案する十分条件により性能が向上するだけでなく,過飽和現象を緩和できることがわかった。
関連論文リスト
- Understanding Oversmoothing in Diffusion-Based GNNs From the Perspective
of Operator Semigroup Theory [12.946113359807551]
本稿では拡散型グラフニューラルネット(GNN)における過剰な問題に関する新しい研究について述べる。
過平滑化が拡散作用素のエルゴード性に本質的に関連していることを厳密に証明する。
実験結果から,このエルゴード性破壊項はディリクレエネルギーによって測定された過密化を効果的に緩和することが明らかとなった。
論文 参考訳(メタデータ) (2024-02-23T13:44:57Z) - Robust Node Representation Learning via Graph Variational Diffusion
Networks [7.335425547621226]
近年,グラフ構造における摂動により,GNNに基づくノード表現学習が著しく劣化する可能性が示唆されている。
摂動の存在下で頑健なノード表現を学習するために、GNNを保護するための様々な研究が提案されている。
本稿では,ガウス雑音を効果的に制御し,摂動グラフ上のロバスト性を保護する新しいノードエンコーダであるグラフ変分拡散ネットワーク(GVDN)を提案する。
論文 参考訳(メタデータ) (2023-12-18T03:18:53Z) - Neural Tangent Kernels Motivate Graph Neural Networks with
Cross-Covariance Graphs [94.44374472696272]
グラフニューラルネットワーク(GNN)の文脈におけるNTKとアライメントについて検討する。
その結果、2層GNNのアライメントの最適性に関する理論的保証が確立された。
これらの保証は、入力と出力データの相互共分散の関数であるグラフシフト演算子によって特徴づけられる。
論文 参考訳(メタデータ) (2023-10-16T19:54:21Z) - Bregman Graph Neural Network [27.64062763929748]
ノード分類タスクでは、GNNによって誘導される滑らか化効果は、連結ノードの表現と過剰な均質化ラベルを同化する傾向がある。
本稿では,Bregman 距離の概念に触発された GNN のための新しい二段階最適化フレームワークを提案する。
論文 参考訳(メタデータ) (2023-09-12T23:54:24Z) - Demystifying Oversmoothing in Attention-Based Graph Neural Networks [23.853636836842604]
グラフニューラルネットワーク(GNN)におけるオーバースムーシング(Oversmoothing in Graph Neural Networks)とは、ネットワーク深度の増加がノードの均質表現につながる現象である。
これまでの研究により、グラフ畳み込みネットワーク(GCN)は指数関数的に表現力を失うことが判明した。
グラフアテンション機構が過剰なスムースを緩和できるかどうかはまだ議論の余地がある。
論文 参考訳(メタデータ) (2023-05-25T14:31:59Z) - ResNorm: Tackling Long-tailed Degree Distribution Issue in Graph Neural
Networks via Normalization [80.90206641975375]
本稿では,正規化によるGNNの性能向上に焦点をあてる。
グラフ中のノード次数の長期分布を調べることにより、GNNの新しい正規化法を提案する。
ResNormの$scale$操作は、尾ノードの精度を向上させるために、ノード単位の標準偏差(NStd)分布を再設定する。
論文 参考訳(メタデータ) (2022-06-16T13:49:09Z) - Generalizing Graph Neural Networks on Out-Of-Distribution Graphs [51.33152272781324]
トレーニンググラフとテストグラフの分散シフトを考慮せずにグラフニューラルネットワーク(GNN)を提案する。
このような環境では、GNNは、たとえ素早い相関であるとしても、予測のためのトレーニングセットに存在する微妙な統計的相関を利用する傾向がある。
本稿では,スプリアス相関の影響を排除するため,StableGNNと呼ばれる一般的な因果表現フレームワークを提案する。
論文 参考訳(メタデータ) (2021-11-20T18:57:18Z) - Is Homophily a Necessity for Graph Neural Networks? [50.959340355849896]
グラフニューラルネットワーク(GNN)は、多数のグラフベースの機械学習タスクに適した学習表現において大きな進歩を見せている。
GNNはホモフィリーな仮定によりうまく機能し、異種ノードが接続する異種グラフへの一般化に失敗したと広く信じられている。
最近の研究は、このような不均一な制限を克服する新しいアーキテクチャを設計し、ベースライン性能の低さと、この概念の証拠として、いくつかの異種グラフベンチマークデータセットに対するアーキテクチャの改善を引用している。
我々の実験では、標準グラフ畳み込みネットワーク(GCN)が実際よりも優れた性能を実現できることを実証的に見出した。
論文 参考訳(メタデータ) (2021-06-11T02:44:00Z) - Optimization and Generalization Analysis of Transduction through
Gradient Boosting and Application to Multi-scale Graph Neural Networks [60.22494363676747]
現在のグラフニューラルネットワーク(GNN)は、オーバースムーシング(over-smoothing)と呼ばれる問題のため、自分自身を深くするのは難しいことが知られている。
マルチスケールGNNは、オーバースムーシング問題を緩和するための有望なアプローチである。
マルチスケールGNNを含むトランスダクティブ学習アルゴリズムの最適化と一般化を保証する。
論文 参考訳(メタデータ) (2020-06-15T17:06:17Z) - Stochastic Graph Neural Networks [123.39024384275054]
グラフニューラルネットワーク(GNN)は、分散エージェント調整、制御、計画に応用したグラフデータの非線形表現をモデル化する。
現在のGNNアーキテクチャは理想的なシナリオを前提として,環境やヒューマンファクタ,あるいは外部攻撃によるリンク変動を無視している。
これらの状況において、GNNは、トポロジカルなランダム性を考慮していない場合、その分散タスクに対処することができない。
論文 参考訳(メタデータ) (2020-06-04T08:00:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。