Flatten Graphs as Sequences: Transformers are Scalable Graph Generators
Authors: Dexiong Chen
Markus Krimmel
Karsten Borgwardt
Venue: NeurIPS 2025 poster ()
Keywords: graph generation
transformers
autoregressive modeling
language models
LLMs
Primary area: deep_learning
TL;DR: A novel autoregressive model for generating attributed graphs using decoder-only transformers.

Abstract: We introduce AutoGraph, a scalable autoregressive model for attributed graph generation using decoder-only transformers. By flattening graphs into random sequences of tokens through a reversible process, AutoGraph enables modeling graphs as sequences without relying on additional node features that are expensive to compute, in contrast to diffusion-based approaches. This results in sampling complexity and sequence lengths that scale optimally linearly with the number of edges, making it scalable and efficient for large, sparse graphs. A key success factor of AutoGraph is that its sequence prefixes represent induced subgraphs, creating a direct link to sub-sentences in language modeling. Empirically, AutoGraph achieves state-of-the-art performance on synthetic and molecular benchmarks, with up to 100x faster generation and 3x faster training than leading diffusion models. It also supports substructure-conditioned generation without fine-tuning and shows promising transferability, bridging language modeling and graph generation to lay the groundwork for graph foundation models. Our code is available at https://github.com/BorgwardtLab/AutoGraph.

Flatten Graphs as Sequences:
Transformers are Scalable Graph Generators
Dexiong Chen Max Planck Institute of Biochemistry Martinsried, Germany dchen@biochem.mpe mww.eemmmpp.... de
Markus Krimmel
Max Planck Institute of Biochemistry Martinsried, Germany
krimme @bi @ww.chem.mpp.g......eeeeee... de
Karsten Borgwardt
Max Planck Institute of Biochemistry Martinsried, Germany
borgsardt@@iochhmm..mo
Abstract
We introduce AUTOGRAPH, scalable autoregressive model for attributed graph generation using decoder-only transformers. By flattening graphs into random sequences of tokens through a reversible process, AUTOGRAPH enables modeling graphs sequences without relying on additional node features that are expensive to compute, in contrast diffusion-bair based approaches. This results in sampling complexity and sequence lengths that scale optimally linearly with the number of edges, making it scalable and efficient for large, sparse graphs. key success factor of AUTOGRAPHI is that its sequence prefixes represent induced subgraphs, creating a direct link to sub-sentences in language modeling. Empirically, AUTOGRAPH achieves state-of- the-art performance synthetic and molecular benchmarks, with up to 100x faster generation and 3x faster training than leading diffusion models. It also supports
generation without fine-tuning and shows promising transferability, bridging language modeling and graph generation to lay the groundwork for graph foundation models.
Our code is available at https:::// //githubg.ttt.. htt.///orrggarrtaaaaatttrrraaaa
Introduction
Recent advancements deep generative models have revolutionized various domains of artificial intel- ligence, demonstrating remarkable capabilities in generating complex data types such images (55), natural language 7 63 64), and audio 17 28 These achievements have been primarily driven by the development of advanced architectures methods such transformers and diffusion models, alongside increasingly large-scale data resources. However, the generation graph-structum which is fundamental to numerous scientific applications including drug discovery [66] 44) protein design [29), and program synthesis [5]. remains a significant challenge. This disparity primarily stems from the inherent complexity of preserving structural validity, maintaining invariance properties within graphs, and achieving scalability real-world graph generation tasks.
data,
To this end, diffusion- models have emerged promising direction for graph generation, demonstrating effectiveness in synthesizing both classic unattributed graphs and molecules [34] (6). These approaches typically implement a denoising process in discrete graph space, simultaneously predicting edge connectivity and attributes. Yet, their practical applications are constrained by fundamental scalability limitations. The requirement for full adjacency matrix operations imposes quadratic memory complexity with respect to the number of nodes. Moreover, computing additional
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

node features in each denoising step, such as spectral features, often involving cubic complexity. further increases the computational overhead.
Autoregressive approaches represent an alternative paradigm, constructing graphs sequentially by generating nodes and edges in step-by-step manner 43 71. These models have demonstrated strong performance in generating small to medium-sized graphs by leveraging their ability to maintain structural validity through the generation process. Nevertheless, these models face inherent limitations: their sequences are not composed of tokens and thereby require specialized architectures, primarily based on recurrent neural networks, to process their complex ad-hoc sequential representations, preventing them from directly leveraging the remarkable advances in large language models (LLMs). Moreover, these specialized architectures often struggle with long-range dependencies and global structural consistency, leading to significantly inferior performance compared to recent diffusion This representational and architectural constraint not only limits their scalability but also creates a growing performance gap as general-purpont L.LMs continue to advance rapidly.
models 66 35
In light of these challenges, we introduce a novel paradigm that bridges the gap between graph generation and LLMs through a graph-to-sequence transformation. Our approach advances previous random walk-based methods by representing graphs as sequences of tokens while maintaining their topological properties. Instead of requiring specialized architectures or operating directly on graph structures, we propose a method linearize graphs into random sequences that encode local connectivity patterns. This transformation enables direct utilization of language models for graph generation while achieving optimally linear complexity with respect to the number of edges in both computational and memory requirements. Our approach effectively addresses the limitations of both diffusion- and autoregressive methods: maintains structural validity while enabling efficient scaling to large graphs and leveraging the powerful capabilities of modern language models.
Our work presents several technical contributions the field of graph generation. (1) We introduce the concept of segmented Eulerian neighborhood trails (SENTs), a specialized class of Eulerian trails that permit breaks and incorporate neighborhood information. We establish sufficient conditions un- der which they can be employed for effective graph generation. (2) We propose an efficient flattening algorithm that transforms graphs into sequences and vice versa by sampling these SENTs, enabling lossless sequence representation of graphs. (3) Our method, termed AUTOGRAPH, achieves state-of- the-art (SOTA) performance across diverse synthetic and molecular graph generation benchmarks, delivering a 100-fold generation and a 3-fold training speedup compared to ceffusiio-based models while maintaining the ability to scale to graphs of possibly immense size. (4) Additionally, AUTO- GRAPH demonstrates strong transfer learning capabilities and supports substructure--codditoonee generation without additional fine-tuning. Our work not only advances the field of graph generation but also opens new avenues for applying LLMs to graph-centric tasks, paving the way for building foundation models for graphs.
2 Methods
In this section, we present an approach to transforming graphs into sequences, enabling their modeling akin to natural language. Our method hinges on specialized class of random trail segments that ensure complete graph coverage. We begin by introducing the concept of segmented Eulerian trails (SET) and demonstrate theoretically why this representation alone is insufficient for effective graph generation. Subsequently, we propose an extension of SET, namely the segmented Eulerian neighborhood trail (SENT), which additionally incorporates neighborhood information alongside the trails. We elucidate sufficient conditions for effective generation and develop an efficient sampling strategy obtain such SENTs. The section concludes with extensions and discusses how to model the SENTss autoregressively using language models, thus bridging the gap between graph learning and language modeling paradigms. An overview of AUTOGRARE APH is illustrated in Figure I and backgrounds and proofs are provided in Appendix Cland D
2.1 Segmented Eulerian Trail
To formalize our approach, we begin by introducing fundamental concepts in graph theory. Let V be a set of vertices and E = V x V a set of edges. A graph is defined as a tuple G = (Va, Ea), where Vo S V is a finite set of vertices and Eg S Va x Va is the set of edges. For simplicity and without loss of generality, restrict our attention to undirected graphs without isolated vertices, where each
2

---

1) SENT Sampling
Tokenization
3) Autoregressive Modeling
Reindcxing vartices
(1) 12 U3, 14, #5 1> (1, 2,
P/
US
(1. b)
(2, B)
(3,
Language Model
(5. B)
(1(2))
B)
(0%, 0)
(09,
V
(14. Dj
(1%. (p
Figure 1: Overview of AUTOGRAPH: (1) We use Algorithm to sample a SENT s from the input
graph: = (2), with $1 = ((11, 0). (22, 0), (v3, 0)) and = ((vs, {r2}), (oy, 0)). (2) We tokenize by reindexing the vertices based on their first occurrence order and adding special tokens ('/' represents breakage between segments, '<' and '>' indicate the start and end of neighborhood set). (3) We perform the next token prediction on the tokenized sequences using decoder-only transformer or any language model.
edge is represented an unordered pair (u, v) for u, U E V. We begin by defining the concept of trail in graph:
Definition 2.1 (Walk and trail). walk sequence of nodes connected by edges G and a trail is a walk in which all edges are distinct. Given a graph G, the set of trails in G is denoted as Ta.
Next, we generalize the concept of trails beyond the context of specific graph:
Definition 2.2 (Generalized trail). A generalized trail of length k is defined as a sequence of nodes (Wo ... w&) V for & 2 s.t. (wi-1, w:) A (wj-1, wy). Vi,j [k] and + j.
The set of all generalized trails is denoted as T, noting that To S T for any G. For a generalized trail w 'T define V. C V and E. C E the sets of vertices and edges traversed by w, respectively, termed the generated sets of w. An Eulerian trail is trail that visits every edge in a graph exactly once. Such trails are of particular interest as they capture the complete topology of the graph. However, the existence of an Eulerian trail depends on specific conditions related to vertex degrees and connectivity of trail segments:
To generalize this concept to arbitrary graphs, we introduce the notion 3
Definition 2.3 (Segmented Eulerian trail (SET)). A segmented Eulerian trail (SET) in G is sequence of trail segments such that each edge is visited exactly once across all segments, and segments do not need to connected. Formally, a SET of size
is defined as 8 := (61......8)) 81)) ) s.f. 8 E Tc, and the generated edge sets of its segments form a partition of Eg. i.e., E. EG and E., n E., = 0, Vi,j E [k]] + j. Similarly, a SET (without relying on a specific graph) is defined as a sequence of generalized trails whose generated edge sets are disjoint.
The set of all SETs in is denoted as Sç, and the set of all SETs is denoted as S. For a SET (st) we define the generated node and edge sets V, == = and E, := 1 E., The graph G. = (V., E.) is termed generated graph of s. It is easy to show that is SET in G if G, G. Moreover, SETs can be classified into equivalence classes based on graph isomorphism, as formalized below:
Definition 2.4 (SET isomorphism). For any two SET's 8, E S, we say they are isomorphic s z if there is bijection π V, > V, between their generated node sets and (() t where applies elementwise to all nodes in s.
This isomorphism partitions S into equivalence classes. Moreover, we have the following relationship between SETs and graphs, relevant for our tokenization (Sec. 2.4p:
Theorem 2.5. For any SETs 8, E S, their generated graphs are isomorphic, i.e., G, ~ G. if 22 Conversely, if two graphs G H. then for any SET E Sc, there exists a SET E SH s.I. 8 at
While a SET in G fully characterizes its structure, we show below the prefixes of the SET do not necessarily describe the substructures of G, a critical property for effective autoregressive graph generation.
Definition 2.6 (Flattening). The flattening of a sequence of sequences s the concatenation all its sequences, denoted as ||s.
3

---

Definition 2.7 (Prefix of SET), For & E S, we call a prefix of s if ||t is a prefix of Iss.
Lemma 2.8. For any graph G and SET s in G, the generated graph of any prefix of is a subgraph of G, but not necessarily an induced subgraph.
This result motivates us to extend the definition of generalized trails to incorporate the full structural information of the induced subgraphx, rather than arbitrary subgraphs, to constrain the generation space better and address long-range dependency challenges. Without this extension, dependencies between neighboring nodes may span a long sequence of generation steps, making it more difficult for the model to learn such dependencies. Empirically, we show that SET fails to generate structurally valid graphs in Section
2.2 Segmented Eulerian Neighborhood Trail
To make the prefixes of a SET encode richer information, we need extend SET to contain neighborhood information in a graph. Thus, we consider the following definitions:
Definition 2.9 (Neighborhood sequence). A neighborhood sequence is a sequence of tuples w == (Wo..... w/k where w; = (1,, A.) with a node v E V and neighborhood set A, S. V. Vi {O..... k}. w is called Hamiltonian if its node sequence n(w) = (vo. .......... Ubb has non-repeated elements. w is called causal if A, only contains visited nodes, i.e. A, S (vo..... 1111) Vi [k].
Definition 2.10 (Neighborhood trail). A neighborhood trail is a neighborhood sequence that satisfies two conditions. (i) n(w) is generalized trail. (ii) If we define the generated edge set of w; as Fu:; = [(1;; u) u E } the family (Fr(w); Fur..... Fmm)) pairwise disjoint. Its union is called the generated edge set of w.
The set of all neighborhood trails is denoted by T.V. For any w E TN,, we denote by G == (Vus Ew) the generated graph of w where Vn == | A.) U VV(m)) is the generated node set and En is the generated edge set. Note that generalized trail is neighborhood trail with A, = 0, Vi. We extend SET to incorporate neighborhood information:
Definition 2.11 (Segmented Fulerian neighborhood trail (SENT)). A segmented Eulerian neighbor- hood trail (SENT) of size k is a sequence of neighborhood trails == (s1.....33) Sk) with pairwise disjoint generated edge sets, i.e., s, T. and E,, n Es, 0, Vi,j i6),i#1
Similarly to SETs, the generated graph of SENT is denoted by G. (Vs, E,). If a graph G G,, we say that s is a SENT in G. We denote by S. and S the set of SENTs and SENTss in G. Analogously to SETs, we define an isomorphism over S. and obtain the same relationship as in Thm. 2.5 A prefix of a SENT is defined similarly to that of a SET. We give below conditions to force generated graphs of prefixes of a SENT to be induced subgraphs.
Definition 2.12 (Causal SENT). A SENT 8 is called causal if its flattening ||
is causal.
Definition 2.13 (Hamiltonian and semi-hamiltonian SENT). A SENT is called Hamiltonian its flattening | is Hamiltonian. s is called semi-hamiltonian if s is Hamiltonian, or for any nodes visited more than once, their occurrences after the first time should be in start tuple of neighborhood trail and their associated neighborhood sets are empty.
Theorem 2.14. For any causal SENT s E S.N, the generated graph of any prefix of is an induced subgraph of G. and only if is amii-hamlloonin. In this case, s is called subgraph-induces
Now let find the conditions for causal and Hamiltonian SENT. For any SENT & and tuple W : (v, A) in s, we denote by V. (w) the set of nodes visited by s before w, excluding the node linked to through the trail if it exists. We have the following necessary and sufficient conditions:
Theorem 2.15. For S.. is causal and Hamiltonian if and only if every tuple
(v, A.) in I|s
satisfies A, = (v) n (w). In this case, every node is visited exactly once. Moreover, s is causal and semi-hamilionian and only if every tuple == (v. A.) in s satisfies either A, = NV.
or A,
This theorem offers simple sufficient condition for subgraph-induced SENTs.. We provide an implementation in the following through random path sampling strategy.

