論文の概要: Provably expressive temporal graph networks

• arxiv url: http://arxiv.org/abs/2209.15059v1
• Date: Thu, 29 Sep 2022 19:06:00 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-03 15:59:04.870865
• Title: Provably expressive temporal graph networks
• Title（参考訳）: 確率表現型時間グラフネットワーク
• Authors: Amauri H. Souza, Diego Mesquita, Samuel Kaski, Vikas Garg
• Abstract要約: 動的相互作用を埋め込むモデルとして時間グラフネットワーク(TGN)が注目されているが,その理論的基盤についてはほとんど分かっていない。 本稿では,時間的歩行(WA-TGN)を集約するTGNと,繰り返しメモリモジュール(MP-TGN)を付加するローカルメッセージパッシング(MP-TGN)という,TGNの2つの主要なカテゴリの表現力と限界に関する基礎的な結果を確立する。 これらの理論的洞察は、注入的時間的メッセージパッシングと相対的な位置特徴を活用する新しいアーキテクチャであるPINTにつながります。
• 参考スコア（独自算出の注目度）: 10.827432480392101
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Temporal graph networks (TGNs) have gained prominence as models for embedding dynamic interactions, but little is known about their theoretical underpinnings. We establish fundamental results about the representational power and limits of the two main categories of TGNs: those that aggregate temporal walks (WA-TGNs), and those that augment local message passing with recurrent memory modules (MP-TGNs). Specifically, novel constructions reveal the inadequacy of MP-TGNs and WA-TGNs, proving that neither category subsumes the other. We extend the 1-WL (Weisfeiler-Leman) test to temporal graphs, and show that the most powerful MP-TGNs should use injective updates, as in this case they become as expressive as the temporal WL. Also, we show that sufficiently deep MP-TGNs cannot benefit from memory, and MP/WA-TGNs fail to compute graph properties such as girth. These theoretical insights lead us to PINT -- a novel architecture that leverages injective temporal message passing and relative positional features. Importantly, PINT is provably more expressive than both MP-TGNs and WA-TGNs. PINT significantly outperforms existing TGNs on several real-world benchmarks.
• Abstract（参考訳）: 時間グラフネットワーク(TGN)は動的相互作用を埋め込むモデルとして注目されているが、その理論的基盤についてはほとんど知られていない。 本稿では、時間的歩行(WA-TGN)を集約するTGNと、繰り返しメモリモジュール(MP-TGN)を付加するローカルメッセージパッシング(MP-TGN)の2つの主要なカテゴリの表現力と限界に関する基礎的な結果を確立する。 具体的には、新しい構造はMP-TGNsとWA-TGNsの不適切さを明らかにし、どちらのカテゴリーも他方を仮定しないことを証明している。 我々は1-WL(Weisfeiler-Leman)テストを時間グラフに拡張し、最も強力なMP-TGNが時間WLと同じくらいの表現力を持つことを示す。 また,十分な深度MP-TGNはメモリの恩恵を受けられず,MP/WA-TGNはガースなどのグラフ特性を計算できないことを示す。 これらの理論的洞察は、注入的時間的メッセージパッシングと相対的な位置特徴を活用する新しいアーキテクチャであるPINTにつながります。 重要なことに、PINTはMP-TGNsとWA-TGNsよりも明らかに表現力が高い。 PINTは、いくつかの実世界のベンチマークで既存のTGNを著しく上回っている。

関連論文リスト

• Enhancing the Expressivity of Temporal Graph Networks through Source-Target Identification [2.06242362470764]
  我々は、TGNの定式化は、メッセージ上での予測や移動平均を表現できないことを示した。 本稿では,各インタラクションイベントメッセージにソースターゲット識別を追加することで,TGNの表現性を高めることを提案する。 提案手法であるTGNv2は,時間グラフベンチマーク(TGB)の動的ノード親和性予測データセットにおいて,TGNと現在のTGモデルを著しく上回っている。
  論文  参考訳（メタデータ） (2024-11-06T01:20:24Z)
• Temporal Graph Rewiring with Expander Graphs [3.468621550644668]
  本稿では、時間グラフ上でのグラフリウィリングの最初のアプローチである時間グラフリウィリング(TGR)を提案する。 TGRは、連続時間動的グラフにおいて、時間的に離れたノード間のメッセージパッシングハイウェイを構築する。 tgbl-reviewでは、TGRはベースTGNモデルよりも50.5%改善され、ベースTNCNモデルより22.2%改善されている。
  論文  参考訳（メタデータ） (2024-06-04T14:39:51Z)
