論文の概要: 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クエリを均一に表現できることを証明する。

関連論文リスト

• 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)

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

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