Pith. sign in

REVIEW 4 major objections 4 minor 77 references

Graph neural networks memorize node labels far more on low-homophily graphs, and feature-based rewiring cuts both memorization and privacy leakage.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

GNNs memorize node labels more on low-homophily graphs, a behavior NCMemo can quantify and graph rewiring can partially mitigate.

T0 review reviewed 2026-08-05 challenge →

load-bearing objection First systematic study of GNN memorization, but the batch estimator behind its headline homophily–memorization trend is confounded by task difficulty. the 4 major comments →

arxiv 2508.19352 v3 pith:2J4DAJ7C submitted 2025-08-26 cs.LG

Memorization in Graph Neural Networks

Adarsh Jamadandi , Jing Xu , Adam Dziedzic , Franziska Boenisch This is my paper
classification cs.LG
keywords memorizationgraph neural networkshomophilynode classificationmembership inferencegraph rewiringneural tangent kernellabel disagreement score
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper sets out to show that graph neural networks memorize node labels in semi-supervised node classification, and that how much they memorize is controlled by graph homophily—the extent to which connected nodes share labels and features. On synthetic graphs spanning homophily levels 0 to 1 and across nine real-world datasets with GCN, GraphSAGE, and GATv2 backbones, the authors report that memorization rate rises sharply as homophily falls, reaching 0% at maximum homophily. They trace this to the GNN's implicit bias to lean on graph structure during training even when that structure carries little label information, and identify individual at-risk nodes with a label-disagreement score. The practical payoff is that feature-similarity rewiring, which nudges homophily upward, reduces memorization and the associated membership-inference privacy risk while keeping accuracy intact.

Core claim

NCMemo measures per-node label memorization as the expected increase in a node's predicted label probability when the node is present in training versus absent, approximated by comparing two models trained on non-overlapping candidate batches. Using this measure, the paper claims an inverse relationship: as homophily rises from 0 to 1, memorization rate falls, reaching 0% at maximum homophily on the synthetic graphs; on real datasets, heterophilic graphs show memorization rates around 38–54%, against 8–28% for homophilic ones. The offered mechanism is that GNN optimization pushes the Neural Tangent Kernel to align with the adjacency matrix regardless of whether structure helps, and in low-ho

What carries the argument

The load-bearing measure is NCMemo's memorization score: for a node, the expected probability the model assigns to its true label when the node is in training minus that probability when the node is left out, approximated by comparing a model trained on shared plus candidate nodes with one trained on shared plus independent nodes. The explanatory mechanism is the GNN's implicit structural bias, read through the Neural Tangent Kernel: training pushes the kernel-graph alignment upward regardless of homophily, and in low-homophily graphs this geometry forces kernel-target alignment down, leaving label memorization as the only route to low training loss. The node-level discriminator is the Label

Load-bearing premise

The whole analysis depends on a cheap two-model approximation—one model trained with a 25% candidate batch, one without it—being a faithful stand-in for true leave-one-out memorization; the paper itself notes it removes batches of nodes rather than single nodes, so if that proxy is off, the reported rates and every trend built on them would shift.

What would settle it

Retrain a GNN many times on a low-homophily graph, each time leaving out a single different training node, and compare those true leave-one-out scores to NCMemo's two-model batch approximation. If the batch approximation does not reproduce the per-node ordering of true leave-one-out scores, the reported memorization rates and the inverse-homophily trend would not be supported.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

  • Heterophilic graph benchmarks will show inflated memorization, so accuracy gains on them may reflect fitting labels instead of learning transferable structure; evaluations on low-homophily data should report memorization alongside accuracy.
  • Nodes flagged as memorized are precisely the ones membership-inference attacks single out: on the lowest-homophily synthetic graph the attack reaches 0.936 AUC versus 0.538 at maximum homophily.
  • Feature-similarity rewiring that raises homophily cuts memorization rate and membership-inference risk, with AUC dropping by more than 20% on the lowest-homophily graphs while test accuracy stays flat or improves.
  • The memorization rate climbs over training epochs, fastest on low-homophily graphs, so early stopping and homophily-aware training can be expected to lower memorization.
  • The inverse homophily–memorization relation holds across GCN, GraphSAGE, GATv2, and SGC on real datasets, making it a general property of message-passing GNNs rather than an artifact of one architecture.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If the inverse homophily law is right, a model's generalization on heterophilic graphs is partly a memorization story; architectures that adaptively down-weight uninformative edges should show a flatter memorization-versus-homophily slope, which is a testable prediction.
  • The Label Disagreement Score could be used before training as a sanitization signal—relabeling, dropping, or down-weighting high-LDS nodes—and one could measure whether that reduces memorization more cheaply than rewiring.
  • Rewiring changes the graph's label-feature correspondence, so the reported accuracy preservation may hide a distribution shift; a useful extension is to measure memorization and privacy risk along the full edge-budget curve rather than at one chosen budget.
  • The framework's extension to graph classification finds zero memorization on clean benchmarks but detects it after adding noise to candidate graphs, suggesting memorization in graph classification is tied to atypical instances—worth testing on naturally long-tailed graph datasets.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

