Flatten Graphs as Sequences: Transformers are Scalable Graph Generators

We thank the reviewer for their constructive feedback, which we believe will strengthen our paper. Below, we address each point in detail.

W1. Positioning of prior work on graph-to-sequence representations

We thank the reviewer for their suggestion. Our intention was not to disregard prior work but to highlight our specific contributions within the scope of graph generation. We will revise the Introduction to more clearly and fairly position our work. Specifically, we will explicitly frame SENT as an advancement of previous random-walk-based sequence representations, emphasizing that its key innovations—being lossless and designed for prompt-based, substructure-conditioned generation that can be seamlessly integrated into language models like decoder-only transformers, addressing critical limitations of earlier generative methods. If the reviewer has any further concrete suggestions, we are more than happy to incorporate them.

W2. Interpretability of evaluation metrics

While we have already provided a short description about the evaluation metrics in Lines 278-291, we agree that providing intuition for these metrics will make our results more accessible. To improve clarity, we will expand our subsection E.2 in the Appendix to briefly explain the high-level meaning of our primary evaluation metrics. For instance:

MMD (Maximum Mean Discrepancy): This measures the distributional similarity between generated and real graphs. Lower MMD scores indicate that the generated graphs' statistics (e.g., degree, clustering) more closely match the training data. Some details and references have already been provided in Appendix E.2.

VUN (Validity, Uniqueness, Novelty): This assesses sample quality. Details have already been provided in Appendix E.2.

W3. Speed comparison beyond diffusion baselines

We emphasize that Table 2 already provides a speed comparison across three distinct paradigms of graph generation models:

• DiGress: A representative diffusion model.
• GRAN: A state-of-the-art autoregressive model.
• ESGG: A hybrid diffusion and autoregressive model specifically designed for efficient generation.

Our results clearly demonstrate that AutoGraph achieves inference speed comparable to GRAN, which is a leading autoregressive model, while simultaneously delivering significantly better sample quality (VUN scores) across various datasets. This comparison already substantiates AutoGraph's scalability and efficiency across different widely-used generation paradigms.

W4. Validity scores in molecular generation (Table 4)

AutoGraph's performance should be viewed through the lens of it being a general-purpose graph model competing against highly domain-specific methods (e.g., SMILES-based models).

The fact that AutoGraph, by learning from graph data alone, can achieve validity scores competitive with these specialized models is a strong demonstration of its learning capabilities. It successfully infers the complex, implicit rules of molecular construction. Furthermore, some models, such as MCTS a search-based method, that guarantee 100% validity do so at the cost of poor distributional similarity (e.g., a low FCD score). From a practical perspective, one can easily reject non-valid graphs to achieve near-perfect validity while generating over-simplified and basic molecules that have low distributional similarity (FCD score) with the training data, which is of low practical interest. AutoGraph achieves a superior overall balance. In short, both validity and FCD should be considered simultaneously when interpreting the model's performance. We will include a discussion in our revision.

Dear reviewer,

Following the NeurIPS 2025 guidelines, I kindly encourage you to read and respond to author rebuttals as soon as possible. Please engage actively in the discussion with authors during the rebuttal process, update your review by filling in the "Final Justification" and acknowledge your involvement.

Thank you, Your AC

We thank the reviewer for their constructive feedback, which we believe will strengthen our paper. Below, we address each point in detail.

W1: The main advantage of the proposed AutoGraph method lies in its generation speed

The advantage of AutoGraph is more than the generation speed. We believe scalability is one of the most crucial factors for success in many recent machine learning applications. Our work paves the way for scaling graph models to very large and diverse datasets, with potential applications in molecular generation, general graph understanding tasks, and even multi-modal LLMs.

W1.1: in Table 1, AutoGraph achieves the best VUN performance on the SMB dataset. However, it underperforms compared to methods like DiGress and GRUM in metrics such as node degree distributions (Deg.), clustering coefficients (Clus.), and orbit count statistics (Orbit). This may indicate that AutoGraph emphasizes the structural feasibility of the generated graphs.