---

2.3 Sampling Algorithm for SENT
Thm. 2.15 offers 1.15fffers& simple strategy sample a causal and Hamiltonian SENT: one needs to traverse the graph and choose the neighborhood set as all neighbors of the current node that have been visited. The traversing strategy could be achieved through random path sampling or depth-first search. In A we provide a sampling strategy based on random path sampling with breaks. Complexity analysis. The length of a SENT, including the sizes of neighborhood sets (in other words, tokenized SENT defined in Section (.4). is bounded by the number of nodes and edges, as each node and edge can be visited exactly once. Therefore, both the time and space complexity of sampling SENT from graph G are (m) where is the number of edges.
2.4 Tokenization of SENT
Previous works have explored related con- cepts of sequences in graphs. For exam- ple, You et al. 71 investigated causal Hamiltonian neighborhood sequences gen- erated through breadth-firs search, while Liao et al. [43] Goyal et al. [23] con- structed SENT-like sequences using depth- first search. However, neither of these works interpreted these sequences as a lan- guage. Here, we present method to bridge the gap between graph generation and lan- guage modeling.
Algorithm 1 Causal and Hamiltonian SENT Sampling
Input: G= EV
Output: A SENT in G
I: Set of unvisited nodes U t
2: t-1
3: V + RandomSample(U)) U -----0 - {o}
4: + [(v, 0)
D first neighborhood trail
5: while U + do
6:
if (v) 0 then
D start new trail
7:
s. s.append(t)
8:
+ RandomSample(U)) U (o) + No(() t [(u,
9:
The tokenization process starts by map-
10:
ping all isomorphic SENTs to the same se- quence, by reindexing the vertices accord-
11:
else
& sample the next node in the trail
ing to their first occurrence order within 12:
RandonS@mple((a(())
the sequence. Specifically, if we denote 13:
U + U {u)
14:
+ (No(u) (v))
this ordering function for SENT by
15:
Lappend (u, A))
ı V. + [V....,[VV]].. s is then re- placed with its ordered representation rTs).
16:
Thanks to the isomorphism property of SENT (Thm. 2.5). π (s) generates a graph isomorphic to G, while ensuring the obtained sequence is invariant to the node ordering of the input graph.
To convert an (ordered) SENT into machine-readable sequence, we tokenize it into sequence of indices using special tokens. These tokens include symbols such / to indicate a breakage between segments, and '<' and '>" to mark the start and end neighborhood set. Specifically, for any = (81, . 8x) E SNN,, we define the tokenization function Token as follows:
(oken(s) : (s1) [[] ... [/] || Token (sk)) where Token(s; (s;) == wl Token (wre),w))
and for each tuple w = (v, A) with the sorted set - {u...... {p (due to the reindexing by TT) we define:
Token(w) = [u. <, W1, ",...., up >|.
This process converts SENT into sequence of tokens that language model can effectively model. Using an equivalent form, the resulting tokenization induces a non-Markovian random walk in the graph, incorporating additional virtual nodes labeled with the above special tokens (see Appendix C.2 for more details). Language modeling of SENTs aims to learn the state transition probabilities.
2.5 Extension to Attributed Graphs
Our method can be easily extended graphs with categorical (or discretized) attributes by inserting node and edge attributes in an interleaved fashion into the tokenized SENT sequence. Specifically, let Lmnde(()) (r) and Ledge(u, (u, v) be the attributes of node v and edge (u, v) respectively. Using the
same notation above, we define for any 8; (wi, ......... w.) E TN with w; (vi, r):
Token(s:) = Token(w: || [Ledge (U1, 22)1 || Token(wy) -.. .. Token(w.))
Token( w) = [v, (v), <, Ledgo (v, u1), u1, Ledge (v, up); Up >].
5

---

2.6 Autoregressive Modeling of Tokenized SENTs
The sampling and tokenization of SENTs in graphs allows for transforming graphs into sequences, which could be modeled by language models. Specifically, given a graph G represented as SENT which consists of a sequence of tokens ($1.....Sn). standard language modeling objective is to maximize the following log-likelihood:
p(s) Σ log (0 $1.... ,1,....88-11))
where the conditional probability pe is modeled using a neural network with parameters 0. The architecture of the neural network can be any state-of-the-art sequence model.
3 Related Work
Autoregressive models for graph generation. Autoregressive models generate graphs by sequen- tially adding nodes and edges. GraphRNN [71] pioneered this approach by framing graph generation as sequence prediction task, demonstrating the capacity of recurrent neural networks (RNNs) [I5) capture complex structures. DeepGMG [42 introduced a probabilistic policy framework for conditional generation, while GRAN 43 and BiGG [6 enhanced efficiency and scalability by
generating multiple nodes and edges in parallel. ANFM
44 leverages filtration to improve efficiency.
Recent research has focused on optimizing the generation order. Chen et al. [2] highlighted that the ordering of node and edge additions impacts graph quality, and GraphARM 39 applied reinforcement learning to dynamically refine this order. Goyal et al. (33 incorporated logical constraints to improve domain-specific generation, and Bacciu et al. 1 proposed Bayesian reasoning better capture graph dependencies. BwR 18 and GEEL 32 investigated node ordering based on optimized bandwidth.
These models, while efficient synthetic datasets, do not explicitly represent graphs token sequences, preventing direct application of LLM techniques. More significantly, their sequences are not guaranteed to be subgraph-induced (see Thm. 2.14). In contrast, our approach enables cewttrructure--codittiii
generation analogous to prompt- -ased generation in language models, establishing more fundamental connection between graph and language modeling paradigms.
Other graph generative models. Other graph generative models include variational, GAN-based, flow-based, and diffusion-based approaches. GAap (38 58 employ variational autoencoders learn latent representations, effectively generating small graphs but struggling with more complex structures. GAN-based models, such as NetGAN 4 and SPECTRE [45). generate graphs by modeling graph descriptors like random walks and spectral features. Flow-based methods such as [57 have shown the ability to generate small molecular graphs.
Diffusion-based models iteratively refine noise into structured graphs through reverse diffusion steps. Continuous diffusion models [51] adapt denoising diffusion probabilistic models for graph generation. To leverage graph sparsity and structure, discrete diffusion models (66 39
35 69 have
been developed. However, a key challenge for these models is the slow sampling process due to the
long reverse diffusion chain. To mitigate this limitation, several efficient diffusion techniques have
been proposed, including EDGE [13. HiGen [36), ESGG 2 and Pard 73).
Random walks for graph learning. Random walks have been widely used in graph learning due to their strong expressive power. GCKN S and RWGNN (50) utilize path and walk kernels to learn graph representations. Several recent works 30 67 70 explicitly integrate random walk sequences with positional encodings, inspiring subsequent methods such as CRaWL [62), NeuralWalker [IO] and RWNN [37]. GraphGPT 774) leverages Eulerian paths improve graph property prediction. Some graph transformers 48, 9 also leverage features based on random walks. Moreover, graph-to- sequence representations have been used assist LLMs in understanding graphs [22 I.] Our work
explores sequence representations of graphs for graph generation, introducing a novel perspective on combining random walks and language modeling for scalable graph generation.
4 Experiments
In this section, we evaluate the performance of AUTOGR APH on several graph generation benchmarks, including both small and large graphs, and synthetic and real-world molecular datasets. Our experi-

---

Table 1: Benchmarking AUTOGRAPH on Planar and SBM
PLANAR GRAPES
STOCHASTIC BLOCK MODELS
Pgrppi
[V]
Sguupka
[Vluse
187, [Vlogg
104
MODEL
DEG.
CLUS.
ORBIT
SPEC.
RATIO
VUN
DEG.
CLUS.
ORBIT
SPEC.
RATIO
VUN
TRAINING SET
0.0002
0.0310
0.0005
0.0038
0.0008
0.0332
0.0255
0.0027
1.0
GRAPHRNN
71
0.0049
0.2779
1.2543
0,0459
638.5
0.0
0.0055
0,0584
0.0785
0.0065
3.5
5.0
GRAN
0.0007
0.0426
0.0009
0.0075
2.1
0.0
0.0113
0.0553
0.0540
0.0054
5.0
25.0
SPECTRE
13
0.0005
0.0785
0.0012
0,0112
2.6
25.0
0.0015
0.0521
0.0412
0,0056
1.8
52.5
EDGE
0.0761
0.3229
0.7737
0.0957
0.0
0.0279
0,1113
0.0854
12.7
0.0
GRAPHGEN 25
0.0328
0.2106
0.4236
0.0430
257.3
7.5
0.0550
0.0623
0.1189
0,0182
20.5
5.0
BIGG [6
0.0007
0.0570
0.0367
0.0105
20.4
5.0
0.0012
0,0604
0.0667
0.0059
2.0
10.0
DICRESS
0.0007
0.0780
0.0079
77.5
0.0485
60.0
GRUM S5
0.0005
0,0353
0.0009
0.0062
1.8
90.0
0.0007
0.0492
0.0448
0.0050
1.5
85.0
GEEL 32
0.0039
0.0013
0.0062
0.0234
9.5
0.0
0.0106
0,0616
0.0023
0.0381
7.3
3.0
ESGG
0.0005
0.0626
0.0017
0.0075
95.0
0.0119
0.0517
0.0666
0.0067
45.0
AUTOGRAPH
0.0004
0,0605
0,0003
0.0064
1,5
87.5
0.0077
0,0519
0.0439
0,0040
3,4
92.5
ments compare its performance to several SOTA methods and particularly focus evaluating the following aspects: (1) We show its ability to generate relatively small graphs with a 100-fold inference speedup compared to diffusion-
models while maintaining or even improving structural validity. (2) We show its ability to scale to large graphs without loss of performance.
(3) We demonstrate its effectiveness in generating real- world graphs with attributes with a focus on molecular generation, outperforming SOTA diffusion models. (4) We showcase its strong transfer capabilities and its ability to perform cesstructure-codiiioon generation without any additional fine-tuning. Additional details on experimental settings and evaluation are provided in Appendix E
Implementation details. We employ the L.LMMA model with 12 layers and hidden dimension of 768 as our sequence model backbone across all experiments, aligning with the architecture of GPT-2's smallest variant (54). Although prior works have used smaller models, we argue that our approach still demonstrates better scalability and faster training and inference speeds compared to diffusion models. For inference, we adopt the commonly used top-k sampling strategy (2I]. Our implementation leverages the Hugging Face framework (31], providing users with a flexible interface to experiment with SOTA language models for graph generation.
Evaluation. For fair comparison, we align our evaluation methodology with established practices from prior works 771 45 66). Our evaluation compares generated samples against the test set using maximum mean discrepancy (MMD) [24), computed across multiple graph descriptors: node degree distributions (DRG.), clustering coefficients (CLUS.), ), orbit count statisties (ORBIT), and eigenvalue spectra (SPEC.). As a reference, we also compute MMDs between the training and test sets and report the average ratio between generated and training MMDs (RATIO) following Bergmeister al. (2).
For synthetic datasets, we additionally assess model performance using the VUN metric, namely the proportion of generated graphs that are simultaneously valid, unique, and novel compared to the training graphs. Our efficiency analysis includes two measurements: inference speed, calculated as the per-graph generation time when producing 1024 graphs, and training speed, measured as the time required to achieve a VUN score of 75.0 for the Planar dataset and 60.0 for the SBM dataset. All efficiency measurements are performed
single NVIDIA H100 GPU.
For molecular generation datasets, we strictly follow the evaluation metries used in DiGress [66] and
use the evaluation tools from the official codebase [53 6
More details are provided in App. E.2
4.1 Comparison to State-of-the-Art Methods
We evaluate the performance of AUTOGRAPH compared to other SOTA graph generative models using the standard setting without pre-training. The comparison partners include GraphRNN [71).
GRAN 43). SPECTRE 45 EDGE [3], GraphGen [23). BiGG [6). DiGress [66). GruM 35
GEEL
32
and ESGG
2
Small synthetic graph generation. We first evaluate our method on the small synthetic graph datasets introduced by Martinkus et al. [45,, including the Planar and SBM datasets. As shown in Table [ AUTOGRAPH demonstrates competitive MMDs while ranking second-best and best in terms of VUN scores on the Planar and SBM datasets, respectively. Importantly, only GruM and AUTOGRAR AP exhibit strong structural validity (VUN 2 80.0) on the SBM dataset. Previous oftt--of-th-aar autoregressive models, particularly GEEL, completely fail on both datasets in terms
7

---

Table 2: Benchmarking AUTOGRAPH Proteins and Point Clouds. OOM indicates out of memory. Note that for GEEL [32], we fail to reproduce their experiments on the Point Clouds dataset using their official codebase.
PROTEINS
POINT CLOUDS
Mgraphs
587. [V|mxx
500,
[Vlag # 258
Nigophh
26, IV Imxx
5037.
[Vl s 1332
MOUEL
DEG.
CLUS
ORBI
SPEC.
RATIO
DEG.
CLUS.
ORBIT
Spec.
RANI
TRAINING SET
0,0003
0,0068
0.0032
0.0005
1.0
0,0000
0.1768
0,0049
0.0043
1.0
GRAPHRNN M1
0,0040
0.1475
0.5851
0.0152
62.1
0OM
00M
00M
00M
00M
GRAN 43
0.0479
0.1234
0.3458
0.0125
77.7
0.0201
0.4330
0.2625
0.0051
19.1
SPECTRE
45
0.0056
0.0843
0.0267
0. 0.0052
12.5
0OM
0OM
00M
00M
00M
EDGE
0.1863
0.3406
0.6786
0.1075
274.5
0.4441
0.3298
1,0730
0.4006
104.7
GRAPHÕEN 23
0,0159
0.1677
0.3789
0.0181
58.1
OOM
00M
0OM
00M
OOM
BIGG [6
0,0070
0.1150
0,4696
0.0067
50.1
0.0994
0.6035
0.3633
0.1589
38.2
DIGRESS
0.0041
0.0489
0,82
0.0018
16.2
0OM
00M
00M
00M
00M
GRUM 35
0.0019
0.0660
0.0345
0.0030
8.2
OOM
00M
00M
00M
0OM
GEEL
0.2110
0.1768
287.9
ESGG 2
0.0030
0,0309
0.0047
0.0013
4.7
0.0139
0.5775
0,0780
0.0055
6.8
AUTOGRAPH
0.0004
0.0244
0.0056
0. 0.0013
2.3
0.0307
0.3031
0.0167
0.0171
3.0
of VUN scores, they largely memorize some subset of the training data. is worth noting that the relatively low MMD ratio of AUTOGRAPH is expected, as we selected the best model based on the VUN score. More results with error bars are provided in App. F.1
Additionally, we assess the training and inference times of AUTOGRAPH against representative mod- els, including DiGress, GRAN, and ESGG. As presented in Table AUTOGR APH is approximately 3 times faster during training and 100 times faster during inference compared to diffusion- based models. This substantial speedup over diffusion-basee models is even more pronounced than that observed in other data modalities such as images [61.
Large graph generation. To understand the evaluate its
scalability of AUTOGRAPH, performance on the Proteins and Point Clouds datasets used by Liao et al. (3). The re- sults. shown in Table 2 demonstrate that even when using a context window shorter than the longest sequence during training, AUTOGRAPH achieves MMD ratios comparable to those ob- served on the Planar and SBM datasets. Further- more, AUTOGRAPH outperforms all existing methods in terms of MMD ratio, achieving twofold or more improvement over the previous best model, ESGG. More significantly, while ESGG was specifically designed for generating unattributed graphs, AUTOGRAPH demonstrates versatility by being applicable to both unattributed and attributed graphs. Finally, previous state-of-the- -he autoregressive models, such GEEL, again fail to achieve competitive performance on these datasets.
Table 3: Time comparison of AUTOGRAPH to repre- sentative models. OOT indicates the model never reaches the target VUN.
DATASET
TIME
DIGRess
GRAN
ESGG
AUTOGGRAPI
PLANAR
TRAINING
INTERENCE
25.9H
2,84%
0.038
4.60s
0.015 (284x)
(4.2x)
SBM
TRAINING
INFERENCE
13.055
47.7H
0,138
00T
30.05
O0T
13.8Ht (3.5%)
0.145 (93x)
Molecular graph generation. We demonstrate the applicability of our method to generating real- world attributed graphs, such as molecular structures. We evaluate AUTOGRAPH on the same datasets used by DiGress [66,, including QM9 (all atoms) [68, MOSES [53], and GuacaMol ( Following the data splits and experimental setup from DiGress, we benchmark AUTOGRAPH against a variety of SOTA models, including DiGress, VAE on SMILES [53], JT- VAE [33, GraphINVENT [47),
NAGVAF 41), LSTM and MCTS 6 On the QM9 dataset (Table 12), AUTOGRAPH outperforms DiGress across all metrics except uniqueness, showing its superiority for attributed graphs.
For the more challenging MOSES and GuacaMol datasets, AUTOGRAPH also demonstrates superior performance, achieving higher validity and improved distributional alignment as measured by metries like FCD, as shown in Table 4 Notably, to our best knowledge, AUTOGRAPH is the first autoregres- sive model for graphs to surpass diffusion-baat based approaches on these datasets. It is worth mentioning that all metrics were computed using SMILES representations rather than molecular graphs. Due to the non-reversible nature of converting SMILES to graphs and back, where approximately 20% of molecules cannot be mapped back to their original SMILES [66), some discrepancies are introduced when calculating these metrics. Despite these challenges, AUTOGRAP APH achieves validity and FCD scores comparable to SMILES- based methods.
8

---

Table 4: Benchmarking AUTOGRAPH on the molecular generation datasets, more results in App. F.2 AUTOGRAPHI was first pretrained on the PubChem- 10M dataset (4].
Poupte Usiquet
LERM. Plass
MOSES
27, [Flwy
Nigupta - -1IM. Viaws - 88, IF ang in
GUACAMoL
VALIUT
NOvELT
FiLitasst
FCD:
SNN.
MoDel.
UNIQURT
NovIC1
GRAPHINVENT GRAPR
VEV FIAASMINTS
VAB SMILES
DiGaesS GRAPE
97.7
96.4
85.7
100
99.5
69.3
100
100
06.
99.9
97.3
99.3 7
07.1
0.57
1,00
1.19
0.52
0.53
0.55
LSTM SMILES
MCTS GRAmE
DIGRESS GRAPT
NACVAE GRAPE
92.1
35.2
95.9
100
95.3
100
100
1.0
91.2
99.9
99.4
100
58.4
53.3
96.1
02.9
91.3
0.9
3.5
AFTOGIRAPH- GRA
87.4
100
0.90
0.35
AUTOGGRAPH GRAPH
AUTOGRAPH" GRAZH
91.5
95.9
100
100
91.2
95.5
91.5
98.1
93.4
70.2
Table 5: Transfer performance on downstream tasks using AUTOGRAPH pre-trained on the NetworkX dataset. Red and green colors indicate relative decreases and increases, respectively, compared to AUTOGRAPH without pre-trriinnn treetriinin..
DATASET
DeG.
CLUS.
OXBIIT
Sinc.
RATIO
VUN (IMPROVEMENT)
NETWORKX
0.0016
0.0073
0.0068
0.0020
PLANAR
0.0007
0.0811
0.0005
0.0061
2:2
(-7.5
SBM
B.0099
B.0566
0.0854
0.0065
4.8
97.5(+5)
PROTHINS
0,0002
8.0183
0.0038
0.0012
1.7
POINT CLOUDS
0.0154
0.2591
0.0076
0.0236
2.8
Furthermore, AUTOGRAPII demonstrates remarkable efficiency, with training times of less than one day on both datasets, compared to up to one week for DiGress [66). This substantial reduction underscores AUTOGRAPH's practical advantages in large-scale molecular graph generation tasks.
4.2 Transfer Performance of AUTOGRAPH
We evaluate the transferability of AUTOGRAPH by pre-training it on large dataset of synthetic graphs generated using NetworkX [26] and fine-tuning it the unattributed graph datasets. Dataset and experimental details are provided in Appendix As shown in Table [S] the pre-trained model consistently outperforms the baseline on small synthetic datasets in terms of the VUN score, achieving near-perfect validity. On larger graph datasets, the pre- pre-trained model also surpasses the baseline across MMD) metrics, demonstrating its ability to generalize to more complex structures. However, on small synthetic datasets, the pre-trained model shows a slight decline in MMD metrics compared to the baseline. These findings highlight the potential of building foundation models for graph generation and underscore the need for more comprehensive benchmarks beyond synthetic datasets.
We also test the transferability of AUTOGRAPII on molecular graphs, by pre-training it the PubChem-10N, 10M dataset [14] and fine-tuning on GuacaMol. The pre-trained model substantially outperforms the baseline, as shown in Table
4.3 Substructure Conditioned Generation
We explore the ability of AUTOGRAPII to perform bobstrrcture-condition generation without requiring fine-tuning, Given a subgraph S (which could represent a functional motif of interest drug discovery), we flat- ten the subgraph into SENT sequence and condition the generation process on this sequence. This approach guarantees that the generated graph will contain S as an
Table 6: Motif scaffolding
MOTIP COFIES
VALID
UNIQUE
NOVELTY
92.0
98.8
88.8
99.7
100.0
100.0
induced subgraph (Thm. 2.14). As a proof-of-concept. we follow the methodology of Vignac et al. (66), Maziarz al. [46] and generate molecular graphs starting from specific motif, called 1,4- Dihydroquinoline! using the model pre-trained on the GuacaMol dataset. Our results in Table
demonstrate that this approach maintains similar validity, uniqueness, and novelty to unconditional generation (Table 4. To further showcase the flexibility of this method, we test more extreme cases by replicating the same motif multiple times before performing the conditional generation. While validity decreases significantly when using an unrealistically large number of copies (e.g. 5), the model still generates some visually plausible molecules (Appendix [.4]) showing superior flexibility over Vignac et al. [66). These results highlight the potential of AUTOGR APH for important applications in drug discovery, particularly in motif scaffolding. Additional experiments multiple but different motifs are provided in App.
https://pubchem..t ncbi nlm. nih, wwth.goo/coopooo gov/compound/1.. htt.d//odoo...ttytouuouu....nee.

---

Table 7: Comparison of sequence model architectures the Planar dataset.
ARCITTCcTURE
DEG.
CLUS.
ORBET
SPEC.
RATIO
VUN
GPT-2
0.0004
0.0720
0.0010
0.0053
1.8
85.0
0.0429
0.0014
0.0087
LLAMA
0.0005
0.0651
0.0005
0.0056
1.6
90.0
Figure 2: Ablation experiments. Left: the effect top-k sampling on the Planar and SBM datasets.
Right: the validation loss and VUN scores when using SET and SENT on the Planar dataset.
4.4 Ablation Experiments
In this study, we aim to understand the effectiveness of the key components in AUTOGRAPHL
Comparison of sequence model architectures. AUTOGRAPH provides novel framework for evaluating the capability of current LLM architectures in graph generation and, more broadly, in structural reasoning tasks. In Table we compare several of-te-of-the-ar architectures on the Planar dataset, including GPT-2 (54), Mamba [25]. and LLaMA 633 While all models achieve comparable MMD ratios, transformer-basee architectures, particularly LLaMA, demonstrate significantly better performance in terms of VUN scores compared to state-space models. These findings highlight the potential of AUTOGRAPII to serve as a valuable benchmark for assessing sequence/language models' capabilities in graph generation tasks.
Effect of top-k sampling. key advantage of AUTOGRAPH over diffusion- based approaches the flexibility to apply top-k sampling (2I) during inference, which can improve generation quality. As shown on the left of Figure [ a smaller improves the VUN score on the Planar dataset, whereas is not beneficial on the SBM dataset. In contrast, increasing k generally improves MMD ratios on both datasets. These results suggest that top-k sampling can optimized based on dataset characteristics. In our experiments, we select the best & that maximizes the VUN score for small synthetic datasets and minimizes the validation MMD ratios for other datasets. This flexibility allows practitioners to select k based on specific performance criteria they aim to prioritize.
Comparison of SET and SENT. As discussed in Section 2 SENT is preferred over SET for graph generation, as incorporating neighborhood information is essential to ensure structural coherence. To empirically validate this, we compare the performance of SENT and SET on the Planar dataset and present the training curves on the right of Figure 2 Consistent with our theoretical analysis, SET fails produce high-validity graphs, resulting VUN score close zero, whereas SENT successfully generates valid planar graphs.
Conclusion
We proposed AUTOGRAPH, scalable and efficient autoregressive model for attributed graph genera- tion that handles large graphs while maintaining high quality. Our approach enables substructure- conditioned generation without additional fine-tuning and demonstrates promising transfer capa- bilities. Crucially, 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-representtng a significant step toward applying language modeling techniques to graph generation and broader graph learning challenges.
Limitations. While AUTOGRAPH demonstrates strong scalability current graph generation benchmarks, we acknowledge that the datasets used our study remain relatively small-scale compared to those used in pre-training L.MMs. To push the boundaries of more powerful graph generative models or eventually foundation models for graphs, we draw the community's 's attention to building more comprehensive graph generation benchmarks and well-curated pre-training datasets.
10

---

Acknowledgements
The authors thank Dr. Till Hendrik Schulz, Philip Hartout, and Blažej Banaszewski for their insightful discussions and valuable feedback on the manuscript. The authors thank Dr. Till Hendrik Schulz for presenting the poster at NeurIPS, as the first author was unable to attend due to visa issue.
References
[1] Davide Bacciu, Alessio Micheli, and Marco Podda. Edge-based sequential graph generation with recurrent neural networks. Neurocomputing, 416:177-189 2020.
[2] Andreas Bergmeister, Karolis Martinkus, Nathanaël Perraudin, and Roger Wattenhofer. Efficient and scalable graph generation through iterative local expansion. In International Conference Learning Representations (ICLR), 2024.
[3] Norman Biggs, E Keith Lloyd, and Robin Wilson. Graph Theory, 1736-1936. Oxford
University Press, 1986.
[4] Aleksandar Bojchevski, Oleksandr Shchur, Daniel Zügner, and Stephan Günnemann. Netgan: Generating graphs via random walks. In International Conference on Machine Learning (ICML), pages 610-619, 2018.
[5] Mare Brockschmidt, Miltiadis Allamanis, Alexander L Gaunt, and Oleksandr Polozov. Gener- ative code modeling with graphs In International Conference on Learning Representations (ICLR), 2019.
[6] Nathan Brown, Marco Fiscato, Marwin HS Segler, and Alain C Vaucher. Guacamol: bench- marking models for de novo molecular design. Journal of chemical information and modeling. 59(3):1096-1 1108, 2019.
[7] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Berbert-Vosss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners. In Advances in Neural Information Processing Systems (NeurIPS), volume 33, pages 1877-1901, 2020.
[8] Dexiong Chen, Laurent Jacob, and Julien Mairal. Convolutional kernel networks for graph- structured data. In International Conference on Machine Learning (ICML), pages 1576-1586, 2020.
[9] Dexiong Chen, Leslie O' O'Bray, and Karsten Borgwardt. Structure-aware transformer for graph representation learning. In International Conference on Machine Learning (ICML), pages 3469-3489 PMLR, 2022.
[10] Dexiong Chen, Till Hendrik Schulz, and Karsten Borgwardt. Learning long range dependencies on graphs via random walks. arXiv preprint arXiv:2406.0333 2024.
[11] Runjin Chen, Tong Zhao, Ajay Kumar Jaiswal, Neil Shah, and Zhangyang Wang. Llaga: Large language and graph assistant. In International Conference Machine Learning (ICML), pages 7809-7823. PMLR, 2024.
[12] Xiaohui Chen, Xu Han, Jiajing Hu, Francisco Ruiz, and Liping Liu. Order matters: Probabilistic modeling of node sequence for graph generation. In International Conference on Machine Learning (ICML), pages 1630-1639. 2021.
[13] Xiaohui Chen, Jiaxing He, Xu Han, and Liping Liu. Efficient and degree-guided graph generation via discrete diffusion modeling. In International Conference on Machine Learning (ICML), pages 4585-4610. 2023.
[14] Seyone Chithrananda, Gabriel Grand, and Bharath Ramsundar. Chemberta: large-scale self- supervised pretraining for molecular property prediction. arXiv preprint arXiv:2010.09885, 2020.
[15] Junyoung Chung, Caglar Gulcehre, Kyunghyun Cho, and Yoshua Bengio. Empirical evaluation of gated recurrent neural networks on sequence modeling. NIPS Workshop on Deep Learning, 2014.
11

---

[16] Hanjun Dai, Azade Nazi, Yujia Li, Bo Dai, and Dale Schuurmans. Scalable deep generative modeling for sparse graphs. In International Conference on Machine Learning (ICML), pages 2302-2312, 2020.
[17] Prafulla Dhariwal, Heewoo Jun, Christine Payne, Jong Wook Kim, Alec Radford, and Ilya Sutskever. Jukebox: generative model for music. arXiv preprint arXiv:2005.00541, 2020.
[18] Nathamiel Lee Diamant, Alex M Tseng, Kangway V Chuang, Tommaso Biancalani, and Gabriele Scalia. Improving graph generation by restricting graph bandwidth. In International Conference on Machine Learning (ICML... PMLR, 2023.
[19] Reinhard Diestel. Graph Theory. Electronic library of mathematics. Springer, 2005.
[20] Paul D Dobson and Andrew J Doig. Distinguishing enzyme structures from non-enzymes without alignments. Journal of molecular biology, 330(4):771 2003.
[21] Angela Fan, Mike Lewis, and Yann Dauphin. Hierarchical neural story generation. In Pro- ceedings of the Annual Meeting of the Association for Computational Linguistics (ACL), pages 889-898, 2018.
[22] Bahare Fatemi, Jonathan Halcrow, and Bryan Perozzi. Talk like graph: Encoding graphs for large language models. In International Conference on Learning Representations (ICIR), 2024.
[23] Nikhil Goyal, Harsh Vardhan Jain, and Sayan Ranu, Graphgen: A scalable approach to domain- agnostic labeled graph generation. In Proceedings of The Web Conference, pages 2020.
[24] Arthur Gretton, Karsten M Borgwardt, Malte J Rasch, Bernhard Schölkopf, and Alexander Smola. A kernel two-sample test. Journal of Machine Learning Research (JMLR), 13(1): 723-773, 2012.
[25] Albert Gu and Tri Dao. Mamba: Linear-time sequence modeling with selective state spaces. arXiv preprint arXiv:2312.00752. 2023.
[26] Aric Hagberg, Pieter Swart, and Daniel A Schult. Exploring network structure, dynamics, and function using networkx. Technical report, Los Alamos National Laboratory (LANL), Los Alamos, NM (United States), 2008
[27] Emiel Hoogeboom, Victor Garcia Satorras, Clément Vignac, and Max Welling. Equivariant diffusion for molecule generation in 3d. In International Conference Machine Learning (ICML), pages 8867-8887, 2022.
[28] Rongjie Huang, Mingze Li, Dongchao Yang, Jiatong Shi, Xuankai Chang, Zhenhui Ye, Yuning Wu, Zhiqing Hong. Jiawei Huang, Jinglin Liu, et al. Audiogpt: Understanding and generating speech, music, sound, and talking head. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 23802-23804, 2024.
[29] John Ingraham, Vikas Garg. Regina Barzilay. and Tommi Jaakkola. Generative models for graph-based protein design. In Advances Neural Information Processing Systems (NeurIPS), volume 32, 2019.
[30] Sergey Ivanov and Evgeny Burnaev. Anonymous walk embeddings. In International Conference on Machine Learning (ICML), 2018
[31] Shashank Mohan Jain. Hugging face. In Introduction to transformers for NLP: With the hugging face library and models to solve problems, pages 51-67. Springer, 2022.
[32] Yunhui Jang, Seul Lee, and Sungsoo Ahn. A simple and scalable representation for graph generation. In International Conference on Learning Representations (ICLR), 2024.
[33] Wengong Jin, Regina Barzilay, and Tommi Jaakkola. Junction tree variational autoencoder for molecular graph generation. In International Conference on Machine Learning (ICML). 2018.
[34] Jachyeong Jo, Seul Lee, and Sung Ju Hwang. Score-based generative modeling of graphs via the system of stochastic differential equations. In International Conference on Machine Learning (ICML). pages 10362-10383, 2022.
[35] Jachyeong Jo, Dongki Kim, and Sung Ju Hwang. Graph generation with diffusion mixture. In International Conference on Machine Learning (ICML.). PMLR, 2024.
[36] Mahdi Karami. Higen: Hierarchical graph generative networks. International Conference on Learning Representations (ICLR), 2024.
12

---

[37] Jinwoo Kim, Olga Zaghen, Ayhan Suleymanzade. Youngmin Ryou, and Seunghoon Hong. Revisiting random walks for learning on graphs. arXiv preprint (xXiv:447.002214 2024.
[38] Thomas N Kipf and Max Welling. Variational graph auto-encoders. arXiv preprint arXiv:1611.07305 2016.
[39] Lingkai Kong, Jiaming Cui, Haotian Sun, Yuchen Zhuang, B Aditya Prakash, and Chao Zhang. Autoregressive diffusion model for graph generation. In International Conference on Machine Learning (ICML), pages 17391-17408, 2023.
[40] Markus Krimmel, Jenna Wiens, Karsten Borgwardt, and Dexiong Chen. Towards fast graph generation via autoregressive noisy filtration modeling. arXiv preprint arXiv:2502.02411 2025.
[41] Youngchun Kwon, Dongseon Lee, Youn-Suk Choi, Kyoham Shin, and Seokho Kang. Com- pressed graph representation for scalable molecular graph generation. Journal of Cheminfor- matics, 12:1-8, 8, 2020.
[42] Yujia Li, Oriol Vinyals, Chris Dyer, Razvan Pascanu, and Peter Battaglia. Learning deep generative models of graphs. arXiv preprint arXiv:/803.083: 03324, 2018.
[43] Renjie Liao, Yujia Li, Yang Song, Shenlong Wang, Will Hamilton, David K Duvenaud, Raquel Urtasun, and Richard Zemel. Efficient graph generation with graph recurrent attention networks. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
[44] Jacchang Lim, Sang-Yeon Yeon Hwang, Scokhyun Moon, Seungsu Kim, and Woo Youn Kim. Scaffold-based molecular design with graph generative model. Chemical Science, 11(4): 1153-1164, 2020.
[45] Karolis Martinkus, Andreas Loukas, Nathanaël Perraudin, and Roger Wattenhofer. Spectre: Spectral conditioning helps to overcome the expressivity limits of one-shot graph generators. In International Conference on Machine Learning (ICML), pages 15159-15179, 2022.
[46] Krzysztof Maziarz, Henry Richard Jackson-Flux, Pashmina Cameron, Finton Sirockin, Nadine Schneider, Nikolaus Stiefl, Marwin Segler, and Mare Brockschmidt. Learning to extend molec- ular scaffolds with structural motifs. In International Conference on Learning Representations (ICLR), 2022.
[47] Rocío Mercado, Tobias Rastemo, Edvard Lindelöf, Günter Klambauer, Ola Engkvist, Hongming Chen, and Esben Jannik Bjerrum. Graph networks for molecular design. Machine Learning: Science and Technology, 2(2):025023, 2021.
[48] Grégoire Mialon, Dexiong Chen, Margot Selosse, and Julien Mairal. Graphit: Encoding graph structure in transformers. arXiv preprint arXiv:2/066 05667, 2021.
[49] Marion Neumann, Plinio Moreno, Laura Antanas, Roman Garnett, and Kristian Kersting, Graph kemnlss for object category prediction in task lask-dependent robot grasping. In Online proceedings of the eleventh workshop on mining and learning with graphs, pages 0-6, ACM Chicago, Illinois, USA, 2013.
[50] Giannis Nikolentzos and Michalis Vazirgiannis. Random walk graph neural networks. In Advances in Neural Information Processing Systems (NeurIPS), volume 33, pages 16211- 16222, 2020.
[51] Chenhao Niu, Yang Song, Jiaming Song. Shengjia Zhao, Aditya Grover, and Stefano Ermon. Permutation invariant graph generation via score-based generative modeling. In International Conference on Artificial Intelligence and Statistics (AISTATS). pages 4474 4484, 2020.
[52] Leslie O' Bray,, Max Horn, Bastian Rieck, and Karsten M. Borgwardt. Evaluation metrics for graph generative models: Problems, pitfalls, and practical solutions. In International Conference on Learning Representations (ICLR), 2022.
[53] Daniil Polykovskiy, Alexander Zhebrak, Benjamin Sanchez-L Sergey Golovanov, Oktai Tatanov, Stanislay Belyaev, Rauf Kurbanov, Aleksey Artamonov, Vladimir Aladinskiy, Mark Veselov, et al. Molecular sets (moses): a benchmarking llltllllalnnl platform for molecular generation
models. Frontiers in pharmacology, 11:565644, 2020.
[54] Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al. Language models are unsupervised multitask learners. OpenAl blog. 188):9 2019.
[55] Robin Rombach, Andreas Blattmann, Dominik Lorenz, Patrick Esser, and Björn Ommer. High- resolution image synthesis with latent diffusion models. In Proceedings of the Conference on Computer Vision and Pattern Recognition (CVPR), pages 10684-10695, 2022.
13

---

[56] Noam Shazeer. Glu variants improve transformer. arXiv preprint arXiv:2002.0522,, 2020.
[57] Chence Shi, Minkai Xu, Zhaocheng Zhu, Weinan Zhang, Ming Zhang, and Jian Tang. Graphaf: a flow-based autoregressive model for molecular graph generation. In International Conference on Learning Representations (ICLR), 2020.
[58] Martin Simonovsky and Nikos Komodakis. Graphvae: Towards generation of small graphs using variational autoencoders. In International Conference on Artificial Neural Networks, pages 412-422, 2018.
[59] Jianlin Su, Murtadha Ahmed, Yu Lu, Shengfeng Pan, Wen Bo, and Yunfeng Liu. Roformer: Enhanced transformer with rotary position embedding. Neurocomputing. 568:127063 170633, 2024.
[60] Rylee Thompson, Boris Knyazev, Elahe Ghalebi, Jungtaek Kim, and Graham W Taylor. On evaluation metries for graph generative models. In International Conference on Learning Representations (ICLR), 2022.
[61] Keyu Tian, Yi Jiang, Zehuan Yuan, Bingyue Peng, and Liwei Wang. Visual autoregressive mod- cling: Scalable image generation via next-scale prediction. In Advances in Neural Information Processing Systems (NeurIPS), 2024.
[62] Jan Tönshoff, Martin Ritzert, Hinrikus Wolf, and Martin Grohe Walking out of the weisfeiler leman hierarchy: Graph learning beyond message passing. Transactions on Machine Learning Research (TMLR), 2023.
[63] Hugo Touvron, Thibaut Lavril, Gautier Izacard. Xavier Martinet, Marie-Anne Lachaux, Timo- thée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al. Llama: Open and efficient foundation language models. arXiv preprint arXiv:2302. 2023.
[64] Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. Llama 2: Open foundation and fine-tuned chat models. arXiv preprint arXiv:2307.0922: 2023.
[65] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez. Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Informa- fion Processing Systems (NeurIPS), 2017.
[66] Clément Vignac, Igor Krawczuk, Antoine Siraudin, Bohan Wang, Volkan Cevher, and Pas- cal Frossard. Digress: Discrete denoising diffusion for graph generation. In International Conference Learning Representations (ICLR), 2023.
[67] Yanbang Wang, Yen-Yu Chang, Yunyu Liu, Jure Leskovec, and Pan Li. Inductive representation learning in temporal networks via causal anonymous walks. arXiv preprint arXiv:2101.05974, 2021.
[68] Zhenqin WU, Bharath Ramsundar, Evan N Feinberg, Joseph Gomes, Caleb Geniesse, Aneesh Pappu, Karl Leswing, and Vijay Pande. Moleculenet: a benchmark for molecular machine learning. Chemical science, 9(2):113-530, 2018.
[69] Zhe Xu, Ruizhong Qiu, Yuzhong Chen, Huiyuan Chen, Xiran Fan, Menghai Pan, Zhichen Zeng, Mahashweta Das, and Hanghang Tong. Discrete-state continuous-time diffusion for graph generation. In Advances in Neural Information Processing Systems (NeurIPS), 2024.
[70] Haoteng Yin, Muhan Zhang, Yanbang Wang, Jianguo Wang, and Pan Li. Algorithm and system co-design for efficient subgraph- based graph representation learning. Proceedings of the VLDB 2022.
Endowment, 15(1 (((11):22
[71] Jiaxuan You, Rex Ying, Xiang Ren, William Hamilton, and Jure Leskovec. GraphRNN: Generating realistic graphs with deep auto-regressive models. In International Conference on Machine Learning (ICML), 2018.
[72] Biao Zhang and Rico Sennrich. Root mean square layer normalization. In Advances in Neural Information Processing Systems (NeurIPS), volume 32, 2019.
[73] Lingxia Zhao Xueying Ding, and Leman Akoglu. Pard: Permutation-invarian autoregres- sive diffusion for graph generation. In Advances in Neural Information Processing Systems (NeurIPS), 2024.
[74] Qifang Zhao. Weidong Ren, Tianyu Li, Xiaoxiao Xu, and Hong Liu. Graphgpt: Graph learning with generative pre-trained transformers. arXiv preprint arXiv:2401.00529, 2023.
14

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
The claims are fully justified in our theoretical and empirical results in Section and
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
The limitations are discussed in Appendix
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
15

---

Justification:
The background for the theoretical results is provided in Section C.1 The full set of assumptions and complete proofs is provided in Appendix D
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: Experimental details, including dataset description, evaluation metrics, com- puting details, and hyperparameter choices, are provided in Appendix E full code upon publication.
We will release the
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
16

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes)
Justification:
We will release the full code and documentation upon publication.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ ptaip..cc/ubblic/guu.ee CoodeSumeeieeeeee ssi iessonPolll molyicyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: All the training and test details are provided in Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: While reporting error bars is not yet standard in the field of graph generation, we report the error bars on small synthetic datasets in Appendix F. to mitigate the impact of small test sample size.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
17

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma enror bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: Computing details are provided Appendix E.3 Runtime to reproduce some experiments is given in Section
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics httts::///urrrr: http://pp...pppblle.caeecccceada
Answer: [Yes]
Justification: The research conducted in this paper conforms with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
The paper discusses both aspects in Appendix
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
18

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied partieular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (c.g., gated release models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: Our work focuses on generative modeling for general graphs, but does not release ready-to-use models for real-world applications.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We have properly cited the code, data, and models used in this study (see Appendix E.I
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
19

---

If assets are released, the license, copyright information, and terms of use in the thcode. has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, batasets.papersstt paperswi
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is available online, the authors encouraged to reach out the asset's s creators.
13. New assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: The new NetworkX dataset and its generation is fully documented in Ap- pendix E.I It conforms with the License of the NetworkX library.
Guidelines:
The answer NA means that the paper does not release assets.
Researchers should communicate the details of the dataset/code/mooel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
This work does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
This work does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
20

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology. scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core method development this research does involve LLMs.
Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy bettts://neurre /0tps//eec.ooooeeeeee////2////// for what should or should be described.
21

---

Appendix
This appendix provides both theoretical and experimental materials. It is organized as follows: Section Section(A|pron provides additional background on sequence models. Section B provides discussion about the broader impact of this work. Section [ provides additional details and remarks on our method. Section D provides proofs for the theorems presented in the main manuscript. Section E provides experimental details. Section F provides additional quantitative and qualitative results.
A Background on Sequence Model Architectures
Our sequence model architectures are fully based on established natural language models. In particular, we consider three prominent models, including GPT-2 [54], LLaMA [63] [4]] and Mamba [25] to demonstrate the effectiveness of our approach. Notably, our methodology not restricted these specific models; it can be applied to any sequence or language model.
GPT-2. GPT-2 represents one of the earliest large language models based on the transformer architecture 655 The model employs pre- rreenormalizatinn with LayerNorm, the GeLU activation function, and absolute positional embeddings to encode token positions sequences. These design choices laid the foundation for many subsequent models.
LLaMA. LLaMA 64 builds upon the transformer framework with several key enhancements. It incorporates pre-normalization through RMSNorm (72) and employs the SwiGLU activation function [56). Additionally, LLaMA replaces absolute positional embeddings with rotary positional
embeddings (59 enabling better generalization to longer sequences.
state-space model (SSM) that maps input sequences to outputs using contiuuus-timm dynamics. It introduces selection mechanism that dynamically controls how input data flows into hidden states, making the model parameters adaptive to time and data. This innovation enables Mamba to achieve superior performance compared other SSMs across various tasks.
Mamba. Mamba 25
B Broader Impacts
Our research focuses on advancing the algorithmic development of graph generative models, strongly emphasizing their responsible and ethical application in specialized fields. In domains such drug discovery and synthetic biology, ensuring the trustworthiness and appropriate use of our methods essential prevent potential misuse. Through our experiments, we showcase the potential of our approach in these fields, underscoring its promise to deliver meaningful societal benefits while acknowledging the need to address potential risks.
Additional Details about AUTOGRAPH
C.1 Background on Graph Theory
We provide additional background graph theory necessary for the definitions and theories of SETs and SENTs. The background is largely based on Diestel [19
We first give the formal definition of graph isomorphism:
Definition C.1 (Graph isomorphism). An isomorphism of graphs G and H is a bijection between the vertex sets G and H: π Va - Vи such that any two vertices and of G are adjacent in and only if π (u) and π (w) are adjacent in H, ie., (u, v) E EG if and only if (I(4), x (v)) E F
Graph isomorphism is an equivalence relation on graphs and such it partitions the class of all graphs into equivalence classes. A set of graphs isomorphic to each other is called an isomorphism
22

---

class of graphs. is worth noting that our SENT isomorphism also partitions the class of all SENTs into equivalence classes in a similar fashion.
We also provide the formal definition of induced subgraph:
Definition C.2 (Induced subgraph). An induced subgraph of graph is another graph, formed from subset of the vertices of the graph and all of the edges, from the original graph, connecting pairs of vertices in that subset. Formally, let S S VG be any subset of vertices of Ec). Then, the induced subgraph G[S] is the graph whose vertex set is S and whose edge set consists of all of the edges in Eg that have endpoints in S. That is, for any two vertices u, E S, (u, v) Egis) if and only if (u, v) E Eg.
C.2 Remarks Tokenized SENTs
we showed that an (ordered) SENT can be converted into a sequence of tokens. Here, we extend this idea by interpreting the tokenized sequence as random walk on slightly modified graph. We first introduce an alternative tokenization scheme that is equivalent to the one described earlier but offers enhanced interpretability. The proposed tokenization remains largely unchanged except for how tuples are handled. For each w (v, A) with A {uI,.... UpJ. we now define
In Section 2.4
Token(w): :- [V, <, W <, U2..., <, Up: >|.
We now detail how to modify the original graph G: we introduce three virtual nodes, labeled I, <. and > respectively. These virtual nodes are connected to all other virtual nodes and original nodes in the graph. This modification ensures that for any non-special token in the tokenized sequence, its subsequent token can either be one of its neighbors or one of the virtual nodes (/, <, or >). Consequently, each token has direct connection to the node corresponding to the current token, and the language model amounts to learning the state transition functions for these random walks. Since these random walks are non-Markovian, this perspective further justifies choice of using autoregressive models instead of one-step generative models. Furthermore, as random walks are random sequences graphs, sampling random walks amounts sampling from those random sequences.
C.3 Remarks on Model Inference
The model inference is straightforward following the same process as LLMs such as LLaMA 63 64] alternative way is to enforce the semantic correctness of the generated sequences of tokens by adjusting the logits at certain token to obey the semantic rule of the tokenization. For instance, the token '>' can only occur after token '<' or no special tokens can appear right after /. We manually implemented these transition constraints and incorporated them into the inference. We compared this strategy with the constraint-
counterpart. Surprisingly, our experiments demonstrate that the constraint-free variant could always generate semantically correct sequences and perform similarly to the one with the transition constraints on unattributed graphs. Therefore, we did not use any transition constraints during the inference in unattributed graph experiments. On the other hand, for attributed graphs, we found that the constraint-frs decoding might generate semantically incorrect sequences. As a consequence, we used constrained decoding in all molccular generation experiments. In practice, we recommend using constrained decoding for attributed and complex graphs.
D Proofs
In this section, we provide proof for the theorems stated in the manuscript.
Theorem 2.5. For any SETs s, t E S, their generated graphs are isomorphic, i.e., G2 ~ Gy, = Conversely, if two graphs G ~ H, then for any SET E Sc. there exists a SET t Sy s.t. ~ t.
Proof of Theorem 2.5 By definition of the isomorphism between s and f, there exists a bijection V, V s.t. T(s) t. Now if u, v E V, are adjacent in G,, Le.. (u, v) E Eg, then (I(n), T())) is
an edge visited by x (s) ()) = t, thus (u), ((v)) E E,, Similarly, the reverse is also true. Consequently, G, G..
Now assume that G H with an isomorphism N and E Sg. It is easy to show that (()) is also a SET and its generated graph Gx(e) H. By taking rT(s, obtain the result.
23

---

Lemma 2.8. For any graph G and SET s in G, the generated graph of any prefix of is a subgraph of G. but not necessarily an induced subgraph.
Assume that is prefix of Then V, S V. = Va and E, S Eg. However, G. is not necessarity an induced subgraph of G,. We consider the following counter-example (1,2,3. 4, 1,3)), V, = {1, 2, 3, 4), and E, = {(1, 2), (2, 3). (3, 4), (1, 4), (1,3)). Let t ((1,2,3, 3, 4, 1)). t is clearly a prefix of 8, but its generated graph is not an induced subgraph of G, as its generated edge set does contain (1.
Proof of Lemma 2.8
Theorem 2.14. For any causal SENT s E SN, the generated graph of any prefix of is an induced subgraph of G. if and only if s is amii-hamiltonia. In this case, 8 is called mubgraph-induccee
Let first introduce some notations. We denote by R2 the sequence of the start tuples across all neighborhood trails in s, which is also a neighborhood sequence. By definition of sami-hamiltonian, the occurrences after the first time of node in s should be in Rg. We denote by nss) the associated node sequence of SENT s, i.e., n(s)= == n[[ss).
Proof of Theorem 2.14
Let us first assume that is
Assume that is a prefix of s. It is easy to show that G2 is a subgraph of G,. Now assume that 2, E V s.f. (u, v) E Eg, we want to show that (u, v) E Et. There are two cases:
n(s) \ nn(t) either does not contain u u, or even if one of them, say u E n(()) ni(t, we have u E n R2)) and its associated neighhorhood set is empty. In both cases, the edge (u, v) does not belong to the generated edge set of the neighborhood subsequence after |tt. By the disjointness of the generated edge sets of s, it can only be included in the generated edge set of t, we thus have (u, v) E Er.
1) Assume that u, v n(t) Since is semi-hamiltonin
2) Assume that one of them, say u & ntt). There exists a neighborhood set A in a tuple of ||t such as A. Since t is causal, we have E n(t) which contradicts the assumption.
In all the above cases, we have (u, v) E E,,
Now let us assume that the generated graph of any prefix of s is an induced subgraph of G.- Let us prove that s is semi-
by contradiction. Assume that there exist two tuples in ||s with the same nodes s; = (v, A.) and 8; = (v, Ag) with <.j. There are two cases: 1) 8j & Rg. A tuple (u, Au) exists one step before sj in the same neighborhood trail. We consider the prefix t ending at (u, A.). We have v, u E V/ and (u, v) E E., but (u, v) & E,, by the disjointness of s and since (u, v) is visited at s, after t. 2) s, & R2 and Ay # 6. Since is causal, there exists su (u, Au) before 8j s.f. u E Aj. We consider the prefix t ending at exactly this tuple. We have u, u E V22 and (u, v) E Eg but (u, v) $ Ec, by the disjointness of s and since (u, v) is an edge visited at (v. Ay) after t.
Theorem 2.15. For s E SN. is causal and Hamiltonian if and only if every tuple w == (v, A,) in I|s satisfies A, = (a n V. (w). In this case, every node is visited exactly once. Moreover, is causal and semi-hamiltonian if and only every upple w == (v., An) in s satisfies either A, = -Vc())VV..())) or A, = 0.
Proof of Theorem 2.15 Let us first assume that for any tuple w == (v, in [|s, A. = Na(()) n (w).. Since A, (ww) which is subset of the set of visited nodes, is causal. Now prove 8 is Hamiltonian by contradiction. Assume that there exist two tuples in ||x, 8u == (u, Aw) and a
later visited one s, : (v, A,) s.f. v. Then, A, NNo(v) Vs.ss) Na(uu) Va(s)) should contain the node visited before that is a neighbor of u (either through trail or the neighborhood set of u). denoted by u'. Thus, the edge (u, u') has been visited twice, which contradicts the disjointness of s.
Assuming that A, NN(()) n Vw( or A, = 0 for any tuple (v, A.,) in we can also prove is hami-hamittonian by contradiction. Assume that there exist two tuples in [|s, Su == (u, A,) and later visited one 8. := (v, A.) s.t.
and A. * 0. Then, A, No n (s.) = No(u)) n V.(ss) by assumption. And using the same argument as above, we have a contradiction.
Now assume that is causal and Hamiltonian. Let us prove the other direction by contradiction. There exists a tuple u: := (v, A.) in s.t. A, # VV As s is causal, A, C (w)). A, S (V) as Sg. Thus, A, c No(e) n (w), which means that there exists u E NNa(v) n (w) and
24

---

& A.. Hence. (u, v) Eg and u is visited before v. However, as u & Au, (u, v) E Ec, and is Hamiltonian, there exists a tuple (u, A,,) in ||s s.t. v E Au. By causality of s, v visited before u. which contradicts the fact that is Hamiltonian.
Assuming that s is causal and cemi-hamiltonian. Let prove the other direction by contradiction. There exists a tuple w := (v, Ag) in s s.t. Av * NC(u)) n Va(w) and A, # 0. Using the same arguments as above, there exists (u, v) Eg, and is visited before v. However, u & A, and (u, E Eg, s should visit the edge (u, v) at some point. Since is semi-hamilonian,, if 8 visits again u, they can only be the first nodes and their associated neighborhood sets are empty. Hence, there is no means for s to visit (u, u) after leading to a contradiction.
E
Experimental Details
E.1
Datasets
We provide details of the datasets used in our experiments. We adopt the standard train/validationntesst splits provided in the original sources. The statisties about the datasets are summarized in Table [
Small synthetic graphs: Planar and SBM. Both of these datasets are from Martinkus et al. 45]. The Planar dataset consists of 200 planar graphs with 64 nodes each, generated via Delaunay triangulation on points uniformly sampled in the unit square. The SBM dataset contains 200 graphs comprising 2 to 5 communities, with each community having between 20 and 40 nodes. edge is placed between two nodes with probability 0.3 if they belong to the same community, and 0.05 otherwise. We follow the same splits as Martinkus et al. (45)
Large graphs: Proteins and Point Clouds. The Proteins dataset includes graph representations (contact maps) of proteins from Dobson and Doig 20 In these graphs, each node represents an amino acid, and an edge connects two nodes if their corresponding amino acids are within 6 angstroms of each other. We use the same data splits as Liao et al. [4]. The Point Clouds dataset, also from Liao et al. [43], consists of 41 point clouds of household objects [49]. As many of these graphs are disconnected, we retain only the largest connected component of each, following Bergmeister et al.
2 and again employ the splits used by Liao et al. 43
QM9.
The QM9 dataset, from Wu al. 668. comprises small molecules with up to nine heavy atoms (carbon, oxygen, nitrogen, and fluorine). In this work, we adopt the more challenging setting proposed by Vignac et al. [66], where hydrogen atoms are modeled explicitly, and we follow the same data splits as in that reference.
MOSES and GuacaMol. The MOSES and GuacaMol datasets are obtained from the respective benchmark tools of Polykovskiy al. [53] and Brown et al. [6]. Both consist of drug-like molecules, with those in GuacaMol typically being larger on average. For each dataset, we convert generated molecular graphs to SMILES using the code from Jo et al. [34], which permits partial charges. We employ the standard data splits provided by the corresponding benchmarks.
PubChem-10M. 10C is subset of about 10M molecules from PubChem curated by Chithrananda et al. [14].
NetworkX. We generate the graphs using the generators from the NetworkX library? 126]. cate- gories including "Classic", "Lattice", "Small", "Random Graphs", "Geometric", "Trees". "T "Commu- nity". "Social Networks". We ensure that this dataset does not contain any graphs in the downstream datasets. The summary of the code for generating these graphs is provided in Table 9 Notably, the largest graph has up 5999 nodes.
E.2 Evaluation Metrics
We follow Martinkus et al. 45 and Vignac et al. [66] in comparing our model's performance with other graph generative approaches. Specifically, we measure the maximum mean discrepancy (MMD)
25

---

Table 8: Dataset statistics
DATASET
Rggaaps VAL
V Imax
Vlav
[|] max
[ avg
TRAIN
TEST
UNATTRIBUTED GRAPHS
PLANAR
128
32
40
64
64
181
178
SBM
128
32
40
187
104
1129
500
PROTEINS
587
147
184
500
258
1575
646
POINT CLOUDS
26
8
5037
1332
10886
2971
ATTRIBUTED GRAPHS
QM9
97734
20042
13055
29
18
28
19
MOSES
1584663
176225
176074
27
22
31
23
GUACAMOL
1118633
69926
209654
28
88
PRE-TRAINING UNATTRIBUTED GRAPHS
NETWORKX
24957
2516
5999
459
5999
751
Table 9: Summary of the code for generating graphs in the NetworkX dataset
GENURATOR
PYTION Cope:
CAVEGORY: CLASSIC
BALANCIE THEE:
10
hal ancln toww (2, randos candint 10))
BARBELL GRAPH
100
barbell, graph randon, randint 31), hap.raads...addieen randinn)addd))(413
BINGMIAL TREE
10
na binoxial cree (ap. rander. randiaz12, 91)
COMPLITED ITTE GRAPH
10
wtre.. cirmulrr, ludder .rwphhggghhheeo randus randint 50:3]
randor, randin:(S, 313)
CIRCULAR LADDER GRAPI
300
CYCLE GRAPH
2000
mx.cyyll
randon r10, 6001))
DOROGOVISEY GOLTSEN MENDES GRAPH
ax. dorogovtsey, goltawy, asndes gwpph randon randizt 7))
LADDSR GRAPH
500
no, badder grrpphhpp.ppp...... randon, randins 1001))
LOI GRAPH
200
no. 1e1l poggppraph (np. rander randine(S, 21), rw..nno.randddnn(10... 51))
STAR GRAPH
200
nn graphh Eop. randon r10, 501))
TURAN GRAPH
100
tartarrn war.n.graahiiiiii... nandor rudiat (10, 4:), sheel..graphie randon. (19, 201))
WHEEL
100
CATEGDRY: LATTICKS
2D GRAPH
400
grrdd.2666.. wwt.:lattssssppplo.o.o wwwpstow..pppppp........ randon. randint 41), xp re-rrnsonrrnddint(.. 413)
warrddd2_ggppp pit.....apppppng randins(s, 31), ra.dend randins(s, 31)
TRIANGULAR EATTICE GRAPH
400
CAVEGORY: SALAEL
ALL LCF GRAPH
(GACH)
(ewthod) Q
CATEGDRY: RANDUM GRAPHS
ERDOS RENYI GRAPH
4000
ardos werddd___any..o. www.preaayaaaaa.. wwa.yi.grpphap...... randee. randiat (20, 101), 0.2)
RANDOM RECUUT API
2000
www.rrnnneepppe. wr.ggrpph(ppp randon, int
wwndon.choica((eee ([20,3000... (00]))
BARABASI ALBERT GRAPI
4000
st. barabarr. _albers (up. randers randirt (20, 501), sp.randon, randint 6))
RANDOM LOBSTIR
4000
randus, Jobalarr (8C, 0.7, 0.7)
CATEGORY: GROMETRIC
RANDOM GEOMETRIC GRAMI
5000
randon, paistrric grraphh randon. chuica (120, 122000,,.... .o.... 100]], 0.3)
WAXMAN GRAPH
2000
vaccan, gwwph/rrpheeeeee candos. choice (150, 130,,,,......................... 3000))
CATEGDRY: TRIESS
RANDOM UNLABELED TREE:
1000
rundon, unlabe abblled trwe randus (20, 50:3)
CATEGDRY: COMMUNITY
CONNECTED CAYEMAN GRAPH
300
connucucecc Led, cavezan, seveeaanggrahiiee graphhip. zundon. randiat 101), sp.randee.. randia: 5))
WINDMILL GRAPH
300
vindeil3, graph randon. r10 101), sp.razdes raadinnt E))
CAVEGORY: SOCIAL NETWORKS ALL SOCIAL NETWORKS
(BACH)
(method)
between the generated and test graphs for degree distribution, clustering coefficient, orbit counts, and spectrum. As a reference, we also compute these metrics on the training set and report the mean ratio across all properties
global indicator of statistical discrepancy between the generated samples and test samples. Note that for the Point Clouds dataset, which is defined by a k-nearest-neighhor structure, the degree MMD is always zero and is therefore excluded from the mean ratio. While utilize these metrics to maintain consistency with previous research, we acknowledge their limitations, particularly regarding arbitrary kernel hyperparameter selection, highlighted by O' D'Bray al. (52). Thompson et al. [60]. In short, MMD measures the distributional similarity between generated and real graphs. Lower MMD scores indicate that the generated graphs' statistics (e.g., degree, clustering coefficients) more closely match the training data.
We additionally track uniqueness and novelty: uniqueness is the fraction of generated graphs that not isomorphic to each other, and novelty is the fraction of generated graphs that are not isomorphic any training graph.
Below, we describe additional metrics specific to each dataset.
Planar and SBM.
Following Martinkus et al. 45 we report a validity score for synthetic datasets.
For Planar graphs, it verifies whether the generated graphs remain planar; for SBM graphs, it measures
26

