Scaling Epidemic Inference on Contact Networks: Theory and Algorithms
Authors: Guanghui Min
Yinhan He
Chen Chen
Venue: NeurIPS 2025 poster ()
Keywords: Computational Epidemiology
Graph Theory
Algorithm Acceleration
Primary area: theory

Abstract: Computational epidemiology is crucial in understanding and controlling infectious diseases, as highlighted by large-scale outbreaks such as COVID-19. Given the inherent uncertainty and variability of disease spread, Monte Carlo (MC) simulations are widely used to predict infection peaks, estimate reproduction numbers, and evaluate the impact of non-pharmaceutical interventions (NPIs). While effective, MC-based methods require numerous runs to achieve statistically reliable estimates and variance, which suffer from high computational costs. In this work, we present a unified theoretical framework for analyzing disease spread dynamics on both directed and undirected contact networks, and propose an algorithm, **RAPID**, that significantly improves computational efficiency. Our contributions are threefold. First, we derive an asymptotic variance lower bound for MC estimates and identify the key factors influencing estimation variance. Second, we provide a theoretical analysis of the probabilistic disease spread process using linear approximations and derive the convergence conditions under non-reinfection epidemic models. Finally, we conduct extensive experiments on six real-world datasets, demonstrating our method's effectiveness and robustness in estimating the nodes' final state distribution. Specifically, our proposed method consistently produces accurate estimates aligned with results from a large number of MC simulations, while maintaining a runtime comparable to a single MC simulation. Our code and datasets are available at https://github.com/GuanghuiMin/RAPID.

