acceptodds
Under review as a conference paper at ICLR 2027

Learning Substructure Regularities from Whole-Graph Sequences

Abstract

Autoregressive Transformers trained on whole graphs can reproduce substructure-level regularities without explicit substructure supervision. We investigate what this agreement reveals about substructure generalization, using PCQM4Mv2 as the main testbed. On PCQM4Mv2, under pure ancestral sampling, a Transformer trained on DFS-code serializations reproduces the support ranking of frequent training substructures, even after exact training-string matches are excluded. Finite-context -gram models also achieve substantial aggregate agreement, and on five small TUDataset benchmarks agreement coincides with replay, so this observation alone does not identify how substructures are generated. We therefore remove every training graph containing a specified target and retrain Transformers on an alternative serialization of node and edge additions. Under unconditional sampling, models generate structurally valid graphs containing withheld cyclic and acyclic targets across all three training seeds. The rare outputs containing a withheld carbon triangle are not labeled-isomorphic to any graph in the original, unfiltered training set and cannot be produced by generators restricted to recombining retained training fragments only through bridge connections. These results establish both support reproduction and the generation of specific structures absent from training, without identifying an internal mechanism or a general construction rule. Combining support evaluation, sequence baselines, and controlled target removal provides an empirical framework for characterizing observable substructure generalization and for future investigation of its underlying mechanisms.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
graph generation, autoregressive Transformers, graph serialization, subgraph statistics, substructure generalization

Reviews

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

The authors train autoregressive graph generation models specifically on whole molecular graphs. Their contribution broadly addresses capturing (and generating) substructures, and organises over two main parts. First they show that generated molecules contain common substructures at roughly the same empirical rates, but also that simpler baselines appear tp achieve this, thus not identifying how the model generates substructures. Second, they move to a setup where specific substructures are removed from the training dataset to check if they are then generated. The authors do it specifically for patterns C3 and P6, and find the retrained model still very occasionally produces them. This excludes, by construction, copying training data and, for C3, producing outputs by joining training fragments only through bridge bonds. Either way, the removal significantly, strongly suppresses both the selected targets.

Critical strengths
  • (S1) The experimental design is generally thorough. For example, the matched-removal condition separates the effect of removing the target from the effect of having less data, and the comparison against real-data resamples gives meaningful reference points.
  • (S2) The general methodology of holding out substructures and inspecting whether those are generated is interesting.
  • (S3) The paper is generally upfront about limitations.
Critical weaknesses
  • (W1) The presentation quality is, according to the reviewer, particularly poor, making the paper extremely difficult to follow and interpret. There is very little narrative in the paper that could guide readers understand the proposed contribution. The paper itself does not read a whole argument, rather as a storm of (quantitative) statements, unexpected acronyms and references to results and data with qualifications and caveats and not much interpretation. This makes it really hard for readers to identify potential relevant take home messages. Some issues worth flagging in particular:
    • The authors consistently use undefined or internal terminology, such as "DGMG-style", or "without establishing serialization invariance" even before the setup is introduced, or "not rule acquisition" without explanation, or, as a further example "headline DFS-code model".
    • Some results seem to be imported without explanation: for example, the paragraph at lines 149-157 mentions a value (bound?) of 0.0012 with an associated probability of at least 0.95 which is not clear where it comes from, or how it is derived. Then it moves to explain it "does not directly apply" to their data-selected panel?
    • Some passages are of unclear purpose: The above could already represent an example. On top of this, another example is the discussion of absorbing-state diffusion (lines 117 onwards) which introduces a theoretical link and right after it notes that the DiGress comparison does not test this.
  • (W2) The contributions and the motivation behind them are not clear. The paper generally frames the investigation around how autoregressive models generate substructures, starting from the observation, in the introduction, that "matching substructure frequencies does not itself show how a generator produces substructures" (lines 43-44). Based on this, the authors move to study the support of substructures in Section 4. However, it is not clear how such "support" can give a more informative measure, as it essentially seem to capture a similar measurement to frequency. Why should one expect a fidelity metric to inform on how a model generates its outputs in the first place, and why support could be a better metric w.r.t. say frequency? In fact, as the authors themselves write in line 156: "support agreement alone cannot identify how outputs are produced", so what is even the point of the whole Section 4? Its role in the argument is unclear, especially considering the conclusions seem to be vain anyway. If it is a methodology contribution, the paper should evaluate what it enables beyond existing metrics, for example.
  • (W3) The significance of results in Section 5, remain , to the reviewer, narrow.
    • For example, for C3, the experiment shows that the target-containing outputs are not copies of training graphs and could not be produced by joining training fragments only through bridge bonds. However, it remains unclear why anyone would hypothesise that the Transformer generates (subgraphs and then) graphs according to this approach? More plausible explanations remain open, as the authors acknowledge (lines 428 through 433), while still this pertains to only an extremely limited number of such C3 patterns found to be generated, so that it would be difficult, anyway, to extrapolate general pattern formation rules.
    • Still on C3, as this is made entirely absent from the withheld training sets, a model that perfectly fits its training distribution would never emit it. So this entails that it is not obvious whether emission at such extremely low rates are to be interpreted as generalisation or simply "model error".
  • (W4) The scope is generally limited: the main results are supported on one dataset only, PCQM4Mv2, on a non-official split (whose motivation is not given), and only two particular target substructures.
Questions for authors
  • (Q1) The paper emphasises that models are trained "without explicit substructure supervision". However, next-token prediction trains on prefixes that correspond to partial graphs. This could in fact give some signal on substructures similarly to how next token prediction provides signal also on grammar and words other than whole sentences. Could the authors clarify in what sense substructures are unsupervised?

