PaperlayerView exact revision on arXiv

Source-linked AI summary

Algorithmic Simplification for Million-Vertex Diffusion History Reconstruction

Gökhan Göktürk

arXiv:2608.28955v1cs.SIcs.DC

TL;DR

Diffusion history reconstruction must infer latent SI/SIR states between sparse observations, while HERMES relies on fitting, learned proposals, and MCMC. This paper replaces those stages with deterministic mean-field forward–backward inference and fixed rates, finding that Battus-Z retains published aggregate quality on the evaluated benchmark and scoring protocol. The method also evaluates unobserved-only quality and causal feasibility, while noting that graph-constrained decoding remains unresolved.

  • Problem

    Diffusion history reconstruction estimates unobserved network states between sparse snapshots, but HERMES’s fitting, learned proposal, and sampling stages complicate deployment on large graphs.

  • Method

    The study removes HERMES stages through controlled ablations, producing deterministic mean-field forward–backward inference with threshold decoding and fixed rates in Battus-Z.

  • Results

    Battus-Z retains published aggregate quality on the evaluated benchmark and scoring protocol, achieving mean F1 0.8431 and NRMSE 0.1181 when observed frames are excluded.

  • Takeaways & Limitations

    The learned proposal, MCMC, and fitting stages can be removed while retaining the evaluated benchmark’s published aggregate quality.

  • Takeaways & Limitations

    Battus-Z enforces observation consistency and irreversible state order but does not certify graph-causal reachability.

Abstract

from arXiv · show

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.

I. INTRODUCTION

Diffusion history reconstruction estimates unobserved network states from sparse snapshots, but HERMES’s fitting, learned proposal, and sampling stages complicate large-graph deployment. The study tests deterministic replacements and evaluates their reconstruction quality and scalability.

  • Complete histories support retrospective analysis and intervention design when continuous diffusion observation is unavailable.
  • For n vertices and T+1 frames, the unconstrained history space contains |X|^(n(T+1)) assignments, while feasible histories must satisfy transition rules and observations.
  • HERMES combines estimated diffusion parameters, a graph-neural proposal, and feasibility-aware Metropolis–Hastings sampling.
  • The study removes or replaces pipeline stages one at a time and retains candidates only when they pass the complete canonical benchmark’s quality gate.
  • Battus-Z uses deterministic mean-field forward–backward inference, threshold decoding, and fixed diffusion rates after removing learned proposals, MCMC, and fitting.
  • SIR uses susceptible, infected, and recovered states with irreversible order, transmission trials, and recovery transitions.

B. History Reconstruction

History reconstruction seeks a complete diffusion trajectory consistent with sparse observations and the assumed process. The output must assign states across all vertices and times, with substantial temporal and graph-work requirements.

  • The reconstruction objective is to recover a complete history with nonzero probability under the assumed diffusion process and exact agreement at every observed time.
  • Only selected snapshots are observed, so unobserved states—including a possibly unobserved terminal frame—must be inferred.
  • Battus guarantees irreversible state order and exact observation agreement but does not test graph-causal reachability after deterministic decoding.
  • A complete output requires Θ(Tn) space, while repeated neighborhood propagation requires Θ(T(m + n)) work.

III. RELATED WORK

Prior work spans source and path reconstruction, probabilistic inverse diffusion, general spatiotemporal imputation, and high-performance graph computation. Battus addresses complete SI/SIR histories with multiple snapshots while combining diffusion constraints with repeated graph propagation.

  • Source localization estimates initial spreaders, path reconstruction estimates transmission structure, and history reconstruction assigns states to every vertex and time.
  • DITTO reconstructs complete SI/SIR histories from one snapshot, whereas HERMES handles multiple snapshots with parameter estimation and feasibility-aware MCMC.
  • Diffusion-specific inverse methods include denoising diffusion, self-supervised reverse processes, temporal hypergraph models, and conformal source detection.
  • General imputers such as BRITS, GRIN, and SPIN do not directly impose SI/SIR feasibility and exact agreement with observed snapshots.
  • Repeated temporal propagation and Θ(Tn) history storage distinguish diffusion reconstruction from conventional graph traversal and motivate GPU evaluation.

IV. METHODOLOGY

