Memorization in Graph Neural Networks

We thank the Reviewer for recognizing NCMemo as a novel framework for measuring per-node memorization in GNNs. We appreciate their acknowledgment of our deep investigation into the mechanisms behind GNN memorization, the connection to graph homophily, and the practical privacy mitigation approach through graph rewiring. Below we address the comments and questions.

Comparing rewiring against other defenses, e.g. label smoothing

Following the Reviewer’s suggestion, we include additional baselines. Eventually, we experiment with three approaches:

1. Graph Rewiring (Method described in the original submission): This technique relies purely on topological information such as node features indirectly improving the graph homophily level.
2. Label Smoothing: This regularization technique discourages overconfidence by training on soft probability distributions instead of hard one-hot labels. We use $\epsilon = 0.1$ for our experiments.
3. Rewiring+ Label smoothing: To analyze their interaction, we combined both methods.

Graph Rewiring:

Label Smoothing:

Rewiring+Label Smoothing:

Our results show that Label Smoothing and Rewiring+Label Smoothing, while lowering the memorization rate, they also generally reduce the test accuracy, compared to the original performance before applying defenses in Table 10, Appendix G. In contrast, graph rewiring improves the downstream performance, i.e., demonstrating a clear performance trade-off.

Finally, to show that this finding is independent of the choice of $\epsilon$ in Label Smoothing, we also include an ablation study with different $\epsilon = 0.1,0.3,0.5,0.7,0.9$ on syn-cora-h0.0. The results suggest that under each $\epsilon$, Label Smoothing yields a lower performance than rewiring, confirming this inherent trade-off.

syn-cora-h0.0:

Evaluating rewiring’s impact on downstream tasks that rely on original topology

To directly evaluate the rewiring’s impact on downstream tasks, we presented the testing accuracy before and after applying rewiring on synthetic datasets in Tables 10-12 in Appendix G. Additionally, we also present the downstream task performance before and after applying rewiring on four real-world graphs, in the following table. For simultaneous additions and deletions, the edge budget is 100. For only additions and deletions, the edge budgets explored are $\{5,10,50,100,500,1000,1500\}$ and the best performance is reported.

Comparing test accuracy before and after rewiring:

In line with graph rewiring approaches [57,32,25,31,51], the downstream performance improves over baselines highlighting the fact that the graph with original topology is usually suboptimal for the task, while rewiring improves.

Could the edge additions/deletions that reduce memorization negatively impact tasks where edge semantics are important (e.g., recommender systems)? Some discussion or a case study would strengthen the practical claims.

Graph rewiring is a well-established pre-processing technique from prior work that we adopt [57,32,25,31,51]. It is motivated by the common problem that real-world graph topologies are often suboptimal for GNNs due to bottlenecks etc.

As demonstrated in our paper (Appendix G, Tables 10,11,12), our application of feature similarity based rewiring [51] indirectly influences the graph homophily and is highly effective in reducing memorization while simultaneously improving downstream performance on node classification. This confirms its utility as a practical tool for mitigating the specific memorization issues we identify.

We agree that for tasks where edges have strict semantic meaning (e.g., chemical bonds in molecular graphs), modifying the graph without domain knowledge could be detrimental. Understanding how to perform "semantically-aware" rewiring in such domains is an important but orthogonal research question that is beyond the scope of our study.

Memorization indicator uses a fixed threshold of $\tau = 0.5$

We chose the threshold provided in the well-established foundational work on memorization by Feldman [21]. This allows our results to be directly comparable and situated within the broader literature on this topic. It is important to note that our main results (e.g., in Figure 2 of the paper) present the full, un-thresholded distribution of memorization scores to provide a complete picture; the threshold is only used for calculating aggregate rates like the Memorization Rate (MR).

To address the Reviewer’s comment, we also conducted an additional threshold-sensitivity analysis, reporting the average memorization score and memorization rate over various thresholds for the synthetic datasets and 4 real-world graphs Cora, Citeseer, Chameleon and Squirrel using GCN.

Synthetic Datasets:

Real-world graphs:

