論文の概要: The Logical Expressiveness of Temporal GNNs via Two-Dimensional Product Logics

• arxiv url: http://arxiv.org/abs/2505.11930v1
• Date: Sat, 17 May 2025 09:34:57 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-20 14:57:10.94594
• Title: The Logical Expressiveness of Temporal GNNs via Two-Dimensional Product Logics
• Title（参考訳）: 二次元積論理による時空間GNNの論理表現性
• Authors: Marco Sälzer, Przemysław Andrzej Wałęga, Martin Lange,
• Abstract要約: 時間的GNNの論理的特徴付けを二次元積論理に結合して検討する。 時間的GNNの表現力は,グラフと時間的成分の組み合わせによって異なることを示す。
• 参考スコア（独自算出の注目度）: 4.096453902709292
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In recent years, the expressive power of various neural architectures -- including graph neural networks (GNNs), transformers, and recurrent neural networks -- has been characterised using tools from logic and formal language theory. As the capabilities of basic architectures are becoming well understood, increasing attention is turning to models that combine multiple architectural paradigms. Among them particularly important, and challenging to analyse, are temporal extensions of GNNs, which integrate both spatial (graph-structure) and temporal (evolution over time) dimensions. In this paper, we initiate the study of logical characterisation of temporal GNNs by connecting them to two-dimensional product logics. We show that the expressive power of temporal GNNs depends on how graph and temporal components are combined. In particular, temporal GNNs that apply static GNNs recursively over time can capture all properties definable in the product logic of (past) propositional temporal logic PTL and the modal logic K. In contrast, architectures such as graph-and-time TGNNs and global TGNNs can only express restricted fragments of this logic, where the interaction between temporal and spatial operators is syntactically constrained. These results yield the first logical characterisations of temporal GNNs and establish new relative expressiveness results for temporal GNNs.
• Abstract（参考訳）: 近年、グラフニューラルネットワーク(GNN)、トランスフォーマー、リカレントニューラルネットワークなど、さまざまなニューラルネットワークの表現力は、論理と形式言語理論のツールを使用して特徴づけられている。 基本的なアーキテクチャの能力がよく理解されつつあるため、複数のアーキテクチャパラダイムを組み合わせたモデルに注目が向けられている。 特に重要で分析が難しいのは、空間的(グラフ構造)次元と時間的(時間による進化)次元を統合したGNNの時間拡張である。 本稿では,時間的GNNを2次元積論理に結合することで,時間的GNNの論理的特徴付けに関する研究を開始する。 時間的GNNの表現力は,グラフと時間的成分の組み合わせによって異なることを示す。 対照的に、グラフ・アンド・タイムのTGNNやグローバルのTGNNのようなアーキテクチャは、時間的演算子と空間的演算子の相互作用が構文的に制約されるような、この論理の制限された断片しか表現できない。 これらの結果から, 時間的GNNの論理的特徴付けを行い, 時間的GNNの相対的表現性を新たに確立した。

関連論文リスト

• On the Computational Capability of Graph Neural Networks: A Circuit Complexity Bound Perspective [28.497567290882355]
  グラフニューラルネットワーク(GNN)は、リレーショナルデータに対する学習と推論の標準的なアプローチとなっている。 本稿では,回路複雑性のレンズによるGNNの計算限界について検討する。 具体的には、共通GNNアーキテクチャの回路複雑性を分析し、定数層、線形またはサブ線形埋め込みサイズ、精度の制約の下で、GNNはグラフ接続やグラフ同型といった重要な問題を解くことができないことを証明している。
  論文  参考訳（メタデータ） (2025-01-11T05:54:10Z)
• DTFormer: A Transformer-Based Method for Discrete-Time Dynamic Graph Representation Learning [38.53424185696828]
  離散時間動的グラフ(DTDG)の表現学習は、時間的に変化するエンティティとその進化する接続のダイナミクスをモデル化するために広く応用されている。 本稿では,従来の GNN+RNN フレームワークから Transformer ベースのアーキテクチャへ移行した DTDG のための表現学習手法 DTFormer を提案する。
  論文  参考訳（メタデータ） (2024-07-26T05:46:23Z)
• Temporal Spiking Neural Networks with Synaptic Delay for Graph Reasoning [91.29876772547348]
  スパイキングニューラルネットワーク(SNN)は、生物学的にインスパイアされたニューラルネットワークモデルとして研究されている。 本稿では,SNNがシナプス遅延と時間符号化とを併用すると,グラフ推論の実行(知識)に長けていることを明らかにする。
  論文  参考訳（メタデータ） (2024-05-27T05:53:30Z)
• Logical Characterizations of Recurrent Graph Neural Networks with Reals and Floats [6.176021290715425]
  本稿では,2つのシナリオにおいて,繰り返しグラフニューラルネットワーク(GNN)の正確な論理的特徴について述べる。 フロートに対して、繰り返しGNNと一致する形式主義は数えられるルールベースのモーダル論理であり、実数に対しては適切な無限のモーダル論理を用いる。 キャラクタリゼーションを適用することで、モナディック二階述語論理で定義可能なグラフ特性と比較して、無限論理と規則論理は等しく表現力があることが証明できる。
  論文  参考訳（メタデータ） (2024-05-23T14:19:21Z)
• Contextualizing MLP-Mixers Spatiotemporally for Urban Data Forecast at Scale [54.15522908057831]
  本稿では,STTD予測を大規模に行うためのコンピュータ・ミクサーの適応版を提案する。 我々の結果は、この単純な効率の良いソリューションが、いくつかのトラフィックベンチマークでテストした場合、SOTAベースラインに匹敵する可能性があることを驚くほど示している。 本研究は, 実世界のSTTD予測において, 簡便な有効モデルの探索に寄与する。
  論文  参考訳（メタデータ） (2023-07-04T05:19:19Z)
• Towards Expressive Spectral-Temporal Graph Neural Networks for Time Series Forecasting [101.5022396668152]
  スペクトル時間グラフニューラルネットワークは、ほとんどの時系列予測モデルの基礎となる、有望な抽象化である。 我々は、スペクトル時間GNNの表現力を高める理論的枠組みを確立する。 本研究は,GNNをベースとした時系列モデルにおいて,より広範に表現可能なGNNモデルを考案するための道筋をたどるものである。
  論文  参考訳（メタデータ） (2023-05-11T05:56:38Z)
• Space-Time Graph Neural Networks with Stochastic Graph Perturbations [100.31591011966603]
  時空間グラフニューラルネットワーク(ST-GNN)は、時間変動データの効率的なグラフ表現を学習する。 本稿では,ST-GNNの特性を再検討し,安定なグラフ安定性を示す。 解析の結果,ST-GNNは時間変化グラフ上での移動学習に適していることが示唆された。
  論文  参考訳（メタデータ） (2022-10-28T16:59:51Z)
• Universal approximation property of invertible neural networks [76.95927093274392]
  Invertible Neural Network (INN) は、設計によって可逆性を持つニューラルネットワークアーキテクチャである。 その可逆性とヤコビアンのトラクタビリティのおかげで、IGNは確率的モデリング、生成的モデリング、表現的学習など、さまざまな機械学習応用がある。
  論文  参考訳（メタデータ） (2022-04-15T10:45:26Z)

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

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