---

how likely they are to be generated under the original SBM parameters. We integrate validity, novelty, and uniqueness into single metric, VUN, which measures the fraction of generated graphs that are simultaneously valid, novel, and unique. In short, VUN assesses sample quality.
QM9. For QM9, we report the validity, uniqueness, and novelty defined for general molecules, as described in the following paragraph. We also report atom stability and molecule stability as defined by Hoogeboom et al. [27] and Vignac et al. [66].
MOSES and GuacaMol. Since MOSES [53 and GuacaMol 6 benchmarking platforms, each comes with its own suite of metrics, which we use to evaluate our model. These include:
Validity: Proportion of molecules passing basic valeney checks.
Uniqueness: Proportion of generated molecules with distinet SMILES strings (indicating non-isomorphic structures).
Novelty: Proportion of generated molecules not present in the training set.
Filter score: Proportion of molecules passing the same filters used to create the test set.
Fréchet ChemNet Distance (FCD): Similarity measure between generated and training based learned neural embeddings.
SNN: Similarity to the nearest neighbor, computed via Tanimoto distance.
Scaffold similarity: Comparison of Bemis- scaffold frequencies.
KL divergence: Differences in the distributions of various physicochemical descriptors.
E.3
Computing Details
We implemented our sequence models using the model hub of Hugging Face. Users can easily test their preferred sequence or language models using our code. Experiments were conducted on shared computing cluster with various CPU and GPU configurations, including 16 NVIDIA H100 (80GB) GPUs. Each experiment was allocated resources a single GPU, along with CPUs and up to 48GB of system RAM. The run-time of each model was measured on single NVIDIA H100 GPU.
E.4 Hyperparameters
Unlike prior studies that adjust model sizes across datasets, we maintain a consistent model architec- ture and size throughout all experiments, specifically using the small GPT configuration (768 hidden dimensions, 12 layers, 12 attention heads). Training hyperparameters are aligned with established practices from popular LLMs such as GPT-3 7 and LLaMA [63]. We fix the context length to 2048 and use a batch size of 128 if possible, otherwise 64 for larger graphs. employ the AdamW optimizer with gradient clipping threshold of 1.0, weight decay of 0.1, and learning rate schedule with a linear warmup followed by cosine decay, peaking at 6e-4. The Adam W hyperparameters are set 3 (0.9, 0.95). Due to the small dataset sizes of previous benchmarks, we tune the only training hyperparameter dropout in {0, 0.5). and find the model achieves better validation loss with the value of 0.5 the small synthetic datasets. Each model was trained for 200000, 400000, or 800000 iterations, depending on the dataset size.
particular, we
Inference hyperparameters, including & (top-k sampling) and (temperature), are reported in Table 10 and analyzed detail Section F.5
F Additional Results
F.1
Additional Results on Synthetic Datasets
Due to the small number of samples in the Planar and SBM datasets, we observe significant variances evaluation metrics. order to mitigate the impact of the small test samples on the evaluation, we use trained models to generate samples with 10 different seeds and report the average metrics and error bars for DiGress, ESGG, and our AUTOGRAPH. For DiGress and ESGG, we use either pretrained models released by the authors, if available, or reproduced models using their officially
27

---

Table 10: Inference hyperparameters for each dataset.
W/O PRE-TRAINING
w/ PRE-TRAINING
DATASET
TOP-k
TEMPERATURE
TOP-k
TEMPERATURE
PLANAR
1.0
30
0.9
SBM
60
1.0
150
1.0
PROTEINS
40
1.0
30
1.05
POINT CLOUDS
60
1.0
20
0.9
NETWORKX
120
1.0
QM9
5
1.0
MOSES
5
1.0
GUACAMOL
5
1.0
Table 11: Performances on the Planar and SBM datasets with error bars
(a) Planar
MODEL.
DEG.
CLUS..
ORBIT
SPEC.
RATIO
VUN
DIGRESS
0.0003+0.000
0.0415#0 008
0.0056=0.000
0.0078=0.000
3.8
79.0+6.0
ESGG
0.0006=0.000 .0004
0.0434=0.01
0.0101=0.007
0.0091=0.00
6.3+4.0
90,5=5.6
AUTOGRAPH
0.0004=0.0003
0.053320.008
0.005=000004
1.006620.0009
1.6+0.5
80.326.8
(b) SBM
MODEL
DEG.
CLUS.
ORBIT
SPEC.
RATIO
VUN
DIGRESS
0.0013+0.0000 0009
0.0501+0. 0009
0.039340 01104
0.005320 0007
1,620.3
66.025.6
ESGG
0.0468+0.0m
0.0554+0.0015
0.0699#0 0051
0.0085#0.00
15.3+3.
16.0+4.7
AUTOGRAPH
0.008140.0051
0.0525#0.0015
0.0687+0.0136
0.0048=0.0011
3.941.6
88.3+4.7
released code repository. As shown in Table I1 the variances appear reasonable, and the conclusions remain the same.
F.2 Additional Results on molecular generation datasets
Due space constraints, provide results the QM9 dataset in Table 12 and additional metrics on the MOSES dataset in Table [3] It is worth noting that all results on MOSES and GuacaMol obtained using the benchmarking tools from the original works, which might rely outdated packages. For instance, using the latest FCD package gives FCD score of 94.7 for the pre-trained AUTOGRAPH.
Our results on all three benchmarks demonstrate the immense potential of AUTOGRAPH for molecular generation. The fact that AutoGraph, by learning from graph data alone, achieve validity scores competitive with these specialized models is a strong demonstration 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., low FCD score). From practical perspective, invalid 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 low practical interest, AutoGraph achieves superior overall balance.
its learning capabilities.
easily reject
Table 12: Benchmarking AUTOGRAPI on the QM9 dataset
QM9 WITH HYDROGEN ATOMS
Ogrppix
100K. IV max
29, [V loog 18
MODEL
VALIDÍ
UNIQUET
NOVELT
ArUM STABLET
Mol STABLET
DIGRESS
95.4
97.6
33.4
98.1
79.8
ALTOGRAPH
97.7
96.7
45.5
98.6
87.3
28

---

Table 13: Benchmarking AUTOGRAPH on the MOSES dataset
MOSES
Tgrappa
1.58M, IV max 27, [Vlvvg 22 22
MODEL
TYPE
VALIDT
UNIQUET
NOVEL1
FILTERST
FCD1
SNNJ
SCAFT
VAE JT-VAE GRAPHINVENT
SMILES
97.7
99.8
69.5
99.7
0.57
0.58
5.9
FRAGMENTS
100
100
99.9
97.8
1.00
0.53
10
GRAPH
96.4
99.8
95.0
1.22
0.54
12.7
DIGRESS
GRAPH
85.7
100
95.0
97.1
1.19
0.52
14.8
AUTOGRAPH
GRAPH
87.4
100
85.9
98.6
0.91
0.55
10.2
2.50
pro-mining pre-triziig
1.0
ger-triningg
2.25
2.00
0.8
Validation Loss
VUN
0.5
0.0
Training Step
Training
Step
Figure 3: Comparison of AUTOGRAPH with and without pre-training the Planar dataset with 50000 training steps. The model with pre-training converges clearly faster than the model without pre-training.
F.3 Transfer Performance of AUTOGRAPH
We provide here additional results for the transfer learning of AUTOGRAPH. We compare the training curves of AUTOGRAPH models with and without pre-training on the Planar datasets in Figure 3 The result suggests that the model with pre-training converges clearly faster.
For the transfer experiment on molecular generation, we first pre-train AUTOGRAPH on the PubChem- 10M dataset [14], and then fine-tune it on the GuacaMol dataset. In this experiment, we use richer node attributes including atom types, total number hydrogens, and formal charges.
F.4 Substructure Conditioned Generation
As presented in Section
test more extreme cases by replicating the same motif multiple times before initiating the conditional generation. Figure 4 5 and demonstrate non-curated samples generated by AUTOGRAPH (trained the GuacaMol dataset without any additional fine-tuning! conditioned on p copies of the same motif, where = 1,2, respectively.
To further showcase the flexibility of AUTOGRAPHI we conduct the same experiments for two different motifs: J.4-Dilyyroquinollne)] and b-(Trftuoromethy))aninnne This very relevant problem in drug discovery, usually termed linker design. The validity, uniqueness, and novelty for 1024 samples are respectively 97.4, 81.4, and 99,9. Visual examples are given in Figure
F.5
Additional Ablation Experiments
Impact of model size. Table 14 and Figure compare the impact of model size. Larger models demonstrate better VUN scores. In this work, we use LLaMA-S in all our experiments to balance the trade-off between performance and speed.
httpe::/pubchemm.net ncbi mlm www..iih... http://pwwmoomt.aaaiiiooonnnnnnn https://pubchem.. nebi. mlm. nih, nwt.govvcompoonnd// http://////rrffffooeeeeee lnniiine
29

