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

• 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)
• Fast Diffusion EM: a diffusion model for blind inverse problems with application to deconvolution [0.0]
  Current methods assume the degradation to be known and provide impressive results in terms of restoration and diversity. In this work, we leverage the efficiency of those models to jointly estimate the restored image and unknown parameters of the kernel model. Our method alternates between approximating the expected log-likelihood of the problem using samples drawn from a diffusion model and a step to estimate unknown model parameters.
  arXiv  Detail & Related papers  (2023-09-01T06:47:13Z)
• Eliminating Lipschitz Singularities in Diffusion Models [51.806899946775076]
  We show that diffusion models frequently exhibit the infinite Lipschitz near the zero point of timesteps. This poses a threat to the stability and accuracy of the diffusion process, which relies on integral operations. We propose a novel approach, dubbed E-TSDM, which eliminates the Lipschitz of the diffusion model near zero.
  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)
• Where to Diffuse, How to Diffuse, and How to Get Back: Automated Learning for Multivariate Diffusions [22.04182099405728]
  Diffusion-based generative models (DBGMs) perturb data to a target noise distribution and reverse this inference diffusion process to generate samples. We show how to maximize a lower-bound on the likelihood for any number of auxiliary variables. We then demonstrate how to parameterize the diffusion for a specified target noise distribution.
  arXiv  Detail & Related papers  (2023-02-14T18:57:04Z)
• Information-Theoretic Diffusion [18.356162596599436]
  Denoising diffusion models have spurred significant gains in density modeling and image generation. We introduce a new mathematical foundation for diffusion models inspired by classic results in information theory.
  arXiv  Detail & Related papers  (2023-02-07T23:03:07Z)
• 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.