# Reconstructing Graph Diffusion History from a Single Snapshot

arXiv: https://arxiv.org/abs/2306.00488 · HTML: https://mlsanity.com/paper/2306.00488/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 100 references that are in the map.
- First posted on arXiv 1 Jun 2023.

## Builds on (most cited first, 22 of 22)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift](https://mlsanity.com/paper/1502.03167/) (2015)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Sigmoid-Weighted Linear Units for Neural Network Function Approximation in Reinforcement Learning](https://mlsanity.com/paper/1702.03118/) (2017)
- [Diffusion Improves Graph Learning](https://mlsanity.com/paper/1911.05485/) (2019)
- [BRITS: Bidirectional Recurrent Imputation for Time Series](https://mlsanity.com/paper/1805.10572/) (2018)
- [GRAND: Graph Neural Diffusion](https://mlsanity.com/paper/2106.10934/) (2021)
- [DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problems](https://mlsanity.com/paper/2210.04123/) (2022)
- [Filling the G_ap_s: Multivariate Time Series Imputation by Graph Neural Networks](https://mlsanity.com/paper/2108.00298/) (2021)
- [Learning to Reconstruct Missing Data from Spatiotemporal Graphs with Sparse Observations](https://mlsanity.com/paper/2205.13479/) (2022)
- [Dissecting the Diffusion Process in Linear Graph Convolutional Networks](https://mlsanity.com/paper/2102.10739/) (2021)
- [Network of Tensor Time Series](https://mlsanity.com/paper/2102.07736/) (2021)
- [Optimization-Induced Graph Implicit Nonlinear Diffusion](https://mlsanity.com/paper/2206.14418/) (2022)
- [Source Localization of Graph Diffusion via Variational Autoencoders for Graph Inverse Problems](https://mlsanity.com/paper/2206.12327/) (2022)
- [Catch'Em All: Locating Multiple Diffusion Sources in Networks with Partial Observations](https://mlsanity.com/paper/1611.06963/) (2016)
- [An Invertible Graph Diffusion Neural Network for Source Localization](https://mlsanity.com/paper/2206.09214/) (2022)
- [Trace Complexity of Network Inference](https://mlsanity.com/paper/1308.2954/) (2013)
- [Diffusion Source Identification on Networks with Statistical Confidence](https://mlsanity.com/paper/2106.04800/) (2021)
- [Back to the Past: Source Identification in Diffusion Networks from Partially Observed Cascades](https://mlsanity.com/paper/1501.06582/) (2015)
- [Collaborative Inference of Coexisting Information Diffusions](https://mlsanity.com/paper/1708.06890/) (2017)
- [Kinetics of Social Contagion](https://mlsanity.com/paper/1506.00251/) (2015)
- [Network Infusion to Infer Information Sources in Networks](https://mlsanity.com/paper/1606.07383/) (2016)

## Built on by (most cited first, 13 of 13)

- [Discrete-state Continuous-time Diffusion for Graph Generation](https://mlsanity.com/paper/2405.11416/) (2024)
- [How Efficient is LLM-Generated Code? A Rigorous & High-Standard Benchmark](https://mlsanity.com/paper/2406.06647/) (2024)
- [Pave Your Own Path: Graph Gradual Domain Adaptation on Fused Gromov-Wasserstein Geodesics](https://mlsanity.com/paper/2505.12709/) (2025)
- [Gradient Compressed Sensing: A Query-Efficient Gradient Estimator for High-Dimensional Zeroth-Order Optimization](https://mlsanity.com/paper/2405.16805/) (2024)
- [Breaking Silos: Adaptive Model Fusion Unlocks Better Time Series Forecasting](https://mlsanity.com/paper/2505.18442/) (2025)
- [Matcha: Mitigating Graph Structure Shifts with Test-Time Adaptation](https://mlsanity.com/paper/2410.06976/) (2024)
- [Ask, and it shall be given: On the Turing completeness of prompting](https://mlsanity.com/paper/2411.01992/) (2024)
- [PLANETALIGN: A Comprehensive Python Library for Benchmarking Network Alignment](https://mlsanity.com/paper/2505.21366/) (2025)
- [Fine-grained Graph Rationalization](https://mlsanity.com/paper/2312.07859/) (2023)
- [Saffron-1: Safety Inference Scaling](https://mlsanity.com/paper/2506.06444/) (2025)
- [Graph Homophily Booster: Rethinking the Role of Discrete Features on Heterophilic Graphs](https://mlsanity.com/paper/2509.12530/) (2025)
- [Graph homophily booster: Reimagining the role of discrete features in heterophilic graph learning](https://mlsanity.com/paper/2602.07256/) (2026)
- [Structuring and Tokenizing Distributed User Interest Context for Generative Recommendation](https://mlsanity.com/paper/2606.20554/) (2026)

## Abstract (arXiv)

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.