4 major / 4 minor

Summary. The paper introduces NCMemo, a framework for measuring label memorization in semi-supervised node classification. The framework compares two GNN models, one trained with a candidate node set and one trained without it, and defines a per-node memorization score and a memorization rate. Based on experiments on synthetic and real-world graphs across several GNN architectures, the paper claims an inverse relationship between memorization rate and graph homophily (Proposition 1), explains this through NTK alignment dynamics (Propositions 2 and 3), introduces a Label Disagreement Score to identify memorization-prone nodes (Proposition 4), and proposes graph rewiring as a mitigation that also reduces membership-inference privacy risk. The paper includes extensive experiments, additional analyses on graph classification, larger datasets, and a graph transformer, plus runtimes and a code link.

Significance. If the central result holds, this is a valuable contribution to the understanding of memorization in GNNs and has practical privacy implications. The empirical scope is broad: four GNN backbones, multiple real datasets, controlled synthetic homophily levels, and a direct evaluation of membership-inference risk. The authors also provide a candidate mitigation (graph rewiring) and demonstrate its effect on both memorization and privacy metrics. The framework is computationally lightweight and the paper includes a reproducibility link. However, the central claim rests on a batch approximation of leave-one-out memorization that is not validated, and the theoretical propositions are largely observational or rely on an assumption that restates the observed phenomenon. These issues need to be addressed before the results can be accepted as stated.

major comments (4)
  1. [§3, Eq. (1)–(2); §5; Appendix F.3] The memorization score used in all experiments is not the leave-one-out quantity in Eq. (1). Model g is trained on SS∪SI, so for a candidate vi∈SC, g has not only vi removed but the entire candidate block SC (25% of training nodes) removed and replaced by SI. As the paper acknowledges in F.3, this is a batch approximation. The bias is likely homophily-dependent: in low-homophily graphs, labels are less predictable from neighbors and features, so removing a block of training labels degrades g's accuracy on SC more than in high-homophily graphs. This can inflate M(vi) uniformly and manufacture the inverse MR–homophily trend (Fig. 3, Prop. 1) even if per-node LOO memorization were flat. Please validate the approximation against true leave-one-out on at least one synthetic and one small real graph, or provide a formal bound on the bias as a function of h. Without this, the central claim is n
  2. [§4.2; Appendix D.2, Prop. 2] The 'simple proof' in D.2 does not establish memorization. Assumption 1 restates the observed tendency that A(Θt,A) increases during training; Assumption 2 is essentially the definition of low homophily. The triangle-inequality argument only derives a lower bound on the angle between Θt and Θ*, i.e., low kernel-target alignment. Nothing in the proof relates these geometric constraints to M(vi) or the memorization rate; the connection is asserted. Proposition 2 itself is a list of empirical observations (i)–(iii). We recommend reframing Prop. 2 as an empirical finding supported by a geometric consistency check, or providing a rigorous argument linking alignment dynamics to the memorization score. As written, the proof gives the appearance of a theorem where none is established.
  3. [§4.2, Prop. 3; Figs. 5 and 7] The Pearson correlations between MR and the final alignments are computed on the same trained models that produce both quantities, and both MR and alignment are strongly driven by the common factor h. The correlations are therefore descriptive fits, not independent confirmations of a predictive relationship. This is especially concerning for the synthetic data (Fig. 5), where the five points are separated by construction. Please report partial correlations controlling for homophily, or show within-graph variance across seeds, to demonstrate that the relationship is not purely an artifact of the h-axis. The statement that these results 'validate' Prop. 3 is overstated.
  4. [§4.3, Tables 1–2; §4.1, Eq. (2)] The LDS analysis relies on classifying nodes as memorized or non-memorized using the batch estimator and threshold τ=0.5. If the estimator is biased (Comment 1), the LDS separation may partly reflect that bias rather than a true per-node phenomenon. Additionally, τ=0.5 is introduced as a predefined threshold but is not inherent to the Feldman definition cited; it is a new hyperparameter that can amplify systematic calibration differences between f and g. Please re-run the LDS analysis with a validated memorization estimator, or at least show robustness to τ and to alternative extreme-score comparisons.
minor comments (4)
  1. [§5 vs. Appendix I.2] The data split is inconsistent: Section 5 states SS=50%, SC=25%, SI=25%, while Appendix I.2 says SS=80%, SI=SC=10%. This makes the experimental setup ambiguous and should be corrected.
  2. [§4.1, Prop. 1] The phrase 'inversely proportional' suggests MR ∝ 1/h, but the results only support a monotonic decrease. Please use 'decreases with' or state the specific functional form if one is intended.
  3. [Table 19] The homophily values for Cornell, Texas, and Wisconsin are reported as negative (−0.20, −0.23, −0.13). Edge homophily is defined on [0,1] in Eq. (5); please clarify which metric is reported (e.g., adjusted homophily) and cite the source.
  4. [Appendix F.3] The sentence 'this keeps the overhead minimal while still aligning closely with the theoretical definition' is unsupported. Given the concern in Major Comment 1, please provide evidence or temper this claim.

