The Devil Within, The Cure Without: Securing Locally Private Graph Learning under Poisoning

Graph neural networks (GNNs) have become the cornerstone of graph representation learning in real-world applications, especially in social networks such as Facebook and Twitter, where user interactions naturally form graph-structured data. To safeguard sensitive information, including user attributes and personal connections, locally private graph learning protocols employ local differential privacy (LDP) to provide rigorous user-level guarantees. Despite these protections, we show that such protocols remain highly vulnerable to data poisoning attacks. Our approach targets the full-privacy setting, where both node features and edges are LDP-protected, and executes coordinated manipulations that significantly degrade utility, such as node classification accuracy, across multiple social network benchmarks. To counter these threats, we propose CureNet, a defense framework with four key components: (1) local data perturbation for privacy, (2) trimmed screening to filter abnormal submissions, (3) privacy-aware fake node pruning to remove sophisticated adversaries, and (4) a utility enhancement module to recover graph learning performance under privacy constraints. Extensive experiments on four real-world social network datasets—LastFM, Twitch, Github, and Facebook—demonstrate both the severe impact of our attack and the effectiveness of our defense. This study underscores the critical need to secure privacy-preserving graph learning against sophisticated poisoning threats.