Fugu-MT 論文翻訳(概要): A Logic for Reasoning About Aggregate-Combine Graph Neural Networks

論文の概要: A Logic for Reasoning About Aggregate-Combine Graph Neural Networks

arxiv url: http://arxiv.org/abs/2405.00205v1
Date: Tue, 30 Apr 2024 21:16:38 GMT
ステータス: 処理完了
システム内更新日: 2024-05-02 17:06:33.128453
Title: A Logic for Reasoning About Aggregate-Combine Graph Neural Networks
Title（参考訳）: 集約型グラフニューラルネットワークの論理
Authors: Pierre Nunn, Marco Sälzer, François Schwarzentruber, Nicolas Troquard,
Abstract要約: 各式が等価グラフニューラルネットワーク(GNN)に変換可能であることを示す。また, 満足度問題はPSPACE完全であることを示す。
参考スコア（独自算出の注目度）: 11.313331046805365
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We propose a modal logic in which counting modalities appear in linear inequalities. We show that each formula can be transformed into an equivalent graph neural network (GNN). We also show that a broad class of GNNs can be transformed efficiently into a formula, thus significantly improving upon the literature about the logical expressiveness of GNNs. We also show that the satisfiability problem is PSPACE-complete. These results bring together the promise of using standard logical methods for reasoning about GNNs and their properties, particularly in applications such as GNN querying, equivalence checking, etc. We prove that such natural problems can be solved in polynomial space.
Abstract（参考訳）: 線形不等式に数える様相が現れる様相論理を提案する。各式は等価グラフニューラルネットワーク(GNN)に変換可能であることを示す。また,GNNの論理的表現性に関する文献により,GNNの幅広いクラスを効率よく公式に変換できることが示唆された。また, 満足度問題はPSPACE完全であることを示す。これらの結果は、特にGNNクエリや等価チェックなどのアプリケーションにおいて、GNNとその特性を推論するために標準的な論理的手法を使用するという約束を結び付ける。このような自然問題は多項式空間で解けることを証明している。

関連論文リスト

Fine-Grained Expressive Power of Weisfeiler-Leman: A Homomorphism Counting Perspective [24.729126775414922]
グラフニューラルネットワークの任意のクラス(GNN)の準同型カウント能力を決定するための理論的枠組みを提供する。検討されている設計空間は、既知の強力なGNNのほとんどすべてに対応するのに十分の大きさであるので、我々の結果は既存のすべての作業を大幅に拡張し、GNNモデル設計の自動化にその応用を見出すことができるかもしれない。
論文参考訳（メタデータ） (2024-10-04T15:36:48Z)
A Manifold Perspective on the Statistical Generalization of Graph Neural Networks [84.01980526069075]
我々は、スペクトル領域の多様体からサンプリングされたグラフ上のGNNの統計的一般化理論を確立するために多様体の視点を取る。我々はGNNの一般化境界が対数スケールのグラフのサイズとともに線形に減少し、フィルタ関数のスペクトル連続定数とともに線形的に増加することを証明した。
論文参考訳（メタデータ） (2024-06-07T19:25:02Z)
A Modal Logic for Explaining some Graph Neural Networks [0.0]
各式が等価グラフニューラルネットワーク(GNN)に変換可能であることを示す。また、満足度問題は決定可能であることも示している。
論文参考訳（メタデータ） (2023-07-11T10:13:25Z)
The Logic of Graph Neural Networks [0.9355115132408681]
グラフニューラルネットワーク(gnns)は、グラフ上の機械学習問題のディープラーニングアーキテクチャである。 GNNの表現力はWeisfeiler-Lemanアルゴリズムと可変カウント論理によって正確に特徴付けられることが示されている。
論文参考訳（メタデータ） (2021-04-29T19:23:26Z)
A Unified View on Graph Neural Networks as Graph Signal Denoising [49.980783124401555]
グラフニューラルネットワーク(GNN)は,グラフ構造化データの学習表現において顕著に普及している。本研究では,代表的GNNモデル群における集約過程を,グラフ記述問題の解法とみなすことができることを数学的に確立する。 UGNNから派生した新しいGNNモデルADA-UGNNをインスタンス化し、ノード間の適応的滑らかさでグラフを処理する。
論文参考訳（メタデータ） (2020-10-05T04:57:18Z)
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)
Expressive Power of Invariant and Equivariant Graph Neural Networks [10.419350129060598]
Folklore Graph Neural Networks (FGNN) は、与えられたテンソル次数に対してこれまで提案されてきた最も表現力のあるアーキテクチャである。 FGNNはこの問題の解決方法を学ぶことができ、既存のアルゴリズムよりも平均的なパフォーマンスが向上する。
論文参考訳（メタデータ） (2020-06-28T16:35:45Z)
Optimization and Generalization Analysis of Transduction through Gradient Boosting and Application to Multi-scale Graph Neural Networks [60.22494363676747]
現在のグラフニューラルネットワーク(GNN)は、オーバースムーシング(over-smoothing)と呼ばれる問題のため、自分自身を深くするのは難しいことが知られている。マルチスケールGNNは、オーバースムーシング問題を緩和するための有望なアプローチである。マルチスケールGNNを含むトランスダクティブ学習アルゴリズムの最適化と一般化を保証する。
論文参考訳（メタデータ） (2020-06-15T17:06:17Z)
Evaluating Logical Generalization in Graph Neural Networks [59.70452462833374]
グラフニューラルネットワーク(GNN)を用いた論理一般化の課題について検討する。ベンチマークスイートであるGraphLogでは、学習アルゴリズムが異なる合成論理でルール誘導を実行する必要がある。モデルが一般化し適応する能力は、トレーニング中に遭遇する論理規則の多様性によって強く決定される。
論文参考訳（メタデータ） (2020-03-14T05:45:55Z)
Efficient Probabilistic Logic Reasoning with Graph Neural Networks [63.099999467118245]
マルコフ論理ネットワーク(MLN)は、多くの知識グラフ問題に対処するために用いられる。 MLNの推論は計算集約的であり、MLNの産業規模での応用は非常に困難である。本稿では,表現力とモデルの単純さとのバランスのよいグラフニューラルネット(GNN)モデルであるExpressGNNを提案する。
論文参考訳（メタデータ） (2020-01-29T23:34:36Z)

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