Approximation and Learning in Network Security Games with Contagion and Uncertainty

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 $(1-1/e)$ 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 $O(\Vert \mathbf{d}{\Vert }_2\sqrt{BT\log (nT)})$ upper bound on surrogate approximation regret, where $B$ bounds the number of defended nodes and $\mathbf{d}$ 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.