{"id":"2c7d6649-3e19-4135-9b35-ba3d8bf20ce0","arxiv_id":"2504.12520","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":2,"one_line_summary":"Edge-level differential privacy protects only tests between complete neighboring networks, not tests of individual edges, except under independence or bounded-dependence conditions.","lead":"Differential privacy for network data is often described as hiding individual links, but this paper shows the standard definition does not actually prevent an adversary from inferring a specific edge when links are correlated. It then gives precise conditions under which such edge-level protection does hold, using the Pufferfish framework.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The paper's critique of common edge-DP claims depends on reading 'protects individual edges from being disclosed' as inferential; a causal reading would make Example 1 non-refuting. A systematic citation audit would settle whether the cited works intended inferential guarantees.","rationale":"The reader's weakest assumption correctly identifies the interpretive ambiguity between causal and inferential readings as the principal vulnerability of the paper's central narrative. The formal mathematics is sound: Example 1 is a valid counterexample to the unqualified inferential claim, Theorem 9 correctly characterizes the independent-edge case, and Lemma 10's proof checks out despite a superficially confusing 1/2 factor that cancels. The only place the central thesis can fail is if the cited authors intended a causal guarantee, in which case the paper would be attacking a strawman. I agree with the reader that the paper argues but does not prove that the cited statements were meant inferentially. However, the natural reading of 'protects individual edges from being disclosed' is inferential, and the Hay et al. quote in Section 3.1 supports that reading at least for one influential source. The formal contributions are independent of the interpretive premise and remain valuable. Therefore I would not change the reader's ACCEPT verdict; the concern warrants a verification step rather than a revision of the mathematical conclusions.","tokens_in":25648,"tokens_out":16560,"duration_ms":176337,"concrete_test":"Extract the exact sentences in which each cited work interprets edge DP (Hay et al., 2009; Task and Clifton, 2012, 2014; Blocki et al., 2013; Xiao et al., 2014; Karwa and Slavkovic, 2016; Karwa et al., 2017; Jiang et al., 2021) and have two independent annotators classify each as inferential (limits on adversary's ability to infer or detect an edge), causal (output distribution is insensitive to edge toggling), or ambiguous. If a majority of the coded passages is causal and none explicitly discusses adversary inference, the paper's 'common misinterpretation' thesis loses its evidentiary basis; if a majority is inferential or ambiguous, the central claim stands.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim that common edge-DP interpretations are flawed rests on Section 3.1's treatment of statements such as Hay et al. (2009)'s 'An edge-differentially private algorithm protects individual edges from being disclosed' as inferential claims, i.e., promises that an adversary cannot detect a specific edge. If the original authors intended a causal guarantee (the mechanism's output distribution is epsilon-close when a single edge is toggled, which is exactly epsilon-edge DP), then Example 1 is not a counterexample: the Laplace edge-count mechanism does satisfy the causal guarantee, and the paper's 'gap' would reduce to a difference in vocabulary rather than a flaw in the literature. The paper argues in Section 3.1 that causal readings are unnatural for networks because there is no clear data-contribution scenario for an edge, but it does not establish that the cited works (Hay et al., 2009; Task and Clifton, 2012, 2014; Blocki et al., 2013; Xiao et al., 2014; Karwa and Slavkovic, 2016; Karwa et al., 2017; Jiang et al., 2021) intended inferential rather than causal readings. Since the motivating thesis that these claims are 'inaccurate or misleading' requires the inferential reading, this is the load-bearing assumption. The formal results (Theorem 9, Lemma 10, Corollary 11) are not affected by the ambiguity; they stand as conditional statements about what edge DP does and does not imply under specified distributional assumptions.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper examines the standard network privacy definition of ε-edge DP and argues that a common interpretation—that edge DP protects individual edges from being disclosed—is generally false. It supports this with a simple counterexample (Example 1): a Laplace mechanism releasing a noisy edge count satisfies ε-edge DP, yet in a network where the presence of one special edge (the 'queen' edge) changes the distribution of all other edges, an adversary can infer that edge with probability tending to 1 as the number of nodes grows. The paper then formalizes the gap using the Pufferfish framework: edge DP protects only hypothesis tests between complete neighboring networks (Corollary 8), not tests about individual edges. It proves that edge DP is equivalent to Pufferfish for edge-level secrets when edge variables are independent (Theorem 9), gives a general sufficient condition for a finite privacy-loss bound (Lemma 10), and applies this to exponential random graph models, deriving an explicit bound (Corollary 11). The paper concludes with a discussion of other network DP variants and open questions.","tokens_in":25934,"tokens_out":13740,"duration_ms":139733,"significance":"If the results hold, the paper makes a valuable conceptual contribution by clearly delineating what ε-edge DP does and does not guarantee. The counterexample is compelling and accessible, and the Pufferfish-based analysis provides a principled framework for stating edge-level privacy guarantees. The proofs in the appendix are complete and self-contained; the paper ships no code but the derivations are checkable. The equivalence in Theorem 9 and the ERGM bound in Corollary 11 are concrete, falsifiable statements that should inform both the practice and the communication of network privacy. The paper also creditably connects abstract DP to a general Pufferfish instantiation (Corollary 8), which may be of independent interest.","major_comments":[{"comment":"The paper's central interpretive claim—that common edge-DP interpretations are 'inaccurate or misleading'—depends on reading the phrase 'protects individual edges from being disclosed' as an inferential privacy guarantee. The paper offers a direct quote from Hay et al. (2009) but merely lists other works (Task and Clifton, 2012, 2014; Blocki et al., 2013; Xiao et al., 2014; Karwa and Slavkovic, 2016; Karwa et al., 2017; Jiang et al., 2021) without demonstrating that they intended an inferential rather than a causal reading. Under a causal reading, ε-edge DP does ensure that toggling a single edge changes the output distribution by at most e^ε, and Example 1 does not refute such a claim. To make the motivating thesis fully rigorous, the authors should either provide direct quotations or a systematic audit showing that the cited works promised inferential guarantees, or explicitly restrict the critique to 'inferential readings' while acknowledging that causal readings are a coherent alternative. This framing issue is load-bearing for the paper's stated motivation, although the formal results in Sections 4.1–4.2 are unaffected.","section":"Section 3.1 and Abstract"}],"minor_comments":[{"comment":"The sentence 'We speculate that this is due to the sheer difficulty of providing an interpretation that is clearly intelligible and relatable to actual privacy concerns' is informal for a research paper; consider rephrasing to a more neutral formulation.","section":"Section 3.1"},{"comment":"In the statement '1_{q̃ > (p+q)/2} converges in probability to 1_{{1,2}∈E}', it would be clearer to say explicitly that the indicator random variable converges to the indicator of the edge's presence, since q̃ itself converges in probability to p or q.","section":"Example 1"},{"comment":"The paper restricts the Pufferfish definitions and equivalence proofs to discrete output spaces and only remarks that continuous distributions may be handled via densities. Since the Laplace mechanism in Example 1 is continuous and many practical edge-DP mechanisms are continuous, a formal treatment of continuous output spaces in Theorem 7 and Theorem 9 would strengthen the paper; as written this is a limitation, not an error.","section":"Remark 1 and Theorems 7–9"},{"comment":"The factor of 1/2 in the expansions of P_θ(M(G)=ω | E) and the analogous term for ¬E is initially surprising; a brief parenthetical explanation that it corrects for double-counting graphs in the summation would improve readability.","section":"Proof of Lemma 10"},{"comment":"There is a minor typographical issue in the displayed formula for α: the expression 'β^T Δ(...)) - log(...)' appears to have an extra parenthesis. Please check the final displayed formula.","section":"Corollary 11"}],"recommendation":"minor_revision","confidential_remarks":"The technical content is sound and the paper is likely to be of interest to the journal's readership. The main concern is the rhetorical framing around 'inaccurate or misleading' claims, which should be either substantiated with a citation audit or explicitly scoped to inferential readings. I would support publication after a minor revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. First, the core result is solid: epsilon-edge DP only guarantees indistinguishability between complete neighboring graphs, and if you want to claim it protects inference about a specific edge you need strong distributional assumptions. Example 1 is a correct counterexample: the Laplace edge-count mechanism is edge-DP yet reveals the queen edge through density. Second, the positive contributions are real: the Pufferfish connection (Corollary 8), the iff for independent-edge networks (Theorem 9), and the ERGM bound (Corollary 11) are new and clearly proven. The paper does not create new mechanisms, but it tells you what an existing guarantee means, which is important for practice.\n\nThe proofs look complete. I checked the appendix: the restatements of Kairouz and Wasserman-Zhou, the Pufferfish equivalence, the edge-DP/Pufferfish theorem, Lemma 10, and Corollary 11 all have legitimate arguments. The counterexample is correct. No post-hoc fitting or circularity.\n\nSoft spots, in order. First, the motivating claim that common edge-DP interpretations are 'inaccurate or misleading' depends on reading phrases like 'protects individual edges from being disclosed' as inferential guarantees. The stress-test note is right: if Hay et al. and the others meant a causal guarantee (the output distribution is epsilon-close when an edge is toggled), then Example 1 does not refute them. The paper argues causal readings are unnatural for networks because there is no clear contribution scenario for an edge, but it does not systematically audit the cited works. The central formal results do not depend on this interpretive debate; they stand as conditional statements. But the framing is slightly overreaching relative to the textual evidence. Second, minor: Theorem 7 and Corollary 8 are stated for discrete output spaces; Remark 1 acknowledges continuous distributions can be handled with densities, but the formal statements do not. Not a problem for the examples. Third, the independence assumption in Theorem 9 is strong and hard to verify, as the authors admit, and Corollary 11's bound is conservative but valid.\n\nWho should read this: anyone working on network privacy, especially practitioners who use edge DP and want to know what they can honestly claim. The authors engage seriously with the literature. I would send this to peer review; it deserves a serious referee. My recommendation is accept with minor revisions, not desk reject.","headline":"A careful, mostly right paper showing edge DP does not protect individual edges from inference except under independence-like assumptions; the main soft spot is that its critique of the literature depends on an inferential reading that some cited authors may not have intended.","tokens_in":26475,"tokens_out":2324,"would_cite":true,"duration_ms":24187,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68P27","62F03"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper shows that $\\varepsilon$-edge differential privacy, by itself, protects only tests between whole neighboring networks, not the presence or absence of any single edge, and identifies assumptions under which the stronger…","keywords":["differential privacy","edge differential privacy","network data","Pufferfish privacy","adversarial hypothesis testing","exponential random graph models","correlated data","privacy interpretation"],"falsifier":"Run the two-queen hive model with $p>q$ and large $n$, release the edge count plus $\\mathrm{Laplace}(1/\\varepsilon)$, and threshold it at $(p+q)/2$. The paper's claim predicts the indicator that the queen edge is present is recovered with probability tending to one; if the recovery probability stays bounded away from one as $n$ grows, the claimed gap between whole-network privacy and edge-level inference would fail.","tokens_in":25445,"feed_emoji":"🕸️","tokens_out":12055,"duration_ms":120550,"temperature":0.7,"pith_summary":"This paper asks what the popular network privacy definition $\\varepsilon$-edge differential privacy actually promises, and argues that the common reading is too strong. It shows that $\\varepsilon$-edge DP controls only tests between two complete neighboring networks, not tests about whether a single edge is present. The demonstration is concrete: releasing a Laplace-noised edge count satisfies $\\varepsilon$-edge DP, yet in a hive network with two queen nodes an adversary can use the noisy count to infer the queens' edge with probability tending to one as $n\\to\\infty$. The paper then uses the Pufferfish privacy framework to identify the assumptions—independent edges, or a bounded effect of one edge on the rest of the network—under which edge-level inference is actually bounded.","feed_headline":"Edge DP does not protect individual edges","feed_subtitle":"A simple edge-count release satisfies edge DP yet exposes one link as the network grows.","key_machinery":"The load-bearing object is Pufferfish privacy, a generalization of differential privacy in which the guarantee is stated over chosen secrets and a class of data-generating distributions; the paper uses it to convert vague claims about hiding edges into precise hypothesis tests with bounded power. Corollary 8 shows that plain DP is Pufferfish with the secrets taken to be complete neighboring databases, which is why the DP guarantee cannot see individual edges. Theorem 9 shows that when edges are independent, $\\varepsilon$-edge DP is equivalent to Pufferfish privacy for the edge-presence secrets. Lemma 10 supplies the mechanism for moving from whole-network to edge-level guarantees under dependence: the extra privacy loss $c$ is the worst-case multiplicative change in the rest of the network's distribution when one edge is conditioned on. Corollary 11 computes $c$ for exponential random graph models using the change statistic $\\Delta(g,i,j)$, so the same argument becomes operational for a standard network model. The counterexample itself is carried by the Laplace mechanism on the edge count, whose sensitivity is one.","core_discovery":"The central claim is that $\\varepsilon$-edge DP protects a narrower set of hypotheses than is usually advertised: pairs of complete networks differing in one edge, not the presence or absence of an individual edge. Example 1 pairs the Laplace mechanism on the edge count with a two-queen hive model; the mechanism is $\\varepsilon$-edge DP because the edge count has sensitivity 1, but because all other edges occur with probability $p>q$ depending on whether the queen edge is present, the noisy density estimate separates the two cases and the queen edge is recoverable with probability tending to one. The paper formalizes the gap through Pufferfish: edge DP is exactly Pufferfish privacy when the protected secrets are entire neighboring databases (Corollary 8), and only under an independent-edge distribution does it become Pufferfish privacy for individual edges (Theorem 9). For dependent networks, Lemma 10 gives a sliding scale: if conditioning on one edge changes the distribution of the rest by at most $e^c$, then $\\varepsilon$-edge DP implies $(\\varepsilon+c)$-Pufferfish edge privacy, and for exponential random graph models the constant $c$ is controlled by the change statistic (Corollary 11).","pith_inferences":["The paper's asymptotic counterexample suggests a finite-sample version: for networks with strong edge dependence, the advantage of an edge-inference adversary should scale with the separation between the two conditional densities, so one can estimate how large $n$ must be before a DP release is effectively transparent for a given edge.","A practical tool could estimate the constant $c$ from Lemma 10 for real network models and report the effective Pufferfish parameter $\\varepsilon+c$ alongside the edge-DP parameter, giving users a number that actually describes edge disclosure risk.","The authors leave approximate DP and local DP on networks open; instantiating Corollary 8 for those settings would likely reveal similar gaps, since the protected secrets remain whole databases or local views rather than individual edges, and in local DP no single party clearly owns an undirected edge."],"forward_implications":["Practitioners should describe $\\varepsilon$-edge DP as bounding tests between complete neighboring networks; without further assumptions it does not bound tests about a single edge.","Edge-level protection claims are warranted only for independent-edge networks, or when the conditional distribution of the rest of the network changes by at most $e^c$ when the edge is toggled.","For exponential random graph models, an $\\varepsilon$-edge-DP release carries an effective edge-privacy parameter bounded by $2|\\beta^\\top \\Delta|$ in the worst case, so unbounded change statistics signal that edge inference is not protected.","Relying on edge DP for attributed graphs leaves node attributes unprotected, since the neighboring relation ignores node-level information; those attributes must be treated as public or handled by a different definition.","The same hypothesis-testing framing extends to node DP and other network privacy variants, where the meaning of neighboring databases is even harder to interpret causally."],"supporting_citations":[{"why":"Defines edge DP and contains the original 'protects individual edges' phrasing the paper shows is too strong.","marker":"Hay et al. (2009)"},{"why":"Supplies the differential privacy definition, the Laplace mechanism used in the counterexample, and the post-processing property used in the hypothesis-testing equivalence.","marker":"Dwork, McSherry, et al., 2006"},{"why":"Provides Theorem 2, the equivalence between DP and bounded power for tests between neighboring databases that anchors the interpretation.","marker":"Kairouz et al. (2015)"},{"why":"Supplies Pufferfish, the framework used to formalize edge-level secrets, and the theorem the paper adapts for independent edges.","marker":"Kifer and Machanavajjhala (2014)"},{"why":"Supplies Theorem 3, the independence assumption that makes tabular DP protect individual records, which the paper adapts to edges.","marker":"L. Wasserman and Zhou (2010)"},{"why":"Supplies the causal-versus-inferential distinction used to explain why common edge-DP interpretations overreach.","marker":"Tschantz et al. (2020)"}],"fun_headline_variants":["Edge DP guards whole networks, not individual edges","Edge differential privacy fails for dependent edges","Network edge privacy: the guarantee is narrower than it seems","Edge DP can expose single edges in correlated networks","Why edge DP won't protect a specific edge in a network"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The paper reads the phrase 'protects individual edges from being disclosed' as a claim about what an adversary can infer from the output; if the original authors meant only that toggling an edge barely changes the mechanism's output distribution, the counterexample would not contradict them.","fun_headline_variants_meta":{"raw":{"variants":["Edge DP guards whole networks, not individual edges","Edge differential privacy fails for dependent edges","Network edge privacy: the guarantee is narrower than it seems","Edge DP can expose single edges in correlated networks","Why edge DP won't protect a specific edge in a network"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000209,"raw_usage":{"total_tokens":1383,"prompt_tokens":895,"completion_tokens":488,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":511,"completion_tokens_details":{"reasoning_tokens":414}},"tokens_in":511,"tokens_out":488,"duration_ms":4776,"temperature":1.0,"reasoning_tokens":414,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T12:30:28.638654+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the two-queen hive model with $p>q$ and large $n$, release the edge count plus $\\mathrm{Laplace}(1/\\varepsilon)$, and threshold it at $(p+q)/2$. The paper's claim predicts the indicator that the queen edge is present is recovered with probability tending to one; if the recovery probability stays bounded away from one as $n$ grows, the claimed gap between whole-network privacy and edge-level inference would fail.","supporting_citations":[],"review_version":1}