acceptodds
Under review as a conference paper at ICLR 2027

Approximation and Learning in Network Security Games with Contagion and Uncertainty

Abstract

Network defense under contagious attacks couples resource allocation with learning, as protecting a node can prevent damage and reveal its otherwise unknown value. We study this problem under a budget constraint and feedback from defended nodes and attacked neighborhoods. For known values, we construct a threshold surrogate that is monotone submodular and quantitatively bounds the original worst-case loss. Enumerating all feasible seeds of size at most three gives a approximation, and a problem-specific maximum-coverage reduction establishes matching hardness for the surrogate with general defending requirements. For unknown values, directly substituting upper confidence bounds into this surrogate is not optimistic because its normalization also depends on the unknown values. We resolve this issue with a normalization fixed by known support bounds. With this oracle, \patch admits an upper bound on surrogate approximation regret, where bounds the number of defended nodes and captures propagation and value scales. Its proof uses observations of selected nodes and requires no uniform observation frequency. Experiments on synthetic and real-world networks assess computational efficiency and show that PatchLearn achieves lower defense loss than baselines using the same UCB rule in the tested settings with heterogeneous node values.

Primary area:
learning theory
Keywords:
learning theory, approximation algorithm, security games, contagious attacks

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_XTRkOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This manuscript examines the issue of contagious attacks in networks where node values are initially unknown and must be determined through repeated interactions. The defender operates within a budget constraint and receives feedback from defended nodes and attacked neighbourhoods. The authors propose PatchLearn, a learning-based defence approach. In the known-value setting, they construct a monotone submodular threshold surrogate intended to bound the original worst-case defence loss. They evaluate PatchLearn using synthetic and real-world networks to assess its computational efficiency and compare its defence performance against baselines. The reported results suggest that PatchLearn achieves lower defence loss in the tested settings with heterogeneous node values. However, the paper would benefit from clearer presentation of the contagious attack threat model, clearer motivation of the proposed approach and more explicit explanation of its game-theoretic setting and how it outperforms state-of-the-art methods.

Critical strengths
  1. The paper considers network defense under contagious attacks while accounting for unknown and potentially heterogeneous node values. This setting is relevant because defense decisions must often be made under resource constraints and incomplete information.
  2. The proposed PatchLearn approach seeks to combine online learning with budget-constrained defense and evaluates its performance on synthetic and real-world networks. This provides a potentially useful basis for studying the trade-offs between learning node importance, computational efficiency, and defense effectiveness.
Critical weaknesses
  1. The limitations of existing approaches and the specific gap addressed by PatchLearn remain insufficiently articulated. These shortcomings make it difficult to identify the paper's precise contribution and assess its relevance to the network security games literature.
  2. The paper lacks to present the threat model that could help to understand the attacker's and defender's roles, objectives, available actions, or interaction model.
  3. The rationale for constructing a monotone submodular threshold surrogate that quantitatively bounds the original worst-case loss needs more clarifications. The authors should explain the purpose and implications of this surrogate, the precise guarantee it provides, and how that guarantee relates to the unknown-value setting.
  4. The term defense loss is not sufficiently defined in the reported performance claims. I have significant concerns about the clarity and completeness of the problem and the justification of the proposed approach.
  5. Although the paper is presented as a contribution to network security games, the threat model and the respective roles, objectives, and action spaces of the attacker and defender are not sufficiently explicit.
  6. The relationship between the known-value optimization problem and the unknown-value learning problem also requires clarification.
  7. The paper should explain how the theoretical guarantees derived from the monotone submodular surrogate relate to the actual defense objective when node values must be learned online.
  8. The claim that PatchLearn achieves lower defense loss in the abstract requires a precise definition of the metric and an explanation of how it is computed.
  9. The paper's presentation requires improvement. Although the general problem of network defense under contagious attacks and uncertain node values is relevant, the motivation, precise research challenge, and distinction from existing literature are not sufficiently clear. In particular, the paper does not appear to provide a dedicated formulation of the threat model or clearly distinguish the attacker's and defender's roles, objectives, and available actions. A more structured presentation of the security model, optimization problem and learning mechanism would make the contribution easier to understand.
  10. The paper addresses an interesting combination of contagious attack propagation, uncertain node values, and budget-constrained defense. However, the paper does not sufficiently explain what fundamental limitation of existing approaches PatchLearn overcomes. A clearer comparison with closely related work and a more explicit statement of the paper's key insights would strengthen its informativeness.
