Graph Diffusion History Reconstruction via Feasibility-Aware Markov Chain Monte Carlo Estimation
Diffusion dynamics on graphs arise across many fields including information spreading and rumor cascades in online platforms, propagation of cascading outages in power and transportation infrastructures, diffusion of behaviors and product adoption in social networks, and transmission of shocks in financial and supply-chain systems. Graph diffusion provides a compact representation of how states propagate through interacting entities, yet in many applications the diffusion history is not fully observed. Typically, only a small set of snapshots are available while all other states are missing. Diffusion history reconstruction is challenging due to explosive search space, complex combinatorial constraints, and scarcity of training data. To address these challenges, we propose a new method called HERMES. HERMES has two main stages: (i) diffusion parameter estimation and (ii) diffusion history reconstruction. The first stage is to estimate the unknown diffusion parameters from the observed snapshots. To bypass the intractable maximum likelihood estimation of diffusion parameters, we instead propose a tractable mean-field approximation to estimate diffusion parameters. Second, based on the estimated diffusion parameters, we theoretically reduce history reconstruction to expected hitting time estimation through a bias--variance decomposition and estimate the expected hitting times via Metropolis--Hastings Markov chain Monte Carlo (M--H MCMC). The core component of M--H MCMC is the proposal distribution, and our proposal distribution handles the complex combinatorial constraints via a dynamic reachability mechanism that ensures compatibility with all observed snapshots. Moreover, to further enhance M--H MCMC, we parameterize the proposal using a graph neural network (GNN) and train the GNN to match the posterior distribution. Extensive experiments demonstrate that HERMES consistently outperforms existing methods on 12 synthetic and real-world datasets. Due to the page limit, please find the theoretical proofs at https://q-rz.github.io/static/kdd26/kdd26-hermes-extended.pdf.