論文の概要: The logic of rational graph neural networks
- arxiv url: http://arxiv.org/abs/2310.13139v8
- Date: Tue, 13 Aug 2024 17:12:03 GMT
- ステータス: 処理完了
- システム内更新日: 2024-08-14 23:14:44.138419
- Title: The logic of rational graph neural networks
- Title(参考訳): 有理グラフニューラルネットワークの論理
- Authors: Sammy Khalife,
- Abstract要約: 我々は,GC2 の深度 3$ のクエリは,合理的なアクティベーション関数を持つ GNN では表現できないことを証明した。
これは、すべての非ポリノミカル活性化関数がGNNの最大表現性を参照しているわけではないことを示している。
また、一階述語論理(RGC2)の有理サブフラグメントを示し、すべてのグラフに対して有理GNNがRGC2クエリを均一に表現できることを証明する。
- 参考スコア(独自算出の注目度): 0.7614628596146602
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The expressivity of Graph Neural Networks (GNNs) can be described via appropriate fragments of the first order logic. Any query of the two variable fragment of graded modal logic (GC2) interpreted over labeled graphs can be expressed using a Rectified Linear Unit (ReLU) GNN whose size does not grow with graph input sizes [Barcelo & Al., 2020]. Conversely, a GNN expresses at most a query of GC2, for any choice of activation function. In this article, we prove that some GC2 queries of depth $3$ cannot be expressed by GNNs with any rational activation function. This shows that not all non-polynomial activation functions confer GNNs maximal expressivity, answering a open question formulated by [Grohe, 2021]. This result is also in contrast with the efficient universal approximation properties of rational feedforward neural networks investigated by [Boull\'e & Al., 2020]. We also present a rational subfragment of the first order logic (RGC2), and prove that rational GNNs can express RGC2 queries uniformly over all graphs.
- Abstract(参考訳): グラフニューラルネットワーク(GNN)の表現性は、一階述語論理の適切な断片を通して記述することができる。
ラベル付きグラフ上で解釈された2つの変分片(GC2)の問合せは、グラフ入力サイズで成長しないRectified Linear Unit (ReLU) GNNを用いて表現することができる。
逆に、GNNは、任意のアクティベーション関数の選択に対して、GC2のクエリを最大で表現する。
本稿では,GC2 の深度 3$ のクエリが,合理的なアクティベーション関数を持つ GNN では表現できないことを証明する。
このことは、すべての非多項式活性化関数が、[Grohe, 2021]で定式化されたオープンな質問に答えて、GNNの最大表現性を参照しているわけではないことを示している。
この結果は、[Boull\'e & Al., 2020] による有理フィードフォワードニューラルネットワークの効率的な普遍近似特性とも対照的である。
また、一階述語論理(RGC2)の有理サブフラグメントを示し、すべてのグラフに対して有理GNNがRGC2クエリを均一に表現できることを証明する。
関連論文リスト
- On Efficiently Representing Regular Languages as RNNs [49.88310438099143]
RNNは、人間の言語で広く使われている有界階層構造を効率的に表現できることを示す。
これは、RNNの成功が階層をモデル化する能力と結びついていることを示唆している。
我々は,RNNが従来主張していたより大規模なLMを効率的に表現できることを示す。
論文 参考訳(メタデータ) (2024-02-24T13:42:06Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。