This performance profile is an intentional result of our hyperparameter choice, which highlights the controllability of AutoGraph's generation process. The trade-off between distribution matching (e.g., Deg., Clus. Orbit) and sample quality (VUN) is explicitly managed by the top-k sampling parameter.

• On the Planar and SBM datasets, we tuned top-k to optimize for VUN, demonstrating AutoGraph's ability to generate valid and novel graphs, where it excels.
• On the Proteins and Point Cloud datasets, we tuned top-k to optimize for MMD on the validation set, where AutoGraph significantly outperforms DiGress and GruM.

This demonstrates that users can steer AutoGraph to prioritize either distribution fidelity or sample quality, depending on the specific application. We discuss this trade-off in detail in Appendix F.5 (Effect of top-k sampling).

W1.2: Table 4, AutoGraph scores lower than DiGress and JT-VAE on the FCD metric in the MOSES dataset, and lower than MCTS on the VALID metric in the GuacaMol dataset. This suggests that AutoGraph still has room for improvement in generating realistic molecular distributions.

AutoGraph represents a significant advance for general graph generative models in the specialized domain of molecular generation.

• Regarding MOSES: We kindly remind the reviewer that on this benchmark, lower FCD indicates better performance. As a result, AutoGraph outperforms DiGress and JT-VAE in terms of FCD.
• Regarding GuacaMol: It is critical to analyze the trade-offs. MCTS is a search-based algorithm engineered to achieve 100% chemical validity. However, its extremely poor FCD score shows it fails to capture the underlying data distribution. In contrast, AutoGraph strikes a much better balance, achieving a strong FCD score while maintaining high validity.

We believe this shows that AutoGraph is one of the first general-purpose graph models to achieve performance competitive with highly specialized, SMILES-based approaches.

W2: The interpretability of the token sequences generated by AutoGraph is less intuitive compared to representations like SMILES, and may not be suitable for all types of graph structures.

Our SENT representation is both more general and highly intuitive.

• While SMILES is an effective representation for chemists, it is a domain-specific language strictly limited to molecules. A primary contribution of our work is developing SENT as a general-purpose graph representation applicable to any type of non-attributed or attributed graph, as detailed in Sections 2.4 and 2.5.
• We respectfully suggest that SENT sequences are quite intuitive. They directly represent a trail through the graph, with explicit tokens for actions like moving to a neighbor, restarting with a new node, or indicating whether current node is a neighbor of a previously visited node. This provides a clear, step-by-step generative trace of the graph's construction.

W2. For dense graphs, where each node may have a large number of neighbors, the authors’ strategy of explicitly encoding adjacent nodes could lead to an excessive number of tokens, potentially affecting generation efficiency.

SENT is intentionally designed for sparse graphs, which represent the vast majority of real-world datasets in key domains like chemistry, social networks, and biology. While specialized methods might be more efficient for denser graphs, our approach is tailored to the problem space where generative modeling is most impactful. We also note that AutoGraph performs well on the SBM dataset, which contains relatively dense community structures.

Questions:

1. What is the difference between AutoGraph-Graph and AUTOGRAPH (Pretrained) in the last two rows of Table 4?

AutoGraph (Pretrained) refers to the model that was first pre-trained on the large-scale PubChem-10M dataset and subsequently fine-tuned on the downstream GuacaMol dataset. AutoGraph-Graph is the model trained on GuacaMol from scratch. This is detailed in Lines 351-353 of the main paper.

2. Currently, AutoGraph uses a 12-layer LLaMA model to align with GPT-2’s smallest variant, which is still relatively small in scale. Have the authors evaluated how AutoGraph scales with larger language models?

Due to computational constraints, our main scaling experiments were conducted on the small Planar dataset (see Appendix F.5, Table 14), where we found our current 12-layer model to be sufficient.

However, we strongly believe, in line with the well-established scaling laws in NLP, that training larger AutoGraph variants on massive graph datasets would unlock significant performance gains. Investigating these scaling laws for graphs is a high-priority and exciting direction for future work.

3. Does the proposed method support generation conditioned on combinations of different motifs as substructure condition? Currently, the experiments only demonstrate generation conditioned on repetitive occurrences of the same motif.

Yes, absolutely. The model handles this complex conditioning out-of-the-box, without any modifications.