The methodology simplifies HERMES through controlled stage ablations, replacing learned sampling with deterministic mean-field inference and then removing rate fitting. The resulting operations are designed for CUDA and preserve snapshot constraints.

  • Ablation workflow: Every candidate is evaluated on all 12 canonical datasets while datasets, observations, seeds, and scoring rules remain fixed.
  • Ablation workflow: The first subtraction replaces learned proposals and sampling with deterministic inference, and removing rate fitting produces Battus-Z.
  • Battus pipeline: Battus performs rate fitting, mean-field propagation, segment-wise forward–backward smoothing, and monotone decoding.
  • Problem setup: The inverse input consists of sparse observed states, leaving unavailable vertex states across the remaining history to reconstruct.
  • Battus pipeline: Battus-Z fixes the diffusion rates and uses compressed sparse row graph storage for implementation.
  • Mean-field propagation: Mean-field propagation approximates per-vertex state probabilities from infection and recovery rates, with an initial marginal shared across vertices.
  • Mean-field propagation: Each propagation update scans every CSR adjacency once and costs O(m + n).

C. Derivative-Free Rate Fitting

Battus fits diffusion rates with bounded derivative-free grid search, while Battus-Z removes fitting by using fixed rates; both retain anchored forward–backward smoothing over observed segments.

  • Rate fitting: Battus estimates diffusion rates with a coarse grid over [10^-4, 0.5] followed by four shrinking refinement rounds.The search is one-dimensional for SI and two-dimensional for SIR, with a graph-size-independent configured grid budget.
  • Fixed-rate variant: Battus-Z fixes βI = 0.1 and βR = 0.1 for SIR, eliminating all parameter-search passes.A continuous mean-field recursion supplies frozen neighbor pressures, while segment-local messages remain anchored at observations.
  • Forward–backward smoothing: Each observed interval uses frozen mean-field neighbor fields to form a time-inhomogeneous three-state Markov chain for each vertex.Forward messages start at the left endpoint and backward messages at the observed right endpoint.
  • Complexity: Forward–backward inference costs O((tr −tl)(m + n)) per segment, O(T(m + n)) overall, and stores O(Tn) posterior values.Segment-local messages use offset j, while output posteriors use absolute time tl + j.

E. Deterministic Decoding

Deterministic decoding converts smoothed posteriors into infection and recovery times using either MAP or threshold rules, then enforces observed endpoints and irreversible state order.

  • Decoder rules: MAP decoding selects the highest-posterior state at every frame and applies cumulative maximum under the irreversible order S < I < R.This produces monotone decoded trajectories for the ordered states.
  • Decoder rules: Threshold decoding identifies infection at the first frame with 1 − γS ≥ τ and recovery at the first frame with γR ≥ τ.Recovery-time decoding applies to SIR histories.
  • Threshold choice: τ = 0.65 is the reported Battus-Z threshold, and Table VI places it on a broad quality plateau.The threshold is therefore selected within a region of similar evaluated quality.
  • Anchor consistency: Decoding projects both boundaries to agree exactly with observed snapshots and pins the terminal frame before scoring.The projection has no numerical effect on the evaluated suite because endpoint-conditioned posteriors already respect the anchors.
  • Scope: The deterministic decoder runs in O(Tn) but does not verify that each decoded infection has an infected predecessor at the prior frame.Thus monotone decoding and projection enforce observation consistency without graph-causal reachability checks.

F. CUDA Implementation

The CUDA implementation keeps graph and inference data on-device, parallelizes vertex work within sequential time steps, and evaluates both canonical and large-graph histories.

  • Device implementation: CUDA kernels retain CSR topology, observations, mean-field fields, and posterior arrays on the device.Destination-oriented kernels compute incoming infection pressure, while vertex-parallel kernels update messages and decode histories.
  • Parallelism: Time steps remain sequential because each frame depends on the previous one, while all vertices within a step execute in parallel.The implementation uses 256-thread blocks with one thread assigned to each destination vertex.
  • Fitted-rate parallelism: The fitted implementation batches 24 × 24 SIR rate candidates and 24 SI infection-rate candidates in device-side grid evaluation.Four refinement rounds then evaluate 7 × 7 SIR or 7 SI candidates.
  • Evaluation: The evaluation includes the 12-dataset HERMES suite and eight additional large-graph histories, for 20 datasets total.The canonical suite covers synthetic SI/SIR and real SI-like and SIR-like diffusion, while large-scale experiments test scalability.
  • Evaluation protocol: The CUDA quality study uses the same canonical text exports, fixed seed, observation schedule, and diffusion settings across runs.Large histories use βI = 0.1, βR = 0.1 for SIR, 100 initial infections, and synchronous simulation.

B. Design Sequence and Quality Gates

