# Beyond Homophily: Towards Generalized Graph Reconstruction Attack and Defense

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 96 references that are in the map.
- First posted on arXiv 6 Jun 2026.

## Builds on (most cited first, 10 of 10)

- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Opening the Black Box of Deep Neural Networks via Information](https://mlsanity.com/paper/1703.00810/) (2017)
- [Adversarial Neural Network Inversion via Auxiliary Knowledge Alignment](https://mlsanity.com/paper/1902.08552/) (2019)
- [Text Revealer: Private Text Reconstruction via Model Inversion Attacks against Transformers](https://mlsanity.com/paper/2209.10505/) (2022)
- [Few-shot link prediction via graph neural networks for Covid-19 drug-repurposing](https://mlsanity.com/paper/2007.10261/) (2020)
- [Canary Extraction in Natural Language Understanding Models](https://mlsanity.com/paper/2203.13920/) (2022)
- [GraphDefense: Towards Robust Graph Convolutional Networks](https://mlsanity.com/paper/1911.04429/) (2019)
- [Degree-Preserving Randomized Response for Graph Neural Networks under Local Differential Privacy](https://mlsanity.com/paper/2202.10209/) (2022)
- [Privacy and Transparency in Graph Machine Learning: A Unified Perspective](https://mlsanity.com/paper/2207.10896/) (2022)
- [Comprehensive Analysis of Over-smoothing in Graph Neural Networks from Markov Chains Perspective](https://mlsanity.com/paper/2211.06605/) (2022)

## Abstract (arXiv)

Graph neural networks (GNNs) are widely deployed on relational data, yet they can leak sensitive or proprietary information about the training graph adjacency, e.g., social ties, transactions, and interactions. This work studies graph reconstruction attacks (GRA), a form of model inversion that reconstructs the training adjacency from a trained GNN, given different levels of attacker-side information. We first provide a systematic characterization of when and why adjacency becomes recoverable through features, labels, embeddings, and predictions, with leakage modulated by graph homophily, heterophily, and the model's inductive bias. Motivated by these findings, we view GNN inference through a Markov chain approximation lens, treating the layered forward computation as a chain of topology-dependent representations. Building on this view, we develop complementary attack and defense methods. On the attack side, we propose MC-GRA (+), which reconstructs the adjacency by optimizing a surrogate adjacency whose GNN-induced representations align with those of the target model at each layer. On the defense side, we propose MC-GPB (+), which suppresses adjacency-dependent information throughout the representation chain while aiming to preserve classification accuracy under a privacy-utility trade-off. Experiments across homophilic/heterophilic graph benchmarks and GNNs show that our attacks improve reconstruction fidelity over prior methods, while our defenses reduce reconstruction success with only minor accuracy loss.