PaperlayerView exact revision on arXiv

Source-linked AI summary

Empirical Auditing of Edge-Private Graph Generators

Anum Fatima, Stratis Limnios, James Adams, Lukasz Szpruch, Carsten Maple, Gesine Reinert, Andrew Elliott

arXiv:2609.25155v1stat.MLcs.LG

TL;DR

Sensitive network statistics may reveal relational information, and there is no widely adopted framework for auditing privacy leakage from graph-generation mechanisms. This paper tests whether outputs from edge-neighbouring inputs are distinguishable using direct, local-structural, and GNN-based attacks, and finds leakage patterns that vary by mechanism and network, with learned representations recovering signals missed by handcrafted summaries.

  • Problem

    Private graph-generator benchmarks have primarily evaluated utility, leaving no widely adopted framework for auditing the privacy leakage of the generation mechanism itself.

    Source: §1 · p. 1

  • Method

    The framework compares attacks on outputs from edge-neighbouring graphs and reports confidence-valid lower bounds on the privacy loss witnessed by those attacks.

    Source: §1 · p. 2, §2 · p. 2

  • Results

    Leakage varies by mechanism and network: RR’s edge auditor tracks nominal ε while its structural auditors show little leakage, and PrivGraph’s structural leakage appears on Karate Club but not sampled EU-core edges.

    Source: §4 · p. 4

  • Takeaways & Limitations

    Learned structural representations can recover leakage that fixed local summaries fail to expose, and the framework can help developers quantify attack-accessible privacy loss.

    Source: §4 · p. 4, §5 · p. 4

    The single-release evaluation on a small set of networks and attacks does not establish generality across graph geometries or adversarial strategies.

    Source: §5 · p. 5

Abstract

from arXiv · show

We empirically audit privacy leakage by testing whether outputs from edge-neighbouring inputs remain distinguishable, using statistically valid lower bounds on the privacy loss witnessed by our attacks. Our framework compares direct-edge, local-structural, and GNN-based attacks through the geometry surrounding a target edge. Experiments across two generators and two networks show that privacy leakage is both mechanism- and network-dependent, with learned representations revealing information not captured by conventional local statistics.

1 Introduction and Motivation

Sensitive relational data can be exposed through released network statistics, while existing work does not provide a widely adopted framework for auditing privacy leakage from graph-generation mechanisms themselves. The paper proposes adversarial distinguishability audits using increasingly expressive attacks and confidence-valid lower bounds on witnessed privacy loss.

1 Introduction and Motivation

  • Releasing statistics derived from sensitive relational networks may reveal information about those networks.The paper situates networks in transportation, biology, and social-science applications.Source: §1 · p. 1
  • Existing benchmarks mainly assess private graph generators’ utility, and related attacks study privacy leakage in differentially private graph learning.The paper identifies a lack of a widely adopted framework for auditing the graph-generation mechanism itself.Source: §1 · p. 1
  • The proposed framework tests whether outputs from edge-neighbouring graphs are distinguishable through the local structural footprint of their differing edge.It compares direct-edge, hand-crafted local-geometry, and GNN-based attacks, and derives confidence-valid lower bounds on witnessed privacy loss.Source: §1 · p. 2

2 Background and Auditing Framework

The auditing framework treats edge privacy as a distinguishability problem between outputs from neighboring graphs and estimates the privacy loss witnessed by an attack. It uses confidence-valid lower bounds, which provide evidence of leakage when large but do not certify the mechanism’s claimed guarantee when no loss is found.

2 Background and Auditing Framework

  • Edge-neighbouring graphs share a node set and differ in exactly one edge; edge differential privacy bounds output-event probabilities across such inputs.The framework expresses the privacy notion as a testing problem using true-positive and false-positive rates for a rejection region.Source: §2 · p. 2
  • The auditor repeatedly generates outputs from the edge-present and edge-absent inputs, then learns a scoring function to distinguish their distributions.The two sets of outputs form a balanced auditing dataset, and a threshold on the score defines the rejection region.Source: §2 · p. 2
  • Exact one-sided Clopper–Pearson bounds yield a statistically valid lower bound on attack-witnessed privacy loss.The error probability is Bonferroni-split to obtain the desired simultaneous confidence level.Source: §2 · p. 2
  • Figure 1 plots maximum εLB across 30 sampled target edges against nominal privacy budget and shows a boxplot at ε = 5.Colours and markers identify auditors; line styles identify generators.Source: Figure 1 · p. 3

3 Attack Models

The paper compares three attacks of increasing expressiveness on a common audit set: direct observation of the target edge, handcrafted local structural features, and a GNN-based representation of its surrounding subgraph.

