論文の概要: Are Targeted Messages More Effective?

• arxiv url: http://arxiv.org/abs/2403.06817v2
• Date: Sun, 19 May 2024 11:43:18 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-21 23:00:48.536674
• Title: Are Targeted Messages More Effective?
• Title（参考訳）: ターゲットメッセージはより効果的か?
• Authors: Martin Grohe, Eran Rosenbluth,
• Abstract要約: グラフニューラルネットワーク(GNN)は、グラフのためのディープラーニングアーキテクチャである。 GNNの表現性は、カウントを伴う一階述語論理の特定の断片によって特徴づけられる。 2つのGNNバージョンが一様でない場合、同じ表現性を持つことを示す。
• 参考スコア（独自算出の注目度）: 2.2625389420008624
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Graph neural networks (GNN) are deep learning architectures for graphs. Essentially, a GNN is a distributed message passing algorithm, which is controlled by parameters learned from data. It operates on the vertices of a graph: in each iteration, vertices receive a message on each incoming edge, aggregate these messages, and then update their state based on their current state and the aggregated messages. The expressivity of GNNs can be characterised in terms of certain fragments of first-order logic with counting and the Weisfeiler-Lehman algorithm. The core GNN architecture comes in two different versions. In the first version, a message only depends on the state of the source vertex, whereas in the second version it depends on the states of the source and target vertices. In practice, both of these versions are used, but the theory of GNNs so far mostly focused on the first one. On the logical side, the two versions correspond to two fragments of first-order logic with counting that we call modal and guarded. The question whether the two versions differ in their expressivity has been mostly overlooked in the GNN literature and has only been asked recently (Grohe, LICS'23). We answer this question here. It turns out that the answer is not as straightforward as one might expect. By proving that the modal and guarded fragment of first-order logic with counting have the same expressivity over labelled undirected graphs, we show that in a non-uniform setting the two GNN versions have the same expressivity. However, we also prove that in a uniform setting the second version is strictly more expressive.
• Abstract（参考訳）: グラフニューラルネットワーク(GNN)は、グラフのためのディープラーニングアーキテクチャである。 基本的に、GNNは分散メッセージパッシングアルゴリズムであり、データから学習したパラメータによって制御される。 各イテレーションにおいて、頂点はそれぞれのエッジでメッセージを受信し、これらのメッセージを集約し、現在の状態と集約されたメッセージに基づいて状態を更新する。 GNNの表現性は、カウントを伴う一階述語論理の断片とWeisfeiler-Lehmanアルゴリズムによって特徴づけられる。 コアGNNアーキテクチャには、2つの異なるバージョンがある。 最初のバージョンでは、メッセージはソース頂点の状態にのみ依存するが、第2バージョンではソースの状態とターゲット頂点にのみ依存する。 実際には、どちらのバージョンも使われているが、これまでのGNNの理論は、主に最初のバージョンに焦点を当てている。 論理的側面では、2つのバージョンは1階述語論理の2つの断片に対応する。 2つのバージョンが表現性に違いがあるかどうかという問題は、GNNの文献では概ね見過ごされ、最近になって質問されただけである(Grohe, licS'23)。 私たちはここでこの質問に答える。 その結果、答えは予想されるほど単純ではないことが判明した。 数える一階述語論理のモーダルおよびガードされた断片がラベル付けされた無向グラフに対して同じ表現性を持つことを示すことにより、2つのGNNバージョンが同じ表現性を持つことを示す。 しかし、均一な設定では、第2版の方が厳密に表現可能であることも証明する。

関連論文リスト

• Improving the Expressiveness of $K$-hop Message-Passing GNNs by Injecting Contextualized Substructure Information [17.56609419806051]
  K$ホップメッセージパスGNNの表現力を高めるために,テキストサブストラクチャ符号化関数を提案する。 提案手法は,従来の$K$-hopグラフニューラルネットワークや1-WLサブグラフGNNよりも強力である。
  論文  参考訳（メタデータ） (2024-06-27T15:10:56Z)
• Logical Distillation of Graph Neural Networks [47.859911892875346]
  グラフを学習するための論理に基づく解釈可能なモデルと,このモデルをグラフニューラルネットワーク(GNN)から抽出するアルゴリズムを提案する。 最近の結果は、GNNの表現性と数量化器を用いた一階述語論理の2変数フラグメント(C2)の関連性を示している。
  論文  参考訳（メタデータ） (2024-06-11T10:18:58Z)
• The logic of rational graph neural networks [0.7614628596146602]
  我々は,GC2 の深度 3$ のクエリは,合理的なアクティベーション関数を持つ GNN では表現できないことを証明した。 これは、すべての非ポリノミカル活性化関数がGNNの最大表現性を参照しているわけではないことを示している。 また、一階述語論理(RGC2)の有理サブフラグメントを示し、すべてのグラフに対して有理GNNがRGC2クエリを均一に表現できることを証明する。
  論文  参考訳（メタデータ） (2023-10-19T20:32:25Z)
• Understanding and Extending Subgraph GNNs by Rethinking Their Symmetries [33.07812045457703]
  グラフGNNはグラフをサブグラフのコレクションとしてモデル化するグラフニューラルネットワーク(GNN)の最近のクラスである。 ノードベースの部分グラフ選択ポリシーを用いた,最も顕著な部分グラフ法について検討する。 本稿では,従来のノードベースサブグラフGNNを一般化したサブグラフ手法に対して,メッセージパッシングの一般的なファミリを提案する。
  論文  参考訳（メタデータ） (2022-06-22T14:35:47Z)
• Two-Dimensional Weisfeiler-Lehman Graph Neural Networks for Link Prediction [61.01337335214126]
  グラフニューラルネットワーク(GNN)のリンク予測 リンク予測のためのほとんどの既存のGNNは、1次元Weisfeiler-Lehman (1-WL) テストに基づいている。 テキスト2次元Weisfeiler-Lehman (2-WL) テストに基づいて,ノード対(リンク)表現を直接取得可能な,まったく異なるアプローチを提案する。
  論文  参考訳（メタデータ） (2022-06-20T04:50:38Z)
• Twin Weisfeiler-Lehman: High Expressive GNNs for Graph Classification [48.087302573188396]
  本稿では,ノードラベルとノードIDを同時に渡す新しいグラフ同型テスト手法Twin-WLを提案する。 2つのツイン-GNNは、従来のメッセージパッシングGNNよりも表現力が高いことが証明された。
  論文  参考訳（メタデータ） (2022-03-22T12:58:03Z)
• Identity-aware Graph Neural Networks [63.6952975763946]
  グラフニューラルネットワーク(ID-GNN)を1-WLテストよりも表現力の高いメッセージクラスを開発しています。 ID-GNNは、メッセージパッシング中にノードのIDを誘導的に考慮することにより、既存のGNNアーキテクチャを拡張します。 既存のGNNをID-GNNに変換すると、挑戦ノード、エッジ、グラフプロパティ予測タスクの平均40%の精度が向上することを示す。
  論文  参考訳（メタデータ） (2021-01-25T18:59:01Z)
• Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning [63.97983530843762]
  グラフニューラルネットワーク(GNN)はグラフ表現学習において大きな成功を収めている。 GNNは、実際には非常に異なるグラフ部分構造に対して同一の表現を生成する。 より強力なGNNは、最近高階試験を模倣して提案され、基礎となるグラフ構造を疎結合にできないため、非効率である。 本稿では,グラフ表現学習の新たなクラスとして距離分解(DE)を提案する。
  論文  参考訳（メタデータ） (2020-08-31T23:15:40Z)
• Let's Agree to Degree: Comparing Graph Convolutional Networks in the Message-Passing Framework [5.835421173589977]
  我々は、グラフ上に定義されたニューラルネットワークをメッセージパッシングニューラルネットワーク(MPNN)としてキャストした。 匿名MPNNと学位対応MPNNの2種類のMPNNについて検討する。 Wesfeiler-Lehman (WL)アルゴリズムの差分パワーの観点から,MPNNの差分パワーの下位値と上位値を求める。
  論文  参考訳（メタデータ） (2020-04-06T12:14:00Z)
• Generalization and Representational Limits of Graph Neural Networks [46.20253808402385]
  ローカル情報に完全に依存するグラフニューラルネットワーク(GNN)では,いくつかの重要なグラフ特性を計算できないことを示す。 メッセージパッシングGNNに対する最初のデータ依存一般化境界を提供する。 私たちのバウンダリは、既存のVC次元ベースのGNN保証よりもはるかに厳格で、リカレントニューラルネットワークのRademacherバウンダリと同等です。
  論文  参考訳（メタデータ） (2020-02-14T18:10:14Z)

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

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