PrivAGM: Secure Construction of Differentially Private Directed Attributed Graph Models on Decentralized Social Graphs

Decentralized social graphs, where no single entity possesses the information of the entire graph, and each user maintains only a limited view of the graph, contain great value for different applications. However, simply collecting local views for analytics raises privacy concerns due to the sensitive information of social relationships they capture. To address this, a canonical approach involves privately fitting a generative graph model to the decentralized social graph, generating a differentially private synthetic graph that serves as a proxy for analytics. Existing solutions, however, often fail to capture the inherent directionality of edges and attribute-edge correlations when dealing with decentralized directed social graphs, leading to synthetic graphs with poor utility. To bridge this gap, we present PrivAGM, a new solution that harnesses the synergies among differential privacy, secure multiparty computation, and generative graph models, enabling the secure construction of differentially private directed attributed graph models on decentralized social graphs while ensuring the privacy preservation of individuals. We evaluate PrivAGM on three real-world directed social graph datasets. The results show that PrivAGM outperforms the state-of-the-art methods, generating synthetic graphs with significantly higher utility.