arXiv CS open access

Algorithmic Simplification for Million-Vertex Diffusion History Reconstruction

2026 · arxiv_cs

arXiv CS · Papers · 2026

cloud distributed-computing parallel-computing

Conceptio Open Archive

Analyze & explore related research in Conceptio

Connect this record directly into your research workflow or AI agent. Explore citations across open repositories, query full text, and export structured proof bundles.

Explore in Search →Connect via MCP / API ↗

Algorithmic Simplification for Million-Vertex Diffusion History Reconstruction Gökhan Göktürk

arXiv:2608.28955v1 [cs.SI] 28 Aug 2026

Independent Researcher ggokturk@sabanciuniv.edu

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 meanfield forward–backward inference, threshold decoding, and fixed rates. This fixed-rate variant, Battus-Z, achieves mean macroF1 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.1× for SI and 20.3× for SIR. Its event-weighted causal-violation rates are 7.50% for SI and 8.77% for SIR; graph-constrained decoding remains future work. Source code is available at https://github.com/ggokturk/battus. Index Terms—diffusion history reconstruction, graph algorithms, deterministic inference, SI model, SIR model, CUDA

I. I NTRODUCTION

histories with millions of vertices and report its absolute algorithm time. Deterministic mean-field forward–backward inference first replaces learned proposal generation and MCMC. Derivativefree rate search then replaces gradient-based fitting, followed by a fixed-rate version that removes fitting. Separate ablations test MAP and posterior-threshold decoding, the backward pass, resets, and anchor projection. These steps produce Battus and its zero-fit Battus-Z variant. Because the canonical scorer pins the final observed frame, we also report F1 and NRMSE after removing all observed frames from truth and prediction. This paper contributes: (i) a full-suite simplification study showing that HERMES’s learned proposal generation, MCMC, and parameter fitting can be removed while retaining its published aggregate quality on the evaluated benchmark and scoring protocol; (ii) Battus, a deterministic fit–smooth–decode method, and Battus-Z, its fixed-rate form; (iii) an unobservedonly quality diagnostic, component ablations, causal-feasibility measurement, and fixed-rate sensitivity analysis; and (iv) a CUDA implementation and an eight-history scalability evaluation on large SNAP topologies.

II. BACKGROUND AND P ROBLEM D EFINITION Graph diffusion represents the propagation of infection, information, adoption, or failure through interacting entities [1], A. Discrete-Time Graph Diffusion [2]. Complete histories support retrospective analysis and Let G = (V, E) be a graph with n = |V | vertices and intervention design, but continuous observation is frequently m directed arcs after storage conversion. The time index is unavailable. Diffusion history reconstruction therefore estimates T = {0, . . . , T } and yt,u ∈ X is the state of vertex u at time t. the unobserved states between a small number of network A snapshot is yt = (yt,u )u∈V , and a complete history is Y = snapshots. (y , . . . , y ). The process is first-order Markov: conditioned 0 T For n vertices, T +1 frames, and |X | states, the unconstrained on y , vertex transitions are independent and depend only on n(T +1) t history space contains |X | assignments. Feasible histhe current state and infected in-neighbors. tories must also satisfy local transition rules and observed For SIR diffusion, X = {S, I, R} with irreversible order snapshots. HERMES uses estimated diffusion parameters, S < I < R [1]. A discrete step comprises independent transa graph-neural proposal, and feasibility-aware Metropolis– mission trials on active incoming arcs, each with probability β I , Hastings sampling [3]. Its fitting, training, and sampling stages R followed by recovery with probability β . If u is susceptible, complicate deployment on large graphs. The study tests which parts of this pipeline are required for its probability of avoiding infection is its published reconstruction quality. We remove or replace one Y qt,u = (1 − β I ). (1) stage at a time, run the complete canonical benchmark under v∈N (u): yt,v =I unchanged metric conventions, and keep a change only when it passes the quality gate. The resulting algorithm is deterministic and consists of regular graph and vertex operations that map Let pt,u (x) = Pr(yt+1,u = x | yt ), let 1[·] denote an indicator, to CUDA. We test the CUDA implementation on generated and define the probability of being infected after transmission

