論文の概要: On the power of graph neural networks and the role of the activation function

• arxiv url: http://arxiv.org/abs/2307.04661v3
• Date: Fri, 23 Feb 2024 22:05:34 GMT
• ステータス: 処理完了
• システム内更新日: 2024-02-28 00:37:51.420624
• Title: On the power of graph neural networks and the role of the activation function
• Title（参考訳）: グラフニューラルネットワークのパワーと活性化関数の役割について
• Authors: Sammy Khalife, Amitabh Basu
• Abstract要約: グラフニューラルネットワーク(GNN)の表現性に関する新しい結果を示す。 グラフ入力サイズでアーキテクチャサイズが成長しない任意のGNNに対して、GNNが任意の反復数までルートを区別できないように、深さ2の非同型ルート木が一対存在することを証明している。
• 参考スコア（独自算出の注目度）: 2.1212179660694104
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this article we present new results about the expressivity of Graph Neural Networks (GNNs). We prove that for any GNN with piecewise polynomial activations, whose architecture size does not grow with the graph input sizes, there exists a pair of non-isomorphic rooted trees of depth two such that the GNN cannot distinguish their root vertex up to an arbitrary number of iterations. The proof relies on tools from the algebra of symmetric polynomials. In contrast, it was already known that unbounded GNNs (those whose size is allowed to change with the graph sizes) with piecewise polynomial activations can distinguish these vertices in only two iterations. Our results imply a strict separation between bounded and unbounded size GNNs, answering an open question formulated by [Grohe, 2021]. We next prove that if one allows activations that are not piecewise polynomial, then in two iterations a single neuron perceptron can distinguish the root vertices of any pair of nonisomorphic trees of depth two (our results hold for activations like the sigmoid, hyperbolic tan and others). This shows how the power of graph neural networks can change drastically if one changes the activation function of the neural networks. The proof of this result utilizes the Lindemann-Weierstrauss theorem from transcendental number theory.
• Abstract（参考訳）: 本稿では,グラフニューラルネットワーク(gnns)の表現性に関する新たな結果について述べる。 グラフの入力サイズでアーキテクチャサイズが増大しない部分的な多項式活性化を持つ任意のgnnに対して、gnnが任意の回数の反復までルート頂点を識別できないような深さ2の非同型根木が一対存在することを証明した。 この証明は対称多項式の代数からのツールに依存する。 対照的に、分割多項式アクティベーションを持つ非有界gnn(そのサイズはグラフサイズで変更できる)は、2回の反復でこれらの頂点を区別できることが既に知られていた。 この結果は,[Grohe, 2021]で定式化されたオープンな質問に答え, 有界サイズと非有界サイズのGNNの厳密な分離を示唆する。 次に、分割多項式でない活性化を許容すると、2つの反復で1つのニューロンパーセプトロンが深さ2の任意の非同型な木の根頂点を区別できることを証明する(我々の結果は、sgmoid、双曲的tanなどの活性化をも持つ)。 これは、ニューラルネットワークのアクティベーション関数を変更すると、グラフニューラルネットワークのパワーが劇的に変化することを示している。 この結果の証明は超越数論のリンデマン・ヴァイエルシュトラウスの定理を用いている。

関連論文リスト

• Graph neural networks and non-commuting operators [4.912318087940015]
  我々は,グラフトン・タプルニューラルネットワークの極限理論を開発し,それを普遍的な伝達可能性定理の証明に利用する。 我々の理論的結果は、GNNのよく知られた移動可能性定理を、複数の同時グラフの場合にまで拡張する。 得られたモデルの安定性を確実に実施する訓練手順を導出する。
  論文  参考訳（メタデータ） (2024-11-06T21:17:14Z)
• Degree-based stratification of nodes in Graph Neural Networks [66.17149106033126]
  グラフニューラルネットワーク(GNN)アーキテクチャを変更して,各グループのノードに対して,重み行列を個別に学習する。 このシンプルな実装変更により、データセットとGNNメソッドのパフォーマンスが改善されているようだ。
  論文  参考訳（メタデータ） (2023-12-16T14:09:23Z)
