acceptodds
Under review as a conference paper at ICLR 2027

Quantifying Graph Structural Memorization in Large Language Models

Abstract

Memorization in Large Language Models (LLMs) is well documented for sequential content such as text and code. As LLMs are increasingly trained with graph-structured data, however, whether memorization also extends to graph structure remains largely unexplored. To study this question, we introduce an exposure-controlled evaluation framework that examines how graph recoverability changes with training exposure. The framework separates training-specific recovery from general graph prediction by comparing exposed target graphs against graphs never exposed during training. Using this framework, we observe an exposure-dependent form of graph structural memorization: graph structure becomes increasingly recoverable as the model is exposed more frequently to the target graph during training. Motivated by this observation, we formalize the underlying recovery procedure as training-graph stealing, a black-box attack against graph-trained LLMs that makes this form of memorization concretely exploitable. Given candidate nodes and their textual descriptions, the attack queries each node pair to infer adjacency and assembles the predicted edges into a reconstructed graph. Experiments show that exposure-dependent recovery persists across graph-access settings, graph scales and model families. Together, these findings demonstrate that LLM memorization can extend beyond sequential content to graph structure, creating a new attack surface for extracting graph-structured training data.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
Memorization, Large Language Models, Graph Stealing Attacks

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_1jWHOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper asks whether LLMs trained on graph-structured data memorize topology, not only sequential text or code. The authors define graph structural memorization as an exposure-dependent gain in recoverability of a target graph that exceeds the corresponding gain on size-matched graphs never seen in training. They then recast the same recovery procedure as a black-box training-graph stealing attack: the attacker is given the candidate node set and node text, queries every pair for adjacency, and assembles predicted edges into a reconstructed graph.

Critical strengths

The paper goes beyond raw link-recovery accuracy and explicitly tests whether recovery changes are target-specific. The rewiring control demonstrates that model behavior tracks exposed relationships rather than only shared node identities and descriptions.

Critical weaknesses

W1: Graph structural memorization is not shown to be a new concept distinct from ordinary fine-tuning memorization of labeled facts. Furthermore, training graph stealing is not a new attack primitive, as it is essentially an exhaustive pairwise querying of a model trained to answer such queries.

W2: The scale of the experimental setup is too small, overly sparse, and excessively privileged to support the derived conclusions. (1), the size of the target graphs is n∈5,10,20,40n \in \\{5,10,20,40\\} with a split ratio of 9/9/3/3, featuring only one graph per size. (2), each target is trained in isolation under e∈0,20,60e \in \\{0,20,60\\}, however graph-LLMs are not trained by repeatedly training a 20-node subgraph 60 times in dedicated runs. (3), the masked graph context provides a 15-node ego graph with only the queried edge removed, which leaks a substantial amount of topological structure during inference.

W3: It lacks mechanistic analysis and defensive measures.

Questions for authors

see the weakness.

Reviewer_TibcOpenReview ↗
Rating
2
Confidence
4
Informativeness
1
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies whether LLMs memorize graph structures seen during training. The authors introduce an exposure-controlled framework to distinguish memorization from general graph prediction, and propose a black-box graph stealing attack based on pairwise adjacency queries. Experiments across three models and four datasets show that repeated exposure generally improves graph recovery.

Critical strengths

1. An interesting problem with a reasonable evaluation design.

Studying graph structural memorization in LLMs is worthwhile. The use of unexposed control graphs helps separate training-specific recovery from general link prediction.

Critical weaknesses

1. Limited novelty and overstated contributions.

The core experiment repeatedly trains models on pairwise adjacency labels and then tests whether those relationships can be recovered. The resulting improvement with increased exposure is unsurprising. While the controls show target-specific gains, it remains unclear what this reveals beyond conventional memorization of training labels.

Similarly, the proposed graph stealing attack simply queries every node pair and assembles the predicted edges. This is essentially exhaustive link prediction rather than a novel attack method. The paper presents these straightforward ideas as broader contributions without sufficient technical depth.

