DGG-LDP: Directed Graph Generation Algorithm with Local Differential Privacy

In various real-world scenarios, directed graphs can express the nature of relationships more clearly than undirected ones. Meanwhile, decentralized networks have attracted increasing attention in recent years. In decentralized directed networks (e.g., the Bitcoin Network), each user maintains only their own local view of the network. To provide better services, third-party providers often need to construct a global graph based on the local views uploaded by users for downstream graph-analysis tasks. However, directly collecting users’ local views poses significant privacy risks. For directed graphs, symmetry plays an important role in restoring data balance and preserving structural integrity. In this paper, we propose DGG-LDP, a directed graph generation algorithm based on local edge differential privacy, tailored for decentralized directed graphs. The core idea of the algorithm is to balance coarse-grained and fine-grained structural information so as to preserve geometric symmetry: we first synthesize an initial graph by collecting one round of community degree vectors, and then—guided by symmetry principles—we iteratively refine the graph using a second round of noisy community degree vectors, removing redundant asymmetric edges in the community vectors to better approximate the original graph. Additionally, the algorithm incorporates graph structure learning and graph embedding techniques to mitigate the impact of noise. Experiments on four real-world datasets demonstrate the effectiveness of the proposed method.