{"id":"8ce78e24-ff6b-417c-8ec8-4973c14e9de9","arxiv_id":"2506.00745","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"This paper gives the first edge-differentially-private algorithms for choosing nodes to vaccinate so that the residual contact network has low maximum degree or spectral radius, with approximation guarantees and experiments.","lead":"The paper presents differentially private algorithms that choose which people to vaccinate by targeting network properties, while keeping social contact edges private. It reduces the problem to a private covering problem and reports good practical tradeoffs between privacy and epidemic control.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem C.7's lower bound uses an infeasible optimum and an impossible subcollection: S1 does not cover I2, and S* can contain {S1,S2}, which covers I2, so the claimed Ω(log n) bound is unproved.","rationale":"The reader's REJECT is well-supported. The central claim of the paper has three advertised contributions: private algorithms for PRIVMAXDEG/PRIVMINSR and lower bounds for explicit solutions. The lower-bound theorem in Appendix C.3 is internally inconsistent: S1 is infeasible for the instance it is claimed to solve optimally, and the collection S* cannot contain multiple copies of the singleton set because S has only two sets. This is not a stylistic or consensus issue but a concrete false premise, so the Ω(log n) lower bound is unproven. The positive algorithmic framework may be salvageable—the reduction to PRIVATEMULSET and the 4-step group-privacy accounting in Algorithm 1 are plausible—but the paper's own headline results include the lower bounds, and the explicit-solution section has additional unresolved issues (e.g., Algorithm 2's stopping rule is described oppositely to the standard AboveThreshold, and the proof of Theorem 4.3 conflates the selected set's marginal utility with the maximum remaining utility). These are repairable in principle, but as submitted the theoretical claims are not reliable. No machine-checked proofs or reproducible code are provided to offset the proof gaps.","tokens_in":20284,"tokens_out":24693,"duration_ms":246230,"concrete_test":"Instantiate Theorem C.7 with α=3, β=1, log n=1, r0=11. Then S1 has 7 copies of e, S2 has 4 copies, and I2 requires r0−β=10 copies. Enumerate the subcollections of S={S1,S2}: {S1,S2} has size 2, contains S1, so it is in S*, and it covers 11 copies, contradicting the proof's assertion that every S∈S* covers at most r0−β−1=9 copies. Recomputing this two-set instance settles that the lower-bound construction is invalid.","verdict_should_be":"REJECT","load_bearing_attack":"The advertised lower bound for explicit solutions (Theorem C.7, and Lemma 4.5 which inherits it) is not established. In the proof, instance I2 has coverage requirement r_e = r0 − β, but S1 is defined with r0 − β − α log n copies of e, so S1 is not a feasible cover of I2; hence the claim 'S1 is the optimal solution, |OPT| = 1' is false. The definition of S* is also impossible as written: the set system S contains only two sets, S1 and {e}×(β+α log n), but S* is described as containing S1 plus up to α−1 copies of {e}. A subcollection can contain at most one copy of the second set, so for α≥2 the subcollection {S1,S2} lies in S* and fully covers I2, contradicting the claim that every S∈S* covers at most r0−β−1 copies. The probability separation Pr[M(I1)∈S*]≤C and Pr[M(I2)∈S*]≥1−C therefore has no valid instance. Since the paper presents these lower bounds as one of its three main contributions, this is a correctness defect in a headline claim, independent of whether the upper-bound algorithms can be repaired.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper initiates the study of edge-differentially private algorithms for choosing vaccination sets that reduce the maximum degree (PRIVMAXDEG) or the spectral radius (PRIVMINSR) of a contact network. The approach reduces these problems to a private multi-set multi-cover problem, provides an implicit-solution algorithm based on the iterative exponential mechanism of Gupta et al. [19], and an explicit-solution variant using the AboveThreshold mechanism. The paper also claims lower bounds showing that any explicit private solution must incur an additive error of Ω(log n) in the coverage requirement, and it reports experiments on synthetic and real-world networks. The main theorem (Theorem 4.2) claims an O((1 + 1/ε') ln|V|)-approximation with high probability for PRIVMAXDEG; Theorem C.7 claims the Ω(log n) lower bound for explicit solutions, and Lemma 4.5 transfers it to PRIVMAXDEG.","tokens_in":20584,"tokens_out":5057,"duration_ms":49761,"significance":"If the results were fully established, they would provide the first edge-differentially private algorithms for two epidemic-control optimization problems that have so far only been studied without privacy, and the explicit-solution lower bound would delineate a fundamental privacy–utility tradeoff. The reduction to multi-set multi-cover and the use of sparse-vector techniques for explicit solutions are natural and potentially useful. However, the lower-bound proof in Appendix C.3 contains a false premise about the constructed instance, and the explicit-solution analysis in Section 4.2 is inconsistent with the stated algorithm. These issues affect headline claims, so the significance is conditional on repair.","major_comments":[{"comment":"The lower-bound construction is not valid as written. In instance I2 the coverage requirement is r_e = r0 − β, but the set S1 is defined with only r0 − β − α log n copies of e, so S1 alone does not cover I2. Therefore the claim 'S1 is the optimal solution, |OPT| = 1' is false for I2; the optimal cover must include additional copies beyond S1. Furthermore, the definition of S* is impossible for the stated set system: S contains exactly two sets, S1 and {e}×(β+α log n), so a subcollection S ⊂ S can contain at most one copy of the second set; the description 'contains S1 and up to α−1 copies of {e}' does not correspond to subsets of S. If α log n ≥ 2, then the valid subcollection {S1, S2} lies in S* and fully covers I2, contradicting the claim that every S ∈ S* covers at most r0−β−1 copies. Consequently the probability separation Pr[M(I1)∈S*] ≤ C and Pr[M(I2)∈S*] ≥ 1−C is not established, and the Ω(log n) lower bound of Theorem C.7 is unproved. Since Lemma 4.5 in Section 4.2 explicitly inherits this lower bound, the paper's third main contribution is not supported.","section":"Appendix C.3, Theorem C.7"},{"comment":"The explicit-solution algorithm and its analysis are inconsistent. Algorithm 2 lines 2–6 define T′ ← 6 ln n/ε′ − Lap(2/ε1), γ_i ← L_i − Lap(4/ε1), and stop at the first k with γ_k ≤ T′. This is the opposite of the standard AboveThreshold rule in Definition B.5, which returns the first index whose noisy query exceeds the noisy threshold. The quantity L_i used in line 4 is never defined in the pseudocode; it first appears in the proof of Theorem 4.3 as the maximum utility after removing the first i nodes, but the algorithm does not state this. In the proof, the sentence 'for i ≥ k̂, L_i ≤ 6 ln n/ε′ but γ_i ≥ T′' is also inconsistent with the stopping condition γ_k ≤ T′, and the subsequent argument that the Laplace noises are 'greater' relies on an unspecified comparison. As written, the proof does not establish the claimed bound Δ(G − ∪_{i=1}^k{π_i}) ≤ D + O(log n/ε′) or the bound k = O(OPT · log n/ε′).","section":"Section 4.2, Algorithm 2 and Theorem 4.3"},{"comment":"The utility proof for the implicit multi-set multi-cover algorithm contains a load-bearing step that is only asserted. The proof states that 'the greedy approximation is a O(ln q) approximation' and therefore the exponential-mechanism process covers the high-utility region with O(OPT ln q) sets, but no proof or precise reference is given for this multi-set multi-cover greedy bound. The standard set-cover greedy analysis does not directly apply to the multi-set multi-cover setting with element multiplicities and residual requirements used here. Since Lemma C.1 is the basis for Theorem 4.2, the main upper bound for PRIVMAXDEG, the O(ln q) approximation claim needs a complete argument or an exact citation that covers this formulation.","section":"Appendix C.1.1, Lemma C.1 and Lemma 4.1"}],"minor_comments":[{"comment":"The variable L_i should be defined in the pseudocode; currently it is used in line 4 but only explained later in the proof of Theorem 4.3.","section":"Section 4.2, Algorithm 2"},{"comment":"There is a typographical error in the displayed definition of OP T_MAXDEG: the condition contains 'S ⊆ V, ,∆(G[V \\ S]) ≤ D' with an extra comma before the maximum-degree condition.","section":"Definition 3.2"},{"comment":"The phrase 'egde-differential privacy' should be 'edge-differential privacy'.","section":"Appendix A"},{"comment":"The privacy parameters in Lemma 5.1 are stated as (Δ²(ε+ε₁), Δ²δe^{(Δ²−1)ε}), but Algorithm 3 sets ε′ = ε/(2 ln(e/δ)) for the set-cover phase, so the composition of the Δ²-fold group privacy with the AboveThreshold step would naturally involve ε′ rather than ε; the statement should be reconciled with the algorithm's parameter choices.","section":"Section 5.1, Lemma 5.1"},{"comment":"The experimental section notes for the explicit-solution experiments that the privacy guarantee was relaxed to the multi-set multi-cover definition rather than the edge-DP definition; this should be stated more prominently, since it weakens the empirical evidence for the edge-DP claims of Section 4.2.","section":"Section 6, Experiments"}],"recommendation":"major_revision","confidential_remarks":"The paper addresses a timely and relevant problem, and the overall algorithmic framework is promising. However, the explicit lower-bound theorem is invalid as written and the explicit-solution proof has a sign/definition inconsistency that affects the main theorem of Section 4.2. These are load-bearing issues but appear repairable within the scope of the paper: the lower-bound instance can likely be redesigned (e.g., with multiple elements or a corrected optimality argument), and the AboveThreshold direction can be fixed by aligning Algorithm 2 with Definition B.5 or by reworking the proof. I recommend major revision rather than rejection, provided the authors supply corrected proofs for Theorem C.7 and Theorem 4.3."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this is a serious first crack at edge-differentially-private vaccination heuristics, and the reduction to private multiset multicover is a real, nontrivial extension of Gupta et al. But the two headline results that are supposed to be new—the explicit-solution algorithm and the Ω(log n) lower bound—are, as written, internally inconsistent. The lower bound in Theorem C.7 is not salvageable by a small fix: S1 is defined with r0−β−α log n copies, yet problem I2 requires r0−β, so S1 is not a feasible cover and the claim that |OPT|=1 is false; the set S* is also misdefined, since it contains at most one copy of S2 but is treated as allowing up to α−1 copies. The probability separation fails, and Lemma 4.5 inherits the problem. Algorithm 2 stops when γk ≤ T′, which is the opposite of the AboveThreshold mechanism it claims to use, and the proof of Theorem 4.3 argues with γi ≥ T′; one of them has to change.\n\nCredit where due: the PRIVMAXDEG-to-multiset reduction with the 4-step neighbor argument is reasonable; the implicit-solution approach via the exponential mechanism and the explicit variant via sparse-vector are the right high-level tools; the spectral radius bounds via walk-hitting and via neighbor-degree estimates are plausible, and the experimental section at least attempts to compare implicit vs explicit cost. The main algorithmic machinery is borrowed, but the transfer is not vacuous.\n\nSofter problems: the spectral-radius algorithms have sensitivity Δ^2 or 4Δ, so the utility bounds are weak, and the experiments for the explicit solution are run under the relaxed multiset-neighbor privacy definition rather than edge-DP, so they do not validate the actual published guarantee. These are issues a revision could address.\n\nWho is this for: people working on private graph algorithms and computational epidemiology. The core idea is worth discussing, but as a citable theorem the paper is not ready. My recommendation: send it to referees, because the problems are new and the upper-bound framework is potentially fixable; but if I were the editor, I would expect a major revision that either proves a correct lower bound or removes the claim, and fixes the sign of the threshold in Algorithm 2. On the current version my own verdict is reject.","headline":"Interesting first attempt at edge-DP epidemic control, but the advertised Ω(log n) lower bound is unproved and the explicit solution algorithm contradicts its own threshold rule.","tokens_in":21076,"tokens_out":5268,"would_cite":false,"duration_ms":49679,"reading_group":"maybe","serious_thinker":"no","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper gives the first edge-differentially-private algorithms for choosing which nodes to vaccinate so that the residual contact network's maximum degree or spectral radius falls below a target, with vaccination cost within an…","keywords":["differential privacy","edge privacy","multi-set multi-cover","maximum degree reduction","spectral radius reduction","vaccination strategy","network epidemiology","exponential mechanism"],"falsifier":"Check the lower-bound construction in Theorem C.7: in an instance requiring $r_0$ copies of the only element, the set $S_1$ is built with only $r_0 - \\beta - \\alpha\\log n$ copies, so it leaves $\\alpha\\log n$ copies uncovered and is not an optimal singleton cover for the nearby instance requiring $r_0 - \\beta$ copies. Verifying whether every set in $\\mathcal{S}^*$ covers at most $r_0 - \\beta - 1$ copies, the inequality the group-privacy argument needs, will confirm or refute the claimed $\\Omega(\\log n)$ lower bound for explicit covers.","tokens_in":20096,"feed_emoji":"💉","tokens_out":9517,"duration_ms":90223,"temperature":0.7,"pith_summary":"Controlling an outbreak by vaccination means removing a small set of nodes from a contact network, and the most effective proxy targets are the network's maximum degree and spectral radius. This paper asks how to choose that set when the edges themselves are sensitive and must be protected with differential privacy, a guarantee that changing any single contact only slightly changes the output distribution. It establishes that both targets admit edge-differentially-private algorithms: the private solution costs at most $O((1+1/\\varepsilon')\\log n)$ times the optimal non-private set, with high probability, and explicit lists of vaccinated nodes are possible at the price of $O(\\log n/\\varepsilon')$ slack in the degree target. It also claims lower bounds showing that any explicit private solution must incur $\\Omega(\\log n)$ additive error, so some residual degree overshoot is unavoidable. The reason a reader should care is that, if these results hold, privacy does not force giving up on principled epidemic planning: a near-optimal vaccination strategy can be released without revealing who is connected to whom.","feed_headline":"Private vaccine targeting on networks within O(log n) of optimal","feed_subtitle":"Edge-differential privacy hides sensitive contacts; degree and spectral-radius targets stay near-optimal.","key_machinery":"The central object is a reduction to multi-set multi-cover: each vertex $v$ becomes a set containing $\\infty$ copies of itself and one copy of each neighbor, and the requirement $r_v$ is how far $v$'s degree exceeds the target $D$. The private routine, borrowed from the iterative exponential-mechanism approach, repeatedly samples a remaining set with probability exponential in its marginal remaining coverage, producing a permutation that implicitly encodes the cover. A second mechanism, AboveThreshold, is used as a noisy stopping rule to convert that permutation into an explicit list of nodes to remove, at the cost of $O(\\log n/\\varepsilon')$ slack in the final degree target.","core_discovery":"The central discovery is that the two epidemic-control optimization problems, PRIVATEMAXDEG and PRIVMINSR, can be solved under edge differential privacy by reducing them to a multi-set multi-cover problem and privatizing the cover routine. For maximum degree, the paper proves that its Algorithm 1 outputs an implicit cover whose size is at most $O((1+1/\\varepsilon')\\ln|V|)$ times the optimal non-private cover with high probability, and that Algorithm 2 makes that cover explicit with a degree violation of $D + O(\\log n/\\varepsilon')$. For spectral radius, it gives two routes: privatizing a greedy walk-removal algorithm yields a bound around $n^{1/4}\\Delta^{1/2}$ on the residual spectral radius, and a second reduction based on the degree-of-neighbors bound $\\rho(G) \\leq \\max_u \\sqrt{\\sum_{v\\sim u} d(v,G)}$ brings the same multi-set machinery to bear at a $4\\Delta$ privacy-sensitivity price. The paper further claims that implicit solutions fully satisfy coverage constraints while explicit solutions cannot, and states lower bounds that any explicit private solution with near-optimal size must leave $\\Omega(\\log n)$ additive slack in the degree target.","pith_inferences":["Beyond the paper, if the $\\Omega(\\log n)$ lower bound can be rigorously established, the practical design question shifts from eliminating overshoot to calibrating it: choose $\\varepsilon$ and $D$ so that $D + O(\\log n/\\varepsilon')$ sits below the epidemic threshold.","The multi-set multi-cover reduction is generic enough to cover other threshold-based node-removal objectives, such as reducing $k$-core numbers or bounding local clustering, suggesting a template for private structural interventions beyond degree and spectral radius.","A testable extension is to use the implicit permutation directly as a priority ranking for vaccine allocation rather than converting it to an explicit set; in the paper's own experiments this preserves more of the degree reduction and may be the more privacy-favorable output.","Because the spectral-radius route pays a $4\\Delta$ sensitivity penalty, it is likely to be most useful on degree-assortative or bounded-degree networks; on heavy-tailed contact networks, a future algorithm that privatizes a lower-sensitivity spectral bound would be needed."],"forward_implications":["If the degree-reduction guarantee is correct, a public-health authority can publish a vaccination list under edge differential privacy and still achieve maximum degree below $D + O(\\log n/\\varepsilon')$, at a vaccination cost within $O((1+1/\\varepsilon')\\log n)$ of the optimal non-private plan.","The spectral-radius algorithms give the first private analogues of structural epidemic control: one reduces length-four walks to force $\\rho(G) \\leq O(n^{1/4}\\Delta^{1/2})$, which beats the trivial $\\Delta$ bound on dense graphs.","The lower bounds, if they survive scrutiny, imply a hard trade-off: an explicit private vaccine list cannot both use near-optimal size and meet the coverage target exactly, so some violation of the target degree is unavoidable.","Implicit solutions retain full coverage and better metric reduction, but they require each node to infer its own membership from the private permutation, which is not a directly publishable vaccine list.","Experiments on contact-network and synthetic graphs show the private implicit solution's cost within a roughly constant factor (about 10) of a non-private greedy cover on tested instances, and explicit solutions' cost and violation trade off with $\\varepsilon$, so privacy budgets need careful selection."],"supporting_citations":[{"why":"Supplies the iterative exponential mechanism for private set cover that Algorithm 4 adapts to multi-set multi-cover, including the privacy and utility proof template and the impossibility of explicit covers.","marker":"[19]"},{"why":"Defines differential privacy and provides the exponential mechanism, Laplace mechanism, and AboveThreshold subroutine used in Algorithms 1-3.","marker":"[13]"},{"why":"Gives the greedy walk-removal algorithm for reducing spectral radius whose length-four-walk utility and approximation analysis Algorithm 3 privatizes.","marker":"[44]"},{"why":"Introduces a differentially private algorithm for partial set cover, the template for the walk-hitting formalization used in the first PRIVMINSR algorithm.","marker":"[30]"},{"why":"States the spectral-radius upper bound in terms of sums of neighbor degrees that the second PRIVMINSR algorithm drives below a target.","marker":"[17]"},{"why":"Provides the non-private multi-set multi-cover approximation algorithm and $H_n$-approximation bound used both as the experimental baseline and in the utility analysis.","marker":"[42]"},{"why":"Introduces the vaccination problem as choosing a node subset to minimize expected infections in the residual graph, the epidemic-control starting point for the paper's objectives.","marker":"[15]"}],"fun_headline_variants":["Private vaccine targeting near-optimal on networks","Edge-differential privacy: near-optimal vaccine targeting","Private network vaccination: degree and spectral near-optimal","Near-optimal vaccination under edge differential privacy"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing assumption is that the repeated sampling mechanism that is private for ordinary set cover stays private and near-optimal when neighboring problem instances may differ in several coverage counts or multiplicities at once (up to four changes, or up to $4\\Delta$ in the spectral-radius variant); the paper relies on this transfer instead of fully proving it.","fun_headline_variants_meta":{"raw":{"variants":["Private vaccine targeting near-optimal on networks","Edge-differential privacy: near-optimal vaccine targeting","Private network vaccination: degree and spectral near-optimal","Near-optimal vaccination under edge differential privacy"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001378,"raw_usage":{"total_tokens":5583,"prompt_tokens":948,"completion_tokens":4635,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":564,"completion_tokens_details":{"reasoning_tokens":4576}},"tokens_in":564,"tokens_out":4635,"duration_ms":34523,"temperature":1.0,"reasoning_tokens":4576,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T12:00:38.870657+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Check the lower-bound construction in Theorem C.7: in an instance requiring $r_0$ copies of the only element, the set $S_1$ is built with only $r_0 - \\beta - \\alpha\\log n$ copies, so it leaves $\\alpha\\log n$ copies uncovered and is not an optimal singleton cover for the nearby instance requiring $r_0 - \\beta$ copies. Verifying whether every set in $\\mathcal{S}^*$ covers at most $r_0 - \\beta - 1$ copies, the inequality the group-privacy argument needs, will confirm or refute the claimed $\\Omega(\\log n)$ lower bound for explicit covers.","supporting_citations":[{"cited_title":"Differentially private combinatorial optimization, 2009","cited_arxiv_id":null,"evidence_quote":"Supplies the iterative exponential mechanism for private set cover that Algorithm 4 adapts to multi-set multi-cover, including the privacy and utility proof template and the impossibility of explicit covers."},{"cited_title":"The algorithmic foundations of differential privacy","cited_arxiv_id":null,"evidence_quote":"Defines differential privacy and provides the exponential mechanism, Laplace mechanism, and AboveThreshold subroutine used in Algorithms 1-3."},{"cited_title":"Approximation algorithms for reducing the spectral radius to control epidemic spread","cited_arxiv_id":null,"evidence_quote":"Gives the greedy walk-removal algorithm for reducing spectral radius whose length-four-walk utility and approximation analysis Algorithm 3 privatizes."},{"cited_title":"Differentially private partial set cover with applications to facility location","cited_arxiv_id":null,"evidence_quote":"Introduces a differentially private algorithm for partial set cover, the template for the walk-hitting formalization used in the first PRIVMINSR algorithm."},{"cited_title":"Some eigenvalue properties in graphs (conjectures of graffiti - ii)","cited_arxiv_id":null,"evidence_quote":"States the spectral-radius upper bound in terms of sums of neighbor degrees that the second PRIVMINSR algorithm drives below a target."},{"cited_title":"Rajagopalan and V .V","cited_arxiv_id":null,"evidence_quote":"Provides the non-private multi-set multi-cover approximation algorithm and $H_n$-approximation bound used both as the experimental baseline and in the utility analysis."},{"cited_title":"Eubank, V","cited_arxiv_id":null,"evidence_quote":"Introduces the vaccination problem as choosing a node subset to minimize expected infections in the residual graph, the epidemic-control starting point for the paper's objectives."}],"review_version":1}