3 Attack Models

  • All three attacks distinguish outputs from edge-present and edge-absent inputs and are evaluated on a common audit set using εLB.They are trained or tuned on training and validation data.Source: §3 · p. 3
  • The target-edge attack predicts membership using only whether the target edge appears in the privatized graph.It provides a baseline for direct edge leakage.Source: §3 · p. 3
  • The local geometric attack removes the target edge and classifies graphs from local connectivity, neighborhood overlap, distance, and clustering features.A Random Forest performs the classification.Source: §3 · p. 3
  • The GNN-based attack learns structural representations from the target edge’s k-hop neighborhood after that edge is removed.It pools node embeddings and combines them with common-neighbor information before an MLP produces the attack score.Source: §3 · p. 3

4 Experiments

The audits find that leakage depends on the generator, network, and information used by the auditor: direct-edge attacks reveal a different pattern from structural attacks, while GNNs can recover signals missed by handcrafted summaries.

Experimental setup

  • The experiments evaluate Randomised response and PrivGraph on Zachary's Karate Club and a 101-node, 745-edge largest-department Eu-core network.They examine six nominal privacy levels from ε = 0.1 to 15.Source: §4 · p. 3

Implementation

  • For each setting, the study samples 30 target edges, generates 10,000 releases per neighbouring-graph distribution, and reports ROC–AUC, ϵLB, and WL-based structural utility.A shared stratified 60/20/20% split separates training, validation, and audit data.Source: §4 · pp. 3–4

Witnessed Privacy Loss Across Networks and Privacy Levels

  • RR's Edge auditor tracks nominal ε on both networks, while its structural auditors show little leakage; PrivGraph leakage appears on Karate Club but not sampled EU-core edges.The table reports privacy utility (WL) and audit loss (ϵLB) over 30 sampled edges.Source: Table 1 · p. 4, §4 · p. 4
  • At large ε, RR's witnessed ϵLB saturates near 6.3, while PrivGraph's structural leakage increases on Karate Club and is not witnessed on sampled EU-core edges.The EU-core audit sampled 30 of its 745 edges, so the result does not rule out leakage on unsampled edges.Source: §4 · p. 4

What Information Drives Privacy Leakage?

  • For PrivGraph on Karate Club, learned GNN representations recover leakage that handcrafted local summaries may miss, while RR serves as a negative control after removing the target edge.The authors attribute the PrivGraph signal to information retained in the target edge's surrounding neighbourhood.Source: §4 · p. 4

5 Discussion

The discussion frames the audit as a way to measure attack-accessible leakage while emphasizing that witnessed loss is not a certificate of a mechanism's privacy guarantee. The notation section collects the graph, audit, and representation symbols used in the paper.

5 Discussion

  • The framework can help developers detect implementation errors, quantify attack-accessible privacy loss, and communicate the limits of private graph releases.The authors note a risk that more accurate communication of leakage could be abused by attackers.Source: §5 · pp. 4–5
  • The evaluation uses pure ε-edge DP, single-release inference, and a small set of networks and attacks, so it does not establish generality across graph geometries or adversarial strategies.Repeated-release auditing and broader graph families are left for future work.Source: §5 · p. 5

A Notation

  • The notation defines the target edge, privatised graph, auditor score, decision region, witnessed loss, and confidence-valid lower bound used in the audit.It also names the normalized degree, local distances, clustering coefficient, common-neighbour count, and pooled GNN representations used in structural attacks.Source: Table 2 · p. 8, A Notation · p. 8
  • Figure 2 plots average ϵLB across 30 target edges against nominal privacy budget and shows an ϵLB boxplot at ε = 5, with auditor and generator encoded by colour/marker and line style.Source: Figure 2 · p. 9

B Additional Details and Results for the Experiments

The supplementary experiments introduce two additional audit metrics: one for distinguishing advantage and one for the fraction of nominal privacy budget witnessed.

Additional details and results

Additional audit metrics

B.1 Zachary’s Karate Club Network

On Karate Club, RR tends to provide higher WL similarity than PrivGraph, while witnessed privacy loss is generally below the nominal ε except for RR’s Edge attack. Under PrivGraph, GNN attacks tend to yield the highest MIA advantage.

B.1 Zachary’s Karate Club Network

  • RR tends to provide higher WL similarity than PrivGraph, while its Edge attack’s witness is close to nominal ε; other witnesses are usually considerably lower.At ε = 15, the stated maximum theoretically possible witness bound is approximately 6.295 for the specified perfect-classifier case.Source: §B.1 · p. 9, Table 3 · p. 10
  • For PrivGraph, even the Edge attack witnesses privacy loss well below nominal ε, and GNN attacks tend to yield the highest MIA advantage at fixed ε.Source: §B.1 · p. 9, Table 3 · p. 10

B.2 EU-core Network

The EU-core experiment uses the largest department’s largest connected component and audits sampled existing edges under six nominal privacy levels. For RR, the Edge attack tends to recover nominal ε, while other attacks often have a witness lower bound of 0.

