論文の概要: Weisfeiler-Lehman meets Events: An Expressivity Analysis for Continuous-Time Dynamic Graph Neural Networks

• arxiv url: http://arxiv.org/abs/2508.18052v1
• Date: Mon, 25 Aug 2025 14:10:45 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-26 18:43:45.809834
• Title: Weisfeiler-Lehman meets Events: An Expressivity Analysis for Continuous-Time Dynamic Graph Neural Networks
• Title（参考訳）: Weisfeiler-Lehman氏のイベント - 連続時間動的グラフニューラルネットワークの表現性解析
• Authors: Silvia Beddar-Wiesing, Alice Moallemy-Oureh,
• Abstract要約: グラフニューラルネットワーク (GNN) は、1-Weisfeiler-Lehman (1-WL) テストの識別能力と一致することが知られている。 GNNは任意の精度でグラフ上の任意の対象関数を普遍的に近似することができる。 属性付き離散力学グラフの理論を任意の接続性を持つ属性付き連続時間動的グラフに拡張する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Graph Neural Networks (GNNs) are known to match the distinguishing power of the 1-Weisfeiler-Lehman (1-WL) test, and the resulting partitions coincide with the unfolding tree equivalence classes of graphs. Preserving this equivalence, GNNs can universally approximate any target function on graphs in probability up to any precision. However, these results are limited to attributed discrete-dynamic graphs represented as sequences of connected graph snapshots. Real-world systems, such as communication networks, financial transaction networks, and molecular interactions, evolve asynchronously and may split into disconnected components. In this paper, we extend the theory of attributed discrete-dynamic graphs to attributed continuous-time dynamic graphs with arbitrary connectivity. To this end, we introduce a continuous-time dynamic 1-WL test, prove its equivalence to continuous-time dynamic unfolding trees, and identify a class of continuous-time dynamic GNNs (CGNNs) based on discrete-dynamic GNN architectures that retain both distinguishing power and universal approximation guarantees. Our constructive proofs further yield practical design guidelines, emphasizing a compact and expressive CGNN architecture with piece-wise continuously differentiable temporal functions to process asynchronous, disconnected graphs.
• Abstract（参考訳）: グラフニューラルネットワーク (GNN) は 1-Weisfeiler-Lehman (1-WL) テストの差分力と一致することが知られている。 この同値性を保つため、GNNは任意の精度のグラフ上の任意の対象関数を普遍的に近似することができる。 しかし、これらの結果は連結グラフスナップショットのシーケンスとして表される離散力学グラフに限られる。 通信ネットワーク、金融取引ネットワーク、分子間相互作用などの現実世界のシステムは非同期に進化し、切断されたコンポーネントに分割される。 本稿では、属性付き離散力学グラフの理論を任意の接続性を持つ属性付き連続時間動的グラフに拡張する。 この目的のために、連続時間動的1-WLテストを導入し、連続時間動的展開木と等価性を証明し、離散動的GNNアーキテクチャに基づく連続時間動的GNN(CGNN)のクラスを同定する。 我々の構成的証明は、より実用的な設計ガイドラインをもたらし、非同期で非連結なグラフを処理するために、断片的に連続的に微分可能な時間関数を持つコンパクトで表現力のあるCGNNアーキテクチャを強調している。

関連論文リスト

• Dynamic Graph Condensation [40.099854631984556]
  動的グラフにおける時間的拡張は、重要なデータ効率の課題を引き起こす。 実動的グラフをコンパクトなバージョンに凝縮するフレームワークであるDyGCを提案する。 提案手法は, 最大96.2%のDGNN性能を保ち, 元のグラフサイズは0.5%に留まり, 最大1846倍の高速化を実現している。
  論文  参考訳（メタデータ） (2025-06-16T05:11:29Z)
• Dynamic Neural Dowker Network: Approximating Persistent Homology in Dynamic Directed Graphs [11.646514065979323]
  本稿ではDNDN(Dynamic Neural Dowker Network)について紹介する。 我々のアプローチは、実世界のデータセットに関する包括的な実験を通じて検証される。
  論文  参考訳（メタデータ） (2024-08-17T07:13:12Z)
• Dynamic Causal Explanation Based Diffusion-Variational Graph Neural Network for Spatio-temporal Forecasting [60.03169701753824]
  時間予測のための動的拡散型グラフニューラルネットワーク(DVGNN)を提案する。 提案したDVGNNモデルは最先端のアプローチよりも優れ,Root Mean Squared Errorの結果が優れている。
  論文  参考訳（メタデータ） (2023-05-16T11:38:19Z)
• Decoupled Graph Neural Networks for Large Dynamic Graphs [14.635923016087503]
  大規模動的グラフのための疎結合グラフニューラルネットワークを提案する。 このアルゴリズムは,両種類の動的グラフにおいて,最先端の性能を実現する。
  論文  参考訳（メタデータ） (2023-05-14T23:00:10Z)
• Temporal Aggregation and Propagation Graph Neural Networks for Dynamic Representation [67.26422477327179]
  時間グラフは連続時間を通してノード間の動的相互作用を示す。 本研究では,周辺地域全体と時間的グラフ畳み込みの新たな手法を提案する。 提案するTAP-GNNは,予測性能とオンライン推論遅延の両面で,既存の時間グラフ手法よりも優れた性能を示す。
  論文  参考訳（メタデータ） (2023-04-15T08:17:18Z)
• Representation Power of Graph Neural Networks: Improved Expressivity via Algebraic Analysis [124.97061497512804]
  標準グラフニューラルネットワーク (GNN) はWeisfeiler-Lehman (WL) アルゴリズムよりも差別的な表現を生成する。 また、白い入力を持つ単純な畳み込みアーキテクチャは、グラフの閉経路をカウントする同変の特徴を生じさせることを示した。
  論文  参考訳（メタデータ） (2022-05-19T18:40:25Z)
• Discovering the Representation Bottleneck of Graph Neural Networks from Multi-order Interactions [51.597480162777074]
  グラフニューラルネットワーク(GNN)は、ノード機能を伝搬し、インタラクションを構築するためにメッセージパッシングパラダイムに依存している。 最近の研究は、異なるグラフ学習タスクはノード間の異なる範囲の相互作用を必要とすることを指摘している。 科学領域における2つの共通グラフ構築法、すなわち、emphK-nearest neighbor(KNN)グラフとemphfully-connected(FC)グラフについて検討する。
  論文  参考訳（メタデータ） (2022-05-15T11:38:14Z)
• On the approximation capability of GNNs in node classification/regression tasks [4.141514895639094]
  グラフニューラルネットワーク(GNN)は、グラフ処理のための幅広い種類の接続モデルである。 GNNはノード分類/回帰タスクの確率の普遍近似であることを示す。
  論文  参考訳（メタデータ） (2021-06-16T17:46:51Z)
• Pointer Graph Networks [48.44209547013781]
  グラフニューラルネットワーク(GNN)は通常、前もって知られていると仮定される静的グラフに適用される。 Pointer Graph Networks (PGNs) モデル一般化能力を改善するために、追加の推論エッジを備えた拡張セットまたはグラフ。 PGNは各ノードが別のノードを動的に指し、メッセージがこれらのポインタを渡ることを可能にする。
  論文  参考訳（メタデータ） (2020-06-11T12:52:31Z)

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

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