Going Deeper into Locally Differentially Private Graph Neural Networks
Authors: Longzhu He
Chaozhuo Li
Peng Tang
Sen Su
Venue: ICML 2025 oral (2025)
Keywords: Differential Privacy
Graph Neural Networks
Privacy-preserving
Primary area: social_aspects->privacy

Abstract: Graph Neural Networks (GNNs) have demonstrated superior performance in a variety of graph mining and learning tasks. However, when node representations involve sensitive personal information or variables related to individuals, learning from graph data can raise significant privacy concerns. Although recent studies have explored local differential privacy (LDP) to address these concerns, they often introduce significant distortions to graph data, severely degrading private learning utility (e.g., node classification accuracy). In this paper, we present UPGNET, an LDP-based privacy-preserving graph learning framework that enhances utility while protecting user data privacy. Specifically, we propose a three-stage pipeline that generalizes the LDP protocols for node features, targeting privacy-sensitive scenarios. Our analysis identifies two key factors that affect the utility of privacy-preserving graph learning: *feature dimension* and *neighborhood size*. Based on the above analysis, UPGNET enhances utility by introducing two core layers: High-Order Aggregator (HOA) layer and the Node Feature Regularization (NFR) layer. Extensive experiments on real-world datasets indicate that UPGNET significantly outperforms existing methods in terms of both privacy protection and learning utility.

Going Deeper into Locally Differentially Private Graph Neural Networks
Longzhu He Chaozhuo Li'
Peng Tang? ?
Sen Su
Abstract
Client-Side
Server-Side
Graph Neural Networks (GNNs) have demon- strated superior performance in a variety of graph mining and learning tasks. However, when node representations involve sensitive personal infor- mation or variables related to individuals, learn- ing from graph data can raise significant privacy concerns. Although recent studies have explored local differential privacy (LDP) to address these concerns, they often introduce significant distor- tions to graph data, severely degrading private learning utility (e.g., node classification accuracy). In this paper, we present UPGNET, an LDP-basee graph learning framework that enhances utility while protecting user data privacy. Specifically, propose three-stage pipeline that generalizes the LDP protocols for node fea- tures, targeting priviiy-sensitive scenarios. Our analysis identifies two key factors that affect the utility of privacy-preseeviig graph learning: fea- ture dimension and neighborhood size. Based on the above analysis, UPGNET enhances utility by introducing two core layers: High- Aggre- gator (HCA) layer and the Node Feature Regular- ization (NFR) layer. Extensive experiments on real-world datasets indicate that UPGNET signifi- cantly outperforms existing methods in terms of both privacy protection and learning utility.
Private Graph Learning
User
X
GNN
Low Utility
(a) Prior Works
Private Graph Learning
g User 1
X,-1IDP~ x
GNN High Utility
(b) Ours
:NFR layer
HOA layer)
Figure I. Comparison of (a) prior works and (b) ours in the lo- cally private graph learning scenario. The scenario comprises a cloud server and multiple users situated across different clients. Users' sensitive node features x are perturbed to x' using LDP before uploading to the cloud server for graph learning. Our ap- proach achieves higher utility by integrating & than prior works.
2018), and community detection (Chen et al., 2019). In real-worl world scenarios, graphs frequently contain significant amounts of sensitive personal information, such user pro- files on social networks. However, recent studies (Wang & Wang, 2022; Shen et al., 2022; Zhang et al., 2022; Meng et al., 2023) have proposed various privacy attack methods targeting GNN models, which pose serious security and pri- vacy challenges during their training. Therefore, designing efficient crivacy-preservin GNN framework to protect users' private information is of paramount importance.
To collect and analyze private data from decentralized data owners, local differential privacy (LDP) (Kasiviswanathan et al., 2011) I) has been increasingly accepted as the de facto standard for data privacy in the research community (Er- lingsson et al., 2014; Ding al., 2017; Wang et al., 2019a;b). In the LDP protocol, multiple users must interact with un- trustworthy server that may exploit their private data. Each user perturbs their data locally, typically through noise injec- tion (Dwork et al., 2006), to ensure privacy. The perturbed data is then transmitted to the server, which conducts data analysis and learning based on this information. Locally private graph learning have recently gained significant atten- tion from researchers (Sajadmanesh & Gatica Periz, 2021; Lin et al., 2022; Jin & Chen, 2022; Pei et al., 2023). Fig. 1 illustrates this scenario, where a cloud server interacts with decentralized users. Each user perturbs their sensitive node features x to x' under LDP before submitting them to the server for private graph learning (e.g., node classification).
1. Introduction
In recent years, Graph Neural Networks (GNNs) have shown superior performance in various domains, including social sciences (Hamilton et al., 2017), graph mining (Li et al., 2019), and bioinformaties (Fout al., 2017). GNNs have also achieved state-of-the-art performance on a range of downstream graph learning tasks, such as node classifica- tion (Kipf& & Welling, 2017), link prediction (Zhang & Chen,
Beijing University of Posts and Telecommunication, Beijing, China 'Shandong University, Qingdao, China. Correspondence to: Sen Su <susen bupt.edu.en
Proceedings of the 4nnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 20255 by the author(s).

---

Going Deeper into Locally Differentially Private Graph Neural Networks
However, in locally private graph learning, existing LDP protocols for perturbing node features cause significant per- formance degradation in GNNs (Sajadmanesh & Gatica- Perez, 2021; Lin et al., 2022). Specifically, LDP regulates noise injection through the privacy budget e, where a smaller e introduces more noise. In practice, e is highly limited and node features are typically multidimensional with multiple attributes. As a result, each attribute receives only a minimal fraction of the budget, leading to substantial information loss. While server-side aggregation mitigates noise to some extent, it also introduces excessive estimation errors, further reducing utility (e.g., node classification accuracy). Thus, the key challenge is how to maximize the utility of privacy- preserving graph learning while ensuring user privacy.
evaluate overall performance of UPGNET and the contribu- tions of each component under different parameters through theoretical analysis and extensive experiments.
Our contributions are summarized as follows. ① We pro- pose a three-stage pipeline to systematically generalize the LDP protocols for perturbing node features. By analyzing the pipeline, we identify two key factors influencing the es- timation error of feature aggregation. @ Based on the above analysis, propose NFR and HOA layers to reduce the estimation error and integrate them with LDP protocols, in- troducing UPGNET, a utility-enanceed graph learning framework. @ Extensive experiments on real datasets demonstrate that UPGNET excels in achieving privacy preservation and superior graph learning utility.
Contributions. To address this challenge, we present a three- stage pipeline that generalizes the current LDP protocols for perturbing node features. Our analysis of the pipeline reveals two key factors that influence the estimation error in feature aggregation: feature dimension and neighborhood size. We conclude that reducing the effective feature dimen- sion and expanding the effective neighborhood size help minimize the estimation error and thus enhance the utility.
2. Preliminaries
This section first defines the problem (Sec. 2.1), then pro- vides the essential background on LDP (Sec. 2.2) and GNN (Sec. 2.3), and finally describes the threat model (Sec. 2.4).
2.1. Problem Definition
Based on these findings, we propose UPGNET, a utility- graph
Consider a graph G = (V,E), where V = {vi, 02 ....... J 1 represents the set of nodes and E is the set of edges. Each decentralized user v E >/ locally possesses d-dimensional feature vector x, E Rd, and the feature matrix is defined as X E R [ Following previous work (Sajadmanesh & Gatica-Perez, 2021; Lin et al., 2022: Pei et al., 2023), we assume that the server has access to V and E, but X remains private and inaccessible to the server. Consequently, we face the challenge of performing graph learning on 9 while protecting the privacy of node features. Consistent with pre- vious work (Sajadmanesh & Fatica-Perez, 2021; Lin et al., 2022), this paper focuses on the node classification task in graph learning. Specifically, the node set V V, J V. is the union of the set of labeled nodes Vi2 and unlabeled ones Vu- The label y. for each node v is derived from set of possible labels, denoted y = (y), 1/113/.--.. ........ Me) The objec- tive of node classification (Kipf & Welling, 2017) is to learn function f V + ) that assigns labels to unlabeled nodes based on the graph structure and available node features.
enhanced framework for locally learning that minimizes estimation error and maximizes utility from two key perspectives (Comparison with prior works is presented in Fig. 1). First, to reduce the effective feature dimensions, we introduce a Node Feature Regular- ization (NFR) layer based on L1 regullarization (Bühlmann & Van De Geer, 2011), classical optimization technique that promotes sparsity in solutions. We conduct theoretical analysis using proximal gradient descent (Nitanda, 2014; Li & Lin, 2015) to derive a one-off, non-iterative solution. This enables the NFR to obtain sparse embeddings through feature selection, thereby reducing effective feature dimen- sions during aggregation. Second, to expand the effective neighborhood size, we propose multi-hop aggregation method, the Iligh-Order Aggregator (HOA) layer. Although our theoretical analysis indicates that increasing neighbor- hood size improves utility, real-world graphs often feature small neighborhoods. A straightforward solution, such as aggregating multi-layer node features (Abu-El-Haija et al., 2019; Gasteiger et al., 2019; Chen et al., 2020), suffers from over-smoothing (Rusch al., 2023). As the number of layers increases, node embeddings tend to converge, di- minishing the effectiveness of higher-order neighbors in correcting errors. To address this, our HOA layer leverages personalized aggregation and Dirichlet energy (Zhou et al., 2021; Rusch et al., 2023) analysis, effectively mitigating oversmoothing and reducing noise bias injection. UPGNET comprises two architectures: H-N (HOA followed by NFR) and N-H (NFR followed by HOA), both of which can be independently integrated with any GNN architecture. We
2.2. Local Differential Privacy
LDP (Kasiviswanathan et al., 2011; Yang et al., 2024; He et al., 2025) has been extensively studied and widely de- ployed in decentralized data collection and analysis scenar- ios. In particular, major companies such Apple (Thakurta et al., 2017), Google (Erlingsson et al., 2014), and Mi- crosoft (Ding et al., 2017) have adopted IDP. In an LDP
'This paper concentrates on protecting node features and can be effortlessly combined with algorithms aimed at protecting neighbor lists (Zhu et al., 2023; Lin al., 2022; Hidano & Murakamii, 2024).
2

---

Going Deeper into Locally Differentially Private Graph Neural Networks
setting, there exists a server and multiple users, each possess- ing sensitive data. Users not required transmit their private data to untrustworthy server. Instead, each user initially perturbs their data using perturbation mechanism M and then transmits the perturbed data to the server. Fol- lowing the collection of perturbed data from each user, the server performs data analysis and learning based on these data, ensuring that user privacy remains uncompromised. The formal definition of c-LDP is provided below.
2.4. Threat Model
As shown in Fig. 1, different users upload graph data to a third Parrt untrustworthy server. On the one hand, under semi-honest adversary setup, although the server follows our LDP protocol honestly, it may attempt to individually learn the private information of the data owner. On the other hand, an attacker (Wang & Wang, 2022; Shen et al., 2022; Zhang et al., 2022; Meng et al., 2023) can target the GNN model to extract private information from the victim node, leading disclosure of the user's privacy.
Definition 1 (e-LDP). A local perturbation mechanism M satisfies c-local differential privacy (c-LDP), where e >> O, if and only if for any user's private data r and x', we have:
3. Methodology
(M)ER yl
(1)
In this section, we begin with a theoretical analysis of prior work on locally differentially private graph neural networks (LDPPGNN) in See. 3.1, identifying the key factors limit- ing their utility. Following this, we introduce UPGNET, a utility- utility-enhanced private graph learning model, in Sec. 3.2.
where Range(M) denotes the set of all possible outputs of the perturbation mechanism M. In essence, I.P guarantees that the data aggregator on the server side can't reconstruct the data source, regardless of any prior knowledge. The parameter e, called the privacy budget, plays a pivotal role in balancing privacy and utility. A smaller (resp. larger) provides stronger (resp. weaker) privacy preservation but also results in lower (resp. higher) utility. LDP has several important properties, such as immunity to post- post-processing and sequential composition (Dwork, 2008).
3.1. Theoretical Analysis of LDPGNN
A series of studies (Sajadmanesh & Gatica-Perez. 2021; Du et al., 2021; Lin al., 2022; Jin & Chen, 2022; Qi et al., 2024; Pei et al., 2023) have been conducted on private graph learning based on LDP. However, no effort has been made to establish a unified framework for revisiting existing work to further enhance the utility of private graph learning. In this subsection, our objective is to identify the key factors influencing the aggregation estimation error by constructing and analyzing unified node feature LDP pipeline.
2.3. Graph Nerual Networks
In recent years, GNNs have gained popularity for graph mining and learning. The primary goal of GNNs is to learn embeddings for each node in a graph by combining initial node features with the graph's 'ss topology. These learned node embeddings can then be applied to various downstream tasks such node classification (Kipf& & Welling, 2017; Sun et al., 2024a;b). A typical K llaer GNN consists of K graph convolutional layers. Each layer aggregates information from neighboring nodes and updates the node's embedding. Following K aggregation iterations, the embedding of a node captures information from its neighbors within K hops. The formal definition of the k-th layer is as follows:
3.1.1. NODE FEATURE LDP PIPELINE
Currently, two faate-of-the-aee art LDP mechanisms are applied to node features: the piecewise mechanism (PM) (Wang et al., 2019a; Pei et al., 2023) and the multi-bit mechanism (MBM) (Du et al., 2021; Sajadmanesh & Gatica-Perez, 2021; Lin et al., 2022: Jin & Chen, 2022) (for more details on PM and MBM App. A). We propose unified node-feature LDP pipeline that generalizes these two approaches. Assum- ing that the node-feature LDP mechanism is denoted as M and the total privacy budget employed is e, the node-feature LDP mechanism can be outlined in three steps:
h() = AGGREGATER (hh Vu E (())),
(2)
h = UPDATER (hy
Perturbation. In total, there are | users, and each user u possesses a d-dimensional node feature x, containing their sensitive information. Users employ an LDP mechanism M to protect their privacy. Initially, the mechanism M randomly selects m dimensions from d dimensions without replacement, with m being a configurable parameter con- trolling the number of perturbed dimensions. Subsequently, each sampled dimension undergoes random perturbation with a privacy budget denoted as e/m, while the remaining d m dimensions are set to O. Ultimately, x,, undergoes the M mechanism to yield x denoted as x .(xx).
where.V(v) (v)) represents the set of neighbors of node u (which could include v itself). For any node E (v). h k- denotes the embedding of node u at layer l: 1. The ag- gregation functions at layer k, such as mean, sum, and max, are denoted as AGGREGATE&()) functions. h+ hrtre)) represents the output of the aggregation function on (v). (PD (-) denotes a learnable non-linear function at layer k. such as a neural network. Initially, h = Xx, indicating that the initial embedding of node is its feature vector X,.
3

---

Going Deeper into Locally Differentially Private Graph Neural Networks
Calibration. Following perturbation, x remains biased, i.e., E [xx] A Xg. Let E [x,] Xg, representing the ex- pected bias shift. The server calibrates the perturbed values with o. Note that o = 0 indicates an unbiased estimate.
3.2. UPGNET:
Utility-Enhaneed Private GNNS
In this section, we propose utility-enhanced private graph learning framework called UPGNET. Designed for various node feature LDP protocols, UPGNET incorporates plug- and-play NFR and HOA layers that significantly boost utility. Fig. 2 (a) provides an overview of UPGNET, and Fig. 2 (b) illustrates the two architectures of UPGNET.
Aggregation. After receiving the feature vectors x for all users v E V, the server aggregates these vectors as follows:
bw(w)) = AGGREGATE ((x,,, Vu (N))))
(4)
where li((t) represents the estimated embedding for any given node e after undergoing the AGGREGATE()). This es- timate is derived by aggregating the perturbed node feature vectors x", from all nodes u adjacent to the target node v. Theorem 2. Assuming o ==0, O, the aggregator function de- fined by Eq. (4) is an unbiased estimate, i.e., for any
3.2.1. OVERVIEW
This subsection introduces the foundational design princi- ples of UPGNET. According to Thm. 3, the key factors influencing the estimation error during the aggregation pro- cess are the feature dimension and the neighborhood size. Naturally, our objective is to minimize the estimation error during aggregation by targeting these two crucial factors, thereby enhancing the practicality of private graph learning. To this end, we design from the following two perspectives:
E Efh hw(())
As demonstrated in Thm. 2, the aggregation process is an unbiased estimate when = O and the AGGREGATE func- tion is linear, meaning the output is weighted summation of the inputs. For the proof, please refer to App. B.I.
Expanding the Effective Neighborhood Size. In order to extend the effective neighborhood size, direct multi-layer aggregation is potential approach. However, our analysis reveals that this method is significantly limited by over- smoothing (Rusch et al., 2023), which adversely affected the denoising performance. To address this, we propose a Frigher-Order Aggregator (HOA) layer, leveraging personal- ized aggregation and Dirichlet energy analysis to effectively mitigate over-smoothing and reduce noise injection.
3.1.2. KEY FACTOR ANALYSIS
In Sec. 3.1.1, we establish an LDP analytical pipeline for the node features, consisting of three stages: perturbation, calibration, and aggregation. In the context of privacy- preserving graph learning, the aggregation stage signifi- cantly impacts the overall utility of graph learning. High- quality aggregation helps mitigate the injected noise to a greater extent. Therefore, our objective to explore the key factors that directly influence the estimation error in the aggregation stage. The estimation error is defined as the dis- crepancy between hy((.). obtained by aggregating the per- turbed node features x', and (y( obtained by aggregating the original node features This discrepancy is represented as &
Reducing the Effective Feature Dimensions. In order to minimize estimation error by reducing the effective feature dimensions, we focus on the aggregation stage². Based on L1 ---egullarization and proximal gradient descent (PGD) (Ni- tanda. 2014; Li & Lin, 2015: Duan et al., 2022), we intro- duce the Node Feature Regularizer (NFR) layer.
Through theoretical analysis and experimental validation, UPGNET, in both the H-N (see Sec. 3.2.2) and the N-H architecture (see Sec. 3.2.3), effectively integrates the HOA layer and the NFR layer to reduce estimation error and en- hance learning utility across various LDP mechanisms.
e (1, (l...., .............. d}. Based on Bern- stein's 's inequality (Giroux et al., 1979), Thm. 3 provides analysis of the various factors influencing the discrepancy.
Theorem 3. Given the aggregator for the first layer and 5>0. with probability at least 1-8, for any node v, we have:
3.2.2. UPGNET IN H-N ARCHITECTURE
max E = O/ /Wo))) (1.....d). (6)
In this part, we introduce the H-N architecture of UPGNET where the perturbed node features x' are successively en- hanced by the HOA layer followed by the NFR layer.
According to Thm. 3, after eliminating the known privacy budget parameter e and the analysis parameter 8, two key factors that impact the estimation error are the feature di- mension d and the neighborhood size [W())). From Eq. (6),
Higher- Order Aggregator. According to Thm. 3, as the size of (w()) (i.e., (W(x))) increases, the estimation error decreases at a rate proportional to the square root of the node degree. This indicates that larger [+()) results in
we infer that smaller effective d is more conducive to re- ducing the estimation error, while larger effective (v)( is also advantageous to minimizing the estimation error. Therefore, in Sec. 3.2, our objective is enhance the utility of presevvire graph learning by influencing d and I (v)). Please see App. B.2 for the proof of Thm. 3.
'The reason for targeting the aggregation stage, rather than the perturbation or calibration stages, is that designing from the aggregation stage provides a certain level of generality and inde- pendence from different LDP mechanisms.
4

