論文の概要: Logical Characterizations of Recurrent Graph Neural Networks with Reals and Floats

• arxiv url: http://arxiv.org/abs/2405.14606v2
• Date: Fri, 12 Jul 2024 13:34:58 GMT
• ステータス: 処理完了
• システム内更新日: 2024-07-16 04:37:57.312787
• Title: Logical Characterizations of Recurrent Graph Neural Networks with Reals and Floats
• Title（参考訳）: リカレントグラフニューラルネットワークのリアルとフロートによる論理的特性評価
• Authors: Veeti Ahvonen, Damian Heiman, Antti Kuusisto, Carsten Lutz,
• Abstract要約: 本稿では,2つのシナリオにおいて,繰り返しグラフニューラルネットワーク(GNN)の正確な論理的特徴について述べる。 フロートに対して、繰り返しGNNと一致する形式主義は数えられるルールベースのモーダル論理であり、実数に対しては適切な無限のモーダル論理を用いる。 キャラクタリゼーションを適用することで、モナディック二階述語論理で定義可能なグラフ特性と比較して、無限論理と規則論理は等しく表現力があることが証明できる。
• 参考スコア（独自算出の注目度）: 6.176021290715425
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In pioneering work from 2019, Barcel\'o and coauthors identified logics that precisely match the expressive power of constant iteration-depth graph neural networks (GNNs) relative to properties definable in first-order logic. In this article, we give exact logical characterizations of recurrent GNNs in two scenarios: (1) in the setting with floating-point numbers and (2) with reals. For floats, the formalism matching recurrent GNNs is a rule-based modal logic with counting, while for reals we use a suitable infinitary modal logic, also with counting. These results give exact matches between logics and GNNs in the recurrent setting without relativising to a background logic in either case, but using some natural assumptions about floating-point arithmetic. Applying our characterizations, we also prove that, relative to graph properties definable in monadic second-order logic (MSO), our infinitary and rule-based logics are equally expressive. This implies that recurrent GNNs with reals and floats have the same expressive power over MSO-definable properties and shows that, for such properties, also recurrent GNNs with reals are characterized by a (finitary!) rule-based modal logic. In the general case, in contrast, the expressive power with floats is weaker than with reals. In addition to logic-oriented results, we also characterize recurrent GNNs, with both reals and floats, via distributed automata, drawing links to distributed computing models.
• Abstract（参考訳）: 2019年の先駆的な研究の中で、Barcel\'o氏と共著者は、一階述語論理で定義可能な特性に対して、定数反復深度グラフニューラルネットワーク(GNN)の表現力に正確に一致するロジックを特定した。 本稿では,(1)浮動小数点数の設定と(2)実数の設定の2つのシナリオにおいて,繰り返しGNNの正確な論理的特徴を与える。 フロートに対して、繰り返しGNNと一致する形式主義は数えられる規則に基づくモーダル論理であり、実数に対しては数えるにも適切な無限のモーダル論理を用いる。 これらの結果は、どちらの場合もバックグラウンド論理に関連付けることなく、繰り返し設定における論理とGNNの正確な一致を与えるが、浮動小数点演算に関する自然な仮定を用いる。 キャラクタリゼーションを適用することで、モナディック二階述語論理(MSO)で定義可能なグラフ特性と比較して、無限論理と規則論理は等しく表現力があることも証明できる。 これは、実数とフロートを持つリカレントGNNが、MSO定義可能な性質に対して同じ表現力を持つことを意味し、そのような性質に対して、実数を持つリカレントGNNも(最終!)ルールに基づくモーダル論理によって特徴づけられることを示している。 一般的には、フロートによる表現力は実数よりも弱い。 論理指向の結果に加えて、分散オートマトンを用いて、実数とフロートの両方を持つ繰り返しGNNを特徴付け、分散コンピューティングモデルへのリンクを描画する。

関連論文リスト

• Logical Distillation of Graph Neural Networks [47.859911892875346]
  グラフを学習するための論理に基づく解釈可能なモデルと,このモデルをグラフニューラルネットワーク(GNN)から抽出するアルゴリズムを提案する。 最近の結果は、GNNの表現性と数量化器を用いた一階述語論理の2変数フラグメント(C2)の関連性を示している。
  論文  参考訳（メタデータ） (2024-06-11T10:18:58Z)
