論文の概要: Analysis of Corrected Graph Convolutions
- arxiv url: http://arxiv.org/abs/2405.13987v2
- Date: Sat, 14 Dec 2024 05:02:54 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-12-17 13:53:03.155253
- Title: Analysis of Corrected Graph Convolutions
- Title(参考訳): 修正グラフ畳み込みの解析
- Authors: Robert Wang, Aseem Baranwal, Kimon Fountoulakis,
- Abstract要約: 最先端の機械学習モデルは、しばしばデータに複数のグラフ畳み込みを使用する。
過度に多くのグラフ畳み込みが性能を著しく低下させることを示す。
正確な分類では、分離性閾値を最大$O(logn/logn)$修正畳み込みまで指数関数的に改善できることが示される。
- 参考スコア(独自算出の注目度): 10.991475575578855
- License:
- Abstract: Machine learning for node classification on graphs is a prominent area driven by applications such as recommendation systems. State-of-the-art models often use multiple graph convolutions on the data, as empirical evidence suggests they can enhance performance. However, it has been shown empirically and theoretically, that too many graph convolutions can degrade performance significantly, a phenomenon known as oversmoothing. In this paper, we provide a rigorous theoretical analysis, based on the two-class contextual stochastic block model (CSBM), of the performance of vanilla graph convolution from which we remove the principal eigenvector to avoid oversmoothing. We perform a spectral analysis for $k$ rounds of corrected graph convolutions, and we provide results for partial and exact classification. For partial classification, we show that each round of convolution can reduce the misclassification error exponentially up to a saturation level, after which performance does not worsen. We also extend this analysis to the multi-class setting with features distributed according to a Gaussian mixture model. For exact classification, we show that the separability threshold can be improved exponentially up to $O({\log{n}}/{\log\log{n}})$ corrected convolutions.
- Abstract(参考訳): グラフ上のノード分類のための機械学習は、レコメンデーションシステムのようなアプリケーションによって駆動される顕著な領域である。
最先端モデルは、しばしばデータ上の複数のグラフ畳み込みを使用する。
しかし、経験的および理論的には、過剰なグラフ畳み込みが性能を著しく低下させることができることが示されている。
本稿では,2種類の文脈確率ブロックモデル(CSBM)に基づく厳密な理論的解析を行い,バニラグラフ畳み込みの性能について述べる。
我々は、補正グラフ畳み込みの$k$ラウンドのスペクトル分析を行い、部分的および正確な分類結果を提供する。
部分的な分類では,各ラウンドの畳み込みにより,飽和レベルまで指数関数的に誤分類誤差が減少し,性能が悪化しないことを示す。
また、この分析をガウス混合モデルに従って分布する特徴を持つマルチクラス設定に拡張する。
正確な分類については、分離性しきい値が指数関数的に$O({\log{n}}/{\log\log{n}})$修正畳み込みまで改善できることが示される。
関連論文リスト
- Graph Generation via Spectral Diffusion [51.60814773299899]
本稿では,1)グラフラプラシア行列のスペクトル分解と2)拡散過程に基づく新しいグラフ生成モデルGRASPを提案する。
具体的には、固有ベクトルと固有値のサンプリングにデノナイジングモデルを用い、グラフラプラシアン行列と隣接行列を再構成する。
我々の置換不変モデルは各ノードの固有ベクトルに連結することでノードの特徴を扱える。
論文 参考訳(メタデータ) (2024-02-29T09:26:46Z) - Graph Out-of-Distribution Generalization with Controllable Data
Augmentation [51.17476258673232]
グラフニューラルネットワーク(GNN)は,グラフ特性の分類において異常な性能を示した。
トレーニングとテストデータの選択バイアスが原因で、分散偏差が広まっています。
仮想サンプルの分布偏差を測定するためのOODキャリブレーションを提案する。
論文 参考訳(メタデータ) (2023-08-16T13:10:27Z) - Explaining and Adapting Graph Conditional Shift [28.532526595793364]
グラフニューラルネットワーク(GNN)は,グラフ構造化データに対して顕著な性能を示した。
最近の実証研究により、GNNは分布シフトに非常に敏感であることが示唆されている。
論文 参考訳(メタデータ) (2023-06-05T21:17:48Z) - A Non-Asymptotic Analysis of Oversmoothing in Graph Neural Networks [33.35609077417775]
非漸近解析により,この現象の背後にあるメカニズムを特徴づける。
混合効果がデノナイジング効果を支配し始めると,過スムージングが生じることを示す。
以上の結果から,PPRは深い層での過度なスムース化を緩和するが,PPRベースのアーキテクチャは依然として浅い深さで最高の性能を発揮することが示唆された。
論文 参考訳(メタデータ) (2022-12-21T00:33:59Z) - Graph Polynomial Convolution Models for Node Classification of
Non-Homophilous Graphs [52.52570805621925]
本研究では,高階グラフ畳み込みからの効率的な学習と,ノード分類のための隣接行列から直接学習する。
得られたモデルが新しいグラフと残留スケーリングパラメータをもたらすことを示す。
提案手法は,非親和性パラメータのノード分類における精度の向上を実証する。
論文 参考訳(メタデータ) (2022-09-12T04:46:55Z) - Beyond spectral gap: The role of the topology in decentralized learning [58.48291921602417]
機械学習モデルのデータ並列最適化では、労働者はモデルの推定値を改善するために協力する。
本稿では、労働者が同じデータ分散を共有するとき、疎結合な分散最適化の正確な図面を描くことを目的とする。
我々の理論は深層学習における経験的観察と一致し、異なるグラフトポロジーの相対的メリットを正確に記述する。
論文 参考訳(メタデータ) (2022-06-07T08:19:06Z) - Effects of Graph Convolutions in Deep Networks [8.937905773981702]
多層ネットワークにおけるグラフ畳み込みの効果に関する厳密な理論的理解を示す。
単一のグラフ畳み込みは、多層ネットワークがデータを分類できる手段間の距離のレギュレーションを拡大することを示す。
ネットワーク層間の異なる組み合わせに配置されたグラフ畳み込みの性能に関する理論的および実証的な知見を提供する。
論文 参考訳(メタデータ) (2022-04-20T08:24:43Z) - Graph Kernel Neural Networks [53.91024360329517]
本稿では、グラフ上の内部積を計算するカーネル関数であるグラフカーネルを用いて、標準畳み込み演算子をグラフ領域に拡張することを提案する。
これにより、入力グラフの埋め込みを計算する必要のない完全に構造的なモデルを定義することができる。
私たちのアーキテクチャでは,任意の種類のグラフカーネルをプラグインすることが可能です。
論文 参考訳(メタデータ) (2021-12-14T14:48:08Z) - Graph Convolution for Semi-Supervised Classification: Improved Linear
Separability and Out-of-Distribution Generalization [3.308743964406687]
グラフ畳み込みを適用した後にデータを分類することに最も基本的なレベルで依存する新しいクラスの学習モデルが登場しました。
グラフの畳み込みは、データを約1/sqrtD$の係数で線形に分離できる状態を拡張していることを示す。
論文 参考訳(メタデータ) (2021-02-13T17:46:57Z) - Multilayer Clustered Graph Learning [66.94201299553336]
我々は、観測された層を代表グラフに適切に集約するために、データ忠実度用語として対照的な損失を用いる。
実験により,本手法がクラスタクラスタw.r.tに繋がることが示された。
クラスタリング問題を解くためのクラスタリングアルゴリズムを学習する。
論文 参考訳(メタデータ) (2020-10-29T09:58:02Z) - The Power of Graph Convolutional Networks to Distinguish Random Graph
Models: Short Version [27.544219236164764]
グラフ畳み込みネットワーク(GCN)はグラフ表現学習において広く使われている手法である。
サンプルグラフの埋め込みに基づいて異なるランダムグラフモデルを区別するGCNのパワーについて検討する。
論文 参考訳(メタデータ) (2020-02-13T17:58:42Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。