Circularity Check

2 steps flagged

Reported memorization–homophily trend is largely an artifact of the batch two-model estimator; the central proposition reduces by construction.

specific steps
  1. self definitional [Section 4, data-partitioning setup and Eq. (1)-(2); Appendix F.3]
    "Subsequently, we train model f on SS ∪ SC and model g on SS ∪ SI. ... Our method only requires a single additional trained model and evaluates the effect for simultaneous removal of batches of nodes (25% of training nodes)."

    For vi∈SC, g has not seen vi or any other candidate node, so E_g[Pr(g(vi)=yi)] in Eq. (1) measures how well yi can be predicted from graph structure/features without the label. This is exactly what homophily controls: at h=1.0 neighbors determine the label, so g is as confident as f and M≈0; at h=0.0 g's accuracy on SC collapses while f can fit the labels, so M is large. The reported inverse MR-homophily trend (Prop. 1) is therefore a property of the batch estimator, not an independent discovery about per-sample memorization; the paper's own F.3 acknowledges the proxy but does not account for its homophily dependence.

  2. self definitional [Section 4.3, Eq. (4), Table 1]
    "We consistently observe that memorized nodes exhibit, on average, significantly higher LDS than 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 to being memorized by the GNN."

    Memorized nodes are defined by M(vi)>τ, i.e., f samples the candidate's label correctly while g (trained without SC) does not. High LDS means the node's label is atypical among its feature neighbors, which is precisely the condition that makes g fail. Thus the Proposition 4 association is largely encoded in the two-model partition rather than being an independent characterization of which nodes a GNN memorizes.

full rationale

The paper's main derivation is empirical rather than a formal derivation from first principles. The NTK analysis in Appendix D.2 is a valid triangle-inequality implication, but Assumption 1 restates the observed increasing A(Θt,A) that Proposition 2 is supposed to establish, so it does not independently explain memorization. The core problem is that NCMemo's reported memorization scores are not the leave-one-out quantity of Eq. (1): f sees SS∪SC, g sees SS∪SI, so for each vi∈SC, g is missing the entire candidate block. The gap M_batch(vi) is dominated by how predictable yi is from homophily-driven context; hence Prop. 1's inverse MR-homophily curve is essentially fixed by the estimator. Similarly, the LDS result labels as 'memorized' exactly the nodes where the no-candidate model fails, which are the high-LDS nodes by construction. The paper's self-citations ([63], [54]) are methodological and not load-bearing. Because the central quantitative claim reduces to the estimator's construction rather than to an independent per-sample LOO measurement, I assign 6.

Axiom & Free-Parameter Ledger

3 free parameters · 3 axioms · 0 invented entities

The paper introduces no new physical entities. The central claims rest on the threshold and k choices, the two assumptions about GNN training and homophily-kernel alignment, and the borrowed Feldman lemmas.

free parameters (3)
  • Memorization threshold tau = 0.5
    Predefined threshold for classifying a node as memorized, following Feldman [21]. Not fitted, but directly affects the memorization rate metric.
  • LDS hyperparameter k = 3
    Number of feature-space neighbors used for the Label Disagreement Score; chosen to mimic the GNN's 3-hop aggregation, not fitted to data.
  • Rewiring edge budget = 100, 500, or 1000 per graph
    Number of edges added, deleted, or both in the rewiring experiments; selected per graph by tuning over {100, 500, 1000} to maximize accuracy, homophily, and memorization reduction (Appendix H).
axioms (3)
  • domain assumption GNN training dynamics increase kernel-graph alignment (Assumption 1, Appendix D.1)
    Used in the geometric proof to argue that high kernel-graph alignment forces low kernel-target alignment in low homophily. This behavior is observed empirically, not proven from first principles.
  • domain assumption Low homophily implies low alignment between the adjacency matrix and the optimal kernel (Assumption 2)
    Encodes the definition of homophily in kernel-alignment terms; used as a premise in the proof of Proposition 2.
  • standard math Feldman's Lemma 4.2 and 4.3 relating memorization to the generalization gap
    Borrowed from Feldman [21] to argue that high-homophily graphs have low memorization and that low-homophily atypical nodes must be memorized to reach zero training loss (Appendix D.4).

reviewed 2026-08-05 · how reviews work

0 comments
Cite this review

Pith. "Pith review of Memorization in Graph Neural Networks." pith.science (2026). https://pith.science/paper/2J4DAJ7C

@misc{pith2026250819352,
  author       = {Pith},
  title        = {Pith review of: Memorization in Graph Neural Networks},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2J4DAJ7C}},
  note         = {Machine review of arXiv:2508.19352}
}
Share X Bluesky LinkedIn Reddit HN
read the original abstract

