Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a private algorithm for Graph Neural Networks at the node level. The algorithm is based on some modifications to the DP-SGD, and it applies to directed graphs. The authors analyze the privacy guarantees through Renyi differential privacy and give amplified privacy guarantees for their algorithm. Empirical evaluation is provided to demonstrate the efficacy of the proposed algorithm.
main_review: The extension of the DP-SGD technique to the graph neural networks is very interesting, and the empirical performance seems improved.  I have the below questions.

1. In algorithm 1, it aggregates subgraphs to get a set of subgraphs S_tr. And then it doesn't appear in any of the following steps. I'm confused about how it plays a role in the algorithm? 

2. One of the main modifications is that they subsample the neighborhood of each node to ensure that each node has only K neighbors. Then they add noise according to the sensitivity of aggregated gradient wrt an individual node. So basically, I think it works like using group privacy (also, there's a K*C term in lemma1). Somehow, I feel the algorithm just extends the traditional DP-SGD to something like the group privacy case (technically, the privacy is still at the node-level, but it just restricts the case to K corrected nodes). Then in the experimental sections, I feel the benefit over DP-MLP is from incorporating the graph information. Overall, the algorithm is not that very exciting. 

3. The paper claims that the mini-batch is uniformly sampled from all training nodes, which contrasts the sampling with replacement in the traditional method. What are the differences? There seems no discussion about why this modification is important for the privacy amplification results.

4. For Table 2 and Table 3, what's the privacy parameter epsilon?



summary_of_the_review: In summary, I think the technical contribution of this paper is not significant, but it's also worth having a DP algorithm for the GNNs.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This work studies the problem of ensuring node-level privacy when training GNNs.  This privacy setting is much stronger than edge-level privacy because it considers the impact a single node can have on training, which may be connected to several other nodes, whereas edge-level privacy considers only the impact of a single edge in the graph.  

main_review: 
The stated privacy parameters of 30 seems high, although there have been other industrial use cases with such parameters.  I would be interested to know whether edge-level privacy with significantly lower privacy parameters actually ensures more privacy, in some sense, than node-level privacy with such a high parameter.  For edge-level, one can make statements about how if a node has a bounded number of edges, then one can make a node-level privacy guarantee by multiplying the privacy parameters accordingly.  It may not always be the case that you can go the other way, where node-level privacy of 30 gives a much lower edge privacy guarantee.

The privacy guarantee does not seem surprising because if any node is guaranteed to have at most K neighbors, then the node’s influence expands to K other nodes.  That is, to ensure edge level privacy, constant noise would ensure constant privacy parameters, but considering addition or removal of K edges, adding noise proportional to K would ensure constant privacy parameters.  Is the analysis presented here some how improving over this intuition or is there a more technical reason why this intuition breaks down?  This should be made more explicit.

For the experiments section, the gradient clipping procedure depends on the data, in particular the scaling factor.  The scaling factor is fine-tuned on each dataset, so is privacy really ensured?  Furthermore, an exhaustive grid search is done over several hyper-parameters.  In Figure 1, it looks like DP-MLP does better than DP-GNN for moderate privacy parameters, say < 7.  Is there any reason for why this might be and at what point would one method do better than another?

Although the proposed procedure seems to improve over existing approaches for some privacy regimes, I would have liked to see more analysis on when the improvement actually occurs (when epsilon > some value).  Furthermore, there are several parameters that need to be tuned, so it is not clear if the extra privacy budget expended for choosing these parameters would actually lead to a better privacy guarantee than the edge-level privacy.  I also do not see the novelty in the algorithm, since we could just pre-process each node to have at most K edges then run an edge-level private algorithm to get the same node-level privacy guarantee.

### UPDATE ###
The paper could significantly benefit from the feedback given here and the comments they plan to make.  I am still not convinced of the novelty here in the privacy analysis.  The authors point out that "standard composition results do not allow for multiple changes in the input dataset" but DP ensures group level privacy, so in particular can ensure k*eps-DP for groups of size k.  I will keep my score unchanged. 

summary_of_the_review: Although the proposed procedure seems to improve over existing approaches for some privacy regimes, I would have liked to see more analysis on when the improvement actually occurs (when epsilon > some value).  Furthermore, there are several parameters that need to be tuned, so it is not clear if the extra privacy budget expended for choosing these parameters would actually lead to a better privacy guarantee than the edge-level privacy.  I also do not see the novelty in the algorithm, since we could just pre-process each node to have at most K edges then run an edge-level private algorithm to get the same node-level privacy guarantee.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper aims to achieve node-level differential privacy on GNNs. Through adding noises to calculated gradients at each optimization step, this work shows that trained GNN layer can be (α, γ) node-level Renyi differentially-private. Concretely, this work considers the 1-layer GNN case, and make the maximum degree of each node to be K. With these requirements, this work theoretically prove the scale of noises.

Its contributions are as follows:
1.	Propose the task of learning node-level differential private GNNs,
2.	Adapt DP-SGD to work on graphs, through extending amplified privacy guarantee,
3.	Evaluate proposed optimization algorithm on benchmark graph datasets. 
main_review: Strengths:
1.	It is the first work to provide strong privacy guarantees for each individual node in graph learning, and designs an optimization algorithm to achieve that;
2.	It theoretically proves that the proposed algorithm is guaranteed to be differential private;
3.	The paper is well-structured and easy to follow.

Weakness: 
1. This work proves the differential privacy only on 1-layer GNNs. The methodology is directly extended from (Abadi et al., (2015)) and Feldman et al. (2018), with the consideration that a subset of K neighbors could appear in each update step. However, usually two or more layers are used for the graph-related tasks. Showing the form of DP in the more general r-layer case would make the contribution more significant.

2. The experiments are not complete. Why other DP GNN approaches are not compared with? It only compared with vanilla GCN and MLP.

3. The introduction is a little unclear. It talks about “preserves the privacy of the features of each node (‘user’), their labels as well as their connectivity information”, which is a little vague and no examples are provided to show the kind of privacy it can preserve. From the methodology and proof part, it seems to be that whether the graph containing a certain node cannot be detected. As a result, the motivation and application of preserving this type of privacy is not well-introduced.

Besides, the introducing of background in introduction seems to be incorrect.  It introduced (Zhou et al., 2020b) as an existing work on “bi-partite graphs or node-level privacy without preserving individual connectivity”, but that work does not focus on graph at all. 

A typo seems to exist in proof of Lemma 7, should the ρ’ in first equation be changed to ρ?
summary_of_the_review: This paper considers the node-level DP problem on graphs, which is the first work on this task as far as I can see.  The problem is formally defined, and guaranteed privacy is proved. 

The methodology is directly extended from (Abadi et al., (2015)) and Feldman et al. (2018), with the consideration that a subset of K neighbors could appear in each update step. However, the proof is incomplete as only 1-layer GNN is considered. Furthermore, none of existing DP GNNs are adopted as baseline approaches.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper claim to proposed a novel training method of GNN under providing both node feature and adjacency privacy. Their main approach is to use existed differential privacy framework into GNN world. They claim that providing privacy on both node feature and their connectivity is novel. 
main_review: ## Strong pints
1. The main motivation of the paper is valid and active research area.
2. It was written well and reasonable clear.

## Weak Points
Even though I have no experiences on private networks, I did some reading on it but try to judge the paper on mostly point of GNN view.
Here is the points that I wanted to discuss with the authors.

1. Differentially private networks protect training data from the end user. In this submission it is not clear from whom we need to protect node features and adjacency. Sometimes I thought they tried to protect node features and adjacency of each node from all rest of the nodes, but not sure. Thus, the usage scenario should be given by a toy example. For instance in (Wu et al., 2021b) there is great example scenario where Bob is customer  has node features and Alice is ML developer has adjacency. Bob sends this data to Alice to develop a GNN for some specific tasks. Alice should provide a trained model where Bob cannot find any part of adjacency by querying to trained model. So their aim is to provide edge level data privacy. Here the aim is to provide privacy both node feature and edge information, it seems the node features and adjacency should not be known by other nodes. But what about server side if the model is centralize? Do the central model knows all raw train data? 

2. In Related Work section, Graph level prediction tasks was cited as they are in different contexts. However, graph based prediction or node level predictions are not so different to each other. Any GNN architecture can be used for either node (or edge) or graph level prediction. Just the differences is to apply graph level readout after last GNN layer. So, whatever exist in graph level task while preserving privacy should be direct competitor of the proposed method. 

3. Node based prediction under transductive problem settings is the easiest problem setting for GNN. Because there is just one graph and  the graph is known in advance. Transferabililty from train graph to the test graph is not the problem. As it is mentioned example scenario in Introduction, the method must be tested under inductive problem settings, where the GNN learns something from train graph ( in example large enterprise) and tested on test graph ( small enterprise). In this way we can see if the learned coefficient can be transferable to the another graph well or not.

4. The authors main concentration was on node level tasks. However there are much more important tasks on graph level prediction while node level privacy is still important (as the same scenario in Introduction, train graphs would belongs some enterprises and task would be predict something about each enterprise. Then we can test given new enterprise's graph by predicting enterprises level output).  The experiments can be extended on this context.

5. Although  (Wu et al., 2021a)'s proposition was tested on bipartite graphs (user to items graphs), since they used a general GNN (the GNN architecture was not changed for bipartite graphs), it can easily extendable on concerned dataset in the paper. Thus their proposal has strong connection to this paper. I think the differences should be discussed in the paper and their method should be used as another baseline.

6. Eq1 and Eq2 are not the general formulation of GNN. Usually we show it by message aggregation and update functions.  More specifically, the author defines GNN as arbitrary number of MLP on node features, aggregation operation based on graph adjacency, followed by arbitrary number of MLP on aggregated features. They used exactly one layer of aggregation but one or two MLP for both on node features and aggregated features.  For sure this equation defines a GNN, but not definitely GCN (Kipf 2016) GAT (velickovic, 2018) and other mentioned models (GIN, Xu 2018, GraphSage Hamilton 2017).

7. Seems in the literature, differentially private networks results were performed for different privacy costs(Abadi et al., 2016). In this submission, it is selected as \epsilon=30. It had better if we can see the result under different privacy cost in 2D plot, like Cost-accuracy scatter plot. I would like to know at what privacy cost, the accuracy of proposed method will be the same with non-private GNN.

8. Is there any specific reason to do analyse for just single GNN layer? Is it extendable for arbitrary number of GNN layers?

9. Does any specific GNN methods (GCN, GAT, ChebNet, GIN ...) perform better than others? In the paper just one type of special GNN (given in Eq1-2) is used. Can any well-known GNN be used in this context?



 

   




summary_of_the_review: Proposed method seems an application of existed DP method for the graph data. So the novelty of the paper is limited. Experimental section is insufficient. I recommend rejection for this paper.
review_title: null

Meta-review: This paper received some additional discussion between the reviewers and the area chair. The reviewers were largely unswayed by the author responses. One concern was the level of technical novelty, feeling that this was largely a straightforward adaptation of DPSGD (as, admittedly, most works in the DP ML setting are). The primary technical contribution may be the sampling amplification theorem, which one reviewer felt was also straightforward from previous work. Other criticisms was that the privacy parameter epsilon is rather large, and that results are restricted to 1-layer GNNs. Generally, the work did not feel very novel to reviewers from either the privacy or the GNN community. However, they felt that the paper could benefit substantially from exploration and implementation of the comments made in the responses, so the authors are encouraged to pursue those directions. Some of the many suggestions from reviewer Xcpu may help the authors make the paper appeal more to the GNN community.
Decision: Reject