a parsimonious temporal Steiner tree without prescribing a parametric epidemic model [6]; its recent online extension modifies source costs to reduce instability under delayed qt,u or missing temporal edges [7]. DITTO targets complete 1 SI/SIR histories from one snapshot by estimating posterior Fig. 1. State transitions of the discrete-time SIR process. expected hitting times with Metropolis–Hastings sampling and a learned proposal [4]. HERMES addresses multiple snapshots using segmented parameter estimation and feasibility-aware but before recovery as at,u = (1−qt,u )1[yt,u = S]+1[yt,u = I]. MCMC [3]. Battus retains the full-history output and exact The synchronous transition kernel used by HERMES is [3] snapshot constraints of this latter setting. Probabilistic inverse graph diffusion. DDMSL applies dispt,u (S) = qt,u 1[yt,u = S], crete denoising diffusion to source localization and propagationR pt,u (I) = (1 − β )at,u , path recovery [8]. GDFSL introduces a self-supervised reverse pt,u (R) = β R at,u + 1[yt,u = R]. (2) process that learns across propagation dynamics without State R is absorbing, and the composed update permits a newly labeled source histories [9], while SourceDetMamba integrates infected vertex to recover within the same discrete interval. temporal hypergraph snapshots with a graph-aware state-space model [10]. Conformal source detection provides finite-sample With β = (β I , β R ), the history probability factorizes as recall guarantees for single and multiple sources independently TY −1 Y of the propagation law [11]. These methods improve source Pr(Y) = Pr(y0 ) pt,u (yt+1,u ). (3) or path inference but do not enforce a complete SI/SIR state β t=0 u∈V tensor consistent with multiple observed snapshots. A feasible history has positive probability under (3). The SI Spatiotemporal imputation. BRITS performs bidirectional model is the special case β R = 0 with state space {S, I}; recurrent imputation [12]; GRIN and SPIN incorporate graph infection is then absorbing. Although each vertex evolves structure into multivariate and sparsely observed time-series monotonically, the number of infected vertices in SIR can reconstruction [13], [14]. These are general imputers, whereas decrease as recovery accumulates. Fig. 1 shows the SIR state diffusion reconstruction requires SI/SIR feasibility and exact transitions. agreement with observed snapshots. High-performance graph computation. Ligra and Gunrock B. History Reconstruction demonstrate the importance of frontier organization, sparse Let Tobs = {t1 < · · · < tK } ⊆ T contain the observed times data layout, and architecture-specific parallelism for graph and let Yobs = {yt : t ∈ Tobs }. The final time need not be workloads [15], [16]. Diffusion reconstruction differs from observed. Given G, T , Yobs , the diffusion family, and a prior on conventional traversal because it combines repeated temporal the initial number of infected vertices, the objective is to recover propagation with Θ(T n) history state. The resulting workload b The ideal reconstruction has nonzero probability under the is dominated by repeated adjacency scans and large temporal Y. bt = yt for every t ∈ state storage, motivating an explicit GPU scalability evaluation. assumed diffusion process and satisfies y Tobs [4], [3]. HERMES explicitly enforces graph-reachability constraints. Battus instead guarantees the irreversible state order IV. M ETHODOLOGY and exact observation agreement but does not test graph-causal A. Full-Suite Simplification Workflow reachability after deterministic decoding; we therefore describe The simplification workflow holds the datasets, observations, its output as observation-consistent rather than fully feasibilitycertified. Following the HERMES benchmark, the ground-truth seed, and scoring rules fixed while removing or replacing one initial infected count n0 is supplied, while the identities of computational stage at a time. Every candidate is evaluated on all 12 canonical datasets. A candidate that fails the aggregate those vertices and the diffusion parameters are unknown. Fig. 2 illustrates the inverse problem on an eight-vertex quality gate is recorded as an ablation and rejected; one that graph over six steps: only t = 3 and t = 5 are supplied, passes becomes the reference for the next subtraction. The while every other state, including the terminal state, must accepted configuration is then implemented in CUDA and be reconstructed. Representing the complete output requires evaluated through the same gate. The first subtraction replaces HERMES’s learned proposal Θ(T n) space, and repeated neighborhood propagation requires and sampling stages with deterministic inference, producing Θ(T (m + n)) work. Battus. Removing rate fitting then produces Battus-Z. OrthogIII. R ELATED W ORK onal trials remove the backward pass, snapshot resets, and History and path reconstruction. Source localization anchor projection, or exchange MAP and threshold decoding. estimates initial spreaders, path reconstruction estimates trans- These trials separate inference, parameter estimation, and output mission structure, and history reconstruction assigns a state calibration instead of changing them simultaneously. to every vertex and time. Diffusion archaeology infers proBattus replaces learned proposals and sampling with detergressions from partial timestamps [5]. CulT instead recovers ministic inference over per-vertex state probabilities. Its stages βI

βR

inverse input complete history

t=1

t=2

S S

? ?

I S

S ?

S ? ?

unobserved

t=3 I I I ?

S I I

unobserved

t=4

I ? ?

observed

Susceptible

I S

t=5

Recovered

I R R

unobserved

Infected

R ?

t=6 R R R R

observed

R R R

? ?

unobserved

Unobserved

Fig. 2. Six-step SIR history on an eight-vertex contact graph and the corresponding inverse input. Only t = 3 and t = 5 are observed; t = 6 is a valid unobserved terminal state. Each vertex is labeled by its state, and question marks denote unavailable states.

are rate fitting, mean-field propagation, segment-wise forward– backward smoothing, and monotone decoding. Battus-Z removes fitting and fixes the diffusion rates. The implementation uses compressed sparse row (CSR) graph storage. B. Mean-Field Propagation x Let ft,u approximate Pr(yt,u = x) for state x ∈ {S, I, R}. Given infection and recovery rates β I and β R , the probability that vertex u receives no infection at step t is approximated by Y I ρt,u = (1 − β I ft,v ). (4) v∈N (u) I S Writing kt,u = ft,u + ft,u (1 − ρt,u ), the synchronous update is S S ft+1,u = ft,u ρt,u , I ft+1,u = kt,u (1 − β R ), R R ft+1,u = ft,u + kt,u β R .

(5)

I The initial marginal is shared across vertices, with f0,u = S R n0 /n, f0,u = 1 − n0 /n, and f0,u = 0, where n0 follows the

benchmark convention in Section V. Each update scans every CSR adjacency once and therefore costs O(m + n). C. Derivative-Free Rate Fitting Battus fits β by maximizing the segmented mean-field pseudolikelihood K

L(β) =

1 XX ytk ,u log ftk ,u . Kn

(6)

