# On Strengthening and Defending Graph Reconstruction Attack with Markov Chain Approximation

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- Builds on 48 of its 83 references that are in the map.
- First posted on arXiv 15 Jun 2023.

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

- [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)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Extracting Training Data from Large Language Models](https://mlsanity.com/paper/2012.07805/) (2020)
- [Similarity of Neural Network Representations Revisited](https://mlsanity.com/paper/1905.00414/) (2019)
- [Variational Graph Auto-Encoders](https://mlsanity.com/paper/1611.07308/) (2016)
- [Graph Contrastive Learning with Augmentations](https://mlsanity.com/paper/2010.13902/) (2020)
- [Link Prediction Based on Graph Neural Networks](https://mlsanity.com/paper/1802.09691/) (2018)
- [Deep Learning and the Information Bottleneck Principle](https://mlsanity.com/paper/1503.02406/) (2015)
- [Graph Neural Networks for Social Recommendation](https://mlsanity.com/paper/1902.07243/) (2019)
- [DropEdge: Towards Deep Graph Convolutional Networks on Node Classification](https://mlsanity.com/paper/1907.10903/) (2019)
- [GraphSAINT: Graph Sampling Based Inductive Learning Method](https://mlsanity.com/paper/1907.04931/) (2019)
- [Opening the Black Box of Deep Neural Networks via Information](https://mlsanity.com/paper/1703.00810/) (2017)
- [Graph Neural Networks in Recommender Systems: A Survey](https://mlsanity.com/paper/2011.02260/) (2020)
- [Adversarial Attack on Graph Structured Data](https://mlsanity.com/paper/1806.02371/) (2018)
- [Neural Bellman-Ford Networks: A General Graph Neural Network Framework for Link Prediction](https://mlsanity.com/paper/2106.06935/) (2021)
- [The Secret Revealer: Generative Model-Inversion Attacks Against Deep Neural Networks](https://mlsanity.com/paper/1911.07135/) (2019)
- [struc2vec: Learning Node Representations from Structural Identity](https://mlsanity.com/paper/1704.03165/) (2017)
- [Stochastic Beams and Where to Find Them: The Gumbel-Top-k Trick for Sampling Sequences Without Replacement](https://mlsanity.com/paper/1903.06059/) (2019)
- [Interpretable and Generalizable Graph Learning via Stochastic Attention Mechanism](https://mlsanity.com/paper/2201.12987/) (2022)
- [Graph Information Bottleneck](https://mlsanity.com/paper/2010.12811/) (2020)
- [Labeling Trick: A Theory of Using Graph Neural Networks for Multi-Node Representation Learning](https://mlsanity.com/paper/2010.16103/) (2020)
- [Stealing Links from Graph Neural Networks](https://mlsanity.com/paper/2005.02131/) (2020)
- [Node-Level Membership Inference Attacks Against Graph Neural Networks](https://mlsanity.com/paper/2102.05429/) (2021)
- [Quantifying Privacy Leakage in Graph Embedding](https://mlsanity.com/paper/2010.00906/) (2020)
- [Variational Model Inversion Attacks](https://mlsanity.com/paper/2201.10787/) (2022)
- [Reparameterizable Subset Sampling via Continuous Relaxations](https://mlsanity.com/paper/1901.10517/) (2019)

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

- [Does Invariant Graph Learning via Environment Augmentation Learn Invariance?](https://mlsanity.com/paper/2310.19035/) (2023)
- [Privacy Leakage on DNNs: A Survey of Model Inversion Attacks and Defenses](https://mlsanity.com/paper/2402.04013/) (2024)
- [From Passive to Active Reasoning: Can Large Language Models Ask the Right Questions under Incomplete Information?](https://mlsanity.com/paper/2506.08295/) (2025)
- [Detecting Machine-Generated Texts by Multi-Population Aware Optimization for Maximum Mean Discrepancy](https://mlsanity.com/paper/2402.16041/) (2024)
- [Towards Tracing Trustworthiness Dynamics: Revisiting Pre-training Period of Large Language Models](https://mlsanity.com/paper/2402.19465/) (2024)
- [FedImpro: Measuring and Improving Client Update in Federated Learning](https://mlsanity.com/paper/2402.07011/) (2024)
- [Model Inversion Attacks: A Survey of Approaches and Countermeasures](https://mlsanity.com/paper/2411.10023/) (2024)
- [Neural Atoms: Propagating Long-range Interaction in Molecular Graphs through Efficient Communication Channel](https://mlsanity.com/paper/2311.01276/) (2023)
- [Combating Bilateral Edge Noise for Robust Link Prediction](https://mlsanity.com/paper/2311.01196/) (2023)
- [Rethinking the impact of noisy labels in graph classification: A utility and privacy perspective](https://mlsanity.com/paper/2406.07314/) (2024)
- [Rank Matters: Understanding and Defending Model Inversion Attacks via Low-Rank Feature Filtering](https://mlsanity.com/paper/2410.05814/) (2024)
- [Intellectual Property in Graph-Based Machine Learning as a Service: Attacks and Defenses](https://mlsanity.com/paper/2508.19641/) (2025)
- [On provable privacy vulnerabilities of graph representations](https://mlsanity.com/paper/2402.04033/) (2024)
- [AI Security in the Foundation Model Era: A Comprehensive Survey from a Unified Perspective](https://mlsanity.com/paper/2603.24857/) (2026)
- [Towards Deeper Understanding of PPR-based Embedding Approaches: A Topological Perspective](https://mlsanity.com/paper/2405.19649/) (2024)
- [How Feasible is Augmenting Fake Nodes with Learnable Features as a Counter-strategy against Link Stealing Attacks?](https://mlsanity.com/paper/2503.09726/) (2025)

## Abstract (arXiv)

Although powerful graph neural networks (GNNs) have boosted numerous real-world applications, the potential privacy risk is still underexplored. To close this gap, we perform the first comprehensive study of graph reconstruction attack that aims to reconstruct the adjacency of nodes. We show that a range of factors in GNNs can lead to the surprising leakage of private links. Especially by taking GNNs as a Markov chain and attacking GNNs via a flexible chain approximation, we systematically explore the underneath principles of graph reconstruction attack, and propose two information theory-guided mechanisms: (1) the chain-based attack method with adaptive designs for extracting more private information; (2) the chain-based defense method that sharply reduces the attack fidelity with moderate accuracy loss. Such two objectives disclose a critical belief that to recover better in attack, you must extract more multi-aspect knowledge from the trained GNN; while to learn safer for defense, you must forget more link-sensitive information in training GNNs. Empirically, we achieve state-of-the-art results on six datasets and three common GNNs. The code is publicly available at: https://github.com/tmlr-group/MC-GRA.