Synthetic Twins for Ranking Graph Privacy Leakage

Graph neural networks (GNNs) compute each node's representation by repeatedly averaging information from its neighbors, a step called message passing. That step spreads private information: a node's sensitive attributes and its private friendships leak into its neighbors' embeddings and into the model's outputs. Attacks that exploit this leak are strong. Defenses differ a lot in how well they work, and which one is safest depends on the graph. The practical problem is that the only way to learn which GNN configuration leaks least on a hospital's patient graph or a bank's customer graph is to attack that graph, which is exactly the activity its owner wants to avoid. This note asks whether a cheap synthetic graph can stand in for the private one. The synthetic graph would match a handful of privately released structural statistics, and it only has to answer one question: which candidate configurations leak more and which leak less. It does not need to predict the absolute attack success rates.

The bet rests on a mechanism, not on generic generator fidelity. Theory and experiments show that message passing amplifies leakage only once homophily (the tendency of linked nodes to share labels or attributes) crosses a threshold, and that a model with $k$ layers has exactly zero influence beyond $k$ hops. If that is how leakage works, then the ordering of configurations by leakage should be controlled by a few quantities: homophily, the degree distribution, and how strongly node features predict the sensitive attribute. A synthetic "twin" matched on those quantities should preserve the leakage ranking. It should also fail in a predictable way: rankings should flip mainly when the twin and the real graph sit on opposite sides of the amplification threshold.

Core Claim