Battus-Z instead sets β I = 0.1 and, for SIR, β R = 0.1. It executes one continuous mean-field recursion without resetting at intermediate snapshots to obtain the frozen neighbor pressures. This removes all parameter-search passes; the separate per-segment forward and backward messages below remain anchored at the observations. D. Dual-Anchor Forward–Backward Smoothing For every observed interval [tl , tr ], Battus treats the meanfield infection probabilities in (4) as frozen neighbor fields. This yields a time-inhomogeneous three-state Markov chain for each vertex. The forward message αj,u is initialized by the observed state at tl , or by the initial prior for the first interval, and propagated with the local transition matrix Pj,u induced by Eq. (5). The backward message δ j,u is initialized as a one-hot vector at the observed right endpoint. Its recursion is X δj,u (x) = Pj,u (x, x′ )δj+1,u (x′ ). (7) x′ ∈X

The smoothed posterior is x x αj,u δj,u z z . z∈X αj,u δj,u

γtxl +j,u = P

(8)

Each segment uses both observed endpoints without a learned proposal or sampling. Computing the frozen pressures and messages costs O((tr − tl )(m + n)); across all segments, inference is O(T (m + n)) and stores O(T n) posterior values. Segment-local messages use offset j, whereas the output in (8) uses absolute time tl + j.

k=1 u∈V

After scoring an observed endpoint, the propagation state is reset to that snapshot before the next segment. SI fixes β R = 0 and searches one dimension; SIR searches both rates. A coarse uniform grid over [10−4 , 0.5] is followed by four shrinking refinement rounds around the best point. This bounded search removes autograd and optimizer state. One objective evaluation is O(T (m + n)); the configured grid budget is independent of graph size.

E. Deterministic Decoding Two decoders convert γ into infection and recovery hitting x times. MAP selects arg maxx γt,u at every frame and applies a cumulative maximum in the irreversible order S < I < R. S Threshold decoding selects the first t satisfying 1 − γt,u ≥τ R as infection time and, for SIR, the first t satisfying γt,u ≥ τ as recovery time. The reported Battus-Z configuration uses τ = 0.65; Table VI shows this threshold lies on a broad

quality plateau. Finally, the two boundaries are projected to agree exactly with every observed snapshot, and the terminal frame is pinned before scoring. This projection is a defensive consistency operation: its ablation has no numerical effect on the evaluated suite because the endpoint-conditioned posterior already respects the anchors. Neither monotone decoding nor projection checks that every decoded infection has an infected neighbor at the preceding frame. Decoding is O(T n) and deterministic. F. CUDA Implementation The CUDA 12 implementation keeps CSR topology, observations, mean-field fields, and posterior arrays resident on the device. Destination-oriented kernels scan incoming CSR adjacency to compute infection pressure, while vertex-parallel kernels update forward and backward messages and decode the final histories. Kernels use 256-thread blocks and assign one thread to each destination vertex. Time steps remain sequential because frame t + 1 depends on frame t, but all vertices within a step execute in parallel. The state arrays are double buffered: a kernel reads the current S/I/R fields, computes the adjacency product and local transition, writes the next fields, and stores the time-major history. This avoids races between a vertex update and neighboring reads; the time-major layout also makes writes by consecutive threads contiguous. The fitted implementation exposes a second level of parallelism across rate candidates. A coarse SIR round evaluates the 24 × 24 grid as one batched device pass; SI uses 24 infection-rate candidates because recovery is fixed to zero. Four refinement rounds evaluate 7 × 7 SIR or 7 SI candidates. Their state layout is vertex–candidate, so a pressure kernel traverses the same CSR row for each candidate, and likelihood kernels accumulate one scalar per candidate. Grid generation, argmax selection, and bound refinement remain on the device. Battus-Z omits these batched fitting buffers and begins directly with the fixed-rate forward pass. Forward and forward–backward states use single precision by default, while the fitting likelihood and rate candidates use double precision. Each smoothing segment allocates contiguous forward-message α and backward-message δ arrays. At each local time step, one thread is assigned to each vertex in the forward and backward passes, and normalized posteriors are written at the corresponding absolute time offset. The decoder then assigns one thread per vertex to scan its posterior trajectory, apply MAP or threshold crossing, project the observed anchors, and emit byte-valued states. Device memory is therefore O(m+ T n), dominated by the CSR structure, three forward histories, three posterior histories, and the largest segment’s messages. Graph allocation and upload occur before the reported algorithm interval; only the final decoded history is returned to the host. V. E XPERIMENTAL S ETTINGS A. Benchmark and Observation Protocol The evaluation contains the 12-dataset HERMES suite and eight additional large-graph histories, for 20 datasets in total (Table I). The canonical suite evaluates synthetic SI and SIR

TABLE I DATASET STATISTICS , MATCHING TABLE 3 OF HERMES [3]. SI/SIR DENOTES TWO HISTORIES . Dataset

|E| T Graph Diffusion

Canonical HERMES suite (12 datasets) BA–SI/SIR 1,000 3,984 10 Synth. Synth. ER–SI/SIR 1,000 3,987 10 Synth. Synth. Oregon2–SI/SIR 11,461 32,730 15 Real Synth. Prost–SI/SIR 15,810 38,540 15 Real Synth. BrFarmers–SI 82 230 16 Real Real SI Pol–SI 18,470 48,053 40 Real Real SI Covid–SIR 344 2,044 10 Real Real SIR Hebrew–SIR 3,521 18,064 9 Real Real SIR Large-graph extension (8 datasets) Web-Stanford–SI/SIR 255,265 2,234,572 40 Real Web-Google–SI/SIR 855,802 5,066,842 40 Real Orkut–SI/SIR 3,072,441 117,185,083 40 Real LiveJournal–SI/SIR 4,843,953 68,466,754 40 Real