• A Teacher-Free Graph Knowledge Distillation Framework with Dual Self-Distillation [58.813991312803246]
  本稿では,教師モデルやGNNを必要としない教師自由グラフ自己蒸留(TGS)フレームワークを提案する。 TGSは、トレーニングにおけるグラフトポロジの認識の利点を享受しているが、推論におけるデータ依存から解放されている。
  論文  参考訳（メタデータ） (2024-03-06T05:52:13Z)
• Graph Neural Networks are Inherently Good Generalizers: Insights by Bridging GNNs and MLPs [71.93227401463199]
  本稿では、P(ropagational)MLPと呼ばれる中間モデルクラスを導入することにより、GNNの性能向上を本質的な能力に向ける。 PMLPは、トレーニングにおいてはるかに効率的でありながら、GNNと同等(あるいはそれ以上)に動作することを観察する。
  論文  参考訳（メタデータ） (2022-12-18T08:17:32Z)
• Space-Time Graph Neural Networks with Stochastic Graph Perturbations [100.31591011966603]
  時空間グラフニューラルネットワーク(ST-GNN)は、時間変動データの効率的なグラフ表現を学習する。 本稿では,ST-GNNの特性を再検討し,安定なグラフ安定性を示す。 解析の結果,ST-GNNは時間変化グラフ上での移動学習に適していることが示唆された。
  論文  参考訳（メタデータ） (2022-10-28T16:59:51Z)
• Evidential Temporal-aware Graph-based Social Event Detection via Dempster-Shafer Theory [76.4580340399321]
  ETGNN(Evidential Temporal-aware Graph Neural Network)を提案する。 ノードがテキストであり、エッジがそれぞれ複数の共有要素によって決定されるビュー固有グラフを構築する。 ビュー固有の不確実性を考慮すると、すべてのビューの表現は、明らかなディープラーニング(EDL)ニューラルネットワークを介してマス関数に変換される。
  論文  参考訳（メタデータ） (2022-05-24T16:22:40Z)
• From Stars to Subgraphs: Uplifting Any GNN with Local Structure Awareness [23.279464786779787]
  私たちはMPNNをより表現力のあるものにするための一般的なフレームワークを導入します。 私たちのフレームワークは1&2-WLよりも強力で、3WLよりも強力です。 本手法は,いくつかのよく知られたグラフMLタスクに対して,新たな最先端性能を大きなマージンで設定する。
  論文  参考訳（メタデータ） (2021-10-07T19:08:08Z)
• Hierarchical graph neural nets can capture long-range interactions [8.067880298298185]
  与えられたグラフの多重解像度表現を利用する階層的メッセージパッシングモデルについて検討する。 これにより、ローカル情報を失うことなく、大きな受容領域にまたがる特徴の学習が容易になる。 階層グラフネット(HGNet)を導入し、任意の2つの接続ノードに対して、最大対数長のメッセージパスパスが存在することを保証します。
  論文  参考訳（メタデータ） (2021-07-15T16:24:22Z)
• T-GAP: Learning to Walk across Time for Temporal Knowledge Graph Completion [13.209193437124881]
  時間的知識グラフ(TKG)は、静的知識グラフとは対照的に、本質的に現実世界の知識の過渡的な性質を反映している。 エンコーダとデコーダにおける時間情報とグラフ構造の両方を最大限に活用するTKG補完の新しいモデルであるT-GAPを提案する。 本実験は、T-GAPが最先端のベースラインに対する優れた性能を達成し、目に見えないタイムスタンプによるクエリに有能に一般化することを示す。
  論文  参考訳（メタデータ） (2020-12-19T04:45:32Z)
• Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting [63.04999833264299]
  グラフサブストラクチャネットワーク(GSN)は,サブストラクチャエンコーディングに基づくトポロジ的に認識可能なメッセージパッシング方式である。 Wesfeiler-Leman (WL) グラフ同型テストよりも厳密に表現可能であることを示す。 グラフ分類と回帰タスクについて広範囲に評価を行い、様々な実世界の環境において最先端の結果を得る。
  論文  参考訳（メタデータ） (2020-06-16T15:30:31Z)
• Pointer Graph Networks [48.44209547013781]
  グラフニューラルネットワーク(GNN)は通常、前もって知られていると仮定される静的グラフに適用される。 Pointer Graph Networks (PGNs) モデル一般化能力を改善するために、追加の推論エッジを備えた拡張セットまたはグラフ。 PGNは各ノードが別のノードを動的に指し、メッセージがこれらのポインタを渡ることを可能にする。
  論文  参考訳（メタデータ） (2020-06-11T12:52:31Z)

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

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