---

Going Deeper into Locally Differentially Private Graph Neural Networks
Client-Side
Server-Side
User
NFR layer
HOA layer
HOA layer
NFR layer
NFR layer
HOA layer
User
GNN
Z
x
LDP
O class I Octass 2
N-H architecture
H-N architecture
(a)
(b)
Figure 2. (a) Overview of our proposed UPGNET. On the client side, local node features x perturbed using LDP to obtain x'. On the server side, x' undergoes processing through an Node Feature Regularization (MFR) layer and an ElghhOrder Aggregator (HOA) layer to enhance utility before being input into the GNN for graph learning, enabling downstream tasks such node classification. (b) UPGNET features two distinct architectures: H-N (HOA layer followed by NER layer) and N-H (NFR layer followed by HOA layer).
smaller estimation errors. However, in practical scenarios, [W()] is usually quite small. One approach to address this issue is to expand ((v) by directly aggregating multiple layers of node features across K hops (Abu-El-Haija et al., 2019; Gasteiger et al., 2019; Chen et al., 2020; Sajadmanesh & Gatica-Perez, 2021; Lin et al., 2022) (defined the SKA method). However, the SKA scheme encounters the over- smoothing (Rusch et al., 2023), where increasing the value of K causes node embeddings to converge, reducing the effectiveness of information aggregation from higher-order neighbors and skewing the calibration of aggregation er- rors. To better understand the over-smoothing issue, we examine the Dirichlet energy (Rusch al., 2023) of the esti- mated node embeddings the graph, a primary measure of over-smoothing in deep GNNs. Specifically, the estimated embedding h is modeled embedding h and the noise signal 17, i.e., h h + 17. The Dirichlet energy T-)) of h is then defined as:
Algorithm High-Ordes Aggregator (HOA) Layer
Input: G = =VV,)) imput vector X., Ve V. step param-
eter K 2 0, linear aggregator function AGGREGATE(.)
for E V do
h (x(w) 0, x xx(o)) =
for k = 1 to K do
x ((t)) = AGGREGATE ((x)Tu) Vu Eu ((W))(o))
h((()) hV( + XX(o))
end for
h, R (x()
end for
Return: Aggregated embedding vector h., Ve E V
bias injection. First, shown in Thm. 4, the energy ratio Dx between HOA(-) and SKA(-) approaches 0 as K - co. This indicates that HOA is less influenced by information from infinite-hop receptive fields, allowing it to mitigate over-smoothing and expand into larger neighborhoods while still aggregating data from smaller ones. Second, HOA em- ploys personalized weightings during neighbor information aggregation, assigning the highest weight the nearest neighbor. The insight behind our approach is that informa- tion from the closest neighbor is more effective in calibrat- ing noise for that specific node, justifying its higher weight, while more distant neighbors receive lower weights. This design further alleviates noise bias injection. See App. B.3 for the proof of Thm. 4 and more details.
combination of the original
T(h) = M
Σ
Σ SEN(
b h
noise signal
where E (1,2..... K} represents the step parameter. Eq. (7) highlights two key observations: ① Over- see-hhho exists. As k increases, the difference between the embedding h; and its neighbor embedding h diminishes. After several rounds of propagation, all node features converge, causing sharp decline in the first term of T ((h), resulting in the typical oversmoothing phenomenon. @ Noise exacerbates over-smoorhing. Under the LDP, when e approaches 0, the noise term ||> - M 2 dominates the Dirichlet energy. This accelerates the homogenization of node features, leading to faster energy decay and thus intensifying the oversmoothing effect. Therefore, mitigating the over-smoothing problem to extend more effective neighborhood sizes is crucial.
Theorem 4. Let Tk Soa and Th I represent the Dirichlet energies of HOA(-) and SKA(-) at layer k, respectively. The energy ratio of HOA(.) to SKA(-) across K layers satisfies:
Φx = limm-
(EK
K nk
/hoa// EEK
k= T
0.
(8)
As in (Sajadmanesh & Gatica-Perez, 2021), we also employ the GCN aggregator function (Kipf & Welling, 2017) and perform the aggregations without including the self-loop. which will facilitate the reduction of the total noise.
To address the aforementioned issues, we propose utility- enhanced graph convolution layer called the High-Order Aggregator (HOA), as shown in Alg. 1. Compared to SKA, it has two advantages in reducing estimation error for noisy data: mitigating wver-smoohhng and reducing noise
Node Feature Regularization. Regularization is a clas-
5

---

Going Deeper into Locally Differentially Private Graph Neural Networks
sical method for optimizing minimization tasks (Hoyer, 2004; Bühlmann & Van De Geer, 2011; Negahban et al., 2017; Duan et al., 2022). Among various regularization techniques, L1 -eggglaarizztion tends to produce sparse so- lutions. In other words, parameters obtained through I regularization are more likely to have fewer non-zero com- ponents. This property facilitates the implementation of embedded feature selection, aligning with our objective of reducing the effective feature dimension. Next, we formal- ize the L -regullarization problem within UPGNET under the H-N architecture. We employ the mean aggregation function and define the embedding of node e after the server aggregates the perturbed feature vectors as follows:
Table 1. Statisties of graph datasets.
Dataset
Classes
Nodes
Edges
Features
Deg.
Cora
7
2.708
5,278
1,433
3.90
Citeseer
6
3,327
4,552
3,703
2.74
LastEM
18
7,624
27,806
7,842
7.29
Facebook
22,470
170,912
4,714
15.21
Deg. the table denotes the average node degree.
Theorem 6. For any node and any i E (1,..., d). (X.)i in Eq. (13) can efficiently achieve feature selection:
(xn): = sign ((x.))) max (I(x()+l - u2, 0),
(13)
where the optimal value for μán Ty where T2 E (0, 1), with B as the boundary of the perturbed node features. Ac- cording Thm. 6, we conclude that Eq. (13) can efficiently achieve feature selection for x',, thus enhancing the utility of graph learning. See Sec. C and App. B.5 for more details.
h AGGREGATE ((x., Vu E (V()))) =Wo)
Σ
X (9)
(EN(
where xl, represents the noisy node features of node u. We
define the loss function L1 (2r) as follows:
3.2.4. PRIVACY AND COMPLEXITY ANALYSIS
(iw = 2 [ EnEN(o) IIx - w11.. (10)
Privacy Analysis. The PM and MBM satisfy e-LDP for each node. The entire training process remains LDP compliant due the robustness of DP against the post-processing the- orem (Dwork al., 2014). Moreover, any subsequent pre- diction is bounded by the post-processing theorem (Dwork et al., 2014), since the LDP protocol is applied only once to the private data. This ensures that LDP holds for all nodes throughout the process. For more details, see App. D.
Based on this, we add the L--regularization terms || to Ci (ww to obtain the enhanced node embedding h. for any node as h. = arg min (iw + P1 || Thm. 5 derives the above L1 -e-egularrization problem by employing the proximal grudient descent (PGD) (Nitanda, 2014; Li & Lin, 2015; Duan et al., 2022) method.
Theorem 5. For any node E V and any feature dimen- sion i E {l....,d} d}, (ho); in the following equation can efficiently achieve feature selection for (bo);:
Complexity Analysis. The computational complexity of UPGNET mainly arises from its two key components: the HOA and the NFR. Through analysis, the overall complexity of UPGNET is O(K |1] d + [V] d), scaling linearly with graph size and feature dimensionality. This ensures that UPGNET remains both practical and scalable for large- scale graphs with high-ddmensional data. See App. E for more detailed analysis and comparisons with baselines.
(hw); = sign ((ho):) -max ((h.)))-mm..). (11)
where sign(-) denotes the sign function, which takes if (be); > 0, 0 if (hx); = O. and -1 if (hr); ); < O. The op- timal value for μ1 is Tı B/dk where TI E (0, 1), with B as the boundary of the perturbed node features, d as the approximate average degree of the graph, and K as the step parameter of the HCA layer. By Thm. 5, we conclude that Eq. (11) can efficiently achieve feature selection for hy, thereby contributing to enhancing the utility of private graph learning. See App. B.4 for the proof.
4. Experiments
In this section, we conduct series of experiments to vali- date the performance of UPGNET and its core components. More experimental results can be found in App. F.
4.1. Experimental Setting
Datasets. We conduct experiments on four representative graph datasets: Cora (Yang et al., 2016), Citeseer (Yang et al., 2016), LastFM (Rozemberezki & Sarkar, 2020), and Facebook (Rozemberczki et al., 2021). These datasets commonly used in graph machine learning (Wu et al., 2020; Zhang et al., 2020). Table provides the statistics for these datasets, with specific descriptions as follows:
3.2.3. UPGNET IN N-H ARCHITECTURE
Under the N-H architecture of UPGNET, the HOA is con- sistent with Alg. 1. The NFR specifically aims to enhance utility through efficient feature selection of the perturbed node features x' directly using Zy-regularization. The ob- jective function L2 of HOA is formalized as follows:
Cora and CiteSeer. They are well-knows citation net- works, where each node represents a scientific paper, and
(x = 2
|x - -x1 A2 |x|||
(12)
6

---

Going Deeper into Locally Differentially Private Graph Neural Networks
82
80
Accurncy (5)
Accurccy (%)
65
Accuracy (%)
Accuracy (%6
85
72
BASE
60
BASE
70
BASE
BASE
Solitude
Solitude
Solitude
Solitude
LPGNN
55
LPGNN
LPGNN
80
LPGNN UPGNer
UPGNer
UPGNer
60
UPGNet
62 0.01
0.1
1.0 Privacy Budget (e)
50
0.01
0.1
1.0
0.01
0.1
1.0
75
0.01
2.0
3.0
Privacy Budget (e)
Privacy Budget (t)
Privacy Budget (t)
(a) Cora (GCN)
(b) CiteSeer (GCN)
(c) LastEM (GCN)
(d) Facebook (GCN)
70
65
90
Accuracy (%6
75
Accurasy (la
80
Accuracy (36)
60
Accuracy
85
BASE
55
BASE
BASE
BASE
65
LPGNN
Solitude
50
LPGNN
Solitude
70
Solitade
LPGNN
80
LPGNN
Solinude
55
UPGNer
UPGNer
UPGNet
UPGNet
60
75
0.01
0.1
1.0
2.0
3.0
0.01
0.1
1.0
2,0
3.0
0.01
0.1
1.0
2.0
3.0
0.01
0.1
1.0
2.0
3.0
Privacy (s)
Privacy Budget (6)
Privacy Budget
(c)
Privacy Budget (c)
(e) Cora (GraphSAGE)
(f) CiteSeer (GraphSAGE)
(g) LastFM (GraphSAGE)
(h) Facebook (GraphSAGE)
88
67
78
72
62
57
668
Accuracy
62
BASE
Accuracy
52
BASE
Ascuracy
58
BASE
Accuracy
65
BASE
52
Solitude
47
Solitude
48
Solitude LPGNN
Solitude
50
42
LPGNN UPGNet
LPGNN
38
LPONN
UPGNer
28
UPGNet
35
UPGNet
0.01
0.1
1.0
2.0
3.0
0.01
0.1
1.0
2.0
3.0
0.01
0.1
1.0
2.0
3.0
0.01
0.1
1.0
2.0
3.0
Privacy (s)
Privacy Budget (6)
Privacy Budget (c)
Privacy Budget (6)
(i) Cora (GAT)
CiteSeer (GAT)
(k) LastFM (GAT)
()) Facebook (GAT)
Figure 3. Performance of UPGNET and other baselincs. X-axis represents and y-axis represents test accuracy (%).
the edges denote citation links. Each node contains a bfg-of-words feature vector and label for each category.
2021) and Solitude (Lin et al., 2022) apply different strate- gies to achieve locally differentially private graph learning. In addition, we consider the multi-bit mechanism (MBM) (Sa- jadmanesh & Gatica-Perez 2021) and the piecewise mecha- nism (PM) (Wang et al., 2019a) independently.
Facebook. This social network consists of nodes as official Facebook pages, with edges representing mutual liking relationships. Each node has feature extracted from the site description and a label indicating the category.
Parameter Settings. All datasets are randomly divided into 50/25/25% for training, validation, and test sets, re- spectively. To evaluate the performance of UPGNET, we use three representative GNN architectures, graph convo- lutional networks (GCN) (Kipf & Welling, 2017), Graph- SAGE (Hamilton al., 2017), and graph attention networks (GAT) (Velickovic et al., 201 8) as backbone models. By default, the dataset used is Cora, the LDP protocol applied is the MBM, the GNN model is the GCN, and UPGNET adopts the N-H architecture. For more details, see App. F.I and F2.
LastFM. Nodes in this dataset represent users of the music streaming service LastFM and links represent friendships between them. The classification task is to predict the users' home country given the artists liked them.
Baselines. To comprehensively assess the performance of UPGNET, we compare it with the following baselines: The NonPriv sets oo and inputs clean (non-perturbed) node features directly into the GNN for graph learning. In con- trast, BASE utilizes the GNN for graph learning directly after using node feature LDP protocols to perturb feature vectors, without incorporating additional utility enhance- ment strategies. LPGNN (Sajadmanesh & Matica-Perez,
Evaluation Metries. Consistent with prior work (Sajad- manesh & Gatica-Perez, 2021; Lin et al., 2022), we conduct experiments the node classification task, using classifi- cation accuracy as the primary metric to evaluate the per-
7

---

Going Deeper into Locally Differentially Private Graph Neural Networks
10
10
85
Cora Cieeeeer
Accuracy55)
ClieSeer LastFM
LastFM
80
Accurao
Tacebook
Accuracy
Tatebook
75
GesplSAGE
N-31
11-3
75
3.0
0.1
0.01
0.1
1.0
2.0
0001
0.1
1.0
2.0
3,0
(a)
(b)
(a) MBM
(b) PM*
Figure 4. (a) Comparison of the performance of UPGNET under different GNN models. (b) Comparison of the performance of UPGNET in H-N vs. N-H architectures.
Figure S. Comparison of the utility enhancement of MBM" and PM" under different e E {0.01, 0.1, 1.0, 2.0, 3.0}. X-axis represents privacy budget and y-axis represents test accuracy enhancement.
Table 2. Applying NFR layer to node feature LDP mechanisms PM and MBM to achieve utility enhancement. MBM and PM" represent the integration of the NE R layer with MEM and PM, respectively.
formance of UPGNET. All models undergo 500 training iterations and the best model is chosen for testing based on validation loss. Accuracy is measured over 10 consecutive runs, and we report the average along with 95% confidence intervals calculated by bootstrapping over 1000 samples.
Dataset
Mcch.
0.01
0.1
1.0
Overall
MBM
64.5
77.9
78.9
Cora
MRM
71.3
168
80.6 127
81.5 126
1.00
PM
65.3
78.5
794
4.2. Evaluating the Performance of UPGNET
PM"
72.0
1.6.
80.5 1.20
81.2 18
3.5
$2.5
61.7
65.4
In this experiment, we vary E in {0.01, 0.1, 1.0, 3.0, to thoroughly validate the performance under different noise scales. The experimental results across four datasets and various GNN backbone models are presented in Fig. 3. It shows that, in all cases, UPGNET consistently achieves higher accuracy than BASE, LPGNN and Solitude, and in some instances, it even approaches the accuracy of NonPriv. For example, in the case of Fig. (f), UPGNET increases accuracy by about 5% over LPGNN and Solitude when e = 3.0. Moreover, for Facebook (Fig. (d), (h)), the accuracy of UPGNET is closely aligned with that of NonPriv. All these observations underscore the superior utility of UPGNET.
CileSeer
MBM
57.2
1.4.
65.0 133.3
67.8 1.24
1 3.5
PM
53.1
62.8
66.
PM'
57.4 1 1.3
64.7 19
67.4 13
1 2.5
MBM
61.4
75.8
79.5
LastFM
MBM
67.1
79.4 11366
81.7 2.2.
1 3.8
PM
66.1
77.1
80.1
PM
68.7
112.6
79.5 1.4.4
81.9 L8
1 2.3
MBM
78.6
86.6
87.3
Facehook
MEM
84.9
1.6.
90.9
1.3
91.4 1.4.
1 1.9
PM
78.4
88.4
88.5
PM"
85.1
1.6.7
90.8
1.7
91.8
133
7 7.6
indicates the increase in utility after incorporating the NER.
between MBM and MBM* (MBM + NFR layer) as well as PM and PM* (PM + NFR layer) across different datasets and e. The results in Table clearly demonstrate that applying the NFR layer improves graph learning accuracy in all cases. Moreover, Table 2 and Fig. 5 indicates that NFR layer is more effective in improving graph learning accuracy when the privacy budget is small compared to when the privacy budget is large. For instance, in the case of the Cora dataset with MBM perturbing the node features, when e 0.01, MBM* improves accuracy by approximately 7% over MBM. When e 1.0, MBM* enhances accuracy by 2.6% over MBM. This is attributed to the fact that when is small, more noise is injected into the node features, so our NFR layer calibrates the noise and improves the accuracy more significantly.
4.3. Comparison of Different GNN Models
Fig. 4(a) intuitively compares the accuracy of UPGNET under different privacy budgets and across various GNN models. The results reveal that the GAT slightly worse than GCN and GraphSAGE. Specifically, under high privacy set- tings (e.g., when c = 0.01), the accuracy gap between GAT and the other two models becomes more pronounced. The GAT model introduces an attention mechanism that learns at- tention coefficients weight the neighbors neighborhood aggregation. Consequently, this makes GAT more sensitive to feature perturbations, resulting in a greater degradation of utility in high-noise settings. On the other hand, the utility of GAT remains comparable when e 2 0.1.
4.5. Ablation Study on the Performance of HOA
4.4. Ablation Study on the Performance of NFR
In this experiment, we investigate two aspects: first, whether Higher- Order Aggregator (HOA) layer can mitigate the over- smoothing in multilayer aggregation; and second, whether the HOA can effectively enhance the performance of private graph learning. To achieve these objectives, we compare
In this experiment, we investigate the utility enhancement of Node Feature Regularizer (NFR) layer for two node feature LDP mechanisms: piecewise mechanism (PM) and multi- bit mechanism (MBM). Table 2 shows the accuracy comparison
8

---

Going Deeper into Locally Differentially Private Graph Neural Networks
65
80
90
Accurncy
50
Accuracy
60
Ageuracy
60
Accurccy
53
20
40
HOA SKA
50
SKA
HOA
HOA SKA
60
HOA SKA
45
50
4
16
32
64
0
16
32
64
16
32
64
0
4
16
32
64
(a) Cora
(b) Citeseer
(c) LastFM
(d) Facebook
Figure Effect of HOA vs. SKA on graph learning performance across various steps K E [0, (0,2, 16, 64).
HOA with SKA and set K 20,2,4,8, 16, 32, for both HOA and SKA, consider the privacy budget 0.01. Fig. 6 shows the performance of HOA compared to SKA on accu- racy for different values of K. As illustrated in Fig. 6, for all datasets, the accuracy trend under SKA initially rises with increasing K, but after a certain point, it sharply de- clines, while the accuracy under HOA continues improve steadily. For example, in the LastEM dataset (Fig. 6 (c)), SKA'S accuracy peaks at K 4 but then drops rapidly, falling below 40% accuracy at K = 64. This sharp decline is due to the oversmoothing effect in SKA, where larger K values cause node embeddings to become overly similar, diminishing graph learning performance. HOA algorithm shows a steady increase in accuracy as K grows, indicating that the proposed HOA layer successfully mitigates oversmoothing and effectively aggregates useful information from expanded neighborhoods. Furthermore, for K E {2, 4, 8, 16, 32, 64), HOA consistently outperforms SKA, demonstrating that the HOA can significantly enhance the learning utility. See App. F.3 and F.5 for more details.
ogy, aligning with the scenario of this paper. In LPGNN, each user perturbs their features using the multi-bi bit mech- anism (MBM). However, this paper demonstrates that MBM introduces excessive noise to the feature vector, thereby reducing the utility of the final private graph learning pro- cess. Similarly, Du et al. (2021), Lin et al. (2022) and Jin & Chen (2022) utilize the MBM to perturb node features or employ the SKA (Sajadmanesh & Gatica-Perez, 2021; Lin et al., 2022) to calibrate noisy features. Besides MBM, the PM (Wang et al., 2019a; Pei et al., 2023) has also been ex- plored for similar utility challenges. In contrast to these approaches, our paper introduces a utility-enhanced locally private graph learning framework applicable to various node feature per- turbation mechanisms, including MBM and PM, to further enhance the utility of private graph learning.
graph learning, Yet, it faces
contrast, the
In addition to node feature perturbation, other efforts have addressed link privacy under LDP. Lin et al. (2022) adopted a naive randomized response mechanism (Qin et al., 2017) to protect adjacency lists. Hidano & Murakami (2024) pro- pose link LDP mechanism called DPRR, which injects noise into adjacency lists and node degrees respectively and calibrates the noisy links by degree-samppee sampling method. Zhu et al. (2023) propose Bayesian estimation- based link LDP mechanism called BLINK. Similar to DPRR, BLINK injects noise into adjacency lists and node degrees, and then esti- mates the ground truth graph using the adjacency lists as prior and the node degrees as evidence. This work, in con- trast, focuses on protecting node features, and is orthogonal to these approaches. It can be seamlessly integrated with existing methods designed to protect neighbor lists.
4.6. Comparison of Different Architectures
We evaluate the effect of both the N-H and H-N architectures on utility by varying e E {0.01, 0.1, 1.0, 2.0, 3.03 and con- ducting comparisons using the GCN. As shown in Fig. 4(b), for the Cora. the N-H architecture outperforms the H-N slightly in terms of accuracy. Notably, with smaller c, the N-H architecture excels in feature dimension optimization, which allows it to better handle the information loss from noise injection. However, as increases, the performance gap between the N-H and H-N architectures narrows, indi- cating that the early application of the NF R layer in the N-H architecture is more effective expanding the neighborhood range and enhancing utility when the noise is higher.
6. Conclusion
In this paper, we initially establish a pipeline to generalize the LDP protocols for perturbing node features. Through our analysis, we identify two key factors that affect the estima- tion error. Building these insights, we propose UPGNET, which incorporates NFR and HOA layers. The generalization and effectiveness of UPGNET and its components are vali- dated through theoretical analysis and extensive experiments in various datasets and parameter settings.
5. Related work
Recently, a series of works related to locally differentially private GNNs have been proposed. Sajadmanesh & Gatica- Perez (2021) propose a privacy-preserving graph learning framework called LPGNN, which assumes that node fea- tures are private and the server has access to the graph topol-

---

Going Deeper into Locally Differentially Private Graph Neural Networks
Acknowledgements
Duan, J., Ye, Q., and Hu, H. Utility analysis and enhance- ment of ldp mechanisms in high-dimensional space. In 2022 IEEE 38th International Conference Data Engi- neering (ICDE), pp. 407-419. IEEE, 2022.
This work supported in part by the National Natural Sci- ence Foundation of China (62072052), in part by the Na- tional Natural Science Foundation of China (62372051).
Dwork, C. Differential privacy: A survey of results. In International Conference on Theory and Applications of Models of Computation, pp. 1-19. Springer, 2008.
Impact Statement
This paper presents work aiming to advance the field of wrivacy-preservee graph learning. It focuses on enhancing the utility of private graph learning while preserving the privacy of graph data using local differential privacy. Our approach introduces more efficient framework for privacy- preserving graph learning, enhancing the overall utility of learning tasks while ensuring that user data remains pro- lected from potential privacy breaches. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here. We believe this work will contribute to the development of more efficient and scalable privacy-preserving graph learning frameworks.
Dwork, C., McSherry, F., Nissim, K., and Smith, A. Cal- ibrating noise to sensitivity in private data analysis. In Theory of Cryptography: Third Theory of Cryptography Conference, pp. 265-26622222 284. Springer, 2006.
Dwork, C., Roth, A., et al. The algorithmic foundations of differential privacy. Foundaations and Trends@) in Theo- retical Computer Science, 9(3-4)2211-40)) 2014.
Erlingsson, Ú., Pihur, V., and Korolova, A. Rappor:
Randomized aggregatable privacy-preserving ordinal re- sponse. In Proceedings of the 2014 ACM SIGSAC Confer- ence on Computer and Communications Security (CCS), pp. 1054-1067, 2014.
References
Fout, A., Byrd, J., Shariat, B., and Ben-Hur, A. Pro- tein interface prediction using graph convolutional net- works, Advances in Neural Information Processing Sys- tems (NeurIPS), 30, 2017.
Abu-EI-Haija, S., Perozzi, B., Kapoor, A., Alipourfard, N., Lerman, K., Harutyunyan, H., Ver Steeg, G., and Gal- styan, A. Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. In In- ternational Conference on Machine Learning (ICML), pp- 21-29. PMLR, 2019.
Gasteiger, J., Weißenberger, S., and Günnemann, Dif- fusion improves graph learning. Advances in Neural Information Processing Systems (NeurIPS), 32, 2019.
Baldi, P. and Sadowski, P. Understanding dropout. Advances in Neural Information Processing Systems (NeurIPS), 26:1-9, 2013.
Giroux, A., Rahman, Q., and Schmeisser, G. On bernstein's inequality. Canadian Journal of Mathematics, 31))): 347-353, 1979.
Bühlmann, P. and Van De Geer, S. Statistics for high- dimensional data: methods, theory and applications. Springer Science & Business Media, 2011.
Hamilton, W., Ying, Z., and Leskovec, Inductive repre- sentation learning on large graphs. Advances in Neural Information Processing Systems (NeurIPS), 30, 2017.
Chen, M., Wei, Z., Huang, Z., Ding, B., and Li, Y. Sim- ple and deep graph convolutional networks. In Inter- national Conference on Machine Learning (ICML), pp. 1725-1735 PMLR, 2020.
He, L., Tang, P., Zhang, Y., Zhou, P., and Su, S. Mitigating privacy risks in retrieval-augmentt generation via locally private entity perturbation. Information Processing & Management, 62(4):104150, 2025.
Chen, Z., Bruna, J., and Li, L. Supervised community detection with line graph neural networks. In 7th Interna- tional Conference on Learning Representations (ICLR), pp. 1-23, 2019.
Hidano, S. and Murakami, T. Pegree-preservve random- ized response for graph neural networks under local dif- ferential privacy. Transactions on Data Privacy, 17(2): 89-121, 2024.
Ding, B., Kulkarni, J., and Yekhanin, S. Collecting telemetry data privately. Advances in Neural Information Process- ing Systems (NeurIPS), 30, 2017.
Hoyer, P. O. Non-negative matrix factorization with sparse- ness constraints. Journal of Machine Learning Research, 5(9). 2004.
Du, W., Ma, X., Dong, W., Zhang, D., Zhang, C., and Sun, Q. Calibrating privacy budgets for locally private graph neural networks. In 202/ International Conference on Nenworking and Network Applicttion (NaNA), pp. pp. 23-29. IEFE, 2021.
Huang, X., Li, J., and Hu, X. Label informed attributed network embedding. In Proceedings of the Tenth ACM In- ternational Conference on Web Search and Data Mining (WSDM), pp. 731-739, 2017.
10

---

Going Deeper into Locally Differentially Private Graph Neural Networks
Jin, H. and Chen, X. Grosov-wasserstein discrepancy with local differential privacy for distributed structural graphs. In Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (ICCAI), pp. 2115- 2121, 2022.
Meng, L., Bai, Y., Chen, Y., Hu, Y., Xu, W., and Weng, H. Devil in disguise: Breaching graph neural networks pri- vacy through infiltration. In Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security (CCS), pp. 1133-1167, 2023.
Kasiviswanathan, S. P., Lee, H. K., Nissim, K., Raskhod- nikova, S., and Smith, A. What can we learn privately? SIAM Journal on Computing, 40(3):793-4 826, 2011.
Negahban, S. N., Ravikumar, P., Wainwright, M. J., and Yu, B. A unified framework for high- nigh-dimenssioal analysis of m-estimators with decomposable regularizers. Statistical Science, 27, 2017.
Kingma, D. P. and Ba, Adam: A method for stochastic optimization. Xrviv preprint arXiv:
Nitanda, A. Stochastic proximal gradient descent with ac- celeration techniques. Advances in Neural Information Processing Systems (NeurIPS), 27, 2014.
2014.
Kipf, T. N. and Welling, M. Semi-supervised classification with graph convolutional networks. In 5th International Conference on Learning Representations (ICLR), 2017.
Pei, X., Deng, X., Tian, S., Liu, J., and Xue, K. Privacy- enhanced graph neural network for decentralized local graphs. IEEE Transactions Information Forensics and Security, 2023.
Klambauer, G., Unterthiner, T., Mayr, A., and Hochreiter, S. Self-normalizing neural networks. Advances in Neural Information Processing Systems (NeurIPS), 30, 2017.
Qi, Y., Lin, X., Liu, Z., Li, G., Wang, J., and Li, J. Link- guard: Link locally works with integrated denoising and private learning. In Companion Proceedings of the ACM on Web Conference 2024 (WWW), pp. 593-596, 2024.
graph neural net-
Lee, J., Kang, S., Yu, Y., Jo, Y.YY,, Kim, S.-W., and Park, Y. Optimization of gpu-based sparse matrix multipli- cation for large sparse networks. In 2020 IEEE 36th International Conference on Data Engineering (ICDE), pp. 925-936. IEEE, 2020.
Qin, Z., Yu, T., Yang. Y., Khalil, I., Xiao, X., and Ren, K. Generating synthetic decentralized social graphs with local differential privacy, In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security (CCS), pp. 425-438, 2017.
Li, H. and Lin, Z. Accelerated proximal gradient meth- ods for nonconvex programming. Advances in Neural Information Processing Systems (NeurIPS). 28, 2015.
Li, Y., Gu, C., Dullien, T., Vinyals, O., and Kohli, P. Graph matching networks for learning the similarity of graph structured objects. In International Conference on Ma-
Rozemberczki, B. and Sarkar, R. Characteristic functions graphs: Birds of feather, from statistical descriptors to parametric models. In Proceedings of the 29th ACM International Conference on Information & Knowledge Management (CIKM), pp. 1325-1334, 2020.
chine Learning (ICLR), pp. 3835-3845. PMLR, 2019.
Lin, W., Li, B., and Wang, C. Towards private learning on decentralized graphs with local differential privacy. IEEE Transactions on Information Forensics and Security, 17: 2936-2946, 2022.
Rozemberezki, B., Allen, C., and Sarkar, R. Multi-scale at- tributed node embedding. Journal of Complex Networks, 9(2):cnab014, 2021.
Liu, C., Ma. X., Zhan, Y., Ding, L., Tao, D., Du, B., Hu, W., and Mandic, D. P. Comprehensive graph gradual prun- ing for sparse training in graph neural networks. IEEE Transactions Neural Networks and Learning Systems, 2023.
Rusch, K., Bronstein, M. M., and Mishra, S. A survey on oversmoothing in graph neural networks. SAM Research Report, 2023, 2023.
Sajadmanesh, S. and Gatica-Perez, Locally private graph neural networks. In Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security (CCS), pp. 2130-2145, 2021.
Liu, X., Ding, J., Jin, W., Xu, H.. Ma. Y., Liu, Z., and Tang. J. Graph neural networks with adaptive residual. Advances in Neural Information Processing Systems (NeurIPS), 34: 9720-9733, 2021.
Shen, Y., He, X., Han, Y., and Zhang, Y. Model stealing attacks against inductive graph neural networks. In 2022 IEEE Symposium on Security and Privacy (S&P), pp. 1175-1192. IEEE, 2022.
Meier, L., Van De Geer, S., and Bühlmann, P. The group lasso for logistic regression. Journal of the Royal Sta- tistical Society Series B: Statistical Methodology, 70(1):
Sun, L., Huang, Z., Wan, Q., Peng, H., and Yu, P. Spiking graph neural network on riemannian manifolds.
53-71, 2008

---

Going Deeper into Locally Differentially Private Graph Neural Networks
In Advances in Neural Information Processing Systems (NeurIPS), pp. 1-12, 2024a.
Zhang, Z., Cui, P., and Zhu, W. Deep learning on graphs:
A survey. IEEE Transactions on Knowledge and Data Engineering, 34(1):249-270, 2020.
Sun, L.. Huang, Z., Wang, Z., Wang. F., Peng, H., and Yu, P. S. Motif-aware riemannian graph neural network with generative-contrr contrastive learning. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAT), volume 38, pp. 9044-9052, 2024b.
Zhang. Z.,, Chen, M., Backes, M., Shen, Y., and Zhang. Y. Inference attacks against graph neural networks. In 31st USENIX Security Symposium (USENIX Security), pp. 4543-4560. 2022.
Thakurta, A. G., Vyrros, A. H., Vaishampayan, U. S.,
Zhou, K., Huang. X., Zha, D., Chen, R., Li, L.., Choi, S.-H., and Hu, X. Dirichlet energy constrained learning for deep graph neural networks. Advances in Neural Information Processing Systems (NeurIPS), 2221834421846 2021.
Kapoor, G., Freudiger, J., Sridhar, R., and Davidson, D. Learning new words, us patent 9,594,741. 2017.
Velickovic, P., Cucurull, G., Casanova, A., Romero, A.,
Liò, P., and Bengio, Y. Graph attention networks. In 6th International Conference on Learning Representations (ICLR), 2018.
Zhu, X., Tan, Y., and Xiao, X. Blink: Link local dif- ferential privacy in graph neural networks via bayesian estimation. In Proceedings of the 2023 ACM SIGSAC Conference Computer and Communications Security (CCS), pp. 2651-2660 1664,, 2023.
Wang, N., Xiao, X., Yang, Y., Zhao, J., Hui, S. C., Shin, H., Shin, J., and Yu, G. Collecting and analyzing multi- dimensional data with local differential privacy. 2019 IEEE 35th International Conference on Data Engineering (ICDE), pp. 638 649. IEEE, 2019a.
Wang, T., Ding, B., Zhou, J., Hong, C., Huang, Z., Li, N., and Jha, S. Answering multi-dimensional analytical queries under local differential privacy, In Proceedings of the 2019 International Conference Management of Data (SIGMOD), pp. 159-176, 2019b.
Wang, X. and Wang, W. H. Group property inference at- tacks against graph neural networks. In Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security (CCS), pp. 2871-2884, 2022.
Wu, Z., Pan, S., Chen, F., Long, G., Zhang, C., and Yu, P. S. comprehensive survey on graph neural networks. IEEE Transactions Neural Networks and Learning Systems, 32(1):4-24 24, 2020.
Yang. M., Guo, T., Zhu, T., Tjuawinata, I., Zhao, J., and Lam, K.-Y. Local differential privacy and its applica- tions: A comprehensive survey. Computer Standards & Interfaces, 89:103827, 2024.
Yang. Z., Cohen, W., and Salakhudinov, R. Revisiting semi-supervised learning with graph embeddings. In International Conference on Machine Learning (ICLR), pp. 40-48. PMLR, 2016.
Yu, S., Mazaheri, A., and Jannesari, A. Topology- net- work pruning using multi-stage graph embedding and re- inforcement learning. In International Conference on Ma- chine Learning (ICLR), pp. 25656-25667. PMLR, 2022.
Zhang, M. and Chen, Y. Link prediction based on graph neu- ral networks. Advances in Neural Information Processing Systems (NeurIPS), 31, 2018
12

---

Going Deeper into Locally Differentially Private Graph Neural Networks
A. Node Feature LDP Mechanisms
A.1. Piecewise Mechanism
The one-dimensional piecewise mechanism (PM) (Wang et al., 2019a) takes E [-1, The perturbed value is sampled from the following distribution:
1] as input* and outputs the perturbed
e'/2+1 value x' E [[QQ,Q] Q], where Q e-/=-1"
P.
e [(x),
Pr(u' = clao
(14)
&u e (z)) (r(x),
where p 5ا
its high-dimensional form, the piecewise mechanism initially uniformly samples m dimensions from the d dimensions without replacement. Subsequently, perturbs the data each of the selected dimensions using the e/m-LDP. According the sequential composition property (Dwork, 2008) of the LDP mechanism, it adheres to c-LDP. After receiving all the perturbed data, the server performs de-biasing the reporting data x² using the following equation: x' .r." The variance of x' is as follows:
- 221 and r(x) = ((x) + Q 1. 1.
2.</242'
d(e + +3)
d. cc/2m
Var[z*] = 3m(e</2m
+
m - 1) -1-1 1 x
(15)
1)2
The range of a' is as follows:
e²12 +1
e²/2 +1
s' E
(16)
g=/2
1 m ge/2
A.2. Multi-bit Mechanism
The multi-bit mechanism (MBM) (Sajadmanesh & Gatica-Perse 2021) is an extension of the 1-bit mechanism (Ding et al., 2017). In its one-dimensional form, for any original data x E [-1,1], 1]. the distribution followed by the perturbed value r' {-1, 1} is follows:
x+1
ifc=
Pr|z' c|ar]
(17)
=
In its high-dimensional form, similar to the piecewise mechanism, each sampled dimension carries out c/m-LDP perturbation. After receiving all the perturbed data, the server transforms the reporting data x to its unbiased estimate x' The variance of x' is as follows:
d.
e// +1
xx"
cf/m m
V Var[æ'] d e +
x
(18)
cc/m
1-/m-11
The range of x' is follows:
d
cc/m +
0, d
c//m +
x' E
(19)
m
ec/m
m
ec/m
B. Theoretical Proof
B.1. Proof for Theorem 2
Proof. According Eq. (4), we have: E [fivie)) E [AGGREGATE ((x,, Vu N(o)))
Since AGGREGATE(() is linear, we have:
E [iN(
AGGREGATE ([E(2)) Vu (No)))
Considering 0, we have E[x(,]
X. and hence have:
E h hwv()
AGGREGATE ((x,, Vu (V)))) hy(")-
WWithout loss of generality, this paper assumes each dimension the input data is normalized the range [-1,
13

---

Going Deeper into Locally Differentially Private Graph Neural Networks
B.2. Proof for Theorem 3
Proof. For any node u e V and dimension E 21,,,.... ....,,.,, d), following the perturbation and calibration stages, we determine that a'y E [-B, B), where B is finite boundary. We define X z'us -n,... Given Fu, E [-1,1], we have: [X] B+1,
and through the calibration stage, a O, we know that E [X] [ Lu,i 0.
Assuming the mean aggregator is employed, for any node E V and any dimension i f1.2.... ...,,....a d}. we have:
(horco)s= = [(
Σ "EN(")
Iuss
(hwow))
[W(v]
Σ s'y.
(20)
MEN(")
Thus, based on the Bernstein inequality, we have:
Pr (hN(o)) (ba(())ss 22 = Pr
(a an.i)
(21)
(EN(v)
(2))()) [W(1] EvEN(e) Var[X] 31(B+1)
x² (2
2. exp
-xpp
2 exp {
(22)
2V [=',.) }ABB +
Considering Eq. (15) and Eq. (18), we have:
Variau,, = O md.
(23)
22
Considering Eq. (16) and Eq. (19), we have:
B = 0
(24)
Substituting the Eq. (23) and Eq. (24) into Eq. (22), we obtain:
X2 (P
- -bx)))(((x)))))) 2 2
s 2. exp
(25)
0 2O
By applying the union bound, we have:
Pr
max i)(
21 = UUr
(hrr)))ss - (kwrr)) 21]
(26)
i=1
{- XPW((o) ( - xO
Pr
(bw(w))) 2 2 = 2d exp
(27)
1=1
To ensure that max;e(1,..... d}
(hwr)); (bw(w))) < x holds with at least probability, it is sufficient to set
5 = 2d exp
X(W(()) o md +
Solving the above for X, we get: À O O(/abggd////////W//
B.3. Proof for Theorem 4
Proof. Considering that
T(h)
Σ
h
by
Σ Σ KEV JEN(m)
|b h
1 n 1|
(28)
V
LEV jEN(mM
noise signal
and
(1 1 Eiev EjEN(o))
[i - Bit
Σk
ck
Φ
lim
k=
Hoa
lim
(29)
K K
E
K+x
( EyENEo)
h2
km
14

---

Going Deeper into Locally Differentially Private Graph Neural Networks
although both HOA and SKA introduce the noise term r/ in each iteration, the key difference lies in how they handle the propagation and amplification of noise. As explained in the main paper, HOA employs personalized aggregation strategy, allowing it to better control the noise amplification effect in subsequent layers. Specifically, by assigning smaller aggregation weights to the neighbors in more distant levels, HOA can mitigate the cumulative impact of noise. Consequently, as K (the number of aggregation steps) approaches infinity, the effect of noise diminishes more effectively in HOA, leading to the condition & x 0.
B.4. Proof for Theorem 5
Proof. For the L1 -ereguularizatin problem addressed this paper, we employ the proximal gradient descent (PGD) (Nitanda, 2014: Li Lin, 2015; Duan et al., 2022) method for its solution. First, we obtain the derivative of Lı(w):
VLi(w)
Σ (w x w mEN(w))
Σ
X
hy.
(30)
uEN(v)
Then, the derivative of VLi(w)
dV dw
According Cauchy mean value theorem, we have:
V IVL (w) VL2 (wx=)l2 $ | - 1
(31)
where wy represents the result of the k-th iteration. We can approximate L1 (w) around wE using second-order Taylor expansion, given by:
C1 (w) (((w)) + (VLL (wx), w - wuk + 2 I|w - wxl
1 || (w) VL, (wx) const,
where const is a constant independent of w and (5 denotes the inner product. The minimum of the above equation is obtained at 1 as follows:
wk+1 = wy - VL, (w)s).
(32)
We then introduce the J.1 regularrizziio term in the iteration:
1
W = arg min | (wx VL (wx))ll + |2]]]
(33)
2
Let w, denote the i-th dimension of Since each dimension is independent, we have:
1 2 I|w; - ((w,); - VL((wx))))) pn
(Wi++ ) arg min
(34)
Let 2; = (wx)+ ((w(())))) (wx); (wx):: (h.)), (h.);. Computing (We+1); depends whether w; is positive, negative or 0. Below, we compute it the following cases:
w. > 0, by setting the gradient w. 2; + μi of Eq. (34) equal to zero, we obtain (WK+1); = 2; 1 > 0, hence 2; μ1-
w < 0, similarly, we obtain (wx+1)s = 2, + M1 < 0, hence z; < -11
w. = 0, we obtain (wx+1); = 0, in which case
| < 14-
Consequently, we have:
(wa+1); = sign(z;). max (12,) 0),
(35)
where sign denotes the sign function, which takes if (f..); 0. if (h.); o, and -1 if (h,); 0. Applying
(wx+1)+ = (hr); and z; = (ha)..
(h.); sign (ho))s max ((h))a - (000)l-m1,00) -1,0)
(36)
15

---

Going Deeper into Locally Differentially Private Graph Neural Networks
The optimal value for jr is Tı B/dk, where Ti (0, 1), with B as the boundary of the perturbed node features, d as the approximate average degree of the graph, and K as the step parameter of the HOA layer. Here, d approximates the number of neighbors, larger number of neighbors tends to smooth out the feature values, allowing for relatively smaller regularization parameter A11. This formulation reflects how the regularization strength can adjust according to the feature magnitude and the neighborhood structure.
B.5. Proof for Theorem 6
Proof. Under the N-H architecture, the NFR layer aims to enhance utility through efficient feature selection of the perturbed node features x' using I--regularization. The objective function L2 is defined as follows:
1 ||x' -x-- -x112 C2(x) 2
u2 ||x||
(37)
Our goal is to minimize the above loss function. The proof procedure is similar to that of Theorem 5 and is not repeated.
C. More Details of N-H Architecture
In this section, We provide more details on the N-H architecture of UPGNET, where the perturbed node features x' are sequentially enhanced by first passing through the NFR layer followed by the HOA layer.
Node Feature Regularization. Under the N-H architecture, the NFR layer specifically aims to enhance utility through efficient feature selection of the perturbed node features x' directly using -e-relularizttion. The objective function L2 is formalized as follows:
(2(x) = 2 ||x x|[ + p2 ||x||
(38)
Our goal is to minimize the above loss function. Thm. 7 derives this regularization problem. According to Thm. 7, conclude that Eq. (39) can efficiently achieve feature selection for x',, thereby enhancing the utility of private graph learning. Theorem 7. For any node and any i {L...., d}. (Ko); in the following equation can efficiently achieve feature selection:
(Xo); sign ((x))x) mmxx
(39)
where the optimal value for in is T2B, where 72 E (0, 1), with B as the boundary of the perturbed node features.
Higher-Order Aggregator. After utility enhancement through the NER layer, additional utility enhancement is achieved by executing Alg. I on the enhanced feature vector X through the HCA layer.
D. Privacy Analysis
The piecewise mechanism (PM) (Wang et al., 2019a; Pei et al., 2023) and multi-bit mechanism (MBM) (Du et al., 2021; Sajadmanesh & Gatica-Perez, 2021; Lin et al., 2022; Jin & Chen, 2022) satisfy e-local differential privacy for each node. The entire training process remains LDP-compliant due to the robustness of differential privacy against post-processing (Dwork et al,, 2014) (Thm. 8). Moreover, any subsequent prediction is bounded by the post-processing theorem (Dwork et al., 2014), since the LDP is applied only once to the private data. This ensures that LDP holds for all nodes throughout the process.
Definition 8 (Post-processill processing). If an algorithm A(-) satisfies c-local differential privacy, then any further processing of its output by another algorithm B()) (i.e., process B(A())) also maintains c-local differential privacy.
E. Complexity Analysis
The computational complexity of UPGNET mainly arises from its two key components: the HOA layer and the NFR layer. The HOA layer performs K steps of high-order neighborhood aggregation, where each step aggregating feature vectors from neighboring nodes. This process has time complexity of O[|E| d), where |ε| is the number of edges and d is the feature dimension, resulting in a total complexity of O(K - d). The NFR layer applies lightweight element-wise transformations to each node's 's feature vector, contributing a complexity of O(V) d), where [V] is the number of nodes. Combining these, the overall computational complexity of UPGNET is O(K 1E] d + + d), scaling linearly with graph size and feature dimensionality. This ensures that UPGNET remains both practical and scalable for large-scale graphs with
16

---

Going Deeper into Locally Differentially Private Graph Neural Networks
high-dimensional data. Furthermore, compared other methods (Solitude (Lin al., 2022) and LPGNN (Sajadmanesh & Gatica-Perez, 2021)), the computational complexity of UPGNET introduces only an additional factor V d. This factor is linear with respect to the number of nodes and the feature dimension, making it highly efficient in practice, Moreover, graph pruning ( (Yu et al., 2022; Liu et al., 2023) or parallelization techniques, such as GPU-based sparse matrix operations (Lee et al., 2020), can be applied to further reduce computational overhead.
F. Additional Details of Experiments
E.1. More Parameter Design
To evaluate the performance of UPGNET, we use three state-of-the-art GNN architectures, graph convolutional networks (GCN) (Kipf& & Welling, 2017) GraphSAGE (Hamilton et al., 2017) and graph attention networks (GAT) (Velickovic et al., 2018), as the backbone models. All GNN models have two graph convolutional layers, each with hidden dimension of size 16 and SeLU activation function (Klambauer et al., 2017) followed by dropout. The GAT model has four attention heads. To obtain the best hyperparameters, we use grid search for selection: both learning rate and weight decay are chosen from {10-4, 1003 10-2 10- 10- and dropout is chosen from {10- 10 1000-,10000 1011001.0000 The HOA's step parameter is denoted by K. Based on the selected best hyperparameters, the best K within {0, 4, 8, 16, 32, 64] for all e E (0.01, 0.1, 1, 3). The parameters Ti. 72 of the NER layer belong to {0.1, 0.3, 0.5, 0.7, 0.9}. We use the Adam optimizer (Kingma & Ba, 2014) for all models. Without specification, we report the average results based on the best of each parameter.
F.2. More Descriptions about the GNN Model
GCN (Kipf& & Welling, 2017) applies spectral graph convolution by propagating node features using the Laplacian matrix. The core update rule is: HT++1 = (D- (O(),, where À = A 7 is the adjacency matrix with self-loops, D is its degree matrix, (1))) is the trainable weight matrix, and a is activation function.
GraphSAGE (Hamilton et al., 2017) samples fixed number of neighbors and aggregates their features, making it scalable for large graphs. The general update rule is: (++1) a (W AGGREGATE (1e Vu E ((())))), where AGGREGATE(() represents the aggregation operation.
GAT (Hamilton et al., 2017) employs self-attention to dynamically assign importance to neighbors. The update rule is: ho (1+1)
(weEN()) awu (O where the attention coefficient Oeu is computed as:
exp(LeakyReLU((/1100 |W( 1
Ogg
Σ (o) E e (
(40)
Here, a is a learnable vector, and denotes concatenation.
F33 Impact of Average Node Degree of Dataset on HOA
As shown Table 1, the social network datasets, Facebook (Rozemberczki et al., 2021) and LastFM (Rozemberczki Sarkar, 2020), exhibit a higher average node degree (Deg.) compared citation networks (Cora (Yang et al., 2016) and CiteSeer (Yang al., 2016).. For Facebook and LastEM, as illustrated in Fig. 6, the accuracy leveled off after K 1, despite further increases in K. This suggests that for social networks with higher average node degrees, the initial aggregation step provides a sufficient representation of node information. In contrast, for lower-degree citation networks Cora and CiteSeer, the accuracy continues to improve until K = 64 after K = 1. This indicates that in low-degree datasets, HOA requires more steps to aggregate enough neighboring nodes for better accuracy.
F44 Scalability on Heterophilic Graphs
When applied to heterophilic graphs (e.g., Flickr (Huang et al., 2017) and Reddit (Hamilton et al., 2017); see Table 3 for detailed statistics), UPGNET continues to demonstrate superior utility compared to other haselines, as shown in Fig. 7. The HOA layer, by preserving Dirichlet energy and enabling personalized aggregation, effectively calibrates noise in heterophilic graphs, as evidenced by the experiments in Fig. 8.
F.5. Ablation Study on HOA layer
17

---

Going Deeper into Locally Differentially Private Graph Neural Networks
Table 3. Statistics of heterophilic graph datasets.
DATASET
#CLASSES
#NODES
#EDGES
#EATURES
FLICKR REDDIT
89,250 232,965
899,756
500
41
114,615,992
602
88
48
Accuncy (5)
86
Accenncy
Accuracy
Accuracy
Solitud
Solitude
44
84
LPGNN
LIGNN
42
HOA SKA
HOA
UPGNet
UPGNNe
SKA
34 0.01
80
0.01
0.1
1.0
2.0
3.0
80
(ed
Privacy Budgeet
(a) Flickr
(b) Reddit
(a) Flickr
(b) Reddit
Figure 7. Performance comparison of UPGNET and other baselines Flickr and Reddit. X-axis represents and y- axis represents test accuracy (%). UPGNET exhibits superior performance compared to other basclines.
Figure Effect of HOA vs.
graph lcarning perfor-
mance across various steps K E {2, 4, 8, 16, 32, 64). HOA
demonstrates its superior denoising capability heterophilic datasets (Flickr and Reddit).
Fig. 9 presents an additional experiment demonstrating its superiority in private graph learning compared to residual connections (RC) (Liu et al., 2021). RC primarily ad- dresses vanishing gradients but remains ineffective in suppressing LDP noise. In contrast, HOA mitigates oversmoothing by preserving Dirichlet energy, thereby effectively cali-
Accuracy
60
HOA
RC
brating noise.
40
20
F.6. NER vs. other Regularization Approaches
2
4
8
16
32
64
K
As stated Thm. 3, a key aspect of noise calibration LDPGNN lies in reducing the effective feature dimensions. NFR employs regularization, which directly facilitates feature selection and enhances fine-grained noise calibration. contrast, Dropout (Baldi & Sadowski, 2013) and Group Lasso (Meier et al., 2008) fail to achieve precise feature selection tailored for noise calibration. Dropout introduces randomness by stochastically deactivating neurons, leading to instability in feature selection, while Group Lasso en- forces sparsity at a predefined group level, requiring carefully designed group definitions that may not align with optimal noise calibration. These limitations reduce their effec- tiveness mitigating noise impact. Empirical results (Table 4) further validate that NFR outperforms Dropout and Group Lasso preserving learning utility.
Figure Comparison of HOA
and Residual Connection (RC)
(Dataset: Cora, = 0.01). HOA demonstrates significantly better
classification accuracy in private
graph learning compared to RC.
Table Comparison of our NFR (without HCA) with dropout and group Lasso 0.01, GCN). The values in the table represent accuracy (9). NER demonstrates significantly better learning utility compared to other sparsity-inducing techniques.
BASELINE
CORA
CITESEER
LASTFM
FACEBOOK
DROPOUT
63.4
$2.7
61.3
77.6
GROUP LASSO
57.6
50.5
57.1
78.9
OURS
71.3
57.2
67.1
84.9
18


Reviews:
[{"review_id": "ECL53IDjqo", "reviewer": "Reviewer_NNeA", "summary": "The paper introduces UPGNET, a utility-enhanced framework for locally differentially private (LDP) graph learning. It addresses privacy challenges in Graph Neural Networks (GNNs) by proposing a three-stage pipeline to generalize LDP protocols for node feature perturbation. Key contributions include identifying two critical factors influencing estimation error: feature dimension and neighborhood size . To mitigate these, UPGNET incorporates a Node Feature Regularization (NFR) layer using L1-regularization to reduce effective feature dimensions and a High-Order Aggregator (HOA) layer to expand effective neighborhood size, thereby minimizing estimation errors . The framework is compatible with existing LDP mechanisms (e.g., MBM, PM) and integrates with GNN architectures like GCN and GraphSAGE. Experiments on datasets (Cora, Citeseer, LastFM, Facebook) demonstrate UPGNET’s superiority over prior methods (e.g., LPGNN) in utility, achieving higher classification accuracy while reducing attribute inference attack success rates. Theoretical analysis validates the effectiveness of NFR and HOA in noise reduction and aggregation efficiency. The work advances privacy-preserving graph learning by balancing utility and LDP guarantees through novel architectural and optimization strategies.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your valuable comments and suggestions. Detailed responses are provided below. The newly added figures and tables can be found in the link ※: https://anonymous.4open.science/r/3814/1.pdf\n\n**Q1: Lack of LPGNN's implementation details**\\\n**R1:** The hyperparameters and optimization settings of LPGNN are detailed in Tables 1 and 2 of the link ※. Based on the settings in the original paper, we further carefully tune the hyperparameters and select optimal values. Additionally, our evaluation follows the standard practices (Sajadmanesh, et al., 2021) to minimize potential biases.\n\n**Q2: Why does the attack experiment assume full access to neighbors’ attributes?**\\\n**R2:** This assumption is designed to set an extreme-case scenario in which attackers are powerful by accessing neighbors' attributes. UPGNet exhibits excellent defensive capabilities under such highly adversarial conditions. In addition, supplementary experiments (shown in Fig. 3 of the link ※) are conducted to investigate the effect of attackers having varying proportions of accessed neighbor information, in which UPGNet consistently shows robust defense performance.\n\n**Q3: Does the attack experiment align with the threat model?**\\\n**R3:** The attack experiment aligns with the threat model outlined in §2.4. Specifically, the attack experiment explicitly targets scenarios in which untrusted servers attempt to infer private attributes, which aligns with the focus of the threat model. Built on this premise, the attack provides a rigorous assessment of the model's defensive capability in adversarial settings.\n\n**Q4: Lack of ablation study on NFR and HOA layers**\\\n**R4:** For the NFR layer, as stated in Tables 1 and 3 of the original manuscript, the ablation study (e.g., testing NFR alone) evaluates its effectiveness in noise calibration. For the HOA layer, Fig. 2 of the link ※ presents an additional experiment demonstrating its superiority in private graph learning compared to residual connections (RC). RC primarily addresses vanishing gradients but remains ineffective in suppressing LDP noise. In contrast, HOA mitigates oversmoothing by preserving Dirichlet energy, thereby effectively calibrating noise.\n\n**Q5: Lack of privacy-utility trade-off curves**\\\n**R5:** Fig. 1 in the link ※ presents privacy-utility trade-off curves (e.g., accuracy vs. ϵ), illustrating that UPFNet consistently outperforms other baselines across a range of privacy levels. The results highlight a clear utility advantage while maintaining strict privacy guarantees, demonstrating that UPFNet effectively navigates the trade-off between privacy and performance. Furthermore, the observed trend aligns with the principles of Pareto optimality, reinforcing that UPFNet effectively balances privacy preservation and model performance in private graph learning.\n\n**Q6: Ambiguous abbreviation \\& unclear phrase**\\\n**R6:** Thank you for pointing out the ambiguous abbreviation \"LPGNN\". It is first introduced in §4.1 with proper citation and further defined in the Related Work (§5) and App. G for clarity. The unclear phrases in Fig. 1 have been revised; see Fig. 6 in the link ※ for the updated version.\n\n**Q7: NFR vs. other regularization approaches**\\\n**R7:** As stated in Thm. 2, a key aspect of noise calibration in LDP-GNN lies in reducing the effective feature dimensions. NFR employs L1 regularization, which directly facilitates feature selection and enhances fine-grained noise calibration. In contrast, Dropout and Group Lasso fail to achieve precise feature selection tailored for noise calibration. Dropout introduces randomness by stochastically deactivating neurons, leading to instability in feature selection, while Group Lasso enforces sparsity at a predefined group level, requiring carefully designed group definitions that may not align with optimal noise calibration. These limitations reduce their effectiveness in mitigating noise impact. Empirical results (Table 4 in the link ※) further validate that NFR outperforms Dropout and Group Lasso in preserving learning utility.\n\n**Q8: HOA vs. nonlinear aggregation**\\\n**R8:** HOA layer is applied prior to the GNN, ensuring compatibility with GNN's nonlinear activations (ReLU, attention). The HOA layer adopts linear aggregation because nonlinear aggregation may distort noise distribution, introducing bias and amplifying estimation errors under LDP constraints. In contrast, its linear aggregation preserves LDP unbiasedness (Thm. 1), effectively mitigating estimation errors and maximizing denoising effectiveness.\n\n**Q9: Scalability on heterophilic graphs**\\\n**R9:** When applied to heterophilic graphs (e.g., Flickr and Reddit), UPGNet continues to demonstrate superior utility compared to other baselines, as shown in Fig. 4 of the link ※. The HOA layer, by preserving Dirichlet energy and enabling personalized aggregation, effectively calibrates noise in heterophilic graphs, as evidenced by the experiments in Fig. 5 of the link ※.", "claims_and_evidence": "The claims in the paper are **not fully supported by clear and convincing evidence** due to methodological limitations. Below are key issues:  \n\n### 1. **Insufficient Baseline Comparison**  \nThe paper claims UPGNET \"excels over prior methods (e.g., LPGNN)\" in utility. However, the comparison lacks **direct implementation details** of LPGNN (e.g., hyperparameters, optimization settings). Without replicating LPGNN’s setup, the superiority claim is **unverifiable**. This violates the requirement for \"clear and convincing evidence\" under standards like \"much more likely than not\" .  \n\n### 2. **Weak Empirical Validation of Privacy Defense**  \nThe attribute attack experiments (Fig. 5(b)) assume attackers have **full access to neighbors’ features**, which is unrealistic in decentralized LDP settings. The paper does not validate whether the attack model aligns with the threat model (§2.4), which assumes \"untrusted servers\" . Additionally, the reduction in attack accuracy (e.g., 50% to 30%) is not tied to **quantitative metrics** like *ϵ* or *δ* (Differential Privacy guarantees), weakening its rigor.  \n\n### 3. **Lack of Isolation in Key Factors**  \nThe theoretical claim that reducing **effective feature dimension** *d* and expanding **neighborhood size** *|N(v)|* minimizes estimation error (Thm. 2) is not empirically isolated. For instance:  \n- **NFR Layer**: While L1-regularization reduces *d*, its impact is conflated with HOA’s effect. Ablation studies (e.g., testing NFR alone) are absent.  \n- **HOA Layer**: The claim that HOA mitigates oversmoothing via Dirichlet energyis not compared to standard techniques like residual connections .  \n\n### 4. **Over-Reliance on Synthetic Metrics**  \nThe utility metric (classification accuracy) is not tied to **privacy-utility trade-off curves** (e.g., accuracy vs. *ϵ*). Without showing Pareto optimality, the claim of \"superior utility\" remains subjective.", "methods_and_evaluation_criteria": "See comments above", "theoretical_claims": "Checked, and it looks sound.", "experimental_designs_or_analyses": "See comments at the end", "relation_to_broader_scientific_literature": "N/A", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "The paper demonstrates **originality** in its dual approach to addressing LDP-GNN utility challenges through feature regularization (NFR) and high-order aggregation (HOA), creatively combining classical L1 regularization with modern GNN architectures. This integration of theoretical insights (e.g., identifying feature dimension and neighborhood size as critical factors) with practical modular design (H-N/N-H architectures) offers a novel framework for balancing privacy and utility. The work also **significantly advances** the field by extending LDP protocols to diverse GNN models (GCN, GraphSAGE) and mechanisms (MBM, PM), providing a scalable solution for decentralized graph learning. The ablation studies and theoretical analysis (e.g., Thm. 2 linking HOA to noise reduction) strengthen its technical depth.  \n\nHowever, **clarity** in validation is compromised by incomplete baseline comparisons (e.g., LPGNN’s hyperparameters not fully disclosed) and limited empirical scope (e.g., reliance on homophilic citation networks). While the threat model aligns with LDP principles, the attribute attack experiments assume unrealistic full neighbor access, weakening practical relevance. Additionally, the societal impact section is vague, limiting the paper’s real-world applicability. Despite these gaps, the framework’s modular design and theoretical grounding make it a promising step toward robust LDP-GNN systems, particularly for scenarios with strong homophily. Its focus on noise mitigation through architectural innovation sets a clear path for future work in heterogeneous graph settings.", "other_comments_or_suggestions": "- **Ambiguous abbreviation**: \"LPGNN\" is first mentioned in Sec. 4 but defined later (Appendix G); forward reference needed or add it to related work.\n- **Unclear phrase**: \"low utility! GNN\" and \"high utility! GNN\" in Figure 1’s caption use exclamation marks without context.", "questions_for_authors": "1. **Alternative Regularization Approaches**: The paper uses L1-regularization (NFR) to reduce effective feature dimensions. Why were other sparsity-inducing techniques (e.g., dropout, group Lasso) not explored? Could these alternatives offer better noise resistance or computational efficiency, and what challenges prevented their adoption? A convincing answer would clarify whether L1 is uniquely suited to LDP-GNNs or if limitations (e.g., sensitivity to hyperparameters) necessitated this choice.  \n\n2. **HOA vs. Nonlinear Aggregation**: The HOA addresses oversmoothing through Dirichlet energy and personalized weights. Given that GNNs often use nonlinear activations (ReLU, attention), why was a linear aggregation framework chosen for theoretical analysis (Thm. 1)? Would nonlinear HOA variants better align with real-world GNNs, and what barriers exist to integrating them? Clarification here could strengthen the practical relevance of the theoretical claims.  \n\n3. **Baseline Implementation Gaps**: The comparison with LPGNN lacks hyperparameter details. What specific challenges arose in replicating LPGNN’s setup, and how were they addressed? If implementation differences (e.g., optimizer choices) skewed results, this could undermine the claim of UPGNET’s superiority.  \n\n4. **Privacy Attack Realism**: The attribute attack assumes attackers have full access to neighbors’ perturbed features (Fig. 5(b)). Why was this unrealistic threat model chosen over scenarios with partial access or decentralized adversaries? Would UPGNET’s defense degrade in more plausible settings, and how does this affect its practical utility?  \n\n5. **Scalability to Heterophilic Graphs**: Experiments focus on homophilic datasets (Cora, Citeseer). What challenges arise when applying UPGNET to heterophilic graphs (e.g., Flickr, Reddit), where node features and neighbors disagree? Could HOA’s reliance on multi-hop aggregation amplify noise in such cases, and how would the framework adapt?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "XKl10JyDBn", "reviewer": "Reviewer_V5sG", "summary": "This paper aims to enhance the utility of locally differential privacy graph learning. Its theoretical analysis derives two key factors affecting the estimation error, i.e., feature dimension and neighborhood size, and concludes that reducing the effective feature dimension and expanding the effective neighborhood size are conducive to enhancing the utility. Based on this conclusion, the paper proposes NFR and HOA layers to optimize the feature dimension and neighborhood scale. The generalization and effectiveness of UPGNet and its components are verified through theoretical analysis and experimental validation.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your valuable comments and suggestions, which have significantly contributed to improving the quality of our paper. Detailed responses to each comment are provided below.\n\n**Q1: Provide an analysis on the impact of graph density on the performance. The difference in graph density—whether a graph is sparse or dense—can play a crucial role in the performance of models, especially in tasks involving graph neural networks. The difference in the density of different graphs, does this have an impact on the model performance in this paper and what is the impact?** \n\n**R1:** Thank you for the valuable suggestion. As detailed in Appendix F.6, our experiments indicate that graph density has a noticeable impact on the performance of the proposed method. The table below shows the average node degree (Avg. Deg.) of the four datasets used in the paper:\n\n| Dataset | Cora | CiteSeer | LastFM | Facebook |\n| ---- | ---- | ---- |---- |---- |\n|Avg. Deg.|\t3.90 |\t2.74 |\t7.29|\t15.21|\n\nSpecifically, social network datasets like Facebook and LastFM, which exhibit higher average node degrees (higher graph density), show that accuracy levels off after just a few aggregation steps (e.g., K = 1). This is because the dense nature of these networks allows effective information aggregation early on, making additional steps less effective. \n\nIn contrast, for sparser graphs like Cora and CiteSeer, the accuracy continues to improve with additional aggregation steps (up to K = 64), indicating that more steps are required to gather sufficient neighboring information for better node representation. These observations suggest that the performance of our method is influenced by the density of the graph, with denser graphs benefiting from fewer aggregation steps and sparser graphs requiring more steps for improved accuracy. For further details, please refer to Appendix F.6 in our paper.\n\n**Q2:  Provides details of different GNN architectures. The paper has validated and compared model performance under different GNN architectures, including Graph Convolutional Networks (GCN), GraphSAGE, and Graph Attention Networks (GAT). However, it would be beneficial to offer more comprehensive implementation details for these architectures. This will help the reader to better understand how these models are applied and compared.** \n\n**R2:** Thank you for the valuable suggestion. Appendix F of the paper provides details on the configurations of three different GNN models. To clarify these configurations further, the following elaboration is provided: All GNN models (GCN, GraphSAGE, and GAT) consist of two graph convolutional layers, each with a hidden dimension of 16 and a SeLU activation function, followed by dropout layer. The GAT model employs four attention heads.\n\nAdditionally, we have added implementation details of these three GNN models to enhance readers' understanding of their application and comparison, as follows:\n\n- **GCN** applies spectral graph convolution by propagating node features using the Laplacian matrix. The core update rule is: $H^{(l+1)} = \\sigma(\\tilde{D}^{-1/2} \\tilde{A} \\tilde{D}^{-1/2} H^{(l)} W^{(l)})$, where $\\tilde{A} = A + I$ is the adjacency matrix with self-loops, $\\tilde{D}$ is its degree matrix, $W^{(l)}$ is the trainable weight matrix, and $\\sigma$ is a activation function.  \n- **GraphSAGE** samples a fixed number of neighbors and aggregates their features, making it scalable for large graphs. The general update rule is:  $h_v^{(l+1)} = \\sigma(W^{(l)} \\cdot \\text{AGGREGATE}(\\{h_u^{(l)}, \\forall u \\in \\mathcal{N}(v)\\}))$, where $\\text{AGGREGATE}(\\cdot)$ represents the aggregation operation.\n- **GAT** employs self-attention to dynamically assign importance to neighbors. The update rule is: $h_v^{(l+1)} = \\sigma\\left(\\sum_{u \\in \\mathcal{N}(v)} \\alpha_{vu} W^{(l)} h_u^{(l)}\\right)$, where the attention coefficient $\\alpha_{vu}$ is computed as:  $\\alpha_{vu} = \\frac{\\exp(\\text{LeakyReLU}(a^T [W^{(l)} h_v^{(l)} \\| W^{(l)} h_u^{(l)}]))}{\\sum_{k \\in \\mathcal{N}(v)} \\exp(\\text{LeakyReLU}(a^T [W^{(l)} h_v^{(l)} \\| W^{(l)} h_k^{(l)}]))}$. Here, $a$ is a learnable vector, and $\\|$ denotes concatenation.\n\n**Q3: Adjust charts for clarity. Adjust the vertical coordinate spacing in the graphs to improve clarity, e.g., Figure 9.** \n\n**R3:** Thank you for your suggestion. The vertical coordinate spacing in Figure 9 has been adjusted to enhance its clarity. Please refer to Figure 7 in the anonymous link (https://anonymous.4open.science/r/3814/1.pdf) for the updated version.", "claims_and_evidence": "Yes, this paper confirms its claims through detailed theoretical analysis and experimental validation.", "methods_and_evaluation_criteria": "- The proposed method effectively enhances the utility of privacy graph learning.\n- The baselines compared and the benchmark datasets employed are comprehensive and sensible.\n- The adopted evaluation metrics are reasonable and aligned with previous work.", "theoretical_claims": "Yes, I have checked the correctness of the five proofs of this paper.", "experimental_designs_or_analyses": "Yes, I have checked the soundness of the experimental design, validation and analysis of this paper.", "relation_to_broader_scientific_literature": "With the increasing use of GNNs in privacy-sensitive domains such as social networking and bioinformatics, the issue of data privacy has become critical. This paper hopes to enhance the model utility while utilizing local differential privacy to achieve privacy preservation, making it more practical and promising for real-world applications in sensitive data environments.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "# Strengths: \n- **Novel and important problem**. With the increasing use of GNNs in privacy-sensitive domains such as social networking and bioinformatics, the issue of data privacy has become critical. This paper hopes to enhance the model utility while utilizing local differential privacy to achieve privacy preservation, making it more practical and promising for real-world applications in sensitive data environments.\n- **Theoretical Innovations**. This paper derives two key factors affecting the estimation error, i.e. feature dimension and neighborhood size, through theoretical analysis. It is concluded that reducing the effective feature dimension and enlarging the effective neighborhood size are conducive to improving the utility. Then, UPGNet integrates two layers, HOA and NFR, expands the effective neighborhood range, and applies L1 regularization for feature sparsification, which reduces the estimation error in the LDP setting. These analyses and components represent important theoretical innovations.\n- **Sufficient experimental validation**.  This paper conducts detailed experiments on multiple datasets to illustrate the performance of UPGNet in various privacy budgets. The results show that the performance of UPGNet is stable and accurate, proving the practicality and robustness of the proposed framework.\n\n\n# Weaknesses: \n- **Provide an analysis on the impact of graph density on the performance**. The difference in graph density—whether a graph is sparse or dense—can play a crucial role in the performance of models, especially in tasks involving graph neural networks. The difference in the density of different graphs, does this have an impact on the model performance in this paper and what is the impact?\n- Provides details of different GNN architectures. The paper has validated and compared model performance under different GNN architectures, including Graph Convolutional Networks (GCN), GraphSAGE, and Graph Attention Networks (GAT). However, it would be beneficial to offer more comprehensive implementation details for these architectures. This will help the reader to better understand how these models are applied and compared.\n- **Adjust charts for clarity**. Adjust the vertical coordinate spacing in the graphs to improve clarity, e.g., Figure 9.", "other_comments_or_suggestions": "- Provide an analysis on the impact of graph density on the performance. \n- Provides details of different GNN architectures. The model performance under different GNN architectures of GCN, GraphSAGE and GAT was validated and compared in the paper, and specific implementation details of the three different GNN architectures should be provided.\n- Adjust charts for clarity.", "questions_for_authors": "- Can you provide details on different GNN architectures?\n- Could the charts be adjusted for better clarity?\n- How does the density of the datasets impact the performance?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "DxlnlB35H3", "reviewer": "Reviewer_XrJc", "summary": "This study introduces the UPGNET framework, which aims to protect user privacy through Local Differential Privacy (LDP) while enhancing the learning utility of graph neural networks. It innovatively proposes the High-Order Aggregator and Node Feature Regularization layers to optimize feature dimensions and neighborhood size. Experimental results demonstrate that UPGNET outperforms existing methods on real-world graph datasets. This work holds significant implications for private machine learning, particularly in the context of privacy-preserving graph neural networks.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your valuable comments and suggestions, which have significantly contributed to improving the quality of our paper. Detailed responses to each comment are provided below.\n\n**Q1: Adding more experiments under the GNN model, e.g. GAT. While the paper provides valuable insights into the GNN model's performance, adding experiments specifically focused on GAT would provide a more comprehensive comparison of different GNN architectures.**  \n\n**R1:** We appreciate the reviewer’s suggestion to include experiments with GAT to provide a more comprehensive comparison across different GNN architectures. These experiments have been conducted, and the results are presented in Appendix F.6. Specifically, Figure 6 in the original manuscript illustrates the performance of UPGNet compared to various baselines (BASE, Solitude, and LPGNN) under GAT with different privacy budgets $\\epsilon \\in$ {0.01, 0.1, 1.0, 2.0, 3.0}. The results demonstrate that UPGNet consistently outperforms these baselines across all privacy settings, further confirming its effectiveness in enhancing both utility and privacy preservation in graph learning. To improve clarity and ensure that readers do not overlook these results, the main text will be revised to explicitly highlight the presence of GAT-based experiments.\n\n**Q2: In the experiment section, the use of the ↑ symbols in Table 1 should be clearly defined. Providing an explanation of what the ↑ symbol represents would enhance the reader’s understanding of the data presented.**  \n\n**R2:** Thank you for your valuable feedback. The ↑ symbols in Table 1 represent the utility improvement achieved by integrating the NFR layer, indicating the enhancement in performance when NFR is applied compared to when it is not. To ensure clarity for readers, an explanation of the ↑ symbol will be added to both the table caption and the surrounding text, making it clear that this symbol indicates the increase in utility after incorporating the NFR layer.\n\n**Q3: There are places in the article where necessary citations should be added, such as line 176 in the right-hand column on page 4, where citations should be added for proximal gradient descent (PGD).**  \n\n**R3:** Thank you for the suggestion. The appropriate citation for proximal gradient descent (PGD) will be added in line 176 to ensure proper referencing.\n\n**Q4: Why is it required to select m dimensions for perturbation in d-dimensional node features under LDP?**  \n\n**R4:** Thank you for your question. The selection of $m$ dimensions for perturbation in $d$-dimensional node features under LDP is a design choice aimed at controlling the trade-off between privacy and utility. By randomly selecting $m$ dimensions from the $d$ available dimensions, the mechanism focuses on perturbing only a subset of the features, thereby limiting the extent of noise injected. Each selected dimension is perturbed with a privacy budget of $\\epsilon/m$, ensuring that the total privacy budget is allocated evenly across the perturbed dimensions. This strategy balances privacy preservation and the maintenance of data utility.\n\n**Q5: Can the method proposed in the paper be applied to more GNN frameworks such as GAT?**  \n\n**R5:** Thank you for your question. As mentioned in Q2, experiments with GAT are presented in Appendix F.6 of the original manuscript. These results demonstrate that our approach is effective across different GNN architectures, confirming its generalizability and applicability to a variety of graph learning models.\n\n**Q6: Why use node classification accuracy as a metric?**  \n\n**R6:** Thank you for your question. Node classification accuracy is used as a metric because it directly measures the effectiveness of graph-based models in learning meaningful representations of nodes, which is central to many graph learning tasks. This metric allows us to evaluate the trade-off between privacy preservation and utility. Additionally, node classification accuracy aligns with prior work (Sajadmanesh & Gatica-Perez, 2021; Lin et al., 2022) in the field, ensuring consistency and comparability of our results with established benchmarks. By using this metric, we maintain continuity with existing research while demonstrating the ability of our proposed methods.", "claims_and_evidence": "The claims made in the study are supported by clear and convincing evidence. The paper provides a solid theoretical foundation for the proposed methods, such as the analysis of key factors impacting the utility of privacy-preserving graph learning. Additionally, extensive experiments on benchmark datasets validate the effectiveness of the proposed framework UPGNET in terms of both privacy preservation and learning utility. The performance comparisons with baseline methods like LPGNN and Solitude further strengthen the claims.", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria, including the benchmark datasets (Cora, CiteSeer, LastFM, Facebook), are well-suited to the problem at hand.", "theoretical_claims": "I checked the proofs in this paper, including unbiased estimation, key factor analysis, feature sparsification analysis in NFR, etc., and these proofs are correct.", "experimental_designs_or_analyses": "I checked the experimental sections of this paper, including the experimental setup, performance validation of UPGNET, ablation study of NFR and HOA, architecture comparison and empirical privacy attack defense experiments. The experimental validation of this study is adequate and detailed.", "relation_to_broader_scientific_literature": "This paper addresses an important and timely issue in privacy preserving machine learning. The methods in the paper effectively enhance the utility of privacy graph learning.", "essential_references_not_discussed": "There are no essential references that have been overlooked in this paper.", "other_strengths_and_weaknesses": "Strengths\n1. this paper addresses significant challenges in privacy-preserving gnn, with a special focus on utility loss due to local differential privacy perturbations. \n2. this paper validates the effectiveness of UPGNET for utility enhancement and privacy preservation through detailed theoretical analyses and extensive experiments. \n3. this paper is well organized and well written.\n\nWeaknesses\n1. Adding more experiments under the GNN model, e.g. GAT. While the paper provides valuable insights into the GNN model's performance, adding experiments specifically focused on GAT would provide a more comprehensive comparison of different GNN architectures.\n2. In the experiment section, the use of the ↑ symbols in Table 1 should be clearly defined. Providing an explanation of what the ↑ symbol represents would enhance the reader’s understanding of the data presented. \n3. There are places in the article where necessary citations should be added, such as line 176 in the right-hand column on page 4, where citations should be added for proximal gradient descent (PGD).", "other_comments_or_suggestions": "Suggestion 1: Conducting additional experiments using different GNN models, such as GAT, would provide a more comprehensive evaluation of the framework's performance.\nSuggestion 2: Providing an explanation of what the ↑ symbol represents would enhance the reader’s understanding of the data presented. \nSuggestion 3: Add the necessary references.", "questions_for_authors": "1.\tWhy is it required to select m dimensions for perturbation in d-dimensional node features under LDP?\n2.\tCan the method proposed in the paper be applied to more GNN frameworks such as GAT? \n3.\tWhy use node classification accuracy as a metric?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "82zBNYjSLv", "reviewer": "Reviewer_jWSr", "summary": "This paper presents UPGNet, a utility-enhanced framework for locally private graph learning. The main contribution is a three-stage pipeline that generalizes local differential privacy protocols for perturbing node features, aiming to balance privacy preservation with improved learning utility. The authors identify two key factors influencing utility: feature dimension and neighborhood size. To address these, they propose two novel components: the Node Feature Regularization (NFR) layer, which reduces the effective feature dimension, and the High-Order Aggregator (HOA) layer, which mitigates over-smoothing by expanding the effective neighborhood size. The theoretical analysis and experimental results validate the effectiveness of the proposed framework in achieving a balance between privacy and utility in graph learning tasks.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your valuable comments and suggestions, which have significantly contributed to improving the quality of our paper. Detailed responses to each comment are provided below.\n\n\n**Q1: Provides more description of the node classification task. This paper conducts experiments based on the node classification task and verifies the effectiveness of the UPGNet method in this paper in terms of utility enhancement compared to other methods. Providing more specific instructions on the node classification task is necessary.**  \n\n**R1:** Thank you for your valuable suggestion. A more detailed description of the node classification task, along with its formal definition, will be included in the revised manuscript.\n\nThe node classification task [1][2] is a fundamental problem in graph learning, where the objective is to predict the labels of nodes based on the graph structure and available node features. Given a graph $\\mathcal{G} = (\\mathcal{V}, \\mathcal{E})$, where $\\mathcal{V}$ is the set of nodes and $\\mathcal{E}$ is the set of edges, each node $v_i \\in \\mathcal{V}$ is associated with a feature vector $\\mathbf{x}_i \\in \\mathbb{R}^d$ and may have a corresponding label $y_i$ from a predefined label set $\\mathcal{Y}$. The goal is to learn a function $f: \\mathcal{V} \\to \\mathcal{Y}$ that assigns labels to unlabeled nodes based on their attributes and graph connectivity.  \n\n> [1] Kipf, Thomas N., and Max Welling. \"Semi-Supervised Classification with Graph Convolutional Networks.\" ICLR. 2017.\\\n [2] Bhagat, Smriti, Graham Cormode, and S. Muthukrishnan. \"Node classification in social networks.\" Social network data analytics (2011): 115-148.\n\n**Q2: The theorem to be referenced should have been presented earlier in the text.**\n\n**R2:** Thank you for your suggestion. The manuscript will be revised to ensure that the referenced theorem appears earlier in the text, improving the logical flow and readability.\n\n**Q3: Equation (2) in the paper uses the superscript $k$ to indicate the layer, while Equation (7) uses the superscript $(k)$ in a slightly different notation. This inconsistency in formalization can confuse readers, making it harder to follow the mathematical derivations. It is suggested that the authors review the formalization of these equations and ensure that the notation for layers is consistent throughout the paper.**\n\n**R3:** Thank you for pointing out this inconsistency in our notation. The notation for layer indices has been carefully reviewed and unified throughout the paper to improve clarity and consistency. Specifically, we now consistently use the superscript [$\\cdot^k$] across all equations to denote the $k$-th layer in our model.\n\n**Q4: How does the HOA layer in the paper differ from multi-hop graph structures?**\n\n**R4:** Thank you for your question. The key difference between the High-Order Aggregator (HOA) and traditional multi-hop graph structures lies in the way information is aggregated across different neighborhood scales. While multi-hop methods explicitly expand the receptive field to fixed-hop neighborhoods, HOA dynamically balances information across different hops, ensuring that the energy ratio $\\Phi_K$ (Equation 8 in Section 3.2.2) approaches 0 as $K \\to \\infty$, which reduces over-smoothing. Unlike standard multi-hop aggregation, which applies uniform or predefined weight decay, HOA assigns personalized weightings, prioritizing closer neighbors to enhance noise calibration. This design prevents excessive noise propagation from distant nodes while still leveraging high-order information adaptively. These differences make HOA more effective in maintaining utility under noisy conditions. For more details, please refer to Section 3.2.2 on HOA and Section 4.4 on HOA ablation experiments in the paper.\n\n**Q5: How is the effectiveness of NFR in improving utility validated in the experiments?**  \n\n**R5:** Thank you for your question. In Section 4.3, a detailed ablation study is conducted to validate the effectiveness of the Node Feature Regularizer (NFR) layer in improving utility. Specifically, the node classification accuracy of the piecewise mechanism (PM) and multi-bit mechanism (MBM) with and without the NFR layer is compared across different datasets and privacy budgets.  As shown in Table 2 in the paper ($\\star$ in the table represents the integration of NFR), incorporating NFR layer consistently enhances accuracy, with more significant improvements under smaller privacy budgets. For example, in the Cora dataset, MBM$^\\star$ improves accuracy by 7% over MBM at $\\epsilon=0.01$, while the improvement is 2.6% at $\\epsilon=1.0$. This demonstrates that NFR effectively mitigates noise impact, especially under strong privacy constraints. Additional results are provided in Appendix D.5.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "Yes, I checked", "experimental_designs_or_analyses": "I reviewed the experimental designs and analyses presented in the paper, particularly those evaluating the performance of the proposed UPGNet framework. The experimental setup includes comprehensive testing on four benchmark datasets and compares UPGNet against several baselines. The experimental results validate the effectiveness of the proposed framework in achieving a balance between privacy and utility in graph learning tasks.", "relation_to_broader_scientific_literature": "The key contributions of this paper are closely related to the broader scientific literature on privacy-preserving machine learning, particularly in the context of Graph Neural Networks (GNNs) and local differential privacy (LDP). The paper's key contributions pushes forward both the theoretical and practical aspects of applying LDP to GNNs.", "essential_references_not_discussed": "The citations and related work in the paper are comprehensive.", "other_strengths_and_weaknesses": "Strengths:\n\n(i)Originality and Innovation: The problem of this paper is interesting and significant, and the method proposed by the authors significantly improves the utility of privacy-preserving graph learning without compromising privacy. \n\n(ii)Clear Theoretical and Experimental Support: The paper is well-structured, with a solid theoretical foundation to justify the proposed methods. \n\n(iii)Practical Relevance: The proposed methods and their demonstrated effectiveness in privacy-preserving settings could have broad applications, making the research practically significant.\n\nWeaknesses: \n\n(i)Provides more description of the node categorization task. This paper conducts experiments based on the node classification task and verifies the effectiveness of the UPGNet method in this paper in terms of utility enhancement compared to other methods. Providing more specific instructions on the node classification task is necessary. \n\n(ii)The theorem to be referenced should have been presented earlier in the text. \n\n(iii)Equation (2) in the paper uses the superscript $k$ to indicate the layer, while Equation (7) uses the superscript $(k)$ in a slightly different notation. This inconsistency in formalization can confuse readers, making it harder to follow the mathematical derivations. It is suggested that the authors review the formalization of these equations and ensure that the notation for layers is consistent throughout the paper.", "other_comments_or_suggestions": "see the weaknesses", "questions_for_authors": "(i)How does the HOA layer in the paper differ from multi-hop graph structures?\n\n(ii)How is the effectiveness of NFR in improving utility validated in the experiments?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper devised a novel utility-enhanced framework for locally differentially private graph learning. All reviewers saw its strengths and reached a clear consensus that this submission could be accepted in ICML-2025. The reviewers also raised several minor issues that should be considered in the final revision.
Decision: Accept (oral)