論文の概要: Projecting infinite time series graphs to finite marginal graphs using
number theory
- arxiv url: http://arxiv.org/abs/2310.05526v1
- Date: Mon, 9 Oct 2023 08:45:06 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-12 06:51:09.856532
- Title: Projecting infinite time series graphs to finite marginal graphs using
number theory
- Title(参考訳): 数論を用いた有限辺グラフへの無限時系列グラフの射影
- Authors: Andreas Gerhardus, Jonas Wahl, Sofia Faltenbacher, Urmi Ninad, Jakob
Runge
- Abstract要約: 本研究では,有限時間ウィンドウ上で,連続エッジを持つ無限時系列グラフを境界グラフィカルモデルに投影する手法を開発した。
本論文は,理論的な基礎と手法に依存しない,様々な因果推論手法の一般化に向けて重要な一歩を踏み出したものである。
- 参考スコア(独自算出の注目度): 15.711918159136387
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In recent years, a growing number of method and application works have
adapted and applied the causal-graphical-model framework to time series data.
Many of these works employ time-resolved causal graphs that extend infinitely
into the past and future and whose edges are repetitive in time, thereby
reflecting the assumption of stationary causal relationships. However, most
results and algorithms from the causal-graphical-model framework are not
designed for infinite graphs. In this work, we develop a method for projecting
infinite time series graphs with repetitive edges to marginal graphical models
on a finite time window. These finite marginal graphs provide the answers to
$m$-separation queries with respect to the infinite graph, a task that was
previously unresolved. Moreover, we argue that these marginal graphs are useful
for causal discovery and causal effect estimation in time series, effectively
enabling to apply results developed for finite graphs to the infinite graphs.
The projection procedure relies on finding common ancestors in the
to-be-projected graph and is, by itself, not new. However, the projection
procedure has not yet been algorithmically implemented for time series graphs
since in these infinite graphs there can be infinite sets of paths that might
give rise to common ancestors. We solve the search over these possibly infinite
sets of paths by an intriguing combination of path-finding techniques for
finite directed graphs and solution theory for linear Diophantine equations. By
providing an algorithm that carries out the projection, our paper makes an
important step towards a theoretically-grounded and method-agnostic
generalization of a range of causal inference methods and results to time
series.
- Abstract(参考訳): 近年,時系列データに因果グラフモデルフレームワークを適用し応用する手法や応用が増えている。
これらの作品の多くは、過去と未来に無限に拡張され、エッジが時間内に反復的である時間分解因果グラフを用いており、定常因果関係の仮定を反映している。
しかし、因果モデルフレームワークのほとんどの結果とアルゴリズムは無限グラフ向けに設計されていない。
本研究では,有限時間窓上の辺縁モデルに対して,繰り返しエッジを持つ無限時系列グラフを投影する手法を開発した。
これらの有限辺グラフは、それまで未解決だった無限グラフに関して、$m$-分離クエリに対する答えを提供する。
さらに,これらの辺グラフは,時系列における因果的発見と因果的効果推定に有用であり,有限グラフで開発された結果を無限グラフに適用することができる。
プロジェクション手順は、投影されるグラフの共通の祖先を見つけることに依存しており、それ自体は新しいものではない。
しかし、射影手順は、これらの無限グラフにおいて、共通の祖先を生み出す可能性のある無限個の経路の集合が存在する可能性があるため、時系列グラフに対してアルゴリズム的に実装されていない。
有限有向グラフに対する経路探索法と線形ディオファントス方程式の解理論の興味深い組み合わせにより、これらの無限個の経路の集合の探索を解く。
このプロジェクションを実行するアルゴリズムを提供することにより,本論文は,様々な因果推論手法の理論的および手法に依存しない一般化に向けて重要な一歩を踏み出した。
関連論文リスト
- HeteroMILE: a Multi-Level Graph Representation Learning Framework for Heterogeneous Graphs [13.01983932286923]
異種グラフ上のノードのマルチレベル埋め込みフレームワーク(HeteroMILE)を提案する。
HeteroMILEは、グラフを埋め込む前に、グラフのバックボーン構造を保ちながら、大きなグラフを小さなサイズに繰り返し調整する。
その後、ヘテロジニアスグラフ畳み込みニューラルネットワークを用いて、元のグラフへの粗い埋め込みを洗練する。
論文 参考訳(メタデータ) (2024-03-31T22:22:10Z) - Overcoming Order in Autoregressive Graph Generation [12.351817671944515]
グラフ生成は、化学やソーシャルネットワークなど、さまざまな領域における基本的な問題である。
近年の研究では、リカレントニューラルネットワーク(RNN)を用いた分子グラフ生成が、従来の生成手法と比較して有利であることが示されている。
論文 参考訳(メタデータ) (2024-02-04T09:58:22Z) - Limits, approximation and size transferability for GNNs on sparse graphs
via graphops [44.02161831977037]
我々は,GNNを構成する集約演算など,グラフから導出される演算子の極限を取るという観点から考える。
我々の結果は、密でスパースなグラフ、およびグラフ極限の様々な概念に当てはまる。
論文 参考訳(メタデータ) (2023-06-07T15:04:58Z) - Graph Generation with Diffusion Mixture [57.78958552860948]
グラフの生成は、非ユークリッド構造の複雑な性質を理解する必要がある実世界のタスクにとって大きな課題である。
本稿では,拡散過程の最終グラフ構造を明示的に学習することにより,グラフのトポロジーをモデル化する生成フレームワークを提案する。
論文 参考訳(メタデータ) (2023-02-07T17:07:46Z) - Explanation Graph Generation via Pre-trained Language Models: An
Empirical Study with Contrastive Learning [84.35102534158621]
エンドツーエンドで説明グラフを生成する事前学習言語モデルについて検討する。
本稿では,ノードとエッジの編集操作によるグラフ摂動の簡易かつ効果的な方法を提案する。
提案手法は,説明グラフの構造的精度と意味的精度を両立させる。
論文 参考訳(メタデータ) (2022-04-11T00:58:27Z) - Graphon based Clustering and Testing of Networks: Algorithms and Theory [11.3700474413248]
ネットワークに価値のあるデータは、幅広いアプリケーションで遭遇し、学習の課題を提起する。
本稿では,2つのクラスタリングアルゴリズムについて述べる。
さらに、グラフ2サンプルテスト問題に対する提案した距離の適用性について検討する。
論文 参考訳(メタデータ) (2021-10-06T13:14:44Z) - Order Matters: Probabilistic Modeling of Node Sequence for Graph
Generation [18.03898476141173]
グラフ生成モデルはグラフ上の分布を定義する。
グラフ上の正確な結合確率とシーケンシャルプロセスのノード順序を導出する。
我々は,従来の手法のアドホックノード順序を使わずに,この境界を最大化してグラフ生成モデルを訓練する。
論文 参考訳(メタデータ) (2021-06-11T06:37:52Z) - ExplaGraphs: An Explanation Graph Generation Task for Structured
Commonsense Reasoning [65.15423587105472]
スタンス予測のための説明グラフ生成の新しい生成および構造化コモンセンスリゾニングタスク(および関連するデータセット)を紹介します。
具体的には、信念と議論が与えられた場合、モデルは、議論が信念を支持しているかどうかを予測し、予測されたスタンスに対する非自明で完全で曖昧な説明として機能する常識強化グラフを生成する必要がある。
グラフの83%は、様々な構造と推論深度を持つ外部のコモンセンスノードを含んでいる。
論文 参考訳(メタデータ) (2021-04-15T17:51:36Z) - Line Graph Neural Networks for Link Prediction [71.00689542259052]
実世界の多くのアプリケーションにおいて古典的なグラフ解析問題であるグラフリンク予測タスクについて検討する。
このフォーマリズムでは、リンク予測問題をグラフ分類タスクに変換する。
本稿では,線グラフをグラフ理論に用いて,根本的に異なる新しい経路を求めることを提案する。
特に、線グラフの各ノードは、元のグラフのユニークなエッジに対応するため、元のグラフのリンク予測問題は、グラフ分類タスクではなく、対応する線グラフのノード分類問題として等価に解決できる。
論文 参考訳(メタデータ) (2020-10-20T05:54:31Z) - Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
我々は高密度サブグラフ発見のための新しい学習問題を導入する。
まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。
そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
論文 参考訳(メタデータ) (2020-06-24T11:37:33Z) - Block-Approximated Exponential Random Graphs [77.4792558024487]
指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。
本稿では,非自明なERGに対する近似フレームワークを提案する。
我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
論文 参考訳(メタデータ) (2020-02-14T11:42:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。