Also please see (W2) and (W3).

5 comments
AuthorsOpenReview ↗

Response to All Reviewers (Part 1/2) — What This Paper Shows

We thank all reviewers. Since all three reviews pointed out that the paper's contribution was difficult to identify, we begin by restating our main contributions to address this shared concern.

By analogy with language models, substructures correspond to phrases, and graph validity corresponds to grammar. In our results, n-gram models also reproduced substructures, the analogue of phrases, quite well. A major difference between the Transformer and n-gram models was in the aspect corresponding to grammar.

Summary. The Transformer generates a carbon triangle withheld from training, like n-gram models, while preserving whole-graph validity, like a generator that recombines training-graph fragments. Each simple generator we evaluated shows only one of these two behaviors.

In the following, “†” indicates experimental results obtained after submission; all of these results are included in the revised version (Appendix L).

1. Transformer-generated graphs reproduce substructure frequencies at the level observed in real data. A simple generator can also reproduce these frequencies with similar accuracy.

In Transformer-generated graphs, the support of 253 frequent substructures deviates from the support in the training graphs by 0.0112 on average, after removing outputs whose strings exactly match training strings. The mean deviation from training-graph support is 0.0121 for held-out samples and 0.0138 for a generator that only recombines training-graph fragments. The errors of 3-gram and 5-gram models are 2–4 times larger (all results in Table 1). The role of §4 (Observation: Generated Graphs Reproduce Substructure Support) is to use this comparison to explain why the removal experiments in §5 (Test: Generating Targets Withheld from Training) are needed.

2. Structures withheld from training become much rarer in Transformer outputs. Even so, the Transformer generates new graphs containing the withheld structures.

When we remove all training graphs containing a target pattern and retrain, target occurrences are reduced relative to the control by a factor of 430–3,000† for carbon triangles and approximately 10 for carbon chains (Figure 2, Table 20; Table 24). Nevertheless, every model trained after target removal generates its target. Under the sampling procedure in §5 (Test: Generating Targets Withheld from Training), none of the 107† outputs containing a triangle is labeled-isomorphic to any original training graph (Table 18; Appendix L.1). We also show separately that recombining training-graph fragments only through bridges, as our fragment generator does, cannot create a carbon triangle (Lemma 5).

3. Local token statistics remain a possible explanation of how the withheld triangle is generated.

N-gram models also generate triangles withheld from training (§5.3, Table 21). Based on differences in the numbers of triangles generated by the Transformer and n-gram models, the submitted paper stated that the Transformer suppresses them far more strongly than local token statistics do (§7; see also §5.3). However, when we compare how much removing target-containing training graphs reduces the probability of the same triangle-closing step, the Transformer's suppression (3.66 nats) does not exceed that of a model using only the preceding 7 tokens (3.87 nats)†. We tested only whether the Transformer's suppression was more than twofold stronger in probability than the local model's; we did not establish equal suppression in the 2 models. We have clarified the meaning of this comparison in the revision (§5.3, §7).

4. A major difference between the Transformer and n-gram models is whole-graph validity.

The Transformer produces valid graphs in 97.5–97.9% of attempts†. An 8-gram model trained on the same data produces valid graphs in 25.1% of attempts†. Most n-gram failures involve 2 types of rule violations: (1) adding an edge whose destination is not an earlier node and (2) producing a disconnected graph. The frequency comparison in Table 1 uses only valid outputs (§3.3). Thus, frequency agreement alone does not imply that a generator can produce valid whole graphs.

Remaining question. The internal mechanism is not yet identified. Points 3 and 4 give two clues, but how the Transformer generates the withheld triangle and preserves whole-graph validity remains unknown.

  • The “factor of 430–3,000 reduction” and “107 outputs” for triangles include 3 training seeds added after submission (Appendix L.1). The submitted paper reported a factor of 430–800 reduction and 65 outputs.
  • The comparison at the same generation step in point 3, and the valid-graph rates and 2 rules in point 4, are post-submission analyses.
AuthorsOpenReview ↗

The tables are in the response to all reviewers (Part 2/2).

We substantially revised the exposition in response to the concerns about clarity: we rewrote the text in plain sentences and moved procedural details to the appendix. The research question, the data, the experiments and the results of the submitted version are unchanged. We summarize the additional experiments below; the change to the scope of our claims is described in point 3 of Part 1/2.

The following includes results from additional experiments conducted after submission. All of these results are included in the revised version (Appendix L; Tables A, B and C correspond to Tables 24, 25 and 26 in the revised manuscript).

Table A. Target Occurrences After Target Removal (5 Targets)

Each value is the ratio of the target-occurrence count from a model trained after removing target-containing training graphs to the target-occurrence count in the matched-removal control (§5.1). The training and sampling settings are the same as in §5, with 163,840 attempts per model.

TargetTraining graphs removed: count (percentage)Transformer (by training seed)Exact-count 8-gram
Triangle C3193,874 (5.7%)0.13%, 0.19%, 0.23% / additional seeds: 0.03%, 0.13%, 0.21%21% [18, 24]
6-membered ring C6217,136 (6.4%)2.02%, 2.10%, 1.80%24% [18, 31]
5-membered ring C5145,699 (4.3%)2.74%, 3.32%, 2.80%50% [42, 60]
Chain P6178,620 (5.3%)10.6%, 10.0%, 10.1%86% [78, 95]
Chain P788,401 (2.6%)10.89%, 9.58%, 9.34%83% [70, 99]