B.2 EU-core Network

  • EU-core is the 101-node, 745-edge graph formed from the largest department and its largest connected component; 30 existing edges are audited at each of six ε levels.Each target edge is retained in one input graph and removed in its edge-neighbouring counterpart before applying the generators and auditors.Source: §B.2 · p. 10
  • For RR on EU-core, the Edge attack tends to recover nominal ε, while other attacks often yield a witness lower bound of 0.Source: §B.2 · p. 10, Table 4 · p. 11

B.3 Experimental settings and Compute Resources

The appendix reports compute resources and the runtime of the full EU-core experiment, then introduces technical definitions and statistical procedures used in the paper.

B.3 Experimental settings and Compute Resources

  • Experiments ran on a server with two Intel Xeon Gold 6254 CPUs, 337 GB RAM, and an NVIDIA RTX A6000 GPU; graph generation and auditing were primarily CPU-based.Source: §B.3 · p. 11
  • The full EU-core experiment took approximately 10 hours over 15 CPU cores for 30 target edges, six ε values, three auditors, and both generators.Source: §B.3 · p. 11

C Technical Definitions

  • The technical-definitions section supplies terminology and technical details for the paper’s definitions and statistical procedures.Source: C Technical Definitions · p. 11

C.1 Network Statistics

The appendix specifies the structural statistics, private graph generators, audit procedure, and learned local representations used to assess edge privacy. It describes both handcrafted and GNN-based ways to test whether outputs from edge-neighbouring inputs remain distinguishable.

C.1 Network Statistics

  • The network summaries include node degree, shortest-path distance, local clustering coefficient, common neighbours, and Adamic–Adar weighting of common neighbours by degree.For the GNN auditor, the listed statistics are computed within the edge-removed local subgraph; degree and distances are normalised by subgraph degree and neighbourhood radius, respectively.Source: §C.1 · pp. 11, 13, 14

C.2 Differentially Private Graph Generators

  • Randomised Response independently perturbs each possible edge, while PrivGraph reconstructs graphs from noisy community-level and within-community degree summaries.PrivGraph generates within-community edges using a Chung–Lu model and between-community edges from noisy inter-community counts.Source: §C.2 · p. 14
  • PrivGraph first partitions nodes into communities and privately refines the partition using the exponential mechanism rather than independently perturbing individual edges.Its released edge state is determined indirectly through noisy structural summaries.Source: §C.2 · pp. 14–15

C.3 Interpreting differential privacy via a hypothesis test

  • The audit casts edge privacy as testing whether a released graph came from either of two inputs differing in one edge.A test with statistically supported operating characteristics incompatible with the DP inequalities witnesses a lower bound on privacy loss.Source: §C.3 · p. 15

C.4 Confidence Bounds for Privacy Auditing

  • Clopper–Pearson one-sided bounds and a Bonferroni correction yield a confidence-valid lower bound on the privacy loss witnessed at a selected threshold.The correction makes the component bounds hold jointly at the desired simultaneous confidence level.Source: §C.4 · pp. 15–16

C.5 WL Structural Utility

  • Structural utility is measured by normalised Weisfeiler–Lehman kernel similarity between each privatised graph and its corresponding neighbouring input graph.The reported setting-level value equally averages the two sample means, with mean and standard deviation reported across 30 target edges.Source: §C.5 · p. 16

D Learned Structural Representations Using GNNs

  • The GNN auditor uses an edge-removed, target-centred k-hop subgraph to compute local structural features and learn a representation of the target pair and its neighbourhood.Its representation combines endpoint embeddings, pooled neighbourhood embeddings, and the common-neighbour count.Source: D Learned Structural Representations… · p. 16, §D.3.1 · p. 18

D.2 Initial Node Features

  • The GNN auditor represents each node using structural features including normalised degree, scaled distances to both targets, and local clustering coefficient.Unreachable target distances are assigned k + 1 before scaling, and endpoint indicators identify the targets without revealing the released target-edge state.Source: §D.2 · p. 17

D.3.2 Classification and Training

The classifier uses the learned local representation to score privatised graphs. Because the target edge is removed before neighbourhood construction and message passing, distinguishability reflects surrounding structure rather than direct observation of its released state.

D.3.2 Classification and Training

  • The GNN representation is passed to a multilayer perceptron to produce the attack score, interpreted as the predicted probability that Y = 1.The GNN and classifier parameters are trained jointly using binary cross-entropy.Source: §D.3.2 · p. 18
  • The target edge is removed before neighbourhood construction, feature computation, and GNN message passing, so the auditor receives target-node identities but not the released edge state.Successful distinguishability therefore provides evidence that information about the target edge persists in the surrounding local structural representation.Source: §D.3.2 · p. 18
  • The resulting auditor distinguishes the neighbouring graph distributions using local structural information rather than direct access to the target edge in the released graph.The target edge is absent from the input throughout neighbourhood construction, feature computation, and message passing.Source: §D.3.2 · p. 18
Loading 2609.25155v1…