論文の概要: Graph neural network outputs are almost surely asymptotically constant
- arxiv url: http://arxiv.org/abs/2403.03880v1
- Date: Wed, 6 Mar 2024 17:40:26 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-07 14:00:29.041952
- Title: Graph neural network outputs are almost surely asymptotically constant
- Title(参考訳): グラフニューラルネットワークの出力はほぼ漸近的に一定である
- Authors: Sam Adam-Day, Michael Benedikt, \.Ismail \.Ilkan Ceylan, Ben
Finkelshtein
- Abstract要約: グラフニューラルネットワーク(GNN)は、グラフ上のさまざまな学習タスクのための主要なアーキテクチャである。
我々は、GNN確率分類器の予測がより大きなグラフに適用されるにつれてどのように進化するかを考察する。
出力は定数関数に収束し、これらの分類器が一様に表現できる上限となることを示す。
- 参考スコア(独自算出の注目度): 8.01812577223632
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Graph neural networks (GNNs) are the predominant architectures for a variety
of learning tasks on graphs. We present a new angle on the expressive power of
GNNs by studying how the predictions of a GNN probabilistic classifier evolve
as we apply it on larger graphs drawn from some random graph model. We show
that the output converges to a constant function, which upper-bounds what these
classifiers can express uniformly. This convergence phenomenon applies to a
very wide class of GNNs, including state of the art models, with aggregates
including mean and the attention-based mechanism of graph transformers. Our
results apply to a broad class of random graph models, including the (sparse)
Erd\H{o}s-R\'enyi model and the stochastic block model. We empirically validate
these findings, observing that the convergence phenomenon already manifests
itself on graphs of relatively modest size.
- Abstract(参考訳): グラフニューラルネットワーク(GNN)は、グラフ上のさまざまな学習タスクのための主要なアーキテクチャである。
我々は,gnnの確率的分類器の予測が,ランダムグラフモデルから描画されたより大きなグラフに対してどのように発展するかを調べることにより,gnnの表現力に対する新たな角度を示す。
出力は定数関数に収束し、これらの分類器が一様に表現できることを上界に示す。
この収束現象は、平均を含む集約とグラフトランスフォーマーの注意に基づくメカニズムを含む、芸術モデルの状態を含む非常に幅広い種類のGNNに適用される。
この結果は、(スパース) erd\h{o}s-r\'enyiモデルや確率ブロックモデルを含む幅広いランダムグラフモデルに適用できる。
これらの知見を実証的に検証し、収束現象が比較的小さなグラフ上にすでに現れていることを観察した。
関連論文リスト
- Advective Diffusion Transformers for Topological Generalization in Graph
Learning [69.2894350228753]
グラフ拡散方程式は、様々なグラフトポロジーの存在下で、どのように外挿して一般化するかを示す。
本稿では,新たなグラフエンコーダのバックボーンであるAdvective Diffusion Transformer (ADiT)を提案する。
論文 参考訳(メタデータ) (2023-10-10T08:40:47Z) - Graph Neural Network-Inspired Kernels for Gaussian Processes in
Semi-Supervised Learning [4.644263115284322]
グラフニューラルネットワーク(GNN)は、半教師付き学習において、グラフ構造化データのモデルとして期待できるクラスとして最近登場した。
この帰納バイアスをGPに導入して,グラフ構造化データの予測性能を向上させる。
これらのグラフベースのカーネルは、各GNNと比較して、競合する分類と回帰性能、および時間の長所をもたらすことを示す。
論文 参考訳(メタデータ) (2023-02-12T01:07:56Z) - Zero-One Laws of Graph Neural Networks [7.783835522945603]
グラフニューラルネットワーク(GNN)は、グラフ上の機械学習のためのデファクト標準ディープラーニングアーキテクチャである。
我々はGNNの表現と外挿能力に関する新しい理論的視点を提供する。
ErdHos-R'enyi モデルから拡大するグラフを描くと、そのようなグラフが特定の出力にマップされる確率は 0 か 1 のいずれかになる傾向があることを示す。
論文 参考訳(メタデータ) (2023-01-30T17:02:23Z) - Relation Embedding based Graph Neural Networks for Handling
Heterogeneous Graph [58.99478502486377]
我々は、同種GNNが不均一グラフを扱うのに十分な能力を持つように、シンプルで効率的なフレームワークを提案する。
具体的には、エッジ型関係と自己ループ接続の重要性を埋め込むために、関係1つのパラメータのみを使用する関係埋め込みベースのグラフニューラルネットワーク(RE-GNN)を提案する。
論文 参考訳(メタデータ) (2022-09-23T05:24:18Z) - Stability and Generalization Capabilities of Message Passing Graph
Neural Networks [4.691259009382681]
グラフ分類におけるMPNNの一般化能力について検討する。
経験的損失と統計的損失の間の一般化ギャップに非漸近的境界を導出する。
これは、グラフに適用されたMPNNが、グラフが識別する幾何学的モデルに適用されたMPNNを近似することを示すことで証明される。
論文 参考訳(メタデータ) (2022-02-01T18:37:53Z) - Graph Neural Networks with Parallel Neighborhood Aggregations for Graph
Classification [14.112444998191698]
グラフニューラルネットワーク(GNN)モデルを用いたグラフ分類に着目し、並列に配置された近傍グラフ演算子のバンクを用いてノード特徴をプリ計算する。
これらのGNNモデルには、事前計算によるトレーニングと推論時間の削減という自然な利点がある。
本研究は,様々な実世界のデータセット上で,開発モデルが最先端の性能を達成することを数値実験により実証する。
論文 参考訳(メタデータ) (2021-11-22T19:19:40Z) - Explicit Pairwise Factorized Graph Neural Network for Semi-Supervised
Node Classification [59.06717774425588]
本稿では,グラフ全体を部分的に観測されたマルコフ確率場としてモデル化するEPFGNN(Explicit Pairwise Factorized Graph Neural Network)を提案する。
出力-出力関係をモデル化するための明示的なペアワイズ要素を含み、入力-出力関係をモデル化するためにGNNバックボーンを使用する。
本研究では,グラフ上での半教師付きノード分類の性能を効果的に向上できることを示す。
論文 参考訳(メタデータ) (2021-07-27T19:47:53Z) - Generalization of graph network inferences in higher-order graphical
models [5.33024001730262]
確率的グラフィカルモデルは、複雑な統計構造を記述する強力なツールを提供する。
辺化のような推論は 一般グラフでは難解です
我々は,多変数相互作用を含むグラフィカルモデル上での高速な近似推定を実現するために,Recurrent Factor Graph Neural Network (RF-GNN) を定義する。
論文 参考訳(メタデータ) (2021-07-12T20:51:27Z) - Graph and graphon neural network stability [122.06927400759021]
グラフネットワーク(GNN)は、ネットワークデータの有意義な表現を生成するためにグラフ構造の知識に依存する学習アーキテクチャである。
我々は,GNNの安定性を,グラファイトと呼ばれるカーネルオブジェクトを用いて解析する。
論文 参考訳(メタデータ) (2020-10-23T16:55:56Z) - A Unified View on Graph Neural Networks as Graph Signal Denoising [49.980783124401555]
グラフニューラルネットワーク(GNN)は,グラフ構造化データの学習表現において顕著に普及している。
本研究では,代表的GNNモデル群における集約過程を,グラフ記述問題の解法とみなすことができることを数学的に確立する。
UGNNから派生した新しいGNNモデルADA-UGNNをインスタンス化し、ノード間の適応的滑らかさでグラフを処理する。
論文 参考訳(メタデータ) (2020-10-05T04:57:18Z) - Block-Approximated Exponential Random Graphs [77.4792558024487]
指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。
本稿では,非自明なERGに対する近似フレームワークを提案する。
我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
論文 参考訳(メタデータ) (2020-02-14T11:42:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。