{"id":"cfe7651b-5450-4367-aba5-942779391c3a","arxiv_id":"2412.19837","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"Fake users can poison local differential privacy graph collection by sending crafted adjacency vectors, inflating degree centrality and clustering coefficient estimates for chosen targets.","lead":"This paper shows that fake users can poison local differential privacy protocols for graphs, degrading estimated degree centrality and clustering coefficient for attacker-chosen targets. It also tests two countermeasures and finds that neither neutralizes the attacks, pointing to a need for new defenses.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The maximal-gain proofs for degree and clustering coefficients rely on incompatible assumptions about how the server obtains degrees; the paper never specifies the degree source.","rationale":"The reader's weakest_assumption identifies the same core issue: the clustering-coefficient derivation assumes the target's estimated degree is unchanged even though the attack adds fake edges to the target. I agree with that identification, and I think it is the single most load-bearing concern because it threatens the central theoretical claim that MGA achieves maximal distortion for both metrics. The concern is not about disagreement with community consensus; it is an internal consistency problem. Section V's degree-centrality gain counts fake edges as increasing target degree, while Section VI's clustering-coefficient gain treats target degree as constant. The paper never states which value the server uses: the reported degree or the degree implied by the reconstructed adjacency matrix. If the server uses reported degree, the degree-centrality attack fails because honest targets do not update their reported degree after fake edges appear. If the server reconstructs degree from adjacency bit vectors, then the clustering-coefficient denominator and the calibration function in Eqs. (16)-(19) change, invalidating Theorem 2. This inconsistency is compounded by the fact that proofs are deferred to an external technical report, so the paper itself does not provide the derivation that would resolve the assumption. The experimental results may still show that some degradation occurs, but the optimality claim, which is a main contribution, is not supported without fixing this modeling ambiguity. Therefore a CONDITIONAL verdict remains appropriate: the authors should specify the aggregation semantics, re-derive Theorem 2 under the correct degree model, and provide the full proofs and code. I do not see a reason to move to REJECT based on this alone, because the issue is fixable and the attack phenomenon may still be real under at least one consistent model.","tokens_in":18193,"tokens_out":7813,"duration_ms":79064,"concrete_test":"Implement the LF-GDPR estimator with the Fig. 5 attack on the Facebook dataset at epsilon=4, beta=0.05, using two degree sources: (a) the target's reported degree, which is unchanged by the attack, and (b) a degree recomputed from the reconstructed adjacency matrix that includes fake edges. Compare the measured Gain with Theorem 2 under both rules. Also re-derive Theorem 2 with ed_i' = ed_i + k_i, where k_i is the number of fake neighbors of target i, substituted into Eqs. (15)-(22). If either numerical comparison deviates materially from the theorem, the constant-degree assumption is load-bearing and the claimed optimality is unsupported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing point is the source of the estimated degree in the metric estimators. In Section VI, Eqs. (19)-(22), the clustering-coefficient MGA proof treats ed_i(ed_i-1) as constant before and after the attack, and the text states that the degree remains constant. But Fig. 5 and the surrounding cases construct the attack precisely by adding fake edges incident to the target, and Section V's degree-centrality gain, Eq. (10), counts those same added edges as increasing the target's degree. The paper does not specify whether the server's degree estimate comes from the target's own reported degree value, which an honest target would not update, or from the reconstructed adjacency matrix/bit vectors, which includes the fake edges. Under the latter rule, the denominator in Eq. (20) and the calibration function R in Eqs. (16)-(19) both depend on ed_i and change, so Theorem 2's closed form is not the maximum gain. Under the former rule, the degree-centrality attack in Section V has no effect on the target's degree centrality, because fake nodes' bit vectors do not alter the target's reported degree. Thus the two central theorems rely on mutually incompatible aggregation semantics unless the protocol is specified and one of the derivations is revised.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies data poisoning attacks against local differential privacy (LDP) protocols for graph metric collection. The attacker controls a set of fake users and crafts their reported adjacency bit vectors and degree values to distort the server's estimates of degree centrality and clustering coefficient for chosen target nodes. The authors propose two baseline attacks (Random Value Attack and Random Node Attack) and one optimization-based attack (Maximal Gain Attack, MGA), and claim that MGA achieves the maximal distortion, stated as Theorems 1 and 2. They also propose two countermeasures (frequent-itemsets-based detection and degree-difference-based detection) and evaluate all methods on four real-world graph datasets. The paper concludes that the attacks significantly degrade metric quality and that the proposed countermeasures are only partially effective.","tokens_in":18444,"tokens_out":4141,"duration_ms":38222,"significance":"If the theoretical claims are correct, this paper opens a new and relevant research direction: the security of LDP protocols for graph data, which has not been systematically studied before. The experimental evaluation on multiple real-world datasets demonstrates that the proposed attacks can substantially lower the quality of estimated degree centrality and clustering coefficient, and the countermeasures are shown to be insufficient. The paper also makes a useful connection to prior poisoning attacks on non-graph LDP frequency estimation. However, the central optimality claims (Theorems 1 and 2) are not proved in the manuscript, and one of the derivations relies on an assumption about the target's degree that conflicts with the attack construction; these issues need to be resolved before the theoretical contribution can be accepted.","major_comments":[{"comment":"The clustering coefficient derivation assumes that the target node's degree remains constant during the attack: the text before Eq. (19) states 'Since only the number of triangles changes for a node before and after the attack, while the degree remains constant,' and Eqs. (20)-(22) treat ed_i(ed_i-1) as a fixed denominator. Yet the attack construction in Fig. 5 and the surrounding cases (Case 1a-3b) explicitly adds edges between fake nodes and the target node, which increases the target's degree. The degree-centrality attack in Section V, Eq. (10), counts the same kind of added edges as increasing the target's degree. The paper never specifies whether the server's degree estimate comes from the target's own reported degree value (which an honest target would not update) or from the reconstructed adjacency matrix/bit vectors (which include the fake edges). Under the latter semantics, the denominator in Eq. (20) and the calibration function R in Eqs. (16)-(19) depend on the changing degree, so the closed form in Theorem 2 is not the maximum gain. Under the former semantics, the Section V degree-centrality attack would have no effect on the target's degree centrality. The paper must specify the degree estimation semantics precisely and revise one of the two derivations accordingly.","section":"Section VI, Eqs. (15)-(22), Fig. 5"},{"comment":"Theorems 1 and 2, which state that MGA achieves the maximal gain for degree centrality and clustering coefficient, are not proved in the manuscript. The paper only says 'Formal proofs of theorems are in [1]' and points to an external GitHub technical report. Since the paper's central contribution is the claim that MGA 'maximally distorts' the collected graph metrics (Section IV.B and the abstract), the absence of proofs or even proof sketches for these theorems leaves the main theoretical result unsupported in the paper itself. The authors should include full proofs or detailed proof sketches in the manuscript so that the optimality claim can be evaluated directly.","section":"Theorems 1 and 2, Section V and VI"},{"comment":"The optimization problem in Eq. (6)-(7) is not formally specified. The constraint set Y is never defined, and the 'average degree limit' and 'number of new connections' constraints that are used to control the attack in Sections V and VI are described only informally (e.g., 'the number of additional connections for each fake node is carefully controlled' and 'we limit the number of new connections each fake node can create to the average degree'). Without a precise statement of these constraints, the meaning of 'maximal gain' is not well-defined, and even a proof of Theorems 1 and 2 would not be verifiable. The authors should formalize the feasible set Y in terms of the protocol parameters and the detection-avoidance heuristic.","section":"Section IV.B, Eqs. (6)-(7); Sections V and VI"}],"minor_comments":[{"comment":"The text says 'MGA and RVA show a clear inverse relationship between the privacy budget and attack effectiveness' and then immediately says 'In contrast, the gain of MGA remains nearly unchanged.' The second sentence appears to refer to RNA, not MGA; this typo makes the paragraph confusing.","section":"Section VIII, Exp. 1"},{"comment":"The notation for the degree used in the clustering coefficient derivation is inconsistent: Eq. (15) uses 'di' as the perturbed degree, while Eqs. (20)-(22) use 'ed_i' (estimated degree). The paper should use a single notation consistently.","section":"Section VI, Eqs. (15), (20)-(22)"},{"comment":"The formula in Eq. (11) uses 'min(r, floor(dtilde))/r' and subtracts 'dtilde/(N-1)' without explanation. The expression appears dimensionally odd, and its sign is not discussed; if the subtracted term can exceed the first term, the formula would predict a negative gain, which would be impossible for a maximization attack. The derivation of this formula should be clarified or corrected.","section":"Theorem 1, Eq. (11)"},{"comment":"The countermeasures rely on free parameters that are not formally defined. The 'predefined threshold' in the frequent-itemset detection (Section VII.A) and the '3-sigma' threshold in the degree-based detection (Section VII.B) are not connected to a specific distribution or variance, making the detection methods hard to reproduce from the description alone.","section":"Section VII.A and VII.B"}],"recommendation":"major_revision","confidential_remarks":"The paper's reliance on an external GitHub technical report for all formal proofs is a significant concern for a security venue; the proofs of Theorems 1 and 2 should be in the manuscript or the technical report should be formally reviewed and submitted as supplementary material. The degree-estimation-semantics ambiguity is a fundamental issue that affects the validity of both main theorems. The experimental results are interesting but they do not by themselves compensate for the lack of rigorous theoretical support for the optimality claims."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this is the first paper to look at data poisoning against LDP protocols that collect graph metrics, and the experiments show the attacks shift degree centrality and clustering coefficient estimates on real networks. That is a real gap and a useful result. But the paper's two main theorems rest on mutually incompatible assumptions about where the estimated degree comes from, and until that is fixed the theoretical claims don't hold as stated.\n\nWhat's actually new: the graph-specific gain analysis, especially for clustering coefficient, and the demonstration that Sybil injection degrades LF-GDPR and LDPGen estimates. RVA, RNA, and MGA are direct adaptations of the frequency-estimation attacks from Cao et al. [65], which the authors acknowledge. The experiments look honest: they vary beta, gamma, and epsilon, use four standard datasets, and the countermeasures are not tuned to succeed. The free parameters in the detection methods are legitimate experimental thresholds, not fitted constants.\n\nThe soft spot is load-bearing. In Section V, Theorem 1 counts each fake-target edge as increasing the target's degree, and Eq. (10) makes that explicit. In Section VI, the clustering-coefficient derivation (Eqs. 18–20) assumes the target's degree ed_i is unchanged by the attack, even though the attack construction in Fig. 5 creates edges between fake nodes and the target. The paper never specifies whether the server obtains the degree from the target's own reported value or from reconstructing the adjacency matrix. If the former, the degree-centrality attack is vacuous for honest targets; if the latter, the clustering coefficient denominator changes and the closed-form gain in Theorem 2 is not the maximum. The two theorems cannot both be right under a single aggregation rule. That is an internal contradiction, not a stylistic complaint.\n\nA second issue: the proofs are deferred to a GitHub technical report. That may be fine for a workshop, but for a journal or conference the proofs need to be in the paper or the claims need to be weakened.\n\nWho should read this: people working on LDP protocols for graphs, and anyone designing Sybil-resistant aggregation. The experimental section is the most convincing part. The theory needs substantial revision. I would not cite it as it stands, but I would send it to peer review because the topic is real, the experiments are reproducible in spirit, and the contradiction is fixable with a clear statement of the aggregation semantics and a revised proof.","headline":"A real gap and real experiments, but the paper's two central theorems rest on contradictory assumptions about how the server estimates degrees.","tokens_in":18934,"tokens_out":2671,"would_cite":false,"duration_ms":25492,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"An attacker with a small fraction of fake users can deliberately distort the degree centrality and clustering coefficient estimated by LDP graph protocols, and the paper identifies the attack that maximizes this distortion.","keywords":["data poisoning","local differential privacy","graph metrics","degree centrality","clustering coefficient","fake user injection","graph attacks"],"falsifier":"Run the MGA clustering-coefficient attack against a server that estimates each node's degree from the same reconstructed adjacency bit vectors used for triangle counting, rather than from the separately reported degree values; if the target's reconstructed degree rises with the fake connections, the measured gain will diverge from Theorem 2's formula, and the claimed optimality of the attack would fail in that setting.","tokens_in":17983,"feed_emoji":"🎯","tokens_out":9302,"duration_ms":85630,"temperature":0.7,"pith_summary":"Local differential privacy for graphs asks each user to send a perturbed list of whom they are connected to and a reported degree to a central server, which then estimates metrics like degree centrality and clustering coefficient. This paper argues that an attacker who controls a modest number of fake users can craft those two atomic reports to push the estimated metrics of chosen target nodes in a desired direction. The paper proves that a Maximal Gain Attack, connecting fake nodes to targets as densely as an average-degree cap allows, maximizes the total distortion, and it gives explicit gain formulas for both metrics. Experiments on real social and communication networks show that even a 5% fraction of fake users substantially degrades the collected metrics, and two countermeasures based on frequent itemsets and degree consistency do not fully restore accuracy. If the claim is right, applications that rely on LDP graph collection for popularity or influence estimates should treat reported data as adversary-controlled input.","feed_headline":"Fake users can skew LDP graph metrics at will","feed_subtitle":"A small fraction of fake users can maximize the distortion of chosen nodes' degree and clustering metrics.","key_machinery":"The load-bearing object is the absolute gain $\\mathrm{Gain} = \\sum_{t \\in T} |\\tilde{f}_{t,a} - \\tilde{f}_{t,b}|$: the attacker's optimization is to maximize this sum over crafted reports. For degree centrality, the mechanism is direct edge injection: each fake node connects to as many target nodes as allowed by an average-degree cap, which keeps fake nodes plausible. For the clustering coefficient, the mechanism is triangle construction: fake nodes are connected to each other and to targets so that, after the protocol's triangle-count calibration $R(\\cdot)$, the estimated triangle count of a target rises while the estimated degree in the denominator is assumed unchanged. The average-degree cap computed from the perturbed graph is what ties the two attacks together, because it limits the number of crafted edges the attacker can add without being obvious.","core_discovery":"The central claim is that an attacker who controls $m$ fake users in an edge-local differential privacy graph collection protocol can deliberately distort the estimated degree centrality and clustering coefficient of chosen target nodes. The attack surface is the pair of atomic reports each user sends: an adjacency bit vector and a degree. The paper defines the attack gain as $\\mathrm{Gain} = \\sum_{t \\in T} |\\tilde{f}_{t,a} - \\tilde{f}_{t,b}|$, and proves in Theorems 1 and 2 that the Maximal Gain Attack (MGA) maximizes this quantity. For degree centrality, each fake node connects to as many target nodes as the average-degree cap allows, yielding a gain of $\\mathrm{Gain} = \\frac{m r}{N-1}\\left(\\frac{\\min(r,\\lfloor \\tilde{d} \\rfloor)}{r} - \\frac{\\tilde{d}}{N-1}\\right)$. For the clustering coefficient, fake nodes are wired into triangles with the target and each other so that the calibrated triangle count rises while the denominator is treated as constant, producing the gain formula in Theorem 2. The paper further argues experimentally that MGA dominates random baselines and that two detection-oriented countermeasures only partially reduce the gain.","pith_inferences":["The same atomic-report model underlies many LDP graph estimators, so targeted poisoning probably extends to metrics the paper did not test, such as closeness or betweenness approximations, whenever those estimators are monotone in reported degrees or triangle counts.","An adaptive attacker could calibrate the number of crafted edges per fake node to sit just below the average-degree cap while still covering all targets, making both proposed detection methods less effective; testing this would require an implementation that tunes the cap against the detector's threshold.","A more promising defense direction is server-side consistency validation between the reported degree and the degree implied by the reconstructed graph, or robust aggregation that bounds the influence of any single fake user; the paper's negative countermeasure results motivate such designs rather than settle them."],"forward_implications":["A 5% injection of fake users, each adding a handful of crafted edges, is enough to move estimated degree centrality and clustering coefficient of target nodes noticeably on all four datasets tested.","MGA consistently dominates the two random baselines for both metrics, so the threat is not an artifact of a particular graph or privacy budget.","The two countermeasures (frequent-itemset mining and reported-versus-reconstructed degree checking) can reduce the gain in some settings but leave a large residual distortion, and they can misclassify genuine high-degree nodes as fake.","Because the attacks operate on the atomic adjacency-bit-vector and degree reports, graph metrics beyond degree centrality and clustering coefficient, including modularity as the paper's experiments show, are also degraded.","The privacy guarantee does not by itself protect the server against fabricated reports; utility of any downstream graph metric is at risk."],"supporting_citations":[{"why":"Supplies the graph-metric estimation pipeline (adjacency bit vectors plus degrees, triangle-count calibration) whose estimates the attacks target.","marker":"[62]"},{"why":"Provides the original random-value, random-item, and maximal-gain attack templates and the frequent-itemset detection idea that the paper adapts to graphs.","marker":"[65]"},{"why":"Supplies the alternative synthetic-graph LDP protocol that the paper also attacks in experiments.","marker":"[13]"},{"why":"Technical report containing the formal proofs of Theorems 1 and 2.","marker":"[1]"},{"why":"Apriori frequent-itemset mining algorithm used by the first countermeasure.","marker":"[67]"}],"fun_headline_variants":["Poisoning LDP graph protocols to distort degree and clustering metrics","Fake user injection corrupts LDP graph metric estimation","Data poisoning attacks against LDP graph analytics","Attacker-controlled fake users skew LDP graph outputs","LDP graph metrics can be manipulated by fake user poisoning"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"For the clustering-coefficient theorem, the derivation assumes the target's estimated degree $\\tilde{d}_i$ is the same before and after the attack; since the attack adds fake edges to the target, a server that recomputes degree from the reconstructed adjacency bit vectors would see the denominator $\\tilde{d}_i(\\tilde{d}_i-1)$ increase, and the fixed-denominator gain formula in Theorem 2 would not hold.","fun_headline_variants_meta":{"raw":{"variants":["Poisoning LDP graph protocols to distort degree and clustering metrics","Fake user injection corrupts LDP graph metric estimation","Data poisoning attacks against LDP graph analytics","Attacker-controlled fake users skew LDP graph outputs","LDP graph metrics can be manipulated by fake user poisoning"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000803,"raw_usage":{"total_tokens":3567,"prompt_tokens":1022,"completion_tokens":2545,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":638,"completion_tokens_details":{"reasoning_tokens":2466}},"tokens_in":638,"tokens_out":2545,"duration_ms":15875,"temperature":1.0,"reasoning_tokens":2466,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T05:28:14.357365+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the MGA clustering-coefficient attack against a server that estimates each node's degree from the same reconstructed adjacency bit vectors used for triangle counting, rather than from the separately reported degree values; if the target's reconstructed degree rises with the fake connections, the measured gain will diverge from Theorem 2's formula, and the claimed optimality of the attack would fail in that setting.","supporting_citations":[{"cited_title":"LF-GDPR: A framework for estimating graph metrics with local differential privacy,","cited_arxiv_id":null,"evidence_quote":"Supplies the graph-metric estimation pipeline (adjacency bit vectors plus degrees, triangle-count calibration) whose estimates the attacks target."},{"cited_title":"Data poisoning attacks to local differential privacy protocols,","cited_arxiv_id":null,"evidence_quote":"Provides the original random-value, random-item, and maximal-gain attack templates and the frequent-itemset detection idea that the paper adapts to graphs."},{"cited_title":"Generating synthetic decentralized social graphs with local differential privacy,","cited_arxiv_id":null,"evidence_quote":"Supplies the alternative synthetic-graph LDP protocol that the paper also attacks in experiments."},{"cited_title":"Available: https://github.com/hahahumble/ DPA2Graphs/blob/main/TechnicalReport.pdf","cited_arxiv_id":null,"evidence_quote":"Technical report containing the formal proofs of Theorems 1 and 2."},{"cited_title":"Fast algorithms for mining association rules,","cited_arxiv_id":null,"evidence_quote":"Apriori frequent-itemset mining algorithm used by the first countermeasure."}],"review_version":1}