論文の概要: The Exact Class of Graph Functions Generated by Graph Neural Networks
- arxiv url: http://arxiv.org/abs/2202.08833v1
- Date: Thu, 17 Feb 2022 18:54:27 GMT
- ステータス: 処理完了
- システム内更新日: 2022-02-18 16:32:55.593185
- Title: The Exact Class of Graph Functions Generated by Graph Neural Networks
- Title（参考訳）: グラフニューラルネットワークが生成するグラフ関数の厳密なクラス
- Authors: Mohammad Fereydounian, Hamed Hassani, Javid Dadashkarimi, Amin Karbasi
- Abstract要約: グラフ関数と出力が同一のグラフニューラルネットワーク(GNN)?
本稿では,この疑問に完全に答え,GNNで表現可能なグラフ問題のクラスを特徴付ける。
この条件は2次的に多くの制約をチェックすることで効率よく検証できることを示す。
- 参考スコア（独自算出の注目度）: 43.25172578943894
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Given a graph function, defined on an arbitrary set of edge weights and node
features, does there exist a Graph Neural Network (GNN) whose output is
identical to the graph function? In this paper, we fully answer this question
and characterize the class of graph problems that can be represented by GNNs.
We identify an algebraic condition, in terms of the permutation of edge weights
and node features, which proves to be necessary and sufficient for a graph
problem to lie within the reach of GNNs. Moreover, we show that this condition
can be efficiently verified by checking quadratically many constraints. Note
that our refined characterization on the expressive power of GNNs are
orthogonal to those theoretical results showing equivalence between GNNs and
Weisfeiler-Lehman graph isomorphism heuristic. For instance, our
characterization implies that many natural graph problems, such as min-cut
value, max-flow value, and max-clique size, can be represented by a GNN. In
contrast, and rather surprisingly, there exist very simple graphs for which no
GNN can correctly find the length of the shortest paths between all nodes. Note
that finding shortest paths is one of the most classical problems in Dynamic
Programming (DP). Thus, the aforementioned negative example highlights the
misalignment between DP and GNN, even though (conceptually) they follow very
similar iterative procedures. Finally, we support our theoretical results by
experimental simulations.
- Abstract（参考訳）: エッジウェイトとノード特徴の任意のセットで定義されたグラフ関数が与えられたとき、グラフ関数と出力が同一であるグラフニューラルネットワーク(gnn)が存在するだろうか?
本稿では,この疑問に完全に答え,GNNで表現可能なグラフ問題のクラスを特徴付ける。
エッジ重みとノード特徴の置換の観点から代数的条件を同定し、グラフ問題がgnnの到達範囲内にあることを証明した。
さらに、この条件を2次的に多くの制約をチェックすることで効率よく検証できることを示す。
GNNの表現力に関する洗練された特徴付けは、GNNとWeisfeiler-Lehmanグラフの同値性を示す理論結果と直交する。
例えば、我々の特徴は、min-cut値、max-flow値、max-clique sizeなどの多くの自然グラフ問題をGNNで表現できることを示唆している。
対照的に、驚くべきことに、GNNがすべてのノード間の最も短いパスの長さを正しく見つけることができない非常に単純なグラフが存在する。
最短経路を見つけることは動的プログラミング(dp)における最も古典的な問題の1つである。
このように、前述の否定例は、(概念的には)非常に類似した反復的手順に従っているにもかかわらず、DPとGNNの相違を浮き彫りにしている。
最後に,実験シミュレーションによる理論結果を支持する。
関連論文リスト
- Uplifting the Expressive Power of Graph Neural Networks through Graph
Partitioning [3.236774847052122]
グラフ分割のレンズによるグラフニューラルネットワークの表現力について検討する。
我々は新しいGNNアーキテクチャ、すなわちグラフ分割ニューラルネットワーク(GPNN)を導入する。
論文 参考訳（メタデータ） (2023-12-14T06:08:35Z) - Robust Graph Neural Network based on Graph Denoising [10.564653734218755]
グラフニューラルネットワーク(GNN)は、非ユークリッドデータセットを扱う学習問題に対して、悪名高い代替手段として登場した。
本研究は,観測トポロジにおける摂動の存在を明示的に考慮した,GNNの堅牢な実装を提案する。
論文 参考訳（メタデータ） (2023-12-11T17:43:57Z) - NodeFormer: A Scalable Graph Structure Learning Transformer for Node
Classification [70.51126383984555]
本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。
効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。
グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
論文 参考訳（メタデータ） (2023-06-14T09:21:15Z) - Seq-HGNN: Learning Sequential Node Representation on Heterogeneous Graph [57.2953563124339]
本稿では,シーケンシャルノード表現,すなわちSeq-HGNNを用いた新しい異種グラフニューラルネットワークを提案する。
Heterogeneous Graph Benchmark (HGB) と Open Graph Benchmark (OGB) の4つの広く使われているデータセットについて広範な実験を行った。
論文 参考訳（メタデータ） (2023-05-18T07:27:18Z) - Training Graph Neural Networks on Growing Stochastic Graphs [114.75710379125412]
グラフニューラルネットワーク(GNN)は、ネットワーク化されたデータの意味のあるパターンを活用するために、グラフ畳み込みに依存している。
我々は,成長するグラフ列の極限オブジェクトであるグラフオンを利用して,非常に大きなグラフ上のGNNを学習することを提案する。
論文 参考訳（メタデータ） (2022-10-27T16:00:45Z) - Transferability Properties of Graph Neural Networks [125.71771240180654]
グラフニューラルネットワーク(GNN)は、中規模グラフでサポートされているデータから表現を学ぶのに成功している。
適度な大きさのグラフ上でGNNを訓練し、それらを大規模グラフに転送する問題について検討する。
その結果, (i) グラフサイズに応じて転送誤差が減少し, (ii) グラフフィルタは非線型性の散乱挙動によってGNNにおいて緩和されるような転送可能性-識別可能性トレードオフを有することがわかった。
論文 参考訳（メタデータ） (2021-12-09T00:08:09Z) - On the approximation capability of GNNs in node
classification/regression tasks [4.141514895639094]
グラフニューラルネットワーク(GNN)は、グラフ処理のための幅広い種類の接続モデルである。
GNNはノード分類/回帰タスクの確率の普遍近似であることを示す。
論文 参考訳（メタデータ） (2021-06-16T17:46:51Z) - Towards Scale-Invariant Graph-related Problem Solving by Iterative
Homogeneous Graph Neural Networks [39.370875358317946]
現在のグラフニューラルネットワーク(GNN)は、多くのグラフ解析問題を解く際に、スケール(グラフサイズ、グラフ径、エッジウェイトなど)に関する一般化性に欠ける。
まず,グラフサイズに対する共通グラフ理論アルゴリズムの反復回数の依存性に着想を得て,GNNにおけるメッセージパッシングプロセスの終了を,進捗に応じて順応的に学習する。
第二に、多くのグラフ理論アルゴリズムがグラフの重みに関して均一であるという事実に着想を得て、一般のGを変換するために、普遍的同次関数近似器である同次変換層を導入する。
論文 参考訳（メタデータ） (2020-10-26T12:57:28Z) - Distance Encoding: Design Provably More Powerful Neural Networks for
Graph Representation Learning [63.97983530843762]
グラフニューラルネットワーク(GNN)はグラフ表現学習において大きな成功を収めている。
GNNは、実際には非常に異なるグラフ部分構造に対して同一の表現を生成する。
より強力なGNNは、最近高階試験を模倣して提案され、基礎となるグラフ構造を疎結合にできないため、非効率である。
本稿では,グラフ表現学習の新たなクラスとして距離分解(DE)を提案する。
論文 参考訳（メタデータ） (2020-08-31T23:15:40Z) - Expressive Power of Invariant and Equivariant Graph Neural Networks [10.419350129060598]
Folklore Graph Neural Networks (FGNN) は、与えられたテンソル次数に対してこれまで提案されてきた最も表現力のあるアーキテクチャである。
FGNNはこの問題の解決方法を学ぶことができ、既存のアルゴリズムよりも平均的なパフォーマンスが向上する。
論文 参考訳（メタデータ） (2020-06-28T16:35:45Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。