We performed this exact experiment on two distinct motifs that were studied before, known as the linker design task. Due to space limitations, we placed the full results in Appendix F.4 and included visualizations in Figure 6.

Crucially, AutoGraph performs this multi-motif conditioned generation effectively without any additional fine-tuning, showcasing the power and flexibility of our prompting framework.

We thank the reviewer for their constructive feedback, which we believe will strengthen our paper. Below, we address each point in detail.

W1. many graph tasks may be non-discrete features.

We agree with the reviewer that handling continuous features is an important challenge. This is a known limitation for all discrete, token-based autoregressive models.

Fortunately, this is a well-studied problem with established solutions. A standard and effective approach is to employ a vector quantization autoencoder, such as a VQ-VAE $1$ , to discretize continuous attributes into a finite set of tokens. AutoGraph's framework is modular, allowing for the straightforward integration of such a quantization front-end.

[1]: Van Den Oord, Aaron, and Oriol Vinyals. "Neural discrete representation learning." NeurIPS 2017.

W2. While this is not a weakness per se and maybe not the focus of this paper, the proposed graph sequence approach has not been evaluated on general graph tasks which prior graph tokenization approaches seem to apply to.

We thank the reviewer for raising this point. While our primary focus was on establishing a new paradigm for graph generation, a core motivation for connecting graphs to language models is precisely to unlock their power for understanding tasks. Our SENT representation is well-suited for this. For any graph, one can generate one or multiple SENT sequences and feed them to the trained AutoGraph model. The resulting (averaged) hidden-state representations from the transformer layers can then be used for downstream tasks. We will add a paragraph discussing this promising direction for future work.

W3. Closely related recent works on graph to sequence methods such as $1$ , $2$ are not discussed.

We are grateful to the reviewer for bringing these relevant works to our attention. We have reviewed them and will incorporate a detailed discussion comparing their graph-to-sequence methodologies with our own in the revised related work section.

Questions:

Can the proposed SENT based graph to sequence representation be adapted for general graph modeling/understanding/downstream tasks?

As outlined in our response to W2, the SENT representations are easily adaptable for graph understanding tasks like classification and regression. By processing a graph's sequence through our trained model, the resulting transformer hidden states can serve as effective graph embeddings. This is similar to how GPT-like models are used for downstream tasks in NLP. While these embeddings are not specifically designed for graph understanding tasks, they should still be effective up to some modifications and fine-tuning, as supported by the fact that AutoGraph learns to generate Planar and SBM graphs without supervision.

If yes, how can the SENT sequencing apply to large size graphs where generally subgraph or partial graph is presented in a GNN network in existing works?

In general, SENT sequencing can be directly applied to large sparse graphs as demonstrated in our Point Cloud and NetworkX datasets. For even larger graphs, one can represent the graph with a set of subgraphs, from which one can sample SENT sequences. The resulting embeddings can be aggregated to form a representation of the entire graph, analogous to subgraph-based GNN evaluation protocols.

Dear reviewer,

Following the NeurIPS 2025 guidelines, I kindly encourage you to read and respond to author rebuttals as soon as possible. Please engage actively in the discussion with authors during the rebuttal process, update your review by filling in the "Final Justification" and acknowledge your involvement.

Thank you, Your AC

Dear reviewer,

Following the NeurIPS 2025 guidelines, I kindly encourage you to read and respond to author rebuttals as soon as possible as the reviewer-author discussion period is coming to the end. Please engage actively in the discussion with authors during the rebuttal process, update your review by filling in the "Final Justification" and acknowledge your involvement.

Thank you, Your AC

We thank the reviewer for their constructive feedback, which we believe will strengthen our paper. Below, we address each point in detail.

Overstatement of novelty

We appreciate the reviewer raising this point, as it allows us to clarify the specific nature of our contribution. Our full claim is that "AutoGraph establishes the first fundamental connection between graph and language modeling–where graphs are losslessly represented as token sequences, and prefixes in these sequences serve as meaningful patterns in both paradigms."

