DP-GPL: Differentially Private Graph Prompt Learning

The manuscript does not specify which neighboring relation / notion of graph privacy is considered.

We thank the reviewer for pointing that out. Our paper considers node-level DP, i.e., we aim to protect the privacy of the nodes used in the graph prompt training. We clarified this information in the introduction, related work, and method section of our updated paper.

The DPG-DGL-W+ procedure proposed in this paper is neither edge-level nor node-level private. Specifically, the partitioning/weighting procedure (Algorithm 2) depends on centrality scores, which depend on the graph adjacency.

We are happy to clarify our setup further to address this comment. We see the reviewer’s concern that the weight of a teacher will give away the connectivity of the training nodes, which could be considered as private information that is not supposed to leak. However, in the similar vein to standard PATE, we assume that the teachers and the training procedure of the student are kept secret, i.e., they are not visible to the outside world. The only part that is visible to the outside world is the student prompt. Thereby, the teacher weights are protected.

We have extended the paper by this explanation.

The manuscript does not provide sufficient background information to follow it without consulting prior work. Specifically, the general paradigm of graph prompt learning is only vaguely and indirectly explained by summarizing related work in Section 2.2. I would strongly suggest introducing a "background" section that defines a generic graph prompt learning procedure and explains the involved terminology (how are GNNs "queried", what is a "target prompt", what is a "shot" in the graph context, ...?)

We thank the reviewer for the suggestion. We have extended the "background" section in the revised manuscript, see Section 2.2.

The related work section does not discuss prior work on DP for graphs, such as DP graph analysis [3], specialized DP-SGD for graphs [4], specialized DP-GNN architectures [5], or PATE for graphs [6] (see [1] for a survey).

We thank the reviewer for the suggestion. We have added a discussion of prior work on DP for graphs in the related work section in the revised manuscript, see Section 2.4.

The results only specify ϵ, but not δ of the (ϵ,δ)-DP prompts (e.g. Table 1).

We have updated the tables accordingly.

The reported accuracies in Tables 1,5,7-11, even without DP guarantees (ϵ=∞), are very low. One could probably achieve much higher accuracy by discarding the private data and performing standard semi-supervised learning on the public subgraph of Cora/Citeseer/PubMed. This calls into question why one would want to use prompt learning in the first place.

The low performance observed stems from the fact that we only operate in the 5-shot setting. However, not every private task can be trained based on some public equivalent. Using graph prompting allows us to adapt the GNNs to private tasks that differ from publicly available tasks. For instance, we can leverage graph prompt learning to effectively and efficiently adapt a pre-trained GNN model, which is pre-trained on edge prediction tasks, to a node classification downstream task.

The overall privacy guarantee should be (maxϵ1,…,ϵN,δ)-DP, because the definition of DP involves worst-case pairs of datasets (i.e., we have to make the pessimistic assumption that the modified data is used to train the least private teacher).

In our paper, we presented the (min_ϵ, max_ϵ)-DP guarantee of DP-GPL+W. This is in line with the reporting of privacy guarantees under heterogenous DP [A] which reports (min_ϵ, …, max_ϵ), showing the epsilon for every privacy group. We shortened it to (min_ϵ, max_ϵ)-DP. In the updated version of the paper, we have changed to reporting (max_ϵ, δ)-DP, but for completeness, provided table 12 in Appendix A.4.4 where we report (min_ϵ, …, max_ϵ)-HDP.

References

[A] Mohammad Alaggan, Se ́bastien Gambs, and Anne-Marie Kermarrec. Heterogeneous differential privacy. Journal of Privacy and Confidentiality, 7(2), 2016.

Thank you, your rebuttal addresses many of my listed concerns.

However, my main concern, i.e., non-privacy of DP-DGL+W remains. To clarify, the issue arises even when the teacher prompts are obfuscated.

