The collection of graph data in decentralized environments raises critical privacy concerns. Local differential privacy (LDP) provides a strong privacy model but applying uniform noise to all graph elements often destroys utility. To address this, we propose the Criticality-Aware Adaptive Local Differential Privacy (CA-LDP) framework. CA-LDP quantifies the structural importance of nodes and edges, then dynamically allocates privacy budgets: stronger protection for critical structures, and weaker protection for non-critical ones. Users report a low-dimensional criticality-weighted vector and, for a subset of critical edges, a precise randomized response. The server reconstructs a synthetic graph using an enhanced graph structure learning model that integrates these criticality signals. A theoretical analysis proves CA-LDP satisfies ε-LDP. Experiments on real-world datasets show that CA-LDP outperforms state-of-the-art baselines in preserving critical edges and node classification accuracy, while effectively reducing the success rate of link inference attacks on critical structures.
Liang et al. (Tue,) studied this question.