Synth. Synth. Synth. Synth.

TABLE II S YSTEMATIC SIMPLIFICATION ABLATIONS ON ALL 12 CANONICAL DATASETS . B OLD MARKS THE BEST VALUE IN EACH METRIC COLUMN ; TIES ARE RETAINED . Configuration

F1 NRMSE Gate

Battus: fit, reset, FB, MAP replace MAP with crossing additionally remove reset additionally remove fit (Battus-Z)

.8730 .8730 .8729 .8726

.1342 .1003 .1003 .1010

Battus-Z without backward pass Battus-Z with MAP decoding Battus-Z without projection

.8171 .8653 .8726

.1540 Fail .1152 Fail .1010 Pass

Pass Pass Pass Pass

histories on BA, ER, Oregon2, and Prost; BrFarmers and Pol contain real SI-like diffusion, and Covid and Hebrew contain real SIR-like diffusion [3]. Both Battus variants are evaluated on the large histories; HERMES is not reported at this scale. Large-scale experiments test scalability, while small synthetic experiments test robustness to diffusion-rate mismatch. Every run observes Tobs = {⌊T /2⌋, T } and uses seed 123456789; the final frame is inserted automatically. Table I reports arcs for directed graphs and edges otherwise; undirected inputs are symmetrized. Large histories use β I = 0.1, β R = 0.1 for SIR, 100 initial infections, and synchronous simulation. Sixteen further robustness runs resimulate the canonical BA and ER topologies (T = 10, 50 initial infections) at (β I , β R ) ∈ {(.05, .05), (.1, .2), (.2, .05)} plus a same-generator (.1, .1) reference, evaluated only with Battus-Z at its fixed rates (Table VII). Recovery rates are immaterial for SI, so its (.1, .2) run duplicates the effective generation setting of the reference and is retained only to display the complete requested pair set. The CUDA implementation consumes the same canonical text exports as the quality study. B. Design Sequence and Quality Gates Table II records the successive-removal experiment. Every row preserves the observation and scoring protocol; the changed factor is accepted or rejected using the full 12-dataset suite rather than a selected dataset. A candidate passes the benchmark-specific aggregate gate when its mean macro-F1 is at least the published HERMES mean of 0.8692 and its mean

TABLE III C ANONICAL RECONSTRUCTION QUALITY. BASELINES REPRODUCE HERMES TABLE 2 [3]; BATTUS ROWS ARE ARTIFACT MEASUREMENTS . AVERAGE RANK SPANS 12 METRIC COLUMNS PER PANEL , WITH MEAN RANKS FOR TIES . SPIN’ S OOM RECEIVES WORST RANK AND IS EXCLUDED FROM ITS SI METRIC MEANS . B OLD MARKS THE BEST VALUE IN EACH COLUMN AND SUMMARY.

Method

BA–SI F1 NRMSE

ER–SI F1 NRMSE

Oregon2–SI F1 NRMSE

Prost–SI BrFarmers–SI F1 NRMSE F1 NRMSE

Pol–SI Six-dataset average F1 NRMSE F1 NRMSE Rank

GCN .8602 GIN .8422 BRITS .5932 GRIN .8939 SPIN .8917 DHREC .7406 CRI .7686 DITTO .8384 HERMES .9012

.2085 .8469 .2188 .8416 .2237 .6135 .1541 .8993 .1377 .8996 .2353 .7537 .2622 .8019 .2139 .8269 .1284 .9011

.2131 .7811 .2104 .7634 .2233 .5579 .1323 .8784 .1291 .8941 .2245 .5686 .2256 .7953 .2225 .8280 .1269 .8964

.3172 .8134 .3106 .8451 .4818 .5616 .1578 .6732 .1328 .7157 .2612 .8204 .2409 .8523 .2289 .8327 .1380 .9056

.2626 .8512 .2226 .7659 .5197 .5617 .4147 .9043 .3751 .8967 .2299 .6366 .1984 .7523 .2317 .8206 .1308 .8980

.1709 .6847 .3572 7.42 .8063 .2652 .7648 .2878 7.25 .8038 .2181 .5127 .4707 10.25 .5668 .1268 .8477 .1752 5.08 .8495 .1315 OOM 6.00 .8596 .2766 .8176 .2096 8.67 .7229 .2681 .8465 .1958 7.58 .8028 .2142 .7471 .2903 7.17 .8156 .1491 .8487 .1823 2.88 .8918

.2549 .2526 .3562 .1935 .1812 .2395 .2318 .2336 .1426

Battus Battus-Z

.0950 .9011 .0937 .9002

.0921 .8884 .0963 .8953

.0971 .9000 .0947 .9015

.0933 .9071 .0950 .9016

.0853 .8807 .0921 .8781

.0935 .0957

Method

.8967 .9014

BA–SIR F1 NRMSE

ER–SIR Oregon2–SIR F1 NRMSE F1 NRMSE

Prost–SIR F1 NRMSE

Covid–SIR F1 NRMSE

.0981 .1026

1.79 .8957 1.92 .8963

Hebrew–SIR Six-dataset average F1 NRMSE Rank F1 NRMSE

GCN .6890 GIN .6435 BRITS .5660 GRIN .8633 SPIN .7458 DHREC .7493 CRI .6417 DITTO .7783 HERMES .8640

