Densest Subgraph Discovery on Decentralized Graphs with Local Edge Differential Privacy

Various real-world graphs, such as social and transaction networks, are typically distributed across users, each of whom holds a local view of the graph (i.e., their own relationships with others). Densest Subgraph Discovery (DSD) on such decentralized graphs is a fundamental task that can uncover valuable insights for downstream applications, including fraud detection, community identification, and user behavior mining. Additionally, in many scenarios, due to privacy concerns, sensitive original local views cannot be collected for DSD. Although there have been extensive studies on DSD, most existing algorithms either do not take user privacy into account or are specific to the centralized privacy setting that requires a (trusted) curator to collect all local views from users and then analyze the entire graph privately. To address these issues, we consider DSD under Local Edge Differential Privacy (LEDP), which allows users to perturb their local graph views via a randomizer such that any single edge is indistinguishable from the data transmitted to the server. We propose a new LEDP algorithm for DSD that utilizes the Randomized Response (RR) mechanism for user-side perturbation and extends greedy peeling with degree correction to find the densest subgraph on the server-side noisy global graph. Our proposed algorithm provides provable privacy and approximation guarantees. Finally, we perform experimental evaluations on real-world graphs to show that our proposed algorithm achieves better privacy-utility trade-offs than state-of-the-art LEDP baselines for DSD.