Algorithmic Simplification for Million-Vertex Diffusion History Reconstruction
Social and Information NetworksDistributed, Parallel, and Cluster Computing
Summary
The authors studied how to figure out hidden steps in spreading processes like disease models (SI and SIR) from limited data. They simplified a complex method called HERMES by removing parts like learning-based proposals and sampling, ending up with a faster, fixed-rate approach named Battus-Z. Despite these simplifications, Battus-Z performed as well as or better than HERMES on standard tests and handled very large networks efficiently using CUDA. However, some challenges like improving future predictions remain to be addressed.
Authors
Gökhan Göktürk
Abstract
Diffusion history reconstruction infers latent node states between sparse observations of SI or SIR processes. HERMES combines parameter fitting, a learned graph-neural proposal, and feasibility-aware Markov chain Monte Carlo. We remove these stages one at a time and evaluate each version on all 12 canonical datasets. The final method uses deterministic mean-field forward-backward inference, threshold decoding, and fixed rates. This fixed-rate variant, Battus-Z, achieves mean macro-F1 of 0.8726 and NRMSE of 0.1010, compared with published HERMES aggregates of 0.8692 and 0.1483. The benchmark pins the final observed frame before scoring, so we also exclude all observed frames. Under this metric, Battus-Z obtains macro-F1 0.8431 and NRMSE 0.1181. Thus, the learned proposal, MCMC, and fitting stages can be removed while retaining the published aggregate quality on the evaluated HERMES benchmark and scoring protocol. A CUDA implementation processes generated histories with up to 4.84M vertices on LiveJournal and 117M edges on Orkut. On the same CUDA backend, Battus-Z reduces the geometric-mean algorithm interval relative to fitted Battus by 5.1x for SI and 20.3x for SIR. Its event-weighted causal-violation rates are 7.50% for SI and 8.77% for SIR; graph-constrained decoding remains future work.