Research map / Graph learning / GNN architectures

Memorization in Graph Neural Networks

NeurIPS 2025 · Graph learning › GNN architectures · approach: GNN generalization theory · 1 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Introduces NCMemo, a leave-one-out framework for measuring label memorization in semi-supervised GNN node classification, linking memorization to graph homophily, NTK kernel alignment, feature-space label disagreement, and privacy risk mitigated by graph rewiring.

Problem

Label memorization in GNNs for semi-supervised node classification is under-explored because nodes are not independent samples on a single graph; it is unclear how memorization depends on graph structure and homophily and how it relates to privacy risk.

Approach

Define per-node memorization as the gap in predicted correct-label probability between models trained with and without the node (approximated by splitting the training set into shared, candidate, and independent partitions), then relate memorization rate to homophily, NTK kernel alignment, and a feature-space Label Disagreement Score, and use feature-similarity graph rewiring as a mitigation.

Key results

• On syn-cora, memorization rate falls from 83.63% at homophily 0.0 to 0.00% at homophily 1.0 for candidate nodes with GCN.
• Correlation between memorization rate and final kernel-target alignment is r = -0.97 on syn-cora and r = -0.79 across 8 real-world datasets.
• Rewiring reduces LiRA attack AUC on syn-cora, with drops of more than 20% for the low-homophily graph (syn-cora-h0.0), while preserving performance.

Measured effects reported in the paper

Surprising findings

• Memorized nodes are not confined to low-homophily graphs; a small number are memorized even in high-homophily graphs, with the authors noting the cost of not fitting them is small.
• Graph classification with GCN shows essentially no memorization on MUTAG, AIDS, BZR and COX2 unless features are noised.

Limitations

• Graph rewiring strategy may be too simple to mitigate memorization on real-world graphs.
• Label Disagreement Score may be less effective on heterophilic datasets with non-uniform label/feature distributions such as Actor.
• Analysis of training dynamics is primarily for GCN; GATs and graph transformers are not analyzed.

Experimental setup

Datasets: Cora Citeseer Pubmed Cornell Texas Wisconsin Chameleon Squirrel Actor syn-cora MUTAG AIDS

Benchmarks: syn-cora Cora Citeseer Pubmed Cornell Texas Wisconsin Chameleon Squirrel Actor MUTAG AIDS

Metrics: memorization score memorization rate label disagreement score kernel-target alignment kernel-graph alignment LiRA AUC TPR at 1% FPR test accuracy

Baselines: GCN GraphSAGE GATv2

Builds on: leave-one-out memorization (Feldman & Zhang) neural tangent kernel kernel-graph alignment GNN analysis LiRA membership inference feature-similarity graph rewiring

Closest papers by meaning

• Small ReLU networks are powerful memorizers: a tight analysis of memorization capacity (NeurIPS 2019 · similarity 0.88)
• Combining Label Propagation and Simple Models out-performs Graph Neural Networks (ICLR 2021 · similarity 0.88)
• What Is Missing For Graph Homophily? Disentangling Graph Homophily For Graph Neural Networks (NeurIPS 2024 · similarity 0.87)
• Locality-Aware Graph Rewiring in GNNs (ICLR 2024 · similarity 0.86)
• On the Impact of Feature Heterophily on Link Prediction with Graph Neural Networks (NeurIPS 2024 · similarity 0.86)
• Label-free Node Classification on Graphs with Large Language Models (LLMs) (ICLR 2024 · similarity 0.86)