Across all thresholds, we can see the same trend, i.e., memorization consistently decreases as graph homophily increases, confirming that our findings are robust to the selection of the threshold.

We thank the Reviewer for their thorough assessment and for acknowledging that our work fills an important gap by studying memorization in GNNs and by highlighting that our empirical evaluation is sufficient and satisfactory. In the following, we address the Reviewer’s comments individually.

Describing the method on data partitioning

We describe the data partitioning in Section 5 (Experimental setup) of our paper. To further clarify, we follow the setup proposed in [59] and divide the training data into three disjoint subsets. We divide our datasets into 60%/20%/20% as training, testing, and validation sets, respectively. Out of the 60% training set S, we further randomly divide the datasets into three disjoint subsets with ratios $S_S$ = 50%, $S_C$ = 25%, $S_I$ = 25%. We use these sets to train two models. Model $f$ is our target model whose memorization we want to evaluate. Model $g$ is an independent model that we use to calibrate according to Equation (1), following the leave-one-out-style definition of memorization by Feldman [21]. Model $f$ is trained on $S_S \cup S_C$, and model $g$ is trained on $S_S \cup S_I$. $S_C$ is the candidate set, i.e., the nodes whose memorization we want to quantify. Models $f$ and $g$ are both trained on $S_S$, but only model $f$ is trained on $S_C$. Therefore, the difference in behavior between model $f$ and $g$ on $S_C$ results from the fact that $f$ has seen the data and $g$ has not, allowing us to quantify the memorization. Including $S_I$ into the training set of $g$ makes $f$ and $g$ have the same number of training data points, which allows model $g$ to reach the performance of model $f$. This makes sure that differences in behavior are not due to dataset differences. We added an extended section with this explanation to Appendix H.

Describing Equation (1)

Equation (1) follows the standard leave-one-out-style definition of memorization [21]. It operates on two models ($f$ and $g$) trained on the same dataset $S$, with the difference that for $f$, $S$ includes node $v_i$ and for $g$ it does not. The node $v_i$ is then the one whose memorization we aim to measure. The memorization is measured over the expectation of outcomes of the training algorithm. This means the expectation of behavior of models $f$ and $g$ on predicting the label of $v_i$ correctly as $y_i$. Intuitively, if $f$ is, on expectation, more capable of correctly predicting the label than $g$, this must result from the sole difference between the models, namely that $f$ has seen $v_i$ and $g$ has not. It hence quantifies $f$’s memorization on $v_i$. We also extended the explanation in Appendix H

Lack of proofs

We believe our paper's primary contribution is a comprehensive empirical investigation into the under-explored phenomenon of memorization in GNNs. Our work provides the first formal framework to address this problem, supported by rigorous experiments across 9 real-world datasets and 5 synthetic datasets with 3 GNN architectures, extensive analysis of training dynamics, and a new node-level metric (LDS). We extended our work with a more formal proof of Proposition 2, added to the appendix. Here, we provide the sketch of the proof.

Proof sketch: We delineate two regimes of learning:

1. High-homophily settings: In high homophily settings the GNN's inductive bias aligns with an informative graph structure, leading to a low generalization gap. Feldman's [21] Lemma 4.2 relates the generalization gap to the average memorization score. Given some distribution $P$, the learning algorithm $\mathcal{A}$, dataset $\mathcal{S}$, $\mathcal{E}^{train}$ is training error and $\mathcal{E}^{gen}$ test error we have

$\frac{1}{n}\mathbb{E}_{\mathcal{S} \sim P^n} \left[\sum^{i \in [n]} mem (\mathcal{A},\mathcal{S}, i) \right] = \mathbb{E}[\mathcal{E}^{train}] - \mathbb{E}[\mathcal{E}^{gen}] \approx 0$. (High homophily $\implies$ low memorization)

