論文の概要: Reconstructing Graph Diffusion History from a Single Snapshot
- arxiv url: http://arxiv.org/abs/2306.00488v4
- Date: Fri, 31 May 2024 23:25:07 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-04 21:29:55.902946
- Title: Reconstructing Graph Diffusion History from a Single Snapshot
- Title(参考訳): 単一スナップショットからのグラフ拡散履歴の再構成
- Authors: Ruizhong Qiu, Dingsu Wang, Lei Ying, H. Vincent Poor, Yifang Zhang, Hanghang Tong,
- Abstract要約: A single SnapsHot (DASH) から拡散履歴を再構築するための新しいバリセンターの定式化を提案する。
本研究では,拡散パラメータ推定のNP硬度により,拡散パラメータの推定誤差が避けられないことを証明する。
また、DITTO(Diffusion hitting Times with Optimal proposal)という効果的な解法も開発している。
- 参考スコア(独自算出の注目度): 87.20550495678907
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Diffusion on graphs is ubiquitous with numerous high-impact applications. In these applications, complete diffusion histories play an essential role in terms of identifying dynamical patterns, reflecting on precaution actions, and forecasting intervention effects. Despite their importance, complete diffusion histories are rarely available and are highly challenging to reconstruct due to ill-posedness, explosive search space, and scarcity of training data. To date, few methods exist for diffusion history reconstruction. They are exclusively based on the maximum likelihood estimation (MLE) formulation and require to know true diffusion parameters. In this paper, we study an even harder problem, namely reconstructing Diffusion history from A single SnapsHot} (DASH), where we seek to reconstruct the history from only the final snapshot without knowing true diffusion parameters. We start with theoretical analyses that reveal a fundamental limitation of the MLE formulation. We prove: (a) estimation error of diffusion parameters is unavoidable due to NP-hardness of diffusion parameter estimation, and (b) the MLE formulation is sensitive to estimation error of diffusion parameters. To overcome the inherent limitation of the MLE formulation, we propose a novel barycenter formulation: finding the barycenter of the posterior distribution of histories, which is provably stable against the estimation error of diffusion parameters. We further develop an effective solver named DIffusion hiTting Times with Optimal proposal (DITTO) by reducing the problem to estimating posterior expected hitting times via the Metropolis--Hastings Markov chain Monte Carlo method (M--H MCMC) and employing an unsupervised graph neural network to learn an optimal proposal to accelerate the convergence of M--H MCMC. We conduct extensive experiments to demonstrate the efficacy of the proposed method.
- Abstract(参考訳): グラフ上の拡散は、多くのハイインパクトな応用でユビキタスである。
これらの応用において、完全な拡散履歴は、動的パターンの同定、予防行動の反映、介入効果の予測において重要な役割を担っている。
その重要性にもかかわらず、完全な拡散履歴はめったに得られず、不適切さ、爆発的な捜索空間、訓練データの不足により、再構築が極めて困難である。
現在、拡散史再構築のための方法はほとんど存在しない。
これらは極大推定(MLE)の定式化のみに基づいており、真の拡散パラメータを知る必要がある。
本稿では,単一SnapsHot(DASH)から拡散履歴を再構成する,さらに難しい問題について検討する。
まず、MLEの定式化の基本的な限界を明らかにする理論解析から始める。
証明する。
(a)拡散パラメータの推定誤差は、拡散パラメータ推定のNP硬度により避けられず、
b) MLE定式化は拡散パラメータの推定誤差に敏感である。
MLEの定式化に固有の限界を克服するために,拡散パラメータの推定誤差に対して確実に安定な,ヒストリーの後部分布のバリ中心を見つけるという,新しいバリセンター定式化を提案する。
さらに,メトロポリス-ハスティングス・マルコフ連鎖モンテカルロ法 (M--H MCMC) を経由し,M-H MCMCの収束を早めるための最適提案を学習するために教師なしグラフニューラルネットワークを用いて,DITTO (Diffusion hitting Times with Optimal proposal) と呼ばれる効果的な解法を開発した。
提案手法の有効性を実証するための広範囲な実験を行った。
関連論文リスト
- Theoretical Benefit and Limitation of Diffusion Language Model [47.579673047639126]
拡散言語モデルは、テキスト生成の有望なアプローチとして現れてきた。
本稿では,広く使われている拡散言語モデルMasked Diffusion Model(MDM)の厳密な理論的解析について述べる。
我々の分析は、MDMの利点と限界を理解するための最初の理論的基盤を確立している。
論文 参考訳(メタデータ) (2025-02-13T18:59:47Z) - RDPI: A Refine Diffusion Probability Generation Method for Spatiotemporal Data Imputation [4.251739849724956]
インキュベーションは交通流のモニタリング、大気質の評価、気候予報など様々な分野で重要な役割を担っている。
センサによって収集されたデータは、しばしば時間的不完全性に悩まされ、蓄積と不均一な分布は、データ不足につながる。
本稿では,初期ネットワークと条件拡散モデルに基づく2段階改良型確率計算フレームワークを提案する。
論文 参考訳(メタデータ) (2024-12-17T08:06:00Z) - A solvable generative model with a linear, one-step denoiser [0.0]
線形デノイザに基づく解析的抽出可能な単一ステップ拡散モデルを構築した。
トレーニングデータセットのサイズがデータポイントの次元に達すると,Kulback-Leibler分散の単調落下相が始まります。
論文 参考訳(メタデータ) (2024-11-26T19:00:01Z) - Diffusion State-Guided Projected Gradient for Inverse Problems [82.24625224110099]
逆問題に対する拡散状態ガイド型射影勾配(DiffStateGrad)を提案する。
DiffStateGrad は拡散過程の中間状態の低ランク近似である部分空間に測定勾配を投影する。
DiffStateGradは、測定手順のステップサイズとノイズの選択によって拡散モデルのロバスト性を向上させる。
論文 参考訳(メタデータ) (2024-10-04T14:26:54Z) - Amortizing intractable inference in diffusion models for vision, language, and control [89.65631572949702]
本稿では,p(mathbfx)$以前の拡散生成モデルとブラックボックス制約,あるいは関数$r(mathbfx)$からなるモデルにおいて,データ上の後部サンプルである $mathbfxsim prm post(mathbfx)propto p(mathbfx)r(mathbfx)$について検討する。
我々は,データフリー学習目標である相対軌道バランスの正しさを,サンプルから抽出した拡散モデルの訓練のために証明する。
論文 参考訳(メタデータ) (2024-05-31T16:18:46Z) - Lipschitz Singularities in Diffusion Models [64.28196620345808]
拡散モデルは、零点付近の時間変数に関して、しばしばネットワークの無限のリプシッツ特性を示す。
ゼロ点近傍の拡散モデルのリプシッツ特異点を緩和する新しい手法 E-TSDM を提案する。
我々の研究は、一般拡散過程の理解を深め、拡散モデルの設計に関する洞察を提供するかもしれない。
論文 参考訳(メタデータ) (2023-06-20T03:05:28Z) - Structural Pruning for Diffusion Models [65.02607075556742]
Diff-Pruningは、既存のものから軽量拡散モデルの学習に適した効率的な圧縮手法である。
複数のデータセットにまたがって実施した経験的評価は,提案手法の2つの利点を浮き彫りにしている。
論文 参考訳(メタデータ) (2023-05-18T12:38:21Z) - How Much is Enough? A Study on Diffusion Times in Score-based Generative
Models [76.76860707897413]
現在のベストプラクティスは、フォワードダイナミクスが既知の単純なノイズ分布に十分に近づくことを確実にするために大きなTを提唱している。
本稿では, 理想とシミュレーションされたフォワードダイナミクスのギャップを埋めるために補助モデルを用いて, 標準的な逆拡散過程を導出する方法について述べる。
論文 参考訳(メタデータ) (2022-06-10T15:09:46Z) - Diffusion Causal Models for Counterfactual Estimation [18.438307666925425]
本稿では,観測画像データから因果構造を推定する作業について考察する。
Diff-SCMは,近年の発電エネルギーモデルの発展を基盤とした構造因果モデルである。
Diff-SCMはMNISTデータに基づくベースラインよりも現実的で最小限のデファクトアルを生成しており、ImageNetデータにも適用可能である。
論文 参考訳(メタデータ) (2022-02-21T12:23:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。