---

Motif:
Figure 4: Substructure conditioned generation on one copy of the motif 1 d-iihyyrrouuiilline...
Motif:
2 X
Figure 5: Substructure conditioned generation on two copies of the motif 1 4-Dihydroquinoline.
F.6
Visualization of Graphs Generated by AUTOGRAPH
F.6.1 Results without Pre-training
provide visualization of non-curated samples generated by AUTOGRAPH without pre-training on all datasets in Figure 10 13
The results on NetworkX are illustrated in Figure [6 Node colors in unattributed graphs represent the eigenvectors associated with the second-smallest eigenvalues of the graph Laplacian.
14 and 15
30

---

Motif:
5 x
Figure 6: Substructure conditioned generation five copies of the motif 1 Liihyydrqquiiilin...
Table 14: Comparison of model size on the Planar dataset
MODEL
# PARAMS
CONFIGURATION
DEG.
CLUS
ORBIT
SPEC.
RATIO
VUN
LLAMA-XS
25.2M
LAYERS, $12 -0.0001
0.0570
0.0006
0.0063
1.0
60.0
LLAMA-S
113M
12 LAYERS, 768 DIMS
0.0005
0.0651
0.0005
0.0056
1.6
90.0
LLAMA-M
402M
24 LAYERS, 1024
0.0001
0.0340
0.0013
0.0064
1.4
82.5
F.6.2 Results with pre-training
We provide visualization of non-curated samples generated by AUTOGRAPH with pre-training (on the NetworkX dataset) trained on the non-attribted datasets including Planar, SBM, Proteins, and Point Clouds, illustrated Figure
20
31

---

Motifs:
HM
Figure 7: Substructure conditioned generation on two different motifs: LiiDiiyyrrquiinlline and D-TTrillorommchhyyaniinee
1.0
0.8
0.6
0.4
0.2
Llannexx
Jama-s
0.0
LJmma-m
150000
200000
Training Step
Figure 8: Comparison of model size on the Planar dataset: VUN score vs training steps. LLaMA-m appears suffer from overfitting and LLaMA-xs appears suffer from underfitting.
32

---

Figure 9; Non-curated samples generated by AUTOGRAPH (without pre-training) trained on the Planar dataset.
Figure 10: Non-curated samples generated by AUTOGRAPH (without pre-training) trained on the SBM dataset.
33

---

Figure 11: Non- con-curated samples generated by AUTOGRAPH (without pre-training) trained on the Proteins dataset.
Figure 12: Non-curated samples generated by AUTOGRAPH (without pre-training) trained on the Point Clouds dataset.
34

---

NH
OH
Figure 13: Non-curated samples generated by AUTOGRAPH (without pre-training) trained on the QM9 dataset.
Figure 14: Non-curated samples generated by AUTOGRAPH (without pre-training) trained on the MOSES dataset.
35

---

Figure 15: Non-curated samples generated by AUTOGRAPI (without pre-training) trained on the
GuacaMol dataset.
36

---

Figure 16: Non-curated samples generated by AUTOGRAPH trained on the NetworkX dataset.
37

---

Figure 17: Non-curated samples generated by AUTOGRAPH (with pre-training on the NetworkX dataset) trained on the Planar dataset.
Figure 18: Non-curated samples generated by AUTOGRAPH (with pre-training on the NetworkX dataset) trained on the SBM dataset.
38

---

Figure 19: Non-curated samples generated by AUTOGRAPH (with pre-training on the NetworkX dataset) trained on the Proteins dataset.
Figure 20: Non-curated samples generated by AUTOGRAPH (with pre-training on the NetworkX dataset) trained on the Point Clouds dataset.
39


Reviews:
[{"review_id": "8ceIRZmExB", "reviewer": "Reviewer_1phq", "summary": "This paper presents AUTOGRAPH, an autoregressive framework for generating graphs using decoder-only transformers. The core contribution lies in a reversible flattening procedure that transforms graphs into sequences, enabling the use of language modeling. The authors claim that this approach is scalable and demonstrate its effectiveness across various synthetic and molecular graph generation benchmarks.", "questions": "- **Clarification on token definition**: The paper states that graphs are “composed of tokens” (line 37) and that it “explicitly represents graphs as token sequences” (lines 230–232). Could you clarify what is meant by “tokens” in this context? For instance, GEEL [1] represents each edge as a token—arguably a more direct analogy to tokens in language modeling—without requiring specialized architectures. How does AUTOGRAPH’s node-based representation differ from or improve upon this? Additionally, what does it mean to “interpret the sequences as language” (lines 187–189)?\n- **Pre-training data scale**: The graph generation benchmarks used for training involve relatively small datasets to train LLMs. Was this data volume sufficient for pre-training a large model like LLaMA? How did you address the challenges posed by the limited scale of training data?", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "[Strengths]\n\n- The paper is clearly written and well-organized.\n- It provides comprehensive experimental evaluations across four general graph generation benchmarks and two molecular graph generation benchmarks.\n\n[Weaknesses]\n\n- **Overstatement of novelty**: The claim that “AUTOGRAPH establishes the first fundamental connection between graph and language modeling” (in the conclusion) appears overstated. Prior works such as [1,2,3] have already employed decoder-only transformers for attributed graph generation. In particular, GEEL [1] shares a similar motivation and framework to AUTOGRAPH.\n- **Omission of baseline metrics**: The omission of MMD metrics for GEEL in Tables 1 and 3 is concerning, especially since the original GEEL paper includes these values for the same benchmarks. Given that GEEL is a highly relevant work as it shares the same motivation and is a walk-based autoregressive graph generative model, its complete evaluation should be included for fair comparison.\n- **Insufficient implementation details**: Key implementation details are missing, such as which version of LLaMA was used, the number of training epochs, and whether the codebase will be made publicly available.", "was_revised": true, "final_justification": "The author rebuttal addressed my scores and I raised the score to borderline accept.", "rebuttal": "We thank the reviewer for their constructive feedback, which we believe will strengthen our paper. Below, we address each point in detail.\n\n> Overstatement of novelty\n\nWe 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**.\"\n\nWhile 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.\n\nTo summarize, our key novel contributions, particularly in contrast to GEEL, are:\n\n1. 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.\n    \n2. Our resulting sequence representation is the first to **directly support substructure conditioning via prompting**, aligning graph generation with language modeling capabilities.\n    \n3. 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.\n\nRegarding 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**.\n\n> Omission of GEEL's MMD metrics\n\nWe 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.\n\nFollowing 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.\n\nThe 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**.\n\n---\n**Planar**\n| Method       | Deg.   | Orbit  | Clus.  | Spec.  | VUN  | Novelty | Uniqueness |\n| ------------ | ------ | ------ | ------ | ------ | ---- | ------- | ---------- |\n| Training set | 0.0002 | 0.0310 | 0.0005 | 0.0038 | --   | --      | --         |\n| GEEL         | 0.0039 | 0.0013 | 0.0062 | 0.0234 | 0.0  | 0.0     | 90.0       |\n| AutoGraph    | 0.0004 | 0.0605 | 0.0003 | 0.0064 | 87.5 | 100.0   | 100.0      |\n\n---\n\n**SBM**\n| Method       | Deg.   | Orbit  | Clus.  | Spec.  | VUN  | Novelty | Uniqueness |\n| ------------ | ------ | ------ | ------ | ------ | ---- | ------- | ---------- |\n| Training set | 0.0008 | 0.0332 | 0.0255 | 0.0027 | --   | --      | --         |\n| GEEL         | 0.0106 | 0.0616 | 0.0023 | 0.0381 | 5.0  | 7.5     | 87.5       |\n| AutoGraph    | 0.0077 | 0.0519 | 0.0439 | 0.0040 | 92.5 | 100.0   | 100.0      |\n\n---\n**Proteins**\n| Method       | Deg.   | Orbit  | Clus.  | Spec.  | Novelty | Uniqueness |\n| ------------ | ------ | ------ | ------ | ------ | ------- | ---------- |\n| Training set | 0.0003 | 0.0068 | 0.0032 | 0.0005 | --      | --         |\n| GEEL         | 0.2110 | 0.3753 | 0.1768 | 0.1689 | 84.6    | 100.0      |\n| AutoGraph    | 0.0004 | 0.0244 | 0.0056 | 0.0013 | 100.0   | 100.0      |\n\n---\nThese 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.\n\n> Insufficient implementation details\n\n**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.\n\nQuestions:\n\n> Clarification on token definition\n\nWe 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.\n\nUnlike 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.\n\n> Pre-training data scale\n\nOur 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.\n\nIn 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."}, {"review_id": "nL2wzCmzfV", "reviewer": "Reviewer_un17", "summary": "This paper is focused on the topic of graph generation using Transformers and uses an existing principle of recent interest that transforms graphs to sequences. It presents AUTOGRAPH, an autoregressive graph generation framework that converts graphs into token sequences to enable direct use of decoder-only Transformers for efficient and scalable generation. The key to their approach in this paper is the concept of Segmented Eulerian Neighborhood Trails (SENTs) which is a reversible graph to sequence transformation that preserves topological structure while producing token sequences applicable or similar to language modeling. This method also ensures subgraph-aware information. The paper demonstrates the effectiveness of AUTOGRAPH on synthetic and molecular benchmarks, showing improved efficiency, performance gains, and support for substructure-conditioned generation without fine-tuning. As such, this work aims to bridge the gap between graph generation and language modeling and perhaps addresses improvements on methods concerned with flattening graphs to sequences which can be well-defined and lossless.", "questions": "- Can the proposed SENT based graph to sequence representation be adapted for general graph modeling/understanding/downstream tasks (e.g., classification, regression)?\n- 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?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n- A key strength of this paper is their progress on graph to sequence conversion methods which has been of much interest in recent literature. \n- The flattening/tokenization process involves a more principled encoding using eulerian trails where each token corresponds to a structurally interpretable graph event. This is in contrast to multiple prior works which may use heuristics, neighborhood or hop encoding and templates that are manually engineered and target for use of those sequences as prompts in LLMs.\n- The SENT sequences based method provides improved validity in graph generation.\n- The construction of SENT sequences are transparent and interpretable, and is complemented with theoretical analysis.\n- The proposed method achieves significantly faster inference and training speedups compared to previous methods.  \n\nWeaknesses:\n- The paper includes an extension of SENT tokenization to (discrete) attributed graphs, but many graph tasks may be non-discrete features.\n- 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.\n- Closely related recent works on graph to sequence methods such as [1], [2] are not discussed.\n\n[1] Fatemi, B., Halcrow, J. and Perozzi, B., 2023. Talk like a graph: Encoding graphs for large language models. \n[2] Chen, R., Zhao, T., Jaiswal, A., Shah, N. and Wang, Z., 2024. Llaga: Large language and graph assistant.", "was_revised": true, "final_justification": "The rebuttal has addressed the questions I raised in the initial review and the authors agree to revise the manuscript appropriately. I will keep my original positive score for the merits and contribution of the paper.", "rebuttal": "We thank the reviewer for their constructive feedback, which we believe will strengthen our paper. Below, we address each point in detail.\n\n> W1. many graph tasks may be non-discrete features.\n\nWe agree with the reviewer that handling continuous features is an important challenge. This is a known limitation for all discrete, token-based autoregressive models.\n\nFortunately, 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. \n\n[1]: Van Den Oord, Aaron, and Oriol Vinyals. \"Neural discrete representation learning.\" NeurIPS 2017.\n\n\n> 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.\n\nWe 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.\n\n> W3. Closely related recent works on graph to sequence methods such as \\[1\\], \\[2\\] are not discussed.\n\nWe 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**.\n\nQuestions:\n\n> Can the proposed SENT based graph to sequence representation be adapted for general graph modeling/understanding/downstream tasks?\n\nAs 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. \nWhile 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.\n\n> 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?\n\nIn 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."}, {"review_id": "VY6NCMkmqJ", "reviewer": "Reviewer_KYkS", "summary": "This paper proposes a graph generation method called AutoGraph, which serializes graph structures by treating sampled graph trials as tokens, enabling the use of decoder-only Transformer models for graph generation tasks. The authors introduce a newly designed structure named SENT (Segmented Eulerian Neighborhood Trail) to ensure that the prefix of the generated sequence corresponds to an induced subgraph. Thanks to these innovations, the proposed model demonstrates efficient generation, strong transferability, and controllable substructure conditioned generation capabilities across multiple synthetic and real-world graph datasets. Compared to diffusion-based models, the proposed approach achieves 100× faster generation and 3× faster training.", "questions": "1. What is the difference between AutoGraph-Graph and AUTOGRAPH (Pretrained) in the last two rows of Table 4?\n2. 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?\n3. 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.", "limitations": "The authors note that their experiments are still conducted on relatively small-scale benchmarks and attribute this limitation to the current lack of comprehensive graph generation benchmarks and well-curated pre-training datasets in the community.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 4, "strengths_and_weaknesses": "### Strengths\n1. The authors propose AutoGraph, the first method that serializes graph structures to enable direct application of language models to graph generation.\n2. The authors carefully design the SENT structure and theoretically prove that sampling SENTs allows for graph serialization, while ensuring that the prefix of the resulting sequence corresponds to an induced subgraph.\n3. The chosen method of serializing and tokenizing graphs using SENT guarantees that isomorphic graphs are mapped to identical token sequences, which facilitates better generalization.\n4. The proposed random trial sampling algorithm with breaks is cleverly designed and enables efficient sampling of SENTs.\n5. AutoGraph achieves significant inference and training speedups while maintaining almost state-of-the-art generation quality, demonstrating strong scalability.\n6. AutoGraph also shows impressive transferability and substructure conditioned generation capabilities without requiring additional finetuning.\n### Weaknesses\n1. The main advantage of the proposed AutoGraph method lies in its generation speed, while it shows some limitations in generation quality and does not consistently outperform other methods across all evaluation metrics:\n* As shown 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.\n* According to 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.\n2. 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.\n3. 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.", "was_revised": true, "final_justification": "I appreciate the authors' detailed clarification, which has addressed all of my concerns. I will keep my original score.", "rebuttal": "We thank the reviewer for their constructive feedback, which we believe will strengthen our paper. Below, we address each point in detail.\n\n> W1: The main advantage of the proposed AutoGraph method lies in its generation speed\n\nThe 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.\n\n> 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.\n\nThis 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.\n\n- 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.\n- 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.\n\nThis 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)**.\n\n> 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.\n\nAutoGraph represents a significant advance for **general graph generative models** in the specialized domain of molecular generation.\n\n-   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**.\n-   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.\n    \nWe believe this shows that AutoGraph is one of the first **general-purpose graph models** to achieve performance competitive with highly specialized, SMILES-based approaches.\n\n> 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.\n\nOur SENT representation is both more general and highly intuitive.\n\n- 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.\n- 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.\n\n> 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.\n\nSENT 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.\n\nQuestions:\n\n> 1. What is the difference between AutoGraph-Graph and AUTOGRAPH (Pretrained) in the last two rows of Table 4?\n\nAutoGraph (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**.\n\n> 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?\n\nDue 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.\n\nHowever, 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.\n\n> 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.\n\n**Yes, absolutely.** The model handles this complex conditioning out-of-the-box, without any modifications.\n\nWe 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**.\n\nCrucially, AutoGraph performs this multi-motif conditioned generation effectively **without any additional fine-tuning**, showcasing the power and flexibility of our prompting framework."}, {"review_id": "iveUg3S584", "reviewer": "Reviewer_FZzL", "summary": "This paper tackles the problem of **scalable and structurally valid graph generation**, a task that remains challenging for existing diffusion-based and autoregressive (AR) models due to either quadratic-to-cubic complexity or limited long-range consistency. The authors propose **AUTOGRAPH**, a framework that bridges graph generation with large language models (LLMs) through a novel **graph-to-sequence transformation**:\n\n1. **Segmented Eulerian Neighborhood Trails (SENTs)** – an extension of segmented Eulerian trails that augments each trail segment with local neighborhood tokens, ensuring complete edge coverage while preserving subgraph-induced structures.\n2. **Lossless flattening and tokenization** – a formal procedure that converts SENTs into token sequences with special delimiters, accompanied by theoretical proofs guaranteeing one-to-one recoverability between graphs and sequences.\n3. **Autoregressive language modeling** – any decoder-only transformer can now treat graph generation as next-token prediction, yielding *O(n)* time and memory complexity via an efficient SENT sampling algorithm.\n4. **Empirical validation** – using a 12-layer LLaMA backbone, AUTOGRAPH achieves:\n   - Up to **100× inference speed-up** and **3× training speed-up** over diffusion baselines on Planar and SBM datasets.\n   - Competitive performance on transfer learning and substructure-conditioned generation, demonstrating the method’s flexibility.\n\nOverall, AUTOGRAPH offers a principled and efficient pathway to leverage modern LLMs for graph generation, effectively mitigating negative transfer issues and outperforming prior diffusion and AR approaches in both accuracy and scalability.", "questions": "While the manuscript exhibits many notable strengths, I would appreciate clarification on the following points:\n\n-----\n\n1. **Positioning of prior work on graph-to-sequence representations**  \n   Introduction section occasionally reads as if no effective graph-to-sequence approach existed before this work. However, random-walk-based representations are acknowledged later in the Related Work section. It would be clearer—and fairer to prior art—if Introduction section explicitly positioned SENT as an improved (lossless and generation-oriented) extension of these earlier methods, rather than implying the absence of any sequence paradigm.\n\n-----\n\n2. **Interpretability of evaluation metrics**  \n   Although Maximum Mean Discrepancy (MMD) and VUN metrics are standard, readers unfamiliar with graph generation benchmarks may struggle to **intuitively grasp what each metric indicates**. **A brief high-level explanation** of the intuition behind each metric, perhaps in an appendix footnote or a short paragraph, would greatly improve result interpretability.\n\n-----\n\n3. **Speed comparison beyond diffusion baselines**  \n   The efficiency analysis highlights impressive speed-ups over diffusion-based models (Table 2). Is it feasible to provide analogous wall-clock comparisons against other baselines? If not, could the authors explain the practical obstacles? Such numbers would further substantiate AUTOGRAPH’s scalability claims across paradigms.\n\n-----\n\n4. **Validity scores in molecular generation (Table 4)**  \n   In the molecular benchmarks, AUTOGRAPH achieves strong uniqueness and novelty but appears to match—or slightly underperform—some baselines in validity. To the best of my knowledge, the validity is the most critical criterion for molecule generation, so the authors need to report the additional discussion.\n\n---\n\nAddressing these points would further strengthen the paper’s clarity and persuasiveness.", "limitations": "All key limitations have been included within the Questions above.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "------\n\n### Strengths\n\n- **S1. Lossless graph-to-sequence transformation**  \n  The paper moves beyond prior random-walk-based graph representations by introducing a **lossless** conversion—Segmented Eulerian Neighborhood Trails (SENTs)—that preserves complete edge coverage and subgraph-induced structures. This theoretically grounded mapping enables direct, reversible use of language models for graph generation without sacrificing structural validity.\n\n-----\n\n- **S2. Comprehensive empirical evaluation**  \n  The authors conduct meticulous head-to-head comparisons against both diffusion-based and conventional autoregressive baselines across four benchmarks encompassing small, medium, and large graphs. Results consistently demonstrate AUTOGRAPH’s superiority in accuracy (MMD, VUN) and efficiency (up to 100× faster inference), underscoring the method’s robustness to graph size and domain diversity.\n\n-----\n\n- **S3. Formal guarantees and linear-time sampling**  \n  Theoretical proofs establish a one-to-one correspondence between SENT sequences and their source graphs, while the proposed sampling algorithm operates in linear time $\\(O(m)\\)$ with respect to edge count—crucial for scalability.\n\n---\n\n## Weaknesses\n\nThese are elaborated under the Questions section below.", "was_revised": true, "final_justification": "Many of my minor concerns have been sufficiently alleviated. Therefore, I have revised my initial score upward by one point, and my final recommendation is a score of 4.", "rebuttal": "We thank the reviewer for their constructive feedback, which we believe will strengthen our paper. Below, we address each point in detail.\n\n> W1. Positioning of prior work on graph-to-sequence representations\n\nWe 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.\n\n\n> W2. Interpretability of evaluation metrics\n\nWhile 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:\n\n**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.\n\n**VUN (Validity, Uniqueness, Novelty):** This assesses **sample quality**. Details have already been provided in Appendix E.2.\n\n\n> W3. Speed comparison beyond diffusion baselines\n\nWe emphasize that **Table 2 already provides a speed comparison across three distinct paradigms of graph generation models**:\n\n- **DiGress:** A representative **diffusion model**.\n- **GRAN:** A state-of-the-art **autoregressive model**.\n- **ESGG:** A **hybrid diffusion and autoregressive model** specifically designed for efficient generation.\n\nOur 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.\n\n> W4. Validity scores in molecular generation (Table 4)\n\nAutoGraph'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).\n\nThe 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."}]

Author rebuttal:

Meta-review: This paper studies the graph generation problem by transforming it to a graph-to-sequence problem. Specifically, the authors proposed a new invertible tokenization to transform a graph to a sequence representation. Empirical evaluations were conducted on large graphs and molecular graphs. Though the performance on molecular graphs was not particularly impressive, the additional experiments on transferrability and substructure conditioned generation demonstrated promising results.

One critical concern raised by multiple reviewers during rebuttal was the discussion of related work and overclaim. I hope the authors could address those in the revision.

Two reviewers gave borderline reject but raised to borderline accept after rebuttal. As all the reviewers feel positive about the paper, I vote to accept this paper.
Decision: Accept (poster)