Research map / Graph learning / Graph self-supervised learning
On provable privacy vulnerabilities of graph representations
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives non-asymptotic theory for similarity-based edge reconstruction attacks (SERA) on GNN representations, showing near-perfect reconstruction on sparse random graphs, failure on dense SBMs, and partial mitigation by noisy aggregation (NAG).
Problem
Edge reconstruction from graph neural network node representations via similarity thresholding is empirically effective, but its theoretical limits are unclear; it is also unknown how well noisy-aggregation privacy defenses resist it.
Approach
Non-asymptotic analysis of cosine/correlation-similarity edge reconstruction on linear GNN embeddings of sparse random graphs with isotropic Gaussian features (no homophily needed), lower bounds for dense SBMs, and error lower bounds for NAG-privatized GNNs that are tied to weight operator norms and noise scale.
Key results
- On the Cora dataset, the linear GNN with L=5 achieves AUROC of 95.9% for SERA on non-trained weights, and GCN L=2 reaches 99.8%.
- On Squirrel and Chameleon (heterophilic, feature homophily 0.01), GCN with L=2 attains AUROC 87.3% and 87.9% for non-trained SERA, far above the feature-similarity baseline (46.2% and 55.2%).
- Under the unconstrained NAG scheme with d>1024, SERA AUROC drops below 0.6 while Cora accuracy stays above 0.7.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use SERA on node representations instead of feature similarity | GCN (L=2), non-trained · Squirrel | AUROC (%): 46.2 -> 87.3 | Helped |
| Use SERA on node representations instead of feature similarity | GCN (L=2), non-trained · Chameleon | AUROC (%): 55.2 -> 87.9 | Helped |
| Use SERA on node representations instead of feature similarity | GCN (L=2), non-trained · Actor | AUROC (%): 44.7 -> 87.1 | Helped |
| Train the model rather than use randomly initialized weights | SERA with LIN and GCN · Eight real-world datasets | AUROC (%) | Mixed |
| Increase GNN depth from L=2 to L=5 | SERA with LIN and GCN · Eight real-world datasets | AUROC (%) | Mixed |
| Use larger feature dimension in the unconstrained NAG scheme | SERA against NAG representations · Cora | AUROC: AUROC <0.6 | Hurt |
| Use larger feature dimension in the unconstrained NAG scheme | NAG model utility · Cora | Accuracy: >0.7 Accuracy | No clear effect |
| Add noisy aggregation to graph representations | SERA · Any graph | Inference error: 1 - \sqrt{1 - \exp \left(-C\dfrac{\sum_{l \in [L]} \opnorm{W_l}^2}{\sigma^2}\right)} | Helped |
Surprising findings
- Feature similarity is not necessary for SERA to succeed: heterophilic graphs with near-zero feature homophily remain highly vulnerable.
- Increasing GNN depth does not reliably increase attack success, and post-training representations are often less vulnerable than randomly initialized ones.
Experimental setup
Datasets: Cora Citeseer Pubmed Squirrel Chameleon Actor Amazon-Products Reddit Erdős–Rényi graphs stochastic block models
Benchmarks: Cora Citeseer Pubmed Squirrel Chameleon Actor Amazon-Products Reddit
Metrics: AUROC FPR FNR ERR
Baselines: EdgeRR GraphMI LinkTeller DeepWalk-based reconstruction
Builds on: noisy aggregation (NAG) edge differential privacy spectral normalization
Closest papers by meaning
- Can Graph Neural Networks Expose Training Data Properties? An Efficient Risk Assessment Approach (NeurIPS 2024 · similarity 0.87)
- GRAIN: Exact Graph Reconstruction from Gradients (ICLR 2025 · similarity 0.86)
- When Witnesses Defend: A Witness Graph Topological Layer for Adversarial Graph Learning (AAAI 2025 · similarity 0.86)
- Going Deeper into Locally Differentially Private Graph Neural Networks (ICML 2025 · similarity 0.86)
- GraphIP–Bench: How Hard Is It to Steal a Graph Neural Network, and Can We Stop It? (NeurIPS 2026 · similarity 0.85)
- Federated Graph Condensation with Information Bottleneck Principles (AAAI 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.