論文の概要: On the Correspondence Between Monotonic Max-Sum GNNs and Datalog
- arxiv url: http://arxiv.org/abs/2305.18015v2
- Date: Wed, 7 Jun 2023 15:06:33 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-08 18:15:37.381027
- Title: On the Correspondence Between Monotonic Max-Sum GNNs and Datalog
- Title（参考訳）: 単調なMax-Sum GNNとデータログの対応について
- Authors: David Tena Cucala, Bernardo Cuenca Grau, Boris Motik, Egor V. Kostylev
- Abstract要約: グラフニューラルネットワーク(GNN)に基づくデータ変換の研究
最大および総和集約関数を持つGNNのサブクラスをカバーするモノトニックマックスサムGNNの表現性について検討する。
- 参考スコア（独自算出の注目度）: 19.288835943223816
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Although there has been significant interest in applying machine learning
techniques to structured data, the expressivity (i.e., a description of what
can be learned) of such techniques is still poorly understood. In this paper,
we study data transformations based on graph neural networks (GNNs). First, we
note that the choice of how a dataset is encoded into a numeric form
processable by a GNN can obscure the characterisation of a model's
expressivity, and we argue that a canonical encoding provides an appropriate
basis. Second, we study the expressivity of monotonic max-sum GNNs, which cover
a subclass of GNNs with max and sum aggregation functions. We show that, for
each such GNN, one can compute a Datalog program such that applying the GNN to
any dataset produces the same facts as a single round of application of the
program's rules to the dataset. Monotonic max-sum GNNs can sum an unbounded
number of feature vectors which can result in arbitrarily large feature values,
whereas rule application requires only a bounded number of constants. Hence,
our result shows that the unbounded summation of monotonic max-sum GNNs does
not increase their expressive power. Third, we sharpen our result to the
subclass of monotonic max GNNs, which use only the max aggregation function,
and identify a corresponding class of Datalog programs.
- Abstract（参考訳）: 構造化データに機械学習技術を適用することには大きな関心があるが、これらの技術の表現力(つまり、何を学ぶことができるかの記述)はまだよく分かっていない。
本稿では,グラフニューラルネットワーク(GNN)に基づくデータ変換について検討する。
まず、GNNが処理可能な数値形式にデータセットをエンコードする方法の選択は、モデルの表現性の特徴を曖昧にし、正準符号化が適切な基盤となることを論じる。
第2に,最大および総集合関数を持つGNNのサブクラスをカバーする単調最大GNNの表現性について検討する。
各GNNに対して、任意のデータセットにGNNを適用することで、プログラムのルールをデータセットに単一ラウンドで適用するのと同じ事実を生成するように、Datalogプログラムを計算できることが示される。
モノトニックなmax-sum gnnは、任意に大きな特徴値をもたらすような、無限個の特徴ベクトルをまとめることができるが、ルールアプリケーションでは、定数の有界数のみを必要とする。
その結果,単調max-sum gnnの非有界和は表現力を高めないことがわかった。
第3に、最大集約関数のみを使用するモノトニックマックスGNNのサブクラスに結果をシャープし、対応するDatalogプログラムのクラスを特定する。
関連論文リスト
- Contextualized Messages Boost Graph Representations [1.5178009359320295]
本稿では,グラフネットワーク(GNN)がグラフとして表現される可能性のあるデータを処理する能力について検討する。
これは、すべてのレベルの能力について調査されているGNNはごくわずかであることを示している。
SIRGCNと広く使われているGNNの関係を数学的に議論し、コントリビューションを文脈に組み込む。
論文 参考訳（メタデータ） (2024-03-19T08:05:49Z) - MAG-GNN: Reinforcement Learning Boosted Graph Neural Network [68.60884768323739]
特定の研究の行は、GNNの表現性を向上させるためにサブグラフ情報を使用するサブグラフGNNを提案し、大きな成功を収めた。
このような効果は、すべての可能な部分グラフを列挙することによって、GNNの効率を犠牲にする。
本稿では,強化学習(RL)により強化されたGNNである磁気グラフニューラルネットワーク(MAG-GNN)を提案する。
論文 参考訳（メタデータ） (2023-10-29T20:32:21Z) - Some Might Say All You Need Is Sum [2.226803104060345]
グラフニューラルネットワーク(GNN)の表現性は、採用する集約関数に依存する。
我々は,Mean や Max GNN によって正確に計算できる基本関数が任意の Sum GNN によって近似できないことを証明した。
論文 参考訳（メタデータ） (2023-02-22T19:01:52Z) - MGNN: Graph Neural Networks Inspired by Distance Geometry Problem [28.789684784093048]
グラフニューラルネットワーク(GNN)は、機械学習分野における顕著な研究トピックとして現れている。
本稿では,GNNの分類段階における分類器の親近性に着想を得たGNNモデルを提案する。
合成および実世界の両方のデータセットを用いて実験を行い,本モデルの有効性を広範囲に評価した。
論文 参考訳（メタデータ） (2022-01-31T04:15:42Z) - VQ-GNN: A Universal Framework to Scale up Graph Neural Networks using
Vector Quantization [70.8567058758375]
VQ-GNNは、Vector Quantization(VQ)を使用して、パフォーマンスを損なうことなく、畳み込みベースのGNNをスケールアップするための普遍的なフレームワークである。
我々のフレームワークは,グラフ畳み込み行列の低ランク版と組み合わせた量子化表現を用いて,GNNの「隣の爆発」問題を回避する。
論文 参考訳（メタデータ） (2021-10-27T11:48:50Z) - On the approximation capability of GNNs in node
classification/regression tasks [4.141514895639094]
グラフニューラルネットワーク(GNN)は、グラフ処理のための幅広い種類の接続モデルである。
GNNはノード分類/回帰タスクの確率の普遍近似であることを示す。
論文 参考訳（メタデータ） (2021-06-16T17:46:51Z) - 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) - Distance Encoding: Design Provably More Powerful Neural Networks for
Graph Representation Learning [63.97983530843762]
グラフニューラルネットワーク(GNN)はグラフ表現学習において大きな成功を収めている。
GNNは、実際には非常に異なるグラフ部分構造に対して同一の表現を生成する。
より強力なGNNは、最近高階試験を模倣して提案され、基礎となるグラフ構造を疎結合にできないため、非効率である。
本稿では,グラフ表現学習の新たなクラスとして距離分解(DE)を提案する。
論文 参考訳（メタデータ） (2020-08-31T23:15:40Z) - Expressive Power of Invariant and Equivariant Graph Neural Networks [10.419350129060598]
Folklore Graph Neural Networks (FGNN) は、与えられたテンソル次数に対してこれまで提案されてきた最も表現力のあるアーキテクチャである。
FGNNはこの問題の解決方法を学ぶことができ、既存のアルゴリズムよりも平均的なパフォーマンスが向上する。
論文 参考訳（メタデータ） (2020-06-28T16:35:45Z) - Eigen-GNN: A Graph Structure Preserving Plug-in for GNNs [95.63153473559865]
グラフニューラルネットワーク(GNN)は、グラフ上の新たな機械学習モデルである。
既存のGNNモデルの多くは浅く、本質的に機能中心である。
我々は,既存の浅いGNNがグラフ構造をよく保存できないことを経験的かつ解析的に示す。
本稿では,グラフ構造保存におけるGNNの能力を高めるプラグインモジュールであるEigen-GNNを提案する。
論文 参考訳（メタデータ） (2020-06-08T02:47:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。