論文の概要: Calibrate and Boost Logical Expressiveness of GNN Over Multi-Relational
and Temporal Graphs
- arxiv url: http://arxiv.org/abs/2311.01647v1
- Date: Fri, 3 Nov 2023 00:33:24 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-06 15:36:36.157001
- Title: Calibrate and Boost Logical Expressiveness of GNN Over Multi-Relational
and Temporal Graphs
- Title(参考訳): マルチリレーショナルグラフとテンポラルグラフによるGNNの論理表現性向上
- Authors: Yeyuan Chen and Dingmin Wang
- Abstract要約: 2つの変数と数量化器を持つ一階述語論理の断片である$mathcalFOC$NNについて検討する。
本稿では,線形時間で実行可能な,前処理ステップに似た単純なグラフ変換手法を提案する。
我々の結果は,グラフ変換によるR$2$-GNNが,合成および実世界のデータセットのベースライン手法よりも優れていることを一貫して示している。
- 参考スコア(独自算出の注目度): 8.095679736030146
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: As a powerful framework for graph representation learning, Graph Neural
Networks (GNNs) have garnered significant attention in recent years. However,
to the best of our knowledge, there has been no formal analysis of the logical
expressiveness of GNNs as Boolean node classifiers over multi-relational
graphs, where each edge carries a specific relation type. In this paper, we
investigate $\mathcal{FOC}_2$, a fragment of first-order logic with two
variables and counting quantifiers. On the negative side, we demonstrate that
the R$^2$-GNN architecture, which extends the local message passing GNN by
incorporating global readout, fails to capture $\mathcal{FOC}_2$ classifiers in
the general case. Nevertheless, on the positive side, we establish that
R$^2$-GNNs models are equivalent to $\mathcal{FOC}_2$ classifiers under certain
restricted yet reasonable scenarios. To address the limitations of R$^2$-GNNs
regarding expressiveness, we propose a simple graph transformation technique,
akin to a preprocessing step, which can be executed in linear time. This
transformation enables R$^2$-GNNs to effectively capture any $\mathcal{FOC}_2$
classifiers when applied to the "transformed" input graph. Moreover, we extend
our analysis of expressiveness and graph transformation to temporal graphs,
exploring several temporal GNN architectures and providing an expressiveness
hierarchy for them. To validate our findings, we implement R$^2$-GNNs and the
graph transformation technique and conduct empirical tests in node
classification tasks against various well-known GNN architectures that support
multi-relational or temporal graphs. Our experimental results consistently
demonstrate that R$^2$-GNN with the graph transformation outperforms the
baseline methods on both synthetic and real-world datasets
- Abstract(参考訳): グラフ表現学習の強力なフレームワークとして、グラフニューラルネットワーク(GNN)は近年大きな注目を集めている。
しかしながら、我々の知る限り、GNNの論理的表現性について、各エッジが特定の関係型を持つ多重関係グラフ上のブールノード分類器としての公式な分析は行われていない。
本稿では,二つの変数を持つ一階述語論理のフラグメントである$\mathcal{FOC}_2$について検討する。
負の面では、グローバルリードアウトを組み込んだローカルメッセージパッシングGNNを拡張したR$^2$-GNNアーキテクチャが、一般的なケースでは$\mathcal{FOC}_2$分類器を捕捉できないことを示す。
それにもかかわらず、正の面において、R$^2$-GNNs モデルは、一定の制限のある妥当なシナリオの下で $\mathcal{FOC}_2$ 分類器と等価であることを示す。
表現性に関するR$^2$-GNNの制限に対処するため、線形時間で実行できる前処理ステップに似た単純なグラフ変換手法を提案する。
この変換により、R$^2$-GNNは"変換"入力グラフに適用された任意の$\mathcal{FOC}_2$分類器を効果的にキャプチャできる。
さらに、表現性およびグラフ変換の分析を時間グラフに拡張し、複数の時間的GNNアーキテクチャを探索し、表現性階層を提供する。
本稿では,R$^2$-GNNとグラフ変換手法を実装し,マルチリレーショナルグラフや時間グラフをサポートするよく知られたGNNアーキテクチャに対して,ノード分類タスクにおける経験的テストを行う。
グラフ変換を用いたr$^2$-gnnが合成データと実世界データの両方のベースラインメソッドを上回ることを一貫して実証した。
関連論文リスト
- Spatio-Spectral Graph Neural Networks [50.277959544420455]
比スペクトルグラフネットワーク(S$2$GNN)を提案する。
S$2$GNNは空間的およびスペクトル的にパラメータ化されたグラフフィルタを組み合わせる。
S$2$GNNsは、MPGNNsよりも厳密な近似理論誤差境界を生じる。
論文 参考訳(メタデータ) (2024-05-29T14:28:08Z) - Learning to Reweight for Graph Neural Network [63.978102332612906]
グラフニューラルネットワーク(GNN)は、グラフタスクに対して有望な結果を示す。
既存のGNNの一般化能力は、テストとトレーニンググラフデータの間に分散シフトが存在する場合に低下する。
本稿では,分布外一般化能力を大幅に向上させる非線形グラフデコリレーション法を提案する。
論文 参考訳(メタデータ) (2023-12-19T12:25:10Z) - $p$-Laplacian Based Graph Neural Networks [27.747195341003263]
グラフネットワーク(GNN)は、グラフ上の半教師付きノード分類において優れた性能を示す。
我々は、離散正規化フレームワークからメッセージパッシング機構を導出する$p$GNNと呼ばれる新しい$p$LaplacianベースのGNNモデルを提案する。
新たなメッセージパッシング機構は低域通過フィルタと高域通過フィルタを同時に動作させることで,ホモ親和性グラフとヘテロ親和性グラフの両方に対して$p$GNNを有効にすることができることを示す。
論文 参考訳(メタデータ) (2021-11-14T13:16:28Z) - 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) - Graph Neural Networks with Local Graph Parameters [1.8600631687568656]
ローカルグラフパラメータは、任意のグラフニューラルネットワーク(GNN)アーキテクチャに追加することができる。
我々の結果は、有限モデル理論と有限変数論理の深い結果とGNNを結びつける。
論文 参考訳(メタデータ) (2021-06-12T07:43:51Z) - Rethinking Graph Regularization for Graph Neural Networks [21.32758655943999]
グラフラプラシア正規化は既存のグラフニューラルネットワーク(GNN)にほとんど恩恵を与えないことを示す。
我々は、伝播正則化(P-reg)と呼ばれるグラフラプラシア正則化の単純だが非自明な変種を提案する。
我々はP-regがノードレベルのタスクとグラフレベルのタスクの両方において既存のGNNモデルの性能を効果的に向上できることを実証した。
論文 参考訳(メタデータ) (2020-09-04T07:04:51Z) - 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) - GPT-GNN: Generative Pre-Training of Graph Neural Networks [93.35945182085948]
グラフニューラルネットワーク(GNN)は、グラフ構造化データのモデリングにおいて強力であることが示されている。
生成事前学習によりGNNを初期化するためのGPT-GNNフレームワークを提案する。
GPT-GNNは、様々な下流タスクにおいて、事前トレーニングを最大9.1%行うことなく、最先端のGNNモデルを大幅に上回ることを示す。
論文 参考訳(メタデータ) (2020-06-27T20:12:33Z) - Gated Graph Recurrent Neural Networks [176.3960927323358]
グラフ処理の一般的な学習フレームワークとしてグラフリカレントニューラルネットワーク(GRNN)を導入する。
勾配の消失問題に対処するため,時間,ノード,エッジゲートの3つの異なるゲーティング機構でGRNNを前進させた。
数値的な結果は、GRNNがGNNやRNNよりも優れており、グラフプロセスの時間構造とグラフ構造の両方を考慮することが重要であることを示している。
論文 参考訳(メタデータ) (2020-02-03T22:35:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。