論文の概要: Not too little, not too much: a theoretical analysis of graph (over)smoothing

• arxiv url: http://arxiv.org/abs/2205.12156v1
• Date: Tue, 24 May 2022 15:39:31 GMT
• ステータス: 処理完了
• システム内更新日: 2022-05-25 13:18:18.908407
• Title: Not too little, not too much: a theoretical analysis of graph (over)smoothing
• Title（参考訳）: あまり多くない、あまり多くない:グラフ(上)の平滑化の理論解析
• Authors: Nicolas Keriven
• Abstract要約: 我々は,各ノードが隣人の特徴量の平均を順次受信する,エンフェメアンアグリゲーションによるグラフの平滑化を解析する。 グラフの平滑化は、主データよりも高速に非主データ方向を縮小し、回帰に役立ち、同時に崩壊するよりも早くコミュニティ内のノードを縮小することを示す。
• 参考スコア（独自算出の注目度）: 8.7314407902481
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We analyze graph smoothing with \emph{mean aggregation}, where each node successively receives the average of the features of its neighbors. Indeed, it has quickly been observed that Graph Neural Networks (GNNs), which generally follow some variant of Message-Passing (MP) with repeated aggregation, may be subject to the \emph{oversmoothing} phenomenon: by performing too many rounds of MP, the node features tend to converge to a non-informative limit. In the case of mean aggregation, for connected graphs, the node features become constant across the whole graph. At the other end of the spectrum, it is intuitively obvious that \emph{some} MP rounds are necessary, but existing analyses do not exhibit both phenomena at once: beneficial ``finite'' smoothing and oversmoothing in the limit. In this paper, we consider simplified linear GNNs, and rigorously analyze two examples for which a finite number of mean aggregation steps provably improves the learning performance, before oversmoothing kicks in. We consider a latent space random graph model, where node features are partial observations of the latent variables and the graph contains pairwise relationships between them. We show that graph smoothing restores some of the lost information, up to a certain point, by two phenomenon: graph smoothing shrinks non-principal directions in the data faster than principal ones, which is useful for regression, and shrinks nodes within communities faster than they collapse together, which improves classification.
• Abstract（参考訳）: グラフの平滑化を<emph{mean aggregation}>で解析し,各ノードは隣接ノードの特徴の平均を逐次受信する。 実際、グラフニューラルネットワーク(gnns)は、繰り返し集約されるメッセージパッシング(mp)のいくつかの変種に従っているが、これは \emph{oversmoothing} 現象の対象となる可能性がある。 平均集約の場合、連結グラフの場合、ノードの特徴はグラフ全体にわたって一定となる。 スペクトルの反対側では、 \emph{some} MP ラウンドが必要であることは直感的には明らかであるが、既存の分析では両方の現象が同時に現れていない。 本稿では,単純な線形gnnについて検討し,有限個の平均集約ステップが学習性能を向上し,過度にスムーシングする前の2つの例を厳格に解析する。 我々は、ノード特徴が潜在変数の部分観測であり、グラフがそれらの間の対関係を含む潜在空間確率グラフモデルを考える。 グラフの平滑化は、主データよりも高速に非主データ方向を縮小し、回帰に役立ち、同時に崩壊するよりも早くコミュニティ内のノードを縮小し、分類を改善するという2つの現象によって、失われた情報のいくつかをある時点まで復元することを示した。

関連論文リスト

• Generalization Bounds for Message Passing Networks on Mixture of Graphons [21.457225542391267]
  メッセージパッシングニューラルネットワーク(MPNN)の一般化機能について検討する。 正規化和アグリゲーションと平均アグリゲーションを持つMPNNに対して、特に一般化バウンダリを導出する。 以上の結果から,MPNNはトレーニングセットのサイズよりも複雑度が高いため,依然として効果的に一般化可能であることが示唆された。
  論文  参考訳（メタデータ） (2024-04-04T14:26:47Z)