.1905 .6754 .2134 .6428 .2191 .5817 .0981 .8631 .1137 .7400 .2511 .7610 .2537 .6594 .1633 .7734 .1509 .8657

.1769 .5994 .2046 .5443 .2118 .3483 .0962 .8706 .1471 .6857 .2349 .7631 .2297 .5993 .1679 .7928 .1307 .8719

.2466 .6091 .2844 .5974 .6243 .3528 .1034 .6079 .1225 .5796 .2695 .7822 .2834 .6240 .1707 .7929 .1874 .8609

.2180 .6008 .2378 .5660 .6156 .4751 .2785 .7635 .2619 .7656 .2653 .6794 .2635 .5171 .1690 .6240 .1737 .7819

.3226 .5805 .2831 .5960 .3485 .4297 .1647 .5582 .2480 .5582 .4226 .7718 .4991 .7258 .2637 .6411 .1589 .8356

.2263 7.33 .6257 .2909 8.42 .5983 .5518 10.42 .4589 .1653 4.75 .7544 .1653 6.08 .6792 .1501 7.17 .7511 .1466 8.50 .6279 .2983 5.58 .7338 .1223 2.92 .8467

.2301 .2524 .4285 .1510 .1764 .2656 .2793 .2055 .1540

Battus Battus-Z

.1612 .8644 .0969 .8675

.1664 .8673 .0957 .8702

.1051 .8740 .1027 .8709

.0996 .7945 .1023 .7801

.4036 .8450 .1334 .8375

.1134 .1070

3.25 .8503 1.58 .8488

.1749 .1063

.8567 .8666

NRMSE is no greater than the published mean of 0.1483. This development criterion is not a statistical-equivalence test or a claim of generalization beyond the suite. The first four rows follow the subtraction sequence; the final three isolate components of Battus-Z. C. Quality and Performance Measures

a direct S → R jump. Every onset after frame zero is an event, and it is a violation when no directed predecessor is infected one frame earlier: P ⊮[∄(u, v) ∈ E : Hav −1,u = I] CV(H) = v:av >0 . (10) |{v : av > 0}|

Initial infections are exogenous and excluded. We report CV Hitting time is the first frame in which a state occurs; absence for both prediction and truth because real histories can violate uses sentinel T + 1. Macro-F1 is computed after flattening the the supplied graph or the assumed synchronous process. The node-major history and averages only classes present in truth or canonical and ablation quality rows are deterministic artifact prediction. The final prediction is pinned to the observed final measurements on fixed exports. CUDA measurements record frame before scoring. The likelihood prior uses the ground- one invocation per method and dataset on an NVIDIA B200. truth number of infections at t = 0, following the benchmark The reported interval contains fitting for Battus only, forward– implementation. With per-vertex infection and recovery hitting backward inference, and decoding after initialization and graph upload; loading, CSR construction, transfer, and scoring times hIu and hR u , the normalized error is r are excluded. The timing results are descriptive scalability 1 MSE(hI ) + MSE(hR ) NRMSE = . (9) measurements rather than repeated statistical performance T +1 2 measurements. The full source code is available at https: For SI, the scorer sets the recovery-error term to zero and //github.com/ggokturk/battus. retains the same factor of 1/2 and T + 1 normalization. VI. E VALUATION We call these the HERMES-compatible scores. They include the observed midpoint and the pinned terminal frame. The A. Canonical HERMES Benchmark unobserved-only scores remove every t ∈ Tobs from truth and Table III applies the quality gate to the two retained methods. prediction before evaluation. F1 is flattened over the remaining It extends Table 2 of HERMES [3]; published baseline values entries. For NRMSE, each hitting time is the first remaining are retained without rerunning the retired suite, while the occurrence on the original time axis; absence, normalization, final rows are Battus artifact measurements under the same and class averaging remain unchanged. This excludes observa- two-snapshot and metric conventions. Both variants pass the tion copying and retains the benchmark’s temporal scale. We aggregate gate. Battus-Z obtains the lowest NRMSE on all 12 additionally measure graph-causal feasibility. For a history H, datasets, while the Battus family obtains the highest or tied let av = min{t : Ht,v ̸= S} be the infection onset, including macro-F1 on nine. Thus, learning, sampling, and fitting can

TABLE IV M EAN CANONICAL QUALITY WITH AND WITHOUT OBSERVED FRAMES . HERMES- COMPATIBLE SCORES USE THE PUBLISHED PROTOCOL ; UNOBSERVED - ONLY SCORES MASK {⌊T /2⌋, T }. B OLD MARKS THE BEST VALUE IN EACH COLUMN .

B. Causal Feasibility and Rate Sensitivity