• Uplifting the Expressive Power of Graph Neural Networks through Graph Partitioning [3.236774847052122]
  グラフ分割のレンズによるグラフニューラルネットワークの表現力について検討する。 我々は新しいGNNアーキテクチャ、すなわちグラフ分割ニューラルネットワーク(GPNN)を導入する。
  論文  参考訳（メタデータ） (2023-12-14T06:08:35Z)
• The logic of rational graph neural networks [0.7614628596146602]
  我々は,GC2 の深度 3$ のクエリは,合理的なアクティベーション関数を持つ GNN では表現できないことを証明した。 これは、すべての非ポリノミカル活性化関数がGNNの最大表現性を参照しているわけではないことを示している。 また、一階述語論理(RGC2)の有理サブフラグメントを示し、すべてのグラフに対して有理GNNがRGC2クエリを均一に表現できることを証明する。
  論文  参考訳（メタデータ） (2023-10-19T20:32:25Z)
• Equivariant Polynomials for Graph Neural Networks [38.15983687193912]
  グラフネットワーク(GNN)は本質的に表現力に制限がある。 本稿では、GNNがある程度の同変を計算する能力に基づく代替パワー階層を提案する。 これらの強化されたGNNは、複数のグラフ学習ベンチマークの実験において最先端の結果を示す。
  論文  参考訳（メタデータ） (2023-02-22T18:53:38Z)
• Graph Neural Network Bandits [89.31889875864599]
  グラフ構造データ上で定義された報酬関数を用いた帯域最適化問題を考察する。 この設定の主な課題は、大きなドメインへのスケーリングと、多くのノードを持つグラフへのスケーリングである。 グラフニューラルネットワーク(GNN)を用いて報酬関数を推定できることを示す。
  論文  参考訳（メタデータ） (2022-07-13T18:12:36Z)
• Graph-adaptive Rectified Linear Unit for Graph Neural Networks [64.92221119723048]
  グラフニューラルネットワーク(GNN)は、従来の畳み込みを非ユークリッドデータでの学習に拡張することで、目覚ましい成功を収めた。 本稿では,周辺情報を利用した新しいパラメトリックアクティベーション機能であるグラフ適応整流線形ユニット(GRELU)を提案する。 我々は,GNNのバックボーンと様々な下流タスクによって,プラグアンドプレイGRELU法が効率的かつ効果的であることを示す包括的実験を行った。
  論文  参考訳（メタデータ） (2022-02-13T10:54:59Z)
• Permutation-equivariant and Proximity-aware Graph Neural Networks with Stochastic Message Passing [88.30867628592112]
  グラフニューラルネットワーク(GNN)は、グラフ上の新たな機械学習モデルである。 置換等価性と近接認識性は、GNNにとって非常に望ましい2つの重要な特性である。 既存のGNNは、主にメッセージパッシング機構に基づいており、同時に2つの特性を保存できないことを示す。 ノードの近さを保つため,既存のGNNをノード表現で拡張する。
  論文  参考訳（メタデータ） (2020-09-05T16:46:56Z)
• Expressive Power of Invariant and Equivariant Graph Neural Networks [10.419350129060598]
  Folklore Graph Neural Networks (FGNN) は、与えられたテンソル次数に対してこれまで提案されてきた最も表現力のあるアーキテクチャである。 FGNNはこの問題の解決方法を学ぶことができ、既存のアルゴリズムよりも平均的なパフォーマンスが向上する。
  論文  参考訳（メタデータ） (2020-06-28T16:35:45Z)
• Deep Polynomial Neural Networks [77.70761658507507]
  $Pi$Netsは拡張に基づいた関数近似の新しいクラスである。 $Pi$Netsは、画像生成、顔検証、および3Dメッシュ表現学習という3つの困難なタスクで、最先端の結果を生成する。
  論文  参考訳（メタデータ） (2020-06-20T16:23:32Z)
• Can Graph Neural Networks Count Substructures? [53.256112515435355]
  グラフニューラルネットワーク(GNN)の能力について,属性付きグラフサブ構造をカウントする能力を用いて検討する。 我々は2種類のサブストラクチャカウントを区別する: インダクションサブグラフカウントとサブグラフカウント、および人気のあるGNNアーキテクチャに対する肯定的および否定的な回答である。
  論文  参考訳（メタデータ） (2020-02-10T18:53:30Z)

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

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