Structure-Preference Enabled Graph Embedding Generation under Differential Privacy
This work addresses privacy concerns in graph analysis for applications like social networks, offering a novel approach to balance utility and protection, though it is incremental by building on skip-gram techniques.
The paper tackles the problem of preserving privacy in graph embedding generation by introducing SE-PrivGEmb, a method that uses differential privacy to protect sensitive information while maintaining structural preferences, achieving superior performance in structural equivalence and link prediction tasks compared to existing state-of-the-art methods.
Graph embedding generation techniques aim to learn low-dimensional vectors for each node in a graph and have recently gained increasing research attention. Publishing low-dimensional node vectors enables various graph analysis tasks, such as structural equivalence and link prediction. Yet, improper publication opens a backdoor to malicious attackers, who can infer sensitive information of individuals from the low-dimensional node vectors. Existing methods tackle this issue by developing deep graph learning models with differential privacy (DP). However, they often suffer from large noise injections and cannot provide structural preferences consistent with mining objectives. Recently, skip-gram based graph embedding generation techniques are widely used due to their ability to extract customizable structures. Based on skip-gram, we present SE-PrivGEmb, a structure-preference enabled graph embedding generation under DP. For arbitrary structure preferences, we design a unified noise tolerance mechanism via perturbing non-zero vectors. This mechanism mitigates utility degradation caused by high sensitivity. By carefully designing negative sampling probabilities in skip-gram, we theoretically demonstrate that skip-gram can preserve arbitrary proximities, which quantify structural features in graphs. Extensive experiments show that our method outperforms existing state-of-the-art methods under structural equivalence and link prediction tasks.