Panel A of Table V reports graph-causal violations in addition to F1 and NRMSE. Synthetic ground truth has no violations, while event-weighted Battus-Z rates are 7.50% for SI and 8.77% for SIR. Covid–SIR is the largest model-side HERMES-compatible Unobserved-only failure at 40.35% for Battus-Z; fitted Battus reaches 67.54%. Method F1 NRMSE F1 NRMSE In the Hebrew truth, 40.65% of events violate the supplied Battus .8730 .1342 .8440 .1476 graph and synchronous model, so a method can be more Battus-Z .8726 .1010 .8431 .1181 graph-consistent than the observed history without being more accurate. Battus is observation-consistent but not feasibilitycertified. A reachability constraint is left for future decoding be removed while retaining the published aggregate quality on work. this suite and scoring protocol. The comparison remains crossPanel B tests the fixed-rate choice on synthetic BA–SIR, implementation and does not establish statistical equivalence. synthetic diffusion on the real Prost topology, and real Covid– Table IV addresses a weakness of that protocol: both SIR. Across all nine combinations, F1 ranges are .8388–.8666, observed frames contribute to F1, and the terminal prediction .8638–.8709, and .7569–.7873, respectively. The default (.1, .1) is pinned before scoring. Removing those frames lowers mean pair gives the best three-dataset mean F1 (.8392) and NRMSE F1 by 0.0290 for Battus and 0.0295 for Battus-Z; NRMSE (.1109), although (.1, .2) is better on Covid. The default is increases by 0.0134 and 0.0171, respectively. The fixed-rate competitive in this small neighborhood, but the real history method still reconstructs the latent frames with mean F1 rules out a claim of universal parameter insensitivity. 0.8431 and NRMSE 0.1181. These masked values cannot be Table VI isolates the remaining fixed choice: it sweeps only compared directly with the published HERMES aggregate the decode threshold for Battus-Z on all twelve datasets, with because predicted histories are available for only six of its rates, snapshots, and seed held fixed. For τ ≤ 0.65, mean F1 twelve datasets; the table is a within-method diagnostic, not a varies by less than 0.006 and mean NRMSE by less than 0.004, new equivalence claim. and per-dataset F1 stays within 0.012 of its τ = 0.65 value on Decoder choice affects temporal calibration more strongly [0.55, 0.65]; quality then degrades monotonically, with Hebrew– than framewise accuracy. Fitted Battus with MAP decoding, SIR falling from .8375 to .7801 at τ = 0.70. Per-dataset optima for example, obtains F1 0.7945 on Covid–SIR but NRMSE scatter across the grid, so τ = 0.65 is a central point of a broad 0.4036. Threshold crossing reduces the corresponding fixed-rate plateau rather than a tuned optimum; the fitted variant behaves NRMSE to 0.1334 while retaining F1 0.7801. We therefore use alike and is reported with MAP decoding, so no reported threshold crossing in Battus-Z instead of selecting the decoder number depends on the threshold there. by macro-F1 alone. Panel B varies the inference rates on histories generated TABLE V C ANONICAL CAUSAL FEASIBILITY AND BATTUS -Z RATE SENSITIVITY. PANEL A REPORTS THE PERCENTAGE OF NONINITIAL INFECTION ONSETS WITHOUT AN INCOMING NEIGHBOR INFECTED AT THE PRECEDING FRAME ; BOLD MARKS THE BETTER RECONSTRUCTION METHOD . T RUTH IS INCLUDED BECAUSE REAL OBSERVATIONS NEED NOT BE FEASIBLE UNDER THE SUPPLIED GRAPH . PANEL B REPORTS THE COMPLETE 3 × 3 GRID ON THREE REPRESENTATIVE SIR DATASETS ; BOLD METRIC ENTRIES MARK THE BEST VALUE FOR EACH DATASET, WHILE THE BOLD RATE PAIR IDENTIFIES THE REPORTED DEFAULT. Panel A: causal-violation rate (%) SI dataset Truth Battus Battus-Z

SIR dataset

Truth

Battus

Battus-Z

BA ER Oregon2 Prost BrFarmers Pol

0.00 0.00 0.00 0.00 18.92 3.51

1.28 22.59 6.43 7.02 21.33 9.15

1.50 40.13 4.91 5.38 20.00 9.19

BA ER Oregon2 Prost Covid Hebrew

0.00 0.00 0.00 0.00 3.42 40.65

2.40 28.42 6.88 8.44 67.54 6.54

5.14 25.54 5.72 9.62 40.35 6.79

Event-weighted

1.36

7.97

7.50

Event-weighted

2.97

9.00

8.77

Panel B: Battus-Z sensitivity; each cell pair is F1 and NRMSE βI

.05 .05 .05 .10 .10 .10 .20 .20 .20

βR

.05 .10 .20 .05 .10 .20 .05 .10 .20

BA–SIR

Prost–SIR

Covid–SIR

NRMSE

.8462 .8533 .8520 .8558 .8666 .8588 .8388 .8528 .8586

.1091 .1077 .1088 .1017 .0969 .1030 .1191 .1107 .1031

.8700 .8688 .8667 .8707 .8709 .8707 .8638 .8647 .8667

.1038 .1060 .1110 .1018 .1023 .1073 .1080 .1071 .1082

.7772 .7820 .7831 .7727 .7801 .7873 .7569 .7640 .7824

.1389 .1341 .1350 .1436 .1334 .1276 .1552 .1477 .1319

TABLE VI BATTUS -Z DECODE - THRESHOLD SENSITIVITY ( ARTIFACT MEASUREMENTS ; FIXED RATES (.1, .1), TWO - SNAPSHOT PROTOCOL , SEED 123456789). B OLD MARKS THE BEST VALUE IN EACH ROW; THE REPORTED τ = 0.65 REPRODUCES THE BATTUS -Z ROWS OF TABLE III EXACTLY.

Panel A: macro-F1 Dataset .50

.55

.60

.65

.70

.75

.80