Scaling Epidemic Inference on Contact Networks: Theory and Algorithms
Yinhan He Chen Chen University of Virginia {jjm8vr, nee7ne, (rh6di))viirgniaa
Guanghui Min
Abstract
Computational epidemiology is erucial in understanding and controlling infectious diseases, highlighted by large-scale outbreaks such 10. Given the in- herent uncertainty and variability of disease spread, Monte Carlo (MC) simulations are widely used to predict infection peaks, estimate reproduction numbers, and evaluate the impact of non-phin soot-haamaceuticll interventions (NPIs). While effective, MC-based methods require numerous runs achieve statistically reliable estimates and variance, which suffer from high computational costs. In this work, we present unified theoretical framework for analyzing disease spread dynamics both directed and undirected contact networks, and propose an algorithm, RAPID, that significantly improves computational efficiency. Our contributions are threefold. First, we derive an asymptotic variance lower bound for MC estimates and identify the key factors influencing estimation variance. Second, provide theoretical analysis of the probabilistic disease spread process using linear approximations and derive the convergence conditions under non-reinfection epidemic models. Finally, we conduct extensive experiments on six real-world datasets, demonstrating our method's s effectiveness and robustness in estimating the nodes' final state distribu- tion. Specifically, our proposed method consistently produces accurate estimates aligned with results from a large number of MC simulations, while maintaining a runtime comparable to a single MC simulation. Our code and datasets are available at hhtttss:////t thub....t..u.... com/ GuwnghuiMin/ RAAPID
Introduction
In recent years, outbreaks of infectious diseases such as COVID-19 have highlighted the critical need for accurate modeling and prediction of disease dynamics [5
8 5 49 Existing epidemic
studies tend to model the disease spread process using differential equations at the population level, and often assume homogeneous populations with random mixing of initial infections within contact networks (27]. Consequently, such work can only provide a rough estimate of the overall dynamics of epidemics, while missing important details about individual- or local-level infection dynamics in the networks. In practice, individual-level infection dynamic inference has important practical implications. For example, individuals with high probability of transmitting the disease can be prioritized for vaccination, thus reducing the overall infected population [22]. In addition,
understanding the results of local infections can provide more accurate projection of the global trajectory of the epidemic. Although some recent studies have enabled advances in understanding the interplay network structure and epidemic spread process, they can only provide an insight about the epidemic at high level by determining whether an outbreak will escalate into a complete pandemic (50) 16 43), while neglecting the impact of distribution of initial cases and offering limited information on the infection states and expected size of the infected population.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Currently, inferring the infectious state of individual nodes in the epidemic network heavily depends on the Monte Carlo (MC) simulations, as they do not rely on assumptions of population homogeneity
or specific distributions of initial infections [60 14 10
I1 21 19 For example, during the COVID-
19 pandemic, MC simulations have been widely employed to predict infection peaks, estimate reproduction numbers, and assess the impact of non- non-pharmaceutical interventions (NPIs) [60] [4]. Due to the simplicity and robustness of MC simulations, they are widely adopted in various related application domains such as information dissemination and cybersecurity, where network-based contagion models play a crucial role [26 47 [57]. However, a non-negligible drawback for MC
simulations is their high computational cost, it requires hundreds or even thousands of runs of
simulations to reach a statistically reliable result due to the inherent uncertainty and variability of the
disease spread process 43]
In this paper, we address the high computational cost of MC simulations for modeling the disease spread process by presenting an efficient framework to estimate the infection dynamics on large networks while ensuring high estimation accuracy on predicting the infection states of individual nodes at convergence. To our knowledge, we are the first to theoretically analyze how the network structure impacts the variance epidemic simulations and provide a linear approximation scheme for nonlinear epidemic dynamics with provable performance guarantees. Our key contributions are as follows:
Theoretical Analysis: We present three key results: (I) we derive the variance lower bound of the Monte Carlo estimator on large contact networks and reveal how the reproduction number, average out-degree, initial infection ratio, and the number of simulations affect the variance; (2) provide linear approximation of the nonlinear epidemic dynamics, clarifying the contribution of neighborhoods to disease spread; and (3) we establish global convergence conditions for probability-basee propagation under non-reinfection epidemic models.
Algorithm and Results: Building on these theoretical insights, we propose RAPID (Residual- A Aware Propagation for Infection Dynamics), local approximation algorithm designed to effi- ciently estimate the node-level state distribution in large networks while preserving interpretability and reliability throughout the computational process. In particular, RAPID consistently produces accurate estimates aligned with results from a large number of MC simulations, while maintaining runtime comparable to single MC simulation.
2 Preliminary
Notations. We denote a general grapt 9 (V,, where is the set of nodes and = | is the number of nodes; & denotes the set of edges, and the edge between nodes v, and v is denoted as Eij (v,, vy); A E {0, N is the adjacency matrix, where Aij = 1 indicates that an edge exists between Uy and fyy, otherwise A, = 0. In this work, we assume a standard SIR (Susceptible- Infected-Reee Recovered) model with constant transmission probability | and recovery probability governs the spread of a virus on this network. All notations and symbols are summarized in Table
Definition 1 (Individual-Leve Epidemic Inference). Given a directed contact network G = - E,E A), epidemic parameters and 7,, and an initial infected node set Ia. the goal of individual-level epidemic inference is to estimate the steady-state (converged) state probability distribution (oo)) = (P?()s), P; (" for each node i V.
This problem fundamentally differs from typical graph-based spatio-temporal prediction tasks, which aim to forecast future node-level observations (such as traffic or sensor signals) based on historical data. In contrast, node-level epidemic inference seeks to estimate the final distribution of susceptible probabilities at convergence with given initial conditions and epidemic parameters, and the contagion process follows the stochastic infection dynamics without relying on past observation sequences.
In this work. the graph or network can be either directed or undirected. Without loss of generality, we derive analysis directed graphs undirected graphs can be considered special case of directed graphs.

---

Table 1: Summary of key notations
Graph
G = (V)
Directed contact network with node V, edge &, and adjaceney matrix A. Number of nodes, [
D
Average out-degree, graph diameter.
NE (E
nn-iobu--eighbors of node i.
Epidemic parameters
7.7 a
Transmission probability. recovery probability in unit time.
Initial infected node set. with fraction a [Zol/N. Edge-level transmission probability, P. = B/(3 + +2).
Pe
State variables
Ps()). P)()), Pk()
Probabilities that node i is susceptible, infected, or recovered at time t. Full state vector of node (L))
(t)
Vectors over all nodes, e.g., Pt(() (t) (t)).
P(t)
Full network state: [P' (t)..... P (t)]" Propagation residual node
(ia(1)
2.1 SIR Dynamics
The classical SIR model describes disease transmission a continuous-time Markov process, governed by the following system of ordinary differential equations (27]
dS
S1 di - N
- N
dl
S1
dR
7/.
(I)
di
di
These nonlinear equations are generally difficult to solve analytically, and the implicit assumption of homogeneous random mixing may not hold in complex contact networks. Notably, the SIR framework serves as a representative example of general non-reinfection epidemic models, where once nodes transition into the recovered (or removed) state, they longer re-enter the infection dynamics 46 28
2.2 Probabilistic Disease Propagation in Neighborhood
Given a directed contact network g =
EV,E, A), epidemic parameters 3 and y, and the full network state P(() at time 4, we model the SIR process non-reinfection system. Specif- ically, for each node i V. the probability of be- ing susceptible at time t + denoted P3 (t++ + 1). is given by its value at time multiplied by the probability of not being infected during the inter- val (t, 1). The probability of being infected at time + 1, (t + 1), consists of two parts: the probability of becoming infected during (t, ++]] I, and the probability
Algorithm 1 Sketch of PID
Require: Graph G, rates (3, y, initial infected set To. threshold
1: Initialize Ps, Pt, PR. t
while P(()) P(t-1)lla >
do
3: for all E V do
4:
Update P(().. (t(t) with Eq.
5:
end for
1+1
7: end while
8: return Ps, PR
while being susceptible of remaining infected by not transitioning to the recovered state. Similarly, the probability of being recovered at + 1, Pa + 1), accounts for nodes that either recovered during (4, 4 1] or remained in the recovered state from the previous time step. Assuming that infection events are independent across neighbors within each unit time interval [43] 25), the resulting update equations correspond to the derivation of the message passing formulation in (24
Pt(++ (t) II Axx - (P)())
(2)
jEV
() + 1)= P)) II A ,0 - (P)(()) + (11 (1))) JEV
1) (t)) PT(((t)
Based on these update equations, we develop baseline inference algorithm, PID (Propagation for Infection Dynamics), as shown in Algorithm
3

---

3 Theoretical Analysis
In this section, we provide a thorough analysis on the impact of network structure and epidemic parameters the variance of variance of Monte Carlo estimators; then derive linear approx- imation of nonlinear epidemic dynamics that highlights neighborhood propagation, and establish convergence guarantees for probability-based propagation in non-reinfection models.
3.1 Monte Carlo Estimator Variance Analysis
In many existing epidemic dynamic studies, Monte Carlo simulations are often repeated 104-103 times without examining their necessity or computational trade-offs. In this subsection, we aim to theoretically investigate this important question: under what conditions does the variance of the steady-star state infection probability across the network become large when performing Monte Carlo simulations of epidemic dynamics, such that more simulation runs needed to achieve sufficient accuracy? To the best of our knowledge, this question has never been explored in prior work. Addressing this overlooked gap not only offers practical guidance for real-world simulation tasks but also motivates our development of scalable methods for epidemic inference.
Theorem 3.1 (Monte Carlo Estimation Variance Lower Bound). Given a directed contact network G = EV) with N = [V,, average out-degree k. and diameter D. Let To S V be the initially infected node set with fraction a == [Zo//N. Assume an SIR model parameterized by infection probability and recovery probability n. Using M independent Monte Carlo simulations to estimate each node 's infection probability Ps. the average variance of the estimator Pr satisfies:
Varlś: -pe) 2 2M
min(1 poo) pokcka ,1 ckkr
N
where
3 3 1 (:= min
log N
Po = (
log K }
(4)
and is a constant depending on the network structure.
Proof. We briefly outline the key argument here: the full derivation is in the Appendix. Each node's infection probability pt is estimated via Monte Carlo simulation as
M
p.
(m)
(5)
M
0==1
where 1((²) indicates infection in simulation m. Its variance is straightforwardly given by Varlø.] =
p.(1 p.M Under the continuous-time SIR model, the transmission probability along any edge is characterized by competing exponential infection and recovery processes, resulting in p. = (3++))
28 46 Assuming independence and sparse network structure, node-level infection probabilities
approximated as p3 A [T (1 - pe*) ), where laj represents the path length between nodes and
j and we neglect higher-order interactions and overlapping paths 25 43
The number of disjoint infection paths m; scales approximately as cka, reflecting the influence of average degree 1e and initial infection fraction a 44 approximated as = min log N/ log k} 9 leading to the simplified expression p; so 1 1- (1 po)cka with == (p.)*. Given the concavity of p;(1 - p.). we apply standard lower bound, yielding (1 - Pt) 2 minfp; 1 pr). Averaging this lower bound across all nodes, we obtain the claimed variance lower bound for the Monte Carlo estimator:
25 28). Typical path lengths & can be
1 N
Var(ś, pc) Z
1
min(1 - -(1 po) (1 (1- (1-po) poka
(6)
2M
observe that the variance of the Monte Carlo estima- for is primarily influenced by four factors: B/%, i. a, and M. The base probability pa := (3/(8 + 7))² increases with B/7, since the ratio B/(3+ + 7) grows monotonically. Meanwhile, L ::= min log N/ log kg decreases as i increases, leading an indirect increase of po with k.
Remark 1. Through Theorem 3.1

---

014
c.om1
Vartance 100
Mean Varience
C.00
Mean Variance
Casp
0.000
0.00
600
log(Bly
875
(a) 3/7
(b) k
(c)
(d) M
Figure 1: Influence of key factors MC estimator variance.
As po. k. increase, the term (1 po)aka in the variance bound decreases. Since the bound depends on
)oka (1-po)ckep ckkc it achieves its maximum when this term approaches 0.5. Therefore, estimator variance increases initially with 3/7, k, or a, reaching a peak when the infection probability nears 0.5, and then decreases as the infection probability saturates. contrast, M appears in the denominator and monotonically reduces 0 as M increases. These factor effects are empirically verified in Figure
3.2
Neighborhood Propagation Analysis
In Section 2.2 wc show how diseases propagate probabilistically through local neighborhoods. However, using PID directly for inference lead to great computational inefficiencies, especially on large-scale networks. A key bottleneck is the path-level inefficiency: in each update round, all nodes with non-zero infected probabilities must be updated, resulting in propagation complexity of approximately O(EE)) as more nodes become affected, In this section, we provide theoretical analy- sis of neighborhood-level approximations and global convergence conditions, laying the groundwork for scalable inference methods.
Remark 2. When using simulation based methods for inference, is common to approximate the continuous-time dynamics with discrele-timee process [18 17y. Here, 3 and denote the per-unit- time transmission probability and healing probability, respectively. However, when B and yy take relatively large vulues, it becomes necessary to scale them down to smaller time units, i.e, setting = =B and y == 7dv. This adjustment ensures consistency with the continuous infection rate:
lim 2.-0
= =3 3--008 003))
which approximates linear growth for small B. Otherwise, if 3 and 7 are large, the non-linear higher- order terms become non-negligible and can introduce significant errors in inference. Therefore, in the following discussions, we assume scaled-down B and satisfying 3 < and 7 1.
A major challenge in SIR inference is that the underlying dynamic system is highly nonlinear, as shown in Eq. (2). Remark 2 guarantees that the higher-order errors remain sufficiently small. Following the linearization technique of [47], we locally linearize the nonlinear dynamics and derive the following theorem.
Theorem 3.2 (Linear Approximation of Infection Dynamies). Given a directed contact network
G = (V. &, A). Assume an SIR model parameterized by infection probability 3 and recovery probability 7, The infection probability update equation Eq. (2)
Pt(t = (t) - (t + (1 Pt(t)
(8)
can be approximated by the following linear expression:
Pt + 1) = (t) Σ
+ +
(9)
JEV
Proof. We sketch the main argument; detailed derivation is provided in the Appendix. Under the SIR model on a directed contact network g (V, & A), let (t(t) and Pt(t) denote the marginal probabilities that node is infected susceptible at time The infection update equation follows from accounting for new infections and recoveries in Eq. (
Pf 1) (t(( II (1 +1- jEV
(10)
5

---

Here, Pt(() (t +) represents the probability that node i transitions from susceptible to infected at time L + 1, while (1 - -) (t) reflects staying infected without recovery. We then apply the first- order approximation log(1 =+) R - for small x to linearize the product term 11 3A (1)). This yields the following approximation for the probability of remaining susceptible:
(t +t) Pg()+11 B Σ p)
(11)
jEV
Substituting into the update equation, we obtain:
P)())3 +()
(12)
JEV
This linear form captures the cumulative infection pressure from neighbors and the retention of infection due to non-recovery with probability ?
Theorem 3.3 (Convergence Condition for Non-Reinfectton Epidemic Models). Consider a gen- eralized non-reinfection epidemic model (e.g., S* (501) over directed contact network 9 = - A), where each susceptible node becomes infected with probability 3 upon contact with infected neighbor, and each infected node transitions to an absorbing state with probability at each time step. Then, the system's 's state distribution Pt) converges if and only if
max (1( + 2EV
(13)
Proof. We sketch our proof as follows; detailed derivations provided in the Appendix. We divide the argument into necessity and sufficiency. For necessity, we observe that if the state difference PPt(t) P(t 1)]l2 tends to zero, then by the update equation of the absorbing state, ||Pv- (t) - Pv- (t - 1)ll2 = 71 (t 1)/l2 must also vanish. Since this term is bounded by the total state difference, immediately obtain [P 1)ll2 + O, and thus maxee Pf 1) - O.
For sufficiency, assume maxiev (t-1) - 0. which implies that (t-1)l - 0. Since the absorbing state update satisfies PP--(t) Pv- (t-1)ll2 = (t- 1) follows that PP-
Pv- (t-11))) -> O. Moreover, we show in the Appendix that (t) (t + 0. By conservation of total probability, we then have:
PP-- (t) Ps- (t-1))l2 - (P) - Pi(t-1)lla + (1Pv-((t) - Pv- (t-(1-))ll2
(14)
Combining these bounds shows that all components in PP(()) - P(t - 1)l12 vanish as increases, proving the claim.
Remark 3. Theorem 3.3 implies that under non-reinfection epidemics models such SIR, SEIR, or SIRD, the process invvitably converges as the infected probability at every node vanishes asymp- totically, ie., Vi E, Pt(t) - O. Consequently, the entire disease dynamics can be equivalently analyzed as a transition from susceptible to non non-susceptible states (S* + V*), without needing to explicitly model the transient infection state in the long term.
4 Methodology
In this section, we first introduce the proposed algorithm RAPID, and then analyze its computational complexity. Our design ensures high efficiency, while the theoretical results 24 37 guarantee the accuracy of inference on sparse or locally tree-like epidemic contact networks, which are commonly encountered in practice.
4.1 The Proposed Algorithms
As our theoretical analysis in section 3.2 suggested that PID may suffer from computational inef- ficiency in the neighborhood propagation process, we propose an accelerated counterpart, RAPID (Residual-Awel Aware Propagation for Infection Dynamics), to efficiently scale inference on large contact networks. Our key idea to define a propagation residual that quantifies the potential change in node's 's infection probability due to local propagation. Nodes with large residuals are marked as active, and infection updates are computed only for these nodes, significantly reducing the overall computational cost.

---

First, we analyze the source of a one-step update on a node's 's infection probability. According to Theorem 3.2, we have
+(0)
(15)
JEV
Taking the difference between consecutive time steps, we get:
1) P((() ~ (3 Σ (3; P Σ - 1))
JEV
JEV
+ (1 - (P)(1) - Pi(L- - 1))
$ Ptt(t 1) Σ (sx(()(()) - (t- - 1))) (1 (P)))) Pj(t 1)) -P/(t
jev
S 3 Σ jEV
, (P) (1 (P) (1- -
(16)
Change due to retained infection
Change due to propagution
We aim to update a node's state through local propagation only when the external influence is sufficiently strong. Based on the derivation in Eq. (16). we define
Ries (i) = 3 Σ 5 (P) PP)
(17)
JEV
as the propagation residual at node i, where P// denotes the current infected probability of node and P/ denotes its cached value before the most recent update.
An overview of RAPID is shown in Algorithm 2] We first perform p rounds of probabilistic dis- ease propagation using Eq.2). which serves as a preheating phase to initialize node states and com- pute propagation residuals. After preheating, we maintain max-heap priority queue (referred to as the active queue) sorted by node residuals. At each iteration, the node with the highest residual is popped and its full state vector p is updated using Eq. (2 in line 13.
Algorithm 2 Sketch of RAPID
Require:
Graph G, threshold rates 3, initial
infected Ia. preheat steps p
1: Initialize Ps, Pr, PR
2: Preheat system for p rounds and record Pr
3: Initialize max heap 7/
4: for v E V do
5: Compute (Roy(1) with Eq.
6: Push (Pogs (1), v) into H
7:
end for
while not empty
The resulting change in infection probability, Pj- Pj. is linearly propagated its out-neighbors by incrementing their propagation residuals. If neighbor's updated residual exceeds the thresh-
9: (Rac(i), i) <- popTopp(H)
10:
if (i) < then break end if
11:
12:
Pj > E then
old, it is pushed into the active queue for future propagation is shown from line 15 to line 19.
13:
Update PS. Pj. Ph. Pi
14:
Set 8 <- Pj Pi
After propagation, the residual of the current node
15:
for j NE (t) do
set to zero, indicating is longer active. The algorithm terminates when the active queue be-
16:
Ris + Ries (J) + B 8
17:
if Ree(() > e then push j into H.
comes empty. Since Rres(2 < B B JEv Py.
18:
end if
Theorem 3.3 guarantees that once the system con-
19:
end for end if
20:
verges (maxlev Pj + 0), the residuals vanish
21:
Res + 0
(Ryes (i) 0), ensuring convergence of RAPID.
22:
end while
23: return Ps, Pt, PR.
4.2 Complexity Analysis
Theorem 4.1 (Worst-Case Time Complexity of RAPID). Consider RAPID directed contact
network G = EV,E) with N = [V] nodes and average out-degree k. Let the infection probability
be 3, the recovery probability be % and the residual threshold be > O. Then, under worst-case
conditions, the total time complexity of RAPID is
O[N A min - ))
(18)
8 .'''
7

---

10
PC
PD
Menooa Tau
Drgine
Dnyaee
Dryaen
22
MD:00
Rartmm (weconda)
Purtinu (sacand))
(a) carilion-Hospital
(b) hiv-Trans
(c) email- Marail-Erron
KENY
Nermi De
T4 Toun
PMn
Engine
Onjiee
Drgann
X
M0:00
Horbre (vecnda)
Purtie (oconda)
Partinn (secand))
(d) email-FuAll
(c) soc-Epinions
(f) soc-Pokec
Figure 2: Trade-off between Kendall- Tau and Runtime across six datasets.
Proof. The key insight is that a node becomes active only if its residual exceeds e, and the residual update it can receive in a single iteration approximates i- B, since infection can passed through k neighbors on average at rate B. In the worst case, all N nodes become active, and each may trigger residual pushes up to k neighbors. When is large (i.e., E > k:3), only large residuals are propagated, and the number of total pushes is upper bounded by O(N k. B/e). However, when e becomes very small (i.e., 8 < k;3), further reducing ε does not lead to more node activations, since the residuals themselves are bounded. Therefore, the total number of pushes saturates at O(N k). Combining both regimes gives the overall time complexity. This scaling behavior mirrors residual-basee approximations in PPR push methods (3), but here it arises from the probabilistic infection dynamics of epidemic modeling.
5
Empirical Study
In this section, conduct extensive experiments to investigate the effectiveness and efficiency of the proposed method.
5.1
Experiment Settings
Datasets. We use graphs from diverse domains, including real-world hospital contact network (carilion-Hospital (1) real-world HIV transmission network (hiv-Trans [40),, communi- cation networks (email-Enrow [35 29), email-EuAll
34) ) and social networks (soc- (soc-Epini and email- Enron are undirected, while the others are directed. Nodes with no incoming or outgoing edges are removed and each undirected edge is represented as two reciprocal directed edges. Detailed statistics are summarized in We also inclue a Bitcoin trade network (bitcoin-Alpha
[52], soc-Pokec [54). Among them,
Table 2
33 32 the appendix.
Baselines. To serve as baselines, we implemented broad range of inference models. detailed description is provided in the Appendix.
Table 2: Datasets Statistics
Dataset
#Nodes
#Edges
Avg Deg
carilion-Hospital
11,810
30,994
2.62
Network centrality measures: Degree, Eigenvector PageRank [45). Betweenness [6] and Closeness
hiv-Trans
35,230
34,243
0.97
471
EmaiilEEnro
36,692
367.66 667,662
10.02
These methods assess structural importance and are evaluated by ranking.
53
email- EuAll
265,214
420,045
1.58
soc-Epinions
75,879
508,837
6.71
MC-hased inference: 5-run and 10-run Monte Carlo simulations (MC-5 and MC-10).
soc-Pokec
1,632,803
30,622,564
18.75
Probabilät-bassed inference: Propagation for Infec- tion Dynamics (PID), which retains all propagation steps during disease spread process, and is unaccelerated invariant of RAPID.

---

y x
RAPID Runtive tecords ko solk))
Precision
0.95
X
0.90
MC:5
MC-10
PID
RAPID
Racal
15"
Me
Figure 3:
Classification metrics (precision, recall, FI) on hiv-Trans.
Figure 4: RAPID runtime grows sublinearly with graph size and density.
Parameter Settings, To ensure the practical relevance of our study, we consulted the literature to obtain the infectious period and basic reproduction number (Ra) for various discases, summarized in the Appendix. In our experiments, the ground-truth infection probability for each node estimated 50-run Monte Carlo simulations For reporting and
by averaging its infection frequency baseline comparisons, we adopt the parameter setting of Nipah Virus (3 = 1/18, Y = 1/9) with an initial infection fraction of 0.01. Results for other disease parameters similar and provided in the Appendix.
5.2 Effectiveness and Efficiency Analysis
Effectiveness of RAPID. We evaluate the effectiveness of RAPID and baseline methods from three perspectives: the ranking of node-level infection probabilities, the classification performance of nodes whether infected, and the accuracy of infection probability estimation.
Figure 2 shows the trade-off between Kendall-7 and runtime across six datasets. RAPID achieves the best or near-best rank correlation on all of them while keeping the runtime consistently fast. We treat nodes with inferred infection probability above 0.5 as infected. Figure 3 presents the classification results on hiv-Trans, where RAPID significantly improves precision over baselines, achieving the best overall performance.
Table B reports the mean absolute error (MAE) for infection probabil- ity estimation. RAPID consistently outperforms MC-5, MC-10, and PID) across all datasets. As noted in (37]
Table 3: MAE comparison (lower is better). All values scaled by 10-2, Best results are in bold.
Dataset
MC-5
MC-10
PID
RAPID
carilion-Hospiat
13.01
10.78+0.44
5,67+0.51
2.64-0.49
when contact networks contain many short loops, nodes within these loops cyclically influence each other's states over time, which reduces the accu- racy of the original PID algorithm. RAPID addresses this issue by em- ploying asynchronous max max-heap heap iterations to accelerate convergence and selective updates to mitigate
div-Trans
5.12-0.12
3.24+0.11
6.43+0.52
1.27-047
email-Enron Enron
7.60s0.02
5,98.003
8.70.004
4.6620.00
email-FuAll
2.09-0.01
1,63+001
1.36-0.2
1.03-0.01
soc-Epins soc-Epinions
5.48-0.03
4,92-003
2.77-0.00
soc-Pokec
4.50.0.00
3,54
3,32a0.00
2.32.0.00
the effect of short loops, thereby achieving higher inference accuracy than PID. Notably, although the Kendall-T on hiv-Trans lower than on other datasets, largely due to the large number of uninfected nodes at convergence, RAPID still achieves superior classification accuracy and lower MAE compared to all baselines.
Runtime Comparison. Table shows the runtime of RAPID and baselines on each dataset. On the six datasets, RAPID achieves an average speedup of 5.11x. x, 10.67x, and 8.52x over MC-5, MC-10, and PID, respectively. Compared to PID, the speedup is more pronounced on denser graphs, reaching 12.91 x on soc- opinninnnoss. Against MC-10, 10, RAPID exhibits stable acceleration ranging from 7.64x to 12.58 x, consistently maintaining runtime comparable to that of single-run MC across all datasets.
'On carilion Mellion-Hosppe Hospital and hiv-Trans, we adopt 1000-run MC simulations the ground truth for acceptable estimator variance.

---

Table 4: Runtime comparison across datasets (seconds, lower is better). A indicates the speedup factor relative to RAPID, computed as A
Baseline time
RAPID time
CarliionHospiia
hiv- TivnTTans
email- Enron
email-FaAll
soc-Epinions
soc-Pokec
[
5.81
21.87a3.15
29.84.1.43
169.46s1.2
59.69s1.26
1241.00.18.79
MC-5
5,43%
5.16x
5.41x
5.06x
5,82x
3.78
13:46:1.14
49.94
56.45:079
330.97
122.31a2.4
2506.60s1544
MC-10
12.58x
11.78x
10.24x
11.91x
7.64x
1234.73a18.13
4678.18:8.00
279.26:3.09
1659.57:23.5
614.58.1.3
12782.37:237. 30
MC-50
1153,95x
1103.34 34x
50.66x
x9.52
59.86x
38.93x
6
3.56+0001
17.91-0.14
66.95-029
206. 18-0.65
132.60
4056.89-6.40
PID
3.33x
x.22x
12.14x
6.15x
12.91x
12.36x
RAPID
1.07.000
4.34 0.03 5.51
33.50
10.27-0:0
328.28
Complexity Validation. Figure shows the empirical log-scale runtime of RAPID versus log(NV) on six real-world networks. The fitted complexity runtime x (Nk)).74 is better than the worst-case bound established in Theorem 4.1 confirming the validity of our analysis.
Conclusion
In this paper, systematically studied the variance of Monte Carlo simulations for modeling the disease spread process in contact networks, and introduce a linear approximation for infection propagation under non-reinfection models with a provable convergence guarantee. Based on the theoretical findings. we propose RAPID, residual-driven framework to infer node-level infection probability distribution with high estimation accuracy and low computational cost. Experiments on six real-world networks show that RAPID matches the accuracy of multi-run Monte Carlo within the runtime of single simulation. Future work includes extensions to models with reinfection, time-varying parameters, and dynamic networks.
Acknowledgments
The authors would like to thank the anonymous reviewers for their constructive comments. This work was supported in part by the NVIDIA Academic Grant Program, the Commonwealth Cyber Initiative (CCI) under Award No. HV-2Q25-032, and the National Science Foundation under Grant No. 2331315. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation.
References
[1] B. Adhikari, B. Lewis, A. Vullikanti. J. M. Jiménez, and A. Prakash. Fast near-optimal monitoring for healthcare acquired infection outbreaks. PLoS computational biology, 15(9):e1077284, 2019.
[2] M. Al-Raeci. The study of human monkeypox disease in 2022 using the epidemic models: Herd immunity and the basic reproduction number case. Annals of Medicine and Surgery, 85(2):11-321,, 2023.
[3] R. Andersen, Chung. and K. Lang. Local graph partitioning using pagerank vectors. In 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS' 06), pages 475-486. IEEE, 2006.
[4] R. Andersen, F. R. K. Chung, and K. J. Lang. Local graph partitioning using pagerank vectors. In Proceedings of the 47th IEEE Symposium Foundations of Computer Science (FOCS), pages 475-486, 2006.
[5] P. Block, M. Hoffmann, I. Raabe, J. B. Dowd, C. Rahal, R. Kashyap, and M. C. Mills. Social network- based distancing strategies flatten the covid-19 curve in a post-lockdown world. Nature human behaviour, 4(6):588-556, 2020.
[6] U. Brandes. A faster algorithm for betweenness centrality. Journal of mathematical sociology, 25(2): 163- 177, 2001.
[7] Centers for Disease Control and Prevention (CDC). Infectious diseases overview, 2023. 2024-12-06.
Accessed:
10

---

[8] M. Chinazzi, J. T. Davis. M. Ajelli, C. Gioannini, M. Litvinova, S. Merler, A. Pastore Piontti. K. Mu,
L. Rossi, K. Sun, et al. The effect of travel restrictions the spread of the 2019 novel coronavirus (covid-19) 19) outbreak. Science, 368(6489) 400, 2020.
[9] F. Chung and L. Lu. The average distances in random graphs with given expected degrees. Proceedings of the National Academy of Sciences, 99(25):15879-15888 15882, 2002.
[10] D. R. Cox and V. Isham. Point processes, volume 12. CRC Press, 1980.
[11] M. J. Crawley. The R book. John Wiley & Sons, 2012.
[12] M. Eichner, S. F. Dowell, and N. Firese. Incubation period of ebola hemorrhagic virus subtype zaire. Osong public health and research perspectives, 2(1):3-7, 201
[13] G. Elidan, I. McGraw, and D. Koller. Residual belief propagation: Informed scheduling for asynchronous message passing. In Proceedings of the 22nd Conference on Uncertainty in Artificial Intelligence (UAI), pages 165-173, 2006.
[14] N. M. Ferguson, D. Laydon, G. Nedjati-Gilani, N. Imai, K. Ainslie, M. Baguelin, S. Bhatia, A. Boonyasiri, 7. Cucunubá, G. Cuomo-Dammenburg, et al. Impact of non-pharmaceutical interventions (npis) reduce covid- 19 mortality and healthcare demand. imperial college covid-19 19 response team. Imperial College COVID-19 Rexponse Team, (O110.25561))77455 2020.
[15] S. Flaxman, Mishra, A. Gandy, H. Unwin, A. Mellan, H. Coupland, C. Whittaker, H. Zhu, T. Berah, J. W. Eaton, et al. Estimating the effects of non-pharmaceutical interventions on covid-19 in europe. Nature, 584(7820)2257-666 2020.
[16] A. Ganesh, L. Massoulié, and D. Towsley. The effect of network topology on the spread of epidemies. In Proceedings IEEE 24th Annual Joint Conference of the IEEE Computer and Communications Societies. volume 2. pages 1455-1466. IEEE, 2005.
[17] F. Gao, J. Liu, and Y. Zhao. Recurrent dynamic message passing with loops for epidemics on networks. Chaos, Solitons& & Fractals, 184:1 154:5, 2024.
[18] F. Gao, J. Zhang, and Y. Zhang. Neural enhanced dynamic message passing. In International Conference Artificial Intelligence and Statistics, pages 10471 PMLR, 2022.
[19] A. Gelman, J. B. Carlin, H. S. Stern, and D. B. Rubin. Bayesian data analysis. Chapman and Hall/CRC, 1995.
[20] R. Grant, L.-B. L. Nguyen, and R. Breban. Modelling human-to-human transmission of monkeypox. Bulletin of the World Health Organization, 98(9):63,, 2020.
[21] X. Hc, E. H. Lau, P. Wu, X. Deng, J. Wang, X. Hao, Y. C. Lau, J. Y. Wong, Y. Guan, X. Tan, et al. Temporal dynamics in viral shedding and transmissibility of covid-19. 19, Nature medicine, 26(5):672-66 675, 2020.
[22] Y. He, C. Chen, S. Wang, G. Min, and J. Li. Demystify epidemic containment in directed networks: Theory and algorithms. In Proceedings of the Eighteenth ACM International Conference Web Search and Data Mining, pages 905-913, 2025.
[23] G. Jeh and J. Widom. Scaling personalized web search. In Proceedings of the 12th International Conference on World Wide Web (WWW), pages 271 1779, 2003.
[24] B. Karrer and M. E. Newman. Message passing approach for general epidemic models. Physical Review Statistical, Nonlinear, and Soft Matter Physics, 82(11:06 2010.
[25] D. Kempe, Kleinberg, and É. Tardos. Maximizing spread of influence through a social network. In Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 137-146, 2003.
[26] J. O. Kephart and S. R. White. Directed-graph epidemiological models of computer viruses. In Computation: the micro and the macro view, pages 71-102. World Scientific, 1992.
[27] W. O. Kermack and A. G. McKendrick. A contribution to the mathematical theory of epidemics. Pruceed- ings of the royal society of london. Series A, Containing papers of a mathematical and physical character, 115(772):700-23 -7211 1927.
[28] I. Z. Kiss, J. C. Miller, P. L. Simon, et al. Mathematics of epidemics on networks. Cham: Springer. 598(2017):31, 2017.
11

---

[29] B. Klimt and Y. Yang, Introducing the enron corpus. In CEAS, volume 4, page 1, 2004.
[30] F. R. Kschischang, B. J. Frey, and H. Loeliger. Factor graphs and the sum-product algorithm. JEEE Trans. Inf. Theory, 47 519, 2001.
[31] A. Kucharski and C. L. Althaus. The rolc of superspreading in middle cast respiratory syndrome coronavirus (mers-cov) transmission. Exrosurveillance, 20(25)211677 2015.
[32] S. Kumar, B. Hooi, D. Makhija, M. Kumar, C. Faloutsos, and V. Subrahmanian. Rev2: Fraudulent user prediction in rating platforms. In Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining, pages 333-341, ACM, 2018.
[33] S. Kumar, F. Spezzano. V. Subrahmanian, and C. Faloutsos. Edge weight prediction in weighted signed networks. In Data Mining (ICDM), 2016 IEEE 16th International Conference on, pages 221-230. IEEE, 2016.
[34] J. Leskovee, J. Kleinberg, and C. Faloutsos. Graph evolution: Densification and shrinking diameters. ACM transactions Knowledge Discovery from Data (TKDD), 1(1):2-es, 2007.
[35] J. Leskovec, K. J. Lang, A. Dasgupta, and M. W. Mahoney. Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters. Internet Mathematics, 6(1):29-123, 2009.
[36] P. Lofgren, S. Banerjee, A. Goel, and C. Seshadhri. Fast-ppr: Scaling personalized pagerank estimation for large graphs. In Proceedings the 20th ACM SIGKDD International Conference Knowledge Discovery and Data Mining (KDD), 2014.
[37] A. Y. Lokhov, M. Mézard, and L.. Zdeborová. Dynamic message-passing equations for models with unidirectional dynamics. Physical Review 91(1):012811, 2015.
[38] S. P. Luby. The pandemic potential of nipah virus. Antiviral research, 100(1 (M:1):38444 43, 2013.
[39] V. P. Martínez, N. Di Paola, D. O. Alonso, U. Pautu, C. M. Bellomo, A. A. Iglesias, R. M. Coelho, B. López. N. Periolo, P. A. Larson, et al. "super-spreaders" and person-to-perse topprsonn transmission of andes virus in argentina. New England Journal of Medicine, 383((3) 2241, 2020.
[40] M. Morris and R. Rothenberg, Hiv transmission network metastudy project: An archive of data from eight network studies, 1988 2001. 2011.
[41] K. P. Murphy, Y. Weiss, and M. I. Jordan. Loopy belief propagation for approximate inference: An empirical study. In Proceedings of the 15th Conference on Uncertainty in Artificial Intelligence (UAI), pages 467-475. Morgan Kaufmann, 1999.
[42] M. Newman. Networks: An Introduction. Oxford University Press, 03 2010.
[43] M. E. Newman, Spread of epidemic disease on networks. Physical review E, 66(1):016128 2002.
[44] M. E. Newman. The mathematics of networks. The new palgnave encyclopedia of economics, 2(2008):1-2,,
2008.
[45] I.. Page. The pagerank citation ranking: Bringing order the web. Technical report, Technical Report, 1999.
[46] R. Pastor-Satorras, C. Castellano, P. Van Mieghem, and A. Vespignani. Epidemic processes in complex networks. Reviews of modern physics, 87(3)925--79, 2015.
[47] R. Pastor-Satorras and A. Vespignani. Epidemic spreading in scale-free networks. Physical review letlers. 86(14):3200, 2001.
[48] J. Pearl. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann, 1988.
[49] S. Pei. S. Kandula, and J. Shaman. Differential effects of intervention timing on covid-19 spread in the united states. Science advances, reab)373,, 2020.
[50] B. A. Prakash, D. Chakrabarti, N. C. Valler, M. Faloutsos. and C. Faloutsos. Threshold conditions for arbitrary cascade models on arbitrary networks. Knowledge and information systems, 33:549-575, 2012.
[51] M. Reuter, S. Biasotti, D. Giorgi, G. Patane, and M. Spagnuolo. Discrete laplace-beltrami shape analysis and segmentation. Computers & Graphics, 33(3):381-390, 2009.
beltrami operators for
12

---

[52] M. Richardson, R. Agrawal, and P. Domingos. Trust management for the semantic web. In International semantic Web conference, pages 351-368. Springer, 2003.
[53] G. Sabidussi. The centrality index of a graph. Psychometrika, 31(4):881-033, 1966.
[54] L. Takac and M. Zabovsky. Data analysis in public social networks. In International scientific conference and International workshop present day trends of innovations, volume 1, 2012.
[55] P. A. Vial, F. Valdivieso, G. Mertz, C. Castillo, E. Belmar, I. Delgado, M. Tapia, and M. Ferrés. Incuhation period of hantavirus cardiopulmonary syndrome. Emerging Infectious Diseases, 12(8):1271, 2006.
[56] H. Wang. Z. Wei, J. Gan, Y. Yuan, X. Du, and J. Wen. Edge-based local push for personalized pagerank. Proc. VLDB Endow. 15(7):1376-189, 2022.
[57] Y. Wang, D. Chakrabarti, C. Wang, and C. Faloutsos. Epidemic spreading in real networks: An cigenvalue viewpoint. In 22nd International Symposiun on Reliable Distributed Systems, 2003. Proceedings., pages 25-34. IEEE, 2003.
[58] 7. Wong, C. Bui, A. Chughtai, and C. Macintyre. A systematic review of early modelling studies of chola virus disease west africa. Epidemiology & Infection, 145(6): 1069-104,, 2017.
[59] World Health Organization (WHO). Fact sheets infectious discases, 2023. Accessed: 2024-12-06.
[60] G. Xie. A novel monte carlo simulation procedure for modelling covid-19 19 spread over time. Scientific reports, 10(1):13120, 2020.
[61] J. S. Yedidia, W. T. Freeman, and Y. Weiss. Constructing free- etee-energy approximations and generalized belief propagation algorithms. IEEE Trans. Information Theory, 51(7):2282 2312, 2005.
[62] H. Zhang, P. Lofgren, and A. Goel. Approximate personalized pagerank on dynamic graphs. In Proceedings of the 22nd ACM SIGKDD International Conference Knowledge Discovery and Data Mining (KDD), 2016.
13

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction in this paper accurately reflect the paper's contributions and scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We discuss the limitations of the work in the supplementary material.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
14

---

Answer: [Yes]
Justification: In this paper, all proofs of theorems are provided and all assumptions are clearly stated or referenced in the statement of any theorems.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: All the results in this paper can be reproduced.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is new model (e-g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
15

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We provide open access the data and code, with sufficient instructions faithfully reproduce the main experimental results.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nnis.cc
aublic//uuides/Codeetubiis
www.sssinnooiiillo for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ wwtp:/cccppppgguuuiiaeoeaec
wtweee///ooSSSeissss.ee.e www.ssssiicggcoooo for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The paper specify the experimental details necessary to understand the results.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We report еттоr bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments in this paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
16

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: For each experiment, the paper provide sufficient information the computer resources needed to reproduce the experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't iidn't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https/ssttt//eursssssc.coo http:///pppppppppppcececcecccccc ins
Answer: [Yes]
Justification: The research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: The paper discuss both potential positive societal impacts and negative socictal impacts of the work performed in the supplementary material.
Guidelines:
17

---

The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploymentt of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (c.g., gated release models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: The creators original owners of assets used in the paper properly credited and the license and terms of use are explicitly mentioned and properly respected.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
18

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in the datasets.paperssiii paperswi thcode. www.com//aaaa datasets package should be provided. For popular datasets,
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmodel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [No]
Justification:
The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
19

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if' applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core method development in this research does not involve LLMS as any important, original, non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy (https://neurips: /att::///earrrpsssc//oooeerreee/ cc///oofeeeeeecs//22/////.. for what should or should not be described.
20

---

Supplemental Material
Organization. This supplementary material is organized follows. Appendix A reviews related work and relevant theoretical background. Appendix presents detailed proofs of the main theorems. Appendix prooides complete algorithm descriptions and highlights our design rationale from a Jacobian perturbation perspective, from which we derive the classical epidemic threshold and offer physical interpretation of the propagation residual. Appendix D outlines implementation details and presents additional experiments, including: (i) how Monte Carlo variance affects the reliability of MC-based inference, (ii) the extension of our method to the SEIR model, (iii) the impact of initial infection distributions, (iv) experiments under alternative disease settings, and (v) a sensitivity analysis of hyperparameters. Appendix discusses current limitations and potential directions for future research.
A Related Work
Belief Propagation on Graphs. Belief propagation (BP), also known as the sum-product algorithm, is a foundational message-passingg technique for probabilistic inference on graphs. Originally intro- duced by Pearl for exact inference in tree-structured Bayesian networks 48). BP was later applied to graphs with cycles as an approximate method, i.e. loopy BP [4]] The algorithm iteratively transmits local "messages" along edges of a factor graph to compute marginal probability estimates [30]. Despite the lack of general convergence guarantees, loopy BP often produces accurate results and has achieved remarkable success across domains (e.g. decoding of error-correcting codes and vision networks). Numerous extensions have enhanced BP's accuracy and robustness. For instance, Yedidia et al. reinterpreted BP in terms of variational free-energy minimization and proposed generalized BP for higher-order region graphs [61]. Other work has focused improving BP's convergence, such as methods that dampen oscillations or prioritize message updates based on residual magnitude [3] These advances have solidified BP versatile approximate inference framework in graphical models.
Local Push Algorithms and Variants. LocalPush algorithms are class of residual-basse methods for approximate graph propagation, widely used in computing node influence scores or similarities on large graphs. A prime example is the estimation of Personalized PageRank (PPR) vectors, which measure the influence of a source node across graph. Early approaches 23 found that by maintaining "residual" at each node and pushing this probability mass outwards along edges, one can obtain accurate PPR estimates efficiently without full graph traversal. Andersen et al. formalized this idea by introducing local push procedure with rigorous error bounds, enabling fast local graph partitioning via PageRank [4]. The LocalPush strategy restricts computation to the source's 's local neighborhood, yielding near-linear time updates for sparse networks. Subsequent research has built on this foundation to handle more complex settings. Notably, bidirectional and multi-target push algorithms improve efficiency for queries between specifie node pairs [6). Dynamic extensions have been developed to maintain PPR results under streaming graph updates, by locally adjusting residuals after each edge insertion or deletion [62]. Further optimizations address weighted graphs and precision guarantees, as in the edge-based LocalPush variant that decomposes pushes per edge to reduce redundant work (56). Collectively, these residual-based propagation techniques have become essential tools for scalable graph mining, enabling approximate inference of importance or similarity scores with provable accuracy massive networks.
B Theoretical Proof
B.1 Proof of Theorem 3.1
Theorem 3.1 (Monte Carlo Estimation Variance Lower Bound) Given directed contact network G = (V,E) E) with N = [V], average out-degree k, and diameter D. Let To C V be the initially infected node set with fraction a := /Zo/NN Assume an SIR model parameterized by infection probability / and recovery probability r. Using M independent Monte Carlo simulations to estimate each node's s
21

---

infection probability Pi, the average variance of the estimator P; satisfies:
N
Var(ps -pi)
min (1 (1 po) (1 poke
(19)
N
2M
where
Po = 3 3+77 t:= min log NV. log k }
(20)
and > 0 is constant depending the network structure.
Proof. Each node's infection probability p; is estimated by Monte Carlo simulation:
P. M
mm)
(21)
where (5(m) {0, 1] indicates whether node is infected in simulation m. The variance is:
1 P.(1 P (p). M
Var[p:]
(22)
Under the continuous-time SIR model, infection along edge competes with recovery via indepen- dent exponential clocks. The transmission probability per edge is [28 46]
8
Pe Pr(Tinteat Trecoverl
(23)
B ++7
Assuming that infection mainly driven by multiple independent disjoint paths [25 probability of node can be approximated as:
infection
P: x
(1- 3=1
(24)
where neglect overlapping paths and higher-order interactions in sparse networks.
In sparse graphs, the number disjoint infection paths to node heuristically assumed scale with the average degree and the initial infection fraction a, yielding m; = cka. This scaling reflects intuition that a higher initial infection fraction increases the number potential sources and thus the likelihood of multiple disjoint infection paths 43 25 28). The typical path length approximates
min D, log N/ log k.)
Substituting these yields:
P= (1 Poac
Po == (pe)
(25)
Since (1 - -p;) is concave with maximum at = 2, we lower bound it by:
p: p.) min - p.j.
(26)
Averaging this bound over all nodes (the bound is node- node-indeeenneet and thus unchanged by averaging). we obtain the claimed variance lower bound for the Monte Carlo estimator:
min { (1 - po)cka (1 poo
Var(ø: ps) 2
(27)
N
2M
B.2 Proof of Theorem 3.2
Theorem 3.2 (Linear Approximation of Infection Dynamics) Given directed contact network
(V,E, E, A). Assume an SIR model parameterized by infection probability B and recovery probability The infection probability update equation
Pt + 1) = (t) (t +
(28)
can be approximated by the following linear expression:
Pt(t + 1) (1) Σ
(1))))))))())))))
(29)
JEV
22

---

Proof. Substitute the susceptible update:
Pš(( 1=
= P((( II 3A3
(30)
into
+ -
(31)
Take logarithm:
log [[1-BAA,P(0)) Σ log(1 - (t)).
(32)
Approximate log(1 z) x and exponentiate both sides:
2 A(.0))
3A =-,,
(33)
According to Remark 2 we have 3 & 1. Use 1 - -
-- (1) ~ 3 Σ (t)
(34)
Substitute into Pf + 1) to obtain the linear form.
B.3 Proof of Theorem 3.3
Lemma B.1. [Pr 1)1l2 - 0 is sufficient for [P((1) - Pı(1 - Pt(1-1)ll: +
Proof. This problem is equivalent to proving that for all E > 0, there exists > 0 such that if [| 1) < e, then (tt))) (t 1)ll2 < 8.
We have:
max Pf 1) s || 1)12 S..
(35)
iEV
First, for the absorbing state Pv- Pv-(1):
[Pvv - Pv. (t 1)l12 1))((t1))2=11111 1) S ye.
(36)
Next, for Ps(t):
Pg(1 - 1) 1) P()(() Pt - 1) (5(1-1) II BA - 1))
JEV
< II (1- (t,,
JEV
(1- (i))
By Bernoulli's inequality, if < x < 1, then (1 - x) din (i) 2 e din( Letting =BE, we get:
(1 BE) dn (i) (0)
(37)
Thus:
Pt - s1
(38)
Since Pt 1) (t) E (0, 1), can further bound:
1 - E (i)
< (1 - )
(39)
Therefore:
- 1) (1) < (1 - e -N8)E.
(40)
Aggregating:
|Ps - 1) - ps(t)]2 < VN(11 - NN8).
(41)
23

---

Finally, for Pt(t) - Py 1);
1):
[Pr(() Pt 1)]12 = 1111- (t) - - (1 Pv- - 1))ll
= ||Ps(L 1) - (2-0)))-((-11----))
S Ps - 1) - [s(()]22+(AAv-()) (t--
S VN - =NND)s 78.
Let:
8 = ( + +7) E.
(42)
Then from max;ev Pj(t ((ft-1) 1) S c, we conclude:
[|Pr(1) - P1i00-PP(L--- S 5.
(43)
Epidemic Models) Consider generalized non-reinfection epidemic model (e.g.. 1-' (50)) over a directed contact network g = (V, A), where each susceptible node becomes infected with probability 3 upon contact with an infected neighbor, and each infected node transitions to an absorbing state with probability y at each time step. Then, the system's state distribution P(t) converges if and only if
Theorem 3.3 (Convergence Condition for
max (t() - O.
(44)
&EV
Proof. We first prove necessity. We aim to show that for any 0, 0f - P(t - 1)ll2 S e, then 36 > 0 such that [t 1)]l2 s 8. Since
[IPv-(t)= Pv- (t- 1) >||Pp(t - 1) S PPt() P(t 1)lla S c,
(45)
it follows that
||: 1)112 s 8 "
(46)
Therefore,
max Pf(t - 1) = Pt - 1)(12 S 5ō = E LV
(47)
?
Next we prove sufficiency. For any E > 0, assume maxley Pf(t 1) S s. Then
[| - 1)l12 S VN max Pi(l - 1) S 1 VNe
(48)
iEV
From the update of Pv-.
| (4) Pv- (1 1)1[2 11 Pr(1 -
Pr(1 1)1l2 S TVN..
(49)
By Lemma B.1 since max; Pt 1) S E, there exists 8' > 0 such that |||)(t) - Pt(tt 1)]12 < 8'.
Since (t) + (t) + Pv- =1
[ts(t) - Ps(t - 1)1l2 = -|11- Pt(() - (t)
1) Pv- (t - 1))
= -|P/(t- - ( P)- -P--(t)l2
I (P((t) - P((t-1]la+(Po-(1) - -Pv-(t - 11)ll2
S 88 + NNNNe
Therefore,
[|P(t)) P(t - 1)112 = [|ps(t) Ps - (1P()) - 1)112 (P) - Pv. - Pv.(t-1)1 1)ll2
S (6' +
+ (nVNN)
Taking square roots:
[P((t) - P(t - 1) - V (8'
+ ( (0) (nvNe)))+) == 8.
(50)
Thus, for any e > 0. (t - 1))la < implies || P(t 1)]l2 56.
24

---

C Details of Algorithms
C.1 Baselines
All centrality-based baselines (including Degree, Eigenvector 44 PageRank (45) Betweenness and Closeness (53) are implemented using Python's 's network library.
C.2 MC for SIR
Algorithm 1: Monte Carlo Simulation for SIR
Require: Graph G = (V, infection rate 3, recovery rate 7, initial infected set Zo, number of
trials M
Ensure: Estimated final-state probabilities Ps. P/. PR for all i
1:
Initialize counters
2: countys f- 0, count' < 0, count +- 0 for all i
3: for 1 to M do
b Run M independent trials
4: slate' +- S for all i E
5: for To do state"
6: end for
while some node has state' = 1 do 8: Initialize next_state" + state" for all i
for all V do if state' then for all j E (N) do if state = S and rand() < 3 then next_state' t-
10:
12:
14:
end if end for if rand() <> then next_state +-
16:
17:
18:
end if end end for
19:
20:
21:
state' + next_state' for all
22:
end while
23:
Update final counts
24:
for all E V do
25:
if state = S then count count +1
26:
27:
end
28:
if state then
29:
end count + count) +
31: if state' = R then
count count 33: end if
end for
35: end for
Normalize to obtain final-state probabilities Pk +- count]
37: PS counti//M
Pj count//M,
38: return Ps, Pt, PR
https://networkk..ogg
25

---

C.3 Details of PID Algorithm
Algorithm 2: PID: Probabilistic Infection Dynamics
Require: Graph 9 (V, infection rate recovery rate 7, initial infected set Io, threshold
Ensure: Marginal probabilities (t),), (t),,, PR(t) 1: (0) + 1. ()) + 0, (0) - 0, vie
for Io do
3:
(3(0) <- P)(0) +-1
4: end for
5: t <- 0
6: repeat
7:
for all E V do
Pš((+1) Pt(() [LEENE (1- (1-B.
8:
9:
Pf(++1 Pt(()= (1--))))))))))- Pf())
10:
(h((+1) + 1-s(((+1) Pf(++]
11:
end for
12:
+-t+1
13:
until [Ps(t)) Ps(t-1)]|e + PP((tt (t-11) + PPR((t) PR(t-1)li s
14:
return Ps( (t))), Pn(L)
C.4 Details of RAPID Algorithm
Algorithm 3: RAPID: Residual-Acceleratee Propagation for Infection Dynamics
Require: Graph G (V, 8). rates y, initial infected set Io, threshold E, preheat steps p Ensure: State probabilities Ps. Pr, Pr.
Initialization
2: P3 +- 1, PT 4,, 0, P% + 0 for all VEV
for Io do
4:
P + 0, +
end for
6: Pj t Pj for all
D Snapshot for residuals
Preheat phase to reduce approximation error
8:
for fort= - to do
9:
for all
do
10:
py <- Pg
11:
PS < P5 IIEENE 3 Ptt)
Py (1 - 7) Pe + (Py P5)
13:
Ph + 1 Pg Pp
end for
15: end for
p Residual initialization
17: for all U E do
18: Ruc(()) 3. EmENs"())
(PF PP
19: end for
20: Initialize max-heap H with all such that Rre((v)
21: while H not empty do
D Residual-driven propagation
22:
(i) i) (P))Top(H)
23: if R < e then break
end if
25: if Pt > then
26:
Pg +- P
26

---

Pg + Pg. TEEEE 3. Pf)
28:
Pi 7 Pf + (P' Pb)
29:
Pk - P Pi
ò Pi Pi
Pi Pi
32:
Propagate residual to out-neighbors
33:
for j E N (i) do Res(j) x (res()) + 3
34:
35:
Ress (j) > then push (Ris(t)). into H.
36:
end if
37:
end for end if
38:
39: Ries (i) +
40:
end while
41:
return Ps, Pr, PR
C.5
Design of Propagation Residual
The residual term is derived from the one-step temporal difference of the infected probability, as formulated in Eq. (15):
(t + 1) Pi(t) S -
(51)
jeV
Change due retained infection
Change due to propagation
Although the propagation residual was originally motivated by the temporal dynamics of infection spread, its formulation is not heuristic. Instead, it admits principled interpretation as first-order Jacobian approximation
neighbor-induced perturbations under lincarized infection model.
In the following, we formally derive this connection, show how it naturally leads to the classical epidemic threshold, and provide physical interpretation of the residual-driver max-heap update mechanism.
Theorem C.1 (Jacobian Interpretation Propagation Residual). In Eq. (16), we define the propaga- tion residual at node as:
Ryes (i) = 3 Σ A (P) P/),
(52)
jEV
where Pj and P?] denote the current and previously cached infection probabilities of node j. This residual can be interpreted local Jacobian-vector product:
OP:
Ress (1)
85
(53)
aP:
JEV
BAj arises from the linear approximation of the infection dynamics. Thus, Bres(i) quantifies the first-order propagation response of node to perturbations in its neighbors.
where 6, P/ and the partial derivative ap!
aPj
Remark (Recovery Epidemic Threshold). Denote A + 1) = -Pt(L + --)-)((1) Starting
from Eq. C..5
express the system in matrix form as:
(1(t+1) ( (B- AT + (1-1) 1) (t)
(54)
which defines linear dynamical system. For this system to remain stable, the spectral radius of the Jacobian matrix must satisfy:
p ( A A 7) < 1,
(55)
which leads the classical epidemic threshold condition:
3
(56)
Xmaz (A)
27

---

This derivation illustrates that our siidual-basede formulation naturally recovers fundamenttl condi- tions in epidemic dynamics.
Remark (Connection Local Lipschitz Bound). The Jacobian matrix J A- governs the propagation sensitivity with respect to neighbor infection states. It induces a local Lipschitz upper bound:
[t + 2 - (t)l
(57)
The residual term Rres captures the Jucobian-induced local propagation energy, and thus provides a structure-awar signal for selective inference.
Remark 6 (Connection to Discrete Diffusion Operators). Although our model targets stochastic epidemic diffusion, the propagation residual exhibits a structural resemblance to classical diffusion operators. Specifically, the residual node i,
Ries (1) = =3 AA -
(58)
jEV
aggregates state changes from incoming neighbors, analogous the discrete Suplace-Beltrant operator (57V:
- wiy ( 5z): Aʃ. = di JEN.
(59)
which measures local imbalance across mesh. While not a Laplacian the strict sense, our formu- lation shares a key geometric intuition: it emphasizes update prioritization where local dynamics remain active-analogons to high-gradien regions in physical diffusion.
D Experiments
D.1 Experimental Settings
Infrastructure and Implementation. All experiments were conducted on a machine equipped with Intel(R) Xeon(R) Gold 6248 CPU @ 2.50GHz processor with 376 GB Memory. All algorithms implemented in Python with the Networkx library.
Setup of Figure 1. The setup for each subfigure of Figure 1 in the main paper is as follows: (a) We 20 Monte Carlo simulations on 1000-node asymmetric Erdös-Rényi graph (k 10), varying 33 and across a [0.01, 1.0) grid. Each point reports the average node-level infection variance, and we plot its relationship with (87) under fixed initial infection ratio of 10%. (b) We simulate disease spread on 1000-node asymmetric Erdös-Rénn Rényi graphs with varying target average degree k {0.5, I,.., 20). For each graph, we randomly infect 10% of nodes and compute the average node-level variance over a 6 x 6 grid of (3,7) E [0.01, 0.2). We then analyze the relationship between the actual average degree and the mean variance of the estimator. (c) We run 10 Monte
grid {0.01, 0.02. ..... 0.30), we compute (d) We run Monte Carlo simulations on 1000-node asymmetric Erdós Rényi graph (f- = 10), using an initial infection ratio of 1 1%. For each sample size M E (5, 10.....,00 50), we evaluate the mean estimator variance across 6 x grid of (8,7) E [0.01, 0.2).
Carlo simulations on a 1000-node asymmetric Erdós Rényi graph (k = 10), across a Erdös-Rényi
of (3, (0.01, 0.2]. For each initial infection ratio
the mean variance of node-level infection probabilities.
Hyperparameter Setting in Experiments. For RAPID, the number of preheat steps is set 20, and the propagation residual threshold is set to 10-3
Full results for Figure 3. We treat nodes with inferred infection probability above 0.5 infected. Figure in the main paper shows the classification results on hiv-Trans using MC-5, MC-10, PID, and RAPID. Here, present the full results across all six datasets in Figure 5 illustrating each method's ability to distinguish highly infected individuals.
SIR Parameter Setting of More Diseases. To ensure the practical relevance of our research, we reviewed the literature and compiled the infectious period and basic reproduction number (Ra) data for various infectious diseases, as summarized in Table 5 It is important note that we assume well-equipped healthcare environment where infected individuals are isolated and treated promptly upon showing symptoms, effectively preventing further transmission. As result, for diseases listed
28

---

MC-10
IARD
Precision
Precision
Precision
Precision
Precision
Prediion
Rocaall
rocall
Rocall
Rucall
Rokall FX
Rocall
bitcoln-Allpha
hlv-Trans
emall-Enron
EuAll
soc-Epintons
Polkec
Figure 5: Classification metrics (precision, recall, FI) on six datasets.
in the table other than the common cold, the infectious period is taken to be the incubation period of the disease.
In traditional epidemiological studies, can also be defined as the rate at which disease transitions from being infectious non-infectious. Therefore, 7 can calculated as the reciprocal of the infectious period. The SIR model parameters are derived as follows:
Infectious Period
B Ro 7
For simplicity, when the infectious period is reported as range, we use the average of the minimum and maximum values for calculations.
Table 5: Summary of some infectious diseases with their parameters in the SIR model.
Disease
Infectious Pe-
Transmission
Ro
[1/day]
8 [1/day]
riod
Nipah Virus
4 14 days 559
Body fluids
0.5
38
0.1111
0.0556
Andes Hantavirus
7-39 days (me-
Respiratory droplets and
1.2
(0.8-1.6)
0.0556
0.0667
dian 18 days)
39
[55
body fluids
MERS
5 days (2-14 days)
Respiratory droplets
0.5
(0.3-0.8)
0.2
0.1
B1
Ebola
Average
12.7
Body fluids
1.8
(1.4-1.8)
0.0787
0.1417
days
58
Mpox
4-14 days
59
Physical tact, body fluids, respira- tory droplets. sexual (MSM)
2.1
(1.1-2.7)
0.1111
0.2333
20
D.2 Inffuence of Variance on the Reliability of MC Inference
In this subsection, we aim to bridge the conclusion of Theorem 3.1 with empirical evidence, by demonstrating how high variance Monte Carlo (MC) estimators can lead degraded inference accuracy.
We investigate the relationship between Kendall-r and ground-truth per-node infection standard deviation on the hiv-Trans dataset by varying the initial infection ratio o, as shown in Figure 6 We observe that while MC-based methods exhibit performance degradation as uncertainty increases, RAPID and PID maintain relatively stable ranking performance across high-variance regimes.
D.3 Extension to Two-stage Non-reinfection Epidemic Model
Although Theorem 3.3 in the main paper shows that our algorithm, while developed under the SIR model, naturally extends generalized non-reinfection models, this subsection we provide empirical results on the SEIR model to demonstrate its effectiveness in more complex setting.
29

---

HGLS
050
333
Figure 6: Scatter plot and LOESS-smoothed trend lines of Kendall-r versus ground-truth per-node infection standard deviation.
SEIR Model Dynamics. The SEIR model extends the classic SIR framework by introducing an intermediate exposed (E) state capture the incubation period of infection. It models two-stage infection process: individuals first become exposed after contact with infectious nodes, and then transition the infected state after latency period. The continuous-time dynamics are governed by the following ODEs:
dS
dt 3SI,
dE 3S1 oE,
dl aF. 7T, dt dR II,
(60)
dl
dt
where 3 is the infection rate, a the incubation (exposuretto-infectoon rate, and y is the recovery rate. The probability- bassed update equations given by:
1)(t+1)= (t) II (t),,
1- [1 1-I[C-BAAPHOO)
(61)
+P)(t)
Extend RAPID to SEIR. Similar to the idea adopted in the SIR model, for general non-reinfection models, global convergence requires that both Pg + and P; + 0. In particular, for the two main transition stages 5 + E and E I, we define the following residuals:
Exposure-stage residual (from S + E):
RE (i) 3 Σ Aji (P/(() 1000-PP11 (t(t-1))
(62)
jEV
Infection-stage residual (from F. + l):
Rd (i) (P) (t 1))
(63)
Note that once P - 0, the infection infeetio--ttage residual RI + naturally follows. Moreover, R (i) depends solely on the change in the node's own state, whereas our main paper defines the propagation residual to be structure-aware, Hence, we define the global propagation residual for non-reinfection models as:
Rio((i) := RE (i) 3 Σ Ago ( PP))
(64)
JEV
30

---

which is exactly the same our derivation in the main paper for SIR! To verify the effectiveness of our method, we conduct similar experiment the main paper on hiv-Trans.
Experiment. We adopt the same parameter setting as in the Nipah Virus scenario, with & = 1/18 18 and 7 = 1/9, and further infected ratio a 0.01. We use 1000-run Monte Carlo simulation as the ground truth. All other hyperparameter settings are kept consistent with those in the main paper.
0.8 model the transition probability from E T. The initially
Precision
RAPID
08
1,00
Kendal Tau
MC-6
6.6
MC-6
99
Eigervoobor
MC-10
PageRark
PID
Betwoonness
02
Clonenees
MC-100
200
403
R00
500
1030
1200
1400
1800
Runlime (seconds)
Figure Kendall-7 vs. Runtime on Liv-Trans under SEIR model.
Figure 8: Classification metrics on hiv-Trans under SEIR model.
Table SEIR Results on hiv-Trans with a = 0.01. All values are scaled by 10-2, Best results are in bold.
Method
hiv Trans
MAE
(s) 4
MC-5
6.13
3.55a0.21
MC-10
4.01
6.79s0.47
PID
6.23+0.51
10.50=0.14
RAPID
0.82:0.23
2.43:0.12
Figure and Figure&present present the Kendall-7 versus runtime trade-off and the radar chart of precision, Fl and recall rate under the SEIR model on the hiv-Trans dataset, respectively. Table further reports the detailed MAE and runtime values. These results closely mirror those under the SIR setting in the main paper, confirming that our RAPID method remains effective across general non-reinfection models beyond SIR.
D.4 Influence of Distribution of Initially Infected Nodes
As highlighted in the Introduction of the main paper, traditional epidemic modeling often relies on assumptions of random mixing and population homogeneity, which limit its applicability in real-world scenarios. In contrast, RAPID takes the initial infected set Zn as an explicit input, allowing flexible adaptation to different initial conditions. In this subsection, demonstrate that RAPID remains robust under varying distributions of Zo.
Impact of Initial Infection Phase a. In this part, we investigate the impact of different values of a, which reflect different stages of an epidemic at the initial time. While the main paper presents results for 0.01 to simulate the early stage which is the most common setting, additionally evaluate = 0.5 and a = 0.8 to represent mid-stage and late-stage outbreaks, respectively, and report the corresponding results.
a 0.5. The trade-off between Kendall-7 and runtime is illustrated in Figure 9 while the MAE scores are summarized in Table
@ 0.8. The trade-off between Kendall-7 and runtime is illustrated in Figure 10 while the MAE scores are summarized Table
Based on the comparison across different epidemic phases, we make the following observations: (1) Consistent with the results in the main paper, our RAPID algorithm maintains high accuracy across
31

---

10
PC
Pg
PD
Aero The
4enooa Tau
Areal Thu
Drgine
Dnyaee
Dryann
MD:00
Rurtire (eecodas)
Purtie poconda)
Purtinm (sacand))
(a) bitcoin-Alpha
(b) hiv-Trans
(c) email-Enron
KENY
Nermu Tr.
Mare Te
PM
Ingine arveerie
Onjiee Brneenv
Drgan
M0:00
Nartrr (vccnda)
Pautim poconda)
Purdiin (secand))
(d) email-FuAll
(c) soc-Epinions
(f) soc-Pokec
Figure 9: Trade-off between Kendall-Tau and Runtime across six datasets. (a = 0.5)
Table 7: MAE comparison (a 0.5, lower is better). All values scaled by 10-2 Best results in bold.
Dataset
MC-5
MC-10
PID
RAPID
bitcoin-Alpha
4,47:002
3.39:004
2.65:0
2.27:0.04
hiv-Trans
4.15
2.14:0.3
4,24:020
1.02:0.20
email Enron
3.99:003
3.14:0.00
2.79
2.26:0.01
email-BuAll
1.33a001
1.02:0000
0.73:000
0.68:0.00
soc-Epinions
2.99
2.36:0.01
191s001
1.57:0001
vec-Pokec
2.24+000
1.76+0.00
1.35+000
Honoa Tte
Poodl Teu
Po UCA
Engins Faroorr
Nundire (econda)
Purane 34cenda)
Puntinn (scands)
(a) bitcoin-Alpha
hiv-Trans
(c) email-Enron
02
Worma To.
MoS
NCC:
trod
Engres
Egenweor
Cipemady
Egenwoor
Ruttme (Pecoide)
Ruttine 34c0n00)
100
Puriliis (eacandd))
(d) email-FuAll
soc-Epinions
(f)
soc-Pokec
Figure 10: Trade-off between Kendall- Tau and Runtime across six datasets. (a 0.8)
all a
settings, consistently accelerating both MC-based methods and PID, while preserving a runtime comparable to single-run MC simulation. (2) As the initial infection ratio increases, centrality- -asedd baselines become increasingly unreliable, and by a = 0.8, most of them exhibit almost no correlation with ground truth.
Impact Initial Infection Clustering Patterns. this part, we divide the initial infection set into several disjoint and disconnected clusters to examine the impact on different methods. We conduct experiments on the bitcoin-Allg -Alph dataset with an initial infection ratio of a = 0.01. Figure TT demonstrates the robustness of RAPID under varying distributions of initial infection clusters.
32

---

Table 8: MAE comparison (a- 0.8, lower is better). All values are scaled by 10- 2, Best results are in bold.
Dataset
MC-5
MC-10
PID
RAPID
bitcoin-Alpha
1.84
1.34
0,96g0.02
0.94
hiv-Trans
1.68:003
1.26:000
a.31
0.45:0.07
email- Enron
1.62s002
1.29:am
0.92s0m1
0.87:0001
email-
0.57:0000
0.45:0.00
0.30+0.00
0.29:0000
soc-Epinions
4.00
0.95,0.00
0.68:000
0.63:0.01
soc-Pokee
0.89
0.70g0000
0.49g0.00
0.47:0.00
MC.5
MG10
RD
RAPID
0.08
0.07
MAE
0.05
0.04
Number of Disjoint Infection Clusters
Figure 11: Expected MAE vs. Number of Disjoint Infection Clusters.
D.5 Results for more Diseases
According Remark 2 since the discrete SIR simulation aims approximate continuous-time process, we require 3 < and y < 1. Under this regime, the simulation behavior depends primarily on the ratio Rg = 3/7, rather than the specific values of B3 and 7 which aligns with classical cpidemiological theory. Therefore, in our additional experiments, we evaluate the algorithm's performance using representative values of Ro listed in Table
Andes Hantavirus (Rg = 1.2). The Kendall-r versus runtime trade-off is shown in Figure and the MAE comparison across different datasets is presented in Figure 9
10
enn
Pmn UrA
Drgen
Drppnn
Gipemador
Gipemoor
Egenssor
02
Claenes
Runtine (ueceed)
Runtinn (eacoste)
(a) bitcoin-Alpha
(b) hiv-Trans
(c) email-Enroo
Wode The
USA
PD
Dapie
02
22
X
Hordine Oecundal
Rurane (eccedaal
Purlin: (scoan)))
(d) email-EuAh
(e) soc-Epinions
(f) soc-Pokec
Figure 12: Trade-off between Kendall-Tau and Runtime across six datasets. (Andes Hantavirus)
MERS (Ro = 0.5). As MERS share the same Rg with Nipah Virus according to Table the results the same those in main paper.
Ebola (Rg- = 1.8). The Kendall-r versus runtime trade-off is shown in Figure 13 and the MAE
comparison across different datasets is presented in Figure 10
33

---

Table 9: MAE comparison (Andes Hantavirus, lower is better). All values are scaled by 10 Best results are in bold.
Dataset
MC-5
MC-10
PID
RAPID
bilcoin-Alpha
8.21s0.10
6,53gous
8.27
6.38
hiv- TranTrans
14.82.0.0
4.
16.79
5,40:036
email-Euron
6.82.0.05
5.26:0.01
4.52
email EuAll
2.13:0.01
2.05a0.03
1.17:000
soc-Epinions
5.47a0.03
4.33
6.96
4.31
soc-Pokec
3.6420.00
2.86:0000
3.68
3.51a0011
RAn Foo
TOV'S
Kontal Tox
B Pi
HR (ssuy
PO
Konset
Drgine Moroo
ME-10
Fagalaes MC:e0
NC
UC.00
Rundim
(a) bitcoin-Alpha
(b) hiv-Trans
(c) email-Enron
Fio
PO
mR B220
PO
Engins
Deples
Orgas
Fageltes
Pagelaer:
Papelaax
22
MD00
NC-00
(ecunds)
Ruitane (650180)
(400m19))
(d) email-EuAll
(e) soc-Epinions
(f) soc-Pokec
Figure 13: Trade-off between Kendall-Tar Tau and Runtime across six datasets. (Ebola)
Table 10: MAE comparison (Ebola, lower is better). All values are scaled by 10-2, Best results are in bold.
Dataset
MC-5
MC-10
PID
RAPID
bitcoin-Alpha
8.79
6.824008
7.10an.11
4.77
Trans
10.50-0.44
6.29-033
1.87-062
email-Earon
7.490004
5.98
9,27a004
4.39g001
MuAil-EuAAl
2.10a000
1.67a001
14468001
1.02:001
soc- no--Epinions
5.51
4.30
5,41:002
2.99:001
soc-Pokee
4.33:000
3.40a000
3.42:0.00
2.68:000
Mpox (Ro = 2.1). The Kendall-r versus runtime trade-off is shown Figure 14 and the MAE comparison across different datasets is presented in Figure II
Table 11: MAE comparison (Mpox, lower is better). All values are scaled by 10 Best results are in bold.
Dataset
MC-5
MC-10
PID
RAPID
bitcoin-Alphs
5,44,003
4.20
2.71a002
2.68:0.01
hiv-Trans
7.442003
6.03:004
1844061
1.78
email- Enron
5.57+001
4.37-0m
2.83+001
2.77-0.01
email-EuAll
0.96:no0
0.76.0.00
0.48:000
0.47.0.00
sec Epinions
2.84nn01
2.24
1.47.00
1.45.0.01
soc-Pokec
6.74
5.29
3.58
3.52.0.00
Discussion. (1) Across all epidemic settings and datasets, our RAPID method consistently maintains high Kendall-r and low MAE, often achieving the best performance while significantly improving computational efficiency. (2) Under the Andes Hantavirus setting (Ro = 1.2), we observe notably higher variance on the hiv-Trans dataset, aligning with Theorem 3.1 the main paper. However, this increased stochasticity also challenges the fidelity of our reference distribution. In experi-
34

---

10
PC
Pg
PD
Wended Tau
Soge Te
Drgine
Dnyaes
Dryaen
22
Rurtine (eecoda)
Plutime (oconda)
Purtinn (secand))
(a) bitcoin-Alpha
(b) hiv-Trans
(c) email-Cnron
12
1o
KENY
Merma Tru
Koroa Da
Pio
Dngine
Onjeee
M0:00
(vconda)
Plutim (ocondx)
Punlim (acdonab))
(d) email-FuAll
(c) soc-Epinions
(f) soc-Pokec
Figure 14: Trade-off between Kendall-Tan and Runtime across six datasets. (Mpox)
ments, estimate the ground truth infection probability Por using 50 Monte Carlo simulations (on hiv-Trans, we use 1000-run Monte Carlo simulation as ground-truth). While this yields accurate approximations most datasets, the elevated randomness in hiv-Trans makes the reference distri- bution inherently noisy. As result, the MAE values should be interpreted with caution, as they may partially reflect the variance of the reference rather than the bias of the estimators.
D.6 Sensitivity of Hyperparameters
RAPID has two key hyperparameters: the number of preheat steps p used to initialize the inference via PID, and the propagation residual threshold used to control message updates. Figure 15 shows how these hyperparameters affect performance in terms of mean Kendall-7 and MAE.
We observe that increasing p initially improves both Kendall-7 and MAE, more preheating facilitates better initialization. However, beyond moderate value, the performance begins to degrade, indicating that excessive preheating may lead over-propagation and reduced inference quality. For the residual threshold E, we observe that overly loose settings (i.e., large ε) lead to reduced performance, many small but informative updates skipped. However, small, its influence diminishes. This is because the scale of local residuals is largely determined by k,8, further reducing without changing has limited effect. Overall, RAPID maintains stable performance across a wide range of settings, demonstrating strong robustness to both hyperparameters.
becomes very
6:5--
EX275
(822)
Stet 0110
6.80
68109
606
10-113-715-45 1100-11------006--
20-126115-- 18-100
10-4
(a) Kendall-T vS
(b) MAE VS
(c) Kendall-T VS
(d) MAE vs
Figure 15: Sensitivity analysis preheat steps p and propagation residual threshold e.
E More Discussion
E.1 Limitation
Although RAPID achieves high inference accuracy and significant runtime reduction across various networks, several limitations remain. First, our framework assumes a discrete-time approximation of the continuous-tim infection process, and the linearization results rely sufficiently small
35

---

per-time-step transmission and recovery probabilities, i.e., 8, < (see Remark 2}. In practical scenarios with coarse time resolution unscaled parameters, this assumption may not strictly hold, potentially introducing approximation bias. Second, RAPID is designed under the assumption of non-reinfection epidemic models (e.g., SIR, SEIR), where infections are irreversible. Extending the method to reinfection settings such as SIS or SIRS models remains non-trivial, as it would require fundamentally different update dynamics and potentially new convergence guarantees.
E.2
Future Work
Extension to General Epidemic Settings. While our method is developed under the setting of general epidemic settings is promising direction. For
non-reinfection models, extending it reinfective models (e.g.. SIS or SIRS), where nodes can return to the susceptible state, the propagation process becomes recurrent and requires modifying the residual formulation account for cyclical transitions. Moreover, real-worid epidemics often involve time-varying parameters-Suudt as dynamic infection recovery rates (t) and (thhwhiic can be incorporated into our framework by adapting the update rules to operate on temporal sequences of residuals. Finally, in dynamic graphs where nodes and edges evolve over time (e.g., contact networks or mobility patterns), our residual-driver approach can be extended by computing propagation residuals on each snapshot and reinitializing the active node queue accordingly. Together, these extensions would enable our method handle wider range of realistic and complex epidemic processes.
Extension to Graph Neural Networks (GNNs). Our theoretical framework of linear approximation, residual-driven selection, and asynchronous propagation can be naturally extended to enhance Graph Neural Networks. Specifically, message passing GNNs often involves nonlinear transformations, which can similarly benefit from Jacobian- -based linear approximations (explained in Theorem CC. quantify node-level sensitivity neighbor perturbations. By defining propagation residuals based on node feature dynamics, one can design prioritized, residual-guie -ggided asynchronous GNNs that selectively update nodes according to their local propagation significance. Such approach promises significant computational efficiency improvements on large-scale graphs and offers theoretical insights into the interpretability and stability of GNNs. Exploring this connection presents an exciting avenue for future research.
36


Reviews:
[{"review_id": "sOOeUbuGn4", "reviewer": "Reviewer_iUqy", "summary": "Researchers use Monte Carlo simulation to estimate the probability of infection over networks given disease dynamics. However, these methods have a high computational cost. This paper suggests a creative new solution for approximating the probability of node infection quickly. The authors also specify  convergence-criterion for non-reinfection epidemic models and bound Monte Carlo estimation error in an epidemics-over-networks context.", "questions": "1. What are the most predictable weaknesses of the linear approximation used in RAPID?\n\n2. How does one choose $\\epsilon$?\n\n3. In the complexity analysis, is it only possible for nodes to be activated once?\n\n4. What is $\\ell_{ij}$ under equation 5? (I may have missed the definition somewhere)\n\nI think it would clearer to move the ideas in remark 1 of the appendix (under section B.2) to the main body somewhere.", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths: This paper is very clearly written. The authors setup their problem and define their contributions well. RAPID is a creative algorithm, and they demonstrate that it performs well empirically across many metrics and datasets. It seems like a novel, useful, and practical tool for the field. Additionally, their theoretical contributions are interesting and help motivate aspects of their algorithm. \n\nWeaknesses: The error inherent to their theoretical simplifications is not well explained. It seems that they use a lot of approximations in Theorems 3.1 and 3.2, and it’s difficult to understand (especially in Theorem 3.1) when these will be more/less accurate. Additionally, it would be useful to understand which network/disease contexts would predictably result in RAPID experiencing problems relative to Monte Carlo estimation.", "was_revised": true, "final_justification": "My main concern was that \"the error inherent to their theoretical simplifications is not well explained. It seems that they use a lot of approximations in Theorems 3.1 and 3.2, and it’s difficult to understand (especially in Theorem 3.1) when these will be more/less accurate.\" The authors' rebuttal addressed this concern and I now believe this it is a relevant and technically solid paper.", "rebuttal": "We sincerely appreciate your efforts to review our paper and provide valuable suggestions. Below we address each concern in detail.\n\n---\n- w1: The error inherent to their theoretical simplifications is not well explained. \n- **R w1**: The approximation in Theorem 3.1 mainly relies on the sparse graph assumption, while the linearization approximation in Theorem 3.2 is justified by Appendix Remark 1. The error inherent to our RAPID algorithm comes from two main sources: (1) the linearization approximation error when computing the propagation residual, and (2) the independent path assumption used during both the preheating step and state updates, which matches the error sources in Algorithm 1. As discussed in Remark 1 (Appendix), the linearization error can be made negligible by proportionally reducing the epidemic parameters $\\beta$ and $\\gamma$ to sufficiently small values when modeling continuous infection processes.\n\nThe primary source of RAPID's approximation error is the independent path assumption. While this assumption is standard in network epidemiology analysis, it introduces errors from non-independent path interactions (e.g., network loops). As shown by [1], Algorithm 1 is exact on tree graphs and provides rigorous upper bounds for the number of infected individuals on arbitrary networks. [2] demonstrates that this approach typically yields accurate estimates on real sparse networks for a broad class of spreading dynamics. Therefore, RAPID’s approximation error is primarily influenced by graph sparsity and local structure: **it achieves high accuracy on commonly encountered sparse or locally tree-like networks**, while on denser networks it may overestimate marginal infection probabilities—but still provides a meaningful worst-case estimate, which is valuable for robust epidemic assessment. As shown in Table 3, RAPID achieves highly accurate results with MAE of 0.0127 and 0.0103 on the sparsest networks (hiv-Trans and email-EuAll), respectively.\n\n---\n- q1: The most predictable weaknesses of the linear approximation used in RAPID.\n- **R1**: As discussed in Appendix Remark 1, epidemic parameters $\\beta,\\gamma$ need to be sufficiently small for the linear approximation to be accurate. If the parameters are large or the network is dense, RAPID may underestimate propagation residuals by neglecting higher-order effects, leading to missed activations for some nodes. The table below (bitcoin-Alpha) empirically demonstrates that smaller $\\beta$ values result in lower MAE:\n| $\\beta$ | $\\gamma$ | MAE ($\\times 10^{-2}$) |\n| ------- | -------- | ---------------------- |\n| 0.2     | 0.4      | 6.86±0.08              |\n| 0.1     | 0.2      | 5.72±0.10              |\n| 0.05    | 0.1      | 4.25±0.06              |\n| 0.01    | 0.02     | 3.01±0.11              |\n\n---\n- q2: How to choose $\\epsilon$.\n- **R2**: We have provided sensitivity analysis for both preheating steps $p$ and residual threshold $\\epsilon$ in Appendix Section D.5 and Figure 10. For $\\epsilon$ specifically, our analysis shows that large values skip informative updates while very small values have diminishing influence since residual scales are approximatedly bounded by $\\bar{k}\\beta$. In our experiments, $\\epsilon=10^{-3}$ works well across datasets. Generally, $\\epsilon$ should be 1-2 orders of magnitude smaller than $\\bar{k}\\beta$ to capture significant state changes while maintaining efficiency.\n\n---\n- q3: Is it only possible for nodes to be activated once in the complexity analysis?\n- **R3**: No, in our algorithm, nodes can be activated and updated multiple times during asynchronous propagation. In our worst-case complexity analysis, we account for up to $\\mathcal{O}(N)$ node activations. Here we present statistics on activation frequency versus node count for the bitcoin-Alpha dataset:\n| activate times | 0    | 1    | 2    | 3    | 4    | 5    |\n| -------------- | ---- | ---- | ---- | ---- | ---- | ---- |\n| Node count     | 35   | 3730 | 12   | 2    | 3    | 1    |\n\nWe can see from the table that most nodes are activated once, making RAPID highly efficient.\n\n---\n- q4: $\\ell_{ij}$ under equation 5.\n- **R4**: Sorry for the confusion. $\\ell_{ij}$ represents the path length between \nnodes $i$ and $j$. We will add this to Table 1 for clarity.\n\n---\n- q5: Content arangement.\n- **R5**: We will move Remark 1 to precede the linearization analysis (i.e., starting from line 157 in the main text). Thank you for the feedback!\n\n---\n[1] Karrer, Brian, and Mark EJ Newman. \"Message passing approach for general epidemic models.\" Physical Review E—Statistical, Nonlinear, and Soft Matter Physics 82.1 (2010): 016101.\n\n[2] Lokhov, Andrey Y., Marc Mézard, and Lenka Zdeborová. \"Dynamic message-passing equations for models with unidirectional dynamics.\" Physical Review E 91.1 (2015): 012811."}, {"review_id": "yaG2564QBs", "reviewer": "Reviewer_MyzN", "summary": "This manuscript proposed 3 theoretical analysis on propagation model, and an algorithm called RAPID (Residual Aware Propagation for Infection Dynamics) based on the theoretical analysis, to efficiently approximate disease spread over networks. It addresses the high computational cost of traditional Monte Carlo (MC) simulation-based approaches by proposing three theoretical contributions:\n1. A variance lower bound for the MC estimator\n2. A linear approximation of nonlinear epidemic dynamics\n3. A convergence condition for non-reinfection epidemic models\nBased on these theoretical insights, the authors build RAPID to estimate individual-level infection dynamics more efficiently. The algorithm is tested on multiple datasets and shows promising improvements in runtime and comparable accuracy. The supplementary material also discusses extension to the SEIR model and provides a hyperparameter sensitivity analysis.", "questions": "1. Could the authors provide more insight or empirical justification for the preheating phase? Like what is the theoretical rationale behind using this initialization step? How should p be selected? Will that be possible if the authors could conduct ablation study on the preheating phase’s impact?\n2. I checked the code, seems like bitcoin-Alpha data is not under /data/.\n3. In paper 5.1 Baselines, the authors list Network centrality measures, MC-based inference, and probability-based inference (PID), but in all results tables, there are MC-5, MC-10, MC-50, PID, so where is Network centrality measures and how it works?\n4. In manuscript, why MC-50 showed in Table 4 but not in Table 3?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. The theoretical analysis looks solid.\n2. The RAPID algorithm (and the baseline PID algorithm) is well-structured and clearly presented.\n3. The authors conduct experiments across multiple datasets and include a detailed hyperparameter sensitivity discussion.\n4. SEIR extension and propagation modeling on individual level add applicability and relevance.\n\nWeaknesses:\n1. Like authors have discussed, the model is limited to non-reinfection dynamics, which restricts its scope for diseases like COVID-19 or flu where reinfection is a factor.\n2. The preheating phase is not fully justified. Though the authors conducted sensitivity study, there is no ablation study showing its impact, and to choose the proper value remain unclear to me.\n3. Some baseline experiments results are not very clear, see questions 3 and 4.", "was_revised": true, "final_justification": "The authors rebuttal addressed my concerns, so I update the rating.", "rebuttal": "We sincerely appreciate your efforts to review our paper and provide valuable suggestions. Below we address each concern in detail.\n\n---\n- w1: The model is limited to non-reinfection dynamics.\n- **R w1**: Our method targets non-reinfection epidemic models (SIR and variants), which represent a well-established and widely important problem setting in epidemic modeling. This framework naturally applies to many practical scenarios: acute outbreaks (SARS, MERS), high-fatality diseases (Ebola, Marburg), vaccine-preventable diseases (measles, MPox), and cases where immunity duration exceeds analysis time frames. Extensive prior work in network epidemiology focuses on this same model class [1,2], reflecting its fundamental importance. \n\nOur contribution achieves significant computational improvements for these established and practically relevant models. We plan to extend our algorithm to reinfection diseases in future work. \n\n---\n- q1: Insight or empirical justification for the preheating phase.\n- **R1**: The preheating phase is designed to **ensure that the linear approximation error remains small** when the epidemic parameter $\\beta$ is not sufficiently small. Theoretically, if both $\\beta$ and $\\gamma$ are proportionally reduced to very small values according to Remark 1 in the Appendix, the linear approximation becomes highly accurate and preheating is unnecessary. However, in our experiments with $\\beta=1/18$ and moderately dense networks like email-Enron ($\\bar{k}=10.02$), the product $\\beta\\bar{k}$ is not much less than 1, resulting in non-negligible linearization error. When further scaling of parameters is not practical, the preheating phase guarantees that $\\max_{v\\in\\mathcal{V}} P_I^v\\leq \\delta$, so that $\\beta\\bar{k}\\delta\\ll1$ and the linear approximation remains valid. Preheating iterates rapidly as only a small fraction of nodes are initially affected. Therefore, we recommend choosing the number of preheating steps $p$ based on a target $\\delta$. Our sensitivity analysis in Appendix D.5 explores $p$ values from 0 to 50 on email-Enron, effectively including both ablation ($p=0$) and varying preheating, providing a more comprehensive understanding than a simple ablation study.\n\n---\n- q2: Bitcoin-Alpha data is not found under `/data/`.\n- **R2**: Sorry for the confusion. We uploaded bitcoin-Alpha under the original filename \"soc-sign-bitcoinalpha\". We did not upload soc-Pokec due to file size limits, but it can be downloaded from Stanford's SNAP Dataset (social networks section). Our code includes the necessary preprocessing logic for this dataset.\n\n---\n- q3: Where is Network centrality measures and how it works.\n- **R3**: Figure 2 shows the Kendall-tau rank correlation and runtime trade-off between RAPID and **baselines including network centrality measures** against MC-50. We use node centrality rankings (e.g., degree, betweenness) as proxies for infection probability rankings, as high-centrality nodes are commonly considered high-risk in epidemic studies before [3,4]. \n\nWhile centrality measures show some alignment with true infection probabilities in certain contexts, no single centrality measure consistently ranks nodes by infection probability. This limitation becomes more pronounced at higher initial infection ratios $\\alpha$, as shown in Appendix D.3.\n\n---\n- q4: Why MC-50 showed in Table 4 but not in Table 3.\n- **R4**: In our experimental setup, MC-50 serves as the ground truth for infection probabilities. Therefore, Table 3 shows MAE relative to this baseline, while Table 4 compares absolute runtime performance including MC-50.\n\n---\n[1] Karrer, Brian, and Mark EJ Newman. \"Message passing approach for general epidemic models.\" Physical Review E—Statistical, Nonlinear, and Soft Matter Physics 82.1 (2010): 016101.\n\n[2] Lokhov, Andrey Y., Marc Mézard, and Lenka Zdeborová. \"Dynamic message-passing equations for models with unidirectional dynamics.\" Physical Review E 91.1 (2015): 012811.\n\n[3] Bell, David C., John S. Atkinson, and Jerry W. Carlson. \"Centrality measures for disease transmission networks.\" Social networks 21.1 (1999): 1-21.\n\n[4] Cohen, Reuven, Shlomo Havlin, and Daniel Ben-Avraham. \"Efficient immunization strategies for computer networks and populations.\" Physical review letters 91.24 (2003): 247901."}, {"review_id": "dRw7783bkG", "reviewer": "Reviewer_7Sx7", "summary": "This paper addresses a stochastic graph/contact network-based epidemic inference problem with the SIR equations as the backbone. The problem is coined \\textbf{\"Individual-Level Epidemic Inference\"}, where the goal is to estimate the steady-state probability distribution of the 3 states: Susceptible, Infectious and Recovered for each node in the graph. \n\nIn particular, the authors first analyze the efficiency (variance of the estimator) of Monte Carlo-based simulation methods with respect to the network structure and SIR model parameters. Then, they analyze a proposed baseline Propagation for Infection Dynamics (\\textbf{PID}) that relies on message passing updates of the SIR probabilities over time and show the neighborhood-level approximations and global convergence, which are then utilized to derive a more computationally efficient algorithm coined Residual-Aware Propagation for Infection Dynamics (\\textbf{RAPID}). Relying on the theoretical results of convergence, they define a \\textbf{propagation residual} term that is used to determine whether to update a node or not, thereby lowering the overall number of nodes that need to be updated. Moreover, worst-case time complexity is derived for RAPID.\n\nEmpirical results include a variety of graph-based datasets, including an undirected graph, and is based on the SIR parameters of the Nipah Virus. The accuracy and computational efficiency of RAPID are demonstrated and are clearly more superior than both Monte Carlo simulation and PID.", "questions": "- Although it is not explained in the paper (which it should be), the Monte Carlo simulations have stochasticity coming from random sampling of the initial infection node set (as I found out in the code https://anonymous.4open.science/r/rapid-8080/simulations/mc.py). What is the reason for not doing this for PID or RAPID? I would have thought that different initial conditions may yield different steady state results, and therefore you can get a distribution over the 3 states over all the random seeds?\n\n- Can this framework be transferred into the Bayesian inference setting with infection/deaths observations of pathogens (e.g. COVID-19)? \n\n- Why is RAPID's accuracy higher than PID, considering that it is an approximation to PID? Is it because it is converging faster than PID? But then shouldn't all models be run until convergence in your experiments?\n\n- It is said that the ground-truth infection probabilities are calculated using 50-run Monte Carlo simulations. How accurate are these results (maybe hard to tell as this is a simulation) and how big are the variance? If the variance is not negligible, then it is not a very reliable ground-truth.", "limitations": "- I think there is not enough discussion of the limitations of both their modeling framework and the proposed RAPID algorithm, particular its application to real world problems such as disease modeling. \n- The variance is mentioned at the beginning for Monte Carlo, but then not analyzed for PID and RAPID. \n- I see no issues with negative societal impacts of the work since this is pure methodological work", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- Many theorems are proposed to address the properties of Monte Carlo simulation and PID\n\n- The efficiency and accuracy are clear compared to the selected baselines\n\n- The proposed algorithms are neatly implemented/proposed and they are easy to follow and justify (based on the theoretical results)\n\nWeaknesses:\n- The variance lower bound is proved in Theorem 3.1 for Monte Carlo, but it is not clear what purpose it serves as there is no comparison to PID or RAPID, both empirically or theoretically. Empirically, it would at least help if the confidence intervals were shown.\n\n- The experiments are all somewhat \"synthetic\" since they use the Nipah Virus parameters on different graphs. Therefore I think there needs to be better and more realistic experimental settings that make the case that RAPID can be used for infectious disease modeling. In addition, the ground-truth is taken to be the Monte Carlo simulation results, but it would have been better if the results were compared against actual observations (e.g. if modeling COVID spread [1], you can look at the actual observed infection/death counts, $R_t$ values or just the general trend of infections). \n\n- I also think the vast literature of inference of SIR models using Bayesian inference (e.g. approximate Bayesian computation (ABC) or MCMC) are not mentioned or compared with at all, reducing the paper's significance. \n\n[1] https://www.imperial.ac.uk/media/imperial-college/medicine/sph/ide/gida-fellowships/Imperial-College-COVID19-NPI-modelling-16-03-2020.pdf", "was_revised": true, "final_justification": "I am satisfied with the authors response to my concerns and there is sufficient additional evidence to improve my score", "rebuttal": "We sincerely appreciate your efforts to review our paper and provide valuable suggestions. Below we address each concern in detail.\n\n---\n- w1: Purpose for the variance lower bound proved in Theorem 3.1 for Monte Carlo.\n- **R w1**: The variance lower bound proved in Theorem 3.1 for Monte Carlo both motivates the development of efficient deterministic methods and highlights scenarios where MC simulations become computationally expensive—precisely the cases where RAPID offers the greatest advantage. Theorem 3.1 analyzes how Monte Carlo estimator variance depends on network structure and epidemic parameters $\\beta,\\gamma$, showing that under certain conditions, this variance can become very large. This high variance is intrinsic to the network itself, as discussed in Remark 1 and empirically validated on ER graphs in Figure 1. For example, small-world networks like hiv-Trans (sparse with small diameter) show higher MC simulation variance than other networks like email-EuAll under identical settings (also shown in **R4**), necessitating MC-1000 for stable, reliable results.\n\nIn contrast, PID and RAPID are deterministic methods that do not involve sampling, so they do not have estimator variance or confidence intervals. Their accuracy depends only on approximation error with respect to the true infection probabilities, not on stochastic variation.\n\n---\n- w2: The experiments are all somewhat \"synthetic\".\n- **R w2**: Due to its theoretical nature, both classical [5,6] and modern work [2,3] in network-based epidemiology rely heavily on simulation-based validation. However, we have considered **realistic epidemic settings** by using hiv-Trans, a real-world HIV transmission network from the U.S. (1988-2001) collected by the National Addiction & HIV Data Archive Program [1]. Other datasets like email-EuAll and bitcoin-Alpha are commonly used for epidemic simulations [2,3], as viral spread shares similarities with rumor propagation and computer viruses propagation. Following your suggestion, we added a hospital contact network derived from patient-provider interactions at Carilion Hospital, Virginia [4]. This dataset contains 11,810 nodes and 30,994 edges (undirected edges converted to bidirectional). Results compared against MC-1000 (for sufficiently small variance) are shown below, and we will incorporate these findings into Figure 2, Figure 4, and Tables 2-4.\n\n|             | Kendall-tau ($\\times 10^{-2}$) | MAE ($\\times 10^{-2}$) | Runtime (s)     |\n| ----------- | ------------------------------ | ---------------------- | --------------- |\n| **RAPID**   | **56.77±0.01**                 | **2.64±0.49**          | **1.07 ± 0.00** |\n| PID         | 56.76±0.01                     | 5.67±0.51              | 3.56 ± 0.01     |\n| MC-5        | 30.80±0.83                     | 13.01±0.35             | 5.81±0.51       |\n| MC-10       | 32.73±0.06                     | 10.78±0.44             | 13.46±1.14      |\n| Degree      | 54.28±0.01                     | --                     | 0.00± 0.00      |\n| Eigenvector | 29.78±0.00                     | --                     | 0.33± 0.00      |\n| PageRank    | 54.28±0.01                     | --                     | 0.18± 0.01      |\n| Betweenness | 47.80±0.01                     | --                     | 2.77± 0.02      |\n| Closeness   | 29.18±0.06                     | --                     | 1.10± 0.01      |\n\n---\n- w3: Not compared with Bayesian inference (e.g. approximate Bayesian computation (ABC) or MCMC).\n- **R w3**: Bayesian methods (e.g., ABC, MCMC) solve the inverse problem: estimating epidemic parameters from observed time-series data (daily cases, deaths, etc.). Our RAPID method solves the inference problem: given known epidemic parameters and contact network structure, efficiently computing node-level infection probabilities at convergence. These are fundamentally different computational tasks with different inputs (time-series vs. network structure) and outputs (parameter estimates vs. node probabilities).\n\n---\n- q1: The Monte Carlo simulations have stochasticity coming from random sampling of the initial infection node set.\n- **R1**: No, the stochasticity in MC simulations comes from random transmission and recovery events during propagation, **not** from sampling of the initial infected nodes. In `simulations/mc.py`, both `run_sir_simulation` and `run_monte_carlo_simulations` use a **fixed set** of initial infected node indices as inputs. The `test_sir_simulation` function, which samples initial seeds randomly, is only used for testing and is **not called by the main code**. The initial infected nodes are selected once in `main.py` (lines 207–208) and are kept the same across all methods (MC, PID, RAPID, centrality measures) to ensure a fair and direct comparison. This follows standard experimental protocol in epidemic modeling and matches our problem definition in the preliminaries (\"given initial infected node set $\\mathcal{I}_0$\"). \n\nAdditionally, as shown in Appendix D.4, we tested different distributions for initial infected nodes, and the conclusions remained consistent, further demonstrating the efficiency and effectiveness of our RAPID algorithm.\n\n---\n- q2: Can this framework be transferred into the Bayesian inference setting.\n- **R2**: Our method and Bayesian inference address different epidemic modeling problems. Our approach focuses on efficiently computing node-level marginal state distributions given known parameters and network structure. In contrast, Bayesian modeling estimates epidemic parameters from macroscopic observations like aggregate infection cases. When complete contact networks are available (e.g., from sensor data or mobility data), our RAPID method can **accelerate forward simulations for methods like ABC**, enabling faster parameter updates through efficient simulation-observation comparisons.\n\n---\n- q3: Why is RAPID's accuracy higher than PID.\n- **R3**: This is an insightful question. As [7] notes in section \"Dynamic Belief Propagation\", when contact graphs contain many **short loops**, nodes within these loops cyclically influence each other's states over time, reducing the accuracy of the original PID algorithm. Our RAPID algorithm improves upon this through asynchronous max-heap iterations that **accelerate convergence** and selective updates that **avoid some short loops**, resulting in higher accuracy than PID.\n\n---\n- q4: How accurate are 50-run Monte Carlo simulations.\n- **R4**: This is an important methodological concern. We provide the standard deviation of global mean infection probability for MC-50 across datasets (see table below; for hiv-Trans and carilion-Hospital, we use MC-1000 for higher reliability). For computational efficiency, we use MC-50 as baseline on large networks, and report the standard deviation across independent simulations as error bars in Table 3 and Table 4, ensuring that stochasticity is fully accounted for and avoiding bias from single-simulation outliers. These standard deviations and error bars (e.g. 1.27±0.47 for RAPID on hiv-Trans in Table 3) are consistently one to two orders of magnitude smaller than the effect sizes (e.g., MAE), confirming that MC-50 is sufficient for stable inference in practice. When propagation variance is higher (as in hiv-Trans and carilion-Hospital), we switch to MC-1000 to ensure robustness.\n\n| bitcoin-Alpha | email-Enron | email-EuAll | soc-Epinion | soc-Pokec | hiv-Trans* | carilion-Hospital* |\n| ------------- | ----------- | ----------- | ----------- | --------- | ---------- | ------------------ |\n| 0.001956      | 0.001144    | 0.000143    | 0.000090    | 0.000018 | 0.002580   | 0.004662           |\n\n**High-variance datasets use MC-1000 as baseline.*\n\n\n\n---\n- q5: Paper Formatting Concerns.\n- **R5**: Thank you for pointing out. We will delete the repeated \"variance of\" in Line 113 and repeated \"state\" in Line 76. We will also change the title of Table 2 to \"Dataset Statistics\".\n\n---\n[1] Morris, Martina, and Richard Rothenberg. \"Hiv transmission network metastudy project: An archive of data from eight network studies, 1988--2001.\" (2011).\n\n[2] He, Yinhan, et al. \"Demystify Epidemic Containment in Directed Networks: Theory and Algorithms.\" Proceedings of the Eighteenth ACM International Conference on Web Search and Data Mining. 2025.\n\n[3] Ru, Xiaolei, et al. \"Inferring patient zero on temporal networks via graph neural networks.\" Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 37. No. 8. 2023.\n\n[4] Adhikari, Bijaya, et al. \"Fast and near-optimal monitoring for healthcare acquired infection outbreaks.\" PLoS computational biology 15.9 (2019): e1007284.\n\n[5] Prakash, B. Aditya, et al. \"Threshold conditions for arbitrary cascade models on arbitrary networks.\" Knowledge and information systems 33.3 (2012): 549-575.\n\n[6]Karrer, Brian, and Mark EJ Newman. \"Message passing approach for general epidemic models.\" Physical Review E—Statistical, Nonlinear, and Soft Matter Physics 82.1 (2010): 016101.\n\n[7] Lokhov, Andrey Y., Marc Mézard, and Lenka Zdeborová. \"Dynamic message-passing equations for models with unidirectional dynamics.\" Physical Review E 91.1 (2015): 012811."}, {"review_id": "NUCdKVyy6t", "reviewer": "Reviewer_wj6a", "summary": "This paper addresses the problem of estimating node-level infection probabilities at convergence under the stochastic SIR (Susceptible-Infected-Recovered) model on large contact networks. It begins by deriving a lower bound on the variance of Monte Carlo (MC) estimators, highlighting the impact of transmission parameters and network structure on simulation cost. The authors then propose a linear approximation to the nonlinear infection dynamics, and prove a convergence condition for non-reinfection models. Building on these theoretical insights, the paper introduces RAPID, a deterministic and residual-aware propagation algorithm that selectively updates nodes based on estimated influence from neighbors. RAPID is empirically evaluated on six real-world networks, showing comparable accuracy to multi-run MC simulations with significantly reduced runtime.", "questions": "1. **Clarify relevance to NeurIPS.** The paper currently reads as a computational epidemiology or network modeling study, with no learning component and limited connection to the broader ML community. If there is a machine learning angle—e.g., inference under uncertainty, approximation of stochastic processes, or use of RAPID as part of a learning pipeline—please make this connection explicit. Without it, it's difficult to see how the work fits within the NeurIPS scope.\n\n2. **Justify novelty beyond existing approximation methods.** The use of linear approximations and deterministic propagation resembles techniques already present in the literature (e.g., Fokker–Planck, mean-field approximations, and message passing). Please clarify what’s truly new here: either in the theoretical analysis, the algorithmic contribution, or the application framing.\n\n3. **Use more realistic contact network data.** The current experiments are based on communication or social graphs that don’t reflect how physical contact or transmission actually occurs. To better support the practical value of RAPID, please consider evaluating on more appropriate datasets—e.g., **time-resolved proximity networks** from **Sociopatterns** (e.g., high school, hospital, workplace settings), **mobility-derived contact graphs** from datasets like **SafeGraph**, or **Bluetooth-based contact traces** (e.g., from MIT's Reality Mining or COVID-related studies). Showing that RAPID produces meaningful predictions on these real-world contact networks—despite soundness concerns—could help demonstrate practical utility.\n\n4. **Clarify when your approximations are accurate.** The theoretical results rely on assumptions like independence of infection paths and small infection probabilities. Can you provide intuition or empirical evidence on when your approximations hold or break down?\n\n**What could change my evaluation:** A clear and convincing explanation of how this work contributes to machine learning, along with stronger justification for its novelty and practical impact, would help address my main concerns.", "limitations": "No. The paper does not discuss potential negative societal impact, though it is unlikely to have one given the focus on epidemic simulation.", "rating": 2, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 1, "originality": 1, "strengths_and_weaknesses": "**Strengths:** The paper is clearly written, well-organized, and technically competent. The authors thoughtfully implement a deterministic approximation algorithm (RAPID) for node-level inference in SIR epidemic models and benchmark it on several real-world networks. The residual-based propagation idea is a reasonable engineering technique to improve computational efficiency, and the empirical runtime comparisons are thorough. The paper also provides a self-contained narrative connecting theoretical motivation, algorithm design, and experiments, which helps with clarity.\n\n**Weaknesses:** Despite its technical completeness, the paper lacks significance and relevance to the NeurIPS community. It is not a machine learning paper in any meaningful sense—there is no learning component, no connection to generative modeling, deep learning, or agentic AI—and it is difficult to imagine which NeurIPS area the paper would fit into if accepted. The core problem of estimating infection probabilities under SIR dynamics is well-studied, and the approximations proposed here (e.g., linearization of nonlinear dynamics, residual propagation) are reminiscent of existing approaches such as the Fokker–Planck formulation of Langevin dynamics and PDE-based moment matching methods. The theoretical results rely heavily on strong assumptions (e.g., independence between infection paths, mean-field approximations), which cast doubt on the validity of the variance bound and the linearized update at the node level. These assumptions are neither controlled nor justified, and the results risk being misleading if interpreted as rigorous. The convergence theorem is also superficial, essentially restating a trivial absorbing property of SIR processes. On the empirical side, the datasets used are either outdated or loosely related to actual contact networks, and more realistic options (e.g., temporal mobility or sensor-based proximity networks) are overlooked. Overall, the paper offers neither new theoretical insight nor practical modeling contributions that rise to the level of significance expected at NeurIPS.", "was_revised": true, "final_justification": "This paper presents RAPID, a deterministic algorithm for scalable epidemic inference on contact networks. The method is technically sound, well implemented, and clearly explained. I appreciate the authors’ responsiveness during the discussion and their efforts to improve the empirical scope, including the addition of a real-world dataset and clarification of theoretical assumptions.\n\nThat said, my evaluation remains unchanged. The paper does not involve learning, estimation, or data-driven modeling, and its connection to machine learning—as typically represented at NeurIPS—is limited. While the algorithm may be valuable within epidemic modeling or network science, I do not find the contribution sufficiently aligned or impactful in the context of modern ML research. I therefore maintain my initial rating.", "rebuttal": "We sincerely appreciate your efforts to review our paper and provide valuable suggestions. Below we address each concern in detail.\n\n---\n- q1: Clarify relevance to NeurIPS.\n- **R1**: Thank you for the comment regarding NeurIPS relevance. We respectfully point out that the NeurIPS 2025 Call for Papers explicitly welcomes research in probabilistic methods, scalable inference, optimization, theory, and machine learning for sciences—including health, network science, and the natural sciences. Our work addresses a core challenge in efficient, deterministic inference for structured infection stochastic processes on large networks, bridging algorithmic theory, scalable probabilistic modeling, and ML for science. We believe RAPID addresses a key bottleneck for **scalable probabilistic inference under uncertainty on networks**, which are central to many areas of modern ML. \n\nFurthermore, probabilistic inference on graphs is a classic topic in machine learning as evidenced by Belief Propagation (BP), which was first published at AAAI’82 [1] and remains foundational in the field. We thus believe that our RAPID algorithm and its advances in scalable, deterministic inference will be of significant interest to the NeurIPS community.\n\n---\n- q2: Justify novelty beyond existing approximation methods. \n- **R2**: As stated in our introduction, our contribution is twofold: (1) we derive a **variance lower bound** for Monte Carlo estimators on large contact networks, revealing how reproduction number, average out-degree, initial infection ratio, and simulation count affect estimator variance. This result is also empirically validated in Figure 1; (2) we develop **RAPID**, an efficient epidemic inference algorithm that innovatively replaces the residual in classical LocalPush algorithms with Jacobian-based perturbation terms, enabling **asynchronous, selective updates** instead of synchronous iterations. This residual-driven approach achieves **4-12x** computational speedup while maintaining accuracy. We also establish worst-case complexity analysis and derive connections between propagation residuals and epidemic thresholds. Extensive experiments validate our method's effectiveness and efficiency. Reviewers iUqy and MyzN both recognized the novelty and practical impact of our algorithm.\n\nRegarding the approximation methods mentioned, we have clarified their relationship to our algorithm in the preliminaries and related work. **Belief Propagation** (a variant of message passing) operates on factor graphs with sum-product updates for general probabilistic inference; in fact, our PID baseline (Algorithm 1) is equivalent to the BP implementation for epidemic diffusion on contact networks, as in [6]. **Mean-field approximation** assumes independence among variables to simplify joint distributions and forms the foundation of traditional MP/BP methods. **Fokker–Planck equations** describe the global density evolution of continuous systems via partial differential equations, and are unrelated to our discrete, network-based approach.  \n\nRAPID advances beyond epidemic BP by **pioneering the use of a local push framework and Jacobian-based residuals for forward inference in nonlinear dynamics**. This asynchronous, selective propagation strategy is not only novel but also highly efficient, making RAPID widely applicable to disease modeling, rumor spreading, and general network-based diffusion processes that require scalable, deterministic inference.\n\n---\n- q3: Use more realistic contact network data. \n- **R3**: Thank you for the suggestion. Contact networks derived from mobility data providers like SafeGraph would indeed be valuable. However, we have also considered realistic settings by using hiv-Trans, a real-world HIV transmission network from the U.S. (1988-2001) collected by the National Addiction & HIV Data Archive Program [2]. Other datasets like email-EuAll and bitcoin-Alpha are commonly used for epidemic simulations [3,4], as viral spread shares similarities with rumor propagation and computer viruses. Following your suggestion, we added a hospital contact network derived from patient-provider interactions at Carilion Hospital, Virginia [5]. This dataset contains 11,810 nodes and 30,994 edges (undirected edges converted to bidirectional). Results compared against MC-1000 (for sufficiently small variance) are shown below, and we will incorporate these findings into Figure 2, Figure 4, and Tables 2-4.\n\n|             | Kendall-tau ($\\times 10^{-2}$) | MAE ($\\times 10^{-2}$) | Runtime (s)     |\n| ----------- | ------------------------------ | ---------------------- | --------------- |\n| **RAPID**   | **56.77±0.01**                 | **2.64±0.49**          | **1.07 ± 0.00** |\n| PID         | 56.76±0.01                     | 5.67±0.51              | 3.56 ± 0.01     |\n| MC-5        | 30.80±0.83                     | 13.01±0.35             | 5.81±0.51       |\n| MC-10       | 32.73±0.06                     | 10.78±0.44             | 13.46±1.14      |\n| Degree      | 54.28±0.01                     | --                     | 0.00± 0.00      |\n| Eigenvector | 29.78±0.00                     | --                     | 0.33± 0.00      |\n| PageRank    | 54.28±0.01                     | --                     | 0.18± 0.01      |\n| Betweenness | 47.80±0.01                     | --                     | 2.77± 0.02      |\n| Closeness   | 29.18±0.06                     | --                     | 1.10± 0.01      |\n\n---\n- q4: Clarify when your approximations are accurate.\n- **R4**: Our approximations are accurate when the contact network is **sparse or locally tree-like**. As mentioned in Remark 1 (Appendix), setting epidemic parameters $\\beta$ and $\\gamma$ to sufficiently small and proportionally reduced values ensures the linear approximation is accurate when modeling continuous infection processes. The primary source of error comes from the independent path assumption in Algorithm 1, which introduces inaccuracies due to non-independent path interactions (such as network loops). However, we emphasize that this is a standard and widely adopted assumption in network-based epidemic modeling.  [6] shows Algorithm 1 is exact on tree graphs and provides rigorous upper bounds for infected individuals on arbitrary networks. [7] proves it typically yields accurate estimations on real sparse networks for a broad class of spreading dynamics. Therefore, RAPID's approximation errors are primarily related to graph sparsity and local structure: it achieves high accuracy on commonly encountered sparse networks or locally tree-like graphs, while on denser networks it may overestimate marginal infection probabilities—but still provides a meaningful worst-case estimate, which is valuable for robust epidemic assessment. As shown in Table 3, RAPID achieves **highly accurate estimates with MAE of 0.0127 and 0.0103 on the sparsest networks** hiv-Trans and email-EuAll, respectively.\n\n\n---\n[1] Pearl, Judea. \"Reverend Bayes on inference engines: A distributed hierarchical approach.\" Proceedings of the Second AAAI Conference on Artificial Intelligence (AAAI-82), 1982, pp. 133–136.\n\n[2] Morris, Martina, and Richard Rothenberg. \"Hiv transmission network metastudy project: An archive of data from eight network studies, 1988--2001.\" (2011).\n\n[3] He, Yinhan, et al. \"Demystify Epidemic Containment in Directed Networks: Theory and Algorithms.\" Proceedings of the Eighteenth ACM International Conference on Web Search and Data Mining. 2025.\n\n[4] Ru, Xiaolei, et al. \"Inferring patient zero on temporal networks via graph neural networks.\" Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 37. No. 8. 2023.\n\n[5] Adhikari, Bijaya, et al. \"Fast and near-optimal monitoring for healthcare acquired infection outbreaks.\" PLoS computational biology 15.9 (2019): e1007284.\n\n[6] Karrer, Brian, and Mark EJ Newman. \"Message passing approach for general epidemic models.\" Physical Review E—Statistical, Nonlinear, and Soft Matter Physics 82.1 (2010): 016101.\n\n[7] Lokhov, Andrey Y., Marc Mézard, and Lenka Zdeborová. \"Dynamic message-passing equations for models with unidirectional dynamics.\" Physical Review E 91.1 (2015): 012811."}]

Author rebuttal:

Meta-review: This paper is recommended for acceptance due to its technical soundness, clear presentation, and the novelty of its proposed RAPID algorithm for scalable epidemic inference. The authors provided a thorough rebuttal that successfully addressed the reviewers' primary concerns, notably by clarifying the practical implications of their theoretical assumptions and by adding a new real-world hospital contact network dataset to strengthen the empirical validation. While one reviewer raised a valid point regarding the paper's scope, the work's contributions to scalable probabilistic inference on networks align well with NeurIPS' focus on theory, probabilistic methods, and machine learning for science.
Decision: Accept (poster)