# Structure-Preference Enabled Graph Embedding Generation under Differential Privacy

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 32 of its 60 references that are in the map.
- First posted on arXiv 7 Jan 2025.

## Builds on (most cited first, 30 of 32)

- [Efficient Estimation of Word Representations in Vector Space](https://mlsanity.com/paper/1301.3781/) (2013)
- [Distributed Representations of Words and Phrases and their Compositionality](https://mlsanity.com/paper/1310.4546/) (2013)
- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (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)
- [Link Prediction Based on Graph Neural Networks](https://mlsanity.com/paper/1802.09691/) (2018)
- [LINE: Large-scale Information Network Embedding](https://mlsanity.com/paper/1503.03578/) (2015)
- [Subsampled R'enyi Differential Privacy and Analytical Moments Accountant](https://mlsanity.com/paper/1808.00087/) (2018)
- [Differentially Private Learning Needs Better Features (or Much More Data)](https://mlsanity.com/paper/2011.11660/) (2020)
- [R'enyi Differential Privacy of the Sampled Gaussian Mechanism](https://mlsanity.com/paper/1908.10530/) (2019)
- [Network Embedding as Matrix Factorization: Unifying DeepWalk, LINE, PTE, and node2vec](https://mlsanity.com/paper/1710.02971/) (2017)
- [Tempered Sigmoid Activations for Deep Learning with Differential Privacy](https://mlsanity.com/paper/2007.14191/) (2020)
- [PTE: Predictive Text Embedding through Large-scale Heterogeneous Text Networks](https://mlsanity.com/paper/1508.00200/) (2015)
- [AdaCliP: Adaptive Clipping for Private SGD](https://mlsanity.com/paper/1908.07643/) (2019)
- [Differentially Private Model Publishing for Deep Learning](https://mlsanity.com/paper/1904.02200/) (2019)
- [Differentially Private Optimization on Large Model at Small Cost](https://mlsanity.com/paper/2210.00038/) (2022)
- [GAP: Differentially Private Graph Neural Networks with Aggregation Perturbation](https://mlsanity.com/paper/2203.00949/) (2022)
- [Differentially Private Federated Knowledge Graphs Embedding](https://mlsanity.com/paper/2105.07615/) (2021)
- [Node-Level Differentially Private Graph Neural Networks](https://mlsanity.com/paper/2111.15521/) (2021)
- [Learning Differentially Private Recurrent Language Models](https://mlsanity.com/paper/1710.06963/) (2017)
- [Releasing Graph Neural Networks with Differential Privacy Guarantees](https://mlsanity.com/paper/2109.08907/) (2021)
- [Improving Deep Learning with Differential Privacy using Gradient Encoding and Denoising](https://mlsanity.com/paper/2007.11524/) (2020)
- [Secure Deep Graph Generation with Link Differential Privacy](https://mlsanity.com/paper/2005.00455/) (2020)
- [ProGAP: Progressive Graph Neural Networks with Differential Privacy Guarantees](https://mlsanity.com/paper/2304.08928/) (2023)
- [Preserving Node-level Privacy in Graph Neural Networks](https://mlsanity.com/paper/2311.06888/) (2023)
- [DPAR: Decoupled Graph Neural Networks with Node-Level Differential Privacy](https://mlsanity.com/paper/2210.04442/) (2022)
- [DPSUR: Accelerating Differentially Private Stochastic Gradient Descent Using Selective Update and Release](https://mlsanity.com/paper/2311.14056/) (2023)
- [Stochastic Adaptive Line Search for Differentially Private Optimization](https://mlsanity.com/paper/2008.07978/) (2020)
- [Understanding and Improvement of Adversarial Training for Network Embedding from an Optimization Perspective](https://mlsanity.com/paper/2105.08007/) (2021)
- [FedWalk: Communication Efficient Federated Unsupervised Node Embedding with Differential Privacy](https://mlsanity.com/paper/2205.15896/) (2022)

## Abstract (arXiv)

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.