Questions for authors
  1. Could the authors explicitly define the contagious attack model, including the attacker's objectives and available actions, the defender's decision variables and budget constraints, and the mechanism by which attacks propagate through the network? What are the assumptions about the interaction between the attacker and defender?

  2. Patching-GSA provides an approximation guarantee for maximizing the surrogate function, but it is unclear how this guarantee translates to the original problem. Does the resulting solution still provide the same bound on the actual loss for a given threshold (W)? If not, can the authors provide a bound on the actual loss when the surrogate is only approximately optimized?

  3. Patching-GSA Fast reduces the set of candidate seeds to improve computational efficiency. Does this restricted search still provide a theoretical approximation guarantee? If so, under what conditions? If not, can the authors quantify the loss in solution quality caused by this restriction?

  4. PatchLearn provides a sublinear regret guarantee with respect to the surrogate objective. However, does this guarantee translate into a guarantee on the original loss? Can the authors show that PatchLearn approaches the optimal defense strategy for the original problem, or does the residual term in their loss bound prevent such a conclusion?

1 comment

Thank you again for your constructive feedback. As the discussion period draws to a close, we would like to briefly summarize how our previous response addressed your questions and how these concerns are reflected in the revised manuscript.

  • Research motivation and threat model. In our previous response, we explained the distinction from known-value allocation, the role of fixed normalization in learning unknown values, and the actions, objectives, timing, and feedback of the attacker and defender. We have also added the ransomware-recovery and backup-power examples in the second paragraph of the Introduction to explain the practical meaning of local protection and the modeling assumptions.

  • Connection between the surrogate and original defense loss. Our previous answers to Q2 and Q4 explained how approximate surrogate optimization yields an explicit original-loss bound and under what conditions the online guarantee implies convergence to the original optimum. The revised manuscript makes this connection explicit in Sections 3 and 4, distinguishing the vanishing learning contribution from the approximation and coverage residuals. Appendix D.4 further explains the effect of optimization error in approximate implementations.

  • Effect of the restricted search in Fast. Our previous answer to Q3 clarified the scope of the Full approximation guarantee, quantified the additional slack in the loss certificate for Fast, and provided comparisons on 40 matched instances. We have incorporated these experiments into Appendix E.9, including Table 12 and Figure 9, with analysis of the loss gaps relative to MILP and the recorded threshold-search times. This makes the measured cost and benefit of the restricted search available in the paper itself.

We would be grateful if you could revisit our responses and the revised manuscript when time permits. If any concerns remain, we would welcome the opportunity to address them before the discussion closes. Thank you for your time and consideration.

Reviewer_Xz6GOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper is about how to spend a resource constrained defense budget among nodes in a network. They consider an adversary capable of attacking any node, which could compromise other nodes in its neighborhood. Some nodes may be more important to protect given finite defense capabilities, and thus it is important to be able to choose which nodes to protect. This is the central problem the paper is tackling. Two different scenarios are considered:

  • The offline setting, where node values representing how much value there is in protecting a node is assumed to be known.
  • The online setting, where node values are not known and have to be learned over the course of T attack rounds.

The general idea to solve the problem is to minimize a loss on the node values, such that essentially the most amount of node value is protected for the worst-case single node attack. However, the authors introduce a surrogate objective that measure the extent to which a defense allocation achieves a loss below a given threshold, when considering all possible single node attacks.

In the offline case they argue that the optimization problem with the surrogate objective is NP hard, but the idea with the surrogate objective is that it allows them to apply a greedy algorithm to solve the problem approximately with a bound on how close their solution is to the true optimal surrogate value.

As for the online case, the idea is to use upper confidence bounds on mean node values from observations of previous runs, and apply the offline greedy algorithm to a surrogate objective (with fixed normalization) in each round to choose which nodes to protect. The paper includes a regret analysis that bounds the regret of using the PatchLearn strategy compared to an offline benchmark having oracle knowledge of the expected node values.

