Individualized Private Graph Neural Network via Node Influence-based Noise Adaptation

• The definition of privacy pertaining to graph settings is unclear.
• The clarity of Section 4 needs significant improvement.
• The logic and reason of the proposed methods are not conveyed clearly.

Detail comments

I have mixed feelings when reading this paper. Everything before Section 3.1 is very well-written, but Section 4 (methodology) makes me feel like it is written by a completely different person. It is not polished, and there are many typos and errors in the notations. The excessive amount of those errors even makes it hard to understand why the proposed method is reason at a high level. It is clearly subpar of top ML conferences like ICLR and I hope the authors can at least polish their Section 4 to the quality of their introduction. Please see my question sections for the subset of errors and typos that I found.

Another issue is that the privacy definition in Section 3.2 is not clear. Is Definition 1 based on add-remove DP or replacement DP? If it is the former as in Sajamanesh et al., 2022, then the corresponding definition 4 is problematic as explained in Chien et al. 2023. Note that removing one node can already cause the dimension of the node embedding matrix $H$ to be different on the adjacent dataset, which makes it impossible to achieve DP. It might make sense if the authors adopt the replacement DP definition, but in this case, the required noise is also large as argued in Chien et al. 2023. I feel the authors should have a detailed discussion on why exactly the privacy definition they are considering.

In summary, I really like the idea that the authors proposed. I do think allocating privacy budget/noise according to the noise importance/influence is the correct direction for better privacy-utility trade-off in DP-GNN. Unfortunately, the authors did not convey clearly why the approach they proposed makes sense. I hope the authors can carefully polish their manuscript and really make this great idea work.

1. You say that your model could get a trade-off between the privacy and performance, how did you show this in the experiment?

1. The research problem is suggested to be formally proposed in section 3.2.
2. Wrong statement. Note that the community recognizes that a lower epsilon indicates a higher level of privacy protection. However, the statement in line 178 violates the definition of DP. The “Compared” should be “compared” in line 308. Authors are suggested to proofread and revise this paper carefully.
3. Vague statement. Authors are suggested to explain the motivation of section 4.1, the reusable privacy ratio in line 286, and the process of obtaining the budget ratio of equation 11. The derivation of equations 12 and 14 is not provided. In the appendix (lin 772), the first + is obtained without showing details. Authors are suggested to carefully revise this paper by providing more details and a smooth logical flow.
4. Missing evaluations. According to definition 1 of this paper, the neighbour graphs are different in their node features, links and labels. This paper also involves the design of edge and label noises. However, this evaluation only focuses on the MIA and ignores the evaluation of edge privacy and label privacy. Authors are suggested to provide sufficient privacy evaluation to verify the effectiveness of the proposed method. A possible evaluation method could be found in Meng, Lingshuo, et al. "Devil in Disguise: Breaching Graph Neural Networks Privacy through Infiltration." Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security. 2023.
5. Limited Scalability Evaluation and Efficiency Concerns: The adaptive noise allocation relies on calculating each node's influence based on the centrality and neighbourhood structure, which is computationally expensive, especially for large or dense graphs. A scalability analysis in terms of time complexity and memory usage would strengthen the paper’s claims on practicality and applicability to real-world datasets. Consider adding a complexity analysis and reporting runtime and memory usage across different graph sizes and densities. Alternatively, discuss possible optimizations to the TNIE calculation, such as approximations for influence estimation that reduce computational cost without sacrificing significant accuracy. Exploring parallel processing or sampling methods for large graphs could also enhance scalability.

1. The literature review and experimental comparisons are insufficient. At least two relevant works on node differential privacy (DP) in GNNs, DPAR (https://arxiv.org/abs/2210.04442v3) and https://arxiv.org/abs/2311.06888, are omitted. Experimental results on the Cora (similar to Cora-ML used in DPAR) and Facebook datasets show that this paper’s performance is significantly inferior to these papers. To provide a fair comparison, the authors should benchmark all methods on Cora-ML, Pubmed, and Facebook datasets, using multiple values of epsilon rather than just one, as currently done.

2. Definition 2 incorrectly states that a "higher epsilon means higher protection," when in fact a higher epsilon implies weaker privacy protection.

3. There is no explanation for the vector “u” in Equation (6), leaving the reader unclear about its role.

4. Equations (7), (8), and (12) iteratively use node degrees to compute node embeddings and scores. However, node degrees vary between neighboring datasets. The paper lacks a DP mechanism to protect this private information and violates node privacy.

5. Theorem 3 references “Algorithm 1,” which does not appear in the paper. The paper would greatly benefit from presenting a complete algorithm to clarify each module’s execution order and purpose. It is unclear if the missing Algorithm 1 was intended to serve this function.

6. In this paper, noise is added to the aggregation results in the first layer of the GNN and then added again to the adjacency matrix used in subsequent layers. The rationale for this is unclear. Why not simplify it by directly adding noise to the adjacency matrix?

7. The experimental setup lacks a sufficient range of epsilon values. For utility experiments, epsilon should range from 4 to 16, as in https://arxiv.org/abs/2311.06888, to provide a more comprehensive evaluation.

8. Typos, e.g., in Section 4.3 and Eq. (20).