The GNNMax privacy analysis in the paragraph "Noisy Teacher Vote Aggregation" of Section 4.2 assumes that the teacher weights $w_i$ are constant. It only accounts for the sensitivity of the teacher votes $y_i$.
However, due to being a function of centrality scores, they are data-dependent and we may have $w_i(A) \neq w_i(A')$ for two adjacent adjacency matrices $A \simeq A'$. A valid privacy analysis would also need to take into acount the sensitivity of $w_i(\cdot)$ and the resultant sensitivity of the aggregated teacher vote.

There is a chance I might be missing something. If your method accounts for this data-dependence, feel free to point me to the corresponding section in your paper or the PATE paper.

Let me maybe rephrase differently: Your analysis assumes that there is a single, constant "weight" $w_i$ per teacher. Instead we have different weights $w_i(A)$ and $w_i(A')$ when consering any two adjacent graphs. Thus, the heterogeneous per-teacher sensitivity, which should be data-independent for GNNMax to provide valid guarantees, is ill-defined.

This is the same issue that is discussed in literature with local sensitivity analysis (propose test release / smooth local sensitivity).

Also, without further analysis of how the centrality scores behave, we have to make the worst-case assumption that we have $w_i(A)=0$, $w_j(A) =1$ for the original graph and $w_i(A')=1$, $w_j(A')=0$ for the modified graph with some $i \neq j$, which means that the aggregate prediction can change arbitrarily.

Disclaimer: I will likely not respond to additional comments on this issue, unless you actually resolve some fundamental misunderstanding on my end.

Should it be better to bring algorithm 3 into the main body of this paper?

We thank the reviewer for the suggestion. We didn’t bring algorithm 3 into the main body due to the page length of the paper.

For the MIA experiment, LiRA attach originally reports true positive at low false positive, which is more sensible than the AUC metric. Have the author considered this?

We thank the reviewer for the suggestion. Instead of evaluating the worst case of MIA, i.e., true positive at low false positive rate, we aim to evaluate the overall performance of the MIA against graph prompt learning. Thus, we consider the AUC-ROC curves to evaluate the performance of the MIA, following the same evaluation metric as in [A] (Figure 2-b).

References:

[A] ”Flocks of Stochastic Parrots: Differentially Private Prompt Learning for Large Language Models”. Haonan Duan, Adam Dziedzic, Nicolas Papernot, Franziska Boenisch, NeurIPS 2023.

The current experiment section lacks a demonstration of MIA attack results after DP has been implemented.

We have conducted additional MIA experiments on the DP-protected models (DP-GPL and DP-GPL+W). Specifically, we also draw the AUC-ROC curves to evaluate the performance of the MIA against the DP-protected models. The results show that all curves are very close to random guess, which shows that our proposed methods are effective against MIA. For example, on Cora and GAT, the AUC score is 0.703 before applying our methods, while that is 0.526 and 0.550 after applying DP-GPL and DP-GPL+W, respectively. We have added the results in the revised manuscript, see Appendix A.4.8.

In the proposed method, there does not appear to be any protection for labels.

We adapted the paper to clarify our privacy setup. We aim to provide node-level DP. This aims at protecting the nodes, however, does not provide label privacy. Hence, providing label privacy is out of the scope of this work.

In DP-GPL+W, the teacher voting is weighted based on node centrality, and the partitioning strategy changes to outperform DP-GPL. Why is this effective? Could the author provide experimental or theoretical evidence, such as ablation studies?

We have conducted experiments to show the effectiveness of DP-GPL+W compared to DP-GPL. Specifically, we have compared the performance of DP-GPL and DP-GPL+W on three standard citation graph datasets (Cora, CiteSeer, PubMed), as shown in Table 1, 7-11 in the paper. The results show that DP-GPL+W outperforms DP-GPL in terms of privacy-utility trade-offs.

Is the proposed method only applicable to homogeneous graphs, or is it suitable for heterogeneous graphs as well?

There is no restriction on the graph data in our proposed method. As long as the teacher prompts can be trained on the private data, our method can output a private graph prompt for the downstream task. Taking the heterogeneous ogbn-mag network [A] from the OGB dataset suit as an example, we can first split the private nodes into different partitions where each partition contains nodes of different types, then train the corresponding teacher prompt on each partition.

The current experiments focus only on the k-shot scenario where k=5. Could performance comparisons for smaller k-values be added?

We thank the reviewer for this suggestion. We will include the experiments with smaller k-values in the revised manuscript.

Please clarify how your method addresses label privacy.

We aim to protect the privacy of the nodes in the prompt's training data, however, providing label privacy is not in scope. We have clarified this in the revised manuscript.

References:

[A] Kuansan Wang, Zhihong Shen, Chiyuan Huang, Chieh-Han Wu, Yuxiao Dong, and Anshul Kanakia. Microsoft academic graph: When experts are not enough. Quantitative Science Studies, 1(1):396–413, 2020.

It would be great if the authors could further clarify the DP settings used in the paper, e.g., node or edge differential privacy are considered.

Considering that the goal of graph-level DP is to protect the property of the graph, e.g., node degree, clustering coefficient, community structure, etc., and the goal of node-level DP is to protect the privacy of the nodes in the graph, e.g., node features, edges, and labels, we here focus on node-level DP as we aim to protect the privacy of the nodes used in the graph prompt training.

Also, note that there is no connection between the training nodes of the different teacher prompts, so the classical PATE privacy guarantee is still applicable in our case. We have added this clarification in the revised manuscript.

The partition scenario that utilize centrality score in DP-GPL+W doesn't seem to be satisfying the partition scenario in the original PATE paper [1].

In the original PATE paper, the partition could be non-randomly formed by either privacy or regulation concerns that are a priori to the actual execution of the training algorithms. However, in our paper, we first assign different weights to partitions according to the average centrality score of the private subset and then assign the same privacy budget for each teacher, i.e., ϵ=2 in our paper. Finally, the actual privacy cost for each partition is calculated following Algorithm 2 in [2].

Furthermore, the partition scenario that utilize centrality score in DP-GPL+W doesn't seem to be satisfying the partition scenario in the original PATE paper [1].

PATE can use arbitrary partitioning, the only requirement is that in the standard PATE the partitions are truly mathematical structures, so there is no data overlap between the partitions. For example, arbitrary partitioning is used in the CaPC framework [A] that leverages PATE and does not incur additional privacy costs. In Private kNN [B], based on PATE, every data point is a separate teacher. The selection of the data points to teachers is also specified explicitly in PATE [1]. Thus, the teachers can be created arbitrarily.

References:

[A] ”CaPC Learning: Confidential and Private Collaborative Learning” Christopher A. Choquette-Choo, Natalie Dullerud, Adam Dziedzic, Yunxiang Zhang, Somesh Jha, Nicolas Papernot, Xiao Wang, ICLR 2021.

[B] ”Private-kNN: Practical Differential Privacy for Computer Vision” Yuqing Zhu, Xiang Yu, Manmohan Chandraker, Yu-Xiang Wang, CVPR 2020.