2. Low-homophily settings: For an atypical node $v_i$ with high LDS, the model trained without it, $f_{\mathcal{S} \setminus \{v_i\}}$, relies on uninformative graph, resulting in a high leave-one-out error $\mathbb{P}_ {f \sim \mathcal{A}(\mathcal{S} \setminus \{v_i\})}[f(v_i) \neq y_i] \to 1$. To achieve 0 training error $\mathbb{P}_ {f \sim \mathcal{A}(\mathcal{S})}[f(v_i) \neq y_i] = 0$, the model needs to memorize.

Feldman's Lemma 4.3 states $\mathbb{P}_ {f \sim \mathcal{A}(\mathcal{S})}[f(v_i) \neq y_i] = \mathbb{P}_{f \sim \mathcal{A}(\mathcal{S} \setminus \{v_i\})}[f(v_i) \neq y_i] - mem(\mathcal{A}, \mathcal{S}, i)$.

By substitution, we get $0 \approx 1 - {mem}(\mathcal{A}, \mathcal{S}, i) \implies {mem}(\mathcal{A}, \mathcal{S}, i) \approx 1$. Thus, in low-homophily, the model must force a high memorization to fit atypical nodes, confirming our empirical findings.

Relying on methods from other papers and low innovativeness

We respectfully disagree that our contributions are not novel. We rely on the well-established leave-one-out principle of measuring memorization because it is notably the most rigorous definition of memorization that has been established (see references [6, 21,59]). Yet our contributions go well beyond simply applying the framework to graphs.

Specifically:

1. To the best of our knowledge and as acknowledged by Reviewer FwDg, our paper is the first work to comprehensively analyze memorization in semi-supervised node classification;
2. We show a novel inverse relationship between memorization and graph homophily and link this to the GNNs’ implicit bias in leveraging graph structure during training;
3. We proposed a new metric, i.e., LDS to show that nodes with higher label inconsistency in their feature-space neighborhood are significantly more prone to memorization;
4. We empirically analyze the link between GNN memorization and privacy risks, highlighting the real-world impact of memorization on GNNs;
5. We also propose a graph rewiring framework as an initial strategy to mitigate memorization. The evaluation results show that it can reduce memorization while maintaining model utility. Further incorporating comments from Reviewers FwDg and uuwn, we have also added additional experiments:

i. Extended our framework to the graph classification setting on 4 datasets and showed promising connections to node feature noise and memorization rate.

ii. Additional experiments on Graph Transformers and large datasets such as ogbn-arxiv.

In summary, we provide an end-to-end analysis of the phenomenon of memorization in GNNs. Our work not only shows that GNNs memorize node labels, but also explains its emergence and provides an initial strategy via graph rewiring to mitigate memorization. Finally, we are also the first to show its practical implications for privacy risks.

Is it appropriate to define the GNN's memorization based on a single node (i.e., leave-one-out)?

It is appropriate to define the memorization in GNNs based on a single node, considering that the task is a node classification task. We then analyze the relationship between memorization and complex graph-specific elements, including graph-level and node-level characteristics and properties, e.g., graph homophily and LDS. In the response to Reviewer FwDg, we additionally show that our framework is not limited to instantiation on single nodes: To measure memorization for graph-level tasks, we show that our framework seamlessly extends to leave-one-out style definitions over entire graphs.

I suggest adding research about the 2-hop topology on graphs

We interpret the reviewer’s suggestion as a valuable question about whether our findings on memorization are robust to the GNN's receptive field size, or if they are merely an artifact of a 1-hop message passing scheme. To investigate this, we conducted additional experiments with another GNN variant called Simplified Graph Convolution (SGC) [A], which is designed to analyze the impact of multi-hop neighborhoods by propagating features over a specified number of hops, K. We ran our experiments using SGC with K=2, thereby allowing the model to aggregate information directly from the 2-hop neighborhood and present results on 4 datasets in the following table.

SGConv:

The results conclusively show that our core findings are robust to this change: Concretely, we observe the same strong inverse relationship between graph homophily and memorization rate when using a 2-hop aggregator. Low-homophily graphs (i.e., Chameleon and Squirrel) continue to exhibit significantly higher memorization, confirming that our conclusions are not dependent on a limited receptive field but are a more fundamental property of how GNNs learn on these graphs. We added these SGC results and a discussion to Appendix E to demonstrate the robustness of our framework.

