Differential privacy preservation for graph auto-encoders: A novel anonymous graph publishing model

In recent years, the number of users in social networks has grown substantially, and more data-intensive applications have been developed. This creates a demand for the ability to mine large-scale graph data more efficiently, so that the information mined can be maximized (e.g., mining social relationships between people). However, the direct publication of the original graphs leads to potential leakage of users' privacy. Therefore, graph anonymization techniques are often utilized to process the original graphs. A key challenge of it lies in the balance between anonymity and usability. In this paper, we introduced the idea of graph auto-encoder, a fundamental element in graph neural networks, and proposed the Differential Privacy Deep Graph Auto-Encoder (DP-DGAE). Our main idea is to convert the anonymous graph publishing problem into a privacy-preserving problem for generative models, and optimize the models in terms of both privacy and usability using a multi-task learning approach. Theoretical analysis and experimental evaluations show that the DP-DGAE achieves anonymity while ensuring usability.