Reproduce “Privacy-Preserving Graph Embedding based on Local Differential Privacy” on OpenResearch

About this paper

Zening Li, Rong-Hua Li, Meihao Liao, Fusheng Jin, Guoren Wang

Researchers from Beijing Institute of Technology developed PrivGE, a privacy-preserving graph embedding framework that uses a novel High-Dimensional Square wave (HDS) mechanism and decoupled Personalized PageRank propagation under local differential privacy. This framework demonstrated superior utility compared to existing LDP methods for node classification and link prediction on various datasets, occasionally exceeding non-private performance.

Key insights

• The High-Dimensional Square wave (HDS) mechanism significantly reduces theoretical error bounds for local differential privacy on high-dimensional data, improving utility retention from O(d log(d/delta) / epsilon) to O(log(d/delta)).
• Decoupling feature transformation from graph propagation, specifically using Personalized PageRank, effectively addresses GNN limitations like over-smoothing and neighborhood explosion while integrating multi-hop information.
• Carefully designed noise, as introduced by the HDS mechanism, can sometimes act as a regularizer, enabling privacy-preserving methods to achieve generalization capabilities comparable to or even better than non-private baselines.

Summary by alphaXiv.