Would it be better to fit the results reflected in Fig. 5 and 7 using a quadratic polynomial?

We thank the reviewer for the suggestion to explore polynomial fitting for the trends in Figures 5 and 7. Our objective in presenting these figures is to highlight the inverse relationship that exists between the alignment kernels and the memorization rate. Additionally, we believe that fitting a specific functional form would risk overfitting to the data and potentially introduce spurious artifacts. Our Pearson correlation analysis from the paper, which makes no assumptions about the parametric form of the relationship, already shows correlation coefficients r=-0.98 and r=-0.88 for synthetic datasets (presented in Section 4.2, Proposition 3) and r=-0.79 and r=-0.58 for real-world datasets (presented in Section 5.1) respectively strongly reinforcing our claims.

References:

[A] Simplifying Graph Convolutional Networks. Wu et al. ICML 2019.

We would like to thank the Reviewer for the detailed feedback, and for acknowledging our work’s contribution in filling an important gap in the understanding of generalization and privacy in graph learning, and for providing insightful results on the relationship between homophily, memorization, and label inconsistency. Below, we address the comments one by one.

The proposed NCMemo framework seems not including graph-specific techniques to tackle the interactions of graph elements.

Our framework builds on Feldman's leave-one-out definition [21], which is the de facto standard for studying memorization in classification tasks. Since our focus is node classification, this choice provides a well-established and principled foundation. By relying on our framework, we obtain multiple graph-specific findings:

i. We propose a novel inverse relationship between the node label memorization and graph homophily, the property of graph which directly takes into account if two connected nodes have the same labels.

ii. Our second novel contribution explains the emergence of memorization in GNNs through the lens of Neural Tangent Kernel and alignment matrices such as Kernel-Graph and Kernel-Target alignment [61] all of which show the implicit bias of GNNs to use the graph structure during the training.

iii. Our novel metric, the Label Disagreement Score, characterizes node atypicality by analysing the local anomaly in the node label. The node feature space allows us to precisely point out which nodes are highly susceptible to memorization.

iv. Our initial strategy to mitigate memorization leverages graph rewiring, that directly involves manipulating the edges of the graph based on feature similarity.

All of these elements directly use graph-specific elements and provide novel insights into graph-specific memorization.

Necessity of model pairs for assessing memorization and overhead

The leave-one-out memorization is theoretically well-founded and provides a precise notion of per-sample-level memorization. While the ideal form requires training multiple models, in our work, we approximate it efficiently: Our method only requires a single additional trained model and evaluates the effect for simultaneous removal of batches of nodes (25% of training nodes). This keeps the overhead minimal while still aligning closely with the theoretical definition. We also presented the empirical runtime for training models $f$ and $g$, calculating the memorization scores for the candidate set and calculating the LDS in Tables 14-16 in Appendix H.3. For instance, on a larger graph such as Squirrel it takes 6.23±0.21 seconds to obtain memorization scores and 24.49±0.11 seconds to calculate the LDS.

More datasets and GNN backbones, e.g., open graph benchmarks and graph transformers

We have added experiments on larger graph datasets, including ogbn-arxiv. The results are presented in the table below. We observe that the average memorization score and memorization rate on these datasets are low because the graphs are highly homophilic, which aligns with our Proposition 1, i.e., memorization is low for highly homophilic graphs. We also present the empirical runtimes in seconds for training models f and g and obtaining the memorization scores for the candidate set.

Large Datasets:

We also run additional experiments on a more advanced GNN backbone, a Graph Transformer, on four real-world datasets. We use the graph transformer setup proposed in [A] with slight modifications, namely we set the attention heads to 2 (instead of 8) and use a 1 layer graph transformer (Input → Linear Projection → [Attention + FFN Block] → Output Linear). The results are presented in the table below, along with the runtimes in seconds for training models f and g and obtaining the memorization scores for the candidate set. The results show that our memorization framework can be applied seamlessly to other GNN architectures including powerful architectures such as Graph Transformers, and that the propositions proposed in the main paper still hold.