The first 3 Transformer values and the 8-gram value for triangles, and the values in the P6 row, were reported in the submitted paper (§5.2 and §5.3; Tables 17, 20 and 21). Intervals were calculated using the same method as in Table 20. The targets differ in frequency, size, and the graphs removed. The ordering of the ratios is therefore an observation, not an explanation of its cause.

Table B. Comparison at the Same Generation Step (Triangles)

The values show how much removing target-containing training graphs reduces the probability of a triangle-closing step (mean change in log probability, in nats; model trained after target removal minus control; ratios capped at 100-fold; brackets indicate nominal 95% intervals across training seeds and states). A value of −2.3 corresponds to reducing this probability to 1/10 of the control probability.

StateNumber of statesTransformerModel using only the preceding 7 tokensDifference (Transformer − local model)
Triangles closed among 3 vertices with nonconsecutive indices1,102−3.66 [−3.74, −3.58]−3.87 [−3.95, −3.79]+0.21 [+0.12, +0.30]
Of these, cases where the 3rd edge is at least 9 tokens earlier398−3.76 [−3.88, −3.63]−3.78 [−3.91, −3.64]+0.02 [−0.13, +0.18]
Distant closures reached by the 8-gram generator674−1.49 [−1.69, −1.30]−1.44 [−1.61, −1.29]−0.05 [−0.24, +0.15]
Triangles retained in training2,000−0.03 [−0.16, +0.11]0.00 [−0.01, 0.00]−0.03 [−0.16, +0.11]

We specified how to interpret the results before evaluation. For the probability of a triangle-closing step, the decrease under the Transformer does not exceed that under the local model by a factor of 2 or more. This is a one-sided test and does not establish equal suppression in the 2 models. Of the 10 local models examined, this result holds in comparisons with 8 models over all states and 7 models over distant states.

Table C. Valid-Graph Rates and Violated Rules

All values are percentages of all attempts. Every generator was trained on the control training data and evaluated for 163,840 attempts using the same sampling procedure as in §5.

GeneratorValid-graph rateEdge destination is not an earlier nodeGenerated graph is disconnected
Transformer (6 training seeds)97.5–97.9%0.1–0.2%1.7–2.2%
8-gram25.1%34.3%40.6%
5-gram3.3%83.2%13.4%
3-gram0.7%98.6%0.65%

No n-gram attempt was classified as a token-ordering error (each invalid attempt is counted under the first rule it breaks). This table shows the rules violated by the generated graphs.

Other Additional Results

  • Untruncated sampling. Every model trained after removing triangles or P6 generates its target. The ratios of target-occurrence counts, summed over the 3 training seeds, to those in the control are 0.55% [0.47, 0.64] for triangles and 14.8% [14.3, 15.3] for P6.
  • DFS code. The ratios of triangle-occurrence counts to those in the control are 0.95%, 0.92%, and 1.01% (DFS codes and training recipe of §4, decoder of §5). Because this experiment uses different settings from §5, we do not attribute the difference between the values to serialization.
AuthorsOpenReview ↗

Response to Reviewer RZAJ

Thank you for the detailed review. Following our response to all reviewers, we address your individual comments below.

In the following, “†” indicates experimental results obtained after submission. All of these results are included in the revised version (Appendix L). The tables are in the response to all reviewers (Part 2/2).

W1 (Presentation)

We agree with your assessment. In the revision, each of the three experimental sections (§4, §5 and §6) opens with its question and closes with the findings. We have addressed the 3 points you raised as follows.

  1. Undefined terminology. We replaced “DGMG-style” with “sequences that add nodes and edges one at a time,” and “headline DFS-code model” with “the DFS-code model of Section 4.” We replaced “serialization invariance” and “rule acquisition” with plain-language statements.
  2. The value 0.0012. This value quantifies the degree of support agreement for a generator that simply replays training graphs. We derived it from Hoeffding’s inequality and a union bound (253 patterns and 3,371,958 training graphs; the derivation is in the appendix). The main text now explains this in one sentence (§3.1).
  3. We removed the paragraph on diffusion models because it is unnecessary for presenting the paper’s main results.

W2 (What support means and the purpose of §4)

Support is the proportion of graphs that contain a given substructure.

The purpose of §4 is to explain why the target-removal experiments in §5 are needed. Even a generator that simply recombines training-graph fragments can reproduce substructure frequencies with accuracy close to that of the Transformer (Table 1). As you point out, agreement in frequencies does not reveal how a model generates graphs. The opening paragraph of §4 now states this purpose.

W3 (The significance of §5)

§5 shows that the Transformer generates structures withheld from training, as n-gram models do.

  1. Why we examined fragment recombination. We chose this generator because it reproduced substructure frequencies with accuracy close to that of the Transformer in §4. This generator cannot produce the withheld triangle (Lemma 5), whereas the Transformer can (Table 18).
  2. A more plausible explanation. Local token statistics remain a possible explanation of the model’s decisions concerning triangles. After submission, we directly examined the relationship between those decisions and local token statistics (point 3 of the response to all reviewers; Table B)†.
  3. Generalization or model error. In language-model terms, the generation of structures withheld from training is analogous to creating an unseen phrase from familiar word sequences. N-gram models, which use only a short token context, also generate withheld structures (§5.3, Table 21). The Transformer generates them while maintaining the validity of the graph as a whole (Table C)†.

W4 (Scope)

We expanded the number of targets from 2 to 5 and the number of training seeds for triangles from 3 to 6 (Table A)†. For all 5 targets, removing training graphs that contain the target greatly reduces its occurrence in Transformer outputs, but every model trained on the remaining data still generates the target.

