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 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.

本文提出了一种针对保护隐私的网络嵌入方法，使用干扰原始网络的方式来减少泄漏隐私链接的风险，并通过量化隐私增益和效用丢失来确定最佳干扰方案，以获得最优的隐私效用权衡。