Reconstructing Graph Diffusion History from a Single Snapshot

• URL: http://arxiv.org/abs/2306.00488v4
• Date: Fri, 31 May 2024 23:25:07 GMT
• Title: Reconstructing Graph Diffusion History from a Single Snapshot
• Authors: Ruizhong Qiu, Dingsu Wang, Lei Ying, H. Vincent Poor, Yifang Zhang, Hanghang Tong,
• Abstract summary: We propose a novel barycenter formulation for reconstructing Diffusion history from A single SnapsHot (DASH) We prove that estimation error of diffusion parameters is unavoidable due to NP-hardness of diffusion parameter estimation. We also develop an effective solver named DIffusion hiTting Times with Optimal proposal (DITTO)
• Score: 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.

Related papers

• Theoretical Benefit and Limitation of Diffusion Language Model [47.579673047639126]
  Diffusion language models have emerged as a promising approach for text generation. We present a rigorous theoretical analysis of a widely used type of diffusion language model, the Masked Diffusion Model (MDM) Our analysis establishes the first theoretical foundation for understanding the benefits and limitations of MDMs.
  arXiv  Detail & Related papers  (2025-02-13T18:59:47Z)
• RDPI: A Refine Diffusion Probability Generation Method for Spatiotemporal Data Imputation [4.251739849724956]
  imputation plays a crucial role in various fields such as traffic flow monitoring, air quality assessment and climate prediction. Data collected by sensors often suffer from temporal incompleteness, and the accumulation and uneven distribution leads to missing data. We propose a novel two-stage refined probability imputation framework based on an initial network and a conditional diffusion model.
  arXiv  Detail & Related papers  (2024-12-17T08:06:00Z)
• A solvable generative model with a linear, one-step denoiser [0.0]
  We develop an analytically tractable single-step diffusion model based on a linear denoiser. We show that the monotonic fall phase of Kullback-Leibler divergence begins when the training dataset size reaches the dimension of the data points.
  arXiv  Detail & Related papers  (2024-11-26T19:00:01Z)
• Diffusion State-Guided Projected Gradient for Inverse Problems [82.24625224110099]
  We propose Diffusion State-Guided Projected Gradient (DiffStateGrad) for inverse problems. DiffStateGrad projects the measurement gradient onto a subspace that is a low-rank approximation of an intermediate state of the diffusion process. We highlight that DiffStateGrad improves the robustness of diffusion models in terms of the choice of measurement guidance step size and noise.
  arXiv  Detail & Related papers  (2024-10-04T14:26:54Z)
• Amortizing intractable inference in diffusion models for vision, language, and control [89.65631572949702]
  This paper studies amortized sampling of the posterior over data, $mathbfxsim prm post(mathbfx)propto p(mathbfx)r(mathbfx)$, in a model that consists of a diffusion generative model prior $p(mathbfx)$ and a black-box constraint or function $r(mathbfx)$. We prove the correctness of a data-free learning objective, relative trajectory balance, for training a diffusion model that samples from
  arXiv  Detail & Related papers  (2024-05-31T16:18:46Z)
• Lipschitz Singularities in Diffusion Models [64.28196620345808]
  Diffusion models often display the infinite Lipschitz property of the network with respect to time variable near the zero point. We propose a novel approach, dubbed E-TSDM, which alleviates the Lipschitz singularities of the diffusion model near the zero point. Our work may advance the understanding of the general diffusion process, and also provide insights for the design of diffusion models.
  arXiv  Detail & Related papers  (2023-06-20T03:05:28Z)
• Structural Pruning for Diffusion Models [65.02607075556742]
  We present Diff-Pruning, an efficient compression method tailored for learning lightweight diffusion models from pre-existing ones. Our empirical assessment, undertaken across several datasets highlights two primary benefits of our proposed method.
  arXiv  Detail & Related papers  (2023-05-18T12:38:21Z)
• How Much is Enough? A Study on Diffusion Times in Score-based Generative Models [76.76860707897413]
  Current best practice advocates for a large T to ensure that the forward dynamics brings the diffusion sufficiently close to a known and simple noise distribution. We show how an auxiliary model can be used to bridge the gap between the ideal and the simulated forward dynamics, followed by a standard reverse diffusion process.
  arXiv  Detail & Related papers  (2022-06-10T15:09:46Z)
• Diffusion Causal Models for Counterfactual Estimation [18.438307666925425]
  We consider the task of counterfactual estimation from observational imaging data given a known causal structure. We propose Diff-SCM, a deep structural causal model that builds on recent advances of generative energy-based models. We find that Diff-SCM produces more realistic and minimal counterfactuals than baselines on MNIST data and can also be applied to ImageNet data.
  arXiv  Detail & Related papers  (2022-02-21T12:23:01Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.