IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING
1
Towards Personalized Differentially Private Learning for Decentralized Local Graphs
arXiv:2607.04777v1 [cs.LG] 6 Jul 2026
Longzhu He, Peng Tang, Chaozhuo Li, Jinhu Fu, Litian Zhang, Li Sun, Philip S. Yu, and Sen Su
(b) Ours
Private Graph Learning with GNNs
Low Utility
Uniform noise intensity noise
User 1
noise
noise
User 2 … User n sensitive node feature
Server
(a) Prior works
Server
Abstract—Graph-structured data is increasingly generated and stored in decentralized environments, such as social platforms, mobile applications, and edge networks, where users maintain control over their local graph data. However, collecting and analyzing such decentralized graph data for downstream learning tasks raises significant privacy concerns, as nodes and their attributes often contain sensitive personal information. Local Differential Privacy (LDP) has emerged as a promising solution for privacy-preserving data collection without relying on trusted servers. Nevertheless, existing LDP-based graph learning methods typically assume uniform privacy requirements across users, ignoring the heterogeneous and personalized privacy preferences commonly observed in real-world systems. This uniform treatment leads to inflexible noise injection at the data collection stage, resulting in substantial distortion of graph data and degraded utility in subsequent analysis. To address this limitation, we propose PPGNN, a personalized differentially private framework for decentralized graph data. PPGNN enables user-specific privacy budgets during local perturbation while preserving analytical utility. To handle heterogeneous privacy levels and noise distortion, we design a two-stage solution consisting of a Personalized Perturbation Mechanism (PPM) and a weighted calibration strategy, FlexProp. Extensive experiments on six real-world graph datasets demonstrate that PPGNN effectively balances personalized privacy protection and data utility in decentralized graph learning scenarios.
Private Graph Learning with GNNs
High Utility
Adaptive noise intensity noise
User 1
noise
noise
User 2 … User n
privacy requirement
Fig. 1. Comparison of (a) prior works and (b) ours in the locally private graph learning scenario. The scenario involves a server (e.g., a social network server) and multiple decentralized users, each with sensitive node features and distinct privacy requirements. The server collects perturbed data and performs private graph learning using a GNN. (a) Previous works overlook personalized privacy requirements of users and apply uniform noise intensity to protect node features, leading to low utility in private graph learning. (b) In contrast, our approach adapts the noise intensity according to user-specific privacy requirements, thereby promoting high utility in private graph learning.
Index Terms—local differential privacy, graph-structured data, graph learning, personalized privacy requirements
I. I NTRODUCTION RAPH-structured data has become a fundamental data type in modern information systems, widely used to model complex relationships in social networks, mobile applications, and online platforms. In many real-world scenarios, such graph data is decentralized and maintained locally by users, containing sensitive information embedded in node attributes and structural connections. Collecting and aggregating
G
This work was supported by the National Key Research and Development Program of China (No. 2024YFF0907401), the National Natural Science Foundation of China (No. 62072052), and the BUPT Excellent Ph.D. Students Foundation (No. CX20260030), and the Shandong Provincial Natural Science Foundation (No. ZR2025MS1038). (Corresponding author: Sen Su.) Longzhu He, Jinhu Fu, Li Sun, and Sen Su are with the School of Computer Science, Beijing University of Posts and Telecommunications, Beijing 100876, China, and also with the State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing 100876, China. (e-mail: [email protected]; [email protected]; [email protected], [email protected]). Peng Tang is with the School of Cyber Science and Technology, Shandong University, Qingdao, China (e-mail: [email protected]). Chaozhuo Li and Litian Zhang are with the School of Cyberspace Security, Beijing University of Posts and Telecommunications, Beijing 100876, China (e-mail: [email protected]; [email protected]). Philip S. Yu is with the Department of Computer Science, University of Illinois at Chicago, Chicago, IL 60607 USA (e-mail: [email protected]).
these local graph data for downstream analytical tasks may therefore raise significant privacy concerns [1]. Graph Neural Networks (GNNs) [2], [3] have emerged as a powerful tool for learning from graph data, demonstrating remarkable performance in various downstream tasks such as node classification [4], link prediction [5], and graph classification [6]. However, applying GNNs in decentralized environments requires collecting user data to a central server, which further amplifies privacy risks. This is particularly evident in social mobile applications like Instagram and WhatsApp [7], where servers aim to gather various types of information (e.g., user profiles and interactions) for recommendation purposes. Recent studies have also shown that GNNs are vulnerable to various privacy attacks [1], [8]–[12], leading to potential leakage of sensitive information. Therefore, there is an urgent need for innovative privacy-preserving graph learning models. To mitigate privacy threats, local differential privacy (LDP) [13] has emerged as a pivotal and well-recognized method for safeguarding sensitive data in distributed systems. LDP [13] offers robust privacy guarantees for secure data collection and analysis, and has been widely adopted by major companies such as Google [14], Apple [15], and Microsoft [16]. In the LDP setting, there is a server and multiple user clients, where it is assumed that the server is untrustworthy. Each
IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING
user ensures privacy by locally perturbing their data (typically through noise injection [17], the magnitude of which depends on the privacy budget) before sending it to the server. Given its strong data privacy guarantees, LDP has become a key approach to protecting decentralized local graph node features, which are often sensitive. Recent research has delved into graph learning under LDP for enhanced privacy preservation, including advanced LDP mechanisms, such as the multi-bit mechanism [18]–[20], as well as classical LDP mechanisms like the Laplace mechanism [13], Gaussian mechanism [21], and 1-bit mechanism [16]. Fig. 1 illustrates the local private graph learning scenario, where each user has a sensitive node feature. The server collects the perturbed data and performs private graph learning on the noisy data. However, as shown in Fig. 1(a), prior studies [18]–[20], [22]–[26] largely overlook the fact that users may have different overall levels of privacy requirement. In real-world scenarios, privacy expectations can vary significantly across users due to factors such as gender, geography, and age. For instance, research [27] shows that females tend to express higher privacy concerns than males, revealing a “privacy gender gap” in the context of online tracking [28]. Similarly, individuals in the UK are reported to be less likely to disclose negative emotions than those in Germany or France, suggesting a “privacy geography gap.” These findings indicate that certain user groups may prefer stronger privacy protection across all of their personal data. Despite this, existing locally differentially private graph learning methods assume a uniform privacy level for all users. As shown in Fig. 1(a), this leads to the application of a global maximum noise intensity determined by the most privacy-sensitive user to all node features. Such a one-size-fitsall strategy significantly degrades model utility, as excessive noise added to satisfy a small subset of users unnecessarily undermines the effectiveness of the overall learning process. To address the above issue, as illustrated in Fig. 1(b), we propose a novel privacy-preserving graph learning framework grounded in the notion of personalized LDP (PLDP) [29]. This framework adaptively adjusts noise intensity to meet users’ privacy requirements while enhancing the utility of private graph learning. PLDP, an extension of the traditional LDP, is designed to offer varying levels of privacy protection tailored to individual users or data points. Introducing a personalized definition to LDP enables dynamic adjustment of privacy parameters based on factors such as importance, sensitivity, or specific user requirements. However, under this personalized privacy setting, two key challenges arise. On the one hand, dual protection of privacy elements becomes essential: not only must node features be safeguarded, but the privacy level [30] of each user also requires protection. A user’s privacy level reflects their valuation of privacy, which can inadvertently reveal sensitive personal attributes that necessitate additional safeguarding. Protecting a user’s privacy level necessitates designing a specialized LDP protection algorithm and addressing the interplay between node feature protection and privacy levels. Improper handling of this interaction risks disclosing the user’s privacy preferences, making the synergistic protection of both aspects a critical consideration. In this dual privacy setting, rationally
2
allocating the privacy budget between the two elements to maximize the utility of privacy-preserving graph learning is vital. On the other hand, noise calibration in multilevel privacy scenarios poses additional challenges. Directly training GNNs with perturbed features can severely reduce the utility of privacy graph learning due to excessive noise. While previous works attempt denoising via multi-hop aggregation [31]–[33], this approach proves suboptimal in a multilevel privacy setting because perturbation levels differ for each node. Simple multilayer aggregation fails to exploit the effective information from each node fully. Consequently, achieving accurate noise calibration under a personalized privacy framework introduces greater complexity than non-personalized approaches. In this paper, we propose a novel locally differentially private graph learning framework, PPGNN (Personalized Privacy-preserving Graph Neural Network), which integrates two core components: the Personalized Perturbation Mechanism (PPM) and the FlexProp algorithm. Specifically, PPM is designed to achieve dual privacy protection for node features and privacy levels. It comprises two fundamental elements: the Multi-dimensional Local Randomizer (MLR) and the Extended Square Wave (ESW) mechanism. The MLR protects multi-dimensional node features and ensures their utility through dimensionality reduction and rigorous theoretical considerations. Meanwhile, the ESW mechanism enhances privacy protection by extending the capabilities of the traditional square wave mechanism [34] to cover users’ privacy levels across discrete domains, ensuring that the protection is effective and adaptable to varying user requirements. To tackle the challenges of calibrating the perturbed node features, we introduce a weighted aggregation algorithm called FlexProp. FlexProp is essential for integrating individual users’ privacy levels and aggregating information from neighboring nodes within K hops. By applying varying weights based on privacy levels, FlexProp facilitates nuanced denoising, thus improving data quality while maintaining robust privacy measures. This aggregation process supports privacy-preserving graph learning, ensuring the GNN performs effectively despite the added noise. Notably, our PPGNN framework is designed to be compatible with various GNN architectures, providing both flexibility and adaptability for different application scenarios. Our contributions are summarized as follows: Problem. We propose a novel and realistic problem in differentially private GNNs, aiming to achieve personalized privacy preservation for users’ local data. • Methodology. We introduce PPGNN, a novel locally differentially private GNN model designed to meet users’ personalized privacy requirements while ensuring the utility of privacy-preserving graph learning. • Experiments. We conduct extensive experiments on six real-world datasets and three GNN architectures (GCN, GraphSAGE, GAT), demonstrating that PPGNN consistently outperforms strong baselines and achieves utility close to the non-private upper bound in multiple settings. •
Organization. The rest of this paper is organized as follows. Section II introduces background knowledge and formulates the problem. Section III describes our personalized privacy-
IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING
TABLE I N OTATIONS Symbol |V| A X τ d m ϵ M xv x′v N (v) hv bv h γ wij g g′ f b
Description the number of users the adjacency matrix the node feature matrix the privay level of users the number of feature dimensions the number of sampled dimensions the privacy budget the perturbation mechanism the original feature vector of user v the perturbed feature vector of user v the set of neighbors of v (including v itself) the original embedding of node v the estimated embedding of node v the privacy budget allocation ratio between PPM and FlexProp modules the aggregation weight from node j to node i in weighted message passing the user’s true privacy level index (input to ESW) the randomized output of ESW the size of the input domain in ESW the smoothing window radius in ESW
preserving graph learning framework, PPGNN. Section IV presents extensive experimental results. Section V reviews the related literature, and Section VI concludes the paper. II. P RELIMINARIES In this section, we first provide a formal definition of the problem (§II-A). Next, we present essential background knowledge related to graph neural networks (§II-B) and local differential privacy (§II-C), followed by an introduction to the four primary node feature LDP mechanisms (§II-D). We summarize the important notations of our paper in Table I. A. Problem Definition We provide a formal definition for the problem of learning a GNN with node data privacy. Consider a graph G = (V, A, X), where V = {v1 , v2 , . . . , v|V| } is the node/user1 set, and |V| represents the total number of users within the network. Each user vi holds locally a privacy feature vector xi ∈ Rd , where d denotes the dimension of the node feature vector. In graph G, the adjacency matrix A ∈ R|V|×|V| encodes the connections between nodes, while the node feature matrix X is defined as {x1 , x2 , . . . , x|V| }. Consistent with prior works [18]–[20], [22], we focus on the node classification task, which serves as a fundamental building block for various applications in social networks and beyond. Specifically, given a labeled node set Vl ⊂ V, containing nodes with known class labels drawn from the set Y = {y1 , y2 , . . . , yc }, along with an unlabeled node set Vu ⊂ V/Vl , the objective of node classification is to accurately assign each node v to one of the predefined classes within Y. This task serves as the foundation for numerous realworld applications, including social influence analysis, content recommendation, and predictive behavior modeling. We assume that the server is an untrusted party, which has access to the node set V and the adjacency matrix A, 1 This paper uses ‘node’ and ‘user’ interchangeably, as in many applications,
such as social networks, each node corresponds to a user.
3
but cannot directly observe the sensitive node feature matrix X. The feature data is decentralized and privately held by individual users. Protecting this information is essential for maintaining user confidentiality and mitigating the risk of data leakage.2 Each user is associated with a personalized privacy level τ ∈ {1, 2, . . . , h}, where a smaller value of τ indicates a stronger privacy preference, and thus requires injecting more noise. Users independently perturb their feature vectors based on their assigned τ using a LDP mechanism, enabling personalized privacy preservation. Importantly, although we focus on feature-level privacy, the graph structure, captured by the adjacency matrix A, remains intact and is fully utilized during training. The server collects the perturbed features and performs graph learning using GNNs, which leverage the underlying topology for message passing and representation learning. Therefore, the graph component remains integral to the framework, and the interplay between noisy features and structural information is central to the model’s design. B. Graph Nerual Networks GNNs [2], [3], [37], [38] learn new node representations by combining initial node features and graph topology by aggregating node and neighbor information. These representations are then used for downstream machine learning tasks like node classification. A typical K-layer GNN consists of K graph convolution layers, where each layer aggregates information from a node’s neighbors and updates the node’s representation. After K aggregation iterations, the representation of a node captures the structural information in its K-hop neighborhood. The k-th layer of the GNN can be defined formally as follows: hkN (v) = AGGk {hk−1 (1) u , ∀u ∈ N (v)} , hkv = U PDk hkN (v) , Θk , (2) where N (v) is the set of neighbors of node v as well as could include v itself, and hk−1 is the embedding of an u adjacent node u in the k − 1 layer. AGGk (·) denotes the aggregator function, such as S UM, M EAN, or M AX. U PDk (·) denotes a learnable update function, such as a neural network, parameterized by Θk . The above structured approach allows GNNs to effectively leverage both node features and relational information inherently present in the graph, thereby enhancing their performance on various tasks. C. Local Differential Privacy LDP, as a variant of DP, has been adopted as a powerful privacy-preserving method by companies such as Google [14], Apple [15] and Microsoft [16], and hundreds of millions of users’ private information is being protected by this technology. In the LDP setting, the user perturbs the original data using a randomizer R on the user side and uploads the perturbed data to the server side. This ensures the privacy of user data, as only the data owner can access the original data [39]. The randomizer R is defined as follows: 2 While this paper focuses on the privacy of node features, our framework is modular and can be seamlessly extended to incorporate edge privacy mechanisms such as those in [35], [36].
IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING
4
Definition 1 (ϵ-LDP [40], [41]). A randomizer R satisfies ϵ-LDP, where ϵ > 0, if and only if for any user’s private data x and x′ , and for all possible outputs y ∈ Range(R): Pr[R(x) = y] ≤ eϵ · Pr[R(x′ ) = y].
(3)
The parameter ϵ, known as the privacy budget, plays a crucial role in LDP by regulating the balance between utility and privacy. A smaller (resp. larger) ϵ value provides stronger (resp. weaker) privacy guarantees but may result in lower (resp. higher) utility. The above definition implies that no matter what side knowledge the adversary has, they cannot, with high probability, infer the input value by observing the output. In addition, LDP satisfies several important properties [40] that are essential for subsequent proofs, as follows: Proposition 1 (Sequential Composition [40]). Consider a sequence of computations A1 , . . . , Ak applied to different components of the same local data record. If each Ai satisfies ϵi -LDP, then performing these computations sequentially P ensures an overall privacy guarantee of ( i ϵi )-LDP for that record. Proposition 2 (Post-processing [40]). If an algorithm A(·) satisfies ϵ-LDP, then any further processing of its output by another algorithm B(·) (i.e., B(A(·))) also maintains ϵ-LDP. In real-world scenarios, users often exhibit varying levels of privacy sensitivity and expectations, resulting in diverse privacy requirements. The standard LDP framework assumes a uniform privacy budget for all users, which limits its applicability in personalized settings. To address this limitation, the notion of personalized LDP (PLDP) has been proposed [29], [30], [42], [43]. Under the PLDP setting, the server provides a set of discrete privacy levels, and each user can independently select a level τ ∈ {1, . . . , h} based on their individual privacy preferences. This selected level corresponds to a user-specific privacy budget ϵτ , allowing for flexible control over the noise injection process while respecting user autonomy. Importantly, despite this personalization, PLDP retains the formal privacy guarantees and desirable properties of standard LDP [40]. D. Four Primary Node Feature LDP Mechanisms 1) Laplace mechanism: The Laplace mechanism [13] is a classical LDP mechanism known for its simplicity. Assume each user possesses a one-dimensional value, denoted as x. Without loss of generality, we assume x is within the normalized value range of [−1, 1]. The subsequent three LDP mechanisms also adhere to this setting. Next, we define a randomization function that produces a perturbed value, denoted as x′ = x + Lap(2/ϵ), where Lap(α) represents a random variable following a Laplace distribution with prob1 ability density function f (x) = 2α exp(− |x| α ). To extend to d-dimensional spaces, a straightforward approach is to apply the Laplacian mechanism independently to each dimension. Each dimension is allocated a privacy budget of ϵ/d. According to the sequential composition property [44] of the LDP mechanism, it adheres to ϵ-LDP. 2) Gaussian mechanism: The Gaussian mechanism [21] is another well-established LDP mechanism recognized for its
effectiveness and flexibility. Consider a scenario where each user has a one-dimensional value x. We define a randomization function that produces a perturbed value denoted as x = x + N (0, σ 2 ), where N (0, σ 2 ) is a Gaussian random variable with zero mean and variance σ 2 . In this context, the variance σ 2 is calibrated based on the privacy budget ϵ and the acceptable privacy leakage probability δ. Specifically, we , ensuring that (ϵ, δ)-LDP is denote σ 2 as σ 2 = 2 ln (1.25/δ) ϵ2 satisfied, where δ > 0 serves as a relaxed privacy parameter. For multidimensional data, the Gaussian mechanism is applied independently to each dimension, mirroring the approach used in the Laplace mechanism. In this case, the privacy budget for each dimension is allocated as ϵ/d. This independent application preserves the (ϵ, δ)-LDP properties due to the sequential combination nature of local differential privacy, thus ensuring robust privacy protection across all dimensions. 3) 1-bit mechanism: In its one-dimensional form [16], for any original data x ∈ [−1, 1], the distribution followed by the perturbed value x′ ∈ {−1, 1} is as follows: ( eϵ −1 1 + x+1 if c = 1 ϵ ′ 2 · eϵ +1 , . (4) Pr[x = c|x] = e e+1 ϵ x+1 eϵ −1 if c = −1 eϵ +1 − 2 · eϵ +1 , The extension to higher-dimensional spaces is implemented similarly to the first two mechanisms and is omitted here. 4) Multi-bit Mechanism: The multi-bit mechanism [18], [22] extends the 1-bit mechanism [16] to higher-dimensional spaces through a sampling process. Specifically, it operates by uniformly sampling m-dimensions from d-dimensional node feature data without replacement. Each of the m selected dimensions is then perturbed using noise that satisfies ϵ/m-LDP. Due to the sequential composition property of LDP mechanisms [44], the overall process adheres to ϵ-LDP. After receiving all the perturbed data, the server transforms the red eϵ/m +1 porting data x̂ to its unbiased estimate x′ = m · eϵ/m −1 · x̂. The ϵ/m 2 d +1 ′ ′ variance of x is as follows: V ar[x ] = m · eeϵ/m −1 − x2 . III. M ETHODOLOGY In this section, we introduce PPGNN, a locally differentially private graph learning model designed to effectively meet users’ personalized privacy requirements while significantly enhancing the utility of private graph learning. Next, we first introduce the overall framework of PPGNN in §III-A, followed by a detailed discussion of the two key steps of PPGNN in §III-B and §III-C, respectively. Finally, we conduct complexity analysis in §III-D and privacy analysis in §III-E. A. Overview In the scenario of locally private graph learning, the node features located on the user side are transmitted to the server after undergoing noise injection. The server performs private graph learning based on the collected node features. The overall framework of PPGNN is illustrated in Fig. 2. PPGNN addresses users’ personalized privacy requirements effectively and enhances the utility of privacy graph learning through adaptive personalized aggregation. Specifically, in PPGNN, each user’s local data consists of node features and privacy levels, which are protected using a Personalized Perturbation
IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING
5
User-Side
Server-Side
privacy level �
PPM
node feature �
node feature �
privacy level �
perturbed �’
… …
perturbed feature �’ sampling value �
0
0
GNN
…
…
…
collected noisy graph
0
…
debiasing rectification
�
MLR privacy 1-� budget set ℰ 1 − � � perturbed ESW privacy level �’ Perturbation
FlexProp
perturbed node feature �’ Rectification
�� |� ��� =
class 1
node classification
…
… …
…
class 2
�∈�(�)
��� = 1
min ��� �� |�
1/�2�
�∈�(�)
1/�2�
Aggregation
Fig. 2. Overview of our proposed PPGNN. Users run the Personalized Perturbation Mechanism (PPM) to their private data (node features x and privacy levels τ ) and send the output to the server. The server calibrates the collected noisy data using the FlexProp algorithm and performs GNN training for the node classification task. The red dashed path illustrates the allocation scheme for privacy budgets.
Algorithm 1: Local Randomizer Input: Numeric data x ∈ [−1, 1], privacy ϵ.o n ϵbudget +1 eϵ +1 Output: Randomized response x′ ∈ − eeϵ −1 , eϵ −1 . 1: Sample a Bernoulli variable u such that eϵ −1 1 Pr[u = 1] = 2e ϵ +2 · x + 2 . 2: if u = 1 then 3: x′ = (eϵ + 1)/(eϵ − 1). 4: else 5: x′ = −(eϵ + 1)/(eϵ − 1). 6: end if 7: return x′
Mechanism (PPM) that dynamically adjusts perturbation levels based on individual privacy preferences. On the server side, the FlexProp algorithm is applied to correct the noisy node features, mitigating the biases introduced by the perturbation process. Once corrected, the server employs a GNN to train on the refined data, enabling downstream tasks such as node classification. PPGNN integrates personalized privacy protection with adaptive feature correction, achieving a balance between robust privacy guarantees and high utility, thus optimizing the performance of privacy-preserving graph learning. In summary, PPGNN consists of the following two parts: 1) Perturbing node features with PPM: Although several LDP mechanisms applicable to node features have been proposed (as outlined in Section II-D), these mechanisms fail to address the dual privacy requirements inherent in personalized privacy graph learning scenarios. Additionally, there remains significant potential to improve the utility of these mechanisms by reducing noise perturbation variance to enhance data accuracy. Balancing these challenges is non-trivial, as it requires
simultaneously minimizing noise and preserving dual privacy. To tackle this issue, we introduce a novel LDP perturbation algorithm, the Personalized Perturbation Mechanism (PPM), which incorporates two interdependent modules: a multidimensional local randomizer and an extended square-wave mechanism. These modules work synergistically to effectively reduce noise variance while addressing dual privacy concerns. In the PPGNN framework, each user perturbs their local data using PPM before transmitting the processed data to the server for further private graph learning. 2) Calibrating noise features with FlexProp: Directly utilizing the noisy data generated by the LDP mechanism for graph learning often leads to poor utility, necessitating further calibration to reduce noise. To address this, we employ multihop aggregation, which is theoretically effective in minimizing estimation errors. However, traditional multi-hop aggregation is suboptimal in personalized privacy-preserving scenarios, as it fails to leverage the effective information of each node fully. To overcome this limitation, we propose the FlexProp algorithm, which efficiently minimizes estimation errors through adaptive weighted aggregation, tailoring the process to individual nodes’ privacy requirements and data features. B. Perturbing Node Features with PPM To achieve personalized privacy preservation for node features, we introduce a novel LDP algorithm called the Personalized Perturbation Mechanism (PPM), as outlined in Alg. 3. The architectural design of PPM is illustrated in Fig. 2. In this framework, we strategically divide the privacy budget into h discrete levels, denoted as E = ∪hτ=1 {ϵτ }. Here, ∆ϵ = ϵτ +1 − ϵτ > 0 indicates that each subsequent level represents a progressively greater privacy budget, while ϵτ denotes the specific budget at privacy level τ . Notably, a smaller
IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING
6
Algorithm 2: Multi-dimensional Local Randomizer
Theorem 2. Algorithm 2 (MLR) satisfies ϵ-LDP for each node. In addition, for any i ∈ {1, 2, . . . , d}, E [x′i ] = xi .
Input: Feature vector x ∈ [−1, 1]d , privacy budget ϵ n od ϵ/m ϵ/m d +1 d +1 Output: x′ ∈ − m · eeϵ/m −1 , 0, m · eeϵ/m −1 1: Let x′ = ⟨0, 0, . . . , 0⟩. 2: Let m = max(1, min(d, ⌊ϵ/2.2⌋)). 3: Sample m values uniformly without replacement from {1, 2, . . . , d}. 4: for each sampled value j do 5: Feed xj and ϵ/m to the Alg. 1 to obtain tj . d · tj . 6: x′j = m 7: end for 8: return x′
value of τ corresponds to a reduced privacy budget, leading to the injection of a greater amount of noise. As depicted in Fig. 2, the PPM consists of two critical components: the Multi-dimensional Local Randomizer (MLR) and the Extended Square Wave (ESW) mechanism. The allocation of the privacy budget between these two components is governed by the parameter γ. Specifically, the ESW utilizes γϵτ of the privacy budget, while the MLR is allocated (1−γ)ϵτ . This careful distribution ensures that each component effectively contributes to the overall privacy protection mechanism, balancing the trade-off between noise injection and data utility. Next, we explore the details of MLR and ESW respectively. 1) Multi-dimensional Local Randomizer: To protect multidimensional node features, we introduce the MLR algorithm, as presented in Alg. 2. This algorithm extends the concept of the local randomizer (Alg.1) [45], originally designed for unidimensional spaces, to accommodate multidimensional contexts. The MLR algorithm3 effectively allocates the total privacy budget across m attributes, rather than the original d, which significantly reduces the noise variance associated with the perturbation process. As a trade-off, the additional estimation error introduced by sampling m attributes from d can be managed by judiciously selecting an appropriate m value. This balancing act is formally addressed in Theorem 1. Furthermore, Theorem 2 establishes that the MLR algorithm satisfies ϵ-LDP and proves that E [x′ ] = x. Theorem 1. To minimize the variance of the perturbation mechanism (as given by Equation (5)), the optimal sampling parameter m = max(1, min(d, ⌊ϵ/2.2⌋)). ϵ/m 2 d e +1 V ar [x′i ] = · − x2i . (5) m eϵ/m − 1 Proof. Given that variance is a critical factor that affects the accuracy of the estimation of the LDP mechanisms: the smaller the variance, the more accurate the estimation, the theorem selects the optimal value of m by minimizing the variance of the LDP mechanism. See Appendix A for more details. 3 The MLR algorithm is not limited to the local randomizer in [45]; it serves as a general wrapper that can integrate any one-dimensional fixedbudget perturbation mechanism. This modularity allows MLR to be adapted to diverse privacy mechanisms (e.g., Laplace).
Proof. We denote the MLR algorithm as R1 . According to Definition 1, our objective is to demonstrate that for any two input the following inequality: features x1 and x2 satisfying Pr R1 (x1 ) = x′ ≤ eϵ · Pr R1 (x2 ) = x′ , where x′ represents a perturbed output. Furthermore, ensuring that the data are unbiased (that is, E [x′i ] = xi ) guarantees the statistical utility of the data. We have also provided a proof of this property. For further details, please refer to the Appendix B. Note that the user’s privacy level τ is also sensitive and utilized in the subsequent FlexProp algorithm. Directly applying the MLR algorithm to protect node features may potentially reveal τ , as τ determines ϵτ , which in turn affects the final output. To address this issue, we propose the Extended Square Wave (ESW) mechanism. Additionally, considering that m could potentially leak the user’s privacy level, instead of ′ directly using τ , we use a randomized j ′version k τ through the ESW, that is: m′ = max(1, min(d, ϵτ /2.2 )). 2) Extended Square Wave mechanism: To protect the users’ privacy levels, the ESW extends from the square wave mechanism [34] and can be applied to the protection of discrete domain data after extension. In ESW, the input domain is defined as D = {1, 2, . . . , f }, where f is the total number of privacy levels, and the input value g ∈ D represents a user’s true privacy level index. The output domain is extended to D′ = {1, 2, . . . , f + 2b}, where g ′ ∈ D′ is the perturbed output value. The parameter b controls the width of the high-probability kwindow around g and is defined as: b = j ϵeϵ −eϵ +1 2eϵ (eϵ −1−ϵ) · f . This extension allows the mechanism to assign higher output probability near the true value to preserve utility, while still satisfying ϵ-LDP through randomization across a larger space. The perturbation process is as follows: ( p, if |g − g ′ | ≤ b , (6) Pr[ESW(g) = g ′ ] = q, otherwise where p = eϵ /((2b + 1)eϵ + f − 1), q = 1/((2b + 1)eϵ + f − 1). The values of p and q ensure ϵ-local differential privacy over the extended output domain D′ , while the use of the highprobability window improves the fidelity of perturbed outputs. C. Calibrating Noise Features with FlexProp In this section, we first conduct an error analysis to identify the key factors influencing the utility enhancement of perturbed node features. Building on these insights, we introduce FlexProp, a weighted aggregation algorithm specifically designed for personalized scenarios, which efficiently calibrates the perturbed node features to maximize utility while respecting individual privacy requirements. 1) Error analysis: The server proceeds with GNN training after receiving all the perturbed node features. During the first layer of GNN, the embedding for any given node v ∈ V is produced through the following process: b N (v) = AGG ({x′ , ∀u ∈ N (v)}) , h (7) u
b N (v) is the estimation of the AGG(·) function that where h aggregates the feature vectors x′u of all perturbed nodes u ∈
IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING
7
N (v). The aggregation process provides an unbiased estimate when E[x′u ] = xu (Theorem 2) and the AGG function operates linearly, as established in Theorem 3. Theorem 3. The linear aggregation function described by Eq. (7) guarantees unbiased estimation. Specifically, for any b N (v) ] = hN (v) . node v ∈ V, it holds that: E[h Proof. See Appendix C for the proof. The estimation error ∆ between the estimated node embedb N (v) and the true node embedding hN (v) for any node ding h v is defined as the maximum absolute difference across each dimension i in the embedding, expressed as: ∆=
max i∈{1,2,...,d}
b N (v) )i − (hN (v) )i |. |(h
Input: User’s feature vector x ∈ [−1, 1]d , privacy level τ ∈ {1, 2, . . . , h}, privacy budget set E = ∪hτ=1 {ϵτ }, allocation parameter γ Output: Perturbed node feature x′ and τ ′ 1: ϵτ ← E(τ ). /* total privacy budget */ 2: ϵ1 ← γϵτ . /* privacy budget of the privacy level */ 3: ϵ2 ← (1 − γ)ϵτ . /* privacy budget of the node feature vector */ 4: τ ′ ← ESW(τ, ϵ1 ) and x′ ← MLR(x, ϵ2 ). 5: return x′ and τ ′
(8)
b N (v) )i and (h b N (v) )i represent the i-th dimension of where (h the estimated and true node embeddings, respectively. This error quantifies the deviation introduced by the perturbation and subsequent aggregation process. The detailed analysis of ∆ is provided in Theorem 4. Theorem 4. Let AGG(·) be the M EAN aggregator and δ > 0, with at least 1−δ probability, ∆ for any √the estimation error d log(d/δ) 1 √ given node v is: ∆ = O + O γϵ . (1−γ)ϵ
Algorithm 3: Personalized Perturbation Mechanism
|N (v)|
Proof. See Appendix D for the proof. The above theorem indicates that, given a fixed ϵ, selecting an appropriate γ and expanding the size of N (v) are both beneficial in reducing the estimation error. The trade-offs of γ are discussed in Section IV-F3. 2) FlexProp algorithm: To further minimize the error, we introduce a denoising aggregation algorithm called FlexProp, which calibrates noise by aggregating larger neighborhoods. Previous works [18], [31]–[33] have shown that considering higher-order neighborhoods aids in learning superior node representations. As illustrated in Alg. 4, for a node v, FlexProp aggregates features of nodes up to the farthest K steps away from v by invoking the AGG function K consecutive times, without any non-linear transformation in between, which facilitates noise calibration. Additionally, FlexProp examines the influence of aggregation policy π on enhancing aggregation accuracy. In a personalized privacy-preserving context, varying aggregation policies can substantially impact accuracy due to differing noise scales among neighboring nodes. We define the estimated feature of node i post-aggregation under policy π as: b i (π) = AGG {x′ , ∀j ∈ N (i)} . Assuming wij represents h j the weight of node j when aggregated to target node i, and considering a weighted aggregation function, we have: P ′ bi (π) = P 1 h (9) j∈N (i) wij xj . w ij j∈N (i) Furthermore, assuming the feature vector x′i of each node i decomposes into the true signal si and noise ni , i.e., x′i = si +ni , where ni is a random variable with a mean P of 0 and a variance bi (π) = P 1 of σi2 , we have: h j∈N (i) wij (sj + nj ). j∈N (i) wij Next, we analyze the variance of the noise after aggregation,
bi |π), to better assess the denoising effecdenoted as V ar(h tiveness and determine the optimal aggregation policy. The variance is calculated as follows: P 1 2 2 bi |π = V ar h σj . (10) 2 j∈N (v) wij P w ij j∈N (v) To achieve optimal noise removal, the variance of the aggregated noise should be minimized. WeP aim to select a set of weights wij that satisfy the constraint j∈N (i) wij = 1 while minimizing this variance. To find the optimal solution, we employ the Lagrange multiplier method [46]. The Lagrange function is defined as: X X 2 2 L(wij , ρ) = wij σj + ρ wij − 1 . (11) j∈N (i)
j∈N (i)
The optimal weights are obtained by solving the above 1/σj2 . For more details, please equation as wij = P 2 j∈N (i) (1/σj ) refer to the Appendix E. In practice, the optimal weights under the given policy π are not always feasible. To address this, we approximate the optimal weights using the neighbor aggregation function Π and incorporate it into Alg. 4.4 The function Π can be represented in matrix form as follows, ( 0, if Ai,j = 0 Πi,j = , (12) αi,j , if Ai,j = 1 P where A is the adjacency matrix and αi,j = τj′ / j∈N (i) τj′ . D. Complexity Analysis The time complexity of PPGNN is determined by its two key components: the PPM and the FlexProp aggregation algorithm. PPM perturbs the privacy level and feature vector of each node locally, requiring O(|V|·d), where |V| is the number of nodes and d is the feature dimension. FlexProp performs K layer message aggregation, involving O(K · E · d), where E is the number of edges and K is the number of layers. Combining these, the overall time complexity is O(|V|·d+K·E·d), scaling 4 Unlike the KProp Layer in [18], which performs multi-hop aggregation under a global privacy budget, our FlexProp is tailored for personalized LDP scenarios, where users have heterogeneous noise levels. FlexProp introduces a privacy-aware weight matrix Π to calibrate the aggregation process while preserving privacy, which is not considered in KProp.
IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING
Algorithm 4: FlexProp Input: Graph G = (V, A), privacy level τv , ∀v ∈ V, input features xv , aggregation function AGG, propagation step K ≥ 0 Output: Final embedding vector hv , ∀v ∈ V 1: Compute propagation weights Π using Eq. (12) 2: for each node v ∈ V do 3: Initialize hidden representation: h0v = xv 4: end for 5: for k = 1 to K do 6: for each node v ∈ V do 7: hkv = AGG Πv,u · hk−1 | u ∈ N (v) u 8: end for 9: end for 10: return hK v , ∀v ∈ V
linearly with graph size and feature dimensionality. This linear scalability ensures computational efficiency in practice and makes PPGNN suitable for real-world applications involving large, high-dimensional graphs. E. Privacy Analysis Recalling the definition of LDP (Definition 1), the PPGNN satisfies ϵτ -LDP as established by Theorem 5, which relies on the composition property (Proposition 1) and robustness to post-processing (Proposition 2) in differential privacy [40]. Furthermore, any subsequent predictions made by the PPGNN are governed by the post-processing theorem, since the LDP mechanism is applied only once to the private data. Theorem 5. PPGNN satisfies ϵτ -LDP for each node. Proof. See Appendix F for the proof. IV. E XPERIMENTS A. Experimental Settings 1) Datasets: Our experiments use six publicly real-world datasets: Cora [47], CiteSeer [47], Pubmed [47], LastFM [48], Facebook [49], and Wikipedia [49]. The statistical details of these datasets are presented in Table II. Cora [47]: A citation network in which each node corresponds to a scientific paper and edges signify citation links between papers. Node features are derived from paper content, and each node is labeled with a research topic. • CiteSeer [47]: Also a citation network where nodes represent academic papers and edges denote citation relationships. Each node has a content-based feature vector and belongs to a research category. • Pubmed [47]: A large-scale citation network in which nodes are biomedical papers and edges represent citations. Node features are TF/IDF weighted term vectors, and the task is multi-class classification among diabetesrelated topics.
•
8
TABLE II S TATISTICS OF GRAPH DATASETS
DATASET C ORA C ITESEER P UBMED L AST FM FACEBOOK W IKIPEDIA
#C LASSES
#N ODES
#E DGES
#F EATURES
7 6 3 18 4 2
2,708 3,327 19,717 7,624 22,470 11,631
5,278 4,552 44,324 27,806 170,912 170,845
1,433 3,703 500 7,842 4,714 13,183
LastFM [48]: A social network where nodes correspond to LastFM music platform users and edges reflect friendship connections. The task is to predict each user’s home country based on the artists they have liked. • Facebook [49]: A social network in which each node is an official Facebook page and edges represent mutual “likes” between pages. Node features are derived from page descriptions, and the task is page-type classification. • Wikipedia [49]: A co-occurrence network constructed from Wikipedia pages, where nodes represent articles and edges connect pages that share common links. The task is binary classification of page category. 2) Baselines: To demonstrate the effectiveness of PPGNN, we compare it with the following baselines: NonPriv, BASE, and LPGNN [18].5 The NonPriv employs clean node features for graph learning. In contrast, BASE uses features perturbed by the LDP mechanism directly in graph learning, bypassing a separate noise calibration step. LPGNN, recognized as the current state-of-the-art in locally private graph learning, perturbs node features using a multi-bit mechanism and calibrates noise using the KProp algorithm. Additionally, to evaluate the performance of PPM, we compare it with the 1-bit mechanism (1B) [16], Laplace mechanism (LP) [39], Gaussian mechanism (GM) [21], and multi-bit mechanism (MB) [18]. 3) Experiment setup: For each dataset, we randomly divide 50% of the data samples as the training set, 25% as the validation set and 25% as the test set. We select three GNN architectures as backbone models: GCN [4], which aggregates neighborhood information via a symmetric normalized adjacency matrix; GraphSAGE [2], which samples a fixedsize neighborhood and aggregates features using learnable aggregator functions; and GAT [50], which introduces an attention mechanism to assign learned importance weights to different neighbors during aggregation. All GNN models have two graph convolutional layers, each with a hidden dimension of size 16 and a SeLU activation function followed by dropout. We implement the GNN models in PyTorch using PyTorch-Geometric (PyG)6 . All experiments are carried out on a machine running Ubuntu 20.04 LTS, equipped with two Intel® Xeon® Gold 6348 CPUs, 100GB RAM, and an NVIDIA® A800 80GB GPU. We set E = {ϵ, 2ϵ, . . . , 2h ϵ}, where ϵ ∈ {0.01, 1, 2, 3}. If not specified otherwise, h is set •
5 Considering that the node feature protection method in [19] aligns with LPGNN [18], and the research context of [22] focuses on subgraph-level protection, a direct comparison is not necessary. Therefore, these works are not included as baselines in this study. 6 https://www.pyg.org
IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING
9