- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper investigates the memorisation problem in GNNs via gradient behaviour, extending the existing understanding in the memorisation problem beyond NCMemo, and investigates the implications on privacy. The investigation includes experiments on common architectures on both synthetic and real graph datasets.
Critical strengths
The experimentations cover common GNN architectures with extensive ablation studies in the appendices
Critical weaknesses
- The authors "defines" and "introduces" LMS and AWS metrics without properly crediting their similarities to the prior works [1]. LMS is a rewritten from Section 4.1 p.4 in [1], and AWS follows the procedure from Section 6.1, p. 7 in [1]
This limits the novelty of the general work as the paper mostly uses or adapts the existing measures and experimentation procedures.
- The theoretical front is weak, where the propositions are just restatements of the empirical observations.
[1] Maini, Pratyush, et al. "Can neural network memorization be localized?." arXiv:2307.09542 (2023).
Questions for authors
Can the authors please clarify what the "GNN-specific mechanism" is?
the gap between them increases with layer depth, indicating that in GNNs, memorization is distributed across all layers but becomes increasingly dominant in deeper layers.
Can the authors also clarify the causal relation between the widening LMS node gap and the memorisation. Could that be e.g. empirically observed through the retrievability of the node embedding at shallow vs deep layers?
3 comments
Response to Reviewer DTzd (2/2)
Q1: What the "GNN-specific mechanism" is.
By the "GNN-specific mechanism", we refer to the role of message passing and graph-coupled computation in shaping how memorization occurs and is distributed within GNNs. Specifically, our findings reveal three phenomena of this mechanism, including (i) Layer-wise gradient contributions, (ii) Homophily-dependent gradient alignment, and (iii) Concentration of memorization. The detailed clarification of these three phenomena caused by the "GNN-specific mechanism" is presented in the response to the W1.
Q2: Causal relation between the LMS gap and memorization.
Following the Reviewer's suggestion, we additionally conducted a retrievability experiment to empirically investigate how the memorization relates to the layer-wise LMS gap. The experiment follows these steps: (1) We use the same GCN as in the paper to train and freeze the model (syn-cora, memorization rate ); (2) We run a forward pass on the model and extract the representations of all nodes at each layer: input features - , the output of Layer 0 - , the output of Layer 1 - , and the output of Layer 2 - (the logits); (3) For each layer, we train a linear probe using each layer's representations, only on clean training nodes, thereby preventing the probe from directly memorizing the noisy labels; (4) For all mislabeled nodes, we calculate the fraction of fitted memorized nodes which the corresponding probe predicts the assigned (noisy) label.
| Homophily level | Input X | Output of Layer 0 | Output of Layer 1 | Output of Layer 2 |
|---|---|---|---|---|
| h=0.00 | 0.014 | 0.035 | 0.072 | 0.923 |
| h=0.50 | 0.009 | 0.013 | 0.184 | 0.914 |
| h=1.00 | 0.007 | 0.021 | 0.304 | 0.966 |
The results show that the memorized label becomes increasingly retrievable across the layer depths, e.g., in the setting, the fraction increases from 1.4% at the input features to 92.3% at the final layer. A similar increasing trend is observed across all three homophily levels. These findings indicate that memorized information becomes more accessible in deeper GNN layers. From Figure 1 in the paper, we can observe that the layer-wise LMS gap also increases with layer depth. Together, the two results support the connection between the memorization and the LMS gap. We have added these results and analysis in Appendix E of the revised paper.
If these clarifications address the reviewer's comments, we would be grateful if they could update their score accordingly.
Request to respond to the rebuttal
As the rebuttal period is coming to an end, we would like to thank the Reviewer again for their constructive feedback. We would like to highlight the additional experiments, theoretical clarifications, and analyses we have provided in response to address their concerns:
- Novelty and GNN-specific contributions (W1, Q1): We have further clarified three GNN-specific memorization phenomena: (i) layer-wise gradient contributions, which distinguish GNNs from conventional DNNs (Maini et al., (2023) [1]); (ii) homophily-dependent gradient alignment; and (iii) concentration of memorization-critical weights in the final layer.
We have also conducted additional experiments to validate these findings across different architectures and settings (see Section 5.2, Appendix N, Appendix J, Appendix G, Appendix H of the revised paper).
-
Theoretical contributions (W2): We have provided formal proofs of Propositions 1 and 2 in Appendices F and G, respectively, and revised their statements in the main paper to distinguish them from the empirical observations clearer. In particular, these propositions characterize how graph homophily affects gradient alignment and explain why the final layer provides a low-cost pathway for memorization in GNNs.
-
Causal relationship between the LMS gap and memorization (Q2): We have conducted an additional retrievability experiment using linear probes trained on clean training nodes. The results show that the memorized labels become increasingly retrievable across GNN layers, supporting the connection between memorization and the layer-wise LMS gap. We have included the experimental results and analysis in
Appendix E.
We believe these additional experiments, analyses, and theoretical clarifications have further demonstrated the novelty and significance of our contributions. We would be grateful if the Reviewer could review our responses and consider updating their rating accordingly. We would also be happy to address any remaining questions.
Response to Reviewer DTzd (1/2)
We thank the Reviewer for acknowledging that our experimentations cover common GNN architectures with extensive ablation studies. We also appreciate the constructive comments, which have helped us better sharpen the GNN-specific contributions of our work.
To the best of our knowledge, our work presents the first systematic study of memorization localization in GNNs. Specifically, we adapted gradient accounting and greedy neuron removal in [1] to the graph setting. More importantly, this study reveals several previously unexplored, GNN-specific properties of memorization in GNNs:
Layer-wise gradient contributions: We find that, in GNNs, memorized nodes exhibit larger gradient contributions than non-memorized nodes across all layers, with the gap increasing with layer depth. This is different from the findings of Maini et al., (2023) [1], who show that in DNNs "no layer receives significantly more contribution from memorized examples than from clean examples" (Figure 1 in [1]). We have conducted additional experiments using an SGC-style graph neural network and a standard MLP to demonstrate that this observation is specific to GNNs with learnable message-passing layers (see
Section 5.2of the revised paper). Specifically, in these GNNs, graph propagation is integrated into the learnable layers, resulting in graph-coupled computations which influences how memorized information is distributed across layers.Homophily-dependent gradient alignment: We find that the gradients of memorized and non-memorized nodes are more positively aligned in heterophilic graphs, but become increasingly opposed as graph homophily increases. This reveals a relationship between a fundamental graph property, i.e., homophily, and the gradient alignment of memorized and non-memorized nodes. We have further validated this finding across a range of settings: (i) general GNN architectures, such as GCN and GAT; (ii) a heterophilic-aware GNN architecture, H2GCN (see
Appendix J); (iii) large-scale graph datasets, including ogbn-arxiv, Coauthor-CS, and Coauthor-Physics (seeAppendix N); and (iv) a more advanced GNN architecture, Graph Transformer (seeAppendix N).Concentration of memorization: We observe that memorized nodes exhibit concentrated memorization in GNNs, with memorization-critical weights located primarily in the final layer. We also provide a theoretical analysis to explain this observation (see
Appendix G). Furthermore, we have conducted additional experiments on layer-wise ablation sensitivity and layer-wise collateral prediction changes (seeAppendix H) to verify that the final-layer memorization concentration is GNN-specific due to the different graph-coupled collateral effects across GNN layers.Finally, building on these insights, we develop a targeted defense against privacy leakage. Our experiments demonstrate that this localization-guided defense achieves a stronger privacy-utility trade-off than existing baseline defenses.
Overall, our contributions go beyond adapting existing techniques to GNNs. We provide a systematic study of memorization localization in GNNs, reveal graph-specific memorization phenomena that distinguish their behavior from that of conventional DNNs, and translate these findings into a practical defense. We have added these clarifications in
Section 5.2, Appendix N, Appendix J, Appendix G, Appendix Hof the revised paper.To provide theoretical support for our empirical findings, we present formal proofs of Propositions 1 and 2 in Appendices F and G, respectively. Following the Reviewer's suggestion, we have revised the Proposition 1 and 2 in the main paper to distinguish them from the empirical observations:
Proposition 1 (Gradient alignment decreases with homophily). Consider a non-memorized node and a memorized node sharing the same true class but assigned different training labels. Under the assumptions specified in Appendix F, the expected inner product between their gradients decreases as graph homophily increases, becoming negative in the high-homophily regime. See Appendix F for the formal statement, definitions, assumptions, and proof.
Proposition 2 (Final-layer weights provide a low-cost pathway for memorization in GNNs). Consider an l-layer GNN and a target node u. A perturbation δWk to the weights of layer k changes the logit of node u through the layer-(k-1) embeddings of u's (l-k)-hop neighbourhood. In contrast, a perturbation δWl to the final layer changes the logit of node u only through u's own embedding. Consequently, a low-cost way to memorize a node is to adjust the final layer's weights, leading to concentrated memorization-critical weights in the final layer.