Memorization in Graph Neural Networks
Authors: Adarsh Jamadandi
Jing Xu
Adam Dziedzic
Franziska Boenisch
Venue: NeurIPS 2025 poster ()
Keywords: graph neural networks
memorization
node classification
homophily
Primary area: deep_learning
TL;DR: We propose the first label memorization framework for node classification in GNNs and investigate the relationship between memorization and graph/node properties.

Abstract: Deep neural networks (DNNs) have been shown to memorize their training data, but similar analyses for graph neural networks (GNNs) remain under-explored. We introduce NCMemo (Node Classification Memorization), the first framework to quantify label memorization in semi-supervised node classification. We establish an inverse relationship between memorization and graph homophily, i.e the tendency of connected nodes to share labels or features. Lower homophily significantly increases memorization, indicating that GNNs rely on label memorization when learning less homophilic graphs. We then analyze GNN training dynamics and find that increased memorization in low-homophily graphs is tightly coupled to GNNs' implicit bias toward using graph structure. When structure is less informative, models instead memorize node labels to minimize training loss. Finally, we show that nodes with higher label inconsistency in their feature-space neighborhood are more prone to memorization. Based on these insights, we investigate graph rewiring as a mitigation strategy. Our results show that rewiring reduces memorization without harming model performance, while also lowering the privacy risk for previously memorized data points. Thus, our work advances understanding of GNN learning and supports more privacy-preserving GNN deployment.

