mlsanityData to 7 Oct 2026

On provable privacy vulnerabilities of graph representations

arXiv 2402.04033 ↗First posted 6 Feb 2024cs.LGcited by 1

Not on the map. Why?

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.

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

Builds on

36 of 49 references.

References · 36

  1. 2019PyTorch: An Imperative Style, High-Performance Deep Learning Librarycited by 20,160
  2. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  3. 2017Graph Attention Networkscited by 8,854
  4. 2017Inductive Representation Learning on Large Graphscited by 6,284
  5. 2018How Powerful are Graph Neural Networks?cited by 4,355
  6. 2015Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classificationcited by 3,590
  7. 2016Deep Learning with Differential Privacycited by 2,682
  8. 2019Fast Graph Representation Learning with PyTorch Geometriccited by 2,414
  9. 2018Spectral Normalization for Generative Adversarial Networkscited by 1,618
  10. 2019Simplifying Graph Convolutional Networkscited by 1,470
  11. 2016Revisiting Semi-Supervised Learning with Graph Embeddingscited by 970
  12. 2018The Secret Sharer: Evaluating and Testing Unintended Memorization in Neural Networkscited by 847
24 more
  1. 2020Geom-GCN: Geometric Graph Convolutional Networkscited by 821
  2. 2017Renyi Differential Privacycited by 643
  3. 2019GraphSAINT: Graph Sampling Based Inductive Learning Methodcited by 618
  4. 2017Representation Learning on Graphs: Methods and Applicationscited by 456
  5. 2017Community Detection and Stochastic Block Modelscited by 317
  6. 2021Adversary Instantiation: Lower Bounds for Differentially Private Machine Learningcited by 193
  7. 2022A Comprehensive Survey on Trustworthy Graph Neural Networks: Privacy, Robustness, Fairness, and Explainabilitycited by 118
  8. 2020Stealing Links from Graph Neural Networkscited by 114
  9. 2020Quantifying Privacy Leakage in Graph Embeddingcited by 82
  10. 2021LinkTeller: Recovering Private Edges from Graph Neural Networks via Influence Analysiscited by 65
  11. 2020Vertically Federated Graph Neural Network for Privacy-Preserving Node Classificationcited by 61
  12. 2021Optimization of Graph Neural Networks: Implicit Acceleration by Skip Connections and More Depthcited by 55
  13. 2021GraphMI: Extracting Private Graph Data from Graph Neural Networkscited by 50
  14. 2022A Non-Asymptotic Analysis of Oversmoothing in Graph Neural Networkscited by 49
  15. 2022GAP: Differentially Private Graph Neural Networks with Aggregation Perturbationcited by 46
  16. 2022Debugging Differential Privacy: A Case Study for Privacy Auditingcited by 39
  17. 2022Model Inversion Attacks against Graph Neural Networkscited by 26
  18. 2022RAW-GNN: RAndom Walk Aggregation based Graph Neural Networkcited by 25
  19. 2021Privacy-Preserving Representation Learning on Graphs: A Mutual Information Perspectivecited by 23
  20. 2023On Strengthening and Defending Graph Reconstruction Attack with Markov Chain Approximationcited by 16
  21. 2023Differentially Private Decoupled Graph Convolutions for Multigranular Topology Protectioncited by 12
  22. 2021DeepWalking Backwards: From Embeddings Back to Graphscited by 6
  23. 2023Privacy-preserving design of graph neural networks with applications to vertical federated learningcited by 2
  24. 2024Statistical Guarantees for Link Prediction using Graph Neural Networkscited by 2

Built on by

Cited by year

Citing papers per year: 2024: 1.

1 paper.

  1. 2024The Heterophilic Graph Learning Handbook: Benchmarks, Models, Theoretical Analysis, Applications and Challengescited by 29