論文の概要: Analysis of Convolutions, Non-linearity and Depth in Graph Neural
Networks using Neural Tangent Kernel
- arxiv url: http://arxiv.org/abs/2210.09809v2
- Date: Mon, 10 Jul 2023 09:54:27 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-11 22:34:08.198001
- Title: Analysis of Convolutions, Non-linearity and Depth in Graph Neural
Networks using Neural Tangent Kernel
- Title（参考訳）: ニューラルタンジェントカーネルを用いたグラフニューラルネットワークの畳み込み・非線形・深さの解析
- Authors: Mahalakshmi Sabanayagam, Pascal Esser, Debarghya Ghoshdastidar
- Abstract要約: グラフニューラルネットワーク(GNN)は、隣接するノードを集約することで、データの構造情報を活用するように設計されている。
半教師付きノード分類設定におけるグラフニューラルカーネルを用いて,GNNアーキテクチャの異なる側面の影響を理論的に解析する。
i) 線形ネットワークはReLUネットワークと同じくらいのクラス情報をキャプチャし、 (ii) 行正規化は、他の畳み込みよりも基礎となるクラス構造を保存し、 (iii) 過スムージングによりネットワーク深さが低下し、 (iv) スキップ接続は無限の深さでもクラス情報を保持し、過スムーズを除去する。
- 参考スコア（独自算出の注目度）: 6.211414805908918
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The fundamental principle of Graph Neural Networks (GNNs) is to exploit the
structural information of the data by aggregating the neighboring nodes using a
`graph convolution' in conjunction with a suitable choice for the network
architecture, such as depth and activation functions. Therefore, understanding
the influence of each of the design choice on the network performance is
crucial. Convolutions based on graph Laplacian have emerged as the dominant
choice with the symmetric normalization of the adjacency matrix as the most
widely adopted one. However, some empirical studies show that row normalization
of the adjacency matrix outperforms it in node classification. Despite the
widespread use of GNNs, there is no rigorous theoretical study on the
representation power of these convolutions, that could explain this behavior.
Similarly, the empirical observation of the linear GNNs performance being on
par with non-linear ReLU GNNs lacks rigorous theory.
In this work, we theoretically analyze the influence of different aspects of
the GNN architecture using the Graph Neural Tangent Kernel in a semi-supervised
node classification setting. Under the population Degree Corrected Stochastic
Block Model, we prove that: (i) linear networks capture the class information
as good as ReLU networks; (ii) row normalization preserves the underlying class
structure better than other convolutions; (iii) performance degrades with
network depth due to over-smoothing, but the loss in class information is the
slowest in row normalization; (iv) skip connections retain the class
information even at infinite depth, thereby eliminating over-smoothing. We
finally validate our theoretical findings numerically and on real datasets such
as Cora and Citeseer.
- Abstract（参考訳）: グラフニューラルネットワーク(gnns)の基本原理は、深度やアクティベーション関数などのネットワークアーキテクチャに適した選択と合わせて、隣接ノードを「グラフ畳み込み」を用いて集約することで、データの構造情報を活用することである。
したがって,ネットワーク性能に対する設計選択の影響を理解することが重要である。
グラフラプラシアンに基づく畳み込みは、最も広く採用されている隣接行列の対称正規化によって支配的な選択として現れる。
しかし、いくつかの実験研究では、隣接行列の行正規化がノード分類でそれを上回ることが示されている。
GNNの普及にもかかわらず、これらの畳み込みの表現力に関する厳密な理論的研究は行われていない。
同様に、非線形relu gnnsと同等の線形gnns性能の実証的観察は厳密な理論を欠いている。
本研究では,GNNアーキテクチャの異なる側面の影響を,半教師付きノード分類設定におけるグラフニューラルタンジェントカーネルを用いて理論的に解析する。
人口次数補正された確率的ブロックモデルの下では
(i)線形ネットワークは、ReLUネットワークと同様に、クラス情報をキャプチャする。
(ii) 行の正規化は,下位のクラス構造を他の畳み込みよりもよく保存する。
(iii)過剰なスムーシングによりネットワークの深さで性能が低下するが、クラス情報の損失は行の正規化において最も遅い。
(iv)スキップ接続は無限の深さでもクラス情報を保持し、過度なスムーシングを除去する。
理論的な結果がCoraやCiteseerのような実際のデータセット上で数値的に検証された。
関連論文リスト
- A Manifold Perspective on the Statistical Generalization of Graph Neural Networks [84.01980526069075]
我々は、スペクトル領域の多様体からサンプリングされたグラフ上のGNNの統計的一般化理論を確立するために多様体の視点を取る。
我々はGNNの一般化境界が対数スケールのグラフのサイズとともに線形に減少し、フィルタ関数のスペクトル連続定数とともに線形的に増加することを証明した。
論文 参考訳（メタデータ） (2024-06-07T19:25:02Z) - On the Initialization of Graph Neural Networks [10.153841274798829]
グラフニューラルネットワーク層間の前方・後方伝播のばらつきを解析する。
GNN最適化(Virgo)における可変不安定化のための新しい手法を提案する。
15のデータセットで包括的な実験を行い、Virgoが優れたモデルパフォーマンスをもたらすことを示す。
論文 参考訳（メタデータ） (2023-12-05T09:55:49Z) - Neural Tangent Kernels Motivate Graph Neural Networks with
Cross-Covariance Graphs [94.44374472696272]
グラフニューラルネットワーク(GNN)の文脈におけるNTKとアライメントについて検討する。
その結果、2層GNNのアライメントの最適性に関する理論的保証が確立された。
これらの保証は、入力と出力データの相互共分散の関数であるグラフシフト演算子によって特徴づけられる。
論文 参考訳（メタデータ） (2023-10-16T19:54:21Z) - Label Deconvolution for Node Representation Learning on Large-scale
Attributed Graphs against Learning Bias [75.44877675117749]
本稿では,GNNの逆写像に対する新しい,スケーラブルな近似による学習バイアスを軽減するために,ラベルの効率的な正規化手法,すなわちラベルのデコンボリューション(LD)を提案する。
実験では、LDはOpen Graphデータセットのベンチマークで最先端のメソッドを大幅に上回っている。
論文 参考訳（メタデータ） (2023-09-26T13:09:43Z) - Benign Overfitting in Deep Neural Networks under Lazy Training [72.28294823115502]
データ分布が適切に分離された場合、DNNは分類のためのベイズ最適テスト誤差を達成できることを示す。
よりスムーズな関数との補間により、より一般化できることを示す。
論文 参考訳（メタデータ） (2023-05-30T19:37:44Z) - Geometric Graph Filters and Neural Networks: Limit Properties and
Discriminability Trade-offs [122.06927400759021]
本稿では,グラフニューラルネットワーク (GNN) と多様体ニューラルネットワーク (MNN) の関係について検討する。
これらのグラフ上の畳み込みフィルタとニューラルネットワークが連続多様体上の畳み込みフィルタとニューラルネットワークに収束することを示す。
論文 参考訳（メタデータ） (2023-05-29T08:27:17Z) - Understanding Non-linearity in Graph Neural Networks from the
Bayesian-Inference Perspective [33.01636846541052]
グラフニューラルネットワーク(GNN)は、グラフよりも多くの予測タスクにおいて優位性を示している。
ノード分類タスクにおけるGNNにおける非線形性の関数について検討する。
論文 参考訳（メタデータ） (2022-07-22T19:36:12Z) - Adaptive Kernel Graph Neural Network [21.863238974404474]
グラフニューラルネットワーク(GNN)は,グラフ構造化データの表現学習において大きな成功を収めている。
本稿では,AKGNN(Adaptive Kernel Graph Neural Network)という新しいフレームワークを提案する。
AKGNNは、最初の試みで最適なグラフカーネルに統一的に適応することを学ぶ。
評価されたベンチマークデータセットで実験を行い、提案したAKGNNの優れた性能を示す有望な結果を得た。
論文 参考訳（メタデータ） (2021-12-08T20:23:58Z) - Fast Learning of Graph Neural Networks with Guaranteed Generalizability:
One-hidden-layer Case [93.37576644429578]
グラフニューラルネットワーク(GNN)は、グラフ構造化データから実際に学習する上で、近年大きな進歩を遂げている。
回帰問題と二項分類問題の両方に隠れ層を持つGNNの理論的に基底的な一般化可能性解析を行う。
論文 参考訳（メタデータ） (2020-06-25T00:45:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。