Memorization in Graph Neural Networks

Adarsh Jamadandi, Jing Xu, Adam Dziedzic, Franziska Boenisch

Abstract

While memorization in standard Deep Neural Networks (DNNs) is well-documented, its manifestation in Graph Neural Networks (GNNs) remains poorly understood due to the inherent dependencies between nodes. This paper introduces NCMemo, a systematic framework to quantify node-level memorization. Our analysis reveals that GNNs are prone to memorizing individual nodes when graph structure is uninformative—a phenomenon characterized by an inverse relationship with graph homophily. We demonstrate that this memorization directly correlates with increased privacy risks, specifically Membership Inference Attacks (MIA), and propose graph rewiring as an effective mitigation strategy that simultaneously improves model generalization.

Introduction

In the context of deep learning, memorization occurs when a model learns specific training examples rather than generalizable patterns. While this behavior is a known "black box" in computer vision and natural language processing, GNNs present a unique challenge: nodes are not independent and identically distributed (i.i.d.). The interconnected nature of graph data makes it difficult to isolate whether a model is learning a general message-passing rule or simply "remembering" the labels of specific nodes.

This research addresses three critical questions: how to quantify GNN memorization, which graph properties trigger this behavior, and how memorization impacts real-world privacy. By introducing the NCMemo framework, the authors provide the first systematic look at the "behavioral gap" between training and inference in graph-based learning.

The NCMemo Framework

The authors introduce NCMemo (Node Classification Memorization), a framework inspired by the "leave-one-out" principle. To determine if a node $v$ is memorized, the framework compares the model's prediction confidence when $v$ is included in the training set versus when it is excluded. A significant discrepancy in confidence indicates that the model has memorized that specific node's label rather than applying a learned rule that generalizes to unseen data.

To analyze the mechanics behind this behavior, the study employs two primary tools:

  1. Neural Tangent Kernel (NTK) Analysis: This is used to track training dynamics, revealing how the model's internal similarity matrix aligns with the graph structure versus the target labels.
  2. Label Disagreement Score (LDS): A novel metric that identifies "atypical" nodes by measuring how much a node's label differs from its $k$-nearest neighbors in the feature space.

Drivers of Memorization: The Homophily Inverse Law

The most significant finding of the study is the Homophily Inverse Law. In highly homophilic graphs—where connected nodes share similar labels—GNNs generalize effectively, and memorization remains near zero. However, in heterophilic (or "noisy") graphs where neighbors have dissimilar labels, GNNs struggle to find consistent message-passing rules.

Through NTK analysis, the authors found that GNNs possess an implicit bias to utilize graph structure even when it is uninformative. When the structure provides a "noisy" signal that contradicts the labels, the GNN "gives up" on generalization and resorts to memorizing individual training labels to drive down the loss function. This behavior is particularly prevalent in nodes with high LDS; these "outliers" are the primary targets for memorization.

Experimental Results and Privacy Risks

The study evaluated NCMemo across a diverse range of datasets, including synthetic benchmarks (syn-cora) and real-world heterophilic graphs like Squirrel and Chameleon.

  • Memorization Rates: In heterophilic environments, memorization rates can exceed 50%, compared to nearly 0% in homophilic graphs like Cora or Pubmed.
  • Privacy Vulnerabilities: There is a direct, positive correlation between a node's NCMemo score and its vulnerability to Membership Inference Attacks (MIA). If a model memorizes a node, an attacker can determine with high accuracy whether that node was part of the private training set.
  • Mitigation via Rewiring: The authors proposed a graph rewiring strategy that modifies edges based on feature similarity (cosine similarity). This reduces structural noise and increases effective homophily. In tests, rewiring reduced the privacy risk (MIA AUC) by over 20% and, surprisingly, increased model accuracy (e.g., a +8.85% boost on syn-cora-h0.0) by forcing the model to rely on cleaner signals.

Conclusion

NCMemo reveals that GNN memorization is a structural byproduct of noisy, heterophilic data. While GNNs are "stubborn" in their reliance on graph topology, strategic rewiring can mitigate the resulting privacy leaks while simultaneously improving performance. Future work will look toward extending these insights to Graph Transformers and more complex, multi-relational graph tasks.

Summary updated

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.
BibTeX
@inproceedings{jamadandi2025memorization,
  author = {Adarsh Jamadandi and Jing Xu and Adam Dziedzic and Franziska Boenisch},
  title = {{Memorization in Graph Neural Networks}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2025},
  url = {https://openreview.net/forum?id=jAJv3CaS4f},
}
Figure