Deep neural networks (DNNs) have been shown to memorize their training data, yet similar analyses for graph neural networks (GNNs) remain largely under-explored. We introduce NCMemo (Node Classification Memorization), the first framework to quantify label memorization in semi-supervised node classification. We first establish an inverse relationship between memorization and graph homophily, i.e., the property that connected nodes share similar labels/features. We find that lower homophily significantly increases memorization, indicating that GNNs rely on memorization to learn less homophilic graphs. Secondly, we analyze GNN training dynamics. We find that the increased memorization in low homophily graphs is tightly coupled to the GNNs' implicit bias on using graph structure during learning. In low homophily regimes, this structure is less informative, hence inducing memorization of the node labels to minimize training loss. Finally, we show that nodes with higher label inconsistency in their feature-space neighborhood are significantly more prone to memorization. Building on our insights into the link between graph homophily and memorization, we investigate graph rewiring as a means to mitigate memorization. Our results demonstrate that this approach effectively reduces memorization without compromising model performance. Moreover, we show that it lowers the privacy risk for previously memorized data points in practice. Thus, our work not only advances understanding of GNN learning but also supports more privacy-preserving GNN deployment.

Figures

Figures reproduced from arXiv: 2508.19352 by Adam Dziedzic, Adarsh Jamadandi, Franziska Boenisch, Jing Xu.