BA–SI .8924 .8969 .9000 .9014 .9017 .9024 .8948 ER–SI .8906 .8954 .8988 .9002 .9022 .8989 .8931 Oregon2–SI .8811 .8891 .8928 .8953 .8952 .8926 .8861 Prost–SI .8956 .8990 .9012 .9015 .9006 .8964 .8917 BrFarmers–SI .8870 .8901 .8939 .9016 .9062 .9061 .9010 Pol–SI .8701 .8736 .8766 .8781 .8772 .8740 .8671 BA–SIR .8602 .8635 .8661 .8666 .8557 .8430 .8279 ER–SIR .8651 .8668 .8680 .8675 .8508 .8398 .8260 Oregon2–SIR .8674 .8712 .8728 .8702 .8663 .8544 .8466 Prost–SIR .8737 .8748 .8751 .8709 .8658 .8531 .8451 Covid–SIR .7833 .7820 .7797 .7801 .7770 .7771 .7425 Hebrew–SIR .8362 .8361 .8374 .8375 .7801 .7750 .7709 Mean

.8669 .8699 .8719 .8726 .8649 .8594 .8494

Panel B: NRMSE Dataset .50

.55

.60

.65

.70

.75

.80

BA–SI .0981 .0970 .0954 .0937 .0934 .0941 .1024 ER–SI .1027 .1000 .0975 .0963 .0948 .0991 .1059 Oregon2–SI .1019 .0969 .0951 .0947 .0966 .1015 .1092 Prost–SI .0967 .0944 .0939 .0950 .0972 .1039 .1098 BrFarmers–SI .0992 .0975 .0947 .0921 .0913 .0935 .0971 Pol–SI .1088 .1056 .1032 .1026 .1035 .1064 .1125 BA–SIR .1030 .0999 .0971 .0969 .1034 .1135 .1218 ER–SIR .1007 .0990 .0965 .0957 .1024 .1134 .1197 Oregon2–SIR .1047 .1027 .1019 .1027 .1087 .1158 .1253 Prost–SIR .0993 .0991 .0999 .1023 .1091 .1169 .1256 Covid–SIR .1346 .1356 .1356 .1334 .1375 .1390 .1662 Hebrew–SIR .1037 .1056 .1063 .1070 .1201 .1214 .1223 Mean

.1045 .1028 .1014 .1010 .1048 .1099 .1181

TABLE VII G ENERATION - SIDE RATE MISSPECIFICATION : BATTUS -Z KEEPS (.1, .1) WHILE THE CANONICAL BA/ER TOPOLOGIES ARE RESIMULATED WITH THE ALTERNATIVE PAIRS ( SAME GENERATOR AS THE LARGE HISTORIES ). C ELLS ARE F1/NRMSE; BOLD INDEPENDENTLY MARKS THE HIGHEST F1 AND LOWEST NRMSE IN EACH COLUMN , INCLUDING TIES . T HE (.1, .1) ROW IS THE SAME - GENERATOR REFERENCE (SI IGNORES β R ).

Gen. (β I , β R ) .10/.10 (ref) .05/.05 .10/.20 .20/.05

BA–SI

BA–SIR

ER–SI

ER–SIR

.9053/.0926 .9078/.0923 .9053/.0926 .8894/.0954

.8714/.1020 .8820/.0896 .8561/.1019 .8720/.1056

.8981/.0993 .8933/.1002 .8981/.0993 .8781/.1044

.8665/.1024 .8789/.0897 .8457/.1030 .8641/.1117

TABLE VIII S INGLE - RUN CUDA IMPLEMENTATION RESULTS ON AN NVIDIA B200 AFTER INITIALIZATION . T IME IS THE FIT– INFERENCE – DECODE INTERVAL ; QUALITY MEANS ARE ARITHMETIC AND TIME MEANS GEOMETRIC . B OLD MARKS THE BEST VALUE WITHIN EACH GRAPH / MODEL OR MEAN PAIR . Graph

Model Method

F1 NRMSE Time (ms)

Web-Stanford SI SI SIR SIR Web-Google SI SI SIR SIR Orkut SI SI SIR SIR LiveJournal SI SI SIR SIR

Battus Battus-Z Battus Battus-Z Battus Battus-Z Battus Battus-Z Battus Battus-Z Battus Battus-Z Battus Battus-Z Battus Battus-Z

.9075 .8919 .8007 .8140 .8811 .8655 .7601 .7820 .9230 .9344 .8625 .8715 .9132 .9145 .8479 .8547

.0815 .1018 .1471 .0733 .0852 .1038 .1175 .0801 .0282 .0254 .0857 .0793 .0869 .0863 .1048 .0941

121 15 227 16 148 36 695 36 1560 368 9119 390 1288 262 4793 186

Mean

Battus Battus-Z Battus Battus-Z

.9062 .9016 .8178 .8306

.0705 .0793 .1138 .0817

436 85 1621 80

SI SI SIR SIR