We used a random split to sample held-out molecules from the same distribution as the training molecules. In §4, we use held-out samples of the same size as a reference.

Testing on other corpora is a next step.

Q1 (What does “without explicit substructure supervision” mean?)

We mean that model training uses no substructure labels, fragment vocabulary, or substructure-specific loss. As you point out, next-token prediction exposes the model to partial graphs, just as a language model receives signals about words and grammar from sentences. In this analogy, n-gram models also reproduced substructure statistics quite well; these substructures correspond to phrases. A major difference between the Transformer and n-gram models is the validity of the graph as a whole, which corresponds to grammar.

† These results were added after submission. The tables are in the response to all reviewers (Part 2/2).

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

This paper investigates whether autoregressive Transformers trained on whole-graph sequences can learn substructure regularities. The authors evaluate substructure frequency matching, introduce target-removal experiments to test the generation of unseen substructures, and examine the relationship between likelihood and substructure statistics.

Critical strengths

The target-removal setup is a useful way to probe substructure generalization. The paper also includes several relevant controls, including matched removal, fragment recombination, and n-gram baselines.

Critical weaknesses

1. The main results provide weak evidence for meaningful substructure generalization.

After removing all training graphs containing C3, the Transformer generates only 15–28 hits out of 163,840 samples, a 430–800× reduction relative to matched-removal controls. More importantly, simple n-gram models can also generate the withheld structure. It is therefore unclear what these results demonstrate beyond what can already be explained by local token statistics.

2. The paper lacks a clear, substantive contribution.

The two main findings—matching substructure frequencies and generating withheld substructures—can both be reproduced, at least qualitatively, by simple baselines. Despite extensive experiments, the paper offers little insight into what structural regularities the Transformer actually learns. The use of different serializations and sampling strategies across the main experiments further weakens the overall narrative.

Questions for authors
  1. What does the Transformer demonstrate beyond the capabilities of the n-gram baselines?
  2. Given the extremely low hit rates after target removal, what justifies interpreting these results as meaningful substructure generalization?
5 comments
AuthorsOpenReview ↗

Response to All Reviewers (Part 1/2) — What This Paper Shows

We thank all reviewers. Since all three reviews pointed out that the paper's contribution was difficult to identify, we begin by restating our main contributions to address this shared concern.

By analogy with language models, substructures correspond to phrases, and graph validity corresponds to grammar. In our results, n-gram models also reproduced substructures, the analogue of phrases, quite well. A major difference between the Transformer and n-gram models was in the aspect corresponding to grammar.

Summary. The Transformer generates a carbon triangle withheld from training, like n-gram models, while preserving whole-graph validity, like a generator that recombines training-graph fragments. Each simple generator we evaluated shows only one of these two behaviors.

In the following, “†” indicates experimental results obtained after submission; all of these results are included in the revised version (Appendix L).

1. Transformer-generated graphs reproduce substructure frequencies at the level observed in real data. A simple generator can also reproduce these frequencies with similar accuracy.

In Transformer-generated graphs, the support of 253 frequent substructures deviates from the support in the training graphs by 0.0112 on average, after removing outputs whose strings exactly match training strings. The mean deviation from training-graph support is 0.0121 for held-out samples and 0.0138 for a generator that only recombines training-graph fragments. The errors of 3-gram and 5-gram models are 2–4 times larger (all results in Table 1). The role of §4 (Observation: Generated Graphs Reproduce Substructure Support) is to use this comparison to explain why the removal experiments in §5 (Test: Generating Targets Withheld from Training) are needed.

2. Structures withheld from training become much rarer in Transformer outputs. Even so, the Transformer generates new graphs containing the withheld structures.

When we remove all training graphs containing a target pattern and retrain, target occurrences are reduced relative to the control by a factor of 430–3,000† for carbon triangles and approximately 10 for carbon chains (Figure 2, Table 20; Table 24). Nevertheless, every model trained after target removal generates its target. Under the sampling procedure in §5 (Test: Generating Targets Withheld from Training), none of the 107† outputs containing a triangle is labeled-isomorphic to any original training graph (Table 18; Appendix L.1). We also show separately that recombining training-graph fragments only through bridges, as our fragment generator does, cannot create a carbon triangle (Lemma 5).

3. Local token statistics remain a possible explanation of how the withheld triangle is generated.

N-gram models also generate triangles withheld from training (§5.3, Table 21). Based on differences in the numbers of triangles generated by the Transformer and n-gram models, the submitted paper stated that the Transformer suppresses them far more strongly than local token statistics do (§7; see also §5.3). However, when we compare how much removing target-containing training graphs reduces the probability of the same triangle-closing step, the Transformer's suppression (3.66 nats) does not exceed that of a model using only the preceding 7 tokens (3.87 nats)†. We tested only whether the Transformer's suppression was more than twofold stronger in probability than the local model's; we did not establish equal suppression in the 2 models. We have clarified the meaning of this comparison in the revision (§5.3, §7).

4. A major difference between the Transformer and n-gram models is whole-graph validity.

The Transformer produces valid graphs in 97.5–97.9% of attempts†. An 8-gram model trained on the same data produces valid graphs in 25.1% of attempts†. Most n-gram failures involve 2 types of rule violations: (1) adding an edge whose destination is not an earlier node and (2) producing a disconnected graph. The frequency comparison in Table 1 uses only valid outputs (§3.3). Thus, frequency agreement alone does not imply that a generator can produce valid whole graphs.

