# On provable privacy vulnerabilities of graph representations

arXiv: https://arxiv.org/abs/2402.04033 · HTML: https://mlsanity.com/paper/2402.04033/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 36 of its 49 references that are in the map.
- First posted on arXiv 6 Feb 2024.

## Builds on (most cited first, 30 of 36)

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classification](https://mlsanity.com/paper/1502.01852/) (2015)
- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Spectral Normalization for Generative Adversarial Networks](https://mlsanity.com/paper/1802.05957/) (2018)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Revisiting Semi-Supervised Learning with Graph Embeddings](https://mlsanity.com/paper/1603.08861/) (2016)
- [The Secret Sharer: Evaluating and Testing Unintended Memorization in Neural Networks](https://mlsanity.com/paper/1802.08232/) (2018)
- [Geom-GCN: Geometric Graph Convolutional Networks](https://mlsanity.com/paper/2002.05287/) (2020)
- [Renyi Differential Privacy](https://mlsanity.com/paper/1702.07476/) (2017)
- [GraphSAINT: Graph Sampling Based Inductive Learning Method](https://mlsanity.com/paper/1907.04931/) (2019)
- [Representation Learning on Graphs: Methods and Applications](https://mlsanity.com/paper/1709.05584/) (2017)
- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Adversary Instantiation: Lower Bounds for Differentially Private Machine Learning](https://mlsanity.com/paper/2101.04535/) (2021)
- [A Comprehensive Survey on Trustworthy Graph Neural Networks: Privacy, Robustness, Fairness, and Explainability](https://mlsanity.com/paper/2204.08570/) (2022)
- [Stealing Links from Graph Neural Networks](https://mlsanity.com/paper/2005.02131/) (2020)
- [Quantifying Privacy Leakage in Graph Embedding](https://mlsanity.com/paper/2010.00906/) (2020)
- [LinkTeller: Recovering Private Edges from Graph Neural Networks via Influence Analysis](https://mlsanity.com/paper/2108.06504/) (2021)
- [Vertically Federated Graph Neural Network for Privacy-Preserving Node Classification](https://mlsanity.com/paper/2005.11903/) (2020)
- [Optimization of Graph Neural Networks: Implicit Acceleration by Skip Connections and More Depth](https://mlsanity.com/paper/2105.04550/) (2021)
- [GraphMI: Extracting Private Graph Data from Graph Neural Networks](https://mlsanity.com/paper/2106.02820/) (2021)
- [A Non-Asymptotic Analysis of Oversmoothing in Graph Neural Networks](https://mlsanity.com/paper/2212.10701/) (2022)
- [GAP: Differentially Private Graph Neural Networks with Aggregation Perturbation](https://mlsanity.com/paper/2203.00949/) (2022)
- [Debugging Differential Privacy: A Case Study for Privacy Auditing](https://mlsanity.com/paper/2202.12219/) (2022)
- [Model Inversion Attacks against Graph Neural Networks](https://mlsanity.com/paper/2209.07807/) (2022)
- [RAW-GNN: RAndom Walk Aggregation based Graph Neural Network](https://mlsanity.com/paper/2206.13953/) (2022)

## Built on by (most cited first, 1 of 1)

- [The Heterophilic Graph Learning Handbook: Benchmarks, Models, Theoretical Analysis, Applications and Challenges](https://mlsanity.com/paper/2407.09618/) (2024)

## Abstract (arXiv)

Graph representation learning (GRL) is critical for extracting insights from complex network structures, but it also raises security concerns due to potential privacy vulnerabilities in these representations. This paper investigates the structural vulnerabilities in graph neural models where sensitive topological information can be inferred through edge reconstruction attacks. Our research primarily addresses the theoretical underpinnings of similarity-based edge reconstruction attacks (SERA), furnishing a non-asymptotic analysis of their reconstruction capacities. Moreover, we present empirical corroboration indicating that such attacks can perfectly reconstruct sparse graphs as graph size increases. Conversely, we establish that sparsity is a critical factor for SERA's effectiveness, as demonstrated through analysis and experiments on (dense) stochastic block models. Finally, we explore the resilience of private graph representations produced via noisy aggregation (NAG) mechanism against SERA. Through theoretical analysis and empirical assessments, we affirm the mitigation of SERA using NAG . In parallel, we also empirically delineate instances wherein SERA demonstrates both efficacy and deficiency in its capacity to function as an instrument for elucidating the trade-off between privacy and utility.