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:
- 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.
- 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
CoraorPubmed. - 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