Remaining question. The internal mechanism is not yet identified. Points 3 and 4 give two clues, but how the Transformer generates the withheld triangle and preserves whole-graph validity remains unknown.

  • The “factor of 430–3,000 reduction” and “107 outputs” for triangles include 3 training seeds added after submission (Appendix L.1). The submitted paper reported a factor of 430–800 reduction and 65 outputs.
  • The comparison at the same generation step in point 3, and the valid-graph rates and 2 rules in point 4, are post-submission analyses.
AuthorsOpenReview ↗

The tables are in the response to all reviewers (Part 2/2).

We substantially revised the exposition in response to the concerns about clarity: we rewrote the text in plain sentences and moved procedural details to the appendix. The research question, the data, the experiments and the results of the submitted version are unchanged. We summarize the additional experiments below; the change to the scope of our claims is described in point 3 of Part 1/2.

The following includes results from additional experiments conducted after submission. All of these results are included in the revised version (Appendix L; Tables A, B and C correspond to Tables 24, 25 and 26 in the revised manuscript).

Table A. Target Occurrences After Target Removal (5 Targets)

Each value is the ratio of the target-occurrence count from a model trained after removing target-containing training graphs to the target-occurrence count in the matched-removal control (§5.1). The training and sampling settings are the same as in §5, with 163,840 attempts per model.

TargetTraining graphs removed: count (percentage)Transformer (by training seed)Exact-count 8-gram
Triangle C3193,874 (5.7%)0.13%, 0.19%, 0.23% / additional seeds: 0.03%, 0.13%, 0.21%21% [18, 24]
6-membered ring C6217,136 (6.4%)2.02%, 2.10%, 1.80%24% [18, 31]
5-membered ring C5145,699 (4.3%)2.74%, 3.32%, 2.80%50% [42, 60]
Chain P6178,620 (5.3%)10.6%, 10.0%, 10.1%86% [78, 95]
Chain P788,401 (2.6%)10.89%, 9.58%, 9.34%83% [70, 99]

The first 3 Transformer values and the 8-gram value for triangles, and the values in the P6 row, were reported in the submitted paper (§5.2 and §5.3; Tables 17, 20 and 21). Intervals were calculated using the same method as in Table 20. The targets differ in frequency, size, and the graphs removed. The ordering of the ratios is therefore an observation, not an explanation of its cause.

Table B. Comparison at the Same Generation Step (Triangles)

The values show how much removing target-containing training graphs reduces the probability of a triangle-closing step (mean change in log probability, in nats; model trained after target removal minus control; ratios capped at 100-fold; brackets indicate nominal 95% intervals across training seeds and states). A value of −2.3 corresponds to reducing this probability to 1/10 of the control probability.

StateNumber of statesTransformerModel using only the preceding 7 tokensDifference (Transformer − local model)
Triangles closed among 3 vertices with nonconsecutive indices1,102−3.66 [−3.74, −3.58]−3.87 [−3.95, −3.79]+0.21 [+0.12, +0.30]
Of these, cases where the 3rd edge is at least 9 tokens earlier398−3.76 [−3.88, −3.63]−3.78 [−3.91, −3.64]+0.02 [−0.13, +0.18]
Distant closures reached by the 8-gram generator674−1.49 [−1.69, −1.30]−1.44 [−1.61, −1.29]−0.05 [−0.24, +0.15]
Triangles retained in training2,000−0.03 [−0.16, +0.11]0.00 [−0.01, 0.00]−0.03 [−0.16, +0.11]

We specified how to interpret the results before evaluation. For the probability of a triangle-closing step, the decrease under the Transformer does not exceed that under the local model by a factor of 2 or more. This is a one-sided test and does not establish equal suppression in the 2 models. Of the 10 local models examined, this result holds in comparisons with 8 models over all states and 7 models over distant states.

Table C. Valid-Graph Rates and Violated Rules

All values are percentages of all attempts. Every generator was trained on the control training data and evaluated for 163,840 attempts using the same sampling procedure as in §5.

GeneratorValid-graph rateEdge destination is not an earlier nodeGenerated graph is disconnected
Transformer (6 training seeds)97.5–97.9%0.1–0.2%1.7–2.2%
8-gram25.1%34.3%40.6%
5-gram3.3%83.2%13.4%
3-gram0.7%98.6%0.65%

No n-gram attempt was classified as a token-ordering error (each invalid attempt is counted under the first rule it breaks). This table shows the rules violated by the generated graphs.

Other Additional Results

  • Untruncated sampling. Every model trained after removing triangles or P6 generates its target. The ratios of target-occurrence counts, summed over the 3 training seeds, to those in the control are 0.55% [0.47, 0.64] for triangles and 14.8% [14.3, 15.3] for P6.
  • DFS code. The ratios of triangle-occurrence counts to those in the control are 0.95%, 0.92%, and 1.01% (DFS codes and training recipe of §4, decoder of §5). Because this experiment uses different settings from §5, we do not attribute the difference between the values to serialization.
AuthorsOpenReview ↗

Response to Reviewer L5Lb

Thank you. Following our response to all reviewers, we address your individual comments below.

In the following, “†” indicates experimental results obtained after submission. All of these results are included in the revised version (Appendix L). The tables are in the response to all reviewers (Part 2/2).

Q1 (What does the Transformer demonstrate beyond n-gram models?)

A major difference between the Transformer and n-gram models is the validity of the whole generated graph. The Transformer produces valid graphs in 97.5–97.9% of attempts. For 8-gram, 5-gram, and 3-gram models trained on the same data, the corresponding rates are 25.1%, 3.3%, and 0.7%, respectively (Table C)†.

