# Large-Scale Privacy-Preserving Network Embedding against Private Link Inference Attacks

arXiv: https://arxiv.org/abs/2205.14440 · HTML: https://mlsanity.com/paper/2205.14440/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 42 references that are in the map.
- First posted on arXiv 28 May 2022.

## Builds on (most cited first, 22 of 22)

- [XGBoost: A Scalable Tree Boosting System](https://mlsanity.com/paper/1603.02754/) (2016)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [LINE: Large-scale Information Network Embedding](https://mlsanity.com/paper/1503.03578/) (2015)
- [Representation Learning on Graphs: Methods and Applications](https://mlsanity.com/paper/1709.05584/) (2017)
- [Adversarial Attack on Graph Structured Data](https://mlsanity.com/paper/1806.02371/) (2018)
- [Adversarial Attacks on Graph Neural Networks via Meta Learning](https://mlsanity.com/paper/1902.08412/) (2019)
- [Network Embedding as Matrix Factorization: Unifying DeepWalk, LINE, PTE, and node2vec](https://mlsanity.com/paper/1710.02971/) (2017)
- [Graph Embedding Techniques, Applications, and Performance: A Survey](https://mlsanity.com/paper/1705.02801/) (2017)
- [Adversarial Attacks on Node Embeddings via Graph Poisoning](https://mlsanity.com/paper/1809.01093/) (2018)
- [Quantifying Privacy Leakage in Graph Embedding](https://mlsanity.com/paper/2010.00906/) (2020)
- [Towards More Practical Adversarial Attacks on Graph Neural Networks](https://mlsanity.com/paper/2006.05057/) (2020)
- [A Restricted Black-box Adversarial Framework Towards Attacking Graph Embedding Models](https://mlsanity.com/paper/1908.01297/) (2019)
- [AttriGuard: A Practical Defense Against Attribute Inference Attacks via Adversarial Machine Learning](https://mlsanity.com/paper/1805.04810/) (2018)
- [You are Who You Know and How You Behave: Attribute Inference Attacks via Users' Social Friends and Behaviors](https://mlsanity.com/paper/1606.05893/) (2016)
- [Privacy-Preserving Representation Learning on Graphs: A Mutual Information Perspective](https://mlsanity.com/paper/2107.01475/) (2021)
- [Adversarial Privacy Preserving Graph Embedding against Inference Attack](https://mlsanity.com/paper/2008.13072/) (2020)
- [Data Poisoning Attack against Unsupervised Node Embedding Methods](https://mlsanity.com/paper/1810.12881/) (2018)
- [Information Obfuscation of Graph Neural Networks](https://mlsanity.com/paper/2009.13504/) (2020)
- [Managing your Private and Public Data: Bringing down Inference Attacks against your Privacy](https://mlsanity.com/paper/1408.3698/) (2014)
- [Privacy Games: Optimal User-Centric Data Obfuscation](https://mlsanity.com/paper/1402.3426/) (2014)
- [Target Defense Against Link-Prediction-Based Attacks via Evolutionary Perturbations](https://mlsanity.com/paper/1809.05912/) (2018)

## Built on by (most cited first, 1 of 1)

- [GraphPub: Generation of Differential Privacy Graph with High Availability](https://mlsanity.com/paper/2403.00030/) (2024)

## Abstract (arXiv)

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.