Finally, they compare the offline and online defense schemes against some baselines on synthetic and real-world graph structures, with synthetically created node values, and demonstrate promising results in these settings.

Critical strengths

The paper is well-written and does overall a good job of presenting the problem and the approach taken to solve it. It contains both theoretical results to bound the performance of the method and provide some insights into the approximation limits of the approach and its computational hardness. It appears to contain a fairly significant contribution and novel parts, primarily in the construction of the surrogate objective and the approach to solving the online problem with PatchLearn. The experiments are reasonable under the constraints of the problem setting.

Critical weaknesses

The most significant weakness of the paper is regarding the statistical significance of the experiments. There is no quantification of errors in the reported results, e.g., in table 3, and no discussion regarding this even though there are randomness present in the experiments. Although the results look promising, they are not scientifically rigorous without a proper account of uncertainty and statistical significance. This is my main critique and I would be willing to consider raising my score if this were addressed.

The problem formulation separates the construction of node values from the defense allocation given node values, which seems reasonable to do. However, there could be more discussion around how one could quantify node values in practice. The paper could also benefit from more discussion of some of the assumptions regarding node values and the defense of nodes, e.g., the assumption that allocating less then the required defense resources to a node has no defensive capability.

Questions for authors

My questions for the authors are as follows:

  1. The paper report seemingly good results for PatchLearn, e.g. in table 3. However, there are no error bars or confidence interval reported, or discussion around uncertainty or statistical significance in general. Are the experimental result statistically significant given the randomness in the experiment?
  2. The modeling assumes an unprotected node contribute with its node value to the loss regardless of whether it is a directly attacked node or a distant neighbor of an attacked node. Is this a reasonable assumption?
  3. How realistic is the all-or-nothing defense assumption that a node is completely unprotected if it is allocated less than its required defense resources?
  4. How can one quantify node values in practice?
Reviewer_M9GZOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies network defense under contagious attacks where node values are initially unknown. The defender allocates limited resources to protect nodes on a graph; attacks propagate through neighborhoods, and the defender observes values only at defended nodes and their attacked neighborhoods. The authors construct a threshold-based surrogate objective that is monotone and submodular, enabling a greedy (1−1/e)(1-1/e) approximation for the offline (known-values) setting. They prove a matching NP-hardness result via a gap-preserving reduction from maximum coverage with general defending requirements. For the online setting with unknown node-value distributions, they propose PatchLearn, which combines UCB-style upper confidence bounds with the offline surrogate oracle. PatchLearn achieves a sublinear ρ\rho-regret bound of O(∥d∥2BTlog⁡(nT))O(\|\mathbf{d}\|_2\sqrt{BT\log(nT)}) using only structured partial feedback from selected nodes — no uniform observation frequency assumption is required. Experiments on synthetic (Erdos-Renyi, power-law) and real-world (Twitch, LastFM) networks show that PatchLearn achieves lower cumulative defense loss than baselines under heterogeneous node values.

Critical strengths
  1. Tight approximation with matching hardness. The (1−1/e)(1-1/e) approximation guarantee for the surrogate objective, paired with the problem-specific NP-hardness result showing this ratio is optimal under general defending requirements (Theorem 3.3), is a clean and complete characterization. This goes beyond generic submodularity appeals by establishing tightness through a dedicated reduction that preserves the gap of Feige (1998), making the approximation guarantee definitive rather than merely an application of known tools.

  2. Online learning with structured partial feedback and no uniform observation assumption. The PatchLearn algorithm and its regret bound (Theorem 4.2) are notable because the feedback structure is genuinely non-standard: the defender only observes nodes in the attacked neighborhood union the defended set, and different nodes may be observed at vastly different rates. The analysis avoids uniform-exploration assumptions by tracking per-node observation counts through the vector d\mathbf{d}, yielding an instance-dependent bound. This is a meaningful contribution to the intersection of combinatorial bandits and security games.