Local token statistics remain a possible explanation of the model’s triangle-closing decisions. When we compare how much removing training graphs containing triangles reduces the probability of the same triangle-closing step, suppression in the Transformer (3.66 nats) does not exceed that in the model that uses only the preceding 7 tokens (3.87 nats; Table B)†. We have revised the discussion in §5.3 and §7 to reflect this result.

Q2 (Why call this “meaningful generalization” when occurrence rates are so low?)

The significance lies in the following 3 points, rather than in a high occurrence rate.

  1. For each of the 5 targets, every model trained after removing training graphs containing that target generates the target (Table A).
  2. All 107† triangle-containing outputs obtained with the sampling procedure in §5 are new graphs (Table 18; added seeds in Appendix L.1).
  3. Recombining training-graph fragments only through bridges cannot create carbon triangles (Lemma 5).

In language-model terms, this is analogous to producing an unseen phrase from familiar word sequences. We use “substructure generalization” to name the generation of a specified substructure removed from all training graphs (§1). The revision states this definition where the term first appears (abstract and §1).

W1 and W2 (Both findings can be reproduced by simple baselines; lack of contribution)

The Transformer combines 2 properties that the simple generators each possess separately. The generator that recombines training-graph fragments reproduces substructure frequencies with accuracy close to that of the Transformer (Table 1), but cannot create rings absent from its fragments (Lemma 5). N-gram models create rings (Table 21), but their valid-graph rate is at most about 25% (Table 21; Table C†).

The Transformer generates a carbon triangle withheld from training, as n-gram models do, while maintaining the validity of the whole graph. This is the contribution of our paper.

Serialization and sampling

The finding that removing training graphs containing a target greatly reduces its occurrence, yet the target is still generated, holds when we change serialization and sampling. With DFS-code serialization and the training recipe of §4, training after removing graphs containing triangles gives triangle-occurrence counts that are 0.92–1.01% of those in the control†. Using untruncated sampling with the serialization in §5 gives a ratio of 0.55%†. In both settings, every model trained after removing training graphs containing triangles generates triangles.

† Results added after submission. The tables are in the response to all reviewers (Part 2/2).

Reviewer_SCK7OpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper tries to understand how autoregressive graph generators based on whole graph canonizations reproduce (or not) the frequency/support of substructures, even those subgraphs were not explicitly "given" as substructures to reproduce. It uses the well known molecular data set PCQM4Mv2 converted with a DFS-code serialization and LLaMA decoders to investigate how empirical generation contains some substructures, combined with a targeted removal of some specific substructures (C_3 and P_6 subgraphs) to check if without them on the training data they would still be generated.

The empirical results show that (with high confidence) the frequent structures appear on the generated graphs, including when they remove from the output exact strings that were on the training data (and the authors also compare to two non-neural generators, with the bridge-only model achieving comparable agreement). When removing the two target substructures from the training data set, the graphs generated present several order of magnitude supression on the subgraphs expresion (particulary on C_3), but still present it and with "novel" non labeled isomorphic occurrences (while they show that bridge-only recombinations cannot reproduce C3 - see Lemma 5).

Critical strengths
  • The empirical test framework and design is thorough well thought (including aspects such as the target removal and the novelty isomorphism check of the found substructures)

  • Usage of controls and baseline to check how results can be read and what they show (e.g. usage of non neural baselines that can sometimes reach similar agreement with much simpler and interpretable mechanisms)

Critical weaknesses
  • There are limited informative conclusions and the papers reads more as an empirical diagnosis concentrated on a single graph dataset and on two particular substructures, rather than providing definitive insight.

  • A very dense presentation relying on over 20 pages of annexes to support the main paper that make the reader have to go back and forth to understand what's happening (with many central claims having been somehow pushed out of the main text).

Questions for authors
  • Can you provide more details on how close the generated C_3 occurrences on section 5 are when compared to the original C_3 suuport dataset before removing those targets? We know that they are not labeled-isomorphic, but they could still be very close (something like graph edit distance or another measure of graph distance), and you state that 10 out of 65 hits are one change away (but what about the others). And can you provide like a distribution of the generated C_3 subgraphs, bot on topology and where they occur on the graph? (are they "concentrated" and close to each other?)

  • Did you check the neighboring structures of the C_3 and P_6 occurrences, to understand if the creations are driven by those neighborhood patterns?

  • Did you try the target removal approach with subgraphs other than C_3 and P_6? Since C_3 is much more supressed than P_6, I would like to understand if you tried to gain insight on why this happens and tested with a larger "vocabulary" of subgraphs to understand how aspects such as the topology and original frequency affect the results. How would you design such an experiment if you had the time and what would you look for?

3 comments
AuthorsOpenReview ↗

Response to All Reviewers (Part 1/2) — What This Paper Shows

We thank all reviewers. Since all three reviews pointed out that the paper's contribution was difficult to identify, we begin by restating our main contributions to address this shared concern.

By analogy with language models, substructures correspond to phrases, and graph validity corresponds to grammar. In our results, n-gram models also reproduced substructures, the analogue of phrases, quite well. A major difference between the Transformer and n-gram models was in the aspect corresponding to grammar.

Summary. The Transformer generates a carbon triangle withheld from training, like n-gram models, while preserving whole-graph validity, like a generator that recombines training-graph fragments. Each simple generator we evaluated shows only one of these two behaviors.

In the following, “†” indicates experimental results obtained after submission; all of these results are included in the revised version (Appendix L).

