Boosting Black-Box Graph Reconstruction Attacks via Adjacency Relationship Recovery of Representative Nodes

Graph Neural Networks (GNNs) have been widely applied across various fields due to their effective modeling of graph data. However, the training data used in GNNs poses privacy risks as it contains sensitive information. Recently, graph reconstruction attacks have been proposed to reconstruct the adjacency matrix of the training dataset in graph neural networks, receiving significant attention due to their strong attack performance. Existing studies have demonstrated graph reconstruction attacks in both white-box and black-box settings. To further advance research in black-box scenarios, we propose ASM-GRA, a black-box graph reconstruction attack that reconstructs the adjacency matrix by attacking a substitute model trained on the target model. Furthermore, we propose a node selection strategy to reconstruct the adjacency relationships of representative nodes across multiple categories, which effectively enhances the accuracy of the entire reconstructed matrix. Extensive experiments on several public datasets demonstrate the effectiveness of our method. For instance, on the Citeseer dataset, we achieve an attack AUC of 0.95 and an attack AP of 0.951. Our code is available at https://github.com/jiangxinyu118/ASM-GRA .