論文の概要: Graph Neural Networks with polynomial activations have limited
expressivity
- arxiv url: http://arxiv.org/abs/2310.13139v7
- Date: Thu, 8 Feb 2024 02:10:26 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-12 20:18:46.754280
- Title: Graph Neural Networks with polynomial activations have limited
expressivity
- Title(参考訳): 多項式アクティベーションを持つグラフニューラルネットワークの表現性に制限がある
- Authors: Sammy Khalife
- Abstract要約: グラフニューラルネットワーク(GNN)は、一階述語論理の適切な断片によって特徴付けられる。
本稿では,GC2クエリはアクティベーション関数を持つGNNでは表現できないことを示す。
- 参考スコア(独自算出の注目度): 0.7614628596146602
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The expressivity of Graph Neural Networks (GNNs) can be entirely
characterized by appropriate fragments of the first order logic. Namely, any
query of the two variable fragment of graded modal logic (GC2) interpreted over
labeled graphs can be expressed using a GNN whose size depends only on the
depth of the query. As pointed out by [Barcelo & Al., 2020, Grohe, 2021], this
description holds for a family of activation functions, leaving the
possibibility for a hierarchy of logics expressible by GNNs depending on the
chosen activation function. In this article, we show that such hierarchy indeed
exists by proving that GC2 queries cannot be expressed by GNNs with polynomial
activation functions. This implies a separation between polynomial and popular
non polynomial activations (such as Rectified Linear Units) and answers an open
question formulated by [Grohe, 21].
- Abstract(参考訳): グラフニューラルネットワーク(GNN)の表現性は、第一次論理の適切な断片によって完全に特徴付けられる。
すなわち、ラベル付きグラフ上で解釈された2つの変分論理(GC2)の任意のクエリは、クエリの深さにのみ依存する大きさのGNNを用いて表現することができる。
barcelo & al., 2020, grohe, 2021] で指摘されているように、この記述は活性化関数の族であり、選択された活性化関数によってgnnによって表現できる論理の階層のポッシビビリティを残している。
本稿では,gc2クエリが多項式アクティベーション関数を持つgnnで表現できないことを証明して,このような階層構造が存在することを示す。
これは多項式と一般的な非多項式の活性化(Rectified Linear Units など)の分離を意味し、[Grohe, 21] で定式化された開問題に答える。
関連論文リスト
- Calibrate and Boost Logical Expressiveness of GNN Over Multi-Relational
and Temporal Graphs [8.095679736030146]
2つの変数と数量化器を持つ一階述語論理の断片である$mathcalFOC$NNについて検討する。
本稿では,線形時間で実行可能な,前処理ステップに似た単純なグラフ変換手法を提案する。
我々の結果は,グラフ変換によるR$2$-GNNが,合成および実世界のデータセットのベースライン手法よりも優れていることを一貫して示している。
論文 参考訳(メタデータ) (2023-11-03T00:33:24Z) - On the power of graph neural networks and the role of the activation function [1.795561427808824]
グラフニューラルネットワーク(GNN)の表現性に関する新しい結果を示す。
部分的活性化を持つ任意のGNNに対して、GNNが任意の反復数までルートを区別できないような、深さ2の非同型ルート木が一対存在することを証明している。
このことは、ニューラルネットワークの活性化関数を変更すると、グラフニューラルネットワークのパワーが劇的に変化することを示している。
論文 参考訳(メタデータ) (2023-07-10T15:59:09Z) - The Descriptive Complexity of Graph Neural Networks [2.6728900378310514]
グラフクエリは、GNNの有界深度ファミリーのクラスによって計算可能であることを示す。
注目すべきは、GNNファミリーは任意のリアルウェイトと幅広い種類のアクティベーション関数を使用することができることである。
GFO+Cでは1つのGNNで1つの線形アクティベーションと有理重みを持つクエリが組込み関係なく定義可能であることを示す。
論文 参考訳(メタデータ) (2023-03-08T14:32:59Z) - Some Might Say All You Need Is Sum [2.226803104060345]
グラフニューラルネットワーク(GNN)の表現性は、採用する集約関数に依存する。
我々は,Mean や Max GNN によって正確に計算できる基本関数が任意の Sum GNN によって近似できないことを証明した。
論文 参考訳(メタデータ) (2023-02-22T19:01:52Z) - Equivariant Polynomials for Graph Neural Networks [38.15983687193912]
グラフネットワーク(GNN)は本質的に表現力に制限がある。
本稿では、GNNがある程度の同変を計算する能力に基づく代替パワー階層を提案する。
これらの強化されたGNNは、複数のグラフ学習ベンチマークの実験において最先端の結果を示す。
論文 参考訳(メタデータ) (2023-02-22T18:53:38Z) - Representation Power of Graph Neural Networks: Improved Expressivity via
Algebraic Analysis [124.97061497512804]
標準グラフニューラルネットワーク (GNN) はWeisfeiler-Lehman (WL) アルゴリズムよりも差別的な表現を生成する。
また、白い入力を持つ単純な畳み込みアーキテクチャは、グラフの閉経路をカウントする同変の特徴を生じさせることを示した。
論文 参考訳(メタデータ) (2022-05-19T18:40:25Z) - Counting Substructures with Higher-Order Graph Neural Networks:
Possibility and Impossibility Results [58.277290855841976]
グラフニューラルネットワーク(GNN)の計算コストと表現力のトレードオフについて検討する。
新しいモデルでは、$k$のサブグラフをカウントでき、低次GNNの既知の制限を克服できることを示す。
いくつかの場合において、提案アルゴリズムは既存の高階$k$-GNNに比べて計算量を大幅に削減することができる。
論文 参考訳(メタデータ) (2020-12-06T03:42:54Z) - On Graph Neural Networks versus Graph-Augmented MLPs [51.23890789522705]
Graph-Augmented Multi-Layer Perceptrons (GA-MLPs)は、まずグラフ上の特定のマルチホップ演算子でノード機能を拡張する。
我々は,GA-MLPとGNNの表現力の分離を証明し,指数関数的に成長することを示す。
論文 参考訳(メタデータ) (2020-10-28T17:59:59Z) - Distance Encoding: Design Provably More Powerful Neural Networks for
Graph Representation Learning [63.97983530843762]
グラフニューラルネットワーク(GNN)はグラフ表現学習において大きな成功を収めている。
GNNは、実際には非常に異なるグラフ部分構造に対して同一の表現を生成する。
より強力なGNNは、最近高階試験を模倣して提案され、基礎となるグラフ構造を疎結合にできないため、非効率である。
本稿では,グラフ表現学習の新たなクラスとして距離分解(DE)を提案する。
論文 参考訳(メタデータ) (2020-08-31T23:15:40Z) - Improving Graph Neural Network Expressivity via Subgraph Isomorphism
Counting [63.04999833264299]
グラフサブストラクチャネットワーク(GSN)は,サブストラクチャエンコーディングに基づくトポロジ的に認識可能なメッセージパッシング方式である。
Wesfeiler-Leman (WL) グラフ同型テストよりも厳密に表現可能であることを示す。
グラフ分類と回帰タスクについて広範囲に評価を行い、様々な実世界の環境において最先端の結果を得る。
論文 参考訳(メタデータ) (2020-06-16T15:30:31Z) - Can Graph Neural Networks Count Substructures? [53.256112515435355]
グラフニューラルネットワーク(GNN)の能力について,属性付きグラフサブ構造をカウントする能力を用いて検討する。
我々は2種類のサブストラクチャカウントを区別する: インダクションサブグラフカウントとサブグラフカウント、および人気のあるGNNアーキテクチャに対する肯定的および否定的な回答である。
論文 参考訳(メタデータ) (2020-02-10T18:53:30Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。