Critical weaknesses
  1. Limited scope and practical relevance of the contagion model. The region-based contagion model — where protecting a node prevents loss at that node but does not block propagation — is one specific model among many studied in the security-games literature. The threshold-based surrogate and the entire algorithmic framework depend on this particular structure. The paper does not discuss how the approach might extend to other propagation models (e.g., cascading failures, influence maximization-style models) or whether the surrogate idea generalizes. This limits the paper's impact to a rather narrow problem class, and the practical motivation (who would deploy PatchLearn?) remains underspecified.

  2. Modest experimental improvements and limited scale. The experiments, while competently executed, show relatively moderate improvements over baselines. On the heterogeneous-value experiments (Table 3), PatchLearn's gains over BA-UCB range from 12.9% to 28.0%, but the absolute loss differences are not contextualized against an optimal benchmark. The networks tested are small to moderate (200–7624 nodes), and the online experiments use only T=1000T=1000 rounds. The paper would benefit from larger-scale experiments and a more thorough empirical investigation of when the surrogate-based approach provides substantial practical benefit over simpler heuristics.

Questions for authors
  1. How sensitive is the framework to the specific contagion model? If protection at a node could partially attenuate (rather than fully prevent) loss, does the surrogate remain submodular? What is the broadest class of propagation models for which your approach applies?

  2. The fixed-normalization surrogate uses known support bounds bvb_v. In practice, how would one obtain these bounds, and how does overestimation of supports affect the quality of the defense? The regret bound scales with ∥d∥2\|\mathbf{d}\|_2, which itself depends on the supports — could loose support estimates significantly degrade performance?

  3. The threshold WW is fixed before online interaction begins. The paper mentions it could be "a deployment target or a value selected from independent calibration information." Can you provide guidance on how to set WW in practice? How sensitive is the online performance to the choice of WW beyond the Rand-S sensitivity study?

3 comments
AuthorsOpenReview ↗

Continue Response by Author

W2. Optimal benchmark, longer horizons, and additional networks

Comparison with MILP.

Table 3 in the revised manuscript includes a MILP reference with access to the true mean node values, which are withheld from the learning methods. For each instance, MILP computes a fixed budget-feasible defense minimizing worst-case loss at the true means. We evaluate this defense and all learning methods using the same cumulative worst-case realized-loss metric and paired random value sequences. We conduct ten paired trials per setting on Twitch and LastFM, with T=1000T=1000, k=2k=2, and η=0.4\eta=0.4. Means and standard deviations are in units of 10310^3.

MethodTwitch / LognormalTwitch / Degree-correlatedLastFM / LognormalLastFM / Degree-correlated
MILP (optimal)110.08 ± 11.07194.01 ± 8.7640.27 ± 17.5357.31 ± 28.67
Greedy-UCB131.51 ± 12.97264.49 ± 15.8458.76 ± 20.3996.72 ± 41.37
Greedy-M-UCB138.78 ± 15.21271.85 ± 16.5947.89 ± 22.9378.43 ± 39.85
BA-UCB137.53 ± 15.17224.08 ± 9.3158.33 ± 18.0474.12 ± 31.82
PatchLearn112.70 ± 11.88195.99 ± 7.9843.38 ± 18.7560.43 ± 27.83

PatchLearn achieves the lowest mean loss among the learning methods in every setting. Its relative loss gap to the MILP reference with known means averages 4.14% across the four settings, calculated by averaging the setting-specific relative differences between the reported mean losses. PatchLearn also reduces mean loss by 9.41–18.47% relative to the strongest online baseline.

Longer horizons.

We extend the Twitch and LastFM experiments to T=5000T=5000, retaining the other settings of Table 3 and conducting ten paired trials per value profile. Methods share the graph, values, costs, and random value sequence within each seed. The following table reports cumulative worst-case realized loss in units of 10310^3, as mean ±\pm sample SD.

MethodTwitch / LognormalTwitch / Degree-correlatedLastFM / LognormalLastFM / Degree-correlated
Greedy-UCB658.07 ± 66.471318.54 ± 92.70293.75 ± 99.11481.81 ± 203.76
Greedy-M-UCB694.23 ± 77.241352.08 ± 88.92239.39 ± 115.33391.88 ± 200.01
BA-UCB689.45 ± 77.301119.33 ± 46.87293.95 ± 90.00373.68 ± 158.95
PatchLearn560.89 ± 59.09978.76 ± 39.81217.81 ± 92.16304.34 ± 139.29