While prior works, including GEEL $1$ , have used autoregressive models, they do not establish this specific connection. The crucial distinction is that our representation ensures that the sequences are subgraph-induced (Theorem 2.14), meaning that all sequence prefixes generate induced subgraphs. This property is what enables high sample novelty and quality as well as prompt-based, substructure-conditioned generation without fine-tuning, a cornerstone of modern language models that previous graph autoregressive models lack.

To summarize, our key novel contributions, particularly in contrast to GEEL, are:

1. We provide a thorough theoretical framework for studying walk-based generative models, identifying the "subgraph-induced" property as essential for meaningful graph generation as well as identifying necessary and sufficient conditions for sequence representations that satisfy such property.

2. Our resulting sequence representation is the first to directly support substructure conditioning via prompting, aligning graph generation with language modeling capabilities.

3. We are the first to show that an autoregressive model can scale effectively to large and diverse graph datasets such as NetworkX and PubChem-10M, marking a critical step towards graph foundation models.

Regarding references $2,3$ , we would be grateful if the reviewer could provide the full citations. We are committed to discussing all relevant prior work and will gladly add them to our revision. If the reviewer has any further concrete suggestions, we are also happy to incorporate them into our revision.

Omission of GEEL's MMD metrics

We understand the reviewer's concern about the missing MMD metrics for GEEL. We omitted them initially due to a critical, undocumented difference in evaluation: GEEL's public code uses a Gaussian EMD kernel for MMD, whereas all recent works (GRAN, SPECTRE, DiGress, and ours) use a Gaussian total variation kernel. This makes a direct comparison with their reported numbers misleading.

Following the reviewer's suggestion, we have invested significant effort in reproducing their results with the correct kernel. Despite challenges with the official codebase (which required debugging and contained missing files for the Point Cloud dataset), we successfully ran experiments for the Planar, SBM, and Proteins datasets using the same hyperparameters as reported in their paper.

The results, presented below, show that GEEL largely memorizes some subset of the training data (indicated by near-zero VUN and Novelty scores and low uniqueness, aligning with the numbers reported in the original paper) and thus fails to generalize. Additionally, GEEL struggles to scale to the relatively larger Proteins dataset with very high MMD metrics.

---

Planar

---

SBM

---

Proteins

---

These results further underscore the novelty and significance of AutoGraph. We will add these new results and our analysis to the revised manuscript to ensure a fair and complete comparison.

Insufficient implementation details

All hyperparameter details are provided in Appendix E.4. We also clarify that both Llama 1 and 2 use the same decoder-only transformer architecture regardless of their version, differing only in model hyperparameters, and our model uses exactly this architecture. To ensure full reproducibility, we will release all documented code and pretrained model weights upon publication, as stated in Appendix B.1.

Questions:

Clarification on token definition

We kindly direct the reviewer to Section 2.4 (Tokenization of SENT) which describes tokens and our tokenization process. In short, a token can represent a node index, a special token, a node label, or an edge label in our sequential representation.

Unlike GEEL, our SENT sequences are subgraph-induced. This property is the key reason AutoGraph supports substructure-conditioned generation and achieves high VUN, while other sequence representations, such as GEEL and our SET representation, tend to memorize training samples, as evidenced by GEEL's low VUN and novelty scores in our new experiments.

Pre-training data scale

Our model is a significantly smaller variant of Llama with 113M parameters (Line 271), not the multi-billion parameter versions, making it suitable for standard dataset sizes.

In addition, as our SENT sequences are random sequences, we resample them at each iteration. This acts as a powerful form of data augmentation, mitigating overfitting even on smaller datasets like Planar. This makes AutoGraph a versatile and powerful model, effective in both small- and large-data regimes.

Dear reviewer,

Following the NeurIPS 2025 guidelines, I kindly encourage you to read and respond to author rebuttals as soon as possible. Please engage actively in the discussion with authors during the rebuttal process, update your review by filling in the "Final Justification" and acknowledge your involvement.

Thank you, Your AC

Dear reviewer,

Following the NeurIPS 2025 guidelines, I kindly encourage you to read and respond to author rebuttals as soon as possible as the reviewer-author discussion period is coming to the end. Please engage actively in the discussion with authors during the rebuttal process, update your review by filling in the "Final Justification" and acknowledge your involvement.

Thank you, Your AC