2. Poor scalability and limited practical relevance.

The experiments only cover graphs with 5–40 nodes. Figure 4 already shows that recovery becomes much harder as graph size increases, with none of the 40-node graphs reaching the persistent high-FGW threshold at the highest exposure level.

The attack also requires O(n2)O(n^2) queries and assumes the full candidate node set is known. These limitations make the practical graph stealing claims difficult to justify.

Questions for authors
  1. How is the observed structural memorization different from simply memorizing pairwise adjacency labels?
  2. What is technically new about the attack beyond exhaustive link prediction?
  3. How would the approach scale to realistic graphs, given the results on just 40 nodes?
Reviewer_bYyvOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies to what extent LLMs fine-tuned on graph data memorize relational structure, i.e., the edges of the graphs. The authors observe that these relational facts are increasingly recoverable as the model is exposed to the graph more frequently, and frame this as a “graph stealing attack” that can recover the graph structure from prompting the LLM for adjacency of nodes. To account for changes in performance under increased exposure, the authors define memorization as difference of the recovery gain on the target graph and an unexposed control graph. The claims are empirically supported by experiments on 7-8B models and small target graphs from Cora/PubMed/CiteSeer/ogbn-products.

Critical strengths
  • The exposition is easy to follow.
  • The metrics are designed carefully (i.e. to make sure that the observed gains cannot be explained solely by node-text similarity or general performance prediction).
  • The evaluation is relatively broad (3 models, 4 datasets, and 2 context settings, i.e. no graph context and masked graph context).
Critical weaknesses
  • One main issue I see is that the phenomenon is not really graph-specific, in the sense that no global structure is memorized but only pairwise facts, and the motivation in the introduction does not match the actual method. While l. 43-51 argues for studying graph structural memorization because the same graph structure (up to isomorphism) admits many serializations, the main experiment does not serialize the graphs, but just queries relational facts (i.e., whether nodes, each represented by some text, are connected by an edge), the text is already known when reconstructing/attacking, and the graph can be simply reconstructed as the union of retrieved edges. Hence, the serialization issue that motivates the problem in the introduction never arises and is irrelevant to what is actually done in the paper. That repeated facts fed to an LLM are memorized is well-established, so the paper does not motivate clearly why this should be a new phenomenon worth studying and not just a known property of LLMs applied to a different type of labels.
  • The recovery procedure under increased exposure (contribution 1, sec. 3.1) and the “black-box attack against graph-trained LLMs” (contribution 3, sec. 3.3) are the same thing, so the “attack” for example adds no inference step other than prompting the model the exact information it was trained on, which seems somewhat obvious.
  • The attack model itself seems quite limited, as it requires the attacker to know already the exact node set, the exact node tests that were used during training, and the training query template. I would see how some weaker versions of this might happen in practice but this is not really motivated in the paper, and the examples brought up (such as patient-related links) might be cases where the texts themselves are private. For example, one could test how robust the recovery is under imperfect specification, e.g. adding irrelevant nodes at attack time that do not occur in the exposed graph, or paraphrasing the node text and checking how stably the relations can still be recovered.
Questions for authors
  • In what sense do you think this memorization is intrinsically structural and not just memorization of independent relational facts, which would already be implied by ordinary LLM memorization, and would it be possible to design an experiment that distinguishes these?
  • More specifically, I wonder if the ability of an LLM to memorize edges is correlated with structural properties of the node pairs in the graph? The only analysis I found is in table 3 (edge betweenness), but this might be confounded by hub nodes being exposed more often to the LLM during the post-training stage. Or, can the model infer distances between nodes that are not connected? Or perhaps are there false positive edges predicted for triangle-closing pairs? Furthermore, does recoverability correlate with similarity of the node texts? It would also be interesting to see how recoverability works on heterophilous graphs, or on tasks where the text contents are not strongly predictive of edge existence. These would all help answer the question if there is anything interesting going on structually, rather than the model just memorizing a list of relations.
  • How does the attack behave when the query is paraphrased or in a different format?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.