1. Transformer-generated graphs reproduce substructure frequencies at the level observed in real data. A simple generator can also reproduce these frequencies with similar accuracy.

In Transformer-generated graphs, the support of 253 frequent substructures deviates from the support in the training graphs by 0.0112 on average, after removing outputs whose strings exactly match training strings. The mean deviation from training-graph support is 0.0121 for held-out samples and 0.0138 for a generator that only recombines training-graph fragments. The errors of 3-gram and 5-gram models are 2–4 times larger (all results in Table 1). The role of §4 (Observation: Generated Graphs Reproduce Substructure Support) is to use this comparison to explain why the removal experiments in §5 (Test: Generating Targets Withheld from Training) are needed.

2. Structures withheld from training become much rarer in Transformer outputs. Even so, the Transformer generates new graphs containing the withheld structures.

When we remove all training graphs containing a target pattern and retrain, target occurrences are reduced relative to the control by a factor of 430–3,000† for carbon triangles and approximately 10 for carbon chains (Figure 2, Table 20; Table 24). Nevertheless, every model trained after target removal generates its target. Under the sampling procedure in §5 (Test: Generating Targets Withheld from Training), none of the 107† outputs containing a triangle is labeled-isomorphic to any original training graph (Table 18; Appendix L.1). We also show separately that recombining training-graph fragments only through bridges, as our fragment generator does, cannot create a carbon triangle (Lemma 5).

3. Local token statistics remain a possible explanation of how the withheld triangle is generated.

N-gram models also generate triangles withheld from training (§5.3, Table 21). Based on differences in the numbers of triangles generated by the Transformer and n-gram models, the submitted paper stated that the Transformer suppresses them far more strongly than local token statistics do (§7; see also §5.3). However, when we compare how much removing target-containing training graphs reduces the probability of the same triangle-closing step, the Transformer's suppression (3.66 nats) does not exceed that of a model using only the preceding 7 tokens (3.87 nats)†. We tested only whether the Transformer's suppression was more than twofold stronger in probability than the local model's; we did not establish equal suppression in the 2 models. We have clarified the meaning of this comparison in the revision (§5.3, §7).

4. A major difference between the Transformer and n-gram models is whole-graph validity.

The Transformer produces valid graphs in 97.5–97.9% of attempts†. An 8-gram model trained on the same data produces valid graphs in 25.1% of attempts†. Most n-gram failures involve 2 types of rule violations: (1) adding an edge whose destination is not an earlier node and (2) producing a disconnected graph. The frequency comparison in Table 1 uses only valid outputs (§3.3). Thus, frequency agreement alone does not imply that a generator can produce valid whole graphs.

Remaining question. The internal mechanism is not yet identified. Points 3 and 4 give two clues, but how the Transformer generates the withheld triangle and preserves whole-graph validity remains unknown.

  • The “factor of 430–3,000 reduction” and “107 outputs” for triangles include 3 training seeds added after submission (Appendix L.1). The submitted paper reported a factor of 430–800 reduction and 65 outputs.
  • The comparison at the same generation step in point 3, and the valid-graph rates and 2 rules in point 4, are post-submission analyses.
AuthorsOpenReview ↗

The tables are in the response to all reviewers (Part 2/2).

We substantially revised the exposition in response to the concerns about clarity: we rewrote the text in plain sentences and moved procedural details to the appendix. The research question, the data, the experiments and the results of the submitted version are unchanged. We summarize the additional experiments below; the change to the scope of our claims is described in point 3 of Part 1/2.

The following includes results from additional experiments conducted after submission. All of these results are included in the revised version (Appendix L; Tables A, B and C correspond to Tables 24, 25 and 26 in the revised manuscript).

Table A. Target Occurrences After Target Removal (5 Targets)

Each value is the ratio of the target-occurrence count from a model trained after removing target-containing training graphs to the target-occurrence count in the matched-removal control (§5.1). The training and sampling settings are the same as in §5, with 163,840 attempts per model.

TargetTraining graphs removed: count (percentage)Transformer (by training seed)Exact-count 8-gram
Triangle C3193,874 (5.7%)0.13%, 0.19%, 0.23% / additional seeds: 0.03%, 0.13%, 0.21%21% [18, 24]
6-membered ring C6217,136 (6.4%)2.02%, 2.10%, 1.80%24% [18, 31]
5-membered ring C5145,699 (4.3%)2.74%, 3.32%, 2.80%50% [42, 60]
Chain P6178,620 (5.3%)10.6%, 10.0%, 10.1%86% [78, 95]
Chain P788,401 (2.6%)10.89%, 9.58%, 9.34%83% [70, 99]

The first 3 Transformer values and the 8-gram value for triangles, and the values in the P6 row, were reported in the submitted paper (§5.2 and §5.3; Tables 17, 20 and 21). Intervals were calculated using the same method as in Table 20. The targets differ in frequency, size, and the graphs removed. The ordering of the ratios is therefore an observation, not an explanation of its cause.

Table B. Comparison at the Same Generation Step (Triangles)

The values show how much removing target-containing training graphs reduces the probability of a triangle-closing step (mean change in log probability, in nats; model trained after target removal minus control; ratios capped at 100-fold; brackets indicate nominal 95% intervals across training seeds and states). A value of −2.3 corresponds to reducing this probability to 1/10 of the control probability.