histories. On the same CUDA backend and hardware, removing fitting reduces the geometric-mean algorithm interval from 436 to 85 ms for SI (5.1×) and from 1621 to 80 ms for with the default pair. Table VII tests the opposite direction. SIR (20.3×). These are same-implementation Battus-versusIt resimulates the 1,000-vertex BA and ER topologies with Battus-Z comparisons, not speedups over HERMES. The labels (.05, .05), (.1, .2), and (.2, .05) while Battus-Z keeps (.1, .1). support quality measurement but do not turn the underlying Across the twelve alternative-rate evaluations, macro-F1 stays SNAP topologies into observed real diffusion histories. These within .021 and NRMSE within .013 of the matched same- histories are simulated with the same (.1, .1) pair that Battus-Z generator reference (mean F1 .8809 versus .8853; mean fixes; Table VII provides only a small-graph check against NRMSE .0988 versus .0991). The largest F1 loss is on ER–SIR generation-rate mismatch. at (.1, .2), while the largest NRMSE increase is on ER–SIR VII. C ONCLUSION at (.2, .05). In this fixed-seed small-graph check, matching the generation and inference rates does not account for the reported The full-suite ablation reduces HERMES’s fitted, learned, Battus-Z quality. and sampled pipeline to deterministic forward–backward inference while retaining its published aggregate quality on the C. Large-Graph Extension evaluated benchmark and scoring protocol. Removing backward After the canonical quality gate, the eight additional histories smoothing or threshold decoding fails the quality gate; fitting, test whether both Battus variants execute beyond the reference forward resets, and projection can be removed without changing suite. Table VIII reports the single-run B200 scalability the aggregate gate outcome. With observed frames excluded, evaluation. The zero-fit variant has slightly higher mean F1 and Battus-Z obtains mean F1 0.8431 and NRMSE 0.1181 on lower mean NRMSE than the fitted variant on these generated latent frames. BA/ER histories generated at three off-default

rate pairs remain within .021 macro-F1 and .013 NRMSE of the matched reference. Its event-weighted causal-violation rates are 7.50% for SI and 8.77% for SIR. The results should be interpreted within the HERMES benchmark protocol. The canonical comparison uses the benchmark’s ground-truth initial infection count n0 , and published HERMES scores are cross-implementation references rather than rerun baselines. CUDA timings are single-run algorithm-interval measurements on one B200 and support scalability and samebackend Battus/Battus-Z comparisons, not a speedup claim over HERMES. The large SNAP histories are synthetic and use the Battus-Z default diffusion rates; the rate-mismatch experiment provides only a small-graph robustness check. Finally, Battus-Z enforces observation consistency and irreversible state order but does not certify graph-causal reachability. A full-suite masked comparison with HERMES requires its six remaining predicted histories. R EFERENCES [1] R. Pastor-Satorras, C. Castellano, P. V. Mieghem, and A. Vespignani, “Epidemic processes in complex networks,” Reviews of Modern Physics, vol. 87, no. 3, pp. 925–979, 2015. [2] F. Zhou, X. Xu, G. Trajcevski, and K. Zhang, “A survey of information cascade analysis: Models, predictions, and recent advances,” ACM Computing Surveys, vol. 54, no. 2, 2021. [3] Y. Zuo, R. Qiu, L. Chen, and H. Tong, “Graph diffusion history reconstruction via feasibility-aware markov chain monte carlo estimation,” in Proceedings of the 32nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2026. [4] R. Qiu, D. Wang, L. Ying, H. V. Poor, Y. Zhang, and H. Tong, “Reconstructing graph diffusion history from a single snapshot,” in Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2023, pp. 1978–1988. [5] E. Sefer and C. Kingsford, “Diffusion archaeology for diffusion progression history reconstruction,” Knowledge and Information Systems, vol. 49, no. 2, pp. 403–427, 2016. [6] P. Rozenshtein, A. Gionis, B. A. Prakash, and J. Vreeken, “Reconstructing an epidemic over time,” in Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2016, pp. 1835–1844. [7] J. Xie, C. Lin, X. Guo, and C. S. Mitchell, “Source robust non-parametric reconstruction of epidemic-like event-based network diffusion processes under online data,” Big Data and Cognitive Computing, vol. 9, no. 10, p. 262, 2025. [8] X. Yan, H. Fang, and Q. He, “Diffusion model for graph inverse problems: Towards effective source localization on complex networks,” in Advances in Neural Information Processing Systems, vol. 36, 2023. [9] D. Hou, Y. Wang, C. Gao, and X. Li, “A generalized diffusion framework with learnable propagation dynamics for source localization,” in Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, 2025, pp. 2919–2927. [10] L. Cheng, P. Zhu, Y. Guo, C. Gao, Z. Wang, and K. Tang, “SourceDetMamba: A graph-aware state space model for source detection in sequential hypergraphs,” in Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, 2025, pp. 2749–2757. [11] X. Jian, P. Zhang, L. Tian, F. Ji, W. Liang, W. P. Tay, B. Wen, and F. Krahmer, “Conformal prediction for multi-source detection on a network,” in Proceedings of the AAAI Conference on Artificial Intelligence, vol. 40, no. 43, 2026, pp. 36 663–36 670. [12] W. Cao, D. Wang, J. Li, H. Zhou, L. Li, and Y. Li, “BRITS: Bidirectional recurrent imputation for time series,” in Advances in Neural Information Processing Systems, vol. 31, 2018. [13] A. Cini, I. Marisca, and C. Alippi, “Filling the gaps: Multivariate time series imputation by graph neural networks,” in International Conference on Learning Representations, 2022. [14] I. Marisca, A. Cini, and C. Alippi, “Learning to reconstruct missing data from spatiotemporal graphs with sparse observations,” in Advances in Neural Information Processing Systems, vol. 35, 2022, pp. 32 069–32 082.

[15] J. Shun and G. E. Blelloch, “Ligra: A lightweight graph processing framework for shared memory,” in Proceedings of the 18th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, 2013, pp. 135–146. [16] Y. Wang, A. Davidson, Y. Pan, Y. Wu, A. Riffel, and J. D. Owens, “Gunrock: A high-performance graph processing library on the GPU,” in Proceedings of the 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, 2016.

Algorithmic Simplification for Million-Vertex Diffusion History Reconstruction

Analyze & explore related research in Conceptio

Related documents