A degree-corrected stochastic block model (a random-graph generator that places nodes in communities and controls each node's expected degree) can be matched to three statistics released with differential privacy (DP, a formal guarantee that limits what can be learned about any one record): label and sensitive-attribute homophily, the degree histogram, and feature–attribute separability. When matched this way, it ranks GNN architectures and privacy defenses by measured leakage with high Spearman correlation to the ranking on the real graph. Two things make this new. First, the evaluation target is leakage ranking, not utility ranking. Second, we predict that ranking errors are concentrated near the homophily amplification threshold. Away from the threshold, a crude twin should suffice. Near it, homophily must be matched precisely.

Where This Sits in Prior Work

The synthetic-to-real literature supplies the evaluation logic. Synthetic data for model selection shows that synthetic validation sets only need to preserve model ordering. In that work, calibrated diffusion-generated ImageNet data reaches a Spearman correlation of 0.986 with real performance, and reweighting against five "anchor" models rescues even a generator whose raw correlation was negative. GraphUniverse carries this to graphs. It generates block-model graph families whose utility rankings of GCN, GATv2, GIN and GraphSAGE correlate with real inductive benchmarks at Spearman "often > 0.8". GraphUniverse never measures any attack. PATE-GAN introduced ranking agreement as a criterion for private synthetic data, but only for tabular classifiers. SynthPAI is the nearest privacy precedent: synthetic Reddit threads preserve the ranking of 18 LLMs on attribute inference. Its leakage comes from text reasoning, not from structural propagation. We reuse the ranking-agreement methodology from these papers and change what is being ranked.

The leakage literature supplies the mechanism and the things we must rank. Unveiling the Role of Message Passing in Dual-Privacy Preservation on GNNs proves on random graphs that leakage amplification switches on above a homophily threshold, and proposes the DPPGNN defense. Its synthetic graphs check the theory; they are not used as an evaluation proxy. LinkTeller recovers private edges by perturbing node features and watching how other nodes' outputs move, with near-100% precision on Twitch, PPI and Flickr. It also shows that DP below $\epsilon=5$ pushes GCN accuracy down to the level of a graph-free MLP. Information Obfuscation of Graph Neural Networks (GAL), DPAR, and the GAP/DP-GCN comparison in Privacy-Utility Trade-offs in Neural Networks for Medical Population Graphs provide the defenses.

The medical-graph paper is the closest existing work and also the strongest motivation. It sweeps homophily from 0.5 to 0.9 on synthetic population graphs and finds that DP-GCN's utility collapses at low homophily while GAP stays stable. That is a ranking that depends on homophily. The paper never asks whether its synthetic sweep reproduces the defense ordering on its real clinical graphs. It also reports that higher accuracy tends to mean higher membership-inference vulnerability, which raises a serious objection we take up below: perhaps leakage ranking is just utility ranking in disguise.

Two findings limit the design. GraphUniverse notes that block models cannot produce specific motifs and use Gaussian features. We therefore restrict the study to node-level social, citation and population graphs and exclude molecules. Synthetic data for model selection warns that generator blind spots make proxies blind to failures on unmodeled slices. That warning is why we report where rankings flip, not only the average correlation.

Research Program

The first step is building the twin. The graph owner releases, under edge-level or node-level DP, four things: the degree histogram; a block-mixing matrix over labels and over the sensitive attribute, from which homophily is computed; per-block feature means and covariances, which fix how separable the features are; and the graph size. The released statistics carry their own privacy budget, which we report alongside the results. The auditor fits a degree-corrected block model to these statistics, extending GraphUniverse's generator so that the sensitive attribute is a second block variable with its own homophily, and samples several twins.

The second step is defining the candidate set and the leakage measurements. Candidates are GCN, GraphSAGE, GAT and GIN at depths 1 to 3, plus DP-GCN, GAP and DPAR at $\epsilon \in \{1,2,4,8\}$, GAL, and DPPGNN. That gives about 30 configurations. Each candidate is trained and attacked identically on the twin and on the real graph. The attacks are LinkTeller edge recovery (scored by AUC), a confidence-based membership inference attack (scored by AUC), and a sensitive-attribute probe on the embeddings (scored by AUC). Utility accuracy is recorded too.

The third step is mechanism analysis. For each real graph we compute $\Delta h = h_{\text{twin}} - h_{\text{real}}$, the gap in sensitive-attribute homophily, and we also measure each graph's distance from the empirical amplification threshold $h^*$, estimated from homophily sweeps. Our prediction is that rank disagreement grows with $|\Delta h|$ much faster when $h_{\text{real}}$ is near $h^*$. If the error instead grows evenly everywhere, the mechanistic story is wrong and the twin is just a weak generic proxy.

The fourth step is an optional calibration, which spends a little real-graph budget. Following Synthetic data for model selection, we audit three to five anchor configurations on the real graph and reweight twin nodes, using ridge regression, so that twin leakage matches those anchors. We then measure how much ranking fidelity each real audit buys.

Baselines

The naive reference point is to pick the default configuration, a two-layer GCN with DP-GCN at a fixed $\epsilon$, or equivalently a random ranking. It sets the floor for Spearman correlation (zero in expectation) and for selection regret, defined below.

The baseline that worries us most is ranking by utility. Because the medical-graph paper found that more accurate models are more vulnerable to membership inference, simply ranking configurations by their utility on a GraphUniverse-style graph might reproduce the leakage ranking for free. We run it on exactly the same twins and candidates and correlate the utility ordering with real leakage. The twin approach beats it only if its leakage-ranking Spearman is higher on at least the edge and attribute attacks. We expect edge leakage to depend on depth and aggregation, following LinkTeller's influence argument, more than on accuracy.

The second strong competitor is a public surrogate. For each "private" graph, we take the most statistically similar other public graph in our pool and use its real leakage ranking. This tests whether a real graph from a related domain beats a matched synthetic one.

The third is the unmatched generic synthetic graph. This is a default GraphUniverse family, plus the fixed 0.5 and 0.9 homophily graphs from the medical-graph study, with no matching to the target. Its utility rankings reach Spearman "often > 0.8" against real benchmarks (GraphUniverse). We found no reported result on Lacuna for any synthetic-to-real leakage-ranking correlation, so that number does not exist yet. As a benchmark target, we consider the twin successful if its median leakage Spearman across real graphs exceeds 0.8, matching the utility-level fidelity, and clearly exceeds both the generic graph and the utility proxy.

Two ablations isolate the key ingredient. In the first, the twin matches everything except sensitive-attribute homophily, which is set to the population mean. In the second, the twin matches everything except feature separability. If dropping homophily matching does not hurt, mainly near the threshold, the core claim fails.

For fairness, every method uses the same candidate set, the same attack hyperparameters, a fixed tuning budget of the same number of trials per configuration, and five seeds per twin and per real graph. All reported correlations come with bootstrap intervals over seeds.

Why not just…?

Why not just rank by utility, since accurate models leak more? This is a genuine threat. For membership inference it may well be enough. Our experiments settle it per attack: if utility rank matches twin leakage rank on all three attacks, we will report that the cheaper utility proxy suffices and the twin adds nothing. We expect it to fail for edge recovery and attribute inference. LinkTeller's influence depends on depth and on how the aggregation step combines neighbors, and DPAR shows that decoupled designs can keep accuracy (0.8569 vs. 0.6563 for GAP on MS Academic at $\epsilon=1$, DPAR) while changing how information is propagated.

Why not just audit a public graph from a similar domain? Public graphs are free to attack, but their homophily is whatever it happens to be. If the private graph sits near the amplification threshold and the surrogate does not, the mechanism predicts the ranking will invert. The public-surrogate baseline tests this directly. If it matches the twin, the conclusion is that domain similarity matters more than structural matching, and we will say so.

Why not just audit a held-out piece of the real graph? That still means attacking the private data. Because message passing spreads information across $k$ hops, a held-out subgraph either keeps its boundary edges, and so stays exposed through them, or is cut loose, which changes its density and homophily. The calibration step measures how much real auditing is actually needed: if three anchors on the real graph lift an unmatched twin to the matched twin's fidelity, a small real audit is the better trade, and we report it as such.

Proposed Experiments

The real graphs, treated as private but with leakage measurable, are Twitch, PPI and Flickr (used in LinkTeller); Rochester38, Yale4, German Credit and Recidivism (from the DPPGNN study, which provides sensitive attributes); Cora-ML, MS Academic, CS and Physics (from DPAR); and TADPOLE and ABIDE (medical population graphs built as $k$-nearest-neighbor graphs with $k=5$). Sanity anchors from the literature are LinkTeller's near-100% top-edge precision on undefended GCNs and DPPGNN's reported 10.8% link-protection gain over DPGCN on Rochester38. We reproduce these first, so that the leakage measurements are trustworthy before any correlations are computed.

The primary metrics are the Spearman and Kendall correlation between twin and real leakage rankings for each attack, and selection regret. Selection regret is computed by picking, on the twin, the most accurate configuration whose leakage AUC stays under a budget, then measuring on the real graph how far it exceeds that budget and how much accuracy it gives up against the true real-graph choice. Regret matters more than correlation, because practitioners act on the top pick.

Three checks decide the outcome. The first is whether the matched twin beats both the utility-rank proxy and the generic synthetic graph on edge and attribute leakage ranking across a majority of the real graphs. The second is whether the homophily-unmatched ablation loses fidelity specifically on graphs near the estimated threshold, which is the signature of the amplification mechanism. The third is whether the conclusions survive charging the DP cost of the released statistics: we repeat the study with statistics released at $\epsilon = 0.5$ and $1$ to show that fidelity does not depend on spending privacy freely. If the first check passes but the second fails, we have a useful proxy without a mechanistic explanation. If the first fails, the negative result is still worth publishing, because it would show that GNN privacy audits cannot be moved off the real graph by block-model synthesis.