StateNumber of statesTransformerModel using only the preceding 7 tokensDifference (Transformer − local model)
Triangles closed among 3 vertices with nonconsecutive indices1,102−3.66 [−3.74, −3.58]−3.87 [−3.95, −3.79]+0.21 [+0.12, +0.30]
Of these, cases where the 3rd edge is at least 9 tokens earlier398−3.76 [−3.88, −3.63]−3.78 [−3.91, −3.64]+0.02 [−0.13, +0.18]
Distant closures reached by the 8-gram generator674−1.49 [−1.69, −1.30]−1.44 [−1.61, −1.29]−0.05 [−0.24, +0.15]
Triangles retained in training2,000−0.03 [−0.16, +0.11]0.00 [−0.01, 0.00]−0.03 [−0.16, +0.11]

We specified how to interpret the results before evaluation. For the probability of a triangle-closing step, the decrease under the Transformer does not exceed that under the local model by a factor of 2 or more. This is a one-sided test and does not establish equal suppression in the 2 models. Of the 10 local models examined, this result holds in comparisons with 8 models over all states and 7 models over distant states.

Table C. Valid-Graph Rates and Violated Rules

All values are percentages of all attempts. Every generator was trained on the control training data and evaluated for 163,840 attempts using the same sampling procedure as in §5.

GeneratorValid-graph rateEdge destination is not an earlier nodeGenerated graph is disconnected
Transformer (6 training seeds)97.5–97.9%0.1–0.2%1.7–2.2%
8-gram25.1%34.3%40.6%
5-gram3.3%83.2%13.4%
3-gram0.7%98.6%0.65%

No n-gram attempt was classified as a token-ordering error (each invalid attempt is counted under the first rule it breaks). This table shows the rules violated by the generated graphs.

Other Additional Results

  • Untruncated sampling. Every model trained after removing triangles or P6 generates its target. The ratios of target-occurrence counts, summed over the 3 training seeds, to those in the control are 0.55% [0.47, 0.64] for triangles and 14.8% [14.3, 15.3] for P6.
  • DFS code. The ratios of triangle-occurrence counts to those in the control are 0.95%, 0.92%, and 1.01% (DFS codes and training recipe of §4, decoder of §5). Because this experiment uses different settings from §5, we do not attribute the difference between the values to serialization.
AuthorsOpenReview ↗

Response to SCK7

Thank you for your careful reading. Your questions have helped us clarify our contributions. Following our response to all reviewers, we address your individual comments below.

In the following, “†” indicates experimental results obtained after submission. All of these results are included in the revised version (Appendix L). The tables are in the response to all reviewers (Part 2/2).

W1 (Limited conclusions, 1 dataset, and 2 targets)

We have restated our conclusion in one sentence: the Transformer generates a carbon triangle withheld from training, as n-gram models do, while maintaining the validity of the whole graph.

We have also broadened the experiments. We increased the number of targets from 2 to 5 and the number of training seeds for triangles from 3 to 6†. For all 5 targets, removing training graphs containing the target greatly reduces its occurrence in Transformer outputs, yet every model trained on the remaining data generates the target (Table A). Testing on other corpora is a next step.

W2 (Dense presentation and reliance on appendices)

We agree. In the revision, each of the three experimental sections (§4, §5 and §6) opens with its question and ends with what we found. The main comparisons, including the added ones, are now in the main text (§5.2, §5.3 and the new Figure 3).

Q1 (How close are the generated triangles to the original data containing triangles?)

The original 3 models generated 65 triangle-containing graphs, all of which are new graphs. None is labeled-isomorphic to any of the original 3,371,958 training graphs, including those removed from training (Table 18).

Of these generated graphs, 10 can be obtained with 1 change to a training graph (Appendix J, Table 22). Adding the removed molecules to the comparison set leaves this count at 10 (Table 22).

We measured fingerprint similarity for the 55 of the 65 generated graphs that RDKit could read as molecules. The mean similarity between each generated molecule and its closest training molecule is 0.45†. Adding the removed molecules to the comparison set increases this mean to 0.48; in 19 cases, the closest molecule is one that was removed from training†.

Each of the 65 generated graphs contains exactly 1 carbon triangle†.

Q2 (Do nearby structures influence generation?)

Possibly. Our results do not rule out that nearby patterns in the sequence explain triangle generation. Removing training graphs containing triangles reduces the probability of the triangle-closing step in the model that uses only the preceding 7 tokens (3.87 nats), and the reduction in the Transformer (3.66 nats) does not exceed it (Table B)†. Here, “nearby” refers to the immediately preceding tokens in the sequence.

Q3 (Other targets, why triangles are strongly suppressed, and experimental design)

We added 5-membered rings, 6-membered rings, and chains of 7 carbon atoms as targets (Table A)†. For every training seed, removing training graphs containing the target suppresses the occurrence of the 3 types of rings more strongly than that of the 2 types of chains.

This ordering of suppression strengths also appears in local token statistics. The exact-count 8-gram gives lower ratios for the 3 rings than for the 2 chains (target-occurrence counts relative to the control: triangles, 21%; 6-membered rings, 24%; 5-membered rings, 50%; and chains, 83% and 86%)†.

There is one more clue to why triangles are strongly suppressed. Of the triangle-containing outputs of the control models, 95–96% close the triangle on 3 consecutively numbered vertices. Removing training graphs containing triangles nearly eliminates generation through this type of closure (1, 1, and 2 outputs in the original 3 models)†.

How would you design such an experiment if you had the time and what would you look for?

If we had the time, we would select targets with different topologies and sizes within a matched frequency range, and look at whether suppression strength varies with topology, frequency, or the length of the token sequence required to complete the target.

† Results added after submission. The tables are in the response to all reviewers (Part 2/2).

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.