論文の概要: Zero-One Laws of Graph Neural Networks
- arxiv url: http://arxiv.org/abs/2301.13060v1
- Date: Mon, 30 Jan 2023 17:02:23 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-31 13:56:42.117603
- Title: Zero-One Laws of Graph Neural Networks
- Title(参考訳): グラフニューラルネットワークのゼロワン法則
- Authors: Sam Adam-Day, Theodor Mihai Iliant, \.Ismail \.Ilkan Ceylan
- Abstract要約: グラフニューラルネットワーク(GNN)は、グラフ上の機械学習のためのデファクト標準ディープラーニングアーキテクチャである。
我々はGNNの表現と外挿能力に関する新しい理論的視点を提供する。
ErdHos-R'enyi モデルから拡大するグラフを描くと、そのようなグラフが特定の出力にマップされる確率は 0 か 1 のいずれかになる傾向があることを示す。
- 参考スコア(独自算出の注目度): 9.700635713828696
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Graph neural networks (GNNs) are de facto standard deep learning
architectures for machine learning on graphs. This has led to a large body of
work analyzing the capabilities and limitations of these models, particularly
pertaining to their representation and extrapolation capacity. We offer a novel
theoretical perspective on the representation and extrapolation capacity of
GNNs, by answering the question: how do GNNs behave as the number of graph
nodes become very large? Under mild assumptions, we show that when we draw
graphs of increasing size from the Erd\H{o}s-R\'enyi model, the probability
that such graphs are mapped to a particular output by a class of GNN
classifiers tends to either zero or to one. This class includes the popular
graph convolutional network architecture. The result establishes 'zero-one
laws' for these GNNs, and analogously to other convergence laws, entails
theoretical limitations on their capacity. We empirically verify our results,
observing that the theoretical asymptotic limits are evident already on
relatively small graphs.
- Abstract(参考訳): グラフニューラルネットワーク(GNN)は、グラフ上の機械学習のためのデファクト標準ディープラーニングアーキテクチャである。
これにより、これらのモデルの能力と限界、特にそれらの表現と外挿能力に関する多くの作業が分析された。
グラフノードの数が非常に大きくなるにつれて、GNNはどのように振る舞うのか?
穏やかな仮定の下では、Erd\H{o}s-R\'enyi モデルから増大するグラフを描くと、そのようなグラフがGNN分類器のクラスによって特定の出力にマップされる確率は 0 または 1 の傾向を示す。
このクラスは一般的なグラフ畳み込みネットワークアーキテクチャを含んでいる。
その結果、これらのGNNに対して「ゼロワン法則」を確立し、他の収束法則と類似して、その能力に関する理論的制限を課す。
理論的な漸近限界は、比較的小さなグラフ上で既に明らかなものであることを観察し、実験的に検証した。
関連論文リスト
- Graph neural network outputs are almost surely asymptotically constant [8.01812577223632]
グラフニューラルネットワーク(GNN)は、グラフ上のさまざまな学習タスクのための主要なアーキテクチャである。
我々は、GNN確率分類器の予測がより大きなグラフに適用されるにつれてどのように進化するかを考察する。
出力は定数関数に収束し、これらの分類器が一様に表現できる上限となることを示す。
論文 参考訳(メタデータ) (2024-03-06T17:40:26Z) - Limits, approximation and size transferability for GNNs on sparse graphs
via graphops [44.02161831977037]
我々は,GNNを構成する集約演算など,グラフから導出される演算子の極限を取るという観点から考える。
我々の結果は、密でスパースなグラフ、およびグラフ極限の様々な概念に当てはまる。
論文 参考訳(メタデータ) (2023-06-07T15:04:58Z) - Training Graph Neural Networks on Growing Stochastic Graphs [114.75710379125412]
グラフニューラルネットワーク(GNN)は、ネットワーク化されたデータの意味のあるパターンを活用するために、グラフ畳み込みに依存している。
我々は,成長するグラフ列の極限オブジェクトであるグラフオンを利用して,非常に大きなグラフ上のGNNを学習することを提案する。
論文 参考訳(メタデータ) (2022-10-27T16:00:45Z) - A Topological characterisation of Weisfeiler-Leman equivalence classes [0.0]
グラフニューラルネットワーク(GNN)は、グラフと信号をグラフ上で処理することを目的とした学習モデルである。
本稿では、GNNが区別できないグラフのクラスを完全に特徴づけるために、被覆空間の理論に依存する。
データセット内の識別不能グラフの数は,ノード数とともに指数関数的に増加することを示す。
論文 参考訳(メタデータ) (2022-06-23T17:28:55Z) - Transferability Properties of Graph Neural Networks [125.71771240180654]
グラフニューラルネットワーク(GNN)は、中規模グラフでサポートされているデータから表現を学ぶのに成功している。
適度な大きさのグラフ上でGNNを訓練し、それらを大規模グラフに転送する問題について検討する。
その結果, (i) グラフサイズに応じて転送誤差が減少し, (ii) グラフフィルタは非線型性の散乱挙動によってGNNにおいて緩和されるような転送可能性-識別可能性トレードオフを有することがわかった。
論文 参考訳(メタデータ) (2021-12-09T00:08:09Z) - Is Homophily a Necessity for Graph Neural Networks? [50.959340355849896]
グラフニューラルネットワーク(GNN)は、多数のグラフベースの機械学習タスクに適した学習表現において大きな進歩を見せている。
GNNはホモフィリーな仮定によりうまく機能し、異種ノードが接続する異種グラフへの一般化に失敗したと広く信じられている。
最近の研究は、このような不均一な制限を克服する新しいアーキテクチャを設計し、ベースライン性能の低さと、この概念の証拠として、いくつかの異種グラフベンチマークデータセットに対するアーキテクチャの改善を引用している。
我々の実験では、標準グラフ畳み込みネットワーク(GCN)が実際よりも優れた性能を実現できることを実証的に見出した。
論文 参考訳(メタデータ) (2021-06-11T02:44:00Z) - Increase and Conquer: Training Graph Neural Networks on Growing Graphs [116.03137405192356]
本稿では,このグラフからBernoulliをサンプリングしたグラフ上でGNNをトレーニングすることで,WNN(Graphon Neural Network)を学習する問題を考察する。
これらの結果から着想を得た大規模グラフ上でGNNを学習するアルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-06-07T15:05:59Z) - Distance Encoding: Design Provably More Powerful Neural Networks for
Graph Representation Learning [63.97983530843762]
グラフニューラルネットワーク(GNN)はグラフ表現学習において大きな成功を収めている。
GNNは、実際には非常に異なるグラフ部分構造に対して同一の表現を生成する。
より強力なGNNは、最近高階試験を模倣して提案され、基礎となるグラフ構造を疎結合にできないため、非効率である。
本稿では,グラフ表現学習の新たなクラスとして距離分解(DE)を提案する。
論文 参考訳(メタデータ) (2020-08-31T23:15:40Z) - XGNN: Towards Model-Level Explanations of Graph Neural Networks [113.51160387804484]
グラフニューラルネットワーク(GNN)は、隣の情報を集約して組み合わせることでノードの特徴を学習する。
GNNはブラックボックスとして扱われ、人間の知的な説明が欠けている。
我々はモデルレベルでGNNを解釈する新しい手法 XGNN を提案する。
論文 参考訳(メタデータ) (2020-06-03T23:52:43Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。