Leveraging Homophily Under Local Differential Privacy for Effective Graph Neural Networks

Abstract

Graph Neural Networks (GNNs) have become indispensable tools for analyzing graph-structured data, with applications across numerous domains. However, collecting graph data that is locally stored by users in privacy-sensitive scenarios remains challenging. Existing methods applying Local Differential Privacy (LDP) fail to account for homophily—the tendency of connected nodes to share similar attributes, which consequently leads to suboptimal performance under limited privacy budgets. To address this challenge, we propose HPGR (Homophily Preserving Graph Reconstruction), a novel approach for collecting and modeling graph topology under LDP, while preserving homophily. Our method employs a homophily-aware querying and modeling mechanism that integrates homophily priors into the data collection process, and enables robust reconstruction of the underlying graph structure despite the injected noise. We provide theoretical analyses demonstrating that our method satisfies LDP requirements while effectively preserving homophily. Extensive experiments on benchmark datasets show that our approach significantly outperforms existing methods, achieving a superior balance between privacy protection and model utility.