PatchLearn retains the lowest mean loss in all four settings. In column order, reductions relative to the strongest online baseline are 14.77%14.77\%, 12.56%12.56\%, 9.01%9.01\%, and 18.56%18.56\%. They are close to the reductions at T=1000T=1000, supporting a persistent advantage as interaction continues. All confidence intervals for the mean paired differences lie below zero, and PatchLearn outperforms all online baselines in almost every paired trial. Appendix E.7 reports the full table, paired comparisons, and experimental settings. Section 5.2 summarizes the conclusion.

Additional networks and larger connected samples.

We extend the evaluation to CondMat and Deezer Europe, whose source networks contain 23,133 and 28,281 nodes, respectively. Using connected samples constructed according to the protocol in Appendix E.7, we conduct ten paired trials per value profile with T=1000T=1000, k=2k=2, and η=0.4\eta=0.4. Node-value and cost generation, UCB updates, feedback, and threshold search follow the preceding experimental settings. Table 4 in the revised manuscript reports cumulative worst-case realized loss as mean ±\pm sample standard deviation, in units of 10310^3.

MethodCondMat / LognormalCondMat / Degree-correlatedDeezer Europe / LognormalDeezer Europe / Degree-correlated
Greedy-UCB67.09 ± 20.90120.25 ± 42.1260.90 ± 26.3881.65 ± 30.73
Greedy-M-UCB45.83 ± 10.6771.63 ± 13.9833.37 ± 10.9850.89 ± 20.10
BA-UCB65.98 ± 16.9376.09 ± 15.1059.37 ± 16.5063.20 ± 23.03
PatchLearn39.68 ± 6.3459.26 ± 11.6431.37 ± 10.0243.46 ± 15.94

PatchLearn achieves the lowest observed mean loss in all four settings. Relative to Greedy-M-UCB, the strongest baseline throughout, reductions are 13.42%13.42\% and 17.26%17.26\% on CondMat and 6.00%6.00\% and 14.61%14.61\% on Deezer Europe, for lognormal and degree-correlated values, respectively. Both networks show larger gains under degree-correlated values, identifying a setting in which the surrogate-based allocation provides greater practical benefit.

Eleven of the 12 paired comparisons remain significant after Holm correction. For lognormal Deezer Europe vs. Greedy-M-UCB, the mean paired difference is −2×103-2\times10^3, with a 95% CI of [−4.26,0.26]×103[-4.26,0.26]\times10^3; this comparison shows a mean reduction with uncertainty that includes zero. Appendix E.7 provides the detailed experimental settings and paired results.

Thank you again for your constructive suggestions. As the discussion period draws to a close, we would be grateful if you could revisit our responses and the revised manuscript when time permits.

The manuscript incorporates the following additions in response to your concerns.

  • Experimental benefit and scale, W2. Section 5.2 and Table 3 add the MILP benchmark and results from ten trials per setting. Table 4 and Appendix E.7 report the additional CondMat and Deezer Europe experiments, while Appendix E.7 also reports the extension to 5,000 rounds on Twitch and LastFM. PatchLearn retains the lowest mean loss among the learning methods in all these settings.

  • Support-bound sensitivity, Q2. Appendix E.8 reports ten paired trials at each bound multiplier. Doubling the supplied bound increases the mean loss of Fixed Fast by approximately 5% in this experiment.

  • Threshold selection and sensitivity, Q3. Appendix C.1 describes threshold search with explicit loss verification, and Appendix E.4 extends the sensitivity study to six networks. The results show why near-complete surrogate coverage still requires checking the original loss against the target.

Our response to W1 and Q1 also explains the intended applications and the extension to fixed fractional protection. We would appreciate any remaining questions and the opportunity to address them before the discussion closes. Thank you for your time and consideration.

Thank you again for your time and constructive feedback. We would be grateful if you could revisit our responses and the revised manuscript before the discussion closes. The manuscript now includes the additional network and longer-horizon experiments, as well as the analyses of support bounds and threshold sensitivity discussed in our responses.

If any concerns remain unresolved, please let us know so that we have an opportunity to address them. We would also appreciate your updated assessment in light of these responses and revisions. Thank you for your consideration.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.