On Strengthening and Defending Graph Reconstruction Attack with Markov
  Chain Approximation
Zhanke Zhou Chenyu Zhou Xuan Li Jiangchao Yao Quanming Yao Bo Han
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.