• A Logic for Reasoning About Aggregate-Combine Graph Neural Networks [11.313331046805365]
  各式が等価グラフニューラルネットワーク(GNN)に変換可能であることを示す。 また, 満足度問題はPSPACE完全であることを示す。
  論文  参考訳（メタデータ） (2024-04-30T21:16:38Z)
• The Descriptive Complexity of Graph Neural Networks [2.6728900378310514]
  グラフクエリは、GNNの有界深度ファミリーのクラスによって計算可能であることを示す。 注目すべきは、GNNファミリーは任意のリアルウェイトと幅広い種類のアクティベーション関数を使用することができることである。 GFO+Cでは1つのGNNで1つの線形アクティベーションと有理重みを持つクエリが組込み関係なく定義可能であることを示す。
  論文  参考訳（メタデータ） (2023-03-08T14:32:59Z)
• Discourse-Aware Graph Networks for Textual Logical Reasoning [142.0097357999134]
  パッセージレベルの論理関係は命題単位間の係り合いまたは矛盾を表す(例、結論文) 論理的推論QAを解くための論理構造制約モデリングを提案し、談話対応グラフネットワーク(DAGN)を導入する。 ネットワークはまず、インラインの談話接続とジェネリック論理理論を利用した論理グラフを構築し、その後、エッジ推論機構を用いて論理関係を進化させ、グラフ機能を更新することで論理表現を学習する。
  論文  参考訳（メタデータ） (2022-07-04T14:38:49Z)
• Neuro-Symbolic Inductive Logic Programming with Logical Neural Networks [65.23508422635862]
  我々は最近提案された論理ニューラルネットワーク(LNN)を用いた学習規則を提案する。 他のものと比較して、LNNは古典的なブール論理と強く結びついている。 標準ベンチマークタスクの実験では、LNNルールが極めて解釈可能であることを確認した。
  論文  参考訳（メタデータ） (2021-12-06T19:38:30Z)
• Logic-Driven Context Extension and Data Augmentation for Logical Reasoning of Text [65.24325614642223]
  論理的な記号や表現をテキストで理解し、答えにたどり着くよう提案します。 このような論理的情報に基づいて,文脈拡張フレームワークとデータ拡張アルゴリズムを提案する。 本手法は最先端の性能を実現し,論理駆動コンテキスト拡張フレームワークとデータ拡張アルゴリズムの両方が精度向上に寄与する。
  論文  参考訳（メタデータ） (2021-05-08T10:09:36Z)
• Uncertain Linear Logic via Fibring of Probabilistic and Fuzzy Logic [0.0]
  確率論理とファジィ論理は 2つの異なる仮定に対応します 証拠ベースが現在利用できない命題の組み合わせについて この2つの式は、線形論理における乗法および加法的作用素集合の自然な基底を与える。 資源の論理としての線形論理の概念」は、証拠の保存の原理を通じてここで証明される。
  論文  参考訳（メタデータ） (2020-09-28T00:19:42Z)
• Logical Neural Networks [51.46602187496816]
  ニューラルネットワーク(学習)と記号論理(知識と推論)の両方の重要な特性をシームレスに提供する新しいフレームワークを提案する。 すべてのニューロンは、重み付けされた実数値論理における公式の構成要素としての意味を持ち、非常に解釈不能な非絡み合い表現をもたらす。 推論は事前に定義されたターゲット変数ではなく、オムニであり、論理的推論に対応する。
  論文  参考訳（メタデータ） (2020-06-23T16:55:45Z)
• Evaluating Logical Generalization in Graph Neural Networks [59.70452462833374]
  グラフニューラルネットワーク(GNN)を用いた論理一般化の課題について検討する。 ベンチマークスイートであるGraphLogでは、学習アルゴリズムが異なる合成論理でルール誘導を実行する必要がある。 モデルが一般化し適応する能力は、トレーニング中に遭遇する論理規則の多様性によって強く決定される。
  論文  参考訳（メタデータ） (2020-03-14T05:45:55Z)

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

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