Memorization in Graph Neural Networks
Adarsh Jamadandi' ; Xu², Adam Dziedzic', Franziska Boenisch² CNRS IRISA CISPA Helmholtz Center for Information Security?
adarsh. adarsh. jamadandi@irisa. fr, (jing.xu xu, adam. dziedzic, boenischJ@cispa.coo
Abstract
Deep neural networks (DNNss have been shown memorize their training data, but similar analyses for graph neural networks (GNNs) remain under-explored. We introduce NCMemo (Node Ptassificatio work to quantify label memorization in semi-supervised node classification. We establish an inverse relationship between memorization and graph homophily, i.e., the tendency of connected nodes to share labels or features. Lower homophily significantly increases memorization, indicating that GNNs rely on label memo- rization when learning less homophilic graphs. We then analyze GNN training dynamics and find that increased memorization in wwwmhhophhll graphs is tightly coupled to GNNs' implicit bias toward using graph structure. When structure is less informative, models instead memorize node labels to minimize training loss. Finally, we show that nodes with higher label inconsistency in their feature-space neighborhood are more prone to memorization. Based on these insights, we investi- gate graph rewiring mitigation strategy. Our results show that rewiring reduces memorization without harming model performance, while also lowering the privacy risk for previously memorized data points. Thus, work advances understanding of GNN learning and supports more wwwacy-preeerving GNN deployment.
Memorization), the first frame-
Introduction
Graph Neural Networks (GNNs) are a class of deep learning algorithms that adopt the paradigm of message passing (27 55
24 14 to learn on graph-structured data. GNNs have found successful applications in diverse domains such as chemistry [22 biology [12,, high-energy physies (58), and
even contribute to the discovery of novel materials 42 Despite their empirical success, the inherent limitations of GNNs continue to be an active area of research, one of which is the challenge of generalization. In deep neural networks (DNNs), memorization, the model's 's ability to remember individual training data points, and how it benefits generalization has been explored [2]] While recent studies (60, 64
3 39 have focused establishing generalization bounds and errors for GNNs, investigation GNN memorization notably scarce. primary reason for the gap in the understanding of memorization for GNNs is the inherent difficulty in conceptualizing and defining per-sample memorization. In other domains, such as computer vision, samples are independent from each other, which allows for a straightforward definition of per-sample memorization. However, in node classification setting, the GNN operates on a single graph where all nodes are inter-connected. This makes analyzing the model's ability to memorize individual nodes challenging, as it requires modeling a complex interplay of factors: the node's 's own features, the features of its neighbors, the information content of its label relative to its neighborhood 49 the overall graph homophily level, and the GNN's training dynamics.
In light of these challenges, propose systematic framework for measuring memorization in node classification. Our approach, called NCMemo (Node Classification Memorization),
"work carried out at CISPA.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

tackles these challenges directly by characterizing memorization from three perspectives: (i) at the node level, by taking into account the feature and label information; (ii) at the graph level. by studying memorization with respect to graph homophily; and finally (iii) the training dynamics, by understanding how memorization affects the ability of the GNNs to learn generalizable functions.
Our proposal is inspired by the leave-one-out [21 63 definition of memorization which involves comparing the predictive behavior of models trained with and without specific data samples. A significant change in this behavior, particularly increased confidence when the sample is included in training, signals that the sample has been memorized. This behavioral gap helps identifies nodes potentially prone memorization.
At first glance, extending this idea to graphs may seem challenging. since nodes are interdependent and masking a single label could lead to information leakage. However, this setup aligns with the standard semi-supervised node classification paradigm, where models access all node features and the full graph structure but only subset of labels during training. Our leave-one-out procedure is fully consistent with this setting, i.e., we mask one node's label, keep all other information fixed, train models with and without that label, and measure the resulting change in predictive behavior. Further discussion is provided in Appendix A Our study reveals several key insights: we find a novel inverse relationship between memorization rate (the number of nodes that get memorized) and graph homophily, i.e., the nodes in lower homophily graphs exhibit higher memorization. To explain the emergence of this memorization behavior. over-pane wver-parametrieed regime through the lens of Neural Tangent Kernel [31 [ 66). We find that the tendency of GNNs to be excessively reliant on the graph structure, even when it is uninformative, as in the case with lower homophilic graphs, results in a model memorizing node labels. We also investigate memorization at the node level by proposing novel metric, Le.,, Label Disagreement Score (LDS), which helps identify why certain nodes are susceptible to memorization. Overall, our analysis suggests that nodes with higher label inconsistency in their feature space, i.e., atypical samples, experience higher memorization. Finally, we show that memorized nodes are significantly more vulnerable privacy leakage (59) than non-memoriee ones. Motivated by the observed link between graph homophily and memorization, we explore graph rewiring [6]] as a mitigation strategy. Specifically, following (54), we rewire edges based on the cosine similarity between connected nodes. This reduces memorization and, as we show, the related privacy risks for memorized nodes, while preserving model performance.
analyze the training dynamics of GNNs in the
Overall, we perform extensive experiments on various real-world datasets and semi-synthetic datasets 68 with various GNN backbones such as SGC (65), GCN (3), GraphSAGE (28). GATv2 [3] and Graph Transformer (GT) to confirm our findings. In summary, we make the following contributions.
1. We introduce NCMemo, a label memorization framework inspired by the leave-one-out memoriza- tion style 21 for the challenging context of semi-supervised node classification.
2. We reveal an interesting inverse relationship between the memorization rate and the graph ho- mophily level: as the graph homophily increases (and consequently label informativeness [49 increases), the memorization rate decreases significantly.
3. We explain memorization's emergence by analyzing GNN training dynamics. We find that GNNs' tendency to utilize graph structure, even when it's unhelpful in low-homophily scenarios, directly leads to memorization as they strive for low training error.
We propose the Label Disagreement Score (LDS) to characterize memorized nodes. This metric, measuring local label-feature inconsistency, shows that nodes with higher LDS are significantly more prone to memorization.
Finally, we demonstrate the privacy risks arising from memorization in GNNs and show that graph rewiring as promising initial strategy for mitigating this risk.
2 Background and Related Work
Limitations of Graph Neural Networks. Although GNNs are being used in various domains, our un- derstanding of the mechanisms governing how GNNs learn and generalize is still in its infancy, More recently, attention has shifted towards understanding GNN generalization. Approaches in this area include studying generalization gaps (60 644, leveraging mean-field theory to study generalization
errors B. establishing convergence guarantees (36] and studying the interplay of generalization and

---

model expressivity 39. Concurrently, other works analyze GNN training dynamics. For instance, Mustafa al. 44 show how standard weight initialization schemes such as Xavier [66 might lead to poor gradient flow dynamics and consequently, diminished generalization performance in To address this, they propose an improved initialization scheme for GATv2 [3] that enhances gradient flow and trainability. Furthermore, a recent work [66] shows the utility of Neural Tangent Kernel (NTK) [31 4 to study GNNs in function space, characterizing how optimization introduces implicit graph structure bias which is encoded in the notion of Kernel-Graph Alignment that aids learning generalizable functions.
Graph Attention Networks (GAT') 662 13
Memorization in Deep Neural Networks. The phenomenon of memorization in deep learn- ing oog-hhere models learn to remember specific training examples has been extensively studied in 40
[1] 63, g 38]. It has been shown that DNNs can memorize even random labels 67 Different memorization metrics have been proposed for supervised [21] and self-supervised learning models showing that memorization in DNNs required for generalization. Memorization has also been associated with multiple risks to the privacy of model's training data [17 [1].. However, similar studies on data memorization in GNNs are lacking. In this work, we aim to fill this gap.
the context of deep neural networks (DNNs) [67 [
[1 6
Overfitting vs Memorization in GNNs. A work that thematically aligns with the goals of this paper [9] which studies how the GNNs' inductive bias towards graph structure can be problematic. The work demonstrates that GNNs may overfit to the graph structure even when ignoring it would yield better solutions, leading to poor generalization, particularly in graph classification. Our work on the other hand, focuses on the related but distinct phenomenon of memorization. Unlike overfitting where the model shows poor generalization beyond the training set, memorization involves using spurious signals to remember specific examples [38] which can be beneficial for generalization [2
3 Our NCMemo Label Memorization Framework
In this section, we present our framework NCMemo, which is inspired by the leave-oneoout definition of memorization proposed by Feldman 211. Let f RR" + Rdd be GNN model trained on the graph G = (X, A). where X is the node feature matrix and A is the adjacency matrix, using a GNN training algorithm T (e.g.. GCN (37). Let S = {v;, yi ) be labeled training dataset, where v; is a node and y/s its true label. Let f(x.) denotes a predicted probability of model f for the node v/s And let eú be target node from dataset S. Finally, let GNN models f E F.9 G be trained with a GNN algorithm T on S and 5 \\ v (dataset S with v removed), respectively. We calculate the memorization score M for a target node 22 as:
M(v.) = E
E [Pr[((u)) = vill (~T()()))) (~T(S)
[Prlg(e:) = vi]l.
Our objective is to measure the memorization for candidate nodes (u)). Since model f has seen the candidate nodes as part of its training corpus, it is expected that f shows higher confidence in these nodes than model g. We define the memorization rate (MR) as
MR
I(M():) > r) x 100,
S
where 1(-) the indicator function and r = 0.5 as a predefined threshold, chosen according to the definition proposed in (21).
Since a full leave-one-out evaluation is computationally prohibitive, it requires retraining for every node. To make this tractable, we follow the efficient setup detailed in 63) We partition the training data into three disjoint subsets: Ss. Se and Sy. We use these sets to train two models. Model f is our target model whose memorization we want to evaluate, while is an independent model that we use to calibrate according to Equation (T). following the
definition of memorization by Feldman (21). Model f is trained on Ss U Sc. and model is trained on Sş U St, where Se the candidate set, i.e., the nodes whose memorization we want to quantify. By the setup of the experiment, models of and are both trained on Ss. but Sç: is only used to train f. Therefore, the difference in behavior between model ʃ and g on Sc: results from the fact that f has seen the data and g has not, allowing us to quantify the memorization. Including S, into the training set of y 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 on Se are not due to model performance
3

---

differences. Applied to our node classification setting, we include node for training model f and for g we do not. We can measure the memorization on this node as the expectation of behavior of models / and on predicting the label of correctly as yi- 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 1; and has not. It hence quantifies f's memorization on v, In the next section, we explain the mechanisms that drive GNN models to memorize and also provide insights into emergence of memorization behavior.
4 Mechanisms of Memorization : Graph Structure to Training Dynamics
In this section, we study the various factors that lead to memorization in GNNs. Particularly, we identify three factors, namely the graph ho- mophily, the training dynamics and the label disagreement at the node level as the key contributors to memorization. To evaluate our label mem- orization framework, we follow the setup in 663 to make the evaluation computationally tractable by approximating the memorization metric over multiple samples at once. Specifically, we divide the training set into three disjoint independent nodes (Sy). Subsequently, we train model f on Sş U Se and model g on Sş U Sz. Figure Lillustrates the data partitioning in our label memorization framework.
nodes (Ss), candidate nodes (Sc) and
Figure 1: Data partition- ing in our label memo- rization framework.
We begin our evaluations by using a synthetic dataset benchmark, where we can control the specific properties of the graphs, e.g., homophily level. The synthetic benchmark is the syn-cora dataset proposed in [68). which contains graphs with different homophily levels, the node features for the graphs are assigned from a real-world graph such as Cora [41]. We choose five graphs with increasing homophily levels h {0.0, 0.3, 0.5, 0.7, 1.0), where, for example syn-cora cora-hO. 0 indicates synthetic graph with homophily level 0.0. Note that, low homophilous graphs are also called as heterophilic graphs, where the connected nodes have different labels/fcatures.
4.1 Highly Homophilous Graphs Exhibit Lower Memorization Rates
Parorbacio
(a) syn-cora-0.0 (b) syn-cora-0.3
(c) syn- syn-cora-0.33
(d) syn- -or
(c) syn-cora-L.0
Figure 2: Memorization Scores for Sc on syn-cora: Comparison of memorization score across syn- cora graphs with increasing homophily levels trained with GCN.
We train three-layered GCN 37 on each graph of syn-cors cora and calculate the memorization scores based on Equation (I). We plot the memorization scores for the candidate nodes (Sc) across different graphs in Figure 2 We can see that the memorization score and memorization rate is higher for
heterophilic graphs than homophilic graphs This result unveils an interesting connection between
the memorization rate, see Equation (2) and the graph homophily level (h), leading us to our first novel insight. We formalize this in proposition below.
Proposition 1 (Inverse relation between memorization rate and homophily. The rate of memo- rization is inversely proportional to the graph homophily level (h). As the homophily level increases (1), the memorization rale tends zero (4).
To investigate the claim made in this proposition, we plot the graph homophily level, the node label informativeness (NLI) which measures the amount of information the neighboring nodes give to
In our generated syn-core dataset, the number of nodes is the same for all generated graphs so it is straightforward to compare the memorization rate between graphs of different homophily levels.

---

predict particular node's label 49] and the memorization rate for the candidate nodes in Figure ((a) The results highlight that as the graph becomes highly homophilic rate drops to O. To see the relationship more clearly, in Figure 5(b) we plot only the homophily vs
1.0), the memorization
memorization rate with red line highlighting the trend. This confirms our hypothesis that one the mechanisms dictating the memorization behavior in GNNs is the graph homophily level.
4.2 GNNs' Structural Bias and Kernel Alignment Dynamics Explains the Emergence of Memorization
Naturally, the next question is how does mem- orization affect the ability of GNNs to learn a desirable function that can generalize well? Yang al. [66] analyze the training dynamics of GNNs through the lens of Neural Tangent
Kernel (NTK) B1 4 in the over- pver-parametrized regime and propose the interplay of three align- ment matrices, namely (1) the alignment be- tween the graph structure (A) and the opti- mal kernel matrix (O* YYY [9 see Def- inition 4 denoted by A(A, 6*), which en- codes the notion of homophily of the graph, (2) A ( O*), the kernel-targer alignment which induces better generalization capabilities espe- cially in learning kernel functions and finally (3) A(O). (), A), the kernel- gernel-graph alignment which allows the NTK matrix to naturally incorporate the adjacency matrix in a node level graph NTK formulation (NL-GNTK). For a I layered GNN with weights W and nodes x, å and the adjacency matrix A, the GNTK is given by
(a) Homophily Label Informativeness vs Mem-
(b) Homophily Memo- rization Rate.
orization Rate.
Figure 3: Inverse relationship between Memo- rization Rate and Homophily. We show results for GCN trained on the syn-cora dataset. As the graph homophily increases, the memorization rate decreases significantly.
O A) Vw
where, (2, ã; A) is the NTK matrix that can be seen as a measure of similarity between nodes x, F. guided by the adjacency matrix A. Following this line of reasoning, we can in Proposition [ as an inverse relation between A(A, θ*) and memorization rate. This connection gives nice ingress to study the influence of memorization on the training dynamics of GNNs. With this preliminary setup, we now introduce our results that connect memorization rate to the way GNNs learn generalizable functions.
results
Homophily
Homophily 0.5
Hamophily
2.2
0.3
3.0
67
1.0
0.6
03
37
100
0.8
80
0.10
Memorization Rate
0.6
60
Z0.00 0.00
40
0.4
0.06
20
20
60
100
20
60
80
100
20
60
100
Training Epachs
Training Epochs
Training Epachs
(a) Memorization rate over train- ing epochs.
(b) The -gaaph alignment
(c) The Bernel-targer aligmment
A (e, A) over training epochs.
A(Or, θ*) over training epochs.
Figure 4: Evolution of the NTK matrix θ and its alignment with the adjacency matrix A and the optimal kernel " during training for syn-cora, trained on GCN. (a) Memorization rate is increasing during training, and it is higher for lower homophily graphs. (b) The kernel-graph alignment A( ( e A) improves during training regardless of the graph homophily level. (c) The kernel-target alignment A(Or, O²) is poor for now-homophilic graphs.
5

---

Proposition 2 (Implicit bias towards graph structure and memorization.) The optimization dy- namics of GNNs on low-homophily graphs (A(A, )") 4) demonstrate a tendency of the GNN model to overfit to the graph structure. For a heterophilic graph (i.e., h = 0.0), training progresses we see that: (i) the memorization rate increases over epocks (t); (ūi) the kernel-tareet alignment A( t: @²)) remains low (4), indicating poor generalization; yet (ii)) the kernel- graph alignment A( A) tends to increase (1), suggesting the inherent capability of GNNs to leverage the graph structure even when it is detrimental to the task.
We track the temporal dynamics of the NTK matrix and its alignment with the other kernels as cora dataset, similar to the setup Proposition [ The results are shown in Figure We track the memorization rate of the candidate nodes trained on model f across training epochs; correspondingly, we also track the A + O*) and A(O), A) across epochs. The lines are color coded by the homophily level. Figure 4(a) reveals that the memorization rate consistently increases with training epochs. This rate is higher for low homophilic graphs. In Figure 4{b) we can observe that the kernel-grahh alignment tends to improve over time regardless of the homophily level. This reinforces the idea of GNNs leveraging the graph structure during optimization regardless of the homophily level (and thus, whether the graph structure is actually useful for the learning task). This alignment trend contrasts with A(Or, O*) behavior (Figure [ where lower homophily graphs show substantially poorer alignment, confirming the model's 's inability to learn generalizable functions in these settings. We provide simple proof in Appendix D.2 to show that a model that shows better kernel-graphe alignment cannot simultancously also obtain better kernel-target alignment in low homophily settings. The interplay of these evolving metrics suggests that the final state of these alignments will be indicative of the overall memorization. To quantify this relationship at convergence, our next proposition presents a correlation analysis between memorization rate and the final kernel matrix alignments.
proposed in [66] over training epochs on GCN trained on the syn-cora
Proposition 3 (Negative correlation between MR, A(O,. O²) and A(Or, A) alignments.) Let I be the GNN model trained for node classification via gradient descent on a graph 9 = =x0 A) with labels Y. converging final weights W₁. Let Juul E Rux= be the empirical Neural Tangent Kernel (NTK) corresponding to W,, and O* is the optimal kernel. As the kernl-tarrett alignment A(O), t: (*) improves, the memorization rate decreases. Similarly, as the kernel- grapp- alignment A(Or. A) improves, the memorization rate decreases.
We measure the correlation between the memorization rate and aligmment matrices by setting O = Iiall i.e., we take the converged GCN model f trained on the syn-cora dataset and use the final weights to calculate the alignment matrices A( (iiin A) and A(Q fiall @*). The results are iinal.
Nemorization (MR %6)
AlBra. 8") MB (mm0.00) AlBraa. Alas Wh a- 0.581
62
presented in Figure 5 where we see a Pearson correlation of r = -0.9 with respect to the kernel-tareet alignment (A(( final θ') )) and a correlation coefficient of = -0.88 with respect to the kernel-graph alignment (A(@) fiaal A)). As the cernel-target alignment A final: θ*) improves, which suggests the model's θ final is aligning well with the optimal kernel O' leading to good generalization behavior, the need for memorization is obviated. Similarly, when the kernel-graph alignment A(@ A) improves, this suggests that the model is leveraging the graph structure which is obviously useful (because of high homophily) for the learning task, and consequently we see decrease in the memorization rate.
20-
03
33
03
05 0.7
NTK Alignment Value
Figure 5: The inverse relationship between MR and the A(Ormal: O*), A(Onnal, A) alignments.
4.3 Feature Space Label Inconsistency is Strong Indicator of Node-Level Memorization
Our preceding analyses have established a crucial link between graph-level properties like homophily and the overall memorization rate (Proposition I]. We have also analyzed the training dynamics (Proposition 2, Proposition 33 to explain how GNNs' reliance on graph structure can lead to mem- orization. However, these perspectives do not fully address fundamental question: why are only specific nodes within graph highly susceptible to being memorized, while others are learned in more generalizable manner? Drawing an analogy from DNNs where atypical examples are often memorized, we hypothesize that, in GNNs, nodes exhibiting strong discordance between their labels

---

and their local feature- space context are particularly susceptible to memorization. We formalize this intuition in a proposition below.
Proposition 4 (Higher label disagreement indicates susceptibility to memorization.) Nodes that exhibit high degree of label inconsistency with their neighbors in feature space are more likely to be memorized by a GNN.
To quantify this label inconsistency, agreement Score (LDS). Let Sc be the set of candidate nodes and Strain f Su be the set of nodes used to train model whose fea- tures form the search space for neighbors. For a target node 0; E Sc with features x; Rd and label ys, we identify its k-nearest neighbors in feature space from Smain f- The node U; itself is omitted from its own neighborhood set [u:);;) including it would artificially decrease the disagreement score (as Ily: a yi] = 0) without reflecting the actual inconsistency with its distinct surroundings. Therefore, Nu (v:) contains & nodes vj Strin \ { that minimize the L2 distance || x,ll2. The LDS for
introduce the Label Dis-
Table 1: LDS for Se on syn- syn-cora-ho.co O.
MomnNodes
Non-MemnNades
LDS
LDS
0318780.0138
node v is then defined as:
LDS 1 A:
Σ Uu + vll
(4)
(v:)
where 1[:] is the indicator function, and l is chosen hyperparameter (e.g., k = 3). The LDS intuitively measures the local anomaly in the label-feature manifold. If a node's features place close neighbors with predominantly different labels, it presents a conflicting signal to the GNN. To minimize training loss on such a node, the GNN might resort to memorizing it rather than learning feature transformation that adequately classifies both this target node and its disagreeing neighbors under a shared rule. Following our experimental setup, in Table [ memorized versus non-memorized nodes within the candidate set of the syn-cora- -0. O dataset, using a GCN model and averaging over three random seeds. We consistently observe that memorized nodes exhibit, on average, significantly higher LDS than non- non-memorized nodes. This finding supports our hypothesis that strong conflicting signals arising from high label inconsistency in a node' s feature-space neighborhood make that node particularly vulnerable being memorized by the GNN.
we measure the LDS for
5 Extending Evaluation to Real- Data and Other Tasks
In this section, we present results on memorization scores on real-world datasets. We use GCN
[37]. GraphSAGE [29] and GATv2 [ with layers as our backbone GNN models. We also report additional results on larger datasets in Appendix
E. with Graph Transformer in Appendix E.4andd and
SGC (65) in Appendix [E.5 backbones. The datasets we use are: Cora [41), Citeseer (56). Pubmed
[45). which are homophilic datasets. Cornell, Texas, Wisconsin [48], Chameleon, Squirrel
53 and
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 Sg 50%. Sc 25%. S 25% We instantiate two GNN models f and g. which are trained on Sg U Sc and S5 U S,, respectively. We train both models on three random seeds. We choose the best model based on the validation accuracy to calculate the memorization scores for the distribution plots, to ensure our memorization results are not an artifact of poor training. Based on Equation (T). the resulting memorization score ranges between and 1, where 0 means no memorization, means the strongest memorization phenomenon on model f, and -1 denotes the strongest memorization on g.
Actor heterophilic datasets. We divide our datasets into 60%/20%/205g
5.1 Memorization Results Real-World Datasets
Inverse Relation Between Memorization Rate and Homophily on Real-World Datasets. Figure shows the distribution of memorization scores for candidate nodes four real-world datasets trained on a GCN, revealing a similar trend as in Figure 2 That is, candidate nodes of homophilic graphs such as Cora and Citeseer show lower memorization scores than heterophilic graphs such Chameleon and Squirrel. We also report the average memorization scores and memorization rate along with additional results for different GNN models in Appendix E
Evolution of Alignment Matrices on Real-World Graphs. We verify the results outlined in Section 4 on real-world datasets. We use GCN for all of our experiments. In Figure 7 we show the
7

---

112
Natvadle
120
130
Namoriattoon Score
Memertarian
200.0000aa0 12
Iimortation
Hamottation Scor
(a) Cora.
(b) Citeseer.
(c) Chameleon.
(d) Squirrel.
Figure 6: Memorization scores of Se for Cora, Citeseer, Chameleon, and Squirrel datasets. The candidate nodes of homophilic graphs exhibit lower memorization scores than heterophilic graphs
evolution of the alignment matrices on 9 real-world graphs. We can observe in Figure 7(a) that our insights from the synthetic dataset holds true for real-world settings: homophilic graphs such as Cora, Citeseer, and Pubmed exhibit lower memorization compared to the heterophilic graphs like Cornlll,
Texas, Wisconsin, Chameleon, Squirrel, and Actor. Correspondingly, in Figure (bb] we can see the kernel-graph alignment A(Or, A) improves over training epochs for all the datasets, regardless of the homophily level, highlighting the implicit bias of GNNs [66]; and Figure [7(c shows that
the homophilic graphs have higher kernel-target alignment (A(O,, θ²)) compared to heterophilic
graphs and thus lead to better generalization. These real-world results align well with the trends
described in Proposition
Moreover, our findings complement Pechler-Speichee et al. 9 but distinguishes label memorization separate phenomenon. Specifically, our analysis of training dynamics (Proposition (2) shows that GNNs' reliance on graph structure (increasing A(O,. A)), particularly in low-homophily settings where this structure is uninformative for label prediction, can compel the model to memorize individual node labels to minimize training loss. This memorization, driven by the need to fit specific labels, is distinct from structural overfitting; while both involve a potentially suboptimal reliance on graph structure, the latter concerns the model's choice of information source, whereas memorization details how specific training instances are fit when signals are conflicting uninformative.
Chouse
Chocsl
Fativea
0.0
0.30
0.5
Momertaate Fate
0.25
20.20
80
0..15
0.10
20-
0.05
0.1
20
50
50
80
100
0.00
20
40
60
80
100
0.0
20
40
50
80
100
Training
Epechs
Training Epochs
(a) Memorization rate over train-
(b) The kernel-grap alignment
(c) The kernel-target alignment
ing epochs.
Ar A) over training epechs.
A O, O*) over training epochs.
Figure 7: Evolution of the NTK matrix θ and its alignment with the adjacency matrix A and the optimal kernel O for real-world graphs trained on GCN. (a) Memorization rate is increasing during training, and it is higher for lower homophily graphs. (b) The kernel-graph alignment A( A) improves during training regardless of the graph homophily level. (c) The kernel-target alignment A(O,, +*) is poor for oww-homppiiiic graphs.
Correlation Between MR, Ale ( Fimll, +*) and f(mim,,, A) Alignments on Real-World Graphs. We also validate Proposition] 3 using 8 real-world datasets In Figure g we plot the Pearson corre- lation coefficients between the memorization rate and the two alignment matrices (i.e..A(O,, e*) and A(O, A)). We can observe a negative correlation of r = -0.79 between memorization rate and A(O,, +*), and a slightly weaker but nevertheless negative correlation of -0.58 between memorization rate and A(O,, A). These findings indicate that as the kernel-target or sernel-graph alignment improves, the memorization rate tends to decrease. We attribute the relatively weaker
'e omit Pubmed from this analysis since it exhibits strong resistance to memorization, see Table and Appendix F for discussion.
8

---

correlation with A( A) to the fact that the actual homophily values of the datasets are highly varied (See Table 18 for the actual values). Nonetheless, the overall trend supports our Proposition on real-world datasets as well.
Label Disagreement Score for Real-World Datasets. We calculate LDS for both memorized and nom-meerr nodes on the candidate set (Sc) averaged over random seeds for Cora, Citeseer, Chameleon and Squirrel datasets in Table 2 along with their statistical significance. From the table, we can see that the memorized nodes have a higher label disagreement scores compared to the memomzzdd nodes and this trend is consistent across both homophilic and heterophilic graphs. Thus, we can use this metric to understand why only certain nodes get memorized, a node belonging to neighborhood where the labels strongly give a conflicting signal for the GNN aggregation step ends up getting memorized by the model. More results on LDS are presented in Appendix [F] In the next section, we discuss graph rewiring decrease memorization in GNNs, further we also discuss the implications of memorization to privacy risk.
80-
70
Mom Numoraatton Rata
4.
ACOP
20
10
0.0
0.1
07
U. 0.5 0.6
Figure 8: The inverse rela- tionship between MR and the A fmal, 9*), A(Onnal A) align- ments for real-world datasets.
possible strategy to
Table 2: LDS for memorized nodes (MemNodes) vs non-memorized nodes (Non-MemNodess) in the Sc, trained on GCN averaged over 3 random seeds.
Datasct
MemNides LDS
Non MoonMMs LDS
p-value (< 0.01)
Effect Size
Cora
0,8016#0 01 186
0,5754=0. 1011
0.0024
14,39
Citeseer
0.7985+0000
0.6192=000040
0.0029
13.13
Chameleon
18433300.0008
0.7362=0000166
0.0000
113.68
Squireel
0.861740.0002
0.7675=000040
0.0020
15.98
5.2 Memorization in Graph Classification
We also extend our memorization framework to graph classification. The dataset now consists of graphs, and memorization is quantified as the change in expected behavior between models s trained on S and models g trained on S \ gr,, where gr; is the graph under test. We evaluate on MUTAG, AIDS, BZR, and COX2 [43] using GCN backbone. The data is split into 60%/22%//00% for training, testing, and validation, with the training set further divided into shared (Sss), candidate (Sc), and independent (Sy) subsets in 50%/25%/255 % ratios. Results (Table 3) indicate that the GCN learns effectively without memorization.
Feature Noise Drives Memorization. We hypothesize 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 measuring memorization in graph classification tasks when it does appear, we introduce Gaussian noise with a E (0.1, 0.3, 0.5, 0.7, 0.9) to node features of all the nodes of candidate graphs, turning them into outliers, and recompute memorization scores. Our results in Table B show that as noise increases, the graphs become more atypical and the framework successfully detects memorization, with MUTAG showing clear monotonic rise in memorization rate and average score, whereas other datasets exhibit less consistent trends. While further work is needed to understand the mechanisms underlying memorization in graph classification, these findings highlight the versatility of our proposed approach.
Table 3: Average memorization score and memorization rate of candidate graphs with GCN.
MUTAG
AIDS
BZR
COX2
Noise Level
Avg
MR
Avg
MR
Avg
MR
Avg
MR
MemScore
(5)
MemScore
(%)
MemScore
(%)
MemScore
(5)
0.0
0.001 120.0045
0.076710.0266
0
-0.009620.0066 0067
0.0068:0.0241
0
0.1
0.0767=0.0260
1.2+1.9
0.0767=0.0200
0.660
0
0.1993
9.243.11
0.191920.0116
1.6+1.3
0.3
0.2352=0.0744
18.3+9.9
0..059
6.5+3.2
0.2965+0.00644
27.7+0.0
0.2326=0.0145
21,5+1.5
0.5
0.3419:0.0420
33.313.7
0.2086:0.0295
13.7+1.2
0.209110.0109
15.910.9
0.285610.0012
28.910.0
0.7
0.3680=0.0239
39.814.9
0.2465=0.006$
18.8=1.4
0.179020.000
18.520.0
0.2237=0.0101
23,720.0
0.9
0.4544=0.0302
46.2+6.7
0.2367+0.0346
17.6#2.2
0.19988000006
20.0+0.0
0.1838=0.0092
18.40.00

---

6 Privacy Risks and the Real-World Impact of Memorization
We finally turn to the real-world impact of mem- orization. In DNNs, memorization has often been linked to privacy risks for the memorized In this section, we
0.3
data points, e.g., [15 [8]
0.
64
highlight that the same holds for GNNs. Based on our findings from the previous sections, we explore graph rewiring as a mitigation strategy. Our findings highlight the effectiveness of this approach for mitigating memorization and re- ducing the associated privacy risks while main- taining high model performance.
08,5
32 0.4
5.6 0.5
1.0
02
0.4
5.8
0.5
10
Figure 9: MIA risk of GNNs trained on original syn-cor: cora (left) and rewired syn-cora (right). h0.0 (1.0) means homophily level 0.0 (1.0).
Analyzing Privacy Risks. Membership inference attacks (MIAs) 55 are a standard tool to assess privacy leakage in machine learning. In these attacks, an adversary aims at inferring whether a certain data point was included in the training set of model. We rely on the Likelihood Ratio Attack (LiRA) [6] to assess the privacy risk in our GNNs. Our results for syn-cora are presented in Figure 9 (left), where we measure the Area Under Curve (AUC) to characterize the vulnerability of the GNN model. We also present the TPR (True Positive Rate) at 1 1% FPR (False Positive Rate) in G We observe that, nodes in low homophily graphs, such as syn-cora-ho O, which exhibit high memorization, are most susceptible to MIAs with an AUC value of 0.936, whereas nodes in a highly homophilic graph, e-g., syn-cora-hi O. show a value of 0.538, close random guessing. Our results indicate that nodes in lower homophily graphs, have a significant higher risk of leaking from trained GNN models due to memorization. This prompts the question How can reduce memorization and its resulting privacy risks?.
Table 1 Appendix
Graph Rewiring to Prevent Privacy Leakage. Our Proposition D suggests that one of the key contributors to memorization is the graph homophily, which means it should be possible to con- trol the memorization by influencing the homophily level. However, since calculating homophily requires access to all the node labels, it cannot be directly optimized for. Therefore, we adopt a feature maiillartty-aased graph rewiring framework proposed in [54], which aims to maximize the feature similarity (based on cosine similarity) between nodes by adding or deleting edges, indirectly influencing the homophily level. See Appendix G for a full description of the approach. It is assumed that after applying the rewiring method, the graph's homophily level will increase, leading to less memorization and MIA risk.
Evaluation. To validate this hypothesis, we rewire the syn-cora graphs by adding a specific number of edges to the graph. The homophily level of the rewired syn-cora graphs indeed increases. We then train new GNN models on the rewired graphs and analyze the memorization behavior of those models using NCMemo. The detailed implementation setups and results are presented in Appendix G We also perform the LiRA attack again on those models. Our results in Figure ( (right) show that the MIA risk is significantly reduced compared to the models trained on the original graphs, i.e., the AUC scores have dramatically dropped for all syn-cora graphs. The drop is most significant for the low homophily graphs (e.g., syn-cora-ho 0), where the AUC scores have dropped by more than 20%. This confirms our hypothesis that graph rewiring can be a simple memorization mitigation strategy to prevent the real-world privacy risks for memorized samples. We also consider label smoothing as an alternative memorization mitigation strategy and compare the results with graph rewiring in Appendix G.
7 Conclusions
In this work, we propose NCMemo, the first framework to quantify label memorization in GNNs. We identify both graph-level and node-level factors that influence memorization, such as graph homophily and feature-label inconsistency. We also extend our framework to graph classification and provide promising initial results. Through experiments on real-world privacy risks stemming from GNN memorization, we further demonstrate that graph rewiring can effectively reduce both memorization and its associated privacy risks. Overall, our work advances the understanding of GNN learning dynamics and contributes to their more privacy-preserving deployment.
10

---

Acknowledgments and Disclosure of Funding
We gratefully acknowledge funding from the Deutsche Forschungsgemeinsccaft (DFG, German Research Foundation), Project number 550224287.
References
[1] Sami Abu-El-Haija, Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard, Kristina Lerman, Hrayr Harutyunyan, Greg Ver Steeg, and Aram Galstyan. MixHop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 21-29, PMLR, 09-15 Jun 2019. URL https: http:::://pooceednnnge mlr. prwss/ aabs///bb-e-aaaa ja19a. html
[2] Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. In International Conference on Learning Representations, 2021. URL https /ooenreviee net/forrmm::d-180PP000
[3] Gholamali Aminian, Yixuan He, Gesine Reinert, Lukasz Szpruch, and Samuel N. Cohen. Generalization error of graph neural networks in the mean-field regime, 2024. URL https
//arxiv. owg/orgg//....o. abs/ 2202 07025
[4] Sanjeev Arora, Simon S. Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization and generalization for overparameterrized two-layer neural networks. CoRR, 08584
abs/1901 1888849 2019. URL
[5] Devansh Arpit, Stanislaw Jastrzkebski, Nicolas Ballas, David Krueger, Emmanuel Bengio, Maxinder S Kanwal, Tegan Maharaj. Asja Fischer, Aaron Courville, Yoshua Bengio, et al. A closer look at memorization deep networks. In International conference on machine learning,
pages 233-242. PMLR, 2017.
[6] Robert John Nicholas Baldock, Hartmut Maennel, and Behnam Neyshabur. Deep learning through the lens of example difficulty. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, 2021. URL https h/open/evvew.nee//eeeeeeeeeeeeee wtwp:/rrrummmddddWdBhhhhhheee
[7] Albert-LászI6 Barabási and Réka Albert. Emergence of scaling in random networks. Science, 28665439) October 1999. ISSN 1095-9203, doi: 10. 126//ccience.2865599.0000 URL http://dx http://xxxdoi..rggg orgh 10. 1 science..cc....cc...oo 286 5439.500
[8] Reza Bayat, Mohammad Pezeshki, Elvis Dohmatob, David Lopez-Paz, and Pascal Vincent. The pitfalls of memorization: When memorization hurts generalization, 2024. URL https
[9] Maya Bechler-Speicher, Ido Amos, Ran Gilha-Bachrach, and Amir Globerson. Graph neural networks use graphs when they shouldn't, 2024. URL hntpe://arxiv..rr//bbb// 04332
[10] Wendong Bi, Lun Du, Qiang Fu, Yanlin Wang, Shi Han, and Dongmei Zhang. Make heterophily graphs better fit gnn: A graph rewiring approach, 2022.
[11] Simone Bombari, Mohammad Hossein Amani, and Marco Mondelli. Memorization and optimization in deep neural networks with minimum wee-pparamtterization. Advances in Neural Information Processing Systems, 35:7628-7640, 2022.
[12] Pietro Bongini, Niccolò Pancino, Franco Scarselli, and Monica Bianchini. Biognn: How graph neural networks solve biological problems. In Artificial Intelligence and Machine Learning for Healthcare, pages 21 2-113... Springer, 2023.
[13] Shaked Brody, Uri Alon, and Eran Yahav. How attentive are graph attention networks? In International Conference on Learning Representations, 2022. URL. http::ttt////t htttps://operrevier het:/oorum?1d=F72xxim
|RIphttps:

---

[14] Michael M. Bronstein, Joan Bruna, Taco Cohen, and Petar Velickovic. Geometric deep learning: Grids, groups. graphs. geodesics, and gauges. CoRR, abs/2104. 13478, 2021. URL https
wawxiv.org/abs/// 2104. 13478
[15] Nicholas Carlini, Florian Tramer, Eric Wallace, Matthew Jagielski, Ariel Herbert-Voss, Kather- ine Lee, Adam Roberts, Tom Brown, Dawn Song, Ulfar Erlingsson, et al. Extracting training data from large language models. In 30th USENIX security symposium (USENIX Security 21).
pages 2633-2650, 2021.
[16] Nicholas Carlini, Steve Chien, Milad Nasr, Shuang Song, Andreas Terzis, and Florian Tramer. Membership inference attacks from first principles. In 2022 IEEE symposium on security and privacy (SP), pages 1897-1914. IEEE, 2022.
[17] Nicholas Carlini, Matthew Jagielski, Chiyuan Zhang, Nicolas Papernot, Andreas Terzis, and Florian Tramer. 'he privacy onion effect: Memorization is relative. Advances in Neural Information Processing Systems, 35:13263-13276, 2022.
[18] Nicholas Carlini, Daphne Ippolito, Matthew Jagielski. Katherine Lee, Florian Tramer, and Chiyuan Zhang. Quantifying memorization across neural language models, 2022. URL httips///arxi. org/abs/2202.07666 076440 2023.
[19] Nello Cristianini, John Shawe- Shawe-Taylor, André Elisseeff, and Jaz Kandola. kernel-target aligmment. In T. Dietterich, S. Becker, and Z. Ghahramani, edi- tors, Advances in Neural Information Processing Systems, volume 14. MIT Press, 2001. URL https: http::////pooeeec...eeeeee.e wwwerrps.ccpppppr.re.... pataappr_flleeppppeeeeeeee htt.f//ieee//ppeee/////eeee T771300088011100000fff5333333233
pdf
[20] Mehmet F Demirel, Shengchao Liu, Siddhant Garg, Zhenmei Shi, and Yingyu Liang. Attentive walk-aggregating graph neural networks. Transactions on Machine Learning Research, 2022.
ISSN 2835-8856. URL httth::t/////
net. htteee//foormmmdddSSSstyYtdtad
[21] Vitaly Feldman. Does learning require memorization? short tale about a long tail. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 954 959, 2020.
[22] Jiarui Feng, Yixin Chen, Fuhai Li, Anindya Sarkar, and Muhan Zhang, How powerful are k-hop message passing graph neural networks. Advances in Neural Information Processing Systems, 35:4776 4790, 2022.
[23] Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
[24] Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference Machine Learning Volume 70, ICML' page 263-12722 JMLR.org, 2017.
[25] Jhony H. Giraldo, Konstantinos Skianis, Thierry Bouwmans, and Fragkiskos D. Malliaros. On the trade-off between over-smoothing and over-squashing in deep graph neural networks. In Proceedings of the 32nd ACM International Conference on Information and Knowledge Management, CIKM '23, page 566-576, New York, NY, USA, 2023. Association for Computing Machinery. ISBN 9798400701245. 10. 10.1145/3583788 3614997
doi: 00.1145/3583788.36449999 URL https:/tts://dee org/
[26] Xavier Glorot and Yoshua Bengio. Understanding the difficulty training deep feedforward neural networks. In Yee Whye Teh and Mike Titterington, editors, Proceedings of the Thirleenth International Conference on Artificial Intelligence and Statistics, volume 9 of Proceedings of Machine Learning Research, pages 249-26492 256, Chia Laguna Resort, Sardinia, Italy, 13-15 May mlr http./ess/////ooootlooo./ html
2010. PMLR. URL |ttp
[27] M. Gori, G. Monfardini, and F. Scarselli. A new model for learning in graph domains. In Proceedings. 2005 IEFE International Joint Conference on Neural Networks, 2005., volume pages 729-734 vol. 2, 2005. doi: 10. N0.1109/JCNN.2200.555550
12

---

[28] William L. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS 17, page 1025-1035, Red Hook, NY, USA, 2017. Curran Associates Inc. ISBN 97885006
[29] William L. Hamilton, Zhitao Ying, and Jure Leskovec. Inductive Representation Learning on Large Graphs. In NIPS. pages 1024-1034, 2017.
[30] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. arXiv preprint vrxiv:2005.00687. 2020.
[31] Arthur Jacot, Franck Gabriel, and Clement Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. misschia and R. Garnett, editors, Advances in Neural Information Processing Sys- tems, volume 31. Curran Associates, Inc., 2018. URL
neurips cc/ Paper pdf
paper Sxper_filese httpr//flle/apprrreeeaeeeaa / hugpo//t...aeeee/....//e//eeeeee
[32] Adarsh Jamadandi, Celia Rubio-Madrigal, and Rebekka Burkholz. Spectral graph pruning against over-squashing and over-smoothing, The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
[33] Kedar Karhadkar, Pradeep Kr. Banerjee, and Guido Montufar. FoSR: First-order spectral rewiring for addressing oversquashing in GNNs. In The Eleventh International Confer- Learning Representations, 2023. URL httph: /ttppr///peereview..o net/ htte//formmmiee id=
3YjQfCLdr2z
[34] Fariba Karimi, Mathieu Génois, Claudia Wagner, Philipp Singer, and Markus Strohmaier. Homophily influences ranking of minorities in social networks. Scientific Reports, 8(1), July 2018. ISSN 2045-2322, doi: 10. 1038/ s41598- 218-299405-
URL http::/dpp/.t./// doi. 1ttp://///..oo.o//10//
[35] Nicolas Keriven. Not too little, not too much: a theoretical analysis of graph (over)smoothing. In The First Learning Graphs Conference, 2022. URL http://ppp//peeeeeviieeeeeeeee/ net/orrruewweeeeoom id=KQNsbAmJEug
[36] Nicolas Keriven, Alberto Bietti, and Samuel Vaiter. Convergence and stability of graph convolu- tional networks on large random graphs, 2020. URL https://axxii..... www.orgg//gaoaeeeeeeeeee 01868
[37] Thomas N. Kipf and Max Welling. Semi-Supervised Classification with Graph Convolutional Networks. In ICLR, 2017.
[38] Qiongxiu Li, Xiaoyu Luo, Yiyi Chen, and Johannes Bjerva. Trustworthy machine learning via memorization and the granular long-tail: A survey on interactions, tradcoffs, and beyond, 2025. https://///ar org/ ab5///03...2...////////// 2503. 07501
[39] Shouheng Li, Floris Geerts, Dongwoo Kim, and Qing Wang. Towards bridging generalization and expressivity of graph neural networks, 2024. URL https://arxiv..rge arw.///////////////
10051
[40] Pratyush Maini, Michael Mozer, Hanie Sedghi, Zachary Lipton,, J Zico Kolter, and Chiyuan Zhang. Can neural network memorization be localized? arXiv preprini arXiv:2307.095.. 2023.
[41] Andrew Kachites McCallum, Kamal Nigam, Jason Rennie, and Kristie Seymore. Automat- ing the construction of internet portals with machine learning. Information Retrieval, 3(2): 127-163, 2000. doi: 10.1993/A:100999388 19988. URL https:///oi.org/ ww..://///...../.....
1009953814988
[42] Amil Merchant, Simon Batzner, Samuel S. Schoenholz, Muratahan Aykol, Gowoon Cheon, and Ekin Dogus Cubuk. Scaling deep learning for materials discovery. Nature, 624(7990): 80-85, 2023. doi: 10.10388/4415566-033-06665333333
URL. https://doi. org 10. 1038/
641586-023
13

---

[43] Christopher Morris, Nils M. Kriege. Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: A collection of benchmark datasets for learning with graphs. CoRR, has/2007.0866.3 2020. URL. htttp:://axiiii http:////wwwww.../a///////////// 2000b//00000033
[44] Nimrah Mustafa, Aleksandar Bojchevski, and Rebekka Burkholz. Are GATs out of balance? In seinth- Conference on Neural Information Processing Systems, 2023. URL https
[45] Galileo Namata, Ben London, Lise Getoor, and Bert Huang. Query-driven active surveying for collective classification. 2012.
[46] Khang Nguyen, Hieu Nong, Vinh Nguyen, Nhat Ho, Stanley Osher, and Tan Nguyen. Revisiting over-smoothing and over-squashing using ollivier-ricci curvature, 2023.
[47] Giannis Nikolentzos, George Dasoulas, and Michalis Vazirgiannis. k-hop graph neural networks, 2020. URL http:::/aaxii...tt http//ba///000 06051
[48] Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom- gen: Geo- metric graph convolutional networks. In International Conference on Learning Representations. 2020. /tR./itttsss//ppeeeeieeee..e www.:neeeoooonndddeeeeaaaareeee
[49] Oleg Platonov, Denis Kuznedelev, Artem Babenko, and Liudmila Prokhorenkova. Charac- terizing graph datasets for node classification: Homophily-heterppn dichotomy and be- yond. In Thirty-seventh Conference on Neural Information Processing Systems, 2023. URL
[50] Oleg Platonov, Denis Kuznedelev, Michael Diskin, Artem Babenko, and Liudmila Prokhorenkova. A critical look at evaluation of gnns under heterophily: Are we really making progress? The Eleventh International Conference on Learning Representations, 2023.
[51] Ladislav Rampášek, Mikhail Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Dominique Beaini. Recipe for a General, Powerful, Scalable Graph Transformer. Advances in Neural Information Processing Systems, 35, 2022.
[52] Patrick Reiser, Marlen Neubert, André Eberhard, Luca Torresi, Chen Zhou, Chen Shao, Hous- sam Metni, Clint van Hoesel, Henrik Schopmans, Timo Sommer, and Pascal Friederich. Graph neural networks for materials science and chemistry. Communications Materials, 3(1):93, 2022. doi: 10. 00.1038/433246-02-000011 1162266022-00315--
URL https://doi. 1000////
[53] Benedek Rozemberezki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. CoRR, abs/1909, 13021, 2019. URL
13021
[54] Celia Rubio- Madrigaa Adarsh Jamadandi, and Rebekka Burkholz. GNNs getting comfy: Com- munity and feature similarity guided rewiring. The Thirteenth International Conference on Learning Representations, 2025. URL
[55] Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transuctions Neural Networks, 20(1):61-80, 2009, doi: 10. 109/00N. 200.....000.000666
[56] Prithviraj Sen, Galileo Namata, Mustafa Bilgic. Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classification network data. Al Magazine, 29(3):93, Sep. 2008 doi: 10. http:9//aiaaa.299..222..2 article/vies/2161
https://:////o aaai org/ index.idxx../ hwtp:/.ppppaaaaae phppaimagazine/ Pitfalls of graph neural network evaluation, 2019.
[57] Oleksandr Shehur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann.
[58] Jonathan Shlomi, Peter Battaglia, and Jean-Roch Vlimant. Graph neural networks in particle physics. Machine Learning: Science and Technology, 2(2)021001, jan 2021. doi: 10. 1088/ 1632-2153/abb/9a. httpss :/tttps://do..ooo org/ 108800638222333 20000/00//22222222222222222/
2153/abbf9a
14

---

[59] Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov. Membership inference attacks against machine learning models. In 2017 IEEE sympostum on security and privacy (SP), pages 3-18. IEEE, 2017.
[60] Huayi Tang and Yong Liu. Towards understanding generalization of graph neural networks. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 33674-33719, PMLR, 23-29 Jul 2023. htlLhhtps://// httpps:/proceeediggs.. mml. wtw../.ppee///////aa///p/eee
.ttll
[61] Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M. Bronstein. Understanding over-squashing and bottlenecks on graphs via curvature. In International Conference on Learning Representations, 2022. htt.:httts://ppprrrrrre A
net/ met//orumn?dd=UmmnHe
[62] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph Attention Networks. In ICLR, 2018.
[63] Wenhao Wang, Muhammad Ahmad Kaleem, Adam Dziedzic, Michael Backes, Nicolas Papernot, and Franziska Boenisch. Memorization in self-supervised learning improves downstream generalization. The Twelfth International Conference on Learning Representations, 2024. URL http:::///pppeeeeeeeeee www.eeewweee/foooreeeeee Korrerid-usuissaaee PPaxxxx
[64] Zhiyang Wang, Juan Cervino, and Alejandro Ribeiro. A manifold perspective the statistical generalization of graph neural networks, 2024. URL https:t/atsxiiii org/abgg aba/2406.... 2400605225
[65] Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simplifying graph convolutional networks. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 6861-6871. PMLR, 09-15 Jun 2019. URL https:://rroceedingg mlr press/ v97 www///ww1...... html
[66] Chenxiao Yang, Qitian Wu, David Wipf. Ruoyu Sun, and Junchi Yan. How graph neural networks learn: Lessons from training dynamics. Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp, editors, Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 56594-56623, PMLR, 21-27 Jul 2024. mlr. press/ h2tll//25///2g22
URL holl:tttss//prrceeding
html
[67] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. In International Conference on Learning Representations, 2017. URL htt/httttt//oopeeeeieee wttprrrewwweeeeeeeeeeeeeeeeeee
[68] Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Be- yond homophily in graph neural networks: Current limitations and effective designs. Advances in Neural Information Processing Systems, 33, 2020.
15

---

NeurIPS Paper Checklist
Claims
Do the main claims made the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: We clearly claim the contributions and scope of our work in the abstract and introduction. In summary, we introduce the first framework to quantify memorization in GNNs and identify multiple characteristics that influence memorization.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We discuss the limitations in Appendix
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model well-specification,
asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets with few runs. In general, empirical results often depend implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't t acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each thcoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [NA]
16

---

Justification:
We don't t have theoretical results in this work.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross-referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experi- mental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification:
We provide the code base reproduce all of our results.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible important, regardless of whether the code and data are provided not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often good way accomplish this, but reproducibility can also provided via detailed instructions for how to replicate the results, access to a hosted model (c.g.. in the case of large language model), releasing of model checkpoint, or other means that are appropriate to the research performed.
example, the contribution
While NeurIPS does not require releasing code, the conference does require all submissions provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is new model (e.g., a large language model), then there should either be a way to access this model for reproducing the results way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited some way (e.g., registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
We provide the code necessary reproduce our results. The datasets are publicly available.
17

---

Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please the NeurIPS code and data submission guidelines (https::/nnips.cc/pplll
guides/ Soaele//CooSSuuissstiss. ssionoiicyy for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed the results. See the NeurlPS code and data submission guidelines (https: guides/CodeSubmi wttpbbmmsssooooooccic.. onPolicy for more details.
reproduce cttpsccccpbbllcccccccccccc
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: We document all the necessary hyperparameters for reproducing the results in the Appendix H
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report eπror bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification:
We provide statistical tests and 95% confidence intervals for all of our results.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, least for the experiments that support the main claims the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard enror of the mean.
It is OK to report 1 I-sigma error bars, but one should state it. The authors should preferably report 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
18

---

For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
Experiments compute resources
Question: For each experiment, does the paper provide sufficient information the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experi- ments?
Answer: [Yes]
Justification:
See Appendix H.3 for experiment details.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics httts:://tttt:tee http:////tt///ttaccccticeeeeeeee
Answer: [Yes]
Justification: We adhere the NeurlPS Code of Ethics and our submission does not need any exceptions.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., .., if there a special consideration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our work deals with characterizing and explaining the phenomenon of memorization in GNNs. Our work by itself poses no negative societal impact. In fact, our work sheds light on the pitfalls of graph neural networks' memorizing sensitive information and its implications on security and privacy. Also see Appendix
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g.. disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploy- ment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied par- ticular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point out. For example, an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
legitimate to point out that
19

---

The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
Justification:
This work poses such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions access the model implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer:
[Yes]
Justification:
In the form citations, all the original creators have been attributed.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets released, the license, copyright information, and terms of use in the package should
be provided. For popular datasets, wwpprawi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.
For existing datasets that are re-packaged, both the original license and the license the derived asset (if it has changed) should be provided.
If this information
available online, the authors are encouraged reach out the asset's
creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
See supplementary material.
Guidelines:
The answer NA means that the paper does not release assets.
20

---

Researchers should communicate the details of the dataset/code/mmodl as part of their sub- missions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsoureing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should paid least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applica- ble), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non- standard component of the core methods in this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this work does not involve L.MSs as any important, original, non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components. Please refer our LLM should or should not be described.
for what
21

---

A Appendix
Limitations. Our work proposes an end-to-end framework to study memorization in semi-supervised node classification setting in GNNs. While our findings on the interplay between homophily, training dynamics, and memorization offer significant insights, this foundational study also presents several avenues for future exploration.
1. Conceptualizing Memorization on Non-IID Graph Data: Our approach, inspired by the leave- one-out framework of Feldman (21). quantifies memorization by observing changes in model behavior when node's label is masked during training. In the semi-supervised node classification setting, where the entire graph structure and all node features are accessible during training. our method correctly isolates the influence of single training label. The difference in predictions between a model trained with a specific node's ' label and one without serves as a robust measure of that label's 's memorization as shown through numerous experiments. However, this is foundational step. The inherent dependencies between nodes in a graph suggest that more intricate definitions of memorization could be developed. Future work could explore how the memorization of one node influences the predictions on its neighbors, moving from single-node perspective to more holistic, subgraph-level understanding of memorization. This could lead new metrics that capture the unique relational aspects of GNNs.
Effectiveness of the Label Disagreement Score (LDS); Our proposed Label Disagreement Score (LDS) effectively identifies nodes prone memorization by measuring local inconsistencies of node in the label-feature space. As demonstrated, we find that nodes with higher LDS are more likely be memorized. Nevertheless, the paper acknowledges that the effectiveness of LDS might be reduced in highly heterophilic graphs with non-uniform feature and label distributions, such as the Actor dataset. In such complex scenarios, the local neighborhood might not provide clear signal, making it difficult to distinguish between atypical nodes that require memorization and the general noise of highly diverse environment.
Limitations of Graph Rewiring: As an initial strategy to mitigate memorization, we explored feature-similaarty similarity-basee and associated privacy risks by increasing graph homophily. However. this approach relatively simple and may not be effective, especially on real-world graphs. The process of adding or removing edges based solely on feature similarity might result in information loss.
rewiring [54). Our results confirm that this can reduce memorization
Future work. Studying memorization for other tasks such as link prediction and graph elassification can be an interesting future work. In Section 5.2, we already extend our memorization framework to characterize memorization in graph classification setting. We find interesting connections between node feature noise and the model's ability to memorize entire graphs. Future work can also focus on understanding the role of over-squashing (2) and over-smoothing (35) on memorization. In our work, have primarily analyzed the training dynamics of GCN, future work could also extend this analysis to GATs [62, [3] and Graph Transformers [51] since the attention mechanism can have non-trivial effects memorization.
B Broad Impact
We propose a new framework to study the memorization phenomenon in GNNs. Our work provides a comprehensive understanding of the factors that contribute to memorization in GNNs, including the role of homophily, label informativeness, kernel alignment, and feature-label inconsistency. We also discuss the implications of memorization for privacy risks. Our findings can help researchers and model developers better understand the memorization phenomenon in GNNs, and encourage the development of more robust and generalizable GNN architectures.
C Definitions
In this section we provide definitions of all the metrics we have used.
Definition (Edge Homophily) The edge homophily ratio is defined as the fraction of edges graph that connect nodes of the same class and is given by
22

---

K(u,e) e): (u, v) E & A yu = yo
(5)
[
This measure is used to generate the synthetic datasets in 668
Definition (Node Label Informativeness [49] Given an edge (u, v) sampled from and let yo and yo be the respective class labels. The label informativenes gives measure of predicting the label yos given we know the label Yo and is encoded by the normalized mutual information:
NLI H (yu) - (yulll))
(6)
H(uw)
where H Hyy)) is the entropy that tells how difficult it would be predict the label without knowing yo- A higher label informativeness implies a node's 's neighborhood gives enough information predict the label. The label informativeness is computed for all pairs of edges and labels give final graph level score.
Definition (Homophily in terms of aligmment (66]) The notion of homophily can also be en- coded in the form of alignment between the adjacency matrix of the graph A and the optimal kernel O 19.. i.e., A(A, O*) measures two connected nodes have the same labels.
Definition 4 (Optimal kernel (e") ) and kernel alignment) The optimal kernel @' proposed in 199 defined as O YY and measures how similar two instances of data points are. Further, can define similarity metric that measures the alignment between two kernels K₁ and
K₂ as
(K1,K2) K2)
A(K1 K2)
| | K2||F
This metric can be seen as a generalization of the cosine similarity applied to matrices and it satisfies the triangle inequality.
D Proof for Proposition 2
In this section, we provide a simple proof to support our empirical results Proposition 2 We showed that one of the main reasons GNNs exhibit memorization is their failure to reconcile the conflicting signals induced by the training dynamics of GNNs, i.e., the implicit tendency to align the O with the A. even when the graph structure is uninformative (i.e., exhibits low A(A, +*)) and can be detrimental to the learning task, while, the overall training objective remains minimizing the training loss. We adopt the terminologies from [66]
D.1 Setup and Assumptions
We consider a GNN trained for node classification on graph G = (V,E) with propagation matrix A. Let D train {v,, Mi bi),,, eve be the labeled training nodes (n; | D. Let F, RT be predictions at time t and Y E R" be true labels. We minimize the empirical risk C(F,,)) F. 2
Assumption (GNN training dynamics increase kernel-graph alignment) The optimization process for GNNs implicitly leverages the graph structure A, such that A(@r, A) tends increase during training.
Assumption (Low homophily) low homophily settings, alignment between the A and O low.
23

---

D.2 Low Homophily (A(A, )²)) Implies Low Kernel-Targee Alignment (A(O,, +*))
The alignment between two kernels 19 K1 and K₂ can be characterized by the cosine similarity as shown in Equation 7 Let @(K1 K₂) matrices. Our proof relies on the simple triangle inequality and a geometric approach to show that, GNN that aligns its adjacency matrix A with the neural tangent kernel Q cannot simultaneously also align well with the O" and thus leads to memorization.
(A(C, K2)) denote the angle between the kernel
Proof:
We define three angles 8 and y the angles between the matrices A(O,, A), A(A, O*) and A(er. @*) respectively, that is
C arccosí (A(O,, (1(0),,A) A)) be the angle between θ, and A. g = arccos (A(A, e*)) be the angle between A and O*.
7 arccos(A((,, )²)) be the angle between O and O*
Using the triangle inequality on the angles we write two inequalities as
7 S c c 8
(8)
8 8 E
(9)
Rearranging to establish a lower bound on 7
7 2 6 -
(10)
Analyzing the inequality 10 light of our assumptions we get
1. Based on Assumption ! a high kernel-graphe alignment implies, the angle between A and O should be small (ideally, 09), from geometrical perspective we can think of this as two vectors pointing in the same direction"]
Based on Assumption 2 in low homophily settings, the angle between and O+ should be large (c.g, 90%)
Therefore, the term 8 - represents a large angle minus small angle, which is still a large angle (quantitatively close to 6). Inequality [0] states that y must be greater than or equal to this large angle (5 - c). This forces y itself to be large.
large angle y between the kernel O and the optimal kernel O signifies poor alignment between them. Since 7 = (A(,,, θ*)) and the arccos function is monotonically decreasing on its domain [-1, 1]. a large angle 7 (specifically, 7 8 e, where
is close 90º more) necessarily implies that the alignment value A(@,, θ*) must be low (close to or negative).
Combining the upper bound equation g and the lower bound equation 10 get 8 S 8 + This confirms that when e is small, 7 is tightly constrained around the large value (y 23 8).
Therefore, the geometric constraints imposed by the triangle inequality demonstrate that high kerne-- graph alignment (small c) under low homophily (large 8) forces the angle 7 between the learned kernel and the optimal kernel to be large, resulting in low kemel-target alignment (A(O,, O*)).
We illustrate our proof through a conceptual diagram in Figure 10 We visualize a hypothetical loss landscape of GNN model (e.g.. GCN trained on syn- cora as in Proposition 2 in 2D contour plot. The blue color represents low loss regions with wider basins, indicating global minima that favor generalization. In contrast, the narrower, red regions correspond to local minima that may achieve low training loss but typically lead to memorization and poor test performance. We visualize the alignment matrices vectors in this 2D space. We get two regimes:
'Note that, these are alignment matrices and not simple vectors, besides, these kernels exist in high di- mensional space which is not feasible to visualize. Our intent here is to provide an intuitive picture of how memorization emerges in GNNs.
24

---

Low homophily regime- We know that GNNs possess an implicit bias to leverage the graph structure during optimization, leading to kerne--rrah alignment, A(O,, A) [66]. This tendency further supported by our experiments in Proposition 2 which demonstrate that kernel-graph alignment increases as training progresses. However, whether such alignment benefits the model depends critically on the graph homophily level, which is encoded in the alignment between the adjacency matrix and the optimal kernel O², denoted as A(A, θ*). Both our geometrical proof and empirical results suggest that in low homophily regimes, the model's tendency to align its NTK matrix with the adjacency matrix becomes problematic. Even when the graph structure contains little task-relevant information, this alignment bias pulls the model away from the optimal kernel O* which would otherwise guide the model toward better generalization. We illustrate this phenomenon conceptually in Figure TO(a) where visualize the adjacency matrix A, the NTK kemel matrix O and the optimal kernel matrix O* as ID vectors in a hypothetical 2D loss landscape, represented red, green, and blue colors, respectively. In this visualization, the NTK kernel matrix θ aligns closely with A, as indicated by the small angle between them (see Appendix (.2). yet it points in a direction far from the O' which represents generalization minimum. The purple trajectory traces the path the model actually follows during optimization, resulting in a biased solution that achieves low training loss through memorization but generalizes poorly unseen data.
High homophily regime- In contrast, within the high homophily regime, the increasing kernel- graph alignment A(@,, A), i.e. the model's tendency leverage the graph structure, becomes highly beneficial for the learning task. We demonstrate this in Figure [obb where, as before, we visualize the adjacency matrix A, the NTK kernel matrix O, and the optimal kernel matrix @* ID vectors in a hypothetical 2D loss landscape, shown in red, green, and blue colors, respectively. In this scenario, observe that the alignment between Q and the adjacency matrix A does not misguide the model away from the direction of the optimal kernel @". Instead, this alignment actually serves as beneficial guide that helps the model toward solution close to the optimal kernel. Consequently, the model converges to solution that generalizes well, performing well on both training and testing data.
1.5
1.5
1.0
-1.9
100
-0111
0.0
-1509
-0.5
-0.5
-1.0
2
-1.0
2311
-1.5
-1.0
-0.5
0.0
-15
ndtoo mp Togerrory
Direttion
optinistinn Wijerwyy
Optinaal Slowetin
Graph Dination A
*
Tini Soltion
Cruph ruction
Tix Good Salacion
(a) Low homophily.
(b) High homophily.
Figure 10: We illustrate the emergence of memorization in this conceptual diagram. We visualize the alignment matrices as ID vectors on a hypothetical 2D loss landscape of some GNN model, for instance a GCN trained on syn-cora cora dataset as in Proposition 2 In low homophily regimes, the model's tendency to align the A with O (kernel-graph alignment) results in the model deviating away from the optimal kernel e resulting memorization. Contrarily, in high homophily regimes, the kernel-grae -gaah alignment does not induce an opposing behavior with respect to the optimal kernel, leading to good generalization.
25

---

D.3
Notations
Symbol
Deseription
G (A
A graph with an adjacency matrix and node feature matrix X.
D
The true, underlying data distribution over node-label pairs (v, v).
Drain
The training set, collection of n labeled nodes {(0), yi) sampled from D.
Us 1/j
A specific node in the graph, indexed by i or j.
Vis 1/j
The ground-truth label for node or U/.
T
The learning algorithm (e.g.. GNN training via gradient descent). A predictive function or model learned by the algorithm T.
P
The specific model function learned by algorithm A when trained on the set Dusin-
The leave-one-out model, trained on Dmin after excluding the i-th sample (vi, y:).
PP|-]
Denotes the probability of an event. The subscript indicates the source of randomness.
[[D-]
Denotes the expectation of random variable.
mem (T, Diriin Egen(]]
The memorization score for the i-th sample in the training set Drrin-
The generalization error of model f, its expected error on the true distribution DD.
Emnin (J, Dariin)
The empirical training error of model / on the specific set D
D.4
Detailed Proof for Proposition
In this section, we leverage the results (Lemma 4.2 and 4.3) proposed by Feldman 21 to highlight two regimes learning conditioned on the graph homophily,
D.4.1 High-homophily regime
GNNs have an implicit bias to leverage the graph structure during optimization. When the input graph has high homophily, the GNN's inductive bias aggregate messages from the neighbors aligns well with the data structure (graph whose neighboring nodes have similar labels) in such cases GNN can obtain good generalization performance.
Lemma (Lemma 4.2 Feldman (27)) For given dataset S, learning algorithmm T and distribu- tion P over the input-output pair x Y, the memorization score is related to the generalization gap as follows
E SSp
Σ iE[n]
mem(T, ST, = E[Earin]]
[[
(11)
In high-homophily graphs, the generalization gap is low, this is also supported by our extensive experiments on synthetic graphs and real-world graphs and also our NTK analysis. Thus, we have
E| [rain]
E[Egen]
mem ( S, =
(12)
In practice, experiments reveal even in high-homophily graphs, small number of nodes are memorized, however the cost not fitting these nodes does not incur high penalty on the training error (21).
D.4.2 Low-homophily regime
Explaining memorization this regime forms central theme of our work. seen earlier in Proposition 2 in low- low-homophily graphs the graph structure is not informative but the tendency of the
26

---

GNNs to still leverage the graph structure results in model that has to memorize to achieve zero training loss. This is explained by Feldman [2]'s Lemma 4.3 which we adapt our GNN setting as follows
Lemma 2 (Lemma 4.3, Feldman (21) The empirical error on high LDS node o; is related to the leave-one-out error. For an atypical node v; with a high Label Disagreement Score (LDS), the model trained without it, fu relies an uninformative graph structure, resulting in a high leave-one-out error. The relation between leave-one-out- error, memorization score and the model's empirical error is given by
P ())T(s)((())) # yul -P--Ats((e)))fff * wl ,,,
(13)
where, the leave-one-out-erro is high because the model needs the label of the node iz with high LDS to correctly predict it.
P P)~T(S((::))(())) + vil +
(14)
However, the overall training objective strives achieve zero empirical error
P Py~T(s)([(()) ml
(15)
Substituting Equations 14 and 15 in 13 we get,
~ 1 mem mem (T, = mem (em[T,S,i]
(16)
Thus, in low-homophily settings the atypical nodes characterized by our Label Disagreement Score need to be memorized by the model in order achieve zero training loss.
E Additional Results Memorization Scores for Node Classification
In this section, we present additional memorization results on both the real-world and synthetic datasets.
E.1 Our Memorization Score Well Behaved
Synthetic dataset In Figure we plot the memorization scores vs frequency for syn- cora across the data categories (Sc, Ss. S7 Sg.. We can see that the candidate nodes show higher memorization scores compared to the other category nodes such as Sş or Sg- We also present the average memorization scores (with 95% confidence interval (CI) and the memorization rate of Sc in Table for syn-cora dataset, trained on GCN model.
(a) syn-cora-0.0 (b) syn-cora-0.3 (c) syn-cora-0.5 (d) syn-cora-0.7 syn-cora-L.0
Figure 11: Distribution of Memorization Scores syn-cora: Comparison of memorization rates across node categories for syn-cora graphs with increasing homophily levels trained with GCN. GNNs exhibits memorization behavior, i.e., the memorization scores higher (lower) for Sc (S1) compared to Sg or Sg-
Real-world graphs. Similarly, Figure 12 Figure and Figure 14 show the distribution of memo- rization scores for nine real-worle datasets trained GCN, GATv2, and GraphSAGE, respectively.
27

---

Table 4: Memorization score (MemScore) and Memorization rate (MR) for the candidate nodes in syn-cora dataset averaged over 3 random seeds on GCN. Heterophilic graphs have higher memorization score and rate than homophilic graphs.
Avg
MR
Dataset
MemScore
(%)
ayn-cora-ba 0
0.709120.0166
83.63=1.82
syn-cora-hO.. 3
0.5573+0.0047
63.96#1.19
ayn-cora-ho.5
0.4106+0.0126
45.95=1.62
ayn-cora-ho.1 7
0.2616=+0.0077
25.98+1.45
syn-cora-h1.0
0.0021#0.0005
0.00=0.00
can be observed that for most of graphs, the nodes in Sc(S,) have higher (lower) memoriza- tion scores than nodes in Sg and Ss. We also present the average memorization scores and the memorization rate of Sc in Table for 9 datasets trained on different GNN models. We observe that heterophilic graphs, such Cornell, Texas, Wisconsin, Chameleon, Squirrel and Actor, have higher memorization score and memorization rate than the homophilic graphs, i.e., Cora, Citeseer and Pubmed, which is consistent with our Proposition]] I We can observe from Tablee5thai Pubmed shows the most resistance to memorization as it has, a very low average memorization score. We can explain this behavior by invoking our Label Disagreement Score reported in Table TO where we can see the LDS values for both memorized and non mom-meerii nodes are very similar, indicating that Pubmed has a highly informative neighborhood that can be leveraged by the model learn generalizable patterns. To formally verify that nodes in Sc (S,) have statistically significantly higher (lower) memorization scores than nodes Sş and Sg, we also conduct t-test on the memorization scores of all nodes in each category. The details of which are outlined in the Appendix E.2
Table 5: Memorization score (MemScore) and Memorization rate (MR) for the candidate nodes real-world dataset, averaged over 3 random seeds. Heterophilic graphs have a higher memorization score and rate than homophilic graphs.
Cora
Citeseer
Puhmed
Avg
MR
Avg MemScore
MR
Avg MemScore
MR
Model
MemScore
(%)
(%)
(%)
GCN
0. 0003
9.7+0.1
0.266 +0.0048
28.4
0.094 #0.0012
8.1
GATv2
0. 1663=000115
17.0=2.0
+.222100.0114
26.3+0.9
0.1312+0.008 0004
12.9+0.5
GraphSAGE
0. 0.100=000044
10.0=0.4
0.241 1141110.000 0000
24.3+0.6
0.0973+0.0023
9.4+0.3
Corelll
Texas
Wisconsin
Avg
MR
Avg MemScore
MR
Avg
MR
Model
MemScore
(%)
(%)
MemScore
(%)
GCN
0.3695+0.0153
36.5+1.7
0.3257 00.107
31.1+1.2
0.2873+0.0116
29.2+0.9
GATv2
0.4102+0.0089
39.0+1.0
0.3701
35.4+1.4
0.3227#0.0135
32.0+1.3
GraphSAGE
0.3542+0.0130
35.0+1.6
0.381770.0887
33.0&1.1
0.3004:0.0120
10.1
Chameleon
Squirrel
Actor
Avg
MR
Avg
MR
Avg
MR
Model
MemScore
(%)
MemScore
(%)
MemScore
(%)
GCN
0.5285+0.0053
52.920.3
0.505020.0133
53.6+1.3
0.3821 0000087
38.320.6
GATv2
0.4962+0.0269
50.3+3.3
0.5131#0.0179
52.9+1.9
0.3599 10311
35.9+1.0
GraphSAGE
0.4570=0.0020
46.020.4
0.5372+0.0021
54.5+1.1
0.3715=0.0071
37.020.5
E.2
Statistical Significance of Memorization Scores
In this section, we present the results for t-tests conducted on the memorization scores obtained from training GCN on real-world datasets in T We test the null hypothesis Ho := M(Sc) S M(s)). Rejecting the null hypothesis indicates that the memorization scores of nodes in Se are significantly higher than those in Ss. Our results reject Ho with p-value < 0.01 and large effect size (iee, more than 0.5) for all datasets, indicating that the observed difference in the memorization scores of Sc and Sg is statistically and practically significant. We also apply the same t-test for all
28

---

Frequency Count
Brequency 223
Frequency
5500
2000
1:50007--05 925 65o 635 1.0
-1:0-66.1--------- 325 a 675
-66
-2.4
-0.3
5.0
02
64
Memorization Score
Momorization Score
Mamorization
(a) Cora.
(b) Citeseer.
(c) Pubmed.
Frequency Court.
Frequency
3.00-2775-4 10:30-223 6.23 030 6.1 185
-122-11 55--2:3 0.6 015 250 6.5
10
Memorizatian Scom
Memoriztion Scom
Memoriaation Score
(d) Corelll.
(c) Texas,
(f) Wisconsin.
402
020
390
Frequency Court
303
020
frequency
200
100
020
100
400
-1100-05
Memorization Score
Memorization Score
Memorization Scone
(g) Chamelcon.
(h) Squirrel.
(i) Actor.
Figure 12: Distribution of memorization scores for each node category Ss. Sc, Sr, and SF, on real-world datasets, trained on the GCN model.
data subsets. The results confirm that Sc (Sy) significantly more (less) memorized by the GNN model than Ss and Sg.
E.3 Larger Datasets
The leave-one-out memorization 21 is theoretically well-founded and provides precise notion of ver-sample-level memorization. While the ideal form requires training multiple models. in our work, approximate it efficiently: Our method only requires 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 present additional results on larger datasets such as Photo, Physics, Computer [57] and ogb-arxiv (30] datasets in Table 7 We can observe that our proposed framework scales well to large graphs and the datasets exhibit low memorization rates as they are highly homophilic which aligns with our Proposition 1.
E.4 Graph Transformer
We also experiment with a Graph Transformer (GT), use the architecture proposed in 50 with following modifications: we use 2 attention heads and I-layer GT (Input - Linear Projection - [Attention FFN Block] -> Output Linear). The results on four real-world datasets are presented in Table A caveat of applying our framework to study memorization in Graph Transformers is that it hard to analyze
non-trivial effects the attention mechanism can have on memorization. Further, since Transformer architecture is more general purpose than GNN, it is unclear if transformer shows an implicit bias leverage the graph structure and a lack of NTK formulation for Graph Transformers makes it difficult to explain the emergence of memorization.
29

---

1600
Frequency Court
Frequency
922
2000
132
1000
143
110---1--55--2-- 3.00 023 050 0:15 1:50
-1.000001 23-05-5-23 2/03 323 030
0.5 1.0
-5A -53
-03
0.0
0.2
54
06
Memorization Score
Momorization
Momorization
(a) Cora.
(b) Citeseer.
(c) Pubmed.
32
Frequency Count
Prequency
-1.00-2175
13--0----------3 1.30--23
030 6.7
-1:0-2.73-
-0200-0-.00 10-00.22 023 230
1222--005----- 022
Memorization Score
Memorization Score
Memorization Score
(d) Corelll.
(c) Texas,
(f) Wisconsin.
390
Frequency Count
230
502
Prequency
2.0
800
160
Memorizabio Score
Memorizaton Score
Memorizatin Score
(g)
Chamelcon.
(h) Squirrel.
(i) Actor.
Figure 13: Distribution of memorization scores for each node category Ss, Sc, S,, and Sp. on 9
real-world datasets, trained on the GATv2 model.
E.5 2-hop aggregator methods
To analyze whether our findings memorization are robust to the GNN's receptive field size, or if they are merely an artifact of 1-hop message passing scheme, we conducted additional experiments with another GNN variant called Simplified Graph Convolution (SGC) (65). 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 four real-world datasets in T
F Label Disagreement Score
Choice of k. An important hyperparameter for calculating the LDS is the value of k. in our case we set this value to 3, here the idea is to mimic the hop aggregation step of the GNN model. By setting & = 3, we model that is trying to aggregate information, and if the label and feature distributions are uniform or do they have large surprises that can induce memorization. Setting smaller & value allows to analyze the local neighborhood anomalies. is possible to also calculate the LDS by setting higher values such 5, 7, 10. but the GNN models aggregate information from higher order neighborhoods, unless they are explicitly designed to do so in cases like [4 22 20
trying to trace how the 3-hop neighborhood of the graph looks like for GNN
in practice do not have large receptive fields to
Additional results. In Table 10 we present the L.DS for remaining datasets trained on GCN model. In Table II and Table 12
present the LDS for datasets trained on GraphSAGE and
30

---

802
Peoquecy Count
320
2520
Frequency
13
2006
13
130
-106-071--65--2222 2.00 323 050 0:15 1.0
-100-077 100------------------0--- 2-5---5--22- 2,03 323 050 075 1.0
-0.35 23
-230
0.5
6,25 5.5 6.5
Memorization Score
Momorization
Memorization
(a) Cora.
(b) Citeseer.
(c) Pubmed.
35
Count
Prequency
-1.00-277--- 1.00-123 0:5 050 6.5 182
-1.0--23--..000 -.30-..22 025 239
-2.21 -0.3 22--0---22 63t 025
Memorization Score
Memorication Score
Memorization Score
(d) Cornlll.
(c) Texas,
(f) Wisconsin.
700
$52
Frequency Count
600
Frequency
Frequency
400
Memorization Score
Memorization Score
Memorization Score
(g)
Chamelcon.
(h) Squirrel.
(i) Actor.
Figure 14: Distribution of memorization scores for each node category Ss. Sc, Sr, and SF, on 9 real-world datasets, trained on the GraphSAGE model.
GATv2 respectively. Across these datasets, we can observe that our proposed metric consistently distinguishes memorized and non-memorized nodes through significantly higher LDS for memorized nodes than non-memorized ones. The metric also explains why certain datasets are potentially resistant to memorization. For instance, in Figure [2(c) and Table I0 we can observe that Pubmed shows little to no candidate nodes as memorized, indicating both the models f and output high confidence. potential reason for such consistent performance of the models can be attributed uniform neighborhood, that is, there are no surprise nodes with unusual labels or features that might require memorization learn.
Nuances of LDS. However, we also have to note certain shortcomings of our proposed metric, for instance the LDS for Actor dataset trained GCN, GraphSAGE and GATv2 consistently yield statistically less significant scores to distinguish memorized and non-memorized nodes, we surmise this does necessarily mean failure of our metric, but rather the inability of the metric to capture the nuances of the dataset itself. From Table T8] we can observe that the Actor dataset is highly heterophilic and the node label informativeness very low, thus the neighborhood of the dataset is highly non-uniform to yield consistent label disagreement scores. It is also possible the different aggregation methods used, for instance the attention mechanism in GATv2 concatenating the final feature vectors instead of simple mean aggregation in GraphSAGE could also affect the LDS calculation. Further, in TO Table we get oc for the effect sizes of Pubmed and, Wisconsin and Texas. For Pubmed, the reason is because there are either or no nodes showing memorization and for datasets like Wisconsin and Texas, these are very small heterophilic datasets and the variance of scores for memorized and non-memorized is 0.0, hinting they all have similar LDS values. While this highlights technical limitation applying standard variance-based effect size metrics these edge cases, it primarily reflects the highly constrained nature of local neighborhoods and the resulting
31

---

Table Results of statistical t-test for comparing memorization scores between different categories on 9 real-world datasets. trained on GCN. It is confirmed that Sc: (S₁) is significantly more (less) memorized by the model than Ss and SE.
Cora
Citeseer
Pubmed
Null Hypothesis
p-value
Eflect size
p-value
Effect size
p-value
Effect size
M(Sc) S M[Ss]
0.000
0.5421
0.000
0.9483
0.000
0.2427
M(Se) _ M(SE)
0.000
0.4211
0.000
0.7998
0.000
0.2365
M(Ss) S M(Ss)
0.000
0.7227
0.000
0.8617
0.000
0.2103
M(Sa) S M(S)
0.000
0.5625
0.000
0.6442
0.000
0.1989
Comell
Texas
Wisconsin
Null Hypothesis
p-value
Effect size
p-value
Effect size
p-value
Effect size
M(Sc) S M(Sss)
0.002576
0,9163
0.000
1.4675
0.000
1.4941
M(Se) S M(SE)
0.000831
0,9849
0,000
1.3502
0.000
1.1926
M(Ss) < M(S)
0,000002
1.6713
0,000
1.6077
0.000
2.1659
M(Sa) < M(Sr)
0.000365
1.0621
0.000
1.3398
0.000
1.4669
Chameleon
Squirrel
Actor
Null Hypottesis
p-value
Eflect size
p-value
Effect size
p-value
Elfect size
M(Sc) S M(Ss}
0.000
1.6719
0.000
1,4719
0.000
1,2230
M(Sc) S M(SE)
0.000
1.4670
0,000
1.5799
0.000
1.0820
M(Ss) S M(Ss)
0,000
1.7081
0.000
1,5538
0.000
1,2615
M(Sa) S M(Sr)
0,000
1.3474
0,000
1.1429
0.000
1.1544
Table 7: Memorization score (MemScore) and Memorization rate (MR) for the candidate nodes on four larger datasets, averaged over 3 random seeds, along with empirical runtimes.
Avg
MR
Runtime (Scconds)
Datasets
Nodes
Edges
Homophily
MemScore
(%)
Photo
0.009340.0088
0.1+0.0
7,650
238,162
0.7850
3.97+0.24
Physics
0.0156#0.0018
0.4+0.1
34,493
495,924
0.8724
17.82=0.24
Computer
0.0005+0.0234
0.6+0.9
13,752
491,722
0.6823
6.26+0.19
ogb-arxiv
0.0031+0.0051
0.4+0.3
169,343
1,166,243
>0.5
491.01+1.55
LDS values on these specific small graphs, rather than necessarily invalidating the underlying concept of label disagreement. It indicates that on such graphs, the local disagreement patterns measured by LDS might be very uniform within certain node groups
Computational complexity of LDS. Calculating the Label Disagreement Score (LDS). LDS; (v:(Sc), requires finding the k-nearest neighbor set Gk-NN for each node v; E Sc. We use the 12 distance on input features x E R4, a naive implementation involves pairwise distance computations and selection. For each U, this takes roughly O[[Sc|d |Scl log (Scl) time. Repeating for nodes in Sc yields an overall complexity of approximately O(ISc (2 + log (Scl)).
Utilizing optimized libraries like scikit-lean often employing spatial indexing (e.g., k-d trees) built on the features of nodes Sc, can improve average-case performance. The index construction takes roughly O[Seel log [Scl)) time. Querying for k neighbors for each Sc then has an average cost potentially closer to ( log [Sc]). The overall optimized average-case complexity becomes approximately O(SSold |Scl + |Sckk log [Scl).
Since |Scl typically scales with the total dataset size N (i.c., |Scl x N), the computational cost exhibits super-linear dependence on N. The optimized complexity scales approximately as O(Ndlog N + Nk lo N). This dependence explains the increased runtime observed for larger datasets. While optimized implementations enhance feasibility. the necessity of indexing or querying within a node set whose size grows with N fundamentally governs the scaling of runtime. We report the empirical runtime for calculating the LDS on all datasets trained GCN, GraphSAGE and GATv2 in Table T9, Table 20 and Table 2T] We can observe that the runtime for LDS computation larger for larger graphs such as Pubmed, Squirrel and Actor datasets.
32

---

Table Memorization score (MemScore) and Memorization rate (MR) for candidiate nodes on four real-world datasets, averaged over 3 random seeds, with Graph Transformer as our backbone model.
Avg
MR
Runtime
Datasets
MemScore
(%)
(Seconds)
Cora
0.1359=0.0072
13.4+0.7
Citeseer
0.2486=0.0000
24.9+0.20
1158.74+7.11
Chameleon
0.2807+0.0150
27.3#1.3
1222.66+1..
Squirrel
0.4810+0.0094
47.7+1.2
4748.68+41.52
Table 9: Memorization score (MemScore) and Memorization rate (MR) for candidiate nodes four real-world datasets, averaged over 3 random seeds, with SGC as our backbone model.
Avg
MR
Datasets
MemScore
(%)
Cora
0.0482+0.0165
3.8+0.4
Citeseer
0.1124=0.0213
9.7+2.8
Chameleon
0.3852#0.0111
37.3+0.8
Squirrel
0.3745#0.0141
34.5+3.2
G Strategies for Mitigating Memorization in GNNs
In Section 6 we diseussed the practical implications of studying GNN memorization. We showed how memorization can put models at privacy risk as adversaries can easily infer sensitive training data. In this section, we propose surprisingly simple yet effective strategy mitigate memorization, namely Gruph Rewiring, which is the process of modifying the edge structure of the graph based
or feature similarity [10] [54 and has been shown to mitigate issues like over-squashing 2 and over-smoothing
on some pre-defined criteria such as Ricci curvature 66 25 46), spectral gap K3] 32
[35] while also improving the generalization performance on downstream tasks. Our theoretical results in Section d that one of the key factors influencing memorization in GNNs is the graph homophily. Ideally, we can optimize homophily directly to control the memorization. However, the challenge here is that calculating homophily requires access to all the node labels, which conflicts with the downstream task of predicting the labels. alternative is look for proxy criteria that can indirectly influence the homophily level.
Graph Rewiring Reduces Memorization. We adopt the graph rewiring framework proposed in [54], which adds or (and) deletes edges by computing the pair-wise cosine similarity. The edges are ranked and modified such that their inclusion/exclusion should lead an increase in the mean feature similarity between the nodes. We defer the readers to [54] for more details on the rewiring framework. We hypothesize that graph rewiring based on feature similarity will indirectly improve the graph homophily, which should effectively decrease the memorization in GNNs. To test this hypothesis we train GCN with 3 random seeds on the syn-cora dataset and compute memorization scores based on our framework (Section 33. we rewire the graph by adding or (and) deleting edges and recompute the memorization scores. We also measure the average reduction in memorization scores and memorization rate on the candidate nodes Sc for the GNNs trained on rewired graphs compared to those trained on the original graphs. Note that, the number of edges to modify is a hyperparameter that needs to be tuned depending on the graph. We consider {100, 500, 1000} as the space of edge budget for hyperparameter tuning. We choose the setting that involves minimal edge modifications while leading to maximum improvement in the model's test accuracy, maximum improvement in the graph homophily level, and maximum reduction the memorization rate. We before and after rewiring
plot the average memorization rate of candidate nodes of syn-cora-ho the graph for additions, both additions and deletions and deletions in Figure T5] We can observe that edge deletions has the most minimal impact reducing memorization. We report the actual values for all the datasets in Table [4
Table 15 and Table [6]
Edge Additions. In Table 14 we present the results for memorization reduction when edges are added to the graph. We can observe, for instance, on syn-cora-ho 0, by adding edges, we improve the test accuracy by 8.85% and reduce the memorization rate on candidate nodes by 5.11%.
33

---

Table 10: Label disagreement score for memorized vs non-memorized nodes in the Se for remaining real-world datasets trained on GCN and averaged over 3 random seeds.
MemNodes
Non-MemNodee
p-value
Effect Size
Dataset
LDS
L.S
(< 0.01)
Pubmed
0.33+0.00
0.29=0.00
0.00
Inf
Cornell
0.50#0.01
0.34+0.003
0.006441
8.7681
Texas
0.73#0.0221
0,45+0.0254
0.010398
6,8804
Wisconsin
0.51+0.00
0.25#0.00
0.00
Inf
Actor
0.78#0.0032
0.76#0.0011
0.0102599
6.9275
Table 11: Label disagreement score for memorized vs non-memorized nodes in the Se for 9 real- world datasets trained on GraphSAGE and averaged over random seeds.
MemNodes LDS
Non-MemNodes
p-value
Effect Size
Dataset
LDS
(< 0.01)
Cora
0.7697+0.0288
2.6179+0.0044
0.017565
5.26
Citeseer
0.7850=0.0122
0.5863+00.00%
0.002069
15.52
Pubmed
0.6312#0.0166
0,2877=0.000
0.000802
24.95
Cornell
0.80+0.0740
0.34#0.015
0.009608
7.16
Texas
0.9048+0.00
0.3667#0.00
0.0
Wisconsin
0.8467#0.0323
0.3520#0.0333
0.001785
16.71
Chameleon
0.7985#0.0022
0.7588+10.000
0.003820
11.40
Squirrel
0.8390#0.0011
0.7814
0.001727
16.99
Actor
0.7911#0.0054
0.774740.0021
0.073673
2.45
Edge Deletions In Table 15
we present the results for memorization reduction by deleting edges in the graph. We can observe that although we show memorization reduction in all the datasets except on dataset syn-cora-hO..
By deleting edges, the memorization rate on syn-cora-ho increases by 2.55% while test accuracy reduces by 0.87%. This counter-result highlights the nuances of trying to mitigate memorization by graph rewiring. is possible that there exists a different edge budget that could still improve the metries this dataset, which only be found by tuning large number of edge budgets and then measuring the memorization rate, which quickly becomes computationally expensive.
Simultaneous Additions-Delettonns ensure we don't 't skew the edge distribution of the graph by adding deleting edges, we also perform experiment where we simultaneously add and delete edges to ensure the rewired graph doesn't deviate much from original graph statistics. The results are presented in Table T6 We can observe that after simultaneously adding and deleting edges, the graph homophily level increases for all syn-cora graphs, leading to an decrease in the memorization score and memorization rate. At the same time, there is improvement in the test accuracy of the models. For instance, on syn-cora-ho O, by adding and deleting 1000 edges, we improve the test accuracy by 7.87% and reduce the memorization rate on candidate nodes by 6.01%.
G.1 Graph Rewiring vs. Label Smoothing for Mitigating Memorization
An alternative approach mitigate memorization is to add regularization technique such as label smoothing which discourages overconfidence by training on soft probability distributions instead of hard one-hot labels. We compare label smoothing with e 0.1 and graph rewiring in Table on syn-cora datasets. Evidently, graph rewiring not only reduces memorization but also improves downstream performance, contrary using label smoothing which has an inherent side-effect of also reducing the test accuracy along with the memorization rate. In the third column of Table [7] we combine both label smoothing and graph rewiring, to highlight that these methods are not mutually exclusive and can be combined, working both at the data level and the model level, to reduce memorization. Our results indicate that graph rewiring is by far the simplest and best strategy to reduce memorization without affecting the downstream performance.
34

---

Table 12: Label disagreement score for memorized vs non-memorized nodes in the Se for real- world datasets trained on GATv2 and averaged over 3 random seeds.
MemNodes
Non-MemNodes
p-value 0.01)
Effect Size
Dataset
LDS
LDS
Cora
0.7717#0.0102
0.6498+0. 0009
0.003147
12.57
Citeseer
0.7276#0.0149
0.5723+0.005
0.006398
8.79
Pubmed
0.4333=0.0815
0.2873+0.00
0.103304
2.02
Cornell
0.5534#0.0177
0.3967
0.017247
5.31
Texas
0.6343#0.0122
0.3999#0.01255
0.003702
11.58
Wisconsin
0.4574
0.3784+0.0622
0.409718
0.73
Chameleon
0.8868+0.0126
0.5934 00008
0.001779
16.74
Squirrel
0.8215+0.0099
0.7849#0.011 01011
0.094732
2.13
Actor
0.7920=0.0037
0.7715+0.0011
0.021174
4.78
8
Nemombation 1561
Mamotiiatoo boatbon Hetee 1961
Namorizatio Haze 1961
15
20
(a) Adding edges
(b) Adding deleting edges
Deleting edges
Figure 15: Memorization rate of candidate nodes in syn-cora-hO. O, before and after edge modification.
H Experimental setup and hyperparameters
H.1 Graph Generation Process for syn-cora.
We use the syn-cora dataset introduced in 688 to derive all our insights on memorization, as this benchmark provides the perfect setup to vary the graph homophily level and study its effects on the rate of memorization. The graph generation process follows similar the methods outlined in 33 I The process involves starting with an initial graph and adding new nodes. We can connect new node u E class to an existing node v E class based on some probability Puv- ensure the graphs generated follow power law and the level of heterophily is controllable, dependency on class compatibility matrix H;j E H between class and j. and the degree d, of the existing node are introduced. The node features from real-world graphs, such as Cora [41], are sampled and assigned to the synthetically generated graphs. We use graphs with homophily levels
setup [ and
{0.0,.... 1.0), where a score of = 0.0 denotes a highly heterophilic graph and homophily score h 1.0 indicates a highly homophilic graph. We refer the readers to [68] for more details on how the compatibility matrix is defined and the graphs are generated. In our experiments, do not generate the graphs ourselves.
H.2 Hyperparameters
We use PyTorch Geometric for of our experiments. The hyperparameters used training our models, the dataset statistics such as the number of nodes and edges, the homophily and label informativeness measures [49] are reported in Table T8 All of our experiments were done on T4 GPU highlighting the computationally efficiency of our proposed framework.
35

---

Table 13: TPR at 1% FPR for MIA on GNNs trained on the original and rewired syn-cora.
TPR@ I%FPR
@PR@ 1%FPR
Dalaset
(Original)
(Rewired)
syn-cors caa--crrahh...o .00
0.0992
0.0090
8yn-cora-ho.c0 30
0.0455
0.0090
ayn-cora-h..8
0.0370
0.0135
syn eyn-cora-ho.77
0.0380
0.0180
eyn-cora-h1.00 0.0194
0.0195
Table 14: Memorization score (MemScore), Memorization rate (MR), Test accuracy and Homophily level for syn-cora dataset averaged over random seeds, trained on GCN, before and after adding
edges to the graph.
Dataset
MemSoore
Refore
Avg
Befrre
MR
Iest Accuracy
Refore
Homophily Before
MemScore
After
After
MR
(S8
Test Accuracy After
Homophily After
Added
Edges
syn-cora-ho- 0
0. 0T666
85.6321.82
14,64:1 :24
0,00
0.656336 0008
78.3540.52
23 S0E1.70
0,0159
1000
оye cora
0.522640.000 0009
0.3659
ayn-cora-ho. 5
0.4064000022 26
45,95=1.62
63.28+4.31
0.5115
0.399240.0029
43,24+0.45
70.2764.49
0.5477
1000
syn-cora-ho.7
0,2616+000070
25.98+1.45
77.27+2.86
0.6927
0.2457+0-0055
25,25+0.00
79.1360.47
0,7020
500
syn-cora-h1.0
0.0021400005
0.0018H0.0005
100
H.3 Empirical runtimes
We present the empirical runtimes averaged over 3 random seeds in seconds for training models f. and calculating the memorization score for candidate nodes Sc Table 19 Table 20 and Table 21 where the backbone GNN models are GCN, GraphSAGE and GATv2 respectively. We can observe that our proposed label memorization framework NCMemo consistently computationally friendly across datasets and different GNN models. We also report the runtime for calculating the label disagreement score the same tables. We can see that our proposed framework for calculating label disagreement score is computationally friendly for almost all the datasets and can be expensive for very large graphs.
36

---

Table 15: Memorization score (MemScore), Memorization rate (MR), Test accuracy and Homophily level for myn-com cora dataset averaged over 3 random seeds, trained GCN, before and after deleting edges to the graph.
Ditaset
MemScore
Before
Avg
Before
MIR
(%)
Test Accuracy
Before
Homophily Before
MemScore
After
Arg
After
MR
(56
Accuracy After
Test
Homophily Afler
Deleted
Edges
aya-cora-ho.
13.63=182
0.629446.0113
14.420034
cya-cora-bo 30.3
0.5573L0 0047
63.96a1.19
33.33a0.90 94
0,3002
0.569810.0002
63.51a1.19
34, 14.4322115
0.3079
500
ayn-tora-ho
6.1166-0.0126
45.95=140 122
63.288e4.3 51
0.5115
0.4413+0.0022
48 S05 0.26
62. 62.40=1.77 700
0.5117
100
aya-tora-h0.7
0.2616=0.0070
13.981144
77.27=2.86
0.6927
( 0.3492+0.0004
25.08+0.52
76.39=4.95
0.6945
100
aya-cora-b1.0
0.0021=0.0005
0.00
0.002300.0005
0.00
1.0
100
Table 16: Memorization score (MemScore), Memorization rate (MR), Test accuracy and Homophily level for syn-cora dataset averaged over 3 random seeds, trained on GCN, before and after simulta- neous edge additions and deletions.
Dataset
MemScore
Avg
MR
(56
Test Accumey
Homophily Before
Avg MemScore
MR
(5)
Test Accuracy
Horsophily Afler
Edges Medified
Before
Before
eyn-cora-ho.
0.7091
8363g182
1.6441124
0.00
0.680
27 7763331.4
22.3120.47
0.0159
1000
syn-core-bae seeehh..3 3
0.557320.0017
63 63.1.11199
33.3310.91
0,3002
0.521020.0143
58. 78..61
37. 37.1612.05
0.3501
500
eyn-cora-bo.
04106=000126
45 45.95e1662
63.2844.31
0.5115
0.3871
39.79+1 45
65,79=1.88
0.5665
1000
syn-cora-bo.
0261650.0070
25.9811.45
77.2742.66
0.6927
0.241320.0058
24.3241
78.9122.49
0.7114
syn-cora-h1.0
000000
0.00
100
1.0
0.002240.000
0.00
100
1.0
100
Table 17: Memorization score (MemScore), Memorization rate (MR) for candidate nodes on syn- cora, averaged over 3 random seeds, trained on GCN, with Graph Rewiring, Label Smoothing.
and Graph Rewiring Label Smoothing.
Graph Rewiring
Label Smoothing
Graph Rewining Label Smoothing
Datasets
MemScore
Aug
(%6
Accurcc
MemScore
(%6
Accuracy
MemScore
Avg
(S8)
Accuracy
con-cora-bb..
78 530032
2130011.0
73652.70
15.30:08
71.300.9
161770030
ayn-cora-hal
0.522640.00099
59.6141.3
38,60+1.44
0.4336400000 0000
56.240.00
30.71+0.68
D.466540.0229
$2.94366
33.01-2.18
0.399240.0029
70.27+4.49
0:00
39.241.20
54.54+0.88
0.3640H0.0167
39.0+3.2
57.81+1.00
ayn-cora-bo.1
0.245700.0036
25 23:0000000
79.13at):47
D 2057
24.5e0.9
73.77:0.33
0.250610.0158
200:2.9
73.77:0.57
ayn-cora-h1.0
0000
0.00
100
0.026500.0066
0
100
0.02220000027
0
100
Table 18: Hyperparameters and dataset statistics.
Hidden Dimension
#
Homophily
Node Label
Dataset
LR
#Layers
[V]
[E]
Classes
Level
Informativeness
Cora
32
0.01
3
2708
101388
7
0.7637
0.5763
Citeseer
0.01
0.6620
0.4653
Pubmed
32
0.01
19717
88648
3
0.6860
0.4223
Cornell
128
0,001
183
298
-0.2029
0.1574
Texas
128
0.001
183
325
5
-0,2260
0.0186
Wisconsin
128
0.001
251
515
5
.0.1323
0.0874
Chameleon
128
0.001
2277
36101
0.0339
0,0516
Squirrel
128
0.001
3
5201
217073
5
0.0074
0.0277
Actor
0.001
7600
30019
0.0062
0.0018
syn-cora
32
0.01
3
1490
2965 in 2968
5
0.0 1.0
0.0 to 1.0
Table 19: Empirical runtime for training GCN models f.g and calculating the memorization scores for Sc and calculating the LD score averaged over random seeds with 95% CI (confidence interval).
MemorizationScore
LDS
Dataset
Runtime
Runtime (in seconds)
(in seconds)
Cora
2.16+0.52
1.
Citeseer
1.93+0.15
10.52+0.28
Pubmed
2.8640.15
41.63+0.72
Cornell
2.113
3.06+0.51
Texas
1,83+0.16
3.88+0.41
Wisconsin
2.00+0.44
3.50+0.07
Chamelcon
2.3640.17
8,27+0.45
Squirrel
6.23+0.21
24.49+0.11
Actor
2.92+0.20
25.1441.28
37

---

Table 20: Empirical runtimes for training GraphSAGE models f.g and calculating the memorization scores for Sc and calculating the LD score averaged over 3 random seeds with 95% CI (confidence interval).
MemorizationScore
LDS
Dataset
Runtime (in seconds)
Runtime (in seconds)
Cora
1.70+0.19
7.24+0.45
Citeseer
2.55#0.15
10.27+0.26
Pubmed
4.30+0.23
69.71+0.30
Cornell
1.40+0.24
3.0420.26
Texas
1.55+0.40
3.74+0.34
Wisconsin
1.39+0.15
3.10:0.56
Chameleon
5.2940.16
8.35+0.46
Squirrel
24.51#0.13
25.56+0.16
Actor
3.83+0.23
24.25+0.53
Table 21: Empirical runtimes for training GAT models f. and calculating the memorization scores for Sc and calculating the LD score averaged over random seeds with 95% CI (confidence interval).
MemorizationScore
LDS
Dataset
Runtime (in seconds)
Runtime seconds)
Cora
3.2440.26
8.38+0.45
Citeseer
3.52+0.18
10.60+0.27
Pubmed
11.97=0.17
70.26+0.81
Coreell
2.99+0.25
3.17+0.35
Texas
3.23+0.30
3.55# .03
Wisconsin
2.96+0.18
3.22+0.45
Chameleon
13.75+0.16
8.18+0.36
Squirrel
64.81+0.48
26.60+0.27
Actor
17.47+0.21
25.57+0.25
38


Reviews:
[{"review_id": "TVYcKncaAC", "reviewer": "Reviewer_FwDg", "summary": "The authors present a framework for quantifying label memorization in graph neural networks trained on semi-supervised node-classification tasks. They show that GNNs depend on memorization when operating on graphs with low homophily (i.e. graphs whose connected nodes do not share similar features). They show that high memorization leads to poor generalization via a kernel-target alignment metric. Finally, they reveal that the reason for increased memorization/poor performance for low homophily graphs is due to the tendency of GNN models to use structural information so in low homophily regimes,the lack of information from graph structure leads to more label memorization.", "questions": "### Questions\n- Is it possible to show experimentally how memorization leads to poor generalization (as suggested by Prop. 2)?\n- NCMemo is specifically for semi-supervised node classification but can the authors say a few words on if this framework can also be extended to graph classification tasks? In that case, is it possible to analyze the intermediary embeddings from each GNN layer to draw conclusions regarding how GNNs memorize information for classification tasks?", "limitations": "yes", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 4, "strengths_and_weaknesses": "### Strengths\n\n(1) *Significance*: This seems to be the first work on memorization in graph neural networks. Provides a good framework/metric for understanding how and when graph neural networks memorize node features and has potential implications for understanding GNN performance out of distribution (more memorization possibly leads to bad OOd generalization). \n(2) *Extensive evaluation*: First, the authors do extensive experiments on both synthetic and real-world datasets. These experiments help clearly explain the link between graph homophily and memorization. They show a clear relationship between homophily and their metric which measures the rate of memorization for GNNs. In their appendix, they also include extensive evaluation with GAT and GraphSAGE (two commonly used graph architectures). I also appreciated the section analyzing privacy risks and the real-world impact of memorization. \n\nIn general, this is a strong paper which I think will have significant impact especially since it seems to be the first work on memorization in GNNs. The authors provide a convincing argument for studying GNN memorization from studying theoretically *when* we see memorization occurs to experimentally demonstrating the problems that arise from meorization at NN deployment time. \n\n### Weaknesses\n\n(1) Their framework only works in the node-classification regime (which is still important). I wonder if the authors could say a few words on how we should keep track of/understand memorization when considering graph level classification tasks. \n(2) Proposition 2 suggests that GNNs suffer from poor generalization when there is high memorization. This part seems relevant esp. given the increased attention to out-of-distribution generalization in several previous works so I wonder if the authors can elaborate more on this point and show this property experimentally?", "was_revised": true, "final_justification": "I repeat the comment that I made here: \n\nI have read the rebuttal to my comment as well as the other reviews and rebuttals. They have addressed all of my questions. This paper is the first to systemically study memorization in graph neural networks and the authors have presented strong empirical evidence both for when GNNs will memorize information (low homophily regimes) as well as how memorization will affect the performance on the GNN. While their NCMemo framework probably could be improved further, I think the aforementioned findings in the current manuscript will already significant enough to for me to strongly recommend acceptance to NeurIPS. The framework itself is also general enough to be applied to many different graph learning techniques and I think it is fair to mainly consider standard message-passing GNNs (GCN, GAT, GraphSAGE) as they are still widely used in practice. I agree with other reviewers that graph transformers have become much more popular lately and I appreciate the additional experiments that the authors have carried out for graph transformers. Additionally, I do not think the authors should be faulted for lack of theory or proof. I think it is equally as significant to do many careful and thoughtful experiments to examine some phenomena (which has not been previously explored) and use such empirical investigations to understand when/where to use GNNs and how they might fail in harmful ways (their final section on privacy risks).\n\nAll this to say: I maintain my score.", "rebuttal": "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.\n\n>**The framework targets the node-classification regime. How about graph-level classification?**\n\nWe 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. \n\nWe 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:\n\n\n|Dataset|AvgMemScore|MR(%)|\n|---|---|---|\n|MUTAG|0.0011±0.0045|0|\n|AIDS|0.0767±0.0260|0|\n|BZR|-0.0096±0.0067|0|\n|COX2|0.0068±0.0241|0|\n\nThese 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].\n\nTo 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.\n\n`GCN+MUTAG:`\n\n|NoiseLevel|AvgMemScore|MR(%)|\n|---|---|---|\n|0.0|0.0011±0.0045|0|\n|0.1|0.0862±0.0244|2.2±1.9|\n|0.3|0.2352±0.0744|18.3±9.9|\n|0.5|0.3419±0.0420|33.3±3.7|\n|0.7|0.3680±0.0239|39.8±4.9|\n|0.9|0.4544±0.0302|46.2±6.7|\n\n`GCN+AIDS:`\n\n|NoiseLevel|AvgMemScore|MR(%)|\n|---|---|---|\n|0.0|0.0066±0.0285|0|\n|0.1|0.0767±0.0260|0|\n|0.3|0.1351±0.0298|6.5±3.2|\n|0.5|0.2086±0.0295|13.7±1.2|\n|0.7|0.2465±0.0087|18.8±1.4|\n|0.9|0.2367±0.0346|17.6±2.2|\n\n`GCN+BZR:`\n\n|NoiseLevel|AvgMemScore|MR(%)|\n|---|---|---|\n|0.0|-0.0096±0.0067|0|\n|0.1|0.1993±0.0137|9.2±3.1|\n|0.3|0.2965±0.0064|27.7±0.0|\n|0.5|0.2091±0.0109|15.9±0.9|\n|0.7|0.1790±0.0010|18.5±0.0|\n|0.9|0.1998±0.0006|20.0±0.0|\n\n`GCN+COX2:`\n\n|NoiseLevel|AvgMemScore|MR(%)|\n|---|---|---|\n|0.0|0.0068±0.0241|0|\n|0.1|0.1939±0.0116|2.6±1.3|\n|0.3|0.2326±0.0145|21.5±1.5|\n|0.5|0.2856±0.0012|28.9±0.0|\n|0.7|0.2237±0.0101|23.7±0.0|\n|0.9|0.1838±0.0092|18.4±0.0|\n\nWhile 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.\n\n >**Showing Proposition 2 experimentally (memorization leads to poor generalization)**\n\nOur paper provides direct experimental evidence for Proposition 2, showing that higher memorization is linked to poorer generalization. This is demonstrated through two key metrics:\n\n1. 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.*\n\n2. 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.\n\n`Generalization Performance of Real-world Datasets:`\n\n|Datasets|Test Accuracy of Model f|AvgMemScore|MR(%)|\n|---|---|---|---|\n|Cora|85.24±0.51|0.1033±0.0006|9.7±0.1|\n|Citeseer|77.52±1.63|0.2661±0.0048|28.4±0.8|\n|Chameleon|33.92±0.80|0.5285±0.0053|52.9±0.3|\n|Squirrel|26.79±0.76|0.5050±0.0133|53.6±1.3|\n\n\n\n\n**References:**\n\n[A] TUDataset: A collection of benchmark datasets for learning with graphs. Morris et al, GRL+ Workshop, ICML 2020."}, {"review_id": "ab0I1wqDMN", "reviewer": "Reviewer_uuwn", "summary": "This paper proposes NCMemo, a framework to measure how much GNNs memorize training labels in node classification tasks. This paper finds that memorization increases as graph homophily decreases. The authors show that this happens because GNNs rely more on memorizing labels when the graph structure provides less useful information. They also propose a Label Disagreement Score (LDS) to identify which nodes are more likely to be memorized. Finally, they show that graph rewiring can reduce memorization and its associated privacy risks without hurting model performance.", "questions": "Please see weaknesses", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- This paper focuses on memorization in GNNs. This helps fill an important gap in understanding generalization and privacy risks in graph learning.\n- This paper proposes a new framework to quantify per-node memorization, inspired by the leave-one-out memorization framework.\n- This paper provides insightful results on the relationship between homophily, memorization, and label inconsistency, based on both synthetic and real-world datasets.\n- This paper includes graph rewiring to mitigate memorization and privacy risks.\n\nWeaknesses:\n- This paper highlights the difficulty in conceptualizing and defining per-sample memorization, but the proposed NCMemo framework seems not including graph-specific techniques to tackle the interactions of graph elements.\n- The framework relies on training paired models with/without each node (or partition approximations), which may be computationally expensive. The scalability of NCMemo on large-scale graphs in the real world can be limited.\n- More datasets and advanced GNN backbones can be included in the experiments such as open graph benchmarks and graph transformers.", "was_revised": true, "final_justification": "My major concerns are addressed by the authors. The technical part directly follows the leave-one-out memorization framework, which is standard. While, I appreciate the novel insights of GNN memorization from their empirical studies. Hence, I tend to accept the paper.", "rebuttal": "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.\n\n>**The proposed NCMemo framework seems not including graph-specific techniques to tackle the interactions of graph elements.**\n\nOur 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:\n\ni. 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.\n\nii. 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.\n\niii. 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.\n \niv. Our initial strategy to mitigate memorization leverages graph rewiring, that directly involves manipulating the edges of the graph based on feature similarity. \n\nAll of these elements *directly use graph-specific elements and provide novel insights into graph-specific memorization*.\n\n>**Necessity of model pairs for assessing memorization and overhead**\n\nThe 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.\n\n>**More datasets and GNN backbones, e.g., open graph benchmarks and graph transformers**\n\nWe 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.\n\n`Large Datasets:`\n\n|Datasets|AvgMemScore|MemRate(%)|Nodes|Edges|Homophily|Runtime(seconds)|\n|---|---|---|---|---|---|---|\n|Photo|0.0093±0.0084|0.1±0.0|7,650|238,162|0.7850|3.97±0.24|\n|Physics|0.0156±0.0018|0.4±0.1|34,493|495,924|0.8724|17.82±0.24|\n|Computer|0.0005±0.0234|0.6±0.9|13,752|491,722|0.6823|6.26±0.19|\n|ogb-arxiv|0.0031±0.0051|0.4±0.3|169,343|1,166,243|>0.5|491.01±1.55|\n\nWe 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.\n\n`Graph Transformer:`\n\n|Datasets|AvgMemScore|MR(%)|Runtime|\n|---|---|---|---|\n|Cora|0.1359±0.0072|13.4±0.7|1355.43±3.76|\n|Citeseer|0.2486±0.0070|24.9±0.20|1158.74±7.11|\n|Chameleon|0.2807±0.0150|27.3±1.3|1222.66±1.49|\n|Squirrel|0.4810±0.0094|47.7±1.2|4748.68±41.52|\n\n\n**References:**\n\n[A] A critical look at the evaluation of GNNs under heterophily: Are we really making progress? Platonov et al. ICLR 2023."}, {"review_id": "KZCm6lc3S5", "reviewer": "Reviewer_UeH1", "summary": "This paper presents the NCMemo, a framework to quantify label memorization in GNNs for semi-supervised node classification. Firstly,  author states the role of memorization in improving the performance of DNNs, and verifies the four proposed propositions on GNNs through many experimental results: (1) Higher graph homophily leads to lower memorization rates; (2) in low-homogeneity graphs, the optimization dynamics of GNNs show an over-reliance on the graph structure, leading to increased memorization rate; (3) better alignment between the kernel and the target or graph structure reduces memorization; (4) nodes with high label inconsistency in their feature space neighborhood are more prone to memorization.", "questions": "1.  The authors pointed out that due to the non-IID properties in graphs, analyzing the model’s ability to memorize individual nodes is challenging, as it requires modeling a complex interplay of factors. So, is it appropriate to define the GNN's memorization based on a single node (i.e., leave-one-out)?\n\n2. In addition, I suggest adding research about the 2-hop topology on graphs, which is also important for the message passing mechanism of GNNs.\n\n3. Would it be better to fit the results reflected in Fig. 5 and 7 using a quadratic polynomial?\n\n4. Others please refer to the Weaknesses part.", "limitations": "Yes", "rating": 2, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\n1. The paper migrates the concept of memorization from DNN to the GNN field and put forward some interesting propositions and discoveries, which fill the gap that similar studies on data memorization in GNNs are lacking. \n\n2. The experiments in the paper are sufficient, and satisfactory experimental results have been obtained on both synthetic datasets and real-world datasets.\n\nWeaknesses:\n\n1. Some descriptions in the paper are not clear, such as the method to divide the training set into three disjoint partitions and Eqn. (1).\n\n2. Lack of solid theoretical proof and derivation.\n\n3. The position of Fig. 3 is not suitable.\n\n4. The paper directly borrows a lot of methods and ideas from other papers, resulting in low innovation of this paper.", "was_revised": true, "final_justification": "After reading the paper again, I think this paper has major flaws, which are explained in my response to the authors' rebuttal. Thus, I have decided to decrease the score.", "rebuttal": "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.\n\n>**Describing the method on data partitioning**\n\nWe 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.\n\n>**Describing Equation (1)**\n\nEquation (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\n\n>**Lack of proofs**\n\nWe 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.\n\n`Proof sketch:`\nWe delineate two regimes of learning:\n\n1. **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 \n\n$\\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)\n\n2. **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. \n\nFeldman's Lemma 4.3 states \n$\\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)$. \n\nBy 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.\n\n>**Relying on methods from other papers and low innovativeness**\n\nWe 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.\n\nSpecifically: \n1. 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; \n2. 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; \n3. 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; \n4. We empirically analyze the link between GNN memorization and privacy risks, highlighting the real-world impact of memorization on GNNs;\n5. 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:\n\ni. Extended our framework to the graph classification setting on 4 datasets and showed promising connections to node feature noise and memorization rate.\n\nii. Additional experiments on Graph Transformers and large datasets such as ogbn-arxiv.\n\nIn 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.\n\n>**Is it appropriate to define the GNN's memorization based on a single node (i.e., leave-one-out)?**\n\nIt 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.\n\n>**I suggest adding research about the 2-hop topology on graphs**\n\nWe 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.\n\n`SGConv:`\n|Datasets|AvgMemScore|MR(%)|\n|---|---|---|\n|Cora|0.0482±0.0165|3.8±0.4|\n|Citeseer|0.1124±0.0213|9.7±2.8|\n|Chameleon|0.3852±0.0111|37.3±0.8|\n|Squirrel|0.3745±0.0141|34.5±3.2|\n\nThe 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.\n\n>**Would it be better to fit the results reflected in Fig. 5 and 7 using a quadratic polynomial?**\n\nWe 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.\n\n\n**References:**\n\n[A] Simplifying Graph Convolutional Networks. Wu et al. ICML 2019."}, {"review_id": "6OWSHYQl1C", "reviewer": "Reviewer_RAPS", "summary": "The paper introduces NCMemo, a novel framework for measuring per-node label memorization in semi-supervised graph-node classification. This work provides a deep investigation into why and how GNNs memorize, links memorization to graph properties such as homophily, and proposes a practical method for mitigating resulting privacy vulnerabilities through graph rewiring.", "questions": "Q1. 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.", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "**Strengths**\n\n- The paper presents interesting insights by extending leave-one-out memorization analysis to the graph domain, and it is the first to attribute memorization to individual nodes.\n- This work builds on insightful training dynamics analysis, incorporating NTK alignment curves to convincingly link increased memorization to the model’s structural bias in cases where kernel-target alignment is poor.\n- The experimental results span three GNN backbones, multiple random seeds, statistical significance testing, and ablation studies (edge addition, deletion, and their combination), lending robustness to the conclusions.\n\n**Weaknesses**\n\n- Rewiring is not compared against other defenses (e.g., label smoothing), and its impact on downstream tasks that rely on the original edge topology is not evaluated.\n- The memorization indicator uses a fixed threshold of τ = 0.5 (line 122) without analysis, which may make the conclusions threshold-dependent.", "was_revised": true, "final_justification": "My question is basically addressed. I believe this paper provides interesting insights into the fundamental properties of GNN models.", "rebuttal": "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.\n\n>**Comparing rewiring against other defenses, e.g. label smoothing**\n\nFollowing the Reviewer’s suggestion, we include additional baselines. Eventually, we experiment with three approaches:\n\n1. **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.\n2. **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. \n3. **Rewiring+ Label smoothing**: To analyze their interaction, we combined both methods. \n\n`Graph Rewiring:`\n\n|Datasets|AvgMemScore|MR(%)|TestAccuracy|\n|---|---|---|---|\n|syn-cora-h0.0|0.6563±0.0081|78.53±0.52|23.50±1.70|\n|syn-cora-h0.3|0.5226±0.0049|59.61±1.13|38.69±1.41|\n|syn-cora-h0.5|0.3992±0.0029|43.24±0.45|70.27±4.49|\n|syn-cora-h0.7|0.2457±0.0036|25.23±0.00|79.13±0.47|\n|syn-cora-h1.0|0.0018±0.0005|0.00|100|\n\n`Label Smoothing:`\n\n|Datasets|AvgMemScore|MR(%)|TestAccuracy|\n|---|---|---|---|\n|syn-cora-h0.0|0.6000±0.0000|73.6±2.70|15.30±0.83|\n|syn-cora-h0.3|0.4836±0.0000|56.2±0.90|30.71±0.68|\n|syn-cora-h0.5|0.3728±0.0100|39.2±1.20|54.54±0.68|\n|syn-cora-h0.7|0.2667±0.0057|24.5±0.9|73.77±0.33|\n|syn-cora-h1.0|0.0265±0.0016|0|100|\n\n`Rewiring+Label Smoothing:`\n\n|Datasets|AvgMemScore|MR(%)|TestAccuracy|\n|---|---|---|---|\n|syn-cora-h0.0|0.6050±0.0130|71.3±0.9|16.17±0.50|\n|syn-cora-h0.3|0.4665±0.0239|52.9±3.6|33.01±2.18|\n|syn-cora-h0.5|0.3640±0.0167|39.0±3.2|57.81±1.00|\n|syn-cora-h0.7|0.2506±0.0158|20.0±2.9|73.77±0.57|\n|syn-cora-h1.0|0.0282±0.0027|0|100|\n\nOur 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. \n\nFinally, 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.\n\n`syn-cora-h0.0:`\n\n| $\\epsilon$ | AvgMem Score     | MR (%)         | Test Accuracy   |\n|------------|------------------|----------------|-----------------|\n| 0.0        | 0.6986 ± 0.01     | 82.4 ± 1.4     | 14.86 ± 1.37    |\n| 0.1        | 0.6000 ± 0.00     | 73.6 ± 2.70    | 15.30 ± 0.85    |\n| 0.3        | 0.4348 ± 0.0028   | 37.7 ± 1.4     | 15.19 ± 0.68    |\n| 0.5        | 0.2877 ± 0.0148   | 4.4 ± 3.2      | 14.75 ± 0.66    |\n| 0.7        | 0.1523 ± 0.0015   | 0              | 14.32 ± 0.38    |\n| 0.9        | 0.0188 ± 0.0036   | 0              | 18.80 ± 2.98    |\n\n>**Evaluating rewiring’s impact on downstream tasks that rely on original topology**\n\nTo 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.\n\n`Comparing test accuracy before and after rewiring:`\n|Datasets|TestAccBefore|TestAccAfter (Adding edges)|TestAccAfter (Deleting edges)|TestAccAfter (Add+Del)|\n|---|---|---|---|---|\n|Cora|85.24±0.51|87.33±0.30|87.32±0.31|86.90±0.30|\n|Citeseer|77.52±1.63|78.07±0.40|79.01±0.38|78.57±0.36|\n|Chameleon|33.92±0.80|40.48±0.68|39.58±0.65|40.07±0.69|\n|Squirrel|26.79±0.76|34.64±0.36|34.07±0.43|33.56±0.43|\n\nIn 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.\n\n>**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.**\n\nGraph 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.\n\nAs 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.\n\nWe 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.\n\n>**Memorization indicator uses a fixed threshold of $\\tau = 0.5$**\n\nWe 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). \n\nTo 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.\n\n\n`Synthetic Datasets:`\n\n||**$\\tau > 0.4$**||**$\\tau > 0.6$**||**$\\tau > 0.8$**||**$\\tau > 0.9$**||\n|---|---|---|---|---|---|---|---|---|\n|Datasets|AvgMemScore|MR(%)|AvgMemScore|MR(%)|AvgMemScore|MR(%)|AvgMemScore|MR(%)|\n|syn-cora-h0.0|0.7087±0.0069|90.09±0.45|0.6798±0.0221|70.72±5.19|0.7292±0.0171|53.30±1.45|0.7239±0.0356|23.87±5.08|\n|syn-cora-h0.3|0.5900±0.0134|70.87±0.26|0.5830±0.0197|60.96±2.48|0.6438±0.0093|48.95±2.27|0.5530±0.0270|22.82±1.82|\n|syn-cora-h0.5|0.4883±0.0098|54.35±0.26|0.5012±0.0138|52.25±1.19|0.4379±0.0226|30.18±3.15|0.4766±0.0305|21.02±2.31|\n|syn-cora-h0.7|0.2295±0.0121|26.28±2.64|0.2174±0.0149|19.22±0.94|0.2393±0.0032|15.77±0.45|0.2103±0.0027|7.96±0.52|\n|syn-cora-h1.0|0.0025±0.0008|0|0.0024±0.0005|0|0.0023±0.0004|0|0.0029±0.0008|0|\n\n`Real-world graphs:`\n\n| |**$\\tau > 0.4$**||**$\\tau > 0.6$**||**$\\tau > 0.8$**||**$\\tau > 0.9$**||\n|---|---|---|---|---|---|---|---|---|\n|Datasets|AvgMemScore|MR(%)|AvgMemScore|MR(%)|AvgMemScore|MR(%)|AvgMemScore|MR(%)|\n|Cora|0.1340±0.0107|16.3±1.0|0.1128±0.0000|10.0±0.4|0.1311±0.0027|8.7±0.8|0.1004±0.0020|2.3±0.8|\n|Citeseer|0.2566±0.0118|30.0±1.8|0.2341±0.0055|23.0±2.3|0.2586±0.0100|18.0±4.0|0.2434±0.0114|12.4±2.0|\n|Chameleon|0.5297±0.0164|60.1±1.5|0.4898±0.0100|44.6±1.5|0.5391±0.0194|37.6±1.5|0.5549±0.0069|31.8±1.1|\n|Squirrel|0.4826±0.0275|57.0±2.7|0.4669±0.0100|37.9±3.1|0.4840±0.0187|22.6±2.5|0.4909±0.0258|11.5±1.0|\n\n\nAcross 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."}]

Author rebuttal:

Meta-review: This paper presents a framework for quantifying label memorization in GNNs trained on semi-supervised node-classification tasks. The authors adopt the classic and standard leave-one-out memorization framework and give interesting insights on the relationship between homophily, memorization, and label inconsistency, based on both synthetic and real-world datasets.

One strength of the work is that it pioneers the study of memorization in GNNs, and it provides a metric for understanding how and when graph neural networks memorize node features. 

The reviewers have a discussion on whether using the standard leave-one-out formula (Eq 1) is a good fit for graphs (particularly on node classification task). The issue arises because typically Eq 1 requires the i.i.d. assumption to quantify memorization, while the assumption does not hold in graphs in general. 

Even though the definition of memorization (Eq 1) may not be perfect, it represents an initial step toward understanding memorization in message-passing GNNs and has the potential to inspire follow-up works in this new field. Therefore, I am inclined to recommend acceptance of this paper, provided that the authors include in the final version a clear discussion on both the rationale and the limitations of using Eq. (1) to quantify memorization in GNNs.
Decision: Accept (poster)