Empirical Auditing of Edge-Private Graph Generators
Anum Fatima, Stratis Limnios, James Adams, Lukasz Szpruch, Carsten Maple, Carsten Maple, Gesine Reinert, Andrew Elliott
stat.ML · cs.LG
Quick verdict
Audits edge-DP leakage in graph generators with Clopper-Pearson-bounded attacks; rigorous and honest, but only two tiny networks and two generators tested.
Summary
The paper introduces a mechanism-agnostic framework for empirically auditing the edge-level differential privacy (DP) guarantees of private graph generators. The auditor knows two edge-neighbouring graphs differing in one target edge, repeatedly queries the mechanism on both, and trains distinguishers: a direct target-edge test, a Random Forest on handcrafted local features (common neighbours, Adamic–Adar, distance, clustering) computed after removing the target edge, and a GCN+MLP attack on 2-hop edge-removed subgraphs. Privacy loss is reported as a confidence-valid lower bound ε_LB built from one-sided Clopper–Pearson bounds on TPR/FPR with Bonferroni correction. Experiments cover Randomized Response (RR) and PrivGraph on Karate Club (34 nodes, 78 edges) and a 101-node/745-edge EU-core department, with ε ∈ {0.1, 0.5, 1, 2, 5, 15}, 30 target edges, and 10,000 releases per neighbouring graph. RR's direct-edge attack closely tracks nominal ε, while structural attacks witness ~0 — a well-behaved negative control. PrivGraph shows small but growing structural leakage on Karate Club (GNN mean ε_LB 0.317, max 0.455 at ε=15) and none on the sampled EU-core edges. No audited configuration exceeds its claimed budget. Limitations: two tiny networks, only 30 audited edges, single-release auditing, and the GNN-over-handcrafted-features advantage is not statistically tested.
Review complete
Assessment at a glance
4
risk flags identified
● high 0
● medium 3
● low 1
4 strengths · 5 weaknesses · 5 author questions
AI text signal = Binoculars zero-shot detector score over 20 sampled passages (Fast-DetectGPT co-reported) — absence does not prove human authorship, and a flag does not imply misconduct.
Levels reflect verification complexity — not a quality score. Evolve never rates your paper.
Key claims under review
- A mechanism-agnostic auditing framework can quantify the edge-level privacy loss witnessed in DP graph generators using confidence-valid Clopper–Pearson lower bounds (ε_LB).
- For randomized response, leakage is confined to the direct edge state: structural attacks witness nothing once the target edge is removed (a validated negative control).
- PrivGraph's community-based reconstruction can encode target-edge membership in local structural geometry, with leakage growing with ε on Karate Club but not on the sampled EU-core edges.
- GNN-based auditors recover structural leakage that handcrafted local statistics miss (asserted in the abstract; supported only by untested mean differences on one network).
Strengths
Confidence-valid statistical inference
Exact one-sided Clopper–Pearson bounds on TPR/FPR with a Bonferroni split at 95% simultaneous confidence per edge (App. C.4); the ε=15 saturation at ε_LB=6.295 is explicitly derived as the finite-sample ceiling for m=2,000 audit samples and α=0.05 (App. B.1) rather than left as an anomaly.
Edge-removal design genuinely isolates structural leakage
The Local and GNN auditors delete the target edge before computing any feature or message passing (App. D.1, D.3), so success cannot come from trivially observing the released edge — a common confound in link-inference audits.
Negative-control discipline
Unusually complete reproducibility specification
Weaknesses
Minimal experimental scope
Headline GNN-over-handcrafted claim lacks statistical support
Max ε_LB over 30 edges has no joint coverage
The audit never demonstrates teeth
No own code release announced
Full Review Report
$1.99 · one-timeUnlock the complete preliminary analysis Evolve produced for this paper.
Report preview
Scope & Claims
This preprint (arXiv 2609.25155, stat.ML) builds an empirical auditing framework for edge-level differential privacy (DP) in graph generators, in the witnessed-loss tradition of Jagielski et al. (2020), Nasr et al. (2021, 2023) and TAPAS (Houssiau et al., 2022). Three claims are made: (1) a mechanism-agnostic audit testing whether outputs generated from two graphs differing in exactly one edge (§2) are distinguishable, reported as a confidence-valid lower bound ε_LB; (2) three increasingly expressive attacks — direct target-edge detection, a Random Forest on handcrafted local statistics, and a GCN+MLP attack on 2-hop edge-removed subgraphs (§3); (3) the empirical finding that leakage is mechanism- and network-dependent, with learned representations revealing signal that fixed local summaries miss (§4, abstract). Throughout, the authors are careful that ε_LB bounds only the loss *witnessed* by the auditor and that null results certify nothing — a level of claim discipline many auditing papers lack.
The remaining sections cover Methodology Assessment, Statistical Evidence, Results & Reproducibility, Limitations & Risks, and Verdict & Recommendations.
- All 4 strengths & 5 weaknesses, analyzed in detail
- 4 risk flags with severity, section & reviewer questions
- Methods & statistical evidence assessment
- 5 questions a peer reviewer would ask
- Full six-dimension evaluation report & recommendations
One-time purchase · this paper only
One-time purchase, this paper only. AI-generated preliminary analysis — not peer review.
Frequently asked questions
What is a 'witnessed' privacy lower bound (ε_LB) in DP auditing?
It is the smallest privacy loss that a specific attacker's test can demonstrate with stated statistical confidence (here 95%, via Clopper–Pearson bounds). A large ε_LB proves the mechanism leaks at least that much; a small ε_LB only means this particular attack found nothing — it never certifies the claimed DP guarantee.
Which graph generators and datasets did this paper audit?
Randomized Response over edges (Karwa et al., 2014) and PrivGraph (community-based DP reconstruction, USENIX Security 2023), on Zachary's Karate Club (34 nodes, 78 edges) and the largest department of the Email-EU-core network (101 nodes, 745 edges), for nominal ε from 0.1 to 15 with 30 target edges per graph.
Did the audit find that any generator violates its differential privacy guarantee?
No. The largest leakage witnessed was 0.455 (PrivGraph, Karate Club, GNN attack, ε=15), far below the nominal budget. Randomized response's direct-edge attack tracked nominal ε closely, and structural attacks found almost nothing once the target edge was removed from the released graphs.
Is code available for this paper?
The paper does not announce its own code release. It states that the PrivGraph implementation adapts the public PGB benchmark code (commit 076a910) and provides a full hyperparameter, seed-formula and software-version specification in its Table 5.
About this review
This is an AI-generated preliminary review by Evolve.Pub, produced from the openly available text of the paper. It is not peer review and does not represent the authors' views. The canonical record of the paper is at the publisher link above.
- Figures 1–2 are available only as captions and garbled axis-tick text; curve shapes and boxplots could not be inspected, so figure-level readings rely on the prose.
- Tables 3–4 were extracted with layout garbling; numbers were cross-checked against Table 1 and the prose, but individual cells could be misaligned.
- Some ε_audit cells appear as '—inf' in the extraction; the original PDF formatting may differ.
- The appendices (B–D) appear complete in the extraction, but no external check against the arXiv source was performed.
Go deeper on this paper
Wrote a paper? Stress-test it before reviewers do.
Upload your manuscript for the same structured scrutiny — reasoning, statistics, evidence, figures, and reproducibility.