• Random Geometric Graph Alignment with Graph Neural Networks [8.08963638000146]
  グラフニューラルネットワークは、2つのグラフの頂点間の未知の1対1マッピングを復元可能であることを示す。 また、ノイズレベルの条件が対数的要因に厳密であることも証明した。 ノイズレベルが少なくとも一定である場合、この直接マッチングは完全なリカバリが得られず、グラフニューラルネットワークは、グラフの大きさのパワーと同じくらいの速さで成長するノイズレベルを許容できることを示した。
  論文  参考訳（メタデータ） (2024-02-12T00:18:25Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。 効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。 グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
  論文  参考訳（メタデータ） (2023-06-14T09:21:15Z)
• What functions can Graph Neural Networks compute on random graphs? The role of Positional Encoding [0.0]
  我々は,グラフニューラルネットワーク(GNN)の大規模グラフに対する理論的理解を深めることを目指しており,その表現力に着目している。 近年、GNNは、非常に一般的なランダムグラフモデルにおいて、ノード数が増加するにつれて、特定の関数に収束することを示した。
  論文  参考訳（メタデータ） (2023-05-24T07:09:53Z)
• Rethinking Explaining Graph Neural Networks via Non-parametric Subgraph Matching [68.35685422301613]
  そこで我々はMatchExplainerと呼ばれる新しい非パラメトリックな部分グラフマッチングフレームワークを提案し、説明的部分グラフを探索する。 ターゲットグラフと他のインスタンスを結合し、ノードに対応する距離を最小化することで最も重要な結合部分構造を識別する。 合成および実世界のデータセットの実験は、最先端のパラメトリックベースラインをかなりのマージンで上回り、MatchExplainerの有効性を示す。
  論文  参考訳（メタデータ） (2023-01-07T05:14:45Z)
• Effects of Graph Convolutions in Deep Networks [8.937905773981702]
  多層ネットワークにおけるグラフ畳み込みの効果に関する厳密な理論的理解を示す。 単一のグラフ畳み込みは、多層ネットワークがデータを分類できる手段間の距離のレギュレーションを拡大することを示す。 ネットワーク層間の異なる組み合わせに配置されたグラフ畳み込みの性能に関する理論的および実証的な知見を提供する。
  論文  参考訳（メタデータ） (2022-04-20T08:24:43Z)
• Graph Denoising with Framelet Regularizer [25.542429117462547]
  本稿では,特徴雑音と構造雑音の両面からグラフデータの正則化を行う。 本モデルでは, グラフが汚染されている場合でも, 一般的なグラフ畳み込みと比較して, 性能が著しく向上する。
  論文  参考訳（メタデータ） (2021-11-05T05:17:23Z)
• Multilayer Clustered Graph Learning [66.94201299553336]
  我々は、観測された層を代表グラフに適切に集約するために、データ忠実度用語として対照的な損失を用いる。 実験により,本手法がクラスタクラスタw.r.tに繋がることが示された。 クラスタリング問題を解くためのクラスタリングアルゴリズムを学習する。
  論文  参考訳（メタデータ） (2020-10-29T09:58:02Z)
• Spectral Embedding of Graph Networks [76.27138343125985]
  ローカルノードの類似性と接続性、グローバル構造をトレードオフする教師なしグラフ埋め込みを導入する。 埋め込みは一般化されたグラフ Laplacian に基づいており、固有ベクトルは1つの表現においてネットワーク構造と近傍近傍の両方をコンパクトにキャプチャする。
  論文  参考訳（メタデータ） (2020-09-30T04:59:10Z)
• Towards Deeper Graph Neural Networks [63.46470695525957]
  グラフ畳み込みは近傍の集約を行い、最も重要なグラフ操作の1つである。 いくつかの最近の研究で、この性能劣化は過度に滑らかな問題に起因している。 本研究では,大きな受容領域からの情報を適応的に組み込むディープ適応グラフニューラルネットワーク(DAGNN)を提案する。
  論文  参考訳（メタデータ） (2020-07-18T01:11:14Z)
• Graph Pooling with Node Proximity for Hierarchical Representation Learning [80.62181998314547]
  本稿では,ノード近接を利用したグラフプーリング手法を提案し,そのマルチホップトポロジを用いたグラフデータの階層的表現学習を改善する。 その結果,提案したグラフプーリング戦略は,公開グラフ分類ベンチマークデータセットの集合において,最先端のパフォーマンスを達成できることが示唆された。
  論文  参考訳（メタデータ） (2020-06-19T13:09:44Z)

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

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