The study removes computational stages one at a time and accepts replacements only when they meet aggregate quality gates on all 12 canonical datasets, using benchmark-compatible scoring and additional causal measurements.

  • Quality gates: Each candidate preserves the observation and scoring protocol and is accepted only if mean macro-F1 is at least 0.8692 and mean NRMSE is at most 0.1483.The criterion is a benchmark-specific development gate, not a statistical-equivalence test or generalization claim.
  • Benchmark comparison: The quality table compares reproduced HERMES baselines with Battus artifact measurements across 12 metric columns per panel.Average rank uses mean ranks for ties, and SPIN’s out-of-memory result receives worst rank and is excluded from SI metric means.
  • Metrics: Hitting time is the first frame in which a state occurs, with absence encoded by sentinel T + 1.Macro-F1 is computed after flattening the node-major history and averages only classes present in truth or prediction.
  • Metrics: Unobserved-only scores remove every observed time from truth and prediction before computing F1 and NRMSE.The final prediction is otherwise pinned to the observed final frame under the HERMES-compatible protocol.
  • Causal feasibility: Causal-violation measurement counts post-initial infection onsets lacking an infected directed predecessor one frame earlier.Initial infections are excluded, and CV is reported for both predictions and ground truth because real histories may violate graph or process assumptions.

VI. EVALUATION

Across the 12-dataset benchmark, Battus variants pass the aggregate quality gate, while masked evaluation exposes the effect of observed-frame inclusion and decoder choice.

  • Canonical benchmark: Both retained Battus variants pass the aggregate quality gate, with Battus-Z attaining the lowest NRMSE on all 12 datasets.The Battus family achieves the highest or tied macro-F1 on nine datasets.
  • Unobserved-only diagnostic: Removing observed frames lowers Battus-Z mean F1 to 0.8431 and raises NRMSE to 0.1181.The masked metric excludes the observed frames that contribute to canonical scoring and pins the terminal prediction.
  • Unobserved-only diagnostic: The masked values are a within-method diagnostic and cannot be directly compared with the published HERMES aggregate.Predicted histories are available for only six of HERMES’s twelve datasets.
  • Decoder ablation: Threshold crossing reduces Covid–SIR NRMSE to 0.1334 while retaining F1 0.7801, motivating its use in Battus-Z.The comparison illustrates that decoder choice affects temporal calibration more strongly than framewise accuracy.

B. Causal Feasibility and Rate Sensitivity

Battus-Z is evaluated for causal feasibility and sensitivity to fixed rates and decoding thresholds. It remains competitive under local parameter changes, but the results do not establish universal parameter insensitivity or graph-causal feasibility.

  • Causal feasibility: 7.50% for SI and 8.77% for SIR are Battus-Z’s event-weighted causal-violation rates.Covid–SIR reaches 40.35% for Battus-Z, while a reachability constraint remains future decoding work.
  • Rate sensitivity: The default rate pair (.1, .1) gives the best three-dataset mean F1 (.8392) and NRMSE (.1109), although (.1, .2) is better on Covid.The sensitivity grid covers synthetic BA–SIR, synthetic diffusion on Prost, and real Covid–SIR.
  • Threshold sensitivity: For τ ≤0.65, mean F1 varies by less than 0.006 and mean NRMSE by less than 0.004 across all twelve datasets.Quality then degrades monotonically; Hebrew–SIR falls from .8375 to .7801 at τ = 0.70.
  • Measurement design: Panel A measures noninitial infection onsets without an infected incoming neighbor, while Panel B reports a 3 × 3 rate grid on three representative SIR datasets.Truth is included because real observations need not be feasible under the supplied graph.
  • Rate sensitivity: Across twelve alternative-rate evaluations, macro-F1 stays within .021 and NRMSE within .013 of the matched same-generator reference.The fixed-seed check does not show that matching generation and inference rates explains Battus-Z quality.

C. Large-Graph Extension

Battus-Z extends deterministic reconstruction to large synthetic SNAP histories on CUDA. Removing fitting substantially shortens the same-backend algorithm interval, while the evaluation remains limited to synthetic histories and descriptive single-run comparisons.

  • CUDA scalability: The CUDA implementation evaluates eight additional generated histories beyond the reference suite on an NVIDIA B200.Table VIII reports single-run fit–inference–decode intervals after initialization.
  • Quality comparison: Battus-Z has slightly higher mean F1 and lower mean NRMSE than fitted Battus on the generated scalability histories.These quality means are arithmetic, while time means are geometric.
  • CUDA scalability: 5.1× for SI and 20.3× for SIR are the reductions in geometric-mean algorithm interval from fitted Battus to Battus-Z.The intervals decrease from 436 to 85 ms for SI and from 1621 to 80 ms for SIR.
  • Scope: The large SNAP histories are synthetic and use Battus-Z’s default diffusion rates, so timing results support scalability and same-backend comparisons rather than speedups over HERMES.The rate-mismatch experiment is only a small-graph robustness check.
  • Scope: Battus-Z retains observation consistency and irreversible state order but does not certify graph-causal reachability.A full-suite masked comparison with HERMES also requires its six remaining predicted histories.
Loading 2608.28955v1…