Graph Transformer:

References:

[A] A critical look at the evaluation of GNNs under heterophily: Are we really making progress? Platonov et al. ICLR 2023.

We would like to thank the Reviewer again for their constructive comments. Based on their suggestions, we have additionally:

(1) clarified the novelty and contributions of our work – proposing a framework built on Feldman’s leave-one-out definition, and relying on our framework, we obtained multiple graph-specific findings;

(2) explained our evaluation strategy, which follows [59] to keep the overhead minimal while still aligning closely with the theoretical definition;

(3) run experiments on larger graph datasets, including ogbn-arxiv, and a more advanced GNN backbone, i.e., Graph Transformer, confirming that our memorization framework can be applied seamlessly to larger graph datasets and other GNN architectures, and the propositions still hold. We also included empirical runtime analysis to demonstrate the scalability of our approach.

These additions have significantly strengthened our contribution. We believe these enhancements have substantially improved the submission and would be happy to clarify any remaining questions the Reviewer may have. We kindly ask them to reassess their rating in light of these improvements.

We thank the Reviewer for recognizing the significance of this work as the first systematic study of memorization in graph neural networks. We appreciate the acknowledgment of our extensive experimental evaluation and the clear relationship established between graph homophily and memorization. Below we address the Reviewer’s comments and questions.

The framework targets the node-classification regime. How about graph-level classification?

We conducted additional analyses to apply our NCMemo framework to graph classification tasks. Concretely, we change the dataset S to contain graphs rather than nodes, and measure memorization as the difference on expected behavior between models $f$ trained on $S$ and models $g$ trained on $S \setminus gr_i$, where $gr_i$ is the graph whose memorization we want to measure.

We applied this framework to measure memorization on 4 graph classification datasets, namely the MUTAG, AIDS, BZR and COX2 [A], using a GCN backbone. The data split strategy is similar to the one presented in the paper, where we divide the graph dataset into 60%/20%/20% as training/testing/validation sets, respectively. Among the 60% training set, we further randomly divide the datasets into three disjoint subsets, i.e., shared graphs $S_S$, candidate graphs $S_C$, and independent graphs $S_I$, with ratios 50%, 25% and 25%, respectively. We measure the average memorization scores on the candidate graphs, we obtained the following results:

These initial results suggest that there is no memorization happening in these training setups. We hypothesise that this is because there are no outlier graphs, making it possible to learn without memorization, following the reasoning of Feldman [21].

To test this hypothesis and assess whether our framework is sensitive to measure memorization in graph tasks when it does appear, we conducted additional experiments where we introduce Gaussian noise to the node features of all the nodes of candidate graphs ($S_C$), de facto turning them into outliers, and see whether their experienced memorization increases. Our results in the tables below support this hypothesis and show that the more outlier the graphs become through the addition of more noise, the more memorization they experience.

GCN+MUTAG:

GCN+AIDS:

GCN+BZR:

GCN+COX2:

While more future work will be required to understand the mechanisms that cause graph-level memorization, we believe that our framework’s flexibility to support this kind of analysis, makes it a valuable tool for future work in this direction.

Showing Proposition 2 experimentally (memorization leads to poor generalization)

Our paper provides direct experimental evidence for Proposition 2, showing that higher memorization is linked to poorer generalization. This is demonstrated through two key metrics:

1. In Figures 4c and 8c of the paper we present the Kernel-Target alignment (Yang et al [61]) which is a formal measure of generalization. This alignment is poor for heterophilic graphs (which have high memorization) and the alignment is high for homophilic graphs directly providing evidence for high memorization results in poor generalization.

2. Further, we also present the test accuracies for real-world datasets in the table below (in addition to the accuracies reported for synthetic datasets in Appendix G), which clearly show heterophilic datasets, such as Chameleon and Squirrel, have lower generalization performance compared to homophilic datasets such as Cora and Citeseer while having higher memorization rates.

Generalization Performance of Real-world Datasets:

References:

[A] TUDataset: A collection of benchmark datasets for learning with graphs. Morris et al, GRL+ Workshop, ICML 2020.