Locally Differentially Private Synthesis of Decentralised Heterogeneous Social Graphs via Spectral Embeddings and Bayesian Optimisation

Abstract

: Synthesising heterogeneous social graphs in decentralised settings is challenging because clients observe only egocentric views and strict privacy rules prevent central access to raw links or content. We present a locally private spectral graph synthesis framework for federated social platforms and peer-to-peer applications. Clients compute Laplacian spectral embeddings and degree summaries of their ego graphs and perturb them locally using the High-Dimensional Spherical mechanism for continuous embeddings and the two-sided Geometric mechanism for integer-valued degrees. An honest but curious server receives only the perturbed summaries and reconstructs a synthetic graph through Bayesian optimisation of reconstruction parameters. All server-side processing operates solely on noisy data and therefore incurs no additional privacy cost. Content is modelled explicitly as nodes, preserving homophily and heterophily. We evaluate structural fidelity through degree heterogeneity, clustering, assortativity, and modularity, and assess downstream utility through link prediction and community detection. Experiments are repeated under multiple random seeds and results are aggregated for robustness. Across communication, citation, and social networks, the proposed method achieves competitive structural fidelity and downstream utility under user-level LDP, with particularly strong performance on assortativity and modularity at moderate to large privacy budgets. Computational trade-offs, scalability considerations, and potential threats are also discussed.