論文の概要: Graph Neural Networks with polynomial activations have limited expressivity

• arxiv url: http://arxiv.org/abs/2310.13139v3
• Date: Fri, 8 Dec 2023 13:38:55 GMT
• ステータス: 処理完了
• システム内更新日: 2023-12-11 18:18:36.860916
• 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 possibility 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, 2021].
• Abstract（参考訳）: グラフニューラルネットワーク(GNN)の表現性は、一階述語論理の適切な断片によって完全に特徴づけられる。 すなわち、ラベル付きグラフ上で解釈された2つの変分論理(GC2)の任意のクエリは、クエリの深さにのみ依存する大きさのGNNを用いて表現することができる。 この記述は[Barcelo & Al., 2020, Grohe, 2021]で指摘されているように、活性化関数の族であり、選択された活性化関数に依存するGNNによって表現される論理階層の可能性を残している。 本稿では,gc2クエリが多項式アクティベーション関数を持つgnnで表現できないことを証明して,このような階層構造が存在することを示す。 これは多項式と一般的な非多項アクティベーション(直交線形単位など)の分離を意味し、[grohe, 2021]で定式化された公開質問に答える。

関連論文リスト

• Is uniform expressivity too restrictive? Towards efficient expressivity of graph neural networks [0.6445605125467574]
  グラフニューラルネットワーク(GNN)は、入力グラフのサイズによってパラメータなしでクエリを表現できる。 入力グラフの最大次数に対してパラメータの数が対数的であるように,多くのGNNがGC2クエリを効率的に表現できることを示す。
  論文  参考訳（メタデータ） (2024-10-02T18:09:12Z)
• Logical Distillation of Graph Neural Networks [47.859911892875346]
  グラフを学習するための論理に基づく解釈可能なモデルと,このモデルをグラフニューラルネットワーク(GNN)から抽出するアルゴリズムを提案する。 最近の結果は、GNNの表現性と数量化器を用いた一階述語論理の2変数フラグメント(C2)の関連性を示している。
  論文  参考訳（メタデータ） (2024-06-11T10:18:58Z)
• A Manifold Perspective on the Statistical Generalization of Graph Neural Networks [84.01980526069075]
  我々は、スペクトル領域の多様体からサンプリングされたグラフ上のGNNの統計的一般化理論を確立するために多様体の視点を取る。 我々はGNNの一般化境界が対数スケールのグラフのサイズとともに線形に減少し、フィルタ関数のスペクトル連続定数とともに線形的に増加することを証明した。
  論文  参考訳（メタデータ） (2024-06-07T19:25:02Z)
• 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)
• The Descriptive Complexity of Graph Neural Networks [2.6728900378310514]
  本稿では,GNN の有界深度ファミリーで計算できるグラフクエリが,一階述語論理のガード付き GFO+C フラグメントで定義可能であることを証明した。 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)
• On the approximation capability of GNNs in node classification/regression tasks [4.141514895639094]
  グラフニューラルネットワーク(GNN)は、グラフ処理のための幅広い種類の接続モデルである。 GNNはノード分類/回帰タスクの確率の普遍近似であることを示す。
  論文  参考訳（メタデータ） (2021-06-16T17:46:51Z)
• Bi-GCN: Binary Graph Convolutional Network [57.733849700089955]
  ネットワークパラメータと入力ノードの特徴を二項化するバイナリグラフ畳み込みネットワーク(Bi-GCN)を提案する。 我々のBi-GCNは、ネットワークパラメータと入力データの両方で平均30倍のメモリ消費を削減でき、推論速度を平均47倍に加速できる。
  論文  参考訳（メタデータ） (2020-10-15T07:26:23Z)
• The Surprising Power of Graph Neural Networks with Random Node Initialization [54.4101931234922]
  グラフニューラルネットワーク(GNN)は、関係データ上での表現学習に有効なモデルである。 標準 GNN はその表現力に制限があり、Weisfeiler-Leman グラフ同型(英語版)の能力以外の区別はできない。 本研究では,ランダムノード(RNI)を用いたGNNの表現力の解析を行う。 我々はこれらのモデルが普遍的であることを証明し、GNNが高次特性の計算に頼らない最初の結果である。
  論文  参考訳（メタデータ） (2020-10-02T19:53:05Z)
• Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning [63.97983530843762]
  グラフニューラルネットワーク(GNN)はグラフ表現学習において大きな成功を収めている。 GNNは、実際には非常に異なるグラフ部分構造に対して同一の表現を生成する。 より強力なGNNは、最近高階試験を模倣して提案され、基礎となるグラフ構造を疎結合にできないため、非効率である。 本稿では,グラフ表現学習の新たなクラスとして距離分解(DE)を提案する。
  論文  参考訳（メタデータ） (2020-08-31T23:15:40Z)
• Can Graph Neural Networks Count Substructures? [53.256112515435355]
  グラフニューラルネットワーク(GNN)の能力について,属性付きグラフサブ構造をカウントする能力を用いて検討する。 我々は2種類のサブストラクチャカウントを区別する: インダクションサブグラフカウントとサブグラフカウント、および人気のあるGNNアーキテクチャに対する肯定的および否定的な回答である。
  論文  参考訳（メタデータ） (2020-02-10T18:53:30Z)

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

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