論文の概要: Representation Power of Graph Convolutions : Neural Tangent Kernel Analysis

• arxiv url: http://arxiv.org/abs/2210.09809v1
• Date: Tue, 18 Oct 2022 12:28:37 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-19 15:34:54.560182
• Title: Representation Power of Graph Convolutions : Neural Tangent Kernel Analysis
• Title（参考訳）: グラフ畳み込みの表現力 : ニューラルタンジェントカーネル解析
• Authors: Mahalakshmi Sabanayagam, Pascal Esser, Debarghya Ghoshdastidar
• Abstract要約: グラフに基づく畳み込みは、隣接行列$A$の対称正規化において支配的な選択として現れている。 いくつかの実験的な研究は、行正規化$D-1A$がノード分類においてそれを上回ることを示している。 行正規化は、基底となるクラス構造を他の畳み込みよりもよく保存することを示す。
• 参考スコア（独自算出の注目度）: 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. Therefore, understanding its influence 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 $A$, defined as $D^{-1/2}AD^{-1/2}$, being the most widely adopted one, where $D$ is the degree matrix. However, some empirical studies show that row normalization $D^{-1}A$ outperforms it in node classification. Despite the widespread use of GNNs, there is no rigorous theoretical study on the representation power of these convolution operators, that could explain this behavior. In this work, we analyze the influence of the graph convolutions theoretically using Graph Neural Tangent Kernel in a semi-supervised node classification setting. Under a Degree Corrected Stochastic Block Model, we prove that: (i) row normalization preserves the underlying class structure better than other convolutions; (ii) performance degrades with network depth due to over-smoothing, but the loss in class information is the slowest in row normalization; (iii) skip connections retain the class information even at infinite depth, thereby eliminating over-smoothing. We finally validate our theoretical findings on real datasets.
• Abstract（参考訳）: グラフニューラルネットワーク(GNN)の基本原理は、グラフ畳み込みを用いて隣接するノードを集約することで、データの構造情報を利用することである。 したがって,ネットワーク性能への影響を理解することが重要である。 グラフラプラシアンに基づく畳み込みは、随伴行列 $a$ の対称正規化($d^{-1/2}ad^{-1/2}$ と定義される)において支配的な選択として現れ、最も広く採用されており、ここでは$d$ が次数行列である。 しかし、いくつかの実験的な研究により、行正規化$D^{-1}A$はノード分類においてそれより優れていることが示されている。 GNNの普及にもかかわらず、これらの畳み込み作用素の表現力に関する厳密な理論的研究は行われておらず、この振る舞いを説明することができる。 本研究では,グラフニューラルタンジェントカーネルを用いた半教師付きノード分類におけるグラフ畳み込みの影響を理論的に解析する。 Degree Corrected Stochastic Block Modelでは、次のように証明します。 i) 行正規化は、下層のクラス構造を他の畳み込みよりもよく保存する。 (II) 過度なスムース化によりネットワーク深さが低下するが、クラス情報の損失は行の正規化において最も遅い。 (iii)スキップ接続は、無限の深さでもクラス情報を保持し、過剰なスムーシングをなくす。 実データから理論的な結果が得られた。

関連論文リスト

• 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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。