Privacy-Preserving Network Embedding Against Private Link Inference Attacks

Network embedding represents network nodes by a low-dimensional informative vector. While it is generally effective for various downstream tasks, it may leak some private information of networks, such as hidden private links. In this work, we address a novel problem of privacy-preserving network embedding against private link inference attacks. Basically, we propose to perturb the original network by adding or removing links, and expect the embedding generated on the perturbed network can leak little information about private links but hold high utility for various downstream tasks. Towards this goal, we first propose general measurements to quantify privacy gain and utility loss incurred by candidate network perturbations; we then design a Privacy-Preserving Network Embedding (i.e., PPNE) framework to identify the optimal perturbation solution with the best privacy-utility trade-off in an iterative way. Furthermore, we propose many techniques to accelerate PPNE and ensure its scalability. For instance, as the skip-gram embedding methods including DeepWalk and LINE can be seen as matrix factorization with closed-form embedding results, we devise efficient privacy gain and utility loss approximation methods to avoid the repetitive time-consuming embedding training for every candidate network perturbation in each iteration. Experiments on real-life network datasets (with up to millions of nodes) verify that PPNE outperforms baselines by sacrificing less utility and obtaining higher privacy protection.

I. Introduction

Data publishing has become imperative for comprehensive data exploration and utilization [1], [2], [3], [4]. Network data such as citation networks, social networks, and communication networks, is ubiquitous in human life and useful for many applications [5], [6], [7]. While network structure is directly published in tradition, network embedding has become a good substitution for publishing along with the prosperity of the network embedding techniques. In particular, network embedding techniques [8], [9] typically represent each node by a low-dimensional dense vector which can be effectively used for a variety of downstream tasks like node classification [10], [11], [12], [13], [14], and clustering [15].