Beyond Homophily: Toward Generalized Graph Reconstruction Attacks and Defenses against GNNs

The researchers propose a generalized graph reconstruction attack MC-GRA(+) against graph neural networks and a companion defense MC-GPB(+), studying the model inversion risk of recovering the adjacency structure of the training graph from a trained GNN. The paper systematically characterizes when and why the adjacency structure can be recovered via features, labels, embeddings and predictions, and how the degree of leakage is modulated by graph homophily, heterophily and model inductive bias; the attack method views GNN inference from a Markov chain approximation perspective, optimizing a surrogate adjacency layer by layer so that its induced representations align with the target model, while the defense method suppresses adjacency-dependent information along the entire representation chain to trade off privacy and utility. Experiments on homophilic and heterophilic graph benchmarks and multiple GNNs show that the attack's reconstruction fidelity is better than prior methods, and the defense reduces the reconstruction success rate while incurring only a small accuracy loss.