Figure 1
Figure 1. Figure 1: Data partition￾ing in our label memo￾rization framework. 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 [63] to make the evalua… view at source ↗
Figure 2
Figure 2. 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 a three-layered GCN [37] on each graph of syn-cora and calculate the memorization scores based on Equation (1). We plot the memorization scores for the candidate nodes (SC ) across different graphs in [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 4
Figure 4. Figure 4: We track the memorization rate of the candidate nodes trained on model f across train￾ing epochs; correspondingly, we also track the A(Θt, Θ∗ ) and A(Θt, A) across epochs. The lines are color coded by the homophily level [PITH_FULL_IMAGE:figures/full_fig_p005_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: The inverse relationship between MR and the A(Θfinal, Θ∗ ), A(Θfinal, A) alignments. We measure the correlation between the memorization rate and alignment matrices by setting Θt = Θfinal, 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(Θfinal, A) and A(Θfinal, Θ∗ ). The results are presented in [PITH_FULL_IMAGE:figure… view at source ↗
Figure 6
Figure 6. Figure 6: Memorization scores of SC for Cora, Citeseer, Chameleon, and Squirrel datasets. The candidate nodes of homophilic graphs exhibit lower memorization scores than heterophilic graphs. 0.0 0.1 0.2 0.3 0.4 0.5 0.6 NTK Alignment Value 0 10 20 30 40 50 60 70 80 Memorization Rate (MR %) A( final, * ) vs MR (r=-0.79) A( final, A) vs MR (r=-0.58) Cora Citeseer Cornell Texas Wisconsin Chameleon Squirrel Actor [PITH_… view at source ↗
Figure 7
Figure 7. Figure 7: The inverse rela￾tionship between MR and the A(Θfinal, Θ∗ ), A(Θfinal, A) align￾ments for real-world datasets. Evolution of alignment matrices on real-world graphs. We also track the evolution of the different alignment matrices on 9 real-world graphs trained on GCN in [PITH_FULL_IMAGE:figures/full_fig_p007_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Evolution of the NTK matrix Θt and its alignment with the adjacency matrix A and the optimal kernel Θ∗ 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(Θt, A) improves during training regardless of the graph homophily level. (c) The kernel-target alignment A(Θt, Θ∗ ) is poor for low-homop… view at source ↗
Figure 9
Figure 9. Figure 9: MIA risk of GNNs trained on original syn-cora (left) and rewired syn-cora (right). h0.0 (1.0) means homophily level 0.0 (1.0). We finally turn to the real-world impact of mem￾orization. In DNNs, memorization has often been linked to privacy risks for the memorized data points, e.g., [15, 18]. In this section, we highlight that the same holds for GNNs. Based on our findings from the previous sections, we ex… view at source ↗
Figure 10
Figure 10. Figure 10: We illustrate the emergence of memorization in this conceptual diagram. We visualize the alignment matrices as 1D vectors on a hypothetical 2D loss landscape of some GNN model, for instance a GCN trained on syn-cora dataset as in Proposition 2. In low homophily regimes, the model’s tendency to align the A with Θt (kernel-graph alignment) results in the model deviating away from the optimal kernel Θ∗ resul… view at source ↗
Figure 11
Figure 11. Figure 11: Distribution of Memorization Scores on 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 are higher (lower) for SC (SI ) compared to SS or SE [PITH_FULL_IMAGE:figures/full_fig_p021_11.png] view at source ↗
Figure 12
Figure 12. Figure 12: Distribution of memorization scores for each node category [PITH_FULL_IMAGE:figures/full_fig_p022_12.png] view at source ↗
Figure 13
Figure 13. Figure 13: Distribution of memorization scores for each node category [PITH_FULL_IMAGE:figures/full_fig_p023_13.png] view at source ↗
Figure 14
Figure 14. Figure 14: Distribution of memorization scores for each node category [PITH_FULL_IMAGE:figures/full_fig_p024_14.png] view at source ↗
Figure 15
Figure 15. Figure 15: Memorization rate of candidate nodes in syn-cora-h0.0, before and after edge modification. Edge Additions. In [PITH_FULL_IMAGE:figures/full_fig_p027_15.png] view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

77 extracted references · 55 canonical work pages · 4 internal anchors

  1. [1]

    MixHop: Higher-order graph convolutional architectures via sparsified neighborhood mixing

    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, ...

    work page 2019

  2. [2]

    On the bottleneck of graph neural networks and its practical implications

    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: //openreview.net/forum?id=i80OPhOCVH2

    work page 2021

  3. [3]

    Gholamali Aminian, Yixuan He, Gesine Reinert, Łukasz Szpruch, and Samuel N. Cohen. Generalization error of graph neural networks in the mean-field regime, 2024. URL https: //arxiv.org/abs/2402.07025

    work page internal anchor Pith review Pith/arXiv arXiv 2024

  4. [4]

    Du, Wei Hu, Zhiyuan Li, and Ruosong Wang

    Sanjeev Arora, Simon S. Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. CoRR, abs/1901.08584, 2019. URL http://arxiv.org/abs/1901.08584

    Pith/arXiv arXiv 1901

  5. [5]

    A closer look at memorization in deep networks

    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 in deep networks. In International conference on machine learning, pages 233–242. PMLR, 2017

    work page 2017

  6. [6]

    Deep learning through the lens of example difficulty

    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: //openreview.net/forum?id=WWRBHhH158K

    work page 2021

  7. [7]

    Emergence of scaling in random networks

    Albert-László Barabási and Réka Albert. Emergence of scaling in random networks. Science, 286(5439):509–512, October 1999. ISSN 1095-9203. doi: 10.1126/science.286.5439.509. URL http://dx.doi.org/10.1126/science.286.5439.509

    doi:10.1126/science.286.5439.509 1999

  8. [8]

    The pitfalls of memorization: When memorization hurts generalization, 2024

    Reza Bayat, Mohammad Pezeshki, Elvis Dohmatob, David Lopez-Paz, and Pascal Vincent. The pitfalls of memorization: When memorization hurts generalization, 2024. URL https: //arxiv.org/abs/2412.07684

    Pith/arXiv arXiv 2024

  9. [9]

    Graph neural networks use graphs when they shouldn’t, 2024

    Maya Bechler-Speicher, Ido Amos, Ran Gilad-Bachrach, and Amir Globerson. Graph neural networks use graphs when they shouldn’t, 2024. URL https://arxiv.org/abs/2309. 04332

    work page 2024

  10. [10]

    Make heterophily graphs better fit gnn: A graph rewiring approach, 2022

    Wendong Bi, Lun Du, Qiang Fu, Yanlin Wang, Shi Han, and Dongmei Zhang. Make heterophily graphs better fit gnn: A graph rewiring approach, 2022

    work page 2022

  11. [11]

    Memorization and optimization in deep neural networks with minimum over-parameterization

    Simone Bombari, Mohammad Hossein Amani, and Marco Mondelli. Memorization and optimization in deep neural networks with minimum over-parameterization. Advances in Neural Information Processing Systems, 35:7628–7640, 2022

    work page 2022

  12. [12]

    Biognn: How graph neural networks can solve biological problems

    Pietro Bongini, Niccolò Pancino, Franco Scarselli, and Monica Bianchini. Biognn: How graph neural networks can solve biological problems. In Artificial Intelligence and Machine Learning for Healthcare, pages 211–231. Springer, 2023

    work page 2023

  13. [13]

    How attentive are graph attention networks? In International Conference on Learning Representations, 2022

    Shaked Brody, Uri Alon, and Eran Yahav. How attentive are graph attention networks? In International Conference on Learning Representations, 2022. URL https://openreview. net/forum?id=F72ximsx7C1. 10

    work page 2022

  14. [14]

    Bronstein, Joan Bruna, Taco Cohen, and Petar Velickovic

    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: //arxiv.org/abs/2104.13478

    Pith/arXiv arXiv 2021

  15. [15]

    Extracting training data from large language models

    Nicholas Carlini, Florian Tramer, Eric Wallace, Matthew Jagielski, Ariel Herbert-V oss, 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

    2021

  16. [16]

    Membership inference attacks from first principles

    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

    work page 2022

  17. [17]

    The privacy onion effect: Memorization is relative

    Nicholas Carlini, Matthew Jagielski, Chiyuan Zhang, Nicolas Papernot, Andreas Terzis, and Florian Tramer. The privacy onion effect: Memorization is relative. Advances in Neural Information Processing Systems, 35:13263–13276, 2022

    work page 2022

  18. [18]

    Quantifying memorization across neural language models, 2022

    Nicholas Carlini, Daphne Ippolito, Matthew Jagielski, Katherine Lee, Florian Tramer, and Chiyuan Zhang. Quantifying memorization across neural language models, 2022. URL https://arxiv. org/abs/2202.07646, 2023

    Pith/arXiv arXiv 2022

  19. [19]

    On kernel-target alignment

    Nello Cristianini, John Shawe-Taylor, André Elisseeff, and Jaz Kandola. On kernel-target alignment. In T. Dietterich, S. Becker, and Z. Ghahramani, edi- tors, Advances in Neural Information Processing Systems , volume 14. MIT Press,

    work page

  20. [20]

    Attentive walk-aggregating graph neural networks

    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 https://openreview.net/forum?id=TWSTyYd2Rl

    work page 2022

  21. [21]

    Does learning require memorization? a short tale about a long tail

    Vitaly Feldman. Does learning require memorization? a short tale about a long tail. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing , pages 954–959, 2020

    2020

  22. [22]

    How powerful are k-hop message passing graph neural networks

    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

    work page 2022

  23. [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

    work page 2019

  24. [24]

    Schoenholz, Patrick F

    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 on Machine Learning - Volume 70, ICML’17, page 1263–1272. JMLR.org, 2017

    work page 2017

  25. [25]

    Giraldo, Konstantinos Skianis, Thierry Bouwmans, and Fragkiskos D

    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 Machine...

    arXiv 2023

  26. [26]

    Understanding the difficulty of training deep feedforward neural networks

    Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Yee Whye Teh and Mike Titterington, editors,Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, volume 9 of Proceedings of Machine Learning Research, pages 249–256, Chia Laguna Resort, Sardinia, Italy...

    work page

  27. [27]

    M. Gori, G. Monfardini, and F. Scarselli. A new model for learning in graph domains. In Proceedings. 2005 IEEE International Joint Conference on Neural Networks, 2005., volume 2, pages 729–734 vol. 2, 2005. doi: 10.1109/IJCNN.2005.1555942. 11

    work page arXiv 2005

  28. [28]

    Hamilton, Rex Ying, and Jure Leskovec

    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 9781510860964

    work page 2017

  29. [29]

    Hamilton, Zhitao Ying, and Jure Leskovec

    William L. Hamilton, Zhitao Ying, and Jure Leskovec. Inductive Representation Learning on Large Graphs. In NIPS, pages 1024–1034, 2017

    work page 2017

  30. [30]

    Open graph benchmark: Datasets for machine learning on graphs

    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 arXiv:2005.00687, 2020

    Pith/arXiv arXiv 2005

  31. [31]

    Neural tangent kernel: Convergence and generalization in neural networks

    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. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Sys- tems, volume 31. Curran Associates, Inc., 2018. URL https://proceedings.neurips.cc/ paper_...

    work page 2018

  32. [32]

    Spectral graph pruning against over-squashing and over-smoothing

    Adarsh Jamadandi, Celia Rubio-Madrigal, and Rebekka Burkholz. Spectral graph pruning against over-squashing and over-smoothing. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024

    work page 2024

  33. [33]

    Banerjee, and Guido Montufar

    Kedar Karhadkar, Pradeep Kr. Banerjee, and Guido Montufar. FoSR: First-order spectral rewiring for addressing oversquashing in GNNs. In The Eleventh International Confer- ence on Learning Representations , 2023. URL https://openreview.net/forum?id= 3YjQfCLdrzz

    work page 2023

  34. [34]

    Homophily influences ranking of minorities in social networks

    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

    work page

  35. [35]

    Not too little, not too much: a theoretical analysis of graph (over)smoothing

    Nicolas Keriven. Not too little, not too much: a theoretical analysis of graph (over)smoothing. In The First Learning on Graphs Conference, 2022. URL https://openreview.net/forum? id=KQNsbAmJEug

    work page 2022

  36. [36]

    Convergence and Stability of Graph Convolutional Networks on Large Random Graphs

    Nicolas Keriven, Alberto Bietti, and Samuel Vaiter. Convergence and stability of graph convolu- tional networks on large random graphs, 2020. URL https://arxiv.org/abs/2006.01868

    work page internal anchor Pith review Pith/arXiv arXiv 2020

  37. [37]

    Kipf and Max Welling

    Thomas N. Kipf and Max Welling. Semi-Supervised Classification with Graph Convolutional Networks. In ICLR, 2017

    work page 2017

  38. [38]

    Trustworthy machine learning via memorization and the granular long-tail: A survey on interactions, tradeoffs, and beyond, 2025

    Qiongxiu Li, Xiaoyu Luo, Yiyi Chen, and Johannes Bjerva. Trustworthy machine learning via memorization and the granular long-tail: A survey on interactions, tradeoffs, and beyond, 2025. URL https://arxiv.org/abs/2503.07501

    Pith/arXiv arXiv 2025

  39. [39]

    Towards bridging generalization and expressivity of graph neural networks, 2024

    Shouheng Li, Floris Geerts, Dongwoo Kim, and Qing Wang. Towards bridging generalization and expressivity of graph neural networks, 2024. URL https://arxiv.org/abs/2410. 10051

    work page 2024

  40. [40]

    Can neural network memorization be localized? arXiv preprint arXiv:2307.09542, 2023

    Pratyush Maini, Michael C Mozer, Hanie Sedghi, Zachary C Lipton, J Zico Kolter, and Chiyuan Zhang. Can neural network memorization be localized? arXiv preprint arXiv:2307.09542, 2023

    Pith/arXiv arXiv 2023

  41. [41]

    Automat- ing the construction of internet portals with machine learning

    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.1023/A:1009953814988. URL https://doi.org/10.1023/A: 1009953814988

    doi:10.1023/a:1009953814988 2000

  42. [42]

    Schoenholz, Muratahan Aykol, Gowoon Cheon, and Ekin Dogus Cubuk

    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.1038/s41586-023-06735-9. URL https://doi.org/10.1038/ s41586-023-06735-9 . 12

    doi:10.1038/s41586-023-06735-9 2023

  43. [43]

    Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann

    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, abs/2007.08663, 2020. URL https://arxiv.org/abs/2007.08663

    Pith/arXiv arXiv 2007

  44. [44]

    Are GATs out of balance? In Thirty-seventh Conference on Neural Information Processing Systems, 2023

    Nimrah Mustafa, Aleksandar Bojchevski, and Rebekka Burkholz. Are GATs out of balance? In Thirty-seventh Conference on Neural Information Processing Systems, 2023. URL https: //openreview.net/forum?id=qY7UqLoora

    work page 2023

  45. [45]

    Query-driven active surveying for collective classification

    Galileo Namata, Ben London, Lise Getoor, and Bert Huang. Query-driven active surveying for collective classification. 2012

    work page 2012

  46. [46]

    Revisiting over-smoothing and over-squashing using ollivier-ricci curvature, 2023

    Khang Nguyen, Hieu Nong, Vinh Nguyen, Nhat Ho, Stanley Osher, and Tan Nguyen. Revisiting over-smoothing and over-squashing using ollivier-ricci curvature, 2023

    work page 2023

  47. [47]

    k-hop graph neural networks,

    Giannis Nikolentzos, George Dasoulas, and Michalis Vazirgiannis. k-hop graph neural networks,

    work page

  48. [48]

    Geom-gcn: Geo- metric graph convolutional networks

    Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gcn: Geo- metric graph convolutional networks. In International Conference on Learning Representations,

    work page

  49. [49]

    Charac- terizing graph datasets for node classification: Homophily-heterophily dichotomy and be- yond

    Oleg Platonov, Denis Kuznedelev, Artem Babenko, and Liudmila Prokhorenkova. Charac- terizing graph datasets for node classification: Homophily-heterophily dichotomy and be- yond. In Thirty-seventh Conference on Neural Information Processing Systems, 2023. URL https://openreview.net/forum?id=m7PIJWOdlY

    work page 2023

  50. [50]

    A critical look at evaluation of gnns under heterophily: Are we really making progress? In The Eleventh International Conference on Learning Representations, 2023

    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? In The Eleventh International Conference on Learning Representations, 2023

    work page 2023

  51. [51]

    Recipe for a General, Powerful, Scalable Graph Transformer

    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

    work page 2022

  52. [52]

    Graph neural networks for materials science and chemistry

    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.1038/s43246-022-00315-6. URL https://doi.org/10.1038/ s43246-022-00315-6

    doi:10.1038/s43246-022-00315-6 2022

  53. [53]

    URL https://openreview.net/forum?id=S1e2agrFvS

    work page

  54. [54]

    GNNs getting comfy: Com- munity and feature similarity guided rewiring

    Celia Rubio-Madrigal, Adarsh Jamadandi, and Rebekka Burkholz. GNNs getting comfy: Com- munity and feature similarity guided rewiring. In The Thirteenth International Conference on Learning Representations, 2025. URL https://openreview.net/forum?id=g6v09VxgFw

    work page 2025

  55. [55]

    The graph neural network model

    Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 20(1):61–80, 2009. doi: 10.1109/TNN.2008.2005605

    arXiv 2009

  56. [56]

    Collective classification in network data

    Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classification in network data. AI Magazine, 29(3):93, Sep. 2008. doi: 10.1609/aimag.v29i3.2157. URL https://ojs.aaai.org/index.php/aimagazine/ article/view/2157

    doi:10.1609/aimag.v29i3.2157 2008

  57. [57]

    Pitfalls of graph neural network evaluation, 2019

    Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation, 2019

    2019

  58. [58]

    Multi-scale attributed node embedding

    Benedek Rozemberczki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. CoRR, abs/1909.13021, 2019. URL http://arxiv.org/abs/1909.13021

    Pith/arXiv arXiv 1909

  59. [59]

    Membership inference attacks against machine learning models

    Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov. Membership inference attacks against machine learning models. In 2017 IEEE symposium on security and privacy (SP), pages 3–18. IEEE, 2017

    2017

  60. [60]

    Towards understanding generalization of graph neural networks

    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 on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 33674–33719. PMLR, 23...

    work page 2023

  61. [61]

    Bronstein

    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. URL https://openreview. net/forum?id=7UmjRGzp-A

    work page 2022

  62. [62]

    Graph Attention Networks

    Petar Veliˇckovi´c, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph Attention Networks. In ICLR, 2018

    work page 2018

  63. [63]

    Graph neural networks in particle physics

    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/ 2632-2153/abbf9a. URL https://doi.org/10.1088/2632-2153/abbf9a. 13

    doi:10.1088/2632-2153/abbf9a 2021

  64. [64]

    A Manifold Perspective on the Statistical Generalization of Graph Neural Networks

    Zhiyang Wang, Juan Cervino, and Alejandro Ribeiro. A manifold perspective on the statistical generalization of graph neural networks, 2024. URL https://arxiv.org/abs/2406.05225

    work page internal anchor Pith review Pith/arXiv arXiv 2024

  65. [65]

    Simplifying graph convolutional networks

    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 ht...

    work page 2019

  66. [66]

    How graph neural networks learn: Lessons from training dynamics in function space, 2024

    Chenxiao Yang, Qitian Wu, David Wipf, Ruoyu Sun, and Junchi Yan. How graph neural networks learn: Lessons from training dynamics in function space, 2024. URL https:// openreview.net/forum?id=OBITU0NAKl

    work page 2024

  67. [67]

    Understanding deep learning requires rethinking generalization

    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 https://openreview.net/forum?id=Sy8gdB9xx

    work page 2017

  68. [68]

    Memorization in self-supervised learning improves downstream generalization

    Wenhao Wang, Muhammad Ahmad Kaleem, Adam Dziedzic, Michael Backes, Nicolas Papernot, and Franziska Boenisch. Memorization in self-supervised learning improves downstream generalization. In The Twelfth International Conference on Learning Representations, 2024. URL https://openreview.net/forum?id=KSjPaXtxP8

    work page 2024

  69. [73]

    Be- yond homophily in graph neural networks: Current limitations and effective designs

    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. 14 A Limitations and Future Work Limitations. Our work proposes an end-to-end framework to study the memorization phenomenon ...

    work page 2020

  70. [74]

    is defined as Θ∗ = ¯Y ¯YT and it measures how similar two instances of data points are. Further, we can define a similarity metric that measures the alignment between two kernelsK1 and K2 as 15 A(K1, K2) = ⟨K1, K2⟩F ||K1||F ||K2||F (7) This metric can be seen as a generalization of the cosine similarity applied to matrices and it satisfies the triangle in...

    work page

  71. [75]

    Based on Assumption 1, a high kernel-graph alignment implies, the angle ϵ between A and Θt should be small (ideally, 0◦), from a geometrical perspective we can think of this as two vectors pointing in the same direction4

    work page

  72. [76]

    Inequality 10 states that γ must be greater than or equal to this large angle (δ − ϵ)

    Based on Assumption 2, in low homophily settings, the angle δ between A and Θ∗ should be large (e.g, 90◦) Therefore, the term δ − ϵ represents a large angle minus a small angle, which is still a large angle (quantitatively close to δ). Inequality 10 states that γ must be greater than or equal to this large angle (δ − ϵ). This forces γ itself to be large. ...

    work page 1993

  73. [77]

    Our theoretical results in Section 4 demonstrate that one of the key factors influencing memorization in GNNs is the graph homophily

    while also improving the generalization performance on downstream tasks. Our theoretical results in Section 4 demonstrate 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 ...

    work page 2029

  74. [2001]

    URL https://proceedings.neurips.cc/paper_files/paper/2001/file/ 1f71e393b3809197ed66df836fe833e5-Paper.pdf

    work page 2001

  75. [2010]

    URL https://proceedings.mlr.press/v9/glorot10a.html

    PMLR. URL https://proceedings.mlr.press/v9/glorot10a.html

    work page

  76. [2018]

    doi: 10.1038/s41598-018-29405-7

    ISSN 2045-2322. doi: 10.1038/s41598-018-29405-7. URL http://dx.doi.org/10. 1038/s41598-018-29405-7

    doi:10.1038/s41598-018-29405-7 2045

  77. [2020]

    URL https://arxiv.org/abs/1907.06051

    work page internal anchor Pith review Pith/arXiv arXiv 1907

This paper was first reviewed by deepseek-v4-flash on August 5, 2026.