Differentially Private Decoupled Graph Convolutions for Multigranular Topology Protection
Authors: Eli Chien
Wei-Ning Chen
Chao Pan
Pan Li
Ayfer Ozgur
Olgica Milenkovic
Venue: NeurIPS 2023 poster (2023)
Keywords: Graph Neural Networks
Differential Privacy
Multigranular Topology Protection
TL;DR: We propose Graph Differential Privacy (GDP) framework and decoupled graph convolution for multigranular topology privacy protection.

Abstract: Graph Neural Networks (GNNs) have proven to be highly effective in solving real-world learning problems that involve graph-structured data. However, GNNs can also inadvertently expose sensitive user information and interactions through their model predictions. To address these privacy concerns, Differential Privacy (DP) protocols are employed to control the trade-off between provable privacy protection and model utility. Applying standard DP approaches to GNNs directly is not advisable due to two main reasons. First, the prediction of node labels, which relies on neighboring node attributes through graph convolutions, can lead to privacy leakage. Second, in practical applications, the privacy requirements for node attributes and graph topology may differ. In the latter setting, existing DP-GNN models fail to provide multigranular trade-offs between graph topology privacy, node attribute privacy, and GNN utility. To address both limitations, we propose a new framework termed Graph Differential Privacy (GDP), specifically tailored to graph learning. GDP ensures both provably private model parameters as well as private predictions. Additionally, we describe a novel unified notion of graph dataset adjacency to analyze the properties of GDP for different levels of graph topology privacy. Our findings reveal that DP-GNNs, which rely on graph convolutions, not only fail to meet the requirements for multigranular graph topology privacy but also necessitate the injection of DP noise that scales at least linearly with the maximum node degree. In contrast, our proposed Differentially Private Decoupled Graph Convolutions (DPDGCs) represent a more flexible and efficient alternative to graph convolutions that still provides the necessary guarantees of GDP. To validate our approach, we conducted extensive experiments on seven node classification benchmarking and illustrative synthetic datasets. The results demonstrate that DPDGCs significantly outperform existing DP-GNNs in terms of privacy-utility trade-offs.

Differentially Private Decoupled Graph Convolutions for Multigranular Topology Protection
Eli Chien" UIUC & GaTech
Wei-Ning Chen" Stanford University wnchen@stanfore www.aanforreeeeeeoooooooo
Chao Pan' UIUC chaopan2@i11inois.eed
Jchien30illinois edu
i schee6@@aatecheddi
Pan Li
Ayfer Özgür Stanford University aozgur@stanf www.urrstaaffddd.e......
Olgica Milenkovic UIUC mi milenkovéillinois edu
GaTech
panli@gatech. edu
Abstract
Graph Neural Networks (GNNs) have proven be highly effective in solving real-world learning problems that involve graph-structured data. However, GNNs can also inadvertently expose sensitive user information and interactions through their model predictions. To address these privacy concerns, Differential Privacy (DP) protocols are employed to control the trade-off between provable privacy protection and model utility. Applying standard DP approaches to GNNs directly advisable due two main reasons. First, the prediction of node labels, which relies on neighboring node attributes through graph convolutions, can lead to privacy leakage. Second, practical applications, the privacy requirements for node attributes and graph topology may differ. In the latter setting, existing DP-GNN models fail provide multigranular trade-offs between graph topology privacy, node attribute privacy, and GNN utility. To address both limitations, we propose a new framework termed Graph Differential Privacy (GDP), specifically tailored to graph learning. GDP ensures both provably private model parameters as well as private predictions. Additionally, we describe a novel unified notion graph dataset adjacency to analyze the properties of GDP for different levels of graph topology privacy. Our findings reveal that DP-GNNs, which rely on graph convolutions, not only fail meet the requirements for multigranular graph topol- ogy privacy but also necessitate the injection of DP noise that scales at least linearly with the maximum node degree. In contrast, our proposed Differentially Private Decoupled Graph Convolutions (DPDGCs) represent more flexible and efficient alternative to graph convolutions that still provides the necessary guarantees of GDP. To validate our approach, we conducted extensive experiments on seven node classification benchmarking and illustrative synthetic datasets. The results demonstrate that DPDGCs significantly outperform existing DP-GNNs in terms of privacy-utilip trade-offs. Our code is publicly available
Introduction
Graph learning methods, such as Graph Neural Networks (GNNs) 155. are indispensable learning tools due to the ubiquity of graph-structured data and their importance in solving real-world problems
$ Equual contribution.
http::///gthhbb..c//ththppaaapp gnn
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Graph dataset
k-neighbor-leve (K 2)
Private (X. F]
Non-private (x. F
Private/Non-privan node attributes
X
[new)
No privacy
r
(new)
Edge-level
D
D
(new)
(new)
Node-level
(new)
(a)
(b)
(c)
Standard graph convolution (AX)
Decoupled graph convolution (AW]IX)
GDP
Noise s²
Coundan mectenam
Bax
Read anjectionn
N(D,s*)
L sup |IAX A 1'Xl/rllF
Trals
Noise S²
x
Z
No trade-off with Need bounded degree
41. max
Carentte
Sow eorecal and
MC0 5*)
sup
|[(A w')Whrll
k
X
(d)
(e)
Figure 1: Top: (a) Illustration of training graph dataset. In the example, the graph involves 6 nodes and does not contain self-loops. Nodes and are left unlabeled the training dataset 'D. (b) An illustration of our novel notion of k-neighbor-level graph dataset adjacency, with/without node attributes privacy. Red colors indicate entries that are to replaced in the adjacent dataset D' with respect to node (c) All possible combinations of graph topology and node attribute privacy requirements under our k-neighbor definition. Bold letters indicate settings not covered by prior literature. Bottom: Illustration of a (d) standard graph convolution and (e) our decoupled graph convolution design. For decoupled graph convolution, we concatenate the node embedding with node feature X to obtain the final prediction. See Figure 2 for more detailed description of the DPDGC model. Note that the required noise for standard graph convolution is independent of k. and hence cannot leverage the intrinsic privacy-utility trade-off in k-neighbor level adjacency.
arising in recommendation systems (6) bioinformatics 7 and fraud detection 8 Graph datasets, which typically comprise records of users (i.e., node attributes) and their interaction patterns (i.e., graph topology), often contain sensitive information. For example, financial graph datasets contain sensitive financial records and transfer logs between accounts 10) Online review system graphs comprise information about customer identities and co-purchase records [T]]
Given the sensitive nature of graph datasets, it is paramount ensure that learned models do not reveal information about user attributes or interactions. Unprotected learning models can inadvertently leak information about the training data even if the data itself is not disclosed to the public [2] Differential privacy (DP) has been used as the gold standard for rigorous quantification of "privacy leakage" of learning algorithm, from that of "adjacent" datasets [33. Classical DP approaches focus on DP guarantees for model weights (i.e,, DP-SGD (14) when only node attributes are present. This suffices to ensure DP of model predictions for standard classification settings when no graph structure is available. In such settings, the prediction of a is merely function of model weights and its own attributes. This assumption does not hold for graph learning methods in general, since graph convolution, by coupling node attributes and topology information, also leverages information from neighboring users the prediction stage. Furthermore. in practice, there are usually different privacy level requirements for node attributes and graph topology. For example, customer identities can be more sensitive compared to co-purchase records in an online review system. A fine-grained trade-off between graph topology privacy, node attribute privacy, and GNN utility necessary consideration overlooked by prior literature. These require rethinking how to achieve adequate DP for GNNs.
it ensures that the output of a training algorithm remains indistinguishable
Our contributions. We perform formal analysis of Graph Differential Privacy (GDP), ensuring that both the GNN weights and node predictions are DP. The key idea of GDP is to protect the privacy of all nodes the prediction step except those nodes whose labels are be predicted, as users who want to know their own predictions must have access to their own data. While this requirement sounds straightforward, it leads to challenges in the analysis due to the interaction between the graph structure and node attributes. To account for different degrees of graph topology and node attribute privacy, we introduce the notion of k-neighbor- datasct adjacency (see Figure (a-c)). It not only unifies previous edge- and node-level adjacency
adjacency which generalizes the notion of graph

---

definitions [15 [6
but also allows for different granularities of privacy protection for the graph topology. Our notion of k-neighbor-level adjacency can be used establish the trade-offs among graph topology privacy, node attribute privacy, and model utility.
The GDP analysis to follow demonstrates that the standard graph convolution operation has two fundamental drawbacks. First, it can be shown that the required DP noise level for a standard graph convolution does not decay even when there are no privacy constraints on the graph topology. Hence, the standard graph convolution design fails to exploit the fine-grained trade-off pertaining to graph topology privacy. Second, the required DP noise variance for standard graph convolutions grows at least linearly with the maximum node degree [17), which leads to suboptimal utility. To mitigate these drawbacks, we propose the Differentially Private Decoupled Graph Convolution (DPDGC) design that provably enables the aforementioned trade-off and makes DP noise variance independent of the maximum node degree. Our key idea to prevent direct neighborhood aggregation of (potentially transformed) node features so that the GDP guarantee can be improved via the DP composition theorem (see Figure (e)) This insight sheds new light on the benefits of decoupled graph convolutions, and may lead to further advances in GDP-aware designs. We conclude by demonstrating excellent privacy-utility trade-offs of DPDGC for different GDP settings via extensive experiments on seven node classification benchmarking datasets and synthetic datasets generated using the contextual stochastic block model (cSBM) [18 19].
Missing proofs and details are relegated to the Appendix due to space limitations.
2 Related works
DP for neural networks and classical graph privacy analysis. Providing rigorous privacy guar- antees for MI. methods is a problem of significant interest [3) where DP gradient descent algorithms and their variants were studied in (14). On the other hand, classical graph analysis with DP guarantees has been extensively studied previously. For example, problems of releasing graphs or their statistics with DP guarantees were examined in (24) and (25). In different setting, [26) investigated the problem of estimating degree distributions with DP guarantees, while (27) studied DP PageRank algorithms. The interested reader is referred to the survey [28] for a more comprehensive list of references.
DP-GNNs. Several attempts were made to establish formal GNN privacy guarantees via DP. 29 propose a strategy achieving edge DP by privatizing the graph structure (i.e., perturbing the topology) before feeding it into GNNs. [15) describe a node DP approach for training general GNNs via extensions of DP-SGD, while (30] suggests combine DP PageRank with DP-SGD GNN training. These approaches can only guarantee DP model weights and fail to provide DP model predictions. [31] study GNNs for graph classification instead of node classification. 32 propose node-level private GNNs via the Private Aggregation of Teacher Ensembles framework 33 which is a different setting
than ours. [17] are the first to point out the importance of ensuring DP of GNN predictions, and to
propose the GAP model for this purpose. Still, their work did not include a formal GDP analysis nor a study of the benefits of decoupled graph convolution designs.
3 Preliminaries
Notation. We reserve bold-font capital letters (c.g., S) for matrices and bold-font lowercase letters (c.g.. s) for vectors. We use S, to denote the 2th row of S, S to denote the submatrix of S excluding its 7th row and Si to denote the entry of S in the ith row and jth column. Furthermore, G (V,E) stands for a directed graph with node set V = [r|] of size n and edge set E. For simplicity, we assume that the graphs do not have self-loops. Standardly, we use A to denote the corresponding adjacency matrix. Without loss of generality, we also assume a labeling such that the first m nodes are labeled (mm) and the remaining [n]] \ [mra] nodes are subjects of prediction. The feature matrix is denoted by X E R where F stands for the feature vector dimension. For a C-class node classification problem, the training labels are summarized in Y E {0. 1 where each row of Y is one-hot vector. We reserve ||- for the lg norm and ||. || for the Frobenius norm. We use || for concatenation. Throughout the paper, we let M(u; D) stand for the (graph) learning algorithm that leverages D to generate label predictions for a node u in [n] \ [m]. We assume the graph model outputs both its leamned weights W and its label prediction Y. (i.e., (Y., W) M(v; D)).
3

---

Node classification. We focus on the transductive node classification problem. The training data is of the form = (X, A), and this information reused at the inference stage. Due to data reusing, it is important to specify which node is subject to prediction in the graph learning mechanism M(,; D). Requiring that all of 'D is private inevitably leads to noninformative predictions. It is therefore reasonable to only protect the information of 'D pertaining to the node that is not subject to prediction. We refer interested readers to Appendix [or discussion on how our analysis generalizes to inductive settings.
3.1 Differential Privacy (DP)
We start with a formal definition of (e, -ddffferrett privacy (DP) 13
Definition 3.1 (Differential Privacy). For e, 8 2 O, a randomized algorithm A satisfies (e, 6DDP condition for all adjacent datasets DD DD' that differ in one record, and all S in the range of A.
Pr (A(D) E S) S E Pr (A(D') E ES)+ +
Note that the standard DP definition does not depend on the choice of nodes to be predicted. Yet, such a dependence is critical for the graph learning setting and constitutes the key difference between Definition 3.I and our definition of GDP in Section 4 We also make use of Rényi DP in order to facilitate privacy accounting. A given (a, Ré-ééni DP guarantee can be convert to a (c. 6DD guarantee via the conversion lemma (34 (see also Appendix [F)
Definition 3.2 (Rényi Differential Privacy). Consider a randomized algorithm A that takes D as its imput. The algorithm A is said to be (a, --éényi DP for every pair of adjacent datasets D and D', one has D (A(D)]] S y, where (-1-1l-) denotes the Rényi divergence of order az
1
[ (P(()) "))
(x(XI
a - log E
with X Pand Y ~ Q.
4 Graph Differential Privacy
We provide next a formal definition of Graph Differential Privacy (GDP), Recall that in this case keeping the entire training data D private (as in standard DP definition, i.e., Definition 3.1 is problematic since it inevitably leads to noninformative model predictions. This follows since in such a setting the prediction Y, fully depends on D. This is unlike the case for standard classification where the test label predictions are formed via access additional test data that not subject to privacy constraints. Our key idea is to protect the privacy of all but the node v being predicted, as users who query their own predictions should clearly have access to their own features and neighbors.
We start by describing our notion of k- k-neighbor- remainder of the paper, we use denote the replaced node.
adjacent graph datasets. Throughout the
Definition 4.1 (K-neighbor-level adjacency). Two graph datasets D and D' are said to be k-neighhor-
level adjacent, which is denoted by DD NE D', Df can be obtained by replacing: 1) the th node feature X, with X E Rd, 2) the thth node label Y, with Y 10, 1) [m]] and 3) replacing l entries in th row and column of A respectively excluding Arr-
Our Definition 4.1 unifies previous graph dataset adjacency notions such as edge- and node-level adjacency. For example, if drop 1). 2) (i.e., keep the node attributes unchanged), and set k 1 for replacement in a row only, our Definition 4.1 recovers that of edge-level adjacency (29]. If 1: = n, we recover the definition of node-level adjacency [15 17 37 38). Edge-Ievel adjacency may be too weak of a privacy concept since it does not protect the privacy of node attributes. At the same time, node-level adjacency may also be too restrictive since it allows arbitrary replacement of an entire node neighborhood. In practice, there are cases where node features and labels carry more sensitive information when compared to the graph topology. It is desirable to allow practitioners to decide the granularity of privacy for the graph structure A while maintaining the privacy of X and Y. This motivates our new and extended k-neighbor-level adjacency definition. Note that the parameter serves as new graph-specific privacy parameter similar to, but independent of, and ő in DP. Our k- k-neighbor definition can shed light on how a private graph learning design relies on the privacy of A controlled by the parameter A and is discussed in more detail in Section 5 We also provide

---

No trwining
Goussion mechanism
Y.
Necmm
GAP
A
((O.s²)
DP-MLPx
H
H
(
Normal
(
X
H
PMA
DP-MLP/
Y
Row
DPDGC
Trai:
OP-Emb
Gamerte
Row normal and Gasssian mechariam
Wi14)
((O.s*))
DP-MLPw
DP-MLP,
Y
DP-MLPX
GAP information flow
DPDGC information flow (A.Y) (z, w b). (x. z. (P. wú,, wo0, w0o)
(X,Y) (H(0), w (H .A) (z. (P, w(n
Figure 2: Illustration of the GAP and DPDGC (top) architectures and their corresponding information flow (bottom). Green modules indicate DP-MLPs trained with a DP-optimizer (14). Blue modules are non-trainable modules. We use red frames to point to designs with DP guarantees (i.e., DP-Emb and PMA 117.. Trainable weights are denoted by ((A) and b for the DP-Emb module. The black dashed arrow indicates modules that are pretrained separately and the outputs are cached.
detailed discussion on the privacy meaning of k in Appendix J In practice, the parameter k also offers unique trade-off between utility and graph structure privacy while preserving the same privacy guarantees of the node features X and labels Y (i.e., it is independent of the DP parameters e, 6).
We now provide formal definition of Graph Differential Privacy (GDP). Unless otherwise specified, we use the superscript to refer to entities with respect to the adjacent dataset D'.
Definition 4.2 (Graph Differential Privacy). A graph model M is said to be edge (node, k-neighbor) (a, GDD for any v E [n]] \ [mn, for all E D' (D N D', D No D'), such that r + v, one has: D. (MM,; DillMMee; D')) S where is the index of the replaced node in the dataset puir D,D'' D'.
The key difference between our definition and that of standard DP is that instead of requiring the Rényi divergence bound hold for all possible (D, D') pairs, we only require it hold for pairs for which the replaced node does not require prediction (i.e., the Rényi divergence has to be bounded for different sets of adjacent graph dataset pairs that depend on At high level, Definition 4.2 ensures that even if an adversary obtains the trained weights and the predictions of node v, it cannot infer information about the remaining nodes.
v). This is crucial since in this case,
5 Graph learning methods with GDP guarantees
We first perform the GDP analysis for GAP 177. the state-of-the-art DP-GNN with standard graph
convolution design in Section [3.1] In the same section, issues with standard graph convolutions under k-neighbor GDP settings discussed as well. We then proceed introduce Differentially Private Decoupled Graph Convolution (DPDGC), model with the decoupled graph convolution design that resolves all issues with GDP guarantees. DPDGC is motivated by the LINKX model (39 which offers excellent performance on heterophilic graphs in a non-private setting. These models are depicted in Figure 2, with the pseudocodes available in Appendix L All missing formal statements and proofs are relegated to Appendix B E We also defer the analysis of the simper edge GDP
scenario Appendix G and formal GDP guarantees to Appendix
5.1 GDP guarantees of GAP and issues of standard graph convolution
GAP training and inference. We first describe the training process of GAP depicted in Figure 2 GAP first pretrains the node feature encoder DP-MLPx separately from the DP-optimizer. The row-normalized node embedding (") is generated and cached after the pretraining of DP-MLP
Then the privatized L multi-hop results (H()) =i are generated by applying the PMA module [17
The intermediate node embedding Z constructed by the concatenation of (H()) H is then cached.
5

---

Finally, node classifier DP-MLP, is trained with imput Z. At the inference stage, node predictions are obtained by the cached embedding Z with the trained DP-MLP,.
Node and k-neighbor GDP. We assume that the out-degree (column-sum) of A is bounded from above by D. Note that prior works 17] also require this assumption. To meet this constraint in practice, preprocessing of the form of graph subsampling is needed, which causes additional data distortion. The first step of proving tight GDP guarantees for GAP is to ensure the cached embedding
Z to be DP, except for the replaced node r. We start with describing the PMA (17) module:
Input: HD) E T
Output: H = row-normalization A AHD ( + N);
(I)
where N E Bax is Gaussian noise matrix whose entries are i.i.d. zero mean Gaussian random variables with standard deviation 8.
Theorem 5.1. For any a > and N D' (or D Ny D'), assume the trained parameter W(X) of DP-MLPx in GAP satisfies D, Da ( by D. Let the replaced node index be and let Zi be the matrix Z with the 7 row excluded. Then
S 71 and that both A, A' have out-degree bounded
the embedding Z in GAP satisfies Da (Z Z S 71 + 25
4DLa
Sketch of the proof: We start by showing that for any D N D. D. (. S
71 +
4Do
25
which done by examining the sensitivity of [AH*] 1y- For simplicity, we abbreviate H))) to
H. Note that [H - (A'H' | 2 = EKEniMr [[(HH] (A'H',,I"" We find that there are three cases of that contribute to a nonzero norm in the summation. Let ((r) and (r)r) denote the out-neighbor node sets of r with respect to A and A', respectively (i.e., N(r) = =fi: A.r 1)). The three cases are: (1) i E (() \ (r),,, (2) i E
(r)r) \ (r). and (3) E (r) n (r). For case (1) and (2), || [AH] [A'H'), = 1 due to H and H' being row- now-normalized. For case (3), we have [AH], A'H = HH, H < 2. Since the out-degree is upper bounded by D. we know that max(|N (r))) S D. The worst case arises for (r() n (r)) = D (i.e., shares common neighbors). Thus the sensitivity equals 2vD (i.e., D of case (3)) which leads to the term 4Da in the divergence bound. By applying 28a W(),, we can prove that D2 (H (H(") Sin 71 + 4Da For the L-hop result Zi,,, one can apply 2
DP composition theorem [4 and the assumption on
Ar
DP composition theorem as part of an induction. For the case of k-neighbor-level adjacency, the worst case scenario still arises for [r(r) n (r)
D for any k 2 0. Thus, the same result holds for the case k-neighbor-level adjacency for all & 2 O. Note that the above analysis/result is tight, with the worst case arising when H, -H, and ( (N()))
D.
Regarding the assumption W(X), it can be met by invoking a standard DP-optimizer result [14], where 71 depends on the noise multiplier of the DP-optimizer. By using further the DP composition can conclude that the weights of the DP-MLP,
theorem and standard DP-optimizer results, module are also DP. At the inference stage, since our GDP definition requires that r * v (i.c., nodes to be predicted are not subject to replacement in adjacent graph dataset pairs), one only needs to ensure that Z - instead of the entire Z - to be DP. This establishes the node and k-neighbor GDP guarantees for GAP (Corollary HH.5).
Surprisingly, the resulting divergence bound does not depend on the parameter ie for the k-neighbor GDP setting. It implies that the privacy noise scale required by GAP is the same even when k much smaller than D, or even equal to zero. At first, this result seems counter-intuitive but can be understood as follows. By replacing H, with an all-zeros row, it becomes impossible to get information about the th row and column of A through [AH])r- Therefore, DP-GNNs based on standard graph convolution designs such as GAP cannot exploit the intrinsic privacy-utility trade-offss adjacency constraints. Furthermore, the resulting divergence bound
induced by k-neighbor-leve grows linearly to the value of the maximum degree D. Consequently, one has to preprocess the graph so that the maximum degree is upper-bounded by a pre-defined value D, which inevitably causes graph information distortion.
Based on our analysis, we observe that the issue arises from the graph convolution operation AH, where both the graph structure (topology) A and transformed node feature H change simultaneously to A' and H' on D'. As result, rows corresponding to case (3) contribute 2 to the norm bound, which indicates greater privacy leakage (sensitivity). This motivates us to decouple the graph convolution

---

so that there are no products of A and H. to work with, which motivates introducing our DPDGC model discussed in the next section.
Remark 5.2. While the proof of Theorem 5.1 is mainly inspired by the proof in [17), it has several technical differences. First, the analysis in [17] asserts that the entire Z is DP (see Lemma 3 in (17)). In contrast, only ensure that ,r is DP. This is crucial as [[AH,
2D in the worst-case sensitivity analysis, which leads to ( in the divergence bound. Also, while
[A'''),
leverage standard DP composition theorems [40] in the sketch of proof similar to (17) for the sake of simplicity, we argue in Appendix B that is more appropriate use our novel generalized adaptive composition theorem (Theorem B. for a rigorous GDP analysis.
5.2
GDP guarantees of DPDGC and benefits of decoupled graph convolution
DPDGC training and inference. We first describe the training process of DPDGC depicted in We first pretrain the DP-Emb module separately and freeze its weights (W(A), b). Then we generate the intermediate embedding Z and cache it. Finally, we use (X, Z, Y) to train the remaining modules in an end-to-end fashion. At the inference stage, the node prediction is obtained by (X, Z) and the trained weights. See the pseudocode Appendix D for further details.
Figure 2
Node k-neighbor GDP guarantees. For DPDGC, we only need the bounded out-degree assumption for node GDP but not k-neighbor GDP. The key idea of the GDP guarantee proof to ensure the cached embedding Z to be DP, except for the replaced node r. We start by introducing the DP-Emb module in DPDGC, which guarantees both the model weight (W(A), b) and 2,, to be DP:
Training: (()) (AA((A) + b)R Generate Z: Z (W +b-N,
(2)
where ((A) E Raxh and E T are learnable weights. Here, R E R is a random but fixed projection head of hidden dimension h, (-) is some nonlinear activation function, and N E R is a Gaussian noise matrix whose entries are i.i.d. zero mean Gaussian random variables with standard deviation s. Importantly, we constraint (44) to be row-normalized, which is critical in proving Zrr DP. In what follows, we focus on privatizing Zr and the GDP guarantee for the overall model then follows by applying DP composition theorem [40].
Theorem 5.3. For any a > 1 and 'D N. DD' assume that Da b)I((W(A)) .b)) S n and both A, A' have out- degree bounded by D. Let the replaced node index be and let Z, be the matrix Z
with the thh row excluded. Then the embedding Z. in DPDGC satisfies D (Z (Z 1Z S 7 + 2
2Da
Theorem 5.4. For any D Ne D', assume that Da((W()),))((WW b)) S 71 and both A. Let the replaced node index be and let Zry be the matrix with the th row excluded. For any a > the embedding Z in DPDGC satisfies Da Zr S m +
koy
28
Sketch of the proof: For any D N D' (D No D'), we examine [AW(A]] A'W''.
i
[n]] \. Mr.. The worst case row norm equals 1 for cases (1) and (2) (defined in the proof of Theorem 5.1 since (AA) is row-normalized. The main difference to the proof in Section 5.1 the case (3), where [A
O, since A, A, for i E (r) (r).. As result, the worst case arises for (r) (r) = 0 and there are at most 2D (k) rows of cases (1) and (2). As result, the sensitivity of Z is 22D (vh) which leads to the term 2Dg (2 in the divergence bound. Once more, our sensitivity bound can be shown to be tight, with the worst case as described above.
[AW(a)]
The key improvement, when compared to GAP, arises from using (W(A) instead of AH. In the case of (A) being DP, the sensitivity analysis only requires one to consider the difference between (W(A) and A' (A)(A) of two adjacent graph datasets, D and D'. In contrast, for GAP, the sensitivity analysis of AH requires taking both A and H into account since both can vary when the underlying dataset changes. Note that even if DP-MLPx is trained via DP-optimizer, H is not DP since is dependent on the weights of DP-MLPX x and the node feature X.
The assumption on (A( b) can be met by applying a standard DP-optimizer with a group size [41 of D + (k: + 1), where Ti depends on the noise multiplier of the DP-optimizer. This follows from the fact that the out-degree is bounded by D for node GDP or from the definition of k-neighbor-level adjacency, since replacing one node can affect at most D (k) neighbors. By further applying the DP
7

---

Table 1: Dataset statistics. Datasets are sorted by homophily.
Squirel
Chamelcon
Facebook
Pubmed
Computers
Cora
Photo
nodes
5,201
2,277
26,406
19.717
13,471
2,708
7,535
edges
216,933
36,051
2,117,924
88,648
491,722
10,556
238.162
features
2,089
2,325
501
500
767
1,433
745
classes
5
10
odge density
0.0160
0.0139
0.0061
0,0005
0.0054
0.0029
0.0084
homophily
0.0254
0,0620
0.3687
0.6641
0.7002
0.7657
0.7722
composition theorem and the standard DP-optimizer result, we arrive at the node (k-neighbor) GDP
guarantees for DPDGC (see Corollary H.2 H.3
Compared to GAP, DPDGC requires significantly lower DP noise whenever < D. can thus ensure graph topology privacy-utility trade-off' that is not possible with GAP. Furthermore, the divergence bound for DPDGC is independent of the maximum degree within the k-neighbor-level adjacency setting. Hence, DPDGC does not require preprocessing the graph, which alleviates the issue of added graph distortion.
6 Experiments
We test graph learning models that can achieve GDP guarantees under various settings, including nonprivate, edge-level, k-neighbor-level (N&) for & (1,5, 25), and node-level. Note that all node GDP methods require the bounded out-degree constraint. We follow [55 17 to subsample the graph to satisfy this constraint.
Methods. In addition DPDGC and GAP introduced in Section we also test (DP-)MLP and several DP-GNN baselines that can achieve GDP guarantees. including RandEdge+SAGE (29 and DP-SAGE [5] for edge and node GDP, respectively. The RandEdge+SAGE approach privatizes the adjacency matrix directly via randomized response (29) and feeds it to GraphSAGE (3), standard GNN backbone. The DP-SAGE approach trains the GraphSAGE model with the strategy proposed in [15) so that the weights are DP. To further ensure that the predictions are DP as well, we follow the strategy (17) to add perturbations directly at the output layer during inference. For each GDP setting, we specity to indicate that all methods satisfy GDP with privacy budget (e, d) according #modes depending on the GDP
to Lemma F.1 Note that is set to be smaller than either #edges or
setting. Addition experimental details are deferred to Appendix K
Datasets. We test 7 benchmark datasets available from either Pytorch Geometric library [42] or prior works. These datasets include the social network Facebook (43), citation networks Cora and Pubmed 45). Amazon co-purchase networks Photo and Computers (46), and Wikipedia networks Squirrel and Chameleon (47). The edge density equals 2/g1/(n x (n (1)- while the
formal definition of the homophily measure is relegated to Appendix
Results. We examine the performance of each model under differrnt GDP settings, including the nonprivate case. The results are summarized in Table For the edge GDP setting, we observe that DPDGC achieves the best performance on heterophilic datasets, while on par with GAP on most homophilic datasets. Surprisingly, for the node GDP setting, we find that DP-MLP achieves the best performance on four datasets. This indicates that for some datasets, the benefits of graph information cannot compensate for the utility loss induced by privacy noise that protects the graph information (for tested private graph learning methods). challenging and highlights the importance of investigating the k-neighbor GDP setting. For the k-neighbor GDP setting, we can see that indeed DPDGC has a much better utility for performance gradually decreases as l grows. The required privacy noise scale is the same for GAP and DP-MLP for any k: this phenomenon is discussed in more depth in Section DPDGC starts to outperform MP-MLP on Photo and Computers for sufficiently small k. which demonstrates the unique utility- topoloy privacy trade-offs of our method that cannot be achieved via models with standard graph convolution design such as GAP. However, DPDGC still underperforms compared to DP-MLP on Cora and Pubmed.
a result, achieving node GDP effectively highly
and the
Experiments on synthetic contextual stochastic block models (cSBMs). In order to test our conjecture that DP-MI.P can only outperform DPDGC when the graph information "too weak," conduct experiment involving cSBMs [8 following setup similar to that reported in [9
8

---

Table 2: Test accuracy (%) with 95% confidence interval. A bold font indicates the best performance one can achieve under the same GDP guarantee. Underlined entries indicate a result within the confidence interval when compared to the best possible. Note that for the k- k-neighorr (N₂) GDP setting, the results of GAP and DP-MLP are identical to those of node GDP.
Squirel
Chameleon
Facebook
Pubmed
Computers
Cora
Photo
DPDGC
79,92 0.26
79.24 0.54
86.06 1 0.24
88.34 1
92.27
0.15
82.4
0.83
94,98 1
none poivace
GAP
36,86 + 1.35
50.35
+ 1.37
79.52
+ 0.24
89.75 + 0,12
91.05
+ 0.16
86.53 + 0,46
95.13 = 0.16
SAGE
35.47
0.58
41.61
0.86
84.62
= 0.13
88.17
+ 0.98
0.22
84.19 = 0.76
94.05 + 0.38
MLP
34.14 0.77
46.78
+ 1.39
51.16
4 0.16
87.25
+ 0.19
85.27
= 0.28
76.48 = 0.91
91.35
= 0.22
DPDGC
38.18
1.48
53.83
1.11
62.04 4:
88.59 +
87.74
0.26
77.71
0.95
92.59 1:
edge
1
GAP
35.15 1: 0.47
49.47
+: 0.88
69.75 1 0.44
87.79 1 0.22
87.74
1: 0.20
76.95
+: 0.90
92.94 1 0.36
RandEdge+SAGE
19.79 : 0.69
21.70
1.23
25.27
+ 2.00
87.88 + 0.18
48.44
1.48
59.95
1.98
46.42 + 0.55
DP-MLP
34.14 0.77
46.78 + 1.39
51.16 + 0.16
87.25
+ 0.19
85.27
0.28
76.48 = 0.91
91.35
0.22
< 16
DPDGC
42.71 1.43
48.63
1.78
80.94 +:
84.33
0.29
59.98
0.81
88.38 0.44
M1
GAP
33.82 1. 0.60
38
1. 0.59
$1.57 1 0.28
85.28 1 0.14
77.50
1: 0.20
54.36 1 1.14
81.27 1 0.31
DP-MPP
34,46 1.09
38. 19 + 1.97
50.12 -: 0.22
85.72 +
80.01
0.37
64.29
0.80
85.61 + 0.42
16
DPDGC
41,00 1: 1.19
47.22
1,90
76.84 1: 0.36
84.31
1 0.46
80.60
0.44
59.56 1. 0.97
87.02 1: 0.49
N
=
GAP
0.60
38.68-5 0.59
51.57 +
77.50
0.20
54.36
L.14
81,27
DP MLP
34,46 1. 1.09
38.19 1 1.97
50.12 1: 0.22
85.72 1 0.11
80.01
0.37
64.29
0.80
85.61
1: 0.42
16
DPDGC
40,51 0.85
46.32 +: 1.87
68,66 + 0.32
84.27 + 0.38
78.25 + 0.31
59.26 + 0.87
84.82 + 0.54
NAG
GAP
33.82 0.60
38 68
+ 0.59
$1.57 + 0.28
85.28 + 0.14
77,50
+ 0.20
54.36 = 1.14
81,27 = 0.31
DP-MLP
34:46 1.09
38.19
1.97
50.12 +
85.72
0.37 80.01
64.29
0,80
85.61
DPDGC
36.17 0.62
46.43 1.21
56.65 + 0.64
84.55 + 0.32
76.62
0.47
58.97
1.05
82.15 + 0.54
16
mode
GAP
33.82 + 0.60
38.68
0.59
51.57 + 0.28
85,28
+ 0.14
77.50
+1.00:00 0.20
54.36
1.14
81.27
= 0.31
DP-SAGE
19.81 + 0.99
20.96 + 1.27
32.15 + 0.78
39.68
+ 0.70
39. 13 + 0.52
15.86
1.55
31.41
- 0.93
DP-MLP
34:46 1.09
38.19
1.97
50.12 + 0.22
85.72
0.11
80.01
0.37
64.29
0,80
85.61
0.42
Edgee GDP, Facebonic
Node and N2 CDP, Paceboos
Nu-reighhrr CDP, 16, Comoutenn
CSRM soper mAEE, < 1.6
08
+15
-0.
3.0
Figure 3: (a): Trade-off between utility and the parameter for edge-GDP on the Facebook dataset. (b): Trade-off between utility and the parameter for node and k-neighbor (N₂)) GDP the Facebook dataset. (c): Trade-off between utility and the parameter & for k-neighbor GDP. (d): The cSBM experiment, which shows that when the graph information is strong enough (i.e., [Ø] is large enough), DPDGC can indeed outperform DP-MLP.
The parameter e E [-1,, 1] indicates the "strength of information" in the graph topology (lo) + 1) and the node features [ - 0). The sign of ø indicates whether the graph topology is homophilic (+) or heterophilic (-). See Appendix K for full details about the experiment setting. The result is depicted in Figure (d). When (Ø] is small, DP-MLP outperforms DPDGC. In contrast, when (ø) is sufficiently large (1.e., the information in the graph topology is strong enough), DPDGC outperforms MP-MLP. This experiment suggests that one should not leverage DP- when the graph topology information too weak, as the cost of privatizing the graph topology information is too high.
Utility-privan trade-off. Lastly, we examine the utility-privacy trade-off for different GDP settings in greater detail. In Figure (left) we show that DPDGC starts to outperform GAP for larger privacy budgets- - 2 in the edge GDP setting. This figure also shows the advantage of GAP when the privacy budget is small for edge GDP. Whether more advanced decoupled graph convolution design can outperform GAP in this regime is left for future studies. Figure 3 (middle) reports the trade-offs between utility and the privacy budget of all methods under dilferent GDP settings (node, N1. N₁. N2s) for the Facebook dataset. We report the trade-off between utility and k under k-neighbor GDP with c 16 for the Computer dataset in Figure 3 (right). Adopting the k-neighbor GDP definition allows us to control the privacy of the graph structure while maintaining the same privacy guarantee on node features and labels. This in contrast with changing the parameters (e, 8) directly as they control the privacy of the entire dataset. DPDGC along with the k-neighbor GDP definitions hence allows a more fine- grained privacy control of the graph topology as needed in different practical applications.
9

---

7 Conclusions
We performed an analysis of a novel notion of Graph Differential Privacy (GDP), specifically tailored to graph learning settings. Our analysis established theoretical privacy guarantees for both model weights and predictions. In addition, to offer multigranular protection for the graph topology, we introduced the concept of k-neighbor-level adjacency, which is a relaxation of standard node-level adjacency. This allows for controlling the strength of privacy protection for node neighborhood information via a parameter k. The supporting GDP approach ensured flexible trade-off between utility and topology privacy for graph learning methods. The GDP analysis also revealed that standard graph convolution designs failed to offer this trade-off. To provably mitigate the problem associated with standard convolutions, we introduced Differentially Private Decoupled Graph Convolution (DPDGC), a model that comes with GDP guarantees. Extensive experiments conducted on seven node classification benchmark datasets and synthetic cSBM datasets demonstrated the superior privacy-utility trade-off's offered by DPDGC when compared existing DP-GNNs that rely on standard graph convolution designs.
Acknowledgments and Disclosure of Funding
and CCF-1956384. PL was supported by JPMC AI Research award. WC and AÔ were supported by NSF grant CCF-2213223. The authors would like to thank Sina Sajadmanesh for answering questions regarding the GAP method. The authors would like to thank the anonymous reviewers and area chair for their feedback and effort, which helped to significantly improve the manuscript.
EC, CP and OM were funded by NSF grants
References
[1] J. Bruna, W. Zaremba, A. Szlam, and Y. Leeun, "Spectral networks and locally connected networks on graphs," in International Conference on Learning Representations (ICLR2014), CBLS, April 2014, 2014, pp. http-opperreieey
[2] T. N. Kipf and M. Welling, "Semi-supervised classification with graph convolutional networks," " in International Conference on Learning Representations, 2017. [Online]. Available: https:/openeeviee.eeefffmmm SJJJS Yg!
[3] W. Hamilton, Z. Ying, and Leskovec, "Inductive representation learning on large graphs," Advances in neural information processing systems, vol. 30, 2017.
[4] P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Y. Bengio, "Graph attention networks." " in International Conference on Learning Representations, 2018. [Online]. Available: http::/oppeneevie.neeefooo Xitpf/rr
[5] J. Gilmer, S. S. Schoenholz, P. F. Riley, O. Vinyals, and G. E. Dahl, "Neural message passing for quantum chemistry," in International conference on machine learning. PMLR, 2017, pp. 1272-1272.
[6] R. Ying. R. Hc, K. Chen, P. Eksombatchai, W. L. Hamilton, and J. Leskovee, "Graph convolu- tional neural networks for web-scale recommender systems," in Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining, 2018. pp. 974-983.
[7] X.-M. Zhang, L. Liang, L. Liu, and M.-J. Tang, "Graph neural networks and their current applications in bioinformatics." Frontiers in Genetics, vol. 12, 2021.
[8] Z. Liu, Y. Dou, P. S. Yu, Y. Deng, and H. Peng, "Alleviating the inconsistency problem of applying graph neural network fraud detection," in Proceedings of the 43rd international ACM SIGIR conference on research and development in information retrieval, 2020, pp. 1569-1572.
[9] Z. Liu, C. Chen, X. Yang. J. Zhou, X. Li, and L. Song, "Heterogeneous graph neural networks for malicious account detection," " in Proceedings of the 27th ACM international conference on information and knowledge management, 2018, pp. 2077-2085.
[10] Q Zhong, Y. Liu, X. Ao, B. Hu, J. Feng, J. Tang, and Q. He, "Financial defaulter detection on online credit payment via multi-view attributed heterogeneous information network," in Proceedings of The Web Conference 2020, 2020, pp. 785-795.
10

---

[11] J. Wang, R. Wen, C. Wu, Y. Huang, and J. Xiong. "Fdgars: Fraudster detection via graph convolutional networks in online app review system." in Companion proceedings of the 2019 World Wide Web conference, 2019, pp. 310-316.
[12] N. Carlini, C. Liu, U. Erlingsson, J. Kos, and D. Song, "The secret sharer: Evaluating and testing unintended memorization in neural networks." in USENIX Security Symposium, vol. 267, 2019.
[13] C. Dwork, F. McSherry, K. Nissim, and A. Smith, "Calibrating noise to sensitivity in private data analysis." " in Theory of cryptography conference. Springer, 2006, pp. 265-284.
[14] M. Abadi, A. Chu, I. Goodfellow, H. B. McMahan, I. Mironov, K. Talwar, and I.. Zhang, "Deep learning with differential privacy," in Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, 2016, pp. 308-318.
[15] A. Daigavane. G. Madan. A. Sinha, A. G. Thakurta, G. Aggarwal, and P. Jain, "Node-level differentially private graph neural networks," arXiv preprint arXiv:2111.15221 2021.
[16) E. Chien, C. Pan, and O. Milenkovie, "Certified graph unlearning," arXiv preprint arXiv:2206.00 09140, 2022.
[17] S. Sajadmanesh, A. S. Shamsabadi, A. Bellet, and D. Gatica-Perez, "Gap: Differentially private graph neural networks with aggregation perturbation," in 32nd USENIX Security Symposium (USENIX Security 23). Anaheim, CA: USENIX Association, Aug. 2023.
[18] Y. Deshpande, S. Sen, A. Montanari, and E. Mossel, "Contextual stochastic block models," Advances in Neural Information Processing Systems, vol. 31, 2018.
[19] E. Chien, J. Peng, P. Li, and O. Milenkovic, "Adaptive universal generalized pagerank graph neural network," in International Conference on Learning Representations, 2021. [Online]. Available:
https://peenevieww.e///oomm "idni//iiiddddd
[20] A. D. Sarwate and K. Chaudhuri, "SSignal processing and machine learning with differential privacy: Algorithms and challenges for continuous data," IEEE signal processing magazine, vol. 30, no. 5, pp. 86 $6-94,2 2013.
[21] R. Bassily, A. Smith, and A. Thakurta, "Private empirical risk minimization: Efficient algorithms and tight error bounds," in 2014 IEEE 55th annual symposium on foundations of computer science. IEEE, 2014, pp. 464-473.
[22] R. Shokri and V. Shmatikov, "Privacy-preserving deep learning," Proceedings of the 22nd ACM SIGSAC conference computer and communications security, 2015, pp. 1310-1321.
[23] X. Wu, F. Li, A. Kumar, K. Chaudhuri, S. Jha, and J. Naughton, "Bolt-on differential privacy for scalable stochastic gradient descent-based analyties," in Proceedings of the 2017 ACM International Conference on Management of Data, 2017, pp. 1307-1322.
[24] A. Sala, X. Zhao, C. Wilson, Zheng, and B. Y. Zhao "Sharing graphs using differentially private graph models," in Proceedings of the 2011 ACM SIGCOMM conference Internet measurement conference, 2011, pp. 81-98.
[25] Z. Qin, T. Yu, Y. Yang, Khalil, X. Xiao, and K. Ren, "Generating synthetic decentralized social graphs with local differential privacy." in Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, 2017, pp. 425-438.
[26] M. Hay, C. Li, G. Miklau, and D. Jensen, "Accurate estimation of the degree distribution of private networks," in 2009 Ninth IEEE International Conference on Data Mining. IEFE, 2009,
pp. 169-178.
[27] A. Epasto, V. Mirrokni, B. Perozzi, A. Tsitsulin, and P. Zhong, "Differentially private graph learning via -ebiiivitt-bounded personalized pagerank," Advances in Neural Information Processing Systems, vol. 35, pp. 22617-22 627, 2022.
[28] 'T. Mueller, D. Usynin, J. C. Paetzold, Rueckert, and G. Kaissis, "Sok: Differential privacy on graph-structured data," arXiv preprint 2:XXi:2003.09005 2022.
[29] F. Wu, Y. Long, C. Zhang, and B. Li, "Linkteller: Recovering private edges from graph neural networks via influence analysis," in 2022 IEEE Symposium on Security and Privacy (SP). IEEE, 2022, pp. 2005-2024.
[30] Q. Zhang, J. Ma, Lou, C. Yang, and I.. Xiong, "Towards training graph neural networks with node-level differential privacy," arXiv preprint arXiv:2210.04444 2022.
11

---

[31] T. T. Mueller, J. C. Paetzold, C. Prabhakar, D. Usynin, D. Rueckert, and G. Kaissis, "Differ- entially private graph neural networks for whole-graph classification," " IEEE Transactions on Puttern Analysis and Machine Intelligence, 2022.
[32] I. E. Olatunji, T. Funke, and M. Khosla, "Relcasing graph neural networks with differential privacy guarantees," arXiv preprint ar arXiv:2 2021.
[33] N. Papernot, M. Abadi, U. Erlingsson, I. Goodfellow, and K. Talwar, "Semi-superrised knowl- edge transfer for deep learning from private training data," arXiv preprint arXiv:1610.05755, 2016.
[34] S. Asoodeh, J. Liao, F. P. Calmon, O. Kosut, and L. Sankar, "A better bound gives a hundred rounds: Enhanced privacy guarantees via f-divergences." in 2020 IEEE International Symposium on Information Theory (ISIT). IEEE, 2020, pp. 920-925.
[35] C. L. Canonne, G. Kamath, and T. Steinke, "The discrete gaussian for differential privacy." arXiv preprint 0rXiv:2004.00010 2020.
[36] M. Bun and T. Steinke, "Concentrated differential privacy: Simplifications, extensions, and lower bounds," " in Theory of Cryptography Conference. Springer, 2016, pp. 635-658.
[37] E. Chien, C. Pan, and O. Milenkovic, "Efficient model updates for approximate unlearning of graph-structured data," " in The Eleventh International Conference on Learning Representations, 2023. [Online]. Available: bttps://openreview.eees www.:://wwwumu/n/cccuuuuu......
[38] C. Pan, E. Chien, and O. Milenkovic, "Unlearning graph classifiers with limited data resources," " in Proceedings of the ACM Web Conference 2023, ser. WWW '23. New York,
NY. USA: Association for Computing Machinery, 2023, p. 716-726. [Online]. Available: 33777777335777733555
[39] D. Lim, F. Hohne, X. Li, S. L. Huang, V. Gupta, O. Bhalerao, and S. N. Lim, "Large scale learning on non-homophilous graphs: New benchmarks and strong simple methods," Advances in Neural Information Processing Systems, vol. 34, pp. 20 88788200000 902, 2021.
[40] I. Mironov, "Rényi differential privacy," in 2017 IEEE 30th Computer Security Foundations Symposium (CSF). IEEE, 2017, pp. 263-275.
[41] C. Dwork, A. Roth el al., "The algorithmic foundations of differential privacy," Foundations and Trends@ in Theoretical Computer Science, vol. 9, no. 3-4, pp. 21 1-14007, 2014.
[42] M. Fey and J. F. Lenssen, "Fast graph representation learning with pytorch geometric," arXiv preprint 1et.:0903002225 2019.
[43] A. L. Traud, P. Mucha, and M. A. Porter, "Social structure of facebook networks," Physica A: Statistical Mechanics and its Applications, vol. 391, no. 16, pp. +165-4180. 2012.
[44] P. Sen, G. Namat, M. Bilgic, L. Getoor, B. Galligher, and T. Eliassi-Rad, "Collective classifica- tion in network data," magazine, vol. 29, no. 3, pp. 93-93, 2008
[45] Z. Yang, W. Cohen, and R. Salakhudinov, "Revisiting cupi-supee learning with graph embeddings." in International conference machine learning. PMLR, 2016, pp. 40-48.
[46] O. Shchur. M. Mumme, A. Bojchevski, and S. Günnemann, "Pitfalls of graph neural network evaluation," arXiv preprint
2018.
[47] B. Rozemberezki, C. Allen, and R. Sarkar. "Multi-scale attributed node embedding," Journal of Complex Networks, vol. 9, no. 2. p. cnab014, 2021.
[48] C. Sun and G. Wu, "Scalable and adaptive graph neural networks with self-label-enhaneed training." " arXiv preprint arXiv:2104. 09376,, 2021.
[49] W. Zhang, Z. Yin, Z. Sheng, Y. Li, W. Ouyang, X. Li, Y. Tao, Z. Yang, and B. Cui, "Graph attention multi-layer perceptron," in Proceedings of the 28th ACM SIGKDD Conference Knowledge Discovery and Data Mining, 2022, pp. 1560045700
[50] P. Kairouz, S. Oh, and P. Viswanath, "The composition theorem for differential privacy," in International conference on machine learning. PMLR, 2015, pp. 1376-1385.
[51] T. Van Erven and P. Harremos, "Rényi divergence and kullback- divergence," IEEE Transactions on Information Theory, vol. 60, no. 7, pp. 3797-3820, 2014.
12

---

[52] J. Zhu, Y. Yan, L. Zhao, M. Heimann, L. Akoglu, and D. Koutra, "Beyond homophily in graph neural networks: Current limitations and effective designs," Advances in Neural Information Processing Systems, vol. 33, pp. 7793-7804, 2020.
[53] A. Yousefpour, I. Shilov, A. Sablayrolles, D. Testuggine, K. Prasad, M. Malek, J. Nguyen, S. Ghosh, A. Bharadwaj, J. Zhao, G. Cormode, and I. Míronov, "Opacus: User-friendly differential privacy library in PyTorch, arXiv preprint arXiv:2109. 122999 2021.
[54] G. Klambauer, T. Unterthiner, A. Mayr, and S. Hochreiter, norf-nioraa neural networks," Advances in neural information processing systems, vol. 30, 2017.
13

---

A Limitations and Broader Impacts
Limitations. While our experimental results demonstrate several benefits of using DPDGC designs over standard convolutions, we do not believe that the current DPDGC model the ultimate solution for GDP-aware graph learning methods. To support this claim, we that the nonprivate state- of-the-art performance for learning on large-scale homophilic graphs is achieved by standard graph convolution models (48] 49). Our experiments for edge GDP settings also reveal that standard graph convolution designs (such as GAP) appear to work well when the parameter is small. We therefore conjecture that further improvements for decoupled graph convolution designs are possible.
Broader Impacts. We are not aware of any negative social impacts of our work. fact, our work establishes formal DP framework for graph learning termed GDP. This is beneficial to many applications that require rigorous protection of the privacy of users when their sensitive information stored as graph dataset be leveraged by graph learning methods. Note that DP is the gold standard for quantifying the privacy of user data and it has found widespread applications. Given the popularity of graph learning methods and the need for user privacy protection, believe that work will actually have a positive social impact.
B Generalized adaptive composition theorem
In order to ensure that a graph learning method satisfies GDP, we need to follow commonly employed approach that involves the following steps: (1) introducing appropriate perturbations to the learned graph representation (e.g., ())) for GAP or Z for DP-DGC as shown in Figure 2 and (2) training the downstream DP-MLP using DPSGD. Subsequently, employing composition theorems allows for establishing an overall privacy budget. However, as we argued in Section 4 it is important to establish "partial DP guarantees for intermediate node embeddings (*) or (i.e., ensure that only Zr DP and exclude Z, from latter mechanisms, as Theorem 5.3) When feeding the entire Z to the subsequent mechanism BZ Z,)) part of the input may not be DP and may exhibit correlations with other (processed) data components. This renders the standard composition theorem for DP [40 [1 50) inapplicable. To address this issue, developed novel generalized composition theorem that can handle potential dependencies.
Theorem B.1. Let Let A: (Ai(D), A2 21 Bg satisfy the (a, (.)11)RDD constraint its first output argument, i.e., Da (AA()))AA())))) S E1. Let B: 21 x B2 - W satisfy the (a, 62)- RDP constraint
second input argument, i.e., max,, Da (B(z), Z2) ZB)]|B((,, 22)2) S E2. Let the random noise used A and B be independent. Then (D), B(A(D))) jointly meets the (0 + RDDP guarantee.
Proof. For ease of explanation, we assume that the density (and the conditional density) of A and B with respect to the Lebesgue measure exist. Let
(A())) (Z, Zz) and (AI( (Z4;%);;
. B(A(D)) = W and B(A(D') W'
14

---

longer independent due the aggregation step, and hence the standard composition theorem may not be applicable. In this case, In addition, let fw (w), fz, (z1), and fz. (Zz) be the density of W, Z1 and Zg, respectively. Observe that
Da ((Z1, W(1,, (Z)) ((2(222))
/wiz. 21.722 (W 22) w) f22 Z2 21 (Zz) fzz (z) ddz
log Ew R1
a
Ma /wIZ) [2; [2,== (W(z), 22) w) f23 [2 =z (Zz) [zz (z) )o1
(a) 1
12, fwiz, [wiZz=2, (W(z), 22) = w) -fzz Zn =1 (22)
log Esz
Ew
112 JwizZ (W(z), = w) fzzz22 =1 (z 122
211
Q
Izi (21) fzz (z1)
ar
(b)
1
fwizz - 22 [wizi= -11 =2 (W k2) = w)
(W = =w]
fz, (z1) Jzz (zi)
log E
max 25 Sig
Ew
21
01
(2)
log Ezz
(e:((a11) 1)
Iz, (21)
a7
fzz (z1)
S E1 + E2:
where (a) holds by the tower rule of conditional expectations; (b) holds due to the joint quasi-convexity of the Rényi divergence [5I]; (c) holds since B is E2 Rényi DP; and (d) holds because A1 is Rényi DP.
Remark B.2. Note that if A2() is independent of (D)), then the above composition theorem reduces the standard sequential composition [40], which follows directly from the chain rule for the Rényi divergence. However, in the analysis of GDP, we need stronger result capable of handling the dependence between A₁(D) and (D))
In the privacy analysis of our proposed DPDGC, we set A1 and A²(D) in Theorem B. to , and Z,, respectively, and let B(D) be the weights of the DP-MLPw trained via DP-SGD (see Appendix Hp. Nevertheless, we note that since the Gaussian noise samples added to Z,r and Z, are indeed independent in DPDGC, by grouping (A,, B(D)). one can directly apply the classical composition theorem (40) to A (D) and (A, B(D)) and arrive the same conclusion. Similarly, in the one-hop GAP illustrated in Figure 2 we applied the same privacy analysis, with A1 (D),
(0) and the weights of DP-MLPW: respectively, which allowed us A2(D), and (DD) set to H Ar H!!)
to obtain the GDP guarantee.
However, it is worth noting that for a L-hop GAP (i.e., when aggregation is performed L times), the DP noise introduced in H( and that introduced in H
our generalized composition theorem rigorously leads to the desired GDP guarantees.
In summary, our generalized composition theorem (Theorem B.I) provides "cleaner argument" for the case that merely part of intermediate node embedding and H (k) are DP (i.e., Z, and H (k) are
DP but not the entire Z and (*))). Furthermore, our Theorem B.1 also allows for handling more complicated cases (i.e., when the noise in A₁ (D) and the one in A²(D) () are not independent).
C Proof of Theorem 5.3
Theorem. For any > 1 and 'D N. D'. assume that (A((W(A), (A()) (/W))))))) both A, A' has bounded out-degree D. Let the replaced node index be r and Z, be the matrix Z excluding its th row. Then the embedding Z in DPDGC satisfies D., (Z ( S m1 + 2
bb)) S 7 and that
2Da
15

---

Proof. We start by examining [A'(
- 1r II.. Note that
|| [A''(A]]/> (AW(A) 1rl1
Σ II(A A.) (E(m)((
-(,)-A)) A.)
which is the sum of row-norms of all nodes except for node r. Let us denote the out out-neighborhood of node with respect to A as N (r) {i: Air = =1. Similarly, we also have (r) = {i: A = 1}.
There are four possible cases for E [n] \ {r]: (1) E Nr) (r)), (2) i E N'(r) (r). (3) i E (r) (r), and (4) ((r) U (r). Clearly, for covered by cases (3) and (4), the
corresponding row norm is 0 since A = A, for i ((r) ( and (rr)) For cases (1) and (2), we have
[IA A.) 12 ||e p
where (a) is due to the fact that (44) is row-normalized. By the bounded out-degree assumption, we know that (r)( (r)) I D. Thus, the worst case upper bound of || /W(4)) /v (AW(A)) Kell arises when (r) and (r)r disjoint, which results in contribution of 2D for cases (1) and (2). As a result, we have
[|A (A'W(4)) - [AW( My
E A,) $ 2D. (E(
This implies a sensitivity bound V2D. As a result, using the Gaussian noise mechanism with standard 2Da in the divergence bound. Finally, since the entire W(4) is DP by deviation s leads to the term 2s the assumption, applying the standard DP composition theorem [40] completes the proof.
L
Regarding the assumption used, can met by applying a standard DP-optimizer with an group size D + 1, where 71 depends on the noise multiplier of the DP-optimizer. This is due to the fact that the out-degree is bounded by D, so replacing one node can affect most 7) neighbors.
D Proof of Theorem 5.4
Theorem. For any D No D'. , let the index of the replaced node be r: also, let Zir be the matrix Z
with its pth row excluded, and assume that D& (AW(A), ( b)') I 7/1 For any a > 1, the embedding Z in DPDGC satisfies D (Z
S 71
ko 2
Proof. The proof is nearly identical to the proof for the node-GDD case (Theorem 5.3
The only
difference arises when for the case E [n] \ {r). Recall that our goal analyze
||[A (W(A)) [AW (4) |r = Σ II -. A,) w(d)j2.
Again, there are four possible cases for i E [n]
{r]: (1) N(r) \ (()
( E (r) n N')); and (4) & ((r) U (r). Clearly, for covered by cases (3) and (4), the corresponding row norm is 0 as in this case, A A; For cases (1) and (2), we have
[[A A.) W 1 2= |le? w (
where (a) is due to the fact that (4) is row-normalized, By the definition of D No D', we know that there are at most & rows corresponding to cases (1) and (2):
Hi E (() (' Hi (N)) \ N()H k
As result, we have
[[A (AW(A) 1r
Σ II - A.) w.)) k xE(a|((r
This implies a sensitivity bound Vk. As a result, applying the Gaussian noise mechanism with standard deviation leads to the term 25 the divergence bound. Finally, since the entire ((A) is DP by assumption, applying the standard DP composition theorem (40) completes the proof. O
16

---

E Proof of Theorem 5.1
Theorem. For any > 1 and DD N DD' or 'D N' D'' assume that Da (W [ I and that both A, A' have bounded out-degree D. Let the replaced node index be and let 2r be the matrix excluding its pah row. Then the embedding Z used in GAP satisfies Da (Z 1 S 71 + 4DLa
2s
Proof. We start by showing that for any D N D', Da (H
S m 28 By examining
[AH]] A " || for all i E [n] \ {rr, we find that there are three cases that contribute nonzero norms. Let (r) and (r) denotes the neighbor node set of with respect to and A', respectively, The three cases are: (1) i E [(r) (r),,, (2) i (r(r) \ (r),, and (3) E (r) 7 (r). For
cases (1) and (2), [AH] [A'H'; < 1 due to H))) and H being row-normalized, For case H = H, - H S 2. Since the out-degree upper bounded by D. we know that max (r)), [N)()) (r) D. The worst-case arises for (N(r ( = D. Hence
(c), we have [AH]
we have the following worst-case upper bound
[[H [A'H]]
Σ ME
|AH [A'H', 12 4D².
This leads to the term 4Da in the divergence bound. By applying Theorem B.1 and the assumption 2;2
on W(X) show that D [H (1)
(1)) S +
4Da
2,2
For the L-hop result ,,, one apply Theorem B.I and induction. The base case L is already (H((")))
established above. For the induction step, we have Da (H(("
AD(L-1)a By
sn n + 2,²
(r
applying Theorem B.T and repeating the previous analysis, we have
(L)
4D(L 1)a
4Do
4DLa
(H
25
252
71
2s
(3)
Here, the key idea is that although H. H (1-1) is not private, it is still row-normalized so that the above
sensitivity analysis still applies. For the case D N D', the worst case scenario still arises for (N(r) n (r)r = D, for all l: 0. This is in fact the case for No (i.e., A A/). Thus, the same result holds for the case D No D', for all l 2 0. This completes the proof.
F
RDP to DP conversion
For a given (a, 7) Rényi DP guarantee, the following conversion lemma 34 36 allows us to convert it back to a (e, 8DD guarantee:
Lemma F.1 If A satisfies (a, ((a))-RDP for all a > 1, then, for any ō > 0, A satisfies (ÉDP (0), 6)- DP. where
(6) inf 7(a) + log (1/a0) a>1
+ log(1 - 1/a).
a a-1
G Edge GDP analysis for DPDGC and GAP
DPDGC. In this setting, ensuring that the embedding Z is DP is sufficient to guarantee the overall model being GDP. We can replace the remaining DP-MLP modules in Figure 2 with standard MLP (i.e., training with standard optimizer).
Theorem G.1. For any 1 and D E D', assume D. ((w()) ())l( S n. Then the embedding of DPDGC satisfies D. (Z S 71 + 2
Proof. Since there is only one replaced entry of the adjacency matrix for any E D', II
A A) S max4g(n) //W(A) || (i.e., the maximum row-norm of W(A)). This implies that
the sensitivity of (A) Thus, applying the Gaussian noise mechanism with standard deviation and standard DP composition rule [40) results in D (Z IZ)) 71 2..
D
17

---

Regarding the assumption, it can be met by applying standard DP-optimizer with group size 1, where " depends on the noise multiplier of the Dp-ommimizer. This due to the fact that at most one establish the edge Thus, we only need to ensure that the non-trainable module in GAP (i.e., PMA) DP.
row of A is different for any D E D'. By further applying Theorem B.1 GDP guarantees for DGDGC (Corollary H.I.
GAP. In this setting, all DP-MLP modules in Figure 2 can be replaced with standard MLP for GAP.
Theorem G.2. For any a > 1 and E D', the embedding Z of GAP satisfies Do ZZ
La 2
Proof. The analysis is similar to that of Theorem G.1 except that we have AH instead of AW A- Following the same argument, we know that Da ( composition theorem, we arrive at the claimed result.
S a 28
Then, by the standard DP
H Formal GDP guarantees for the complete DPDGC and GAP models
Corollary H.1. For any a > 1, the DPDGC model is edge (a.7 + 25 GDP.
Proof. This direct consequence of applying Theorem G.I (for guarantees pertaining Z) and the DP composition theorem.
Corollary H.2. Assume that the graph has bounded out-degree D. For any o > 1, the DPDGC model is node (a, "/1 + 1/2 2
2Da JGDP, where the remaining weights satisfy (a,, (0x;72)-RR) -2D-
Proof. This is a direct consequence of Theorem 5.3 oP-optimizer result [14] and Theorem B.l (the generalized adaptive composition theorem). O
(for guarantees pertaining to Zyr), the standard
Corollary H.3. For any a > 1, the DPDGC model is k-neighbor (a, 711 + 7/2 + remaining weights are (a, 712) -RDP.
ko GDDP, with 25
Proof. This follows by applying Theorem 5.4 (with guarantees for 7,,,, the standard DP-optimizer result [14), and Theorem B.I (generalized adaptive composition theorem).
Corollary H.4. For any 1, the CAP model is edge (a, 2g GDDP.
Proof. This follows by applying Theorem G.2 guarantees of Z) and the DP composition theorem.
Corollary H.5. Assume that the underlying graph has bounded out-degree D. For any 1. the GAP model is node or k-neighbor (a, " + 72 (ac, RDP.
+ 4DLe GGDP, while the remaining weights are
25²
Proof. This follows by applying Theorem 5.1 (with guarantees for Z,,,), the standard DP-optimizer result 14]. and Theorem B.I (generalized adaptive composition theorem).
I Discussion on inductive settings
While we focus on the main text was on the transductive setting, we note that the inductive setting is actually significantly easier from the perspective of insuring privacy. There are two different settings for inductive graph learning. We call the first scenario the "fully inductive setting". What this means that the information pertaining to test nodes completely unavailable during the training phase and not subject to privacy protection [ One can think of this as a case where the training graph and the test graph are disjoint. In this case, model DP sufficient to guarantee prediction DP, as one only access training data information through the model weights. As result, the extension of DP-SGD for GNNs [15] suffices to ensure rigorous user data privacy.
We refer to the second setting as the "incrementally inductive setting". What this means is that we will use all training and test node information during inference, despite the test nodes not being used during the training phase. In this case, DP of model weight does not ensure the DP of the model
18

---

prediction. Hence, we will need our GDP guarantees to ensure user data privacy protection. Since we only need to ensure the privacy of training data, the RDP condition Definition (4.2 no longer needs to specify which test node is to be predicted. This is due to the fact that any test node that could be the target for prediction cannot be a training node. Thus, we will not replace in the adjacent dataset. The remainder of the GDP analysis is similar to the previous one.
J Practical privacy meaning of k in k-neigbor GDP
The notion of k-neighbor GDP with (e, 6) = (0,0) implics that an adversary cannot simultaneously infer information about any in-edges and k out-edges in A. As discussed in the main text, even the case = already provides a similar but stronger topology privacy protection than edge GDP. Although adversary cannot infer the existence of any edges for the k 1 case, they might be confident that there is one edge among two node pairs even though they cannot be certain which one it is. For instance, even though adversary cannot individually infer whether A12 and A3 are 1 or O, they may be confident that the event {A12 = 1 V A13 = }} is true. The that the adversary cannot simultaneously infer
k 2 setting provides additional protection information about any k- = 2 edges. Nevertheless, the adversary may still be confident that the event {A12 V A13 V A14 1} is true (in the worst case). similar reasoning holds for general values of k. As result, selecting an intermediate value of k may reveal some edge information, but allows for a trade-off between the potentially sensitive edge information and model utility. is worth noting that in many practical scenarios, edge information is less sensitive than that of node features, making this notion of privacy particularly useful. For instance, if we are satisfied with the graph structure protection from edge-level GDP, we can simply use k = 1 for additional protection of sensitive node features and labels, with similar graph topology privacy.
K Additional experimental details
Datasets. We test seven benehmark datasets available from either the Pytorch Geometric library 42
or prior works. These datasets include the social network Facebook [17 43 citation networks Cora and Pubmed 45). the Amazon co-purchase networks Photo and Computers [46). and Wikipedia networks Squirrel and Chameleon (47). Pertinent dataset statistics can be found in Table We also
report the class insensitive edge homophily measure defined in [39], with value in [0, 1]; the value 1 indicates the strongest possible homophily. Its definition is as follows:
{i: Yie
homophily
max(0, lie
= C-1
he K(t,w) (V, EEA Yuo = 11
Note that he represents the edge homophily ratio of nodes of class e, where the general edge homophily is defined in (2))
The cSBM model. We mainly follow the cSM model as described in [9 The cSBM model includes Gaussian random vector node features in addition to the classical SBM graph topology. For simplicity, we assume that there are = 2 equally sized communities with node labels V (+1,-1). Each node is associate with a dimensional Gaussian vector b, = / + 3 where is the number of nodes, 1/ and Z, R/ has independent standard normal entries. The graph in cSBM is described by an adjacency matrix A defined as
d+Ava R Lva
if 0vu, >0 otherwise
P (A.; =
Similar to the classical SBM, given the node labels, the edges independent. The symbol d stands for the average degree of the graph. Also, recall that μ and control the strength of the information content conveyed by the node features and the graph structure, respectively.
One reason for using the cSBM to generate synthetic data that the commmattooo-thorettii limit of the model has already been characterized in [18] This result is summarized below.
19

---

Theorem K.1 (Informal main result from [8] Assume that n. - oc, & and d + co. Kdail is bounded away from O if and only if
Then there exists estimator i such that lim inf 100
X 1 1.
In experiment, we
10, 000.f = 200, that Ç 50. We vary a and X along the X² + +/// ++ e, for some e > 0, to ensure that we are within the allowed parameter regime. We also set 3.25 in all our experiments.
Experiment environments. All experiments are performed on Linux Machine with 48 cores, 376GB of RAM, and an NVIDIA Tesla P100 GPU with 12GB of GPU memory. We use PyTorch Geometrid [42] for graph-related operations and models, autodp for privacy accounting and Opa- cus 53 for the DP-optimizer. Our code is developed based on the GAP repository 66 17 and follows
a similar experimental pipeline.
Hyperparameters. For all methods, we set the hidden dimension to 64, and use ScLU [54] as the nonlinear activation function. The learning rate is set to 10-3, and do not decay the weights. Training involves 100 epochs for both pretraining and classifier modules. We use dropout 0.5 for nonprivate and edge GDP experiments and no dropout for the node GDP and k-neighbor GDP experiments. For DPDGC, find that row-normalizing (A)) 10-8 and reducing s accordingly gives better utility in practice (see Algorithm 2 where we set c = 10-$). Following the analysis of DPDGC, we know that this changes the sensitivity of (W to v2De for node GDP and vke for k-neighbor GDP, respectively. Note that when c 1, we recover the results of Theorem [.3 and 5.4 For GAP, we tune the number of hops L E {1, 2, 3). For both DPDGC and GAP, the MLP modules have layers in general, except for the MLPA A and MLPx modules in DPDGC which have 1 layer. For MLP, we use 3 layers following the choice of [17]. We upper bound the out-degree by D = 100 for all datasets, following the default choice stated in [17]. The batch size depends on the dataset size, where we choose 256 for Facebook and Pubmed, and 64 for the rest. Note that we train without mini-batching whenever the training does not involve a DP-optimizer and the method has better performance. For the cSBM experiments, we adopted the settings used for the Facebook dataset. We observe that DPDGC (nopriv) can have severe overfitting issues for & = 0, which causes the results to be unstable. For this particular case, we change the learning rate of the embedding module to 10-5 in order to mitigate the issue.
DP-optimizer. We use DP-Adam by leveraging the Opacus library. We retain the default setting for all methods.
L Pseudocode for GAP and DPDGC
h wwwp
20

---

Algorithm Training process of GAP
1: Model input: node feature X, adjacency matrix A, training labels Y.
2: Parameters: noise std s, hops L, and max degree D.
3: if edge GDP then
4: Train DP-MLPx using a standard optimizer.
5: else
6:
Train DP-MLPx using a DP-optimizer with group size of 1.
7: end if
8: H + DP-MLPx(X),
9: ())) f- row-normoiie row-normalized| H) and cache H
if node or k-neighbor GDP then
11:
Subsample A so that the out-degree (column-sum) is bounded by D.
end if
13: for 1 I L do
H row normalized(H (0, s)).
15: end for
Z + 1 H and cache Z.
17: if edge GDP then
Train DP-MIP, using a standard optimizer.
19: else
20:
Train DP-MLP, using a DP-optimizer with a group size 1.
21: end if
Algorithm 2 Training process of DPDGC
1: Model input:
node feature X, adjacency matrix A, training labels Y.
2: Parameters: noise std maximum degree D (for node GDP) or k for k-level GDP, row- normalized constant
3: if node GDP then
4: Subsample A so that the out-degree (column-sum) is bounded by
5: end if
6: if node GDP then
D1 8: else if k-neighbor GDP then
7:
9:
x=
10: else
T-1
12: end if
(A) b)+ Train DP-Emb using DP-omtimizer with group size x and constrain ((4) be row-normalized to
+- x 8.
15: Z row-normalized( (A + (2) b) and cache Z.
if edge GDP then
17: Train the remaining modules using standard optimizer.
18: else
19:
Train the remaining modules using DP-optimizer with group size 1.
20: end if
21


Reviews:
[{"review_id": "lmkzqXL1QO", "reviewer": "Reviewer_WwFs", "summary": "The authors introduce a new model for Graph Differential Privacy (GDP) that ensures a parametric level of topological privacy through decoupling of the graph convolution mechanism (i.e., preventing direct neighborhood aggregation of features = standard $AXW$ aggregation). The key definition is that up to $k$ in- and out-neighbours of a randomly selected single node $r$ can be modified to create  a new adjacency matrix. This makes this a hybrid between edge ($k=1) and node ($k=n) GDP, the parameter $k$ allows a tradeoff between  topology privacy and accuracy. All GNN training is done using this modified graph $D’$ to create the model parameters for inference. The main contribution of the paper is three-fold 1)  proving theoretical bounds on the Differential Privacy (DP) state of the art DPGNN called GAP [19] 2) Intuitions from analyzing the DP weakness of GAP to develop a novel Differentially Private Decoupled Graph Convolution (DPDGC) model, which benefits from decoupling graph convolution while providing GDP guarantees 3) theoretical bounds on the DP of their proposed DPDGC. The key intuition is that GAP has greater privacy leakage because they compute $A'H'$ where both adjacency matrix and features change. Motivated by this the authors propose DPDGC in which the $A'H'$ product is avoided thus providing more privacy than GAP.", "questions": "What is the practical meaning of high-$k$ topology protection? in other words what are the additional security benefits obtained by going from $k$ to $k+1$. Its not clear to what is the marginal utility of increasing $k$ in terms of the increasing cost to an adversary who wants to break privacy. This is an important question as varying $k$ is the major difference between this work and GAP.\n\nHow well will the decoupling method DPDGC work on large scale homophilous graphs with moderately high privacy budgets. I would like to see more extensive experimental results to justify the cost of decoupling versus simple MLP methods. \n\nFig 1 is hard to understand (contextualize) with a lot of undefined terms (e.g., k-neighbor level adjacency) especially as it comes so early in the paper. Consider moving to later or defining better in-text.\n\nDef 4.3 seems ambiguous: $k$ entries of $A_{rj}$ and $A_{lj}$ are modified but what is the size of $ j + l $( Is $j+l=k$ or $2k$?). Text only says “some” $j$ and $l$.\n\nThere are multiple variations of row normalization, are you doing Euclidean norm normalization of each row, it is not clear from the text and obviously it makes a big difference in the proof as it is known that Euclidean row normalization dampens the effect of outliers [1] “Sign and rank covariance matrices” J. of Statistical Planning and Inference, Dec. 2000.\n", "limitations": "The authors have addressed the limitations of this work in the appendix. \"we do not believe that the current DPDGC model is the ultimate solution for GDP-aware graph learning methods. To support this claim, we note that the nonprivate state of-the-art performance for learning on large-scale homophilic graphs is achieved by standard graph convolution models [47, 48].\n\nThe authors have stated that the proposed topic doesn't have any negative societal impacts, instead GDP can potentially protect user data and is beneficial. However this is a generic statement and needs to be proved (to what extent will  breaking GDP of a graph impact individual users?)", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Sound theoretical analysis of the two GDP models \n\nTheoretical analysis of GAP i.e., the presence of the $A'H'$ product which is shown from Theorem 1 to be a contributing factor to the DP limitation of GAP. This leads to their derivation of DPGDC which applies a DP-MLP to adjacency matrix A using a non-linear operation on $AW^{(A)}$  to create the adjacency matrix embedding $Z$, where $W_A$ are fixed model weights. This is opposed to GAP which computes $AH$ for the $Z$ embeddings.  By ensuring $W^{(A)}$ is DP, they only need to look at $A'W^{(A)}$ versus $A'H'$ in GAP.\n\n\n", "weaknesses": "\nA big portion of the paper is spent defining the problem and setting up conventions for future Differential Privacy studies to be more suitable to the GNN field/setting. \n\nThe novelty of the decoupling method is not very convincing. The idea of decoupling is previously found in this paper [1]\"Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methods\", D. Lim, F. Hohme et. al, Neurips 2021, which defines a method called LINKX for non-homophilous graphs. LINKX separately embeds the adjacency $A$ to $h^A$ and the features $X$ into $h^X$ before mixing adjacency and feature information. The decoupling method proposed here seems to be a modification of the LINKX strategy. \n\nFrom Table 3, the proposed DPDGC model works well compared to the other differential privacy models when the graphs are heterophilic.  This is not surprising because the decoupling idea is known to be beneficial for heterophilic graphs [1]. However, the other baseline methods work better in a homophily setting (columns in the right side of the table) because they are not specifically designed for that kind of setting. I would expect a more adaptive method that works in both settings to be more convinced about the utility of this method.\n\nAlso from Table 3, simple MLP outperforms DPDGC in accuracy for higher $k$ on many datasets, especially homophilic ones. As pointed out by the authors themselves, protecting the graph information (higher privacy requirements) quite drastically reduces the utility of these decoupling methods. So the practical utility of this seems questionable.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer WwFs for their thoughtful feedback and comments. We addressed all questions below.\n \n- W1: `` A big portion of the paper is spent defining the problem and setting up conventions for future Differential Privacy studies to be more suitable to the GNN field/setting.``\n \nWe believe this is in fact one of our most important contributions. Note that we need a rigorous definition and proof for GDP to truly ensure the privacy of graph datasets. As first pointed out by the authors of [19], merely ensuring GNN weight DP is insufficient to protect the privacy of graph datasets. We are the first to formally define GDP and lay rigorous theoretical foundations for future DP GNN studies.\n \n- W2: `` The novelty of DPDGC with respect to LINKX``\n\nPlease see G4 in our general response.\n \n- W3: “DPDGC only works well on heterophilic graphs but not homophilic graphs”\n \nWe agree that part of the reason that DPDGC works well on heterophilic graphs is due to the same reason LINKX works well on heterophilic graphs. However, we would like to emphasize that our contribution is to propose the privatization design of DPDGC and identify the theoretical privacy benefits of decoupled graph convolution design. Note that ensuring the GDP guarantee is not trivial, as a direct extension of DP-SGD training to GNN does not work (see lines 41-46). GAP is the only (and prior state-of-the-art) DP-GNNs that satisfies GDP guarantees (our Corollary H.4 and H.5) but does not work for heterophilic graph datasets as demonstrated in Table 3. Our DPDGC is currently the only method that can achieve nontrivial performance on heterophilic graph datasets with GDP guarantees.\n \nWe agree that DPDGC is only on-par with GAP under the node-level GDP setting for homophilic datasets. Nevertheless, DPDGC still significantly outperforms GAP in the  $k$-neighbor-level GDP setting on three out of four homophilic datasets. While DP-MLP can outperform all DPGNNs in certain scenarios, we conjecture this to be the case due to the benefits of graph information not being able to compensate for the utility loss induced by privacy noise that protects the graph information (line 330). Please check our general response G1 for more information. Still, we agree that there should be a more adaptive design of DPGNNs that works across all settings and datasets, which we also mention in our limitation section (Appendix A). Such a design appears hard to find and work on this problem is ongoing.\n \n- W4: `` simple MLP outperforms DPDGC in accuracy for higher $k$ on many datasets``\n \nPlease see G1 in our general response.\n \n- Q1: `` What is the practical meaning of high-$k$ topology protection?``\n\nThis is an excellent question. One can think that the parameter choice $k=1$ provides roughly the same privacy protection on $A$ as in edge-level GDP (albeit $k$-neighbor-level GDP also protects the node features and labels). For general $k$, this implies that the adversary cannot simultaneously infer the existence of $k$ neighbors for each node. Let's consider the simplest case of $k=1$: according to Definition 4.4, the GDP algorithm output prevents the adversary from inferring the existence of any edge, even with access to the remaining n-1 nodes and their edges. However, the adversary may still be confident that there is a true edge between certain node pairs. For instance, even though the adversary cannot individually infer whether $A_{12}$ or $A_{13}$ are $1$ or $0$, they might be confident that $A_{12}=1$ or $A_{13}=1$ in the worst case. The case $k=2$ additionally protects this case but the adversary might be confident that $A_{12}=1$ or $ A_{13}=1$ or $A_{14}=1$ in the worst case. A similar explanation holds for general $k$.\nSelecting an intermediate value of $k$ (where $1 < k < n$) may reveal some portion of edge information, but it represents a trade-off between the potentially sensitive edge information and utility. It's worth noting that in many practical scenarios, edge information can be less sensitive than node features, making this notion of privacy particularly useful in various applications. For instance, if we are satisfied with the graph structure protection from edge-level GDP, we can simply use $k=1$ for additionally protecting sensitive node features and labels with a similar graph structure privacy.\nPlease let us know if further clarification is needed, we are happy to provide a more intuitive explanation.  \n- Q2: ``How well will the decoupling method DPDGC work on large scale homophilous graphs?``\n \nThis is a good question. Please check G2 in our general response.\n \n- Q3: ``Fig 1 hard to understand, consider to move it later``\n \nThank you for the suggestion. We will either try to make it more clear or move it to the later part of the paper as suggested.\n \n- Q4: `` Def 4.3 seems ambiguous``\n \nSorry for the confusion. We meant to say that the total number of replaced entries is $2k$ ($k$ for in-edges and $k$ for out-edges). We will make this clear in our revision.\n \n- Q5: ``question about row normalization``\n \nWe apologize for the confusion. We mean an $\\ell_2$ norm (Euclidean) row normalization. That is, for a matrix $H\\in \\mathbb{R}^{n\\times d}$, we normalize each row of $H$ to have  $\\ell_2$ norm equal to one (i.e., $||H_i||_2 = 1$ for all $i\\in [n]$). We will make this clear in our revision.\n \nIt is interesting to investigate the outlier effect mentioned by the reviewer WwFs as a future direction. However, in this work, we merely focus on the privacy aspect and this future direction is out of the scope. We thank reviewer WwFs for this intriguing comment.\n \nPlease feel free to let us know if there are follow-up questions. We will try our best to address them in a timely manner.\n"}, {"review_id": "pecKEtOgI0", "reviewer": "Reviewer_XfoH", "summary": "The paper introduces a differentially private GNN model that allows for different privacy requirements for node attributes and graph structure. The model decouples graph convolutions from node attributes and graph topology and provides provable privacy guarantees. Experimental results are provided to show the proposed methodology's superiority.", "questions": "1. From line 310: \"we also test (DP-)MLP and several DP-GNN baselines that can achieve GDP guarantees, including RandEdge+SAGE [29] and DP-SAGE [18] for edge and node GDP, respectively.\". However, it is not clear what MLP refers to in Table 3. \n\n2. There is a large jump in performance for the non-private setting for DPDGC but the other methods do not exhibit this behavior. Any insight into this phenomenon?\n\n3. From line 341 - DPDGC starts to outperform GAP when privacy budget increases but lags behind when privacy budget is small. What is the typical scenario in real world situations? \n\n4. Regarding the comment on line 330: does homophily alone decide for which datasets utility loss from privacy noise compensates graph structure information? Basically, what are the things that one has to consider before picking the right algorithm to achieve GDP?\n\nMinor:\nOn line 109, what is T?\nTable 3: change \"none\" to \"non\"", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The problem and contributions discussed in the paper are clearly mentioned and the illustrations do a good job of conveying them. Graph differential privacy is an interesting topic and the idea of providing flexibility for node attributes and graph structure is promising.", "weaknesses": "Some discussion regarding the questions mentioned in the next section would add to the paper greatly.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer XfoH for their thoughtful feedback, comments, and positive assessment of our work. We addressed all questions below.\n \n- Q1: `` From line 310: \"...\". However, it is not clear what MLP refers to in Table 3.``\n \nWe apologize for the confusion. MLP in Table 3 refers to both non-private MLP and DP-MLP, depending on whether it is in the first row of Table 3 or not (i.e., having $\\epsilon>0$ or not). We will change MLP to DP-MLP in Table 3 when it is trained with DPSGD. See our pdf in the general response.\n \n- Q2: `` There is a large jump in performance for the non-private setting for DPDGC but the other methods do not exhibit this behavior. Any insight into this phenomenon?``\n \nWe assume that reviewer XfoH refers to results on heterophily datasets (Squirrel, Chameleon, and Facebook). It is known in the literature that standard GNN designs (such as GCN) do not work well on heterophilic datasets. In contrast, specially designed GNNs such as LINKX [38] work much better in this setting. Thus, we conjecture that GAP (and the other DPGNN baselines) which are similar to GCN cannot perform well on heterophilic datasets even in the nonprivate setting, as described in [38] and our Table 3. As a result, adding privacy noise to these models will not result in a huge performance drop, as they already have poor performance in nonprivate settings. In contrast, since LINKX can learn well on heterophilic datasets in nonprivate settings, injecting large privacy noise into LINKX can result in a huge performance drop. Please let us know if we misinterpret your question, we will follow up in a timely manner.\n \n- Q3: `` From line 341 - DPDGC starts to outperform GAP when privacy budget increases but lags behind when privacy budget is small. What is the typical scenario in real world situations?``\n \nIn practice, the privacy parameters $\\epsilon,\\delta$ and $k$ should be determined based on the agreement between the model holder, the users or privacy regulators. That is, the model holders and users should first determine the ***strength*** of privacy (i.e., $\\epsilon, \\delta$) they agree with even before training models. Given such GDP constraints, we can then identify the DPGNNs with the best utility. Our experimental results only demonstrate the privacy-utility trade-off, but do not assume any particular privacy level requirements.\n \n- Q4: `` Regarding the comment on line 330: does homophily alone decide for which datasets utility loss from privacy noise compensates graph structure information? Basically, what are the things that one has to consider before picking the right algorithm to achieve GDP?``\n \nThis is an interesting question. We believe that there are multiple factors that affect this phenomenon. We conjecture that both homophily level and edge density are two good indicators. Our conjecture is based on the analysis of the Stochastic Block Model (SBM) with two clusters [ref 1]. Consider a graph that has two even-size clusters ($n/2$). “In-cluster” edges are sampled i.i.d. from Bernoulli distribution with probability $p=a \\log(n)/n$. “Intra-cluster” edges are sampled i.i.d. from Bernoulli distribution with probability $q=b \\log(n)/n $ for some non-negative reals $a,b$. It is known from the literature that the fundamental limit of exact recovery (i.e. recover the clusters with high probability) is $|\\sqrt{a}-\\sqrt{b}|>\\sqrt{2}$ [ref 1]. Interestingly, this simplified case reveals two facts about how strong the graph information alone is: 1) when the homophily measure is close to $1$ or $0$ (i.e. |p-q| is large, where $p$ and $q$ are the edge density of in-cluster and intra-cluster edges respectively), the graph structure has strong information about the labels (clusters). 2) one needs edge density to be large enough. In the case of SBM, it should be $\\Omega(\\log(n)/n)$. If the edge density is too low (i.e., there are only n/2 edges), then it is impossible to achieve exact recovery even if $q=0$ as the graph is not even connected.\nIndeed, this only characterizes the strength of the graph information in a simplified case (2 clusters SBM). In real-world data, we also have node features and training node labels to learn from. We refer you to [ref 2] for a study of GNN utility on a generalized version of SBM, where both node features and training node labels are considered. Nevertheless, the privacy aspect of GNNs was not considered in [ref 2]. We also hope to further study the question of “when will the benefits of graph information compensate the price to privatize themselves.” \n\nPlease feel free to let us know if there are follow-up questions. We will try our best to address them in a timely manner. \n \n### References\n \n[ref 1] Community detection and stochastic block models: recent developments, Emmanuel Abbe, JMLR 2017.\n \n[ref 2] Graph Convolution for Semi-Supervised Classification: Improved Linear Separability and Out-of-Distribution Generalization, Baranwal et al., ICML 2021\n"}, {"review_id": "6wzscakvvd", "reviewer": "Reviewer_tLab", "summary": "The paper presents a well-written and easily understandable framework called Graph Differential Privacy (GDP) tailored for graph learning methods. The proposed framework aims to address the privacy challenges associated with GNNs by ensuring both model parameter and prediction privacy. The authors introduce the Differentially Private Decoupled Graph Convolution (DPDGC) model, which offers superior privacy-utility trade-offs compared to existing approaches. The paper includes theoretical analysis that provides a solid foundation for the proposed model. The authors evaluate the DPDGC and compare it with existing differentially DP-GNN methods, as well as non-private models. By achieving SOTA performance, the experimental results validate the effectiveness and utility of the proposed DPDGC model in graph learning tasks.\n", "questions": "See Weaknesses", "limitations": "The authors do not adequately acknowledge potential limitations in their work, which may indicate a lack of comprehensive understanding of the challenges and constraints associated with the proposed framework.\n", "rating": 4, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The paper is its clarity and coherence. The authors have effectively conveyed complex concepts and ideas in a well-structured manner. \n2. The theoretical analysis provided in the paper adds good value to the research, supporting the proposed model and enhancing its credibility. \n3. The incorporation of the DPDGC model, which leverages decoupled graph convolution, achieves SOTA result.\n", "weaknesses": "1. Lack of comparison with other methods: The paper focuses primarily on comparing the performance of the proposed GDP-based methods (including DPDGC) against other differentially private graph learning methods. However, it would be beneficial to include a comparison with SOTA non-private graph learning methods to better understand the tradeoffs between privacy and utility.\n \n2. Limited evaluation on larger and more diverse datasets: The experimental evaluation of the proposed methods is conducted on a relatively small set of benchmark datasets. The generalizability and scalability of the methods to larger and more diverse datasets are not extensively explored. Including a broader range of datasets would provide a more comprehensive evaluation of the proposed methods' performance and generalizability. \n \n3. Lack of detailed analysis on privacy guarantees: While the paper mentions the privacy guarantees provided by the GDP framework and the DPDGC model, the detailed analysis of these guarantees is not thoroughly discussed. Providing more in-depth analysis, proofs, and discussions of the privacy guarantees would strengthen the paper's claims about the privacy properties of the proposed methods.\n \n4. Limited exploration of alternative privacy mechanisms: The paper primarily focuses on GDP as the privacy framework and DPDGC as the corresponding graph learning model. However, there are various other privacy mechanisms and techniques available in the field of differential privacy. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer tLab for their thoughtful feedback and comments. We addressed all questions below.\n \n- W1: `` Lack of comparison with other methods: ... include a comparison with SOTA non-private graph learning methods to better understand the tradeoffs between privacy and utility.``\n \nWe appreciate the comment. We agree that comparing our method with SOTA ***non-private*** graph learning methods will reveal the exact price we need to pay for privacy (GNN GDP). However, we would like to point out that studying GDP for graph learning methods is very different from studying standard DP neural networks, as incorporating (modified) DP-SGD can only ensure GNN weights being DP, but not their final output predictions. A direct injection of DP noise typically leads to very poor, if not meaningless, results. See the DP-SAGE approach and the discussion in the GAP paper [19] for an example.\n\nFor standard (graph-free) classification problems, one can simply adopt DPSGD during training to make any neural network model DP. That is, the model design and the privatization approach are decoupled. Unfortunately, this is not the case for graph learning as we explain in lines 41-46. When requiring both GNN weights and the output to be GDP, we have to also specifically design DPGNNs and thus not all GNN models can be privatized easily to satisfy GDP. As we also mentioned in our limitation section (Appendix A), DPDGC designs may not be the ultimate solution for DPGNNs. Due to the complex nature of the graph learning problem, one may need to jointly design the GNN and the privacy mechanism as in GAP and our DPDGC. Nevertheless, ours is currently the best GNN model that offers GDP guarantees. As a result, we only compare GNNs that can achieve GDP with the method described in our manuscript.\n \n- W2: `` Limited evaluation on larger and more diverse datasets``\n\nThank you for this comment. While we agree that evaluating our model on larger datasets is beneficial, we believe that our tested datasets are the most diverse one known in the DPGNN literature. Note that we are the first to test DPGNNs on heterophilic datasets and various homophilic datasets. Due to the diversity of our dataset’s choice we were able (for the first time) to establish that DP-MLP can outperform all other existing DPGNNs in some cases. This phenomenon also shows the importance of our novel $k$-neighbor-level GDP definition, as it provides a new utility-graph structure privacy tradeoff. \n\nRegarding the experiments on large datasets, please check G2 in our general response.\n \n- W3: `` Lack of detailed analysis on privacy guarantees``\n \nDue to space limitations, we were only able to provide sketches of proofs in the main text (Section 5). Complete proofs were presented in  Appendices (B to H), as is standardly done with ML conference submissions. We have tried our best to explain the key steps of our analysis in Section 5, especially regarding why the “coupling” graph convolution design fails to explore the trade-off of $k$-neighbor-level GDP and utility in lines 244-251 (i.e., the sensitivity remains unchanged for different $k$). The key ingredient for establishing a GDP guarantee is to derive tight sensitivity bounds for GAP and DPDGC, which are discussed in detail in Section 5, lines 222-236 and lines 287-292. For the proof of our main theorem (i.e., Theorem 5.1, 5.3, and 5.4), please check Appendix E, C, and D, respectively. Nevertheless, we will try our best to make our sketch of proof and discussion more transparent in the revision.\n \n- W4: `` Limited exploration of alternative privacy mechanisms: The paper primarily focuses on GDP as the privacy framework and DPDGC as the corresponding graph learning model. However, there are various other privacy mechanisms and techniques available in the field of differential privacy.``\n\nWe believe that our privacy definitions for graph datasets are common and appropriate in both theory and practice. It is worth noting that the notions of edge-level and node-level DP have been widely adopted and studied in numerous previous works [18,19,29]. In our work, we further extend DP definitions by introducing the concept of k-neighbor-level privacy, which offers a novel way to capture practical privacy considerations specific to graph datasets.\n\nRegarding the techniques employed to achieve GDP, we have designed a GNN architecture with small sensitivity,  compatible with the DP noise addition mechanism. Our choice of Gaussian noise as the mechanism to achieve DP is well-founded for several reasons: (1) Gaussian noise allows for tighter privacy accounting, (2) the Gaussian mechanism has been proven to achieve optimal MSE under a z-CDP constraint [ref 1] (note that z-CDP can be viewed as a variant of Renyi DP), and (3) Gaussian noise DP is easy to implement in practice. While we believe that our technique based on the Gaussian mechanism is well-suited for the task, we are also open to alternative suggestions and would be happy to implement and compare with other solutions proposed by the reviewer.\n\n [ref 1 ] Mark Bun and Thomas Steinke, “Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds”, TCC 2016\n \n### Comments regarding the limitation\n \nDue to the space limit, we have put the limitation section in Appendix A. We have mentioned that current SOTA non-private GNNs on homophily datasets are still using “coupling” graph convolution designs. Thus, our proposed DPDGC may not be the ultimate solution but it is the best currently known solution under GDP constraint. We hope to further investigate whether there is a new GNN design that can have the merits of both worlds. Hence, we respectfully disagree with the comment about us not adequately acknowledging the limitations of our work.\n \nPlease feel free to let us know if there are follow-up questions. We will try our best to address them in a timely manner.\n"}, {"review_id": "7MCZzij3N2", "reviewer": "Reviewer_ssFv", "summary": "This paper introduces a new framework called Differentially Private Decoupled Graph Convolutions (DPDGC) for graph learning settings that ensures both provably private model parameters and predictions. The framework is designed to protect sensitive user information and interactions in graph-structured data. The authors highlight the limitations of standard Differential Privacy techniques in graph learning settings and propose a novel notion of relaxed node-level data adjacency to establish guarantees for different degrees of graph topology privacy. The paper also includes an analysis of the framework and its performance compared to existing methods.", "questions": "1. How can one determine the appropriate value of K for a given dataset, in order to achieve meaningful results considering both privacy protection and utility?\n2. In the case of the Pubmed and Cora datasets, why do the results of graph-based machine learning methods remain unchanged across different values of K, and what implications does this have for the use of these datasets in research?\n", "limitations": "1. The paper's presentation could be improved to make it easier for the reader to follow the content and understand the proposed method.\n2. The utility of the proposed method is limited, as the privacy protection achieved with a privacy budget of eps=16 is too weak to be meaningful for many datasets. Furthermore, even with this level of privacy protection, the performance of the proposed method is significantly worse than that of non-private baseline models on most datasets, indicating poor utility.\n3. The paper could benefit from a more comprehensive review of related works, as some relevant studies are not cited or discussed in the text, including [1].\n \n[1] Zhang, Q., Ma, J., Lou, J., Yang, C., & Xiong, L. (2022). Towards Training Graph Neural Networks with Node-Level Differential Privacy. arXiv preprint arXiv:2210.04442.\n", "rating": 4, "confidence": 5, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. This paper focuses on the important problem of graph differential privacy, which is critical in protecting sensitive user information and interactions in graph-structured data. \n2. This paper conducts experimental evaluation on seven node classification benchmarking datasets. ", "weaknesses": "1. The paper's presentation is difficult to follow, which may make it challenging for readers, especially for those who do not have strong background knowledge on this topic hard to understand the proposed method and its contribution.\n2. The proposed method has poor performance, which is reflected in the experimental results presented in the paper. \n3. Some relevant literature has not been cited in the paper, which could suggest that the authors have not conducted a thorough review of the existing research in this area. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer ssFv for their comments. We addressed all questions below.\n \n- W1: `` The paper's presentation is difficult to follow.``\n \nWe appreciate the reviewer’s comments regarding readability. We spend significant efforts to find a good order of exposition and lengths of explanations under page limit constraints, but there is clearly always room for improvement. Nevertheless, we would like to point out that all other reviewers mentioned that our presentation is good (score 3). Moreover, Reviewer XfoH even explicitly mentioned that `` The problem and contributions discussed in the paper are clearly mentioned and the illustrations do a good job of conveying them.`` Reviewer tLab also mentions that ``The authors have effectively conveyed complex concepts and ideas in a well-structured manner.`` and put it as one of the strengths of our paper. We are already working on improving the presentation of our paper even further.\n \n- W2: `` The proposed method has poor performance.``\n \nWe respectfully disagree with this comment. Note that our proposed method outperforms or matches the prior state-of-the-art method GAP and all the other baselines in almost all cases. Even for a few cases for which DP-MLP has the best performance, our approach is still competitive with the other DP-GNN baselines. Note that it is reasonable that in some cases, DP-MLP can outperform DP-GNNs. See G1 in our general response for further discussion and examples.\n \nIn summary, we would like to emphasize again that our DPDGC model already has the overall best performance compared to other DP-GNN baselines. It is important to bear in mind how difficult it is in practice to ensure provable privacy guarantees for graph-based learners with satisfied utility.\n \n- W3: ``Some relevant literature has not been cited in the paper, which could suggest that the authors have not conducted a thorough review of the existing research in this area.``\n\nWe thank reviewer ssFv for bringing to our attention the paper of Zhang et al. [ref 1]. We will include it in the related work section of our revision. However, we would like to point out that [ref 1] considers the case that the training graph and test graph are disjoint. Hence, they only need to ensure GNN weights are DP. Their method cannot be extended to the more challenging setting where training nodes are reused for inference, as is the case of our work and the common node classification scenario. See page 7 in [ref 1]. As a result, we cannot compare [ref 1] with GAP and our approach. Furthermore, their method can be viewed as a privatized version of APPNP [ref 2], which is unable to learn well on heterophilic datasets [ref 3]. In contrast, our DPDGC can work well on heterophilic datasets. \n \n- Q1: `` How can one determine the appropriate value of K for a given dataset?``\n \nOne should treat the parameter $k$ in our $k$-neighbor-level GDP similar to $(\\epsilon,\\delta)$ as in approximate DP (see our discussion in lines 348-352); it serves as a design parameter specifically tailored to graph datasets. The appropriate value of $k$ can be determined by considering the level of sensitivity in revealing a portion of edge information. In practical implementations, the model holder (e.g., the server) should proactively choose privacy parameters $k$, $\\epsilon$, and $\\delta$ in compliance with regulations or users' agreements. While we demonstrate the utility-privacy trade-off for different choices of $k, \\epsilon, \\delta$, the final choice should be made by the practitioners in the field.\n \n- Q2: `` In the case of the Pubmed and Cora datasets, why do the results of graph-based machine learning methods remain unchanged across different values of K, and what implications does this have for the use of these datasets in research?``\n \nNote that GAP and the other DP-GNN baselines are unaffected by the choice of $k$, as already discussed in Section 5. The main reason behind this finding is their “coupling” design, i.e., the use of the product of $A$ and (a function of) $X$. We also give a detailed discussion and simple example explaining why prior DP-GNN models are not affected by the choice of $k$, see lines 244-251. On the other hand, we would like to point out that our DPDGC ***does offer different performance*** for different choices of $k$. Please check our Table 3 and Figure 3 for details. Also check our updated Table in the general response.\n \n- L1: `` The utility of the proposed method is limited, as the privacy protection achieved with a privacy budget of eps=16 is too weak ...``\n \nWe would like to point out that our method already outperforms the state-of-the-art DP-GNN method, GAP, across different datasets and privacy parameter settings. We also want to point out that the authors of GAP also choose $\\epsilon=16$ to demonstrate the utility of DP-GNNs for node-level DP experiments. While we agree that $\\epsilon=16$ may be too weak in practice, we are not aware of any other methods that outperform our DPGDC and we do test for different $\\epsilon \\in \\\\{ 1,2,4,8,16 \\\\}$ in Figure 3. In fact, our novel $k$-neighbor-level GDP definition partially addresses the issue that node-level GDP with low $\\epsilon$ results in poor utility. We hope the reviewer ssFv can appreciate the challenging nature of the problem of graph privacy and our contribution given the pointers above.\n \nPlease feel free to let us know if there are follow-up questions. We will try our best to address them in a timely manner.\n\n### Reference\n\n[ref 1] Towards Training Graph Neural Networks with Node-Level Differential Privacy. Zhang et al. arXiv preprint arXiv:2210.04442.\n\n[ref 2] Predict then Propagate: Graph Neural Networks meet Personalized PageRank. Gasteiger et al. ICLR 2019.\n\n[ref 3] Adaptive Universal Generalized PageRank Graph Neural Network. Chien et al. ICLR 2021.\n"}, {"review_id": "i7YpUc1dlr", "reviewer": "Reviewer_fPNi", "summary": "Graph neural networks have privacy leakage in both their topology information and node attribute information. This paper proposes a differential privacy framework to protect both graph topology and node attributes. A model that decouples graph convolution and node attribute embedding is proposed. ", "questions": "1. It was not immediately clear by the end of Section 5 that the output of DP-MLP_W is also designed to be DP, hence the overall framework is DP due to the composition theorem. It caused some confusion for me and I would appreciate if this point is emphasized since DP-MLP_W is never discussed in detail throughout the paper. \n\n2. How is the MLP in Table 3 trained to achieve GDP? If the MLP is GDP and protects graph information (i.e., using the individual outputs from the MLP applied to individual nodes, one cannot easily infer if there are edges between them), why does it perform significantly better than DPDGC or DP-SAGE?\n\n3. On the heterophily datasets, the reduction in test accuracy is very significant compared to the non-private scenario. What is causing this? A detailed discussion should be added.\n\n4. How tight are the bounds in the theoretical results in Section 5 and are these used directly in the DPDGC model or is the model tuned instead based on an empirical estimate of its GDP?\n\n5. What is the computational complexity compared to baselines? Is a distributed implementation using message passing possible? \n", "limitations": "Yes", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "A graph differential privacy (GDP) framework is proposed for GNN models. Theoretical GDP guarantees are provided.", "weaknesses": "1. A weakness of using the differential privacy (DP) metric is the significant deterioration of utility (in this paper, it is the node classification accuracy) for even a very generous privacy budget. As seen in Table 3 and Figure 3, \\epsilon=16 has to be set to achieve reasonable accuracy (except for the simplest case of edge-level privacy). However, even with such a generous budget, the test accuracy drops significantly compared to the non-private case. One should question if DP is indeed the proper framework to use in GNN (despite its popularity in database privacy). For example, there are frameworks on *inference* privacy that specifically protect certain private attributes instead of the full \"data\" (graph topology  + features), which are more applicable in practice. \n\n2. By decoupling the graph adjacency information A from the node attributes X, the model can no longer benefit from graph aggregation and local node processing. This also explains why the proposed model does not perform well on homophily datasets. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer fPNi for their thoughtful feedback, comments, and positive assessments of our work. All questions are addressed below.\n \n- W1: ``A weakness of using the differential privacy (DP) metric is the significant deterioration of utility … for even a very generous privacy budget. … One should question if DP is indeed the proper framework to use in GNN (despite its popularity in database privacy).``\n \nThis is indeed an interesting comment. Please see G3 of our general response.\n  \n- W2: ``By decoupling the graph adjacency information A from the node attributes X, the model can no longer benefit from graph aggregation and local node processing.``\n \nThank you for pointing this out. We have indeed discussed this issue and described it in our “limitation” section in the Appendix (lines 506-512). The key contributions of our work are to introduce new differential privacy criteria for graph learning tasks and establish theoretical privacy guarantees for different learning settings. Decoupling the graph adjacency matrix allowed us to better control the privacy-utility trade-offs and it was fundamental for motivating partial topology privacy concepts such as $k$-neighbor-level GDP. Note that traditional message-passing designs mostly focus on the utility aspect of GNNs: Whether there exists a GNN design that can achieve our $k$-neighbor-level GDP and offer similar utility as standard message-passing GNNs remains a challenging open problem. It is also worth noting that LINKX [38] also adopts a similar decoupled structure and empirically demonstrates strong (nonprivate) performance on heterophilic datasets. Nevertheless, that work does not study privacy-related features of decoupling.  \n- Q1: ``It was not immediately clear by the end of Section 5 that the output of DP-MLP_W is also designed to be DP, …``\n \nWe apologize for the confusion. Once we obtain the cached intermediate embedding $Z$, the remaining DP-MLP modules are trained with DP-SGD in an end-to-end fashion. We will clarify this point in our revision.\n \n- Q2: ``Questions about DP-MLP``\n\nPlease see G1 in our general response. \n\n- Q3: `` Why on the heterophily datasets, the reduction in test accuracy is very significant compared to the non-private scenario.``\n \nThis is a good question. We conjecture that the beneficial information in Squirrel and Chameleon datasets is relatively delicate. That is, most node embeddings are close to the classification boundaries of GNNs even if they are correctly classified in the non-private case. Thus, adding noise during the computation of $Z$ embedding may greatly obfuscate these beneficial signals. It is unclear at this point why this phenomenon happens, and we hope to further investigate it in the future. \n \n- Q4: ``How tight are the bounds in the theoretical results in Section 5 and are these used directly in the DPDGC model?``\n \nNote that DP is defined with respect to the worst case scenario, and following our proof in Section 5, one can easily construct a worst case pair ($(X, A)$ and $(X’, A’)$) such that the bounds are tight, implying our bounds are worst-case optimal. On the other hand, we use a tight upper bound on sensitivity in our experiment to obtain a practical GDP guarantee. As stated in Appendix I (line 677), we use autodp for privacy accounting (which adopts privacy amplification via subsampling and compositions via Renyi DP). We note that the conversion from RDP to approximate DP  (Lemma F.1) is known to be nearly optimal and has been used in most practical DP frameworks.  \n\n- Q5: ``What is the computational complexity compared to baselines?``\n \nThe computational complexity of DPDGC and GAP are roughly the same. Note that the bottleneck of the computational complexity is the operation $AX$, $AH$ (GAP), or $AW$ (DPDGC). We set the (hidden) dimension of $W$ to be 64 (Appendix I, line 680), which is usually smaller than the feature dimension of $X$. As a result, the computational complexity of DPDGC, GAP, and the other GNN baselines are similar. Note that the implementation of DPDGC and message-passing in Pytorch Geometric already uses sparse tensor/matrix multiplication to speed up the computation of $AX$, $AH$, or $AW$. Furthermore, similar to LINKX [38], DPDGC by default can support the arbitrary size of mini-batch training and is thus scalable. Please see G2 in our general response for further discussion.\n \nPlease feel free to let us know if there are follow-up questions. We will try our best to address them in a timely manner. \n"}]

Author rebuttal:
We appreciate the time and effort of all reviewers and the AC. The reviews indeed provided helpful feedback. In this general response, we elaborate on some common questions raised by the reviewers (G1, G2). We also highlight some thoughtful questions and comments that initiate valuable discussions (G3, G4).

- G1: ``Why simple DP-MLP has the best performance in some cases and how is it trained`` (Reviewer fPNi, WwFs)

Note that the DP-MLP model does not leverage the graph structure information $A$. Hence, it does not need to pay an extra privacy price for protecting the graph structure. DP-MLP is simply trained with DP-SGD to achieve the same $(\epsilon,\delta)$ guarantees from the DP definition. Roughly speaking, DP-MLP can spend the whole privacy budget $(\epsilon,\delta)$ on DP-SGD training. However, both GAP and DPDGC need to spend some privacy budget to account for protecting $A$, such as the PMA module and multi-step training. As a result, DP-MLP requires less noise during training compared to GAP and DPDGC. Hence, DP-MLP might outperform GDP-GNNs such as our DPDGC when the benefit of graph structure information is insufficient to compensate for the additional noise needed for a GDP guarantee.  

Consider an extreme example, where $X = Y$ and $A$ is purely random (i.e., generated from Erdos-Renyi random graph model with edge probability 1/2). Clearly, introducing $A$ will not benefit the node classification accuracy. However, in order to make the graph algorithm GDP, we still need to pay an additional privacy budget to “protect” the privacy of $A$. It is obvious that DP-MLP will outperform any possible DP-GNNs in this case. For further discussion on how to characterize graph structure information, see our response to Q4 of reviewer XfoH.
 
- G2: ``Performance on large homophilous graph datasets`` (Reviewer fPNi, tLab, WwFs)
 
We are also very interested in conducting experiments on them. Unfortunately, the Opacus library (library for DP training) currently does not support SparseTensor (see issue #579 of Opacus GitHub repository) so we are unable to run tests on larger datasets. We believe that Opacus will support SparseTensor in a future version (as indicated by issue #350 of the Opacus GitHub repository by the creators) and we are willing to test on large graph datasets such as those in the Open Graph Benchmark repository.

- G3: `` A weakness of using the differential privacy (DP) metric is the significant deterioration of utility… One should question if DP is indeed the proper framework to use in GNN.`` (Reviewer fPNi)


While we acknowledge that there might be alternative definitions of privacy that could be considered "proper" for Graph Neural Networks (GNNs), we want to emphasize that Differential Privacy (DP) has emerged as the most widely accepted and implemented  privacy standard across various fields, including machine learning, database & privacy research communities as a whole. The adoption of DP algorithms and models by prominent tech companies like Apple and Google, as well as the U.S. Census Bureau's embrace of Differential Privacy for data privacy, all further highlight its practical relevance and applicability in real-world settings. Given the widespread acceptance and deployment of DP, we firmly believe that investigating GNN performance under DP requirements is both valuable in theory and practice.

On the other hand, we also acknowledge that requiring node-level Differential Privacy (DP) can significantly impact the utility of GNNs or necessitate a high privacy budget to maintain reasonable utility. In fact, we are the first to highlight this limitation of DP-GNNs, as prior works (e.g., GAP) only demonstrate the case where GAP outperforms MLP on three datasets. In contrast, our extensive testing on seven datasets reveals this phenomenon, underscoring the importance of addressing this challenge. It remains an interesting and open problem to explore whether a DP-GNN design can achieve node-level DP with a moderate privacy budget while maintaining comparable utility, or whether there is a fundamental price to pay for node-level DP.

The above observations motivated us to introduce the concept of "k-neighbor-level" DP. As mentioned in our paper (lines 56-64), selecting $k = 0$ implies no privacy protection on the graph structure, while $k=n$ indicates node-level DP.  In other words, it offers a trade-off between the edge information and utility and mitigates the possibly overly pessimistic node-level DP. It is also worth noting that in many practical scenarios, edge information can be less sensitive than node features, making this notion of privacy particularly useful in various applications.

Lastly, we recognize that further research is necessary to determine whether the extent of utility drop is indeed the fundamental privacy price we must pay in the graph learning scenario. Nonetheless, exploring this aspect lies outside the scope of this single paper, but we hope that future studies will provide new answers to the challenging graph DP problem.

- G4: `` The novelty of DPDGC with respect to LINKX`` (Reviewer WwFs)
 
Note that we cited LINKX [38] in the original manuscript on line 198, where we also mentioned that our DPDGC is motivated by LINKX. We would like to emphasize the key novelty of DPDGC with respect to LINKX. LINKX focuses on learning with heterophilic graph datasets, and the authors purely focus on the utility aspect of the graph learning problem. In contrast, we are the first to identify and study the theoretical privacy benefit of this decoupled graph convolutional design and propose a corresponding privatization design. None of these ideas appear in the LINKX [38] paper or other prior literature. Furthermore, all prior DPGNNs leverage the “standard coupling graph convolution” design as their building block, which is significantly different from our approach. Thus, we believe that our DPDGC model is significantly novel.



Meta-review: This paper was a borderline case for which the reviewers did not come to a consensus regarding the acceptance or rejection of the paper. Several reviewers also had limited confidence in their evaluation. Consequently, the Area Chair also looked closely at the paper in addition to the reviews, author response and discussions. While this work has some shortcomings, it appears to be a worthy addition to the DP-GNN literature:
- It introduces a new variant of DP for graphs which interpolates between edge DP (often considered too weak) and node DP (often too strong to yield any utility);
- It proposes a new GNN architecture well-suited to privacy, along with a clean privacy analysis.
- It provides a solid empirical evaluation showing the relevance of the proposed privacy notion and architecture, but also the limitations of DP in certain regimes.

For these reasons, I recommend acceptance.
Decision: Accept (poster)