Fast Graph Generation via Autoregressive Noisy Filtration Modeling
Authors: Markus Krimmel
Jenna Wiens
Karsten Borgwardt
Dexiong Chen
Venue: Accepted by TMLR ()

Abstract: Existing graph generative models often face a critical trade-off between sample quality and generation speed. We introduce Autoregressive Noisy Filtration Modeling (ANFM), a flexible autoregressive framework that addresses both challenges. ANFM leverages filtration, a concept from topological data analysis, to transform graphs into short sequences of subgraphs. We identify exposure bias as a potential hurdle in autoregressive graph generation and propose noise augmentation and reinforcement learning as effective mitigation strategies, which allow ANFM to learn both edge addition and deletion operations. This unique capability enables ANFM to correct errors during generation by modeling non-monotonic graph sequences. Our results show that ANFM matches state-of-the-art diffusion models in quality while offering over 100 times faster inference, making it a promising approach for high-throughput graph generation. The source code is publicly available at https://github.com/BorgwardtLab/anfm.

Published in Transactions on Machine Learning Research (01/2026)
Fast Graph Generation via Autoregressive Noisy Filtration Modeling
Markus Krimmel
krimmel@biochem.mpp de
Mar Planck Institute of Biochemistry
Jenna Wiens
wrenssj@huiich.com edu
University of Michigan
Karsten Borgwardt
borguarddtShicche..mpp
Max Planck Institute of Biochemistry
Dexiong Chen
dchen @thochmmooc de
Max Planck Institute of Biochemistry
Reviewed on OpenReview: https: // oppnrreveee. net/ forum? id- 3Up
Abstract
Existing graph generative models often face a critical trade-off between sample quality and generation speed. We introduce Autoregressive Noisy Filtration Modeling (ANFM), flex- ible autoregressive framework that addresses both challenges. ANFM leverages filtration, concept from topological data analysis, to transform graphs into short sequences of sub- graphs. We identify exposure bias as potential hurdle in autoregressive graph generation and propose noise augmentation and reinforcement learning as effective mitigation strate- gies, which allow ANFM to learn both edge addition and deletion operations. This unique capability enables ANFM to correct errors during generation by modeling non-monotonic graph sequences. Our results show that ANFM matches stale-of-the-art diffusion mod- els in quality while offering over 100 times faster inference, making a promising ap- proach for high-throughput graph generation. The source code is publicly available at httts:///gtthen htt...////.oeeewaraabaaaaaa.at
1 Introduction
Graphs are fundamental structures that model relational data in various domains, from social networks and molecular structures to transportation systems and neural architectures. The ability to generate re- alistic. and diverse graphs therefore holds great promise in many applications, such drug discovery {Liu) lt al. 2018 Vignac et al. 2023), network simulation (Yu & Gu 2019). and protein design (Ingraham et al. 2019). The space of drug- like molecules and protein conformations is, for practical purposes, infinite, lim- iting the effectiveness of in-silico screening existing libraries (Polishchuk et al., 2013 Levinthal 1969 Consoquently, high-throughput graph gencration- the task of efficiently creating new graphs that faithfully emulate properties similar to those observed in given domain thus emerging as critical challenge in machine learning and generative artificial intelligence.
Recent deep learning- basod approaches, particularly antoregressive You et al. 2018b Liao et al. 2019:
Kong et al.) 2023) and diffusion models (Vignac et al. 2023 Bergmeister et al. 2024), have shown promise in generating increasingly realistic graphs. However, many current diffusion- based approaches rely on iter- ative refinement processes involving large number steps. This computational burden may hinder their potential for high-throughput applications (Gentile al. 2022
et al. 2016). While au- toregressive models are more efficient during inference, they have underperformed in terms of generation

---

Published in Transactions on Machine Learning Research (01/2026)
quality. Moreover, they might be susceptible to exposure bias (Ranzato et al. 2016). where performance deteriorates as errors accumulate during sampling and a train-test discrepancy consequently arises.
Recent work has explored the use of topological data analysis, particularly persistent homology and filtra- tion (Edelsbrunner et al. 2002 Zomorodian & Carlsson 2005p, for graph representation. A filtration provides a multi-scale view of a graph structure by constructing a nested sequence of subgraphs. This approach has shown potential in various graph analysis tasks, including classification and similarity measurement (O'Bray et al. 2021 Schulz et al., 2022 In the context of generative modeling, filtration- based representations have been used to develop more expressive tools for generative model evaluation (Southern et al. 2023). However, the application of filtration-baser methods for graph generation remains unexplorod. In this work, we pro- pose filtrations as a generalization of graph sequence families used in prior autoregressive models (You et al., 2018b Liao et al. 2019), offering a flexible framework to construct sequences for generation. heneth modeling filtration sequences in a naive manner remains prone to exposure bias.
To address this, we introduce Autoregressive Noisy Filtration Modeling (ANFM), novel approach to fast graph generation that models noise-augmented filtration sequences autoregressively. To generate target graph, our method produces short sequence of increasingly dense and detailed intermediate graphs, which interpolate the target graph and the fully disconnected graph. Compared to diffusion models (Vignac et al. 2023 Bergmeister et. al. 2024), ANFM requires fewer iterations during sampling, resulting in significantly faster inference speed. By adding noise to the filtration sequences, ANFM learns to simultaneously remove or add edges. As a result, the model can recover from errors during sampling. Additionally, we further mitigate exposure bias with adversarial ine-tuning using reinforcement learning (RL). Our method offers promising balance between efficiency and accuracy in graph generation, providing 100-fold speedup over diffusion- based approaches, while substantially outperforming existing autoregressive models in terms of generation quality.
In summary, our contributions are as follows:
We propose a novel auloregressive graph generation framework that leverages graph filtration. Our formulation generalizes the graph sequences used by previous autoregressive models that operate via node addition.
We introduce specialized autoregressive model architecture designed to operate these graph sequences.
We identify exposure bias as a potential challenge in autoregressive graph generation and propose noise augmentation and adversarial fine-tuning as effective strategics to mitigate this issuc.
We conduct ablation studies to evaluate the impact of different components within our framework, demonstrating that noise augmentation and adversarial fine-tuning substantially improve perfor- mance.
Our empirical results highlight the strong performance and efficiency of our model compared to recent baselines. Notably, our model achieves inference speed 100 times faster than existing diffusion-basel models.
2 Related Work
ANFM builds on the concopt of graph filtration and incorporates noise augmentation. It is finc-tuned via reinforcement learning to mitigate exposure bias. In the following, we provide a brief overview of related graph generative models (GGMs), approaches address exposure bias, and applications of graph filtration.
Autoregressive GGMs. GraphRNN (You et al. 2018b) made the first advances towards deep generative graph models by autoregressively generating nodes and their incident edges to build up adjacency matrix row-by-row. In similar fashion, DecpGMG (Li et al. 2018) iteratively builds a graph in nodc-by- node fashion. Liao et al. (2019) proposed a more efficient autoregressive model, GRAN, by generating multiple nodes at a time in a block-wise fashion, leveraging mixtures of multivariate Bernoulli distributions. GraphArm Kong et al.) 2023) introduced an autoregressive model that reverses diffusion process which nodes and their incident edges decay to an absorbing state. These models share the property that they build graphs by node addition. Hence, they autoregressively generate increasing sequence of induced subgraphs
2

---

Published in Transactions on Machine Learning Research (01/2026)
(i.e., maximal subgraphs subset of the nodes). In comparison, the subgraphs we consider in our work do not necessarily need to be induced. Moreover, ANFM may generate sequences that are not monotonic. That is, ANFM may simultaneously add and delete edges. In contrast to autoregressive node-addition methods, approaches by Goyal et al. (2020) and Bacciu et al. (2020) generate graphs through edgo-addition following a pre-defined edge ordering.
Diffusion GGMs. Diffusion models for graphs such as EDD--GNN NNu et al.
2020 and GDSS (Jo et al.
2022), based on score matching, or DiGress (Vignac et al.) 2023 based on discrete denoising diffusion (Austin ct al. 2021p, have emerged as powerful generators. However, they require many itcrative denoising steps, making them slow during sampling. Hierarchical approaches (Bergmeister et al. 2024) and absorbing state processes (Chen et al., 2023) have subsequently been proposed to allow diffusion models be scaled to large graphs. In contrast to the noise processes in denoising diffusion models, the filtration processes we consider are in general non-Markowian, necessitating full autoregressive modeling.
In concurrent work, [Boget (2025) proposed SID, a modification of discrete denoising graph diffusion in which intermediate states are conditionally independent. This work was motivated by a phenomenon similar to exposure bias, termed compourding denoising errors. Similar to ANFM, the sequences modeled by an absorbing state variant of STD are non-montonic and non-Markovian.
Single-Step GGMs. Unlike iterative approaches such as autoregression and diffusion, graph variational autoencoders (VAEs) (Kipf & Welling, 2016; Simonovsky & Komodakis 2018) generate all edges in a single step, reducing computational costs during inference. However, VAEs struggle to model complicated distribu- tions and require graph matching during training, restricting their application to small graphs. Generative adversarial networks (GANs) (Gooddiellww al.) (0014) offer an alternative, operating in a likelihood-free lashion and avoiding graph matchings. Despite this advantage, GANs are notoriously difficult to train and suffer from issues such mode collapse (Cao & Kipf 2018). To address these instabilities, Martinkus ct al. 2022) proposed SPECTRE, GAN that first generates Laplacian spectrum before producing the corresponding graph.
RL in Graph Generation. In the context of graph generation, reinforcement learning has been used mainly to generate molecular graphs. You et al. (2018a) trained a generative model for molecules via RL, combining adversarial and domain-speeific rewards. In contrast to our work, they only considered molecular graphs and did not use teacher-forcing during training. Taiga (Mazuz et al. 2023) used reinforcement learning to optimize the chemical properties of molecules obtained from a language model pre-trained on SMILES strings. Diffusion models have also been shown to be amenable to RL. finetuning, allowing extrinsic non-differentiable metrics to be optimized [Lu et al. 2024).
Exposure Bias. Exposure bias (Bengio et al. 2015 Ranzato et al. 2016) refers to the train-test discrep- ancies autoregressive models face when they are exposed to their own predictions during inference. Errors may accumulate during sampling, leading to distribution shift and degrading performance. To mitigate this phenomenon in natural language generation, [Bngiio al. (2015) proposed a data augmentation strategy to expose models to their predictions during training. In a similar effort, Ranzato et. al. (2016) proposed training in free-running mode using reinforcement learning to optimize sequence-level performance metrics. SeqGAN (Yu et al. 2017), which is the most relevant to our work, also trains models in free-running mode using reinforcement learning. Instead of relying on extrinsic metrics like Ranzato et al. (2016), il adversari- ally trains a discriminator to provide feedback to the generative model. GCPN (You et al.) 2018a) adopts a hybrid framework for generating small molecules, combining adversarial and domain-specific rewards.
Filtration is commonly used in the field of persistent homology (Edelsbrunner et al. 2002) to extract features of geometric data structures at different resolutions. Previously, graph filtration has mostly been used to construct graph kernels (Zhao & Wang 2019 Schulz et al. 2022 or extract graph ropresentations that can be leveraged in downstream tasks such as classification (O Bray et al. 2021). While filtration has also been used for evaluating graph generative models (Southern et al. 2023). to the best of knowledge, our work presents the first model that direclly leverages filiration for generation.
Graph Filtration.
3

---

Published in Transactions on Machine Learning Research (01/2026)
3 Background
In the following, we consider unlabeled and undirected graphs, denoted by G = (V, where V is the set of vertices and E [ V x is the set of edges. Without loss of gencrality, we assume V f1.2.....u n) and denote by egj the edge between nodes i. E V. We assume that only connected graphs are presenled to our model during training and filter training sets if necessary, Our approach based on the concept of graph filtration.
Graph Filtration. A filtration of graph G is defined as nested sequence of subgraphs:
G= GT 2 Gr-1 ... G. 2 Go = (V.0)
(1)
where each G. (V, Ex) is graph sharing the same node set as GT G. The filtration satisfies the following properties: (1) E. C Ey for all < l' and (2) Go is the fully disconnected graph, d.e., Eg = 0. The syper-parameter T controls the length of the sequences, which is selected to be typically small in our experiments (T - 32).
Filtration Function and Schedule. A convenient method to define filtration of G' involves specifying
two key components ( (O'raa& et al. 2021 filtration function defined the edge set f E R and a non-decreasing sequence of scalars (0o, a....., .r) with -00 S a1 .... S or I or = +00. Given these components, we can define the edge sets E, as nested sub-levels of the function ʃ for / = ,,...,
T 1
Eg = (-=c, (cEE f(e) S }
(2)
The sequence (a=)== is referred to as the filtration schedule sequence. The choice of the filtration function and the schedule sequence plays a crucial role effective graph generation. We present a visual example of the filtration process in Figure lb
4 Autoregressive Noisy Filtration Modeling
In this section, we present the Autoregressive Noisy Filtration Modeling (ANFM) approach for graph genera- tion. Given node set V, our objective is to generate sequence of increasingly dense graphs Go, GI,.., "y....,r, on V. The final graph Gr should plausibly represent sample from the target data distribution. To achieve this goal, ANFM will be trained to reverse a noise augmented filtration process.
Ör
This section organized as follows: We present two filtration strategies in Sec. bias, we propose noise-augmentation of the resulting graph sequences in Sec. We then introduce
To mitigate exposure
Sec. 4.3 our autoregressive model that reverses this noisy filtration process. In Sec. 4.4 we propose a two- staged training scheme for ANFM, introducing adversarial fine-tuning stage to further address exposure bias. Finally, in Sec. 4.5 we discuss algorithmic differences of ANFM and existing graph generative models.
As our proposed method consists of several components, we study their individual contributions in extensive ablation experiments in Sec. 5.4 and Section Furthermore, implementation details and hyperparameter settings are provided Sections
and
4.1 Filtration Strategies
In the following, we discuss two primary strategies for the filtration function and schodule. Alternative choices are investigated in Appendix
Filtrations from Node Orderings. Many existing autoregressive models operate via node addition and thereby model sequences of nested induced subgraphs (You et al. 2018b Li et al. 2018 Liao et al.) 2019: Kong el al.) 2023). We show that similar sequences may be obtained via filtration. In this sense, the filtration framework generalizes the sequences considered by these previous works. Given a graph G, let g V (1.....n) be node ordering, i.e., a bijection. Models that operate node addition generate a graph sequence
(0,0) = G[Vo] .... C G[V] =
4

---

Published in Transactions on Machine Learning Research (01/2026)
0.30
60
1000
0.05
20
0.10
Line Fiedler
DFS
(a) Filtration functions
(b) A filtration sequence
Reward
ccB
og
Generator
Fake Graphs
Lce
Autoragressive Graph Mixe
Discriminator
{ <-... Loss
Noise
Noise
Noise
Noise
Real Graphs
LRR
(c)
Training stage (teacher-forcing)
(d) Training stage II (adversarial fine-tuning)
Figure 1: Top: A graph is transformed into sequence of subgraphs (filtration) by taking sub-levels of filtration function (i.e., performing edge-deletion according to the order prescribed by the filtration function). Bottom left: the generator is trained via teacher-forcing to reverse the filtration process. Bottom right: the generator is finc-tuned in free-running mode via reinforcement learning on a reward signal output by a discriminator in a SeqGAN-like framework (c.f. Appendix J
where Vo, Vr are monotonically increasing sub-levels of g with V = g==--- ([(-(( az))) for some scalars -00 dg S ... < ar +o,, and G[V]] denotes the induced subgraph whose node set V. Now we consider the following filtration function f + E:
S(uu, v)) max (gx),
Vu,u) E E.
(4)
It is not hard to verify that this filtration function combined with the filtration schedule (at) yields a filtration sequence (Go) in which the edge set of G, coincides with the edge set of G[Vi] for any == ,,...,T Hence, this filtration closely mirrors the sequence of induced subgraphs, differing only in that the node set does not change over time. We say that graphs in this sequence have induced edge sets. While a filtration function may be derived from any node ordering, we focus on depth-first search (DFS) orderings in this work, as shown to be optimal among several orderings for autoregressive graph generation in GRAN (Lioo ct al. 2019). We visualize resulting edge weights on planar graph in Figure la For filtrations derived from DFS orderings, we choose the filtration schedule o to linearly increase from a minimum edge weight at = (01 = 2) to a maximum edge weight at f = (ar = [V]). Unlike in previous autoregressive models YYuu et al. 2018b; Liao al. 2019 Kong et al. 2023 T fixed across all graphs. We argue that fixed simplifies both training and inference: since sequence lengths are uniform across all graphs, no padding must be applied during training. Additionally, no end-of-sequence signal must be emitted during inference.
Line Fiedler Filtrations. In contrast to the family of graph sequences leveraged by node-addition ap- proaches, the filtration framework is not limited to sequences of induced subgraphs. We present the line Fiedler filtration function, which is one particular choice that, in general, yiclds sequence of subgraphs with non-induced edge sets. This filtration function is intended to decompose graphs in a local fashion, assigning similar edge weights to neighboring edges. We are motivated by the intuition that may potentially beneficial construct graphs by adding edges that are incident to the same vertex at similar timesteps the generation process. To achieve this goal, we leverage the first non-trivial cigenvectors of graph Laplacians, called Fiedler vectors. It. is known that these eigenvectors represent. low-frequency signals on vertices suitable
5

---

Published in Transactions on Machine Learning Research (01/2026)
for clustering (Shi & Malik 1997 and often coloring them in "contimuous gradient". Since interested in coloring the edges of a given graph G, we transition to its line graph (Harary & Norman 1960) L(G). Edges in G form vertices in L(G), and they are adjacent in L(G) if they are incident to a shared vertex in G. The Fiedler vector of L(G) now tends to color its vertices in a continuous gradient, which transfors to a continuous coloring of the edges of G. We choose the line Fiedler filtration function as such a Laplacian eigenvector of [(G) and refer to Appendix M for a more rigorous definition. We visualize the resulting edge weights on planar graph in Figure [a] demonstrating how it varies across edges in a "continuous gradient". For 0 S t v T, we propose to define the filtration schedule de
axDI [[-,((-00,,:))) 2 7(/7))
0r :== CER:
(5)
E
where f the line Fiedler filtration function, and 7 [0, 1] [0, 1] is a monotonic function governing the rate at which edges are added in the filtration sequence. We choose (t) t, leading to an approximately linear increase in the number of edges throughout the graph sequence. We investigate other choices of in Appendix
4.2 Noise Augmentation of Filtrations
Our goal is to autoregressively generate sequences of graphs that approximately reverse the filtration pro- cesses above. To mitigate exposure bias in autoregressive modcling, previous works have proposed data augmentation scherne to make models more robust to the distribution shift occurring during inference (Ben- gio et al. 2015). We propose a simpler yet effective strategy: namely, randomly perturbing intermediate graphs in a filtration sequence Gø.... GT during the first training stage to expose the model to erroneous transitions. For each intermediate graph G, with 0 < < T, we generate a perturbed graph G, with edge set Fg by including each possible edge independently with probability
(1 Xx) depa if e E,
Ple E Ed
(6)
Aeps else
where d E [0, 1] controls stochasticity and Pt == (E:1/(())) is the density of G.. In practice we decrease X linearly as increases and include multiple perturbations of each filtration sequence in the training set. The choice of hyper-parameters, such as X and the number of included perturbations, is detailed in Appendix D.2 We note that this augmentation yields non-monotonic noisy filtration sequences (G.) during training. Hence, our autoregressive model is trained to allow for edge deletions.
4.3 Autoregressive Modeling of Graph Sequences
The generative model will be trained to reverse the noise-augmented filtration process detailed above. We formulate the generative process using an autoregressive model, expressing the joint. likelihood as follows:
pe(Gr...., Go) = p(Go) II pe (...............
where p(Go) represents the distribution over initial graphs, defined as a point mass on the fully disconnected graph (V, 9). In the following, we will detail our implementation of the autoregressive model pe, including the architecture and training procedure. While existing autoregressive models typically utilize RNNs (You al.
2019 Goyal et al. 2020 Bacciu et al. 2020) first-order autoregressive structure (Kong et al. 2023), our model architecture for implementing Po is novel and efficient design inspired by MT.P-
2018b Liao et al.
Mixers (Tolstikhin et al. 2021).
Backbone Architecture. The graph sequences we consider can be viewed as dynamic graphs with con- stant node sets but evolving edge sets. Our backbone architecture operates on this structure by alternating between two types of information processing layers. The first type, called structural mixing, consists of a GNN that processes graph structures Coo...GT-- independently, with weights shared across time steps.

---

Published in Transactions on Machine Learning Research (01/2026)
The second type, called temporal mixing, consists of transformer decoder (TRDecoder) that processes node representations along the temporal axis, with weights shared across nodes. Our model inherits the causal structure of the transformer decoder, ensuring that node representations at timestep f only depend on the graphs Go.... Gt. Formally, given input node representations vtth E RD for nodes i E V and time steps E [T - II, a single mixing operation in our backbone model produces new representations u, and is defined as:
w ())
IV
= GNN, ((44)
IV i=
Ee,
Vt O.... T
i=1
(8)
T-1
= TRDecoder
12
=i= 1,... V).
1=
where the first equation defines structural mixing operation and the second equation defines a temporal Awweuurr-wwaae----aeaaaa
mixing operation. For the structural mixing, we use Additionally, we incorporate both the timestop t and cycle counts in G, using FiLM (Perez et al. These structural features were used previously in other graph generative models such as DiGress Multiple mixing operations stacked to form the backbone model.
layers CChen et al. 2022
2018
Vignac
et al. 2023
Edge Decoder. To model po(GrlG.-.,..... Go); we produce a distribution over possible edge sets of G. We use a mixture of multivariate Bernoulli distributions to capture dependencies between edges, similar to previous works (Liao et al. 2019 Kong et al., 2023 Mixture distributions are more expressive than simple multivariate Bernoulli distributions, which model the existence edges independently in each generation step. Given K 2 mixture components, we infer Bernoulli parameters for each node pair i. E V from the node representations e produced by the backbone model timestep t 1:
(9) where k: 1,.., K and D.o is some neural network. We enforce that Ph (i.) is symmetric and that the probability of self-loops is zero. In addition, produce mixture distribution π E RK in the K - 1 dimensional probability simplex from pooled node representations. The architectural details of D., are provided in Appendix E.3 The final likelihood is defined as:
Pk (1.)) = (v,,(vi, Uz) E [0,
K
(15) if ciy E,
Do(E,(Ge Go) =
T
Pk
(1.)
(10)
isj
1
- Pk
clse
2018b Liao et al. 2019 Goyal el al. 2020 Bacciu et al. 2020 Kong et al. 2023). our model introduces a key innovation: the ability to generate non-monotonic graph sequences. This means it can both add and delete edges. We argue that this capability is crucial for mitigating error accumulation during sampling (i.c., exposure bias). Consider, for instance, the task of generating tree structures. If cycle is inadvertently introduced into an intermediate graph G, (where <<T T), traditional autoregressive approaches would be unable to rectify this error. Our model, however, potentially delete the appropriate edges in subsequent timesteps, thus recovering from such mistakes. The noise augmentation approach from Sec. 4.2 exposes ANFM to such erroneous transitions during training. We show empirically in Sec. 5.4 that this augmentation substantially improves performance.
In contrast to existing autoregressive graph generators Youu et al.
Input Node Representations. The initialization of node representations is a crucial step preceding the forward pass through the mixer architecture above. We compute initial node representations from positional
and structural fcatures in similar fashion as Vignac et al. (2023). Morcover, we add lcarned positional embeddings based a node ordering derived from the filtration function. We refer to Section E. for further implementational details and to Section H for ablations of the node ordering.
Asymptotic Complexity. We provide a detailed analysis of the asymptotic runtime complexity of our method in Appendix B.1 Asymptotically, ANFM's complexity of sampling a graph with N nodes is O(T2 N+ TN3), where we recall that T denotes the number of filtration steps. Although cubic the number of nodes, we found that the efficiency of ANFM is largely driven by our ability to use a small T (T < 32), while diffusion-based models generally require a much larger number of iterations.
7

---

Published in Transactions on Machine Learning Research (01/2026)
While ANFM is in practice faster during inference than competing methods, we find that training could be we compare the training costs of ANFM to those of DiGress.
more expensive. In Appendix K
4.4 Training Algorithm
Teacher-Forcing. We employ teacher-forcing (Williams & Zipser 1989 to train our generative model po in first training stage. We illustrate this training scheme in Figure Ic Teacher-forcing allows the model to learn from complete sequences of graph evolution, providing good initialization for subsequent reinforcement learning- based fine-tuning. Given dataset of graphs D, convert it into a dataset of noisy filtration sequences, denoted as D. Our objective is to maximize the log- log-likelhhood of these sequences under our model:
[ = B(Go....Gr)wb [log
.,.,)....
(11)
In practice, this objective is implemented cross-entropy loss. While the noise augmentation introduced in Sec. 4.2 improves the overall quality of generated graphs after teacher-forcing training, it still falls short in generating graphs with high structural validity. To further mitigate exposure bias, we propose an RL-based fine-tuning stage to refine the model trained with teacher-forcing,
Adversarial Fine-tuning with RL. Adapting the SeqGAN framework (Yu et al. 2017]. we implement a inverator-discrmmintte architecture where the generator (our mixer model) operates in inference mode as a stochastic policy and is thereby exposed to its own predictions during training. The discriminator a graph transformer, namely GraphGPS (Rampásek et al. 2022). During training, the generator produces graph samples, which the discriminator evaluates for plausibility. The generator is updated using Proximal Policy Optimization (PPO) (Schulman et al. 2017) based the discriminator's feedback, while the discriminator is trained adversarially to distinguish between generated and training set graphs. This training scheme is illustrated in Figure Id It is worth noting that only the final generated graph is presented to the discrimina- tor. Therefore, the generator is trained to maximize a terminal reward without constraints on intermediate graphs. Wc provide pseudo-code Appendix [J] While we focus on adversarial fine-tuning of ANFM, similar techniques might prove useful for diffusion models or existing autoregressive graph generators. However, incorporating this training strategy into existing generative models would require substantial modifications, falling outside the scope of our work.
4.5 Comparison to Other Generation Paradigms
While we calegorize ANFM as an autoregressive model, it also exhibits superficial similarities to diffusion- based approaches. Hence, we further clarify its conceptual similarities and differences to existing generation paradigms.
Autoregressive Approaches. Existing autoregressive graph generators build graphs iteratively by gen- 2018b Liao et al.) 2019 Li ct al.) 2018: Kong et al. 2023)
erating sequences of nodo-addition You al. edge-addition (Goyal et al. 2020 Bacciu et al. 2020 operations, thus modeling monotonic sequences of sub- graphs. The operations performed by these models are non-reversible, making them vulnerable to exposure bias. In contrast, ANFM explicitly models sequences of entire graphs, allowing for both edge addition and edge deletion. ANFM is encouraged to perform both operations by training with noise augmentations, thus allowing ANFM to generate non-monotonic graph sequences. We demonstrate Sec. 5.4 that noise aug- mentation improves performance substantially, justifying the necessity of modeling non-monotonic soquences. Graph filtration is a natural and general framework for defining monotonic graph sequences to which we apply noise augmentations during the first training stage. This approach generalizes existing autoregres- sive methods by allowing sequences of subgraphs with non-induced edge sets to be constructed. While this enables the exploration of a wider variety of graph sequences for training, the non-induced sequences we investigate in our experiments (c.f., Sec. 5 are oftentimes outperformed by sequences of subgraphs with induced edge sets.
In autoregressive tasks, one is usually interestod in the entire generated sequence. In contrast, we model the sequence Go,... Gr but are only interested in the marginal of GT. This is akin to diffusion modeling,
8

---

Published in Transactions on Machine Learning Research (01/2026)
where intermediate states serve latent variables. Hence, we now clarify why we do not categorize ANFM as diffusion model.
Diffusion Models. Similar to graph denoising diffusion models (Vignac et al. 2023: Chen et al. 2023 Kong et al., 2023 we reverse corrupting process that transforms graph samples Gr into graphs Go from a convergent distribution. Unlike standard denoising diffusion models, our filtration process is explicitly non- Mon-MMakov Instead of simply accumulating noise over time steps, our sequence GT,..., Co based on the topology of Gr. Hence, it may not be Markov. This why we introduce a full autoregressive struc- ture, which leads to improvements over first-order structure (used in diffussin models), we demonstrate in Appendix B.2 In practice, this filtration-basee approach allows us to perform substantially fewer gen- EDGE (Chen et al. 2023),
eration steps than diffuusin models such DiGress (Vignac et al. 2023 GraphARM Kong et al. 2023).
5 Experiments
We empirically evaluate our method on synthetic and real-world datasets. We investigate the filtration strategy based on depth-first search node orderings (DFS) and the line Fiedler function (Fdl.). In Sec. 5.1 we first present results on the commonly used small benchmark datasets (arrtinkus et al., 2022). comparing our method to a variety of baselines. We then demonstrate in Sec. S.c. th2 we can improve upon these results by using more realistic sctting with more training examples. Additionally, we present results for inference efficiency. Finally, in Sec. 5.3 we demonstrate that our model is applicable to real-world data, namely larger protein graphs (Dobson & Doig 2003) and drug-like like molecules (Brown et al.) 2019). In Sec. 5.4 we present ablation studies demonstrating the efficacy of noise augmentation and adversarial fine-tuning.
Evaluation. We follow established practices from previous works (You et al. 2018b Martinkus el al. 2022 Vignac et al. 2023) in our evaluation. We compare a set of model-generated samples to a test set via maximum mean discrepancy (MMD) (Gretton et al. 2012), based on various graph descriptors. These descriptors include histograms of node degrees (Deg.); clustering coefficients (Clus.), orbit count statistics (Orbit), and eigenvalues (Spec.).
In previous works (Martinkus et al. 2022 Vignac et al. 2023 very few samples are generated for the evaluation of graph generative models. In Appendix ! we show theoretically and empirically that this
leads to high bias and variance in the reported metries. In Sec. 5.2 and 5.3 we generate 1024 samples for evaluation to mitigate this, while we generate 40 samples in Sec. 5.1 to fairly compare to previous methods. For synthetic datasets, we follow previous works by reporting the ratio of generated samples that are valid, unique, and novel (VUN). In Sec. 5.2 and 5.3 we report. inference speed, measured the time needed to generate 1024 graphs The measured inference times inherently depend the implementation details of the
H100 GPU, normalized to a per-graph cost. Hence, the reported metrics have the
unit second/gras methods. While we ensure that all models are evaluated on identical hardware under comparable conditions, this limitation cannot be fully eliminated. For each evaluation metric, we highlight the best and second-best performing method in bold and underlined, respectively.
Baselines. We aim to demonstrate that our method is competitive with state-of diffusion models in terms of sample quality while outperforming them in terms of inference speed. Hence, we compare our method to two recent diffusion models, namely DiGress (Vignac et al. 2023) and ESGG (Bergmeister al., 2024). DiGress first introduced discrete diffusion to the area of graph generation and remains one of the most robust baselines. ESGG is acutely relevant to our work, it aims to improve inference speed. In addition, we also present results on an autorcgressive model, GRAN (Liao et al., 2019). which focuses on efficiency during inference. For details on model selection and hyper-paraneeer for these baselines, we refer to Sections G.1 to G.5 In Sec. 5.1 we report baseline results from the literature, also comparing to the hicrarchical HiGen [Kaamm 2024) approach, the scalable EDGE (Chen al.] 2023) diffusion model, the autoregressive GraphRNN model (You et al. 2018b), and the GaN-based SPECTRE model (Martinkus
et al. 2022
9

---

Published in Transactions on Machine Learning Research (01/2026)
5.1 Experiments with Small Synthetic Datasets
Table 1: Performance of models on small synthetic SPECTRE datasets. Results on GraphRNN, GRAN and SPECTRE taken from Martinkus et al. (2022). Results on DiGress, ESGG and EDGE from Bergmeister
et al. 2024).
Planer Grephs ([V] 64,
Nerain 128)
SBM Graphs ([V) ~ 104, Norata 128)
VUN (1)
Deg. (U)
Clus. (4)
Orbit (4)
Spec. (4)
VUN (1)
Deg. (4)
Clus. (L)
Orbit (4)
Spec. (L)
GraphRNN
0.0
0.00:19
0.2779
1.2543
0.0459
5.0
0.0055
0.0584
0.0785
0.0065
GRAN
0.0
0.0007
0.0426
0.0009
0.0075
25.0
0.0113
0.0553
0.0540
0.0054
SPECTRE
25.0
0.0005
0.0785
0.0012
0.0112
52.5
0.0015
0.0521
0.0412
0.0056
DiCress
77.5
0.0007
0,0750
0.0079
0.0098
60.0
0.0018
0.0485
0.04115
0.00455
EDGE
0.0
0.0761
0.3229
0.7737
0.0955
0.0
0.0279
0.1113
0.0854
0.0251
HlGenn
0.0019
0.0498
0.0352
0.0046
ESGG
95.0
0.0005
0.0626
0.0017
0.0075
45.0
0.0119
0.0517
0.0669
0.0067
ANFM (FAL.)
72.5
0.0037
0.1332
0.0047
0.0099
47.5
0.0014
0.0506
0.0551
0.0058
ANFM (DFS)
33..5
0.0004
0.0309
0.0012
0.0061
65.0
0.0007
0.0488
0.0335
0.0048
As a first demonstration of our method, we present results on the planar and SBM datasets by Martinkus et al. (2022). o Since the training set consists of only 128 graphs, we find that ANFM models using the line Fiedler function tend to overfit during the teacher-forcing training stage. To mitigate this issue, we introduce some small stochastic perturbations to node orderings used for initializing node representations. We discuss this in more detail in Appendix E.1 Model selection is performed based on the minimal validation loss. Table [ models outperform GraphRNN You ct al. 2018b), GRAN (Liao et al. 2019), EDGE Chen et al. (2023). and SPECTRE (Martinkus et al. 2022
illustrates that, in terms of VUN on the planar graph dataset,
While they perform worse than DiGress (Vignac et al. 2023) and ESGG (Bergmeister et al. 2024 on the planar graph dataset in terms of VUN, the DFS variant performs better than these baselines in terms of most MMD metrics. While the line Fiedler variant outperforms the DFS variant on the planar graph dataset w.r.t. VUN, the DFS variant performs substantially better on the SBM dataset. Notably, on the SBM dataset, the DFS variant putperforms all baselines w.r.t. VUN and many MMD metrics. On both datasets, ANFM appears competitive with the two diffusion-based approaches, DiGress and ESGG.
5.2 Experiments with Expanded Synthetic Datasets
We supplement the results presented above by training our model on larger synthotic datasets. Namely, we generale training sets consisting of 8192 graphs and corresponding validation and test sets consisting of 256 graphs each. We use the same data generation approach as Martinkus et al. [2022) to obtain expanded planar and SBM datasets. Additionally, we produce an expanded dataset of lobster graphs using NetworkX (Hagberg) et al. 2008), done in (Liao et al. 2019 We perform one training run per dataset for the DFS variant and three independent runs for the line Fiedler variant. to illustrate robust We present the deviations observed across the three runs in Appendix F.2 We visualize samples from our model in Appendix F.3 In Table 2 we compare our method to our three baselines. For reasons of brevity, we only report the median performance here and refer to Appendix F.I for a critical discussion of techniques to evaluate performance across multiple runs. All models reach perfect uniqueness and novelty scores on the expanded planar and SBM datasets and comparable uniqueness and novelty performance on the expanded lobster dataset (c.f. Appendix F.2 We find that ANFM is substantially faster during inference than the diffusion models, consistently achieving at least 100-fold speedup in comparison to DiGress and ESGG. Moreover, we find that our method appears competitive with respect to sample quality, outperforming the two diffusion models on the expanded SBM datasel in terms of validity. On the expanded planar graph dataset, we observe that the line Fiedler ANEM variant outperforms or matches these baselines w...t. three of the four MMD metrics. For ESGG, we note that we obtain a surprisingly low validity score on the expanded SBM datasct and refer to Appendix G.5 for further discussion on this. We find that ANFM substantially outperforms the autoregressive baseline, GRAN, in terms of validity and MMD metrics.
10

---

Published in Transactions on Machine Learning Research (01/2026)
Table 2: Performance on expanded syuthetic datasets, evaluated on 1024 model samples. Showing a single run for the baselines and DFS, the median across three runs for the line Fiedler variant. *ESGG evaluation modified to draw graph sizes from empirical training distribution and use 100 refinement steps for determining SBM validity.
Expanded Planar Graphs ([V) = 64, Nerain 8192)
VUN (t)
Deg. (4)
Clus. (4)
Orbit (4)
Spec. (4)
Time (4)
GRAN
0.19
0.0061
0.1862
0.0961
0.0081
0.0303
DiGress
80.76
0.0004
0.0217
0.0045
0.0024
2.73
ESGG*
89.94
0.0007
0.0162
0.0074
0.0012
4.65
ANFM (Fal)
79.20
0.0004
0.0183
0.0002
0.0012
0.0154
ANFM (DFS)
45.61
0.0003
0.0296
0.0004
0.0017
0.0164
Expanded SBM Graphs (Nuain 8192)
VUN (t)
Deg. (4)
Clus. (4)
Orbit (4)
Spec. (4)
Time (4)
GRAN
25.29
0.0186
0.0086
0.0305
0.0022
0.133
DiGress
56.15
0.0002
0.0056
0.0076
0.0009
12.99
ESGG
3.52
0.0949
0.0121
0.0518
0.0122
39.42
ANFM (Fal)
75.98
0.0014
0.0051
0.0180
0.0011
0.0396
ANFM (DFS)
78.03
0.0008
0.0049
0.0049
0.0008
0.0397
Expanded Lobster Graphs (Nuam = 8192)
VUN (t)
Deg. (4)
Clus. (4)
Orbit (4)
Spec. (4)
Time (4)
GRAN
41.99
0.0436
0.0069
0.1510
0.1469
0.0399
DiGress
96.58
9.79 10-5
8.33 10-7
0.0016
0.0009
4.86
ESGG
63.96
0.0007
0.00
0.0027
0.0023
3.16
ANFM (Fal.)
79.10
0.0004
7.89 x 10-5
0.0010
0.0016
0.0175
ANEM (DFS)
87.60
7.82 x 10-5
1.64 x 10
0.0007
0,0010
0.0160
Consistent with our previous experiments, find that the DFS variant outperforms the line Fiedler variant two of the three datasets in terms of the VUN metric. Hence, the exploration of more effective filtration strategies remains an important area for future investigation.
5.3 Experiments with World Data
In this subsection, present empirical results the protein graph dataset introduced by Dobson & Doig 2003) and the GuacaMol (Brown et al. 2019) dataset consisting of drug-like molecules.
Proteins. While results have been reported for the protein dataset in previous works, we re-evaluate the baselines on 1024 model samples to reduce bias and variance in the reported metrics. We use a trained GRAN checkpoint provided by Liao et al. (2019) but re-train ESGG and DiGress, as no trained models are available. In Table we find that our model again substantially faster than the diffusion- based baselines. Moreover, it also 10 times faster than GRAN while outperforming with respect to all MMD metrics. Comparod to diffusion-based models, the sample quality of our approach appears worse by most, but not all, MMD metrics. We note that the sub-quadratic asymptolic sampling complexity (w.r.t the number of nodes) of ESGG starts to become noticeable at the large size of protein graphs, enabling substantially faster generation than DiGress. However, despite the cubic asymptotic complexity of ANFM, it remains over 100 times faster than ESGG.
So far, we have focused on generating un-attributed graphs. However, molecular structures require node and edge labels represent atom and bond types, respectively. Inspired by the approach of Li et al. (2020), first train ANFM to generate un-attributed topologies and then assign node and edge
GuacaMol.
11

---

Published in Transactions on Machine Learning Research (01/2026)
labels using a simple VAE. Details of this post-hoc labeling procedure can be found in Appendix A We re- port established metries for the GuacaMol benchmark: the Fréchet ChemNet distance (FCD) (Preuer et al. 2018) embeds the SMILES representations of valid generated molecules via a pre-trained language model and computes an optimal transport distance between the approximate generated and reference embedding distri- butions. The KT. Divergence metric (rrwnn et al. 2019 determines various physicochemical paramelers of the generated molccules and compares them to the reference distribution via the Kullback-Leibler divergence. Consistent with Brown al. (2019), both metrics are reported as the exponential of the scaled negative FCD and KL divergence and should thus be maximized. In Table E we compare the performance of ANFM to several baselines from Vignac et al. (2023), namely an LSTM model trained on SMILES strings (Brown eet al. 2019), graph MCTS (Brown et al.] 2019), and NAGVAE (Kwon et al. 2020]. Here, only DiGress and ANFM are general-purpose graph generation methods, while the other models are specific to molecule generation. Notably, ANFM demonstrates competitive performance with DiGress. Consistent with previous findings (Vignac et al. 2023 Xu et al. 2024 Qin et al. 2025), we observe that language models for SMILES strings (i.e., the LSTM model) remain strong baselines, outperforming general-purpose graph generators in terms of FCD and KL divergence.
Table 3: Performance of models on protein graph dataset. *Graph sizes are drawn from empirical training distribution.
Table 4: Performance of models GuacaMol benchmark.
Protein Grophs (100 S V 5000
Arros 587)
GuncsMol (2 S 88,
Nusin 1.34))
Deg. (4)
Clus. (4)
Orbit (1)
Spec. (1)
Time (4)
Valid (f)
Unique (1)
Novel (1)
Div (1) (1)
GRAN DiGress
0.0025
0.0610
0,1539
0.0051
2.25
LSTM
95.9
100
91.2
99.1
91.3
0.0006
0.0231
0.0289
0.0014
72:27
NAGVAE
95.5
38.4
ESSG*
0.0033
0.0216
0.0357
0.0008
19:48
MCTS
100
100
99.4
52.2
1.5
ANFM (RiL.
0.0024
0.0464
0.0332
0.0024
0.194
DiGres
92.9
ANFM (DFS)
0.0024
0.0370
0.0620
0.0020
0.191
ANPM (DFS)
75.6
100.0
98.3
96.1
65.2
5.4 Ablation Studies
In this subsection, we demonstrate that teacher forcing, noise augmentation, and adversarial fine-tuning are crucial components of our method. The substantial performance gains from noise augmentation and adver- sarial fine-tuning, in particular, suggest that exposure bias is significant factor affecting our autoregressive model. We also study the effect of filtration granularity, controlled by the hyper-parameter T'. In Ap- pendix H. we present extensive additional ablations, investigating alternative filtration functions, schedules, and node individualization schemes.
Table 5: Two ablation studies using the line Fiedler variant on the expanded planar graph dataset. Showing median + maximum deviation across three runs. For the noise ablation, we train for 100k steps in stage T. For the finctuning ablation, we train for 200k steps in stage I.
Noise Ablation
Finetuning Ablation
Stage I w/ Noise
Stage w/o Noise
Stage 11
Stage w/ Noise
VUN (t)
20.21 i 3:22
0.00 = 0.00
79.20 + 1.13
23.24 9.87
Deg. (L)
0.0058 0.0008
0.0864 + 0.0740
0.0004
5.43 10
0.0036 4 0.0009
Clus. (L)
0.1768
0.0106
0.3179 4: o 0037
0.0183
0.0014
0.1547 + 0.0260
Spec. (L)
0.0048
0.0011
0.1042 + 0.0700
0.0012
0.0004
0,0033 + 0.0014
Orbit (4)
0.0129
0.0189
0.7115 + 0.4411
0.0002
0.0016
0.0043 + 0.0029
Noise Augmentation. We find that noise augmentation of intermediate graphs substantially improves performance during training with teacher forcing (stage T). We illustrate this using the line Fiedler variant on the expanded planar graph dataset in Table (left). A corresponding experiment for the DFS variant can be found in Appendix H
12

---

Published in Transactions on Machine Learning Research (01/2026)
1.0
Inference Time [s]
0.25
ANFM
0.8
0.20
DjGress
VUN
0.6
0.15
0.4
0.10
0.2
ANFM
0.05
DiGress
0.0
0.00
20
30
40
50
60
70
20
30
40
50
60
70
# Generation Steps
# Generation Steps
(a) Planar VUN vs T
(b) Inference time vs T
Figure 2: Performance of ANFM and DiGress on the expanded planar dataset as number of generation steps varies. The original (default) DiGress variant uses 1000 generation steps.
GAN Tuning. In Table 5 (right), we compare performance after training with teacher-forcing and sub- sequent adversarial fino-tuning on the expanded planar graph dataset. We find that adversarial fino-tuning substantially improves performance, both lerms validity and MMD metrics. A correspouding analysis for the DFS variant and the expanded SBM and lobster datasets can be found in Appendix
Teacher Forcing. We illustrate in Table 6 the significance of the teacher forcing training stage (i.e. stage Т). We compare the performance that ANFM achieves with adversarial fine-tuning using two different check- points collected during the first training stage. Initializing fine-tuning with an earlier checkpoint substantially harms performance, underscoring the important role of teacher forcing training finding a near-optimal model before performing the adversarial fine-tuning.
Table 6: Performance of the line Fiedler ANFM variant on the expanded planar graph dataset with different training durations during stage I, followed by stage training. Showing median across three runs for 200k steps and single run for 10k steps.
# Stage Steps
VUN (t)
Deg. (1)
Clus. (L)
Orbit (4)
Spec. (4)
200k
79.20
0.0004
0.0183
0.0002
0.0012
10k
3.32
0.0016
0.2278
0.0464
0.0069
we study the impact of filtration granularity, i.e., the number of steps T, generation quality and speed of ANFM. Analogously, investigate how the number of denoising steps influences quality and speed in DiGress. We re-train the models with varying T. ANFM consistently outperforms DiGress in computational efficiency across all T. While DiGress only achieves a maximum VUN of 41% for our largest considered T, ANFM achieves a VUN of 81% for = 30. We provide a complementary analysis of MMD metrics in Appendix L
Filtration Granularity. In Figure 2
6 Conclusion
We proposed ANFM, an efficient autoregressive graph generative model basod on graph filtration. ANFM generates high-quality graphs, outperforming existing autoregressive models and rivaling discrete diffussion approaches in terms of quality while being substantially faster at inference. Various ablations demonstrated the configurability of ANFM and indicated that exposure bias is an important challenge for autoregressive graph modeling. Our experiments suggested that ANFM's unique ability to construct non-montonic graph sequences and training strategies encouraging this behavior (noise augmentation and adversarial finetuning via RL) are the main drivers of performance.
We have argued that our proposed filtration approach generalizes existing autoregressive methods by al- lowing for sequences of subgraphs with non-induced edge sets. Although this affords additional flexibility
13

---

Published in Transactions on Machine Learning Research (01/2026)
in constructing graph sequences for training, the non-induced sequences we investigated (line Fiedler filtra- tions) were often outperformed by sequences of subgraphs with induced edge sets (DFS filtrations). Thus, the exploration of alternative filtration strategies is left for future research.
While we have demonstrated that node and edge attributes may be sampled in a post-hoc fashion using a VAE, direct modeling within ANFM remains an interesting area for future investigation. We also highlight issues with existing benchmark datasets, where small sample sizes during evaluation lead to unreliable results with high variance and bias. Systematically addressing these challenges is essential for enabling more reliable and fair benchmarking in future research.
Acknowledgements
This work was supported by the Max Planck Society, We thank Nina Corvelo Benz for her insightful feedback the manuscript.
References
J. M. Anthonisse. The rush in a directed graph. Tech. Rep. BN 9/71, Stichting Mathematisch Centrum, 2e Boerhaavestraat 49, Amsterdam, October 1971.
Jacob Austin, Daniel D. Johnson, Jonathan Ho, Daniel Tarlow, and Rianne van den Berg. Structured denoising diffusion modols in discrete state-spaces. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
Davide Bacciu, Alessio Micheli, and Marco Podda. Edge-based sequential graph generation with recurrent neural networks. Neurocompuling, 416:177-188 189, 2020. doi: 1LI01//IBBBCCOM2211111....
Samy Bengio, Oriol Vinyals, Navdeep Jaitly, and Noam Shazeer. Scheduled sampling for sequence prediction with recurrent neural networks. In Advances in Neural Information Processing Systems (NeurIPS), 2015.
Andreas Bergmeister, Karolis Martinkus, Nathanaël Perraudin, and Roger Wattenhofer. Efficient and scal- able graph generation through iterative local expansion. In International Conference on Learning Repre- sentations (ICLR), 2024.
Yoann Boget. Simple and critical iterative denoising: A recasting of discrete diffusion in graph generation. In International Conference on Machine Learning (ICML.), 2025.
Ulrik Brandes. On variants of shortest-path betweenness centrality and their generic computation. Soc. Networks, 30(2):136-145, 2008. doi: 10. 10010//.SOCNET.200...111
Nathan Brown, Marco Fiscato, Marwin HS Segler, and Alain C Vaucher. Guacamol: benchmarking models for de novo molecular design. Journal of chemical information and modeling, 59(3):1096-1108, 2019.
Nicola De Cao and Thomas Kipf. Molgan: An implicit generative model for small molecular graphs. arXiv preprint 1005 11973, 2018
Dexiong Chen, Leslic O'Bray, and Karsten M. Borgwardt. Structuro-aware transformer for graph represen- talion learning. In International Conference on Machine Learning (ICML), 2022.
Xiaohui Chen, Jiaxing He, Xu Han, and Liping Liu. Efficient and rrgree-ggidee graph generation via discrete diffusion modeling. International Conference on Machine Learning (ICMI., 2023.
Paul D Dobson and Andrew J Doig. Distinguishing enzyme structures from non-enzymes without alignments. J. Mol. Biol., 330(4):771-783, July 2003.
Vijay Prakash Dwivedi, Anh Tuan Luu, Thomas Laurent, Yoshma Bengio, and Xavier Bresson. Graph neural networks with learnable structural and positional representations. In International Conference on Learning Represendations (ICLR), 2022.
14

---

Published in Transactions on Machine Learning Research (01/2026)
Vijay Prakash Dwivedi, Chaitanya K. Joshi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. Journal of Machine Learning Research (JMLR), 24: 43:1 43:48, 2023.
Edelsbrunner, Letscher, and Zomorodian. Topological persistence and simplification. Discrete 8 Compula- tional Geometry, 28(4):511 533, Nov 2002. ISSN 1432-0444. doi: 00.1007//000454-0022288885
Francosco Gentile, Jean Charle Yaacoub, James Gleave, Michael Fernandez, Anh-Tien Ton, Fuqiang Ban, Abraham Stern, and Artem Cherkasov. Artificial intelligence enabled virtual screening of ultra-large chemical libraries with deep docking. Nature Protocols, 17(3):672-69) 697, Mar 2022. ISSN 1750-2799, doi:
10.1088//411986-221100000222
Rafael Komez-Bommarrllit Jorge rin, Martin A. Blood-Forsythe, Hyun Sik Chac, Markus Einzinger, Dong-Gwang Ha, Tony Wu, Georgios Markopoulos, Soonok Jeon, Hosuk Kang, Hiroshi Miyazaki, Masaki Numata, Sunghan Kim, Wenliang Huang, Seong Ik Hong, Mare Baldo, Ryan P. Adams, and Alén Aspuru-Guzik. Design of elficient molec- ular organic light-emitting diodes by a high-throughput virtual screening and experimental approach. Nature Materials, 15(10):1120-13) Oct 2016. ISSN 1476-4660. doi: 10. 00.1038/mmmt44117
Timothy D. Hirzel, David Duvenaud, Dougal Maclau-
lan J. Goodfellow, Jean Pouget-Abadiee, Mehdi Mirza, Bing Xu, David Warde- Farley, Sherjil Ozair, Aaron C. Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in Neural Information Processing Systems (NeurIPS), 2014.
Nikhil Goyal, Harsh Vardhan Jain, and Sayan Ranu. Graphgen: A scalable approach to domain-ognostic labeled graph generation. In WWW '20: The Web Conference, 2020.
Arthur
Gretton, Karsten M. Borgwardt, Malte J. Rasch, Bernhard Schölkopf, and Alexander J. Smola. A kernel two-sample test. Journal of Machine Learning Research (JMLRR, 14723-7733 2012. doi: 10.5555/ 2503308.2188410.
Aric Hagborg, Picter Swart, and Daniel Chult. Exploring network structure, dynamics, and function using networkx. In Proceedings of the 7th Python in Science Conference, 06 2008
Frank Harary and R. Z. Norman. Some properties of line digraphs. Rendiconti del Circolo Matematico di Palermo, 9:161 168, 1960.
Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay S. Pande, and Jure Leskovec. Stralegies for pre-training graph neural networks. In International Conference on Learning Representations (ICLR), 2020.
John Ingraham, Vikas K. Garg, Regina Barzilay, and Tommi S. Jaakkola. Generative models for graph-based protein design. In Advances in Neural Information Processing Systems (NewrIPS), 2019.
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), 2022.
Mahdi Karami. Higen: Hicrarchical graph generative networks. In International Conference on Learning Representations (ICLR), 2024.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Confer- ence on Learning Representations (ICLR), 2015.
Diederik P. Kingma and Max Welling. Auto-encoding variational bayes. In International Conference on Learning Represendations (ICLR), 2014.
Thomas N. Kipf and Max Welling. Variational graph auto-encoders. arXiv preprint arXtv:6611.07900 2016.
Lingkai Kong, Jiaming Cui, Haotian Sun, Yuchen Zhuang, B. Aditya Prakash, and Chao Zhang. Autore- gressive diffusion model for graph generation. In International Conference on Machine Learning (ICML), 2023.
15

---

Published in Transactions on Machine Learning Research (01/2026)
Youngchun Kwon, Dongscon Lee, Youn-Suk Choi, Kyoham Shin, and Scokho Kang. Compressed graph representation ion for scalable molecular graph generation. Journal of Cheminformalics, 12(1) (21))58, Sep 2020.
ISSN 1758-2946. doi: 10.1186/s133221-00000000
Cyrus Levinthal. How to fold graciously. In Mossbauer Spectroscopy in Biological Systems: Proceedings of a meeling held Allerton House, Monticello, Illinois., 1969. URL ottpp////pppi.etttttttooooooorr. orgg Co 9923873
Yibo Li, Jianxing Hu, Yanxing Wang, Jielong Zhou, Liangren Zhang, and Zhenming Liu. Deepscaffold: A comprehensive tool for scaffold-based de novo drug discovery using deep learning. Journal of Chemical Information and Modeling, 60(1):77-91 -9,, Jan 2020. ISSN 1549-9596. doi: (000///ac.jci../bbbe..
Yujia Li, Oriol Vinyals, Chris Dyer, Razvan Pascamu, and Peter W. Battaglia. Learning deep generative models of graphs. arXiv preprint 1803. 1803.0332,, 2018.
Renjie Liao, Yujia Li, Yang Song, Shenlong Wang, William L. Hamilton, David Duvenaud, Raquel Urtasun, and Richard S. Zemel. Efficient graph generation with graph recurrent attention networks. In Advances in Newral Information Processing Systems (NewrIPS), 2019.
Qi Liu, Miltiadis Allamanis, Mare Brockschmidt, and Alexander L. Gaunt. Constrained graph variational autoencoders for molecule design. In Advances in Neural Information Processing Systems (NeurIPS), 2018.
Yijing Liu, Chao Du, Tianyu Pang, Chongxuan Li, Wei Chen, and Min Lin. Graph diffusion policy opti- mization. arXiv preprint arXiv:2402.16300 16302, 2024.
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), 2022.
Eyal Mazuz, Guy Shtar, Bracha Shapira, and Lior Rokach. Molecule generation using transformers and policy gradient reinforcement learning. Scientific Reports, 13(1):8799, May 2023. ISSN 2045-2322. doi: 10.1038/s41598-000 93--60333----
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), 2020.
Leslie O'Bray, Bastian Rieck, and Karsten M. Borgwardt. Filtration curves for graph representation. In Conference on Knowledge Discovery and Data Mining (KDD), 2021.
Ethan Perez, Florian Strub, Harm de Vries, Vincent Dumoulin, and Aaron C. Courville. Film: Visual rea- soning with general conditioning layer. In Proceedings of the AAAI Conference on Artificial Intelligence, 2018.
P G Polishchuk, T I Madzhidov, and A Varnek. Estimation of the size of drug-like chemical space based on GDB-17 data. Journal of Computer-Aided Molecular Design, 27(8):675 679, August 2013.
Kristina Preuer, Philipp Renz, Thomas Unterthiner, Sepp Hochreiter, and Günter Klambauer. Fréchet chemnet distance: A metric for generative models for molecules in drug discovery. Journal of Chemical Information and Modeling, 58(9):1736 1741, Sep 2018. ISSN 1549-9596. doi: 10.1021 10.1021/acs.jcinn jct.//cc.cmmmm00222...
Yiming Qin, Manuel Madeira, Dorina Thanou, and Pascal Frossard. Defog: Discrete flow matching for graph generation. International Conference on Machine Learning (ICML), 2025.
Ladislav Rampásck, Michael Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Dominique Beaini. Recipe for general, powerful, scalable graph transformer. In Advonces in Neural Information Processing Systems (NeurIPS), 2022.
16

---

Published in Transactions on Machine Learning Research (01/2026)
Mare' Aurelio Ranzato, Sumit Chopra, Michael Auli, and Wojeiech Zaremba. Sequence level training with recurrent neural networks. In International Conference on Learning Represenlations (TCLR), 2016.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimiza- tion algorithins. arXiv preprinl ar (at:1777.0034/ 2017.
Till Hendrik Schulz, Pascal Welke, and Stefan Wrobel. Graph filtration kernels. In Proceedings of the AAAI Conference on Artificial Intelligence, 2022.
Jianbo Shi and Jitendra Malik. Normalized cuts and image segmentation. In Proceedings of the Conference on Computer Vision and Pattern Recognition (CVPR), pp. 731-737. IEEE Computer Society, 1997.
Martin Simonovsky and Nikos Komodakis. Graphvae: Towards generation of small graphs using variational autoencoders. In 27th International Conference on Artificial Neural Networks (ICANN), Proceedings, Part I, volume 11139 of Lecture Notes in Computer Science, pp. 412-422. Springer, 2018.
Joshua Southern, Jeremy Wayland, Michael M. Bronstein, and Bastian Rieck. Curvature filtrations for graph generative model evaluation. In Advances in Neural Information Processing Systems (NeurIPS), 2023.
Nitish Srivastava, Geoffrey E. Hinton, Alex Krizhevsky, Llya Sutskever, and Ruslan Salakhutdinov. Dropout: simple way to prevent neural networks from overfitting. Journal of Machine Learning Research (JMLR), 15(1):1929-1958, 2014. doi:
llya O. Tolstikhin, Neil Houlsby, Alexander Kolesnikov, Lucas Beyer, Xiaohua Zhai, Thomas Unterthiner, Jessica Yung, Andreas Steiner, Daniel Keysers, Jakob Uszkoreit, Mario Lucic, and Alexey Dosovitskiy. Mlp-mixer: An all-mlp architecture for vision. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
Clément Vignac, Igor Krawczuk, Antoine Sirandin, Bohan Wang, Volkan Cevher, and Pascal Frossard. Digress: Discrete denoising diffusion for graph generation. In International Conference on Learning Rep- resentations (ICLR), 2023.
Ronald J Williams and David Zipser. A learning algorithm for continually running fully recurrent neural networks. Neural computation, 1(2):270 280, 1989.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Leurning Representations (ICLR), 2019.
Zhe Xu, Ruizhong Qiu, Yuzhong Chen, Huiyuan Chen, Xiran Fan, Menghai Pan, Zhichen Zeng, Mahashweta Das, and Hanghang Tong. Discreto-state continuous-tim diffusion for graph generation. In Advances in Neural Information Processing Systems (NewrIPS), 2024.
Jiaxuan You, Bowen Liu, Zhitao Ying, Vijay S. Pande, and Jure Leskovec. Graph convolutional policy network for goal-directed molecular graph generation. In Advances in Neurul Information Processing Systems (NeurIPS), 2018a.
Jiaxuan You, Rex Ying, Xiang Ren, William L. Hamilton, and Jure Leskovec. Graphrun: Generating realistic graphs with deep auto-regressive models. In International Conference on Machine Learning (ICML), 2018b.
James Jian Qiao Yu and Jiatao Gu. Real-time traffic speed ostimation with graph convolutional generative autoencoder. IEEE Trons. Intell. Transp. Syst., 20(10)33940 3951, 2019. doi: 10.1109/TITS. 2019.2910560.
Lantao Yu, Weinan Zhang, Jun Wang, and Yong Yu. Seggan: Sequence generative adversarial nets with policy gradient. In Proceedings of the AAAI Conference on Artificial Intelligence, 2017.
Qi Zhao and Yusu Wang. Learning metrics for persistence- based summaries and applications for graph classification. In Advonces in Neural Information Processing Systems (NeurIPS). 2019.
Afra Zooorodiian and Gunnar E. Carlsson. Computing persistent homology. Discrete & Computational Geometry, 33(2):249-21) 274, 2005. doi: 10.1007//5004544-00444444 -14466
17

---

Published in Transactions on Machine Learning Research (01/2026)
Appendix
This appendix is organized as follows: We provide details on post-hoc attribute generation Appendix In Section B we analyze the runtime complexity of ANFM and investigate variant. that. is asymplotically
more efficient w.r.t. T. In Section C we show that optimize a lower-bound on the data log- log-likelihood in training stage I. Details on hyperparameters and model architecture are provided in Sections D and E We
provide evaluation results across several runs and qualitative model samples in Section Section G provides details on our baselines. Additional ablations on filtration function, schedule, node individualization, etc., are presented in Section H.
We discuss the shortcomings of established evaluation approaches in Section Finally, we detail the adversarial finetuning algorithm in Section
A Generating Attributed Graphs
A.1 Variational Inference
To generate attributed graphs (G) with topology G and node and edge labels ly and Le, we propose to first generate the un-attributed graph topology using ANFM. Subsequently, we label nodes and edges using a separate model. Le., we decompose the joint distribution as:
Po Iv,
-label(LE, (LE.Iv G) Po PANFM(G)
(12)
where pe plabel generates node and edge attributes. We take inspiration from Li ct al. (2020) and train pl plabel variational autoencoder.
Variational Inference. Let G= F) be graph topology from the training dataset and let ly V X and (g y be ground-truth node and edge labels for G, respectively. An encoder do maps the labeled graph (G) to a distribution over D-dimensional latent node representations 2 E RR V A decoder Po maps a tuple (G,z), i.e. the graph topology combined with a latent representation, to a distribution over node and edge attributes. In practice, we consider discrete attributes and po parametrizes a product distribution across nodes and edges. If X or factorize into product of simpler spaces (i.e., when there are multiple node edge attributes). pe parametrizes corresponding product distribution over X or V. The encoder te parametrizes Gaussian distribution with a diagonal covariance matrix. We formulate the typical evidence lower bound (Kingma & Welling 2014):
PolLE,Ly by G) 2 Eg G.G.dv Ioo(,,,l [G, - DKL G,,,,,) IN(0,) (0)
(13)
Architecture. We implement Js and pa as GraphGPS (Rampásek et al. 2022 models. Since op- crates on odge-labeled graphs, we use GINE message passing layers (Hu et al. 2020) within its graph transformer. The decoder Pe: on the other hand, only operates on node representations, and we therefore use GIN layers (Xu et al., 2019). The two GNNs are provided with Laplacian and random walk positional embeddings Dwiieddi et al.) 2022) and use 5% dropout layers (Srivastava et al., 22014). We feed the node representations produced by pe through MLPs to generate distributions over node attributes. To generate distribution over the attribute of an edge v), we add the node representations corresponding to u and v and feed the resulting vector through an MLP.
Training. We train Is and pa jointly by maximizing a re-weighted version of the ELBO in Equ. Specifically, we divide the loss for a given datum (G.4g,ly) by [V], the cardinality of the node set of G.
13
Sampling. To sample attributes, we draw latent node representations z from the standard normal distri- bution. We select the maximum likelihood node and edge attributes from po( G,z). The encoder ga may be discarded after training.
18

---

Published in Transactions on Machine Learning Research (01/2026)
Figure 3: Uncurated samples from ANFM model trained on GuacaMol.
A.2 Details on GuacaMol Experiments
Below, we provide details on the molecule graph generation presented in Sec. 5.3 As described in Ap- pendix A we train ANFM on the un-attributed molecule topologies GuacaMol. Independently, we train VAE to generate attributes conditioned on a topology. To sample a molecule, we first generate a graph using ANFM and label nodes and edges using the VAE.
Attributes. We produce edge labels that indicate the bond type between heavy atoms, distinguishing between single, double, triple, and aromatic bonds. To reconstruct the correct molecule from its graph representation, we find that we require require several node attributes. Namely, given an atom (i.c., node). we generate its type (i.e., the element), the number of explicit hydrogens bound to it, the number of radical electrons, and its partial charge.
ANFM Hyperparameters. We train an ANFM model using the DFS filtration strategy. stage I, use similar hyper-parameters for the other datasets. We T 30 filtration steps, learning rate of 10-5, local batch size of 64 two GPUs, and 300k training steps. Throughout stage I training, we monitor validation loss and ensure that the model does not overfit. During training stage II, we use batch size of 32 and a learning rate of 2.5 x 10 for the generative model. The discriminator has 3 layers and a hidden dimension of 32. The other hyperparametors the discriminator and value model match those used in the other experiments.
VAE Hyperparameters. We use 5-layer GraphGPS (Rampásek et al. 2022 models for the encoder and decoder, respectively. The hidden dimension is 256 while we choose the latent dimension D to be 8. The Laplacian positional embedding 3-dimensional while the random walk positional embedding is 8-dimensional. We train for 250 epochs on the GuacaMol dataset, using batch size of 512, an Adam optimizer (Kingma & Ba 2015 and learning rate of 10-4
Model Samples. In Figure we show uncurated samples from the ANFM model.
B Sampling Complexity of ANFM
B.1 Complexity Analysis
In the following, we analyze the asymptotic runtime complexity of sampling graph from our proposed model and the baselines studied in Section
19

---

Published in Transactions on Machine Learning Research (01/2026)
Proposition B.1. The asymptotic runtime complexity for sampling graph with N nodes from ANFM with T limesteps is:
N
(14)
Proof. To sample a graph from an ANFM, one has to perform 7 forward passes through our proposed mixer architecture. These forward passes are preceded by the computation of various graph features, including Laplacian eigenvaltes and cigenvectors. This eigendecomposition has complexity O(N2). At timestep I N, the structural mixing layers have complexity O(N2) due to the self-attention component of SAT. The temporal mixing layers, on the other hand, have complexity (( + 1)), as cach node attends its representations timesteps O,...,l. We bound this complexity by O(NT). Hence, aggregating these complexities across all T timesteps, obtain the following runtime complexity:
O TN TN O
(15)
Below we show that the asymptotic complexity of ANFM differs from the complexity of DiGress only in the quadratic term w.r.t. T:
Proposition B.2. The asymptotic runtime complexity for sampling graph with N nodes from a DiGress model with T denoising sleps is:
?(TN2)
(16)
Proof- Similar to ANFM, DiGress performs an eigendecomposition of the graph laplacian in each denoising step. Hence, one obtains complexity of (2(5)) in each timestep, resulting in an overall complexity of ((TN3).
We further analyze the asymptotic complexities of our other baselines of Sec. 5.2 and Sec. 5.3
Proposition B.3. The asymptotic runtime complerity for sampling graph with N nodes from GRAN model is 2(N3).
Proof. GRAN explicitly constructs dense adjacency matrix with N entries.
Proposition B.4. The asymptotic runtime complexity of sampling a graph with N nodes and M edges from ESGG model is S(N + +M).
Proof. This bound should trivially be satisfied by any generative model, as one already needs Q(N + M) bits to represent graph with M edges on N nodes. We refer to (Bergmeister et al. 2024 for discussion on how tight this bound is.
In Table summarize these asymptotic complexities.
While this analysis may suggest that ANFM Table 7: Asymptotic runtime complexities for sampling from different graph generative models.
Method
Sampling complexity
ANFM
O + TN3
DiGress
Q(TN3) ((N22)
GRAN
ESGG
Q(N + M)
does not scale well to extremly large graphs, we caution the reader that the asymptotic behavior may not accurately reflect efficioncy in practice: Firstly, multiplicative constants and lower-order terms are ignored. Hence, it remains unknown in which regimes the asymptotic behavior governs inference time. Secondly, the analysis was made under the assumption that hyper-parameter choices (i.e. depth, width, etc.) is kept
20

---

Published in Transactions on Machine Learning Research (01/2026)
constant N and M increase. It is reasonable to expect that more expressive networks required to model large graphs.
B.2 A First-Order Autoregressive Variant
As demonstrated in Appendix B.1 the runtime of ANFM quadratic in the number of generation steps T due to the temporal mixing operations which are implemented transformer decoder layers. Analogously, one may verify that the memory complexity of sampling from ANFM is lincar in T. In this subsection, we study simplified variant of ANFM in which we use first-order autoregressive structure. Le., we enforce:
po(GetilGr..... ,,) po(G(+1(G))
(17)
We implement this by ablating the causally masked sell-attention mechanism from the transformer layers in our mixer model, leaving only the feed-forward modules. The resulting first-order variant of ANEM has space complexity which is independent of T and runtime complexity which is linear in T.
We train such first-order variant of ANFM on the expanded planar graph dataset, using the line Fiedler filtration strategy and the same hyperparameters as for the transformer-basee variant (see Appendix D.2 Using the first-order variant, we observe training instabilities after the first 100k training steps of stage I. While reducing the learning rate rectifies this instability, we find that this slows learning progress substan- tially. Instcad, we use model chockpoint at 100k steps and continue with training stage II.
In Table 8 we compare the performance of the transformer- and the first-order variants after 100k steps of stage I training. In Table g we compare the performance after the subsequent stage II training, While we perform only 100k training steps in stage I for the first-order variant, we perform 200k training steps for the transformer-basee variant, as it did not exhibit instabilities.
Table 8: Performance of two ANFM variants on the expanded planar graph datasct after 100k steps of stage training. Showing median across three runs for the transformer- based variant and a single run for the first-order variant. All models reach perfect uniqueness and novelty scores.
VUN (f)
Deg. (4)
Clus. (1)
Orbit (4)
Spec. (4)
Transformer
20.21
0.0058
0.1768
0.0129
0.0048
Orett-
5.66
0.0004
0.1782
0.0041
0.0035
Table 9: Performance of two ANFM variants on the expanded planar graph dataset after stage II training. The transformer-based variant was trained for 200k steps in stage I while the first-order variant trained for 100k steps in stage 1. Showing median across three runs for the transformer-ben based variant and single run for the first-order variant. All models reach perfect uniqueness and novelty scores.
VUN (t)
Deg. (1)
Clus. (1)
Orbit (L)
Spec. (L)
Time (1)
Transformer
79.20
0.0004
0.0183
0.0002
0.0012
0.0278
First-Ordes
70.02
0.0004
0.0229
0.0046
0.0013
0.0247
Generally, we observe that the transformer-based ANFM variant slightly outperforms the first-order variant in terms of quality. However, the first-order variant remains competitive after stage trainig and, thus, may be a suitable alternative cases where a large T chosen. In our sctting (T = 30), however, we find that the first-order variant is not substantially faster during inference, indicating that the runtime is not governed by the quadratic complexity in T.
21

---

Published in Transactions on Machine Learning Research (01/2026)
C A Bound on Model Evidence in ANFM
Given a graph GT, let QGGT-I....Gi GT) be the data distribution over noisy filtrations of this graph, de- termined by the choice of filtration function, scheduling, and noise augmentation. We assume that Go is deterministically the completely disconnected graph. Moreover, we note that by applying our noise augmen- tation strategy we ensure that is supported everywhere. Given some graph Gr, we can now derive the following evidence lower bound:
log Po (Gr) log Σ
Po(Gr,...,GGu
GrE
Po Go)
log
(GT-- GiG..) (CTT,,,... G1 GT)
(18)
Po Go)
log QGTT-I..... G₁
log pe (G Go) - log (GGGTI-I.......... G.GG)
= M(Grran..GG))aa---1
We note that this lower bound is (up to sign and constant that does not depend on 0) exactly the autoregressive loss we use in training stage I. Hence, while we train ANFM to model sequences of graphs, we do actually optimize an evidence lower bound for the final graph samples Gr.
D Hyperparameters
D.1 Practical Advice on Hyperparameter Choice
In the following, we provide some practical advice on choosing some of the most important hyper-paramctorr in ANFM. Generally, we tuned few hyper-paramelers in our experiments. We found the number of generation steps T to be one of the most impactful aaperr-arameters.
Filtration Function. The filtration function f E + R the main component determining the structure of the graph sequence during stage training. We recommend that should convey meaningful information about the structure and assign (mostly) distinet values to distinct edges. We note that fails to assign distinet values to edges, many edges may be added in a single generation step, regardless of the choice of T. We found both the edge Fiedler function and the DFS filtrations to perform well in many settings. We recommend that practitioners utilize these filtration strategics and perform experiments with further filtration functions that incorporate domain-specifie inductive biases. In the case of generating protein graphs, for instance, one may consider a filtration function that quantifies the distance of residues in the sequence (this filtration would first generate a backbone path, followed by increasingly long-range interactions of residues).
Filtration Granularity. As we demonstrate Soc. 5.4 the choice of the number of generation steps T has substantial influence on sampling efficiency and generation quality. Generally, T can be chosen substantially smaller than in other autoregressive models. In our experiments, we chose T S 32. We recommend that practitioners experiment with different values in this order of magnitude. We further caution that increasing T does not necessarily improve sample quality and may actually harm it.
Scheduling Function. The filtration schedule governs the rate at which edges are added at different timesteps. In the case of the line Fiedler filtration function, it is determined by 7, which should be mono- tonically increasing with 7(0) = 0 and 7(1) = 1. We found the heuristic choice of r(t) ;= to work well in many settings. However, as we demonstrate alternative. We recommend that practitioners validate stage I training with a convex, linear, and concave scheduling function. We note that the scheduling function is no longer used during stage II training, as the
Appendix H. the concave schedule may be a promising
22

---

Published in Transactions on Machine Learning Research (01/2026)
model is left free to generate arbitrary intermediate graphs. Hence, performance after stage training may be a suitable metric for selecting scheduling function.
Noise Augmentation. We use noise augmentation during training stage I to counteract exposure bias, i.e. the accumulation of errors in the sampling trajectory. Manual inspection of the graph sequence Gu...., GT may be difficult. However, we found that inspecting the development of the edge density over this graph sequence can provide a simple tool for diagnosing exposure bias. In models that do not utilize noise aug- mentation, we can observe that, after some generation steps, the edge density oftentimes deviates from its expected behavior (e.g. by suddenly increasing or dropping substantially). In this case we expect that noise augmentation rectify exposure bias. In experiments, we find that do not need to tune the noise schedule. Instead, we fix single schedule that is shared across all models. For details this schodule, refer to Appendix D.2
Perturbation of Node Orderings. During training stage 1, ANFM variants using the line Fiedler fil- tration function may overfit small datasets. This manifests as an increase in validation loss, while the validation MMD metries continue to improve. We observe this behavior only on the small datasets in Sec. 5. and find that it can be mostly attributed to the node ordering used to derive initial node representations (c.f. Appendix E.1 J. We recommend to monitor validation losses during stage training. If the validation loss starts slowly increase while the training loss continues decrease, we recommend to randomly perturb the node ordering, as described in Appendix 1. The noise scale should be increased until no over-fitting can be observed. We find that the DFS filtration strategy less prone to overfitting, DFS node orderings are not unique. Hence, we may include many distinct filtrations of single graph GT in our training set.
D.2 ANFM Hyperparameters
In Tables 10 and 11 summarize the most important hyperparameters of the generative model used in our experiments, including the number of filtration steps (T), mixture components (K), learning rate (LR), batch size (BS) in the format num_gpus X
local_bes and the mumber of perturbed filtration sequences we produce per graph in our training set (# Perturbations).
Table 10: Hyper-parameten for line Fiedler variant of ANFM.
SPECTRE Planar
SPECTRE SBM
Expanded Planar
Expauded SBM
Expanded Lobster
Protein
T
30
15
30
15
30
15 16
# Layers
Hidden Dim
256
Leplacian PE dim.
4
RWPE dim.
20
Angm.
A, affine with A
Ar-
# Perturbations
256
256 Yes
4 No
8 No
Pecturb Node Order
No
Stg. T L.R
2.5 10
10
2.5 x 10
x 10
1 x 10
1 x 10
Slg. grad. clip
Noue
Stg. T BS
2 1 x
2 x 1 x
32
2 1
32
2 4 x 100k
Stg. Steps
100k:
Stg. I Precision
BF16 AMP
Slg. LR
1.25 10-7
Stg. II BS
x 4 x
x 4
x 4 32
1 4
4. 32
x 16 1.5k
Stg.
we additionally provide the most important hyperparameters of the discriminator and value model trained during the adversarial fine-tuning stage.
In Table 12
23

---

Published in Transactions on Machine Learning Research (01/2026)
Table 11: hyper-parametery for DFS variant of ANFM. Parameters that do not appear this table exactly
match the corresponding parameters for the line Fiedler variant, c.f. Table I0
SPECTRE Planar
SPECTRE SBM
Expanded Planar
Expanded SBM
Expanded Lobster
Protein
T.
32
15
32
30
# Perturhations Perturb Node Order
1,024
512
32
32
16
No
Skg. 1 LL
x 10
5 x 10
1 x 10
5 10
5 x 10
x 10-
Stg. grad. clip
250
# Stg. I Steps
200k
200k
200k
200k
100k
200k
Stg.
Table 12: Hyper-pane parameters of discriminator and value model used during adversarial fine-tuning.
SPECTRE Planar
SPECTRE SBM
Expanded Planar
Expanded SBM
Expanded Lobster
Protein
LR.
1.00 x 10-4
BS
x
Layers
3
Hidden dim.
32
128
128
128 x 32
128
64
RWPE dim.
20
20
20
20
LR
2.50 x 10-4
VaL
BS
Layers
Hidden dim.
128
E Details on Architecture
E.1 Input Node Representations
We define the input node represenlations as:
o = Jo(G,); + Waode
(19)
random walk encodings (Dwivedi et al. 2022), and cycle counts following DiGress Vignac et al, 2023 For precise definitions of these features, we refer to Appendix E.2 The matrix Wnood E ERDD is trainable embedding layer where N denotes the cardinality of the largest vertex set seen during training. It is important to note that the computation of input node representations requires a specifie node ordering to index Wnode, While the permutation equivariance of our model and the symmetry of the initially empty graph Go allow for arbitrary ordering during inference, we employ a structured approach during teacher-forcing training. This ordering is derived from the structure of the graph Gr and depends the filtration strategy.
where So produces node features from Laplacian positional encodings (Dwivedi el. al. 2023
Node Ordering for DFS Variant. The filtration function of the DFS variant is derived from DFS node ordering of Gr. Hence, we simply use this node ordering to assign positional embeddings.
Node Ordering for Line Ficdler Variant. For the line Fiedler variant, we propose a node weighting scheme h > IR defined as:
h(1) == We(() jENot()
Σ f(eig) ViEV,
(20)
where Ni(1) represents the neighborhood of node i in G. This weighting assigns to each node the average weight of its incident edges, as determined by the filtration function f. We then establish node ordering such that h non-increasing. The impact of different ordering strategies on model performance is further studied and compared in Appendix
When training on small datasets, such as those introduced by Martinkus 2022), we find that the node individualization in Eqn. (19) can lead to overfitting. This manifests increase validation loss, while
24

---

Published in Transactions on Machine Learning Research (01/2026)
the evaluation metrics (i.e. MMD and VUN) continue to improve. As data augmentation strategy to avoid overfitting, we propose to add Gaussian noise to the node weights hy defined in Eqn. (19 when training on small datasets, Le., we use the perturbed node weights
hG(s) *N(0,²²)
(21)
for sorting the nodes. We emphasize that this measure independent the perturbation of intermediate graphs introduced in Sec. 1.2 Moreover, we perturb node orderings only in the experiments on the small SPECTRE datasets (i.c., Sec 5.1
E.2 Positional and Structural Encodings
In this section, we describe the positional and structural encodings (PSE) we use to construct (o(G.). The positional and structural encodings are obtained by stacking Laplacian positional embeddings, random walk encodings, and cycle counts: PSE LPE || RWE || CC R In the following, we describe how each of the three components is computed. Let A be the adjacency matrix of G. and let D RRRNN be the diagonal matrix containing the node degrees.
Laplacian Positional Encoding. For h > 0, the k-dimensional Laplacian positional encoding is defined as the first orthonormal eigenvectors with non-zero eigenvalues of the symmetrically normalized Laplacian matrix RNNN
if i = j and d, + 0,
Lig =
if i + j and Ai = 1,
(22)
v Dj
0,
otherwise.
These eigenvectors are stacked into the matrix LPE, E R.Nk In addition, we compute the corresponding cigenvalues E R* and replicate them across nodes: LPE2 == Ix= E NR The final Laplacian positional encoding obtained by stacking eigenvectors and replicated eigenvalues: LPE LPE, LPE2 N22k
Random Walk Encoding. For A: > O, the k-dimensional random walk structural encoding of vertex iE N1 is defined as the vector
[RW RW
RW
R
(23)
where RW := AD-1 E NNN is the random walk operator. The random walk encodings of all nodes form the random walk encoding RWE E Nxk
Cycle Counts. For each vertex, we count the number of distinct 3- and 4-cycles the vertex participates in. Additionally, we count the total number of 3-, 4-, 5-, and 6-cycles contained in the graph. These counts are computed via closed-form formulas from Vignac et al. (2023). We refer to the published code and Appendix B2 of Vignac al. (2023) for the exact formulas. Graph-level counts are replicated across nodes analogous to the Laplacian cigenvalues and stacked with node-level counts, producing CC Nx5.
E.3 Edge Decoder Architecture
In this subsection, we present details on the edge decoder D., While our approach is principle applicable to discretely labeled edges, concentrate predicting distributions over unlabeled edges here. Fix some timestep 0 <<<<> T. Assume that for this timestep, we are given some node representations (v:)[V) produced by the backbone model. The edge decoder contains K submodules that produce multivariate Bernoulli distributions. Assuming that the node-represnntations produced by the backbone are D-dimensional, let [ense()) (1) RD > 2DD and (ense(2) (2) (3nss(3) R2D + 22D be fully connected layers learned for cach
component Define corresponding MLPs:
ML.P k.o ReLU Dense (2) ReLU Dense (1)
(24)
25

---

Published in Transactions on Machine Learning Research (01/2026)
For each k we process the node representations ea separately and split the resulting vectors into two D- dimensional halves:
(1.
(k) Mi (+)))= = MLPk.o(v))
(o) (k) (g.)))))))))) Densel (8) ((o) Mi
m1(1))
(25)
We define the logit las for the presence of an edge and the logit rk,s for the absence of an edge:
(K]
(()) + xj
(K)
(K) (k) (k) (k)
Di Dj + Vj Dr
(26)
2
Finally, we define the likelihood of the presence of an edge as:
exp(IR,ú,)
Du,o By) = exp(la,s)) exp(Tk.6.))
(27)
While this modeling of the mixture distributions is quite involved, it allows the edge decoder to be easily extended to produce distributions over labeled edges by producing logits for labels of node pairs (instead of producing logits for presence and absence of edges).
Finally, we compute a mixture distribution E A K-1 via Duixx To this end, we learn a node-level MLP:
MLP mix,0 = ReLU Dense (1)
(28)
mix,0
and a graph-level MLP:
MLP mix,9 == Dense mix,9 ReLU o Dense m m
(29)
where Dense (3)
RDD RR We then define:
mix,0
V
D (1:)) softmax MLP(2)
1
MLP
(1) mix.o o
(v:)
(30)
mix,0
M
In the following, we discuss how our approach, and the edge decoder in particular, may be extended to edge-attributed and directed graphs.
Edge Attributes. While we only present experiments on un-attributed graphs, we note that our approach (in particular the edge decoder) is naturally extendable discretely edge-attributed graphs. Assuming that one has S possible edge labels (where one edge label encodes the absence of an edge), one would predict S logits (()) k.i. instead of predicting only two logits lass and Tk,ag- Then, for fixed i, k, the vector
softmax, (122.))
S
8-1
(31)
s=1
would provide a distribution over labels for edge U5}- This distribution would be incorporated into a mixture (over k) of categorical distributions as above. Eqn. (10) would be adjusted to quantify the likelihood of edge labels instead of the likelihood of edge presence/absence.
Directed Graphs. In our experiments, we only consider applications of ANFM to undirected graphs. However, our approach is also naturally extendable directed graphs. Concretely, one would first adjust all GNNs in ANFM to take edge directionality into account. One would additionally modify the product in Equ. 10p to run over the entire adjacency matrix instead of only considering the upper triangle. Le., one would get:
K
(i Pk
Ex if eij
Po F Go) =
II 1.j
(32)
Pk
(i.j)
else
Finally, the edge decoder would be adjustod Equ. (26) drop the symmetrization of 4.s and rk, w.r.t. and (i.c., one no longer enforces the presence of the edge (v,, to have the same probability as the presence of (p),
26

---

Published in Transactions on Machine Learning Research (01/2026)
F Extended Evaluation Results
F.1 Evaluation Methodology for Analyzing Performance Across Multiple Runs
While previous works in graph generation oftentimes present results for only a single training run per dataset, we believe that important to provide some evidence that our proposed method yields stable results across different runs. We provide this evidence by performing three independent training runs with the line Fiedler filtration strategy on the expanded synthetic datasets and reporting median performance in Section 5.2 and the maximum deviation across the three runs in Appendix F.2
Coneretely, we perform three training runs and compute corresponding performance metries 21 S 22 S 23. We report the median as m := and the maximum deviation as d == max([z1 ml, [23 ml).
We settle on this evaluation methodology for the following practical reasons:
Since training is expensive, we can only perform three training runs per dataset. These are too few trials to reliably determine empirical standard deviations.
The median and maximum deviation allow straightforward reasoning about the outcomes of all three runs: m d lower-bounds the performance of the worst run, one run achieved exactly the median performance m, and the best run achieved least the median performance, potentially exceeding it.
F.2
Comprehensive Evaluation Results Expanded Synthetic Datasets
In Table 13
wC present the deviations observed across the three training runs discussed in Sec. 5.2
Addi-
tionally, in Table 14 we present uniqueness and novelty metrics for ANFM and our baselines.
Table 13: Full evaluation results for the Fiedler variant of ANEM trained on expanded synthetic datasets. Showing median across three runs + maximum deviation.
Expaned Planar
Expanded SBM
Expanded Lobster
VUN (t)
79.20
75.98
79.10
Degree (4)
0.0004 5.43 10-3
0.0014 i 0.0082
0.0004 + 0.0013
Clustering (1)
0.0183
0.0014
0.0051 + 0.0009
7.89
10
: 5.32 10-3
Spectral (4)
0.0012
0.0004
0.0011 + 0.0006
0.0016
0.0028
Orbit (4)
0.0002
0.0016
0.0180 1: 0.0171
0.0010 0.0156
Unique (1)
100.00 0.00
100.00 4 0.00
99.80 0.10
Novel (t)
100.00 0.00
100.00 + 0.00
100.00 0.10
F.3
Qualitative Model Samples
In Figure
!
present uncurated samples from the different models described in Sec.
G
Baselines
G.1 GRAN Hyperparameters
For our experiments on the expanded lobster dataset, we use the hyperparameters provided by Liao et al. (2019) for their own (smaller) lobster dataset. For experiments on the expanded planar graph datasel, we utilize the same hyper-parameter setting but reduce the batchsize to 16. For experiments on the SBM datasct, we further reduce the batchsize 8 and use 2 gradient accumulation steps. For the experiments on the protein dataset, we utilize the pretrained model provided at htttp://www... cs. toronto. www.oto..eeurrjill.... edu/-rjliao/ model/ /tra//rannDDaa Beeaa_DDD.ppttt Dth We perform inference with batch size of 20.
27

---

Published in Transactions on Machine Learning Research (01/2026)
(a) Uncurated samples from ANEM model trained on expanded planar graph dataset.
(b) Uncurated samples from ANEM model trained on expanded SBM dataset.
(c) Uncurated samples from ANFM model trained expanded lobster dataset.
(d) Uncurated samples from ANFM model trained on protein dataset.
Figure 4: Uncurated samples from ANFM (line Fiedler variant).
28

---

Published in Transactions on Machine Learning Research (01/2026)
Table 14: Uniqueness and novelty metrics.
Method
Expaned Planar
Expanded SBM
Expanded Lobster
GRAN
100.00
100.00
99.90
DiGress
100.00
100.00
99.22
Unique (1)
ESGG
100.00
100.00
99.61
ANEM (Fdl.)
100.00
100.00
99.80
ANEM (DFS)
100.00
100.00
99.71
GRAN
100.00
100.00
97.56
DiGress
100.00
100.00
96.78
Novel (f)
ESGG
100.00
100.00
98.24
ANEM (Fal.
100.00
100.00
100.00
ANEM (DFS)
100.00
100.00
99.71
G.2 DiGress Hyperparameters
For our experiments on the expanded planar graph and SBM datasets, we use the hyperparameters provided by Vignac et al. (2023) for the corresponding SPECTRE datasets. On the lobster dataset, we use the same hyperparameters as for the expanded SBM dataset (8 layers and batch size 12). On the protein dataset, we use similar hyperparameters as for the expanded SBM dataset but reduce the batch size due GPU memory constraints. We use the same inference approach as Vignac et al. (2023), performing generation with batch size that is twice as large the batch size used for training. In all cases, follow Vignac ct al. 2023) in using 1000 diffusion steps.
G.3 ESGG Hyperparameters
For our experiments the expanded planar graph and SBM datasets, we use the hyperparameters provided by [ergmeister et al. (024)) for the corresponding SPECTRE datasets. For the expanded lobster dataset, we use the byperparameters used by |Bergmeister et al. 2024 for their tree dataset. We use the test batch sizes provided by Bergmeister el al. (0024) in their hyperparameter configurations.
G.4 GRAN Model Selection
we present validation results of the GRAN model trained on the expanded planar graph dataset. We observe no clear development in model performance past 500 steps. We select the checkpoint at 1000 steps.
Expanded Planar. In Table 15
Table 15: Validation results for GRAN model trained on expanded planar graph dataset. Evaluated on 260 model samples.
# Steps
Valid (t)
Node Count (1)
Degree (1)
Clustering (1)
Orbit (J)
Spectral (1)
500
0.00
0.0065
0.0087
0.1749
0.0693
0.0096
1000
0.00
0.0007
0.0070
0.1696
0.1100
0.0086
1500
0.77
0.0100
0.0066
0.1730
0.0743
0.0078
2000
0.00
0.0021
0.0056
0.1658
0.0816
0.0094
2500
0.77
0.0033
0.0064
0.1768
0.1042
0.0087
In Table 16 we present validation results of the GRAN model trained on the expanded SBM dataset. We find that, overall, the checkpoint at 200 steps appears to perform best and select it.
Expanded SBM.
29

---

Published in Transactions on Machine Learning Research (01/2026)
Table 16:
Validation results for GRAN model trained on expanded SBM dataset. Evaluated on 260 model
samples.
# Steps
Valid (1)
Node Count (4)
Degree (V)
Clustering (4)
Orbit (J)
Spectral (1)
100
22.31
1.9992
0.0243
0.0119
0.0400
0.0037
200
24.23
1.9998
0.0194
0.0114
0.0290
0.0026
400
20.38
1.9999
0.0278
0.0130
0.0448
0.0039
600
20.38
1.9999
0.0225
0.0120
0.0318
0.0030
Expanded Lobster. In Table 17 we present validation results of the GRAN model trained on the ex-
panded lobster dataset.
We observe improvement in validity past 2500 steps and select this chockpoint.
Table 17: Validation results for GRAN model trained on expanded lobster graph dataset. Evaluated on 260 model samples.
# Steps
Valid (t)
Node Count (4)
Degree (L)
Clustering (1)
Orbit (U)
Spectral (L)
500
2.34
2.0000
0.0257
0.4753
0.2507
0.0509
1500
38.67
2.0000
0.0092
0.0112
0.1624
0.0329
2500
42.58
2.0000
0.0083
0.0059
0.1749
0.0361
3500
42.97
2.0000
0.0101
0.0049
0.1970
0.0406
G.5
ESGG Model Selection
While ESGG maintains exponential moving averages of model weights during training, we choose to only evaluate non-smoothed model weights (i.e. the EMA weights with decay parameter ? = 1), as validation is compute-intensive.
SBM Dataset. In our experiments, obtain worse performance the expanded SBM dataset than was reported on the smaller SPECTRE SBM dataset in (Bergmeister et al. 2024 In Figure 5 we show the development of validity throughout training, which lasted over 4.5 days on an H100 GPU. Throughout training. we fail to match the validity reported in (Bergmeister et al. 2024 Although the validity estimate is quite noisy, appears to plateau. We select a model checkpoint at 4.8M steps.
Protein Dataset. Model selection on the protein graph dataset challenging, the MMD metrics computed during validation noisy, and generating model samples is time-consuming. We take struc- tured approach and evaluate model checkpoints at 1-4M training steps using the same validation approach as Bergmeisttr et al. (2024). Namely, for each graph in the validation set, we generate corresponding model sample with the same number nodes. We present the resulting MMD metrics Table T8
Based
Table 18:
Validation results of ESGG trained on protein dataset.
Steps
Degree (1)
Clustering (4)
Orbit (L)
Spectral (.)
Wavelet (L)
Ratio (L)
IM
0.0242
0.1074
0.1091
0.0095
0.0267
63.8122
2M
0.0028
0.0254
0.0520
0.0009
0.0023
12.2426
3M
0.0066
0.0632
0.06-10
0.0030
0.0090
23.6206
4M
0.0293
0.1016
0.2474
0.0079
0.0224
84.9982
these results, select the model checkpoint at. 2M steps.
30

---

Published in Transactions on Machine Learning Research (01/2026)
0.20
SBM Validity
0.15
0.10
0.05
0.00
Steps
1c8
Figure 5: SBM validity during training of ESGG on expanded SBM dataset. Validity is computed using 1000 refinement steps in validation but 100 refinement steps during testing to remain consistent with other baselines.
H Additional Ablations
Noise Augmentation. We ablate noise augmentation for the DFS variant of ANFM, supplementing the results previously reported in Table 5 We run 100k training steps of stage I with DFS filtrations the expanded planar graph dataset and compare performance with and without noise augmentation. Consistent with our previous observations, we find in Table 19 that noise augmentation substantially boosts performance.
Performance of DFS variant of AFNM after 100k steps of stage training expanded planar graph dataset with and without noise augmentation.
Table 19:
Stage w/ Noise
Stage w/o Noise
VUN (f)
2.25
0.29
Degree (4)
0.0050
0.0381
Clustering (L)
0.2275
0.3136
Spectral (1)
0.0049
0.0169
Orbit (1)
0.0504
0.1045
We supplement the results on the effectiveness of adversarial finetuning we presented in present ablation results for the DFS variant the expanded planar graph dataset. we compare models after training stage and II on the expanded SBM and lobster Again, we observe that adversarial fine-tuning substantially improves performance in terms of validity and MMD metrics.
GAN Tuning.
Table In Table
20
In Tables 21 and
22
datasets from Sec. 5.2.
Table 20: Performance of DFS variant of AFNM after stage I (200k steps) and stage II on expanded planar graph dataset, For results on Fiedler variant, see Table 5
Stage 11
Stage
VUN (t)
45.61
2.05
Degree (1)
0.0003
0.0057
Clustering (L)
0.0296
0.2297
Spectral (L)
0.0017
0.0058
Orbit (L)
0.0004
0.0318
31

---

Published in Transactions on Machine Learning Research (01/2026)
Table 21: Performance of ANFM models after stage 1 (200k steps) and stage on expanded SBM dataset.
Showing median maximum deviation across three runs for Fiedler variant and single run for DFS variant. All models attain perfect uniqueness and novelty scores.
Fiedler
DFS
Stage TT
Stage
Stage II
Stage
VUN (1)
75.98 3.71
39.65
4.69
78.03
22.85
Degree (4)
0.0014
0.0002
0.0023
0.0063
0.0008
0.0004
Clustering (4)
0.0051
+ 0.0009
0.0082
+ 0.0012
0.0049
0.0117
Spectral (4)
0.0011
0.0032
0.0008
0.0008
0.0020
Orbit (1)
0.0180
+ 0.0171
0.0210
+ 0.0185
0.0049
0.0390
Table 22: Performance of models after stage T (100k steps) and stage IT on expanded lobster dataset. Showing median + maximum deviation across three runs.
Fiedler
DFS
Stage II
Stage I
Stage II
Stage I
VUN (t)
79.10
31.25
87.60
47.46
Degree (4)
0.0004 + 0.0013
0.0004 = 0.0010
x 10-5
0.0209
Clustering (4)
7.89 X 10
0.0136
1.64 X 10
0.0043
Spectral (L)
0.0016 1 0.002s
0.0030 1 o 0012
0.0010
0.0119
Orbit (4)
0.0010
0.0073
0.0007
0.0206
Unique (t)
99.80 + 0.10
99.51 + 0.39
99.71
100.00
Novel (t)
100.00
99.90 99.71
99.90
Filtration Function. In Table 23 we study alternative filtration functions. We compare the line fiedler function to centrality-basod filtration functions. Following Anthonissc (1971 : Brandes (2008), we let (i, J) denote the nunber of shortest paths between two nodes i, E V, and oii e) denote the number of these paths passing through an edge E E. Then, we define the betweenness centrality function as:
oii, oi.j))
fbetweeu (e) Σ ijEV
V.EE.
(33)
Based on this, we define the remoteness centrality as fremote (e) - fbetween (e). We use the same filtration scheduling approach as for the line Fiedler function. We observe that the line fiedler function appears out-perform the two alternatives in setting.
Table 23: Performance after training stage with different filtration functions for 100k steps expanded planar graph dataset. Showing median of three runs for spectral variant and one run each for betweenness and remoteness variants.
VUN (t)
Degree (L)
Clustering (L)
Spectral (4)
Orbit (4)
Line Fiedler
20.21
0.0058
0.1768
0.0048
0.0129
DFS
2.25
0.0050
0.2275
0.0049
0.0504
Beiweenness
0.20
0.0069
0.2724
0.0124
0.0804
Remoteness
3.52
0.0136
0.2720
0.0085
0.0234
32

---

Published in Transactions on Machine Learning Research (01/2026)
0.10
0.10
0.05
0.08
-0.04
0.00
00.6
-0.05
-0100
0.02
-0.12
(a) Line Fiedler
(b) DFS
(c)
Betweenness
(d) Remoteness
Figure 6: Visualization of different filtration functions on planar graph
Scheduling.
We recall that the filtration schedule of the line Fiedler variant depends mononotonically increasing function 7: 1] -> [0, 1]. Here, we study the performance of the three choices for y:
Linear:
7() =
Convex
7(t)
cos
2
(34)
n 2
Concave:
r(t) sin
We present results on the planar graph dataset in Table 24
We find that no single variant performs
Table 24: Performance after training stage I with different filtration schodules for 100k steps expanded planar graph dataset with line Fiedler variant. All models attain perfect uniqueness and novelty scores. Showing median of three runs for linear variant and one run each for convex and concave variants.
VUN (f)
Degree (1)
Clustering (4) Spectral (4)
Orbit (L)
Linear
20.21
0.0058
0.1768
0.0048
0.0129
Convex
5.66
0.0043
0.2239
0.0040
0.0062
Concave
31.05
0.0045
0.1590
0.0059
0.0153
consistently best across all evaluation metrics. However, the concave variant attains the highest validity score.
Node Individualization. In Table 25 we study different node individualization techniques for the line Fiedler variant of ANFM. We refer to the ordering scheme we describe in Appendix E.] as the derived ordering, as it is based on the values of the line Fiedler filtration function. Additionally, we study random orderings and node orderings according to a depth first search (DFS). Moreover, we compare to node individ- ualizations that do not consist of positional embeddings w.r.t. a node orderings but instead i.i.d. gaussian noise that re-applied in each time-step. Finally, we also consider a variant in which no individualization is applied, i.e., the embedding matrix Wnode is fixed to be all-zeros. We find that individualizing nodes with learned embeddings based on some ordering (either random, derived from the line Fiedler filtration function, or a DFS scarch) appears to be beneficial. On the planar graph datasct, there is no clear benefit of the derived ordering over random orderings. However, we observe a clear ad advantage on the SBM dataset, as can seen Table 26
33

---

Published in Transactions on Machine Learning Research (01/2026)
Table 25: Performance after training stage of the line Fiedler variant with different node individualization techniques for 100k steps on expanded planar graph dataset. All models attain perfect uniquencss and novelty scores. Showing median of three runs for derived ordering and one run each for all other variants.
VUN (1)
Degree (4)
Clustering (L)
Spectral (4)
Orbit (4)
Derived Ordering
20.21
0.0058
0.1768
0.0048
0.0129
DF'S Ordering
28.91
0.0055
0.1803
0.0024
0.0053
Random Ordering
18.36
0.0085
0.2332
0.0023
0.0091
Gaussian Noise
12.99
0.0086
0.2356
0.0031
0.0112
Zeros
13.48
0.0057
0.2195
0.0023
0.0091
Table 26: Performance after training stage of the line Fiedler variant with derived and random node ordering after 100k steps expanded SBM datasets. Showing median + maximum deviation across three runs for derived ordering and one for random ordering.
Derived Ordering
Random Ordering
VUN (f)
26.95 è 2.64
2.44
Degree (4)
0.0222
0.0396
Clustering (L)
0.0106 + 0.0012
0.0122
Spectral (4)
0.0061
0.0144
Orbit (4)
0.0548 1 0.0244
0.0596
Unique (1)
1.0000 i 0.0000
0.9951
Novel (t)
1.0000
+ 0.0000
1.0000
Bias and Variance of Estimators
Previous works Martinkus et al. 2022 Vignac al. 2023 Bergmeister al. 2024 evaluate their graph generative models on few as 40 samples. In this section, we investigate how this practice impacts the variance and bias of the estimators used in model evaluation and argue that higher number of test samples should be chosen.
1.1 Variance of Validity Estimation
On synthetic datasets such those introduced in (Martinkus et al. 2022 samples are "valid", i.e., whether they satisfy a property that is fulfilled by (almost) all samples of the true data distribution. By taking the ratio of valid graphs out of n model samples, previous works have estimated the probability of obtaining valid graphs from the generator.
may verify whether model
Definition L.1. Let the random variable G denote a sample from a graph generative model and let valid G + {0, 1} a measurable binary function that determines whether a sample is valid. Then the models true validity ratio is defined as:
Pfyalid(G) 1]
(35)
For i.dd samples Gi,..., On, introduce the following estimator:
valid(G.)
V
(36)
n
Given the simplicity of the validity metric, we can very easily derive the uncertainty of the estimator used for evaluation. We make this concrete in Proposition I.2
Proposition I.2. For generative model with a true validity ratio of p E [0, 1), the validity estimator on n samples is unbiased and has slandard deviation vp(1 p)/ nn.
34

---

Published in Transactions on Machine Learning Research (01/2026)
Proof. Assuming that the random variables Gl...., Gn are ii.d. samples from the generative model, then the random variables valid(G)),.... vald(()).....vll((((.... are i.idd according to Bernoullipp). The validity estimator is given as:
Ei val)d(G,))
(37)
n
By the linearity expectation, we have
E E[valid Σ -==
npp
B[V]
=
(38)
n
p
which shows that the estimator is unbiased. The variance is given by:
Var E== valid((.)]
Ei= Varlvalid(G..)
Var[V]
n2
n2
(39)
p( p)
where we used the independence assumption in the first line. Taking the square root, we obtain the standard deviation from the proposition.
From Proposition L.2 we note that the standard deviation the validity estimate can be as high as 1/(2/n), which is achicved at p 0.5. For = 40, we find that the standard deviation can therefore be as high 7.9 percentage points.
We illustrate the magnitude of this effect a practical example: for DiGress, we obtain validity ratio the SBM dataset of approximately = 56.2% (c.f., Table 2) While this estimated ratio itself is subject to uncertainty, we assume it to be the ground truth for the sake of the following illustration (justified by the large sample size 1024 graphs used to estimate it). In Table 27 we analytically (using Proposition [.2] compute the mean and standard deviation of the validity estimator at different sample sizes. We note that the mean is constant since the estimator is unbiased. However, the standard deviation remains substantial, even at 128 graph samples.
Table 27: Mean validity estimate + standard deviation across evaluations of validity estimator. Computed analytically via Proposition 1.2
The estimated validity is unbiased but has high standard deviation.
# Model Samples
Validity Estimate
56.2 + 8.8
64
56.2 + 6.2
128
56.2 + 4.4
256
36.2
512
56.2 + 2.2
1024
56.2 + 1.6
1.2 Bias and Variance of MMD Estimation
Definition 1.3. Let (X, d) be a metric space and let k : X X + R be a measurable, symmetric kernel which is bounded but not necessarily positive-definite Let X == [x1...., 2,]] be i.id. samples from a Borel distribution Ps on X' and : [y1..... Un] be i.i.d. samples from a distribution Py. Assume X and Y to be independent. Following (Gretton al. 2012), define the squared MMD of Pa and Py
MMD B(k(11, E[k[(1, 12)] 2E[k((11 v1)]
(40)
and note that this is well-defined by our assumptions. Finally, introduce the following estimator for the squared MMD:
M = n2 $11=1
Σ
k(01,
Σ
kly 4z)
2 YUT
ΣΣ> Σ k( vi)
(41)
m²
$1==1
35

---

Published in Transactions on Machine Learning Research (01/2026)
We empirically study bias and variance of the MMD estimates the planar graph dataset. We generate 8192 samples from one of our trained models and repeatedly compute the MMD between the test set and a random subset of those samples. We vary the size of the random subsets and run 64 evaluations for each size, computing the mean and standard deviation the MMD metrics across the 64 evaluations. We report the results in Table 28 We observe that, on average, the MMD is severely over-estimated when using fewer
Table 28: Mean MMD + standard deviation across 64 evaluation runs of a single model. The test set contains 256 planar graphs, while a varying number of model samples is used, as indicated on the left. The MMD and ils variance decrease substantially with larger numbers of model samples.
# Model Samples
Degree (4)
Clustering (4)
Spectral (4)
32
8.59 x 10-1 5.59 x 10
4.21 x 10-2 + 1.44 x 10
4.73 x 10-3 3 + 9.14
64
5.58 x 10
10
2.68 x 10-2 +
10-3
2.59 x 10 + 4.78 10
128
4.40 x 10 = 1.79
2.17 x 10-2 + 4.33
1.61 x 10-3 + 3.16
256
4.39 x 10-1 1
2.02 x 10-2 + 3.89 10-3
1.14 x 10-3 + 1.86 10-4
512
4.32 x 10 8.48
1.81 x 10-2 + 2.58 x 10-3
1.18 x 10-3 + 2.04 1074
1024
4.26 x 10 5..99
1.72 x 10-2 + 1.60 x 10
1.18 x 10 3 + 2.00 10
than 256 model samples. At the same time, the variance between evaluation runs is large when few samples are used, making the results unreliable.
J Adversarial Finetuning Details
We provide pseudocode for the adversarial fine-tuning stage in Algorithm [ We note that we do not make all procedures explicit and that many hyper- paperr-paamterrs must be chosen (including the number of steps and epochs in TRAIN GEENERATORANDVALUUEAA
Generator. The generator operates in inference mode, meaning that all dropout layers are disabled and batch normalization modules utilize the (now frozen) moving averages from training stage 1. Hence, the behavior of the generative model becomes reproducible. It acts as a stochastic policy in a higher-order MDP, where the graphs Go...., GT are the stales. It receives terminal reward for the plausibility of the final sample Gr.
Discriminator. The discriminator is implemented as a GraphiPSS (Rampásek et al. 2022) model which performs binary classification on graph samples Gr, distinguishing real samples from generated samples. It is trained via binary cross-entropy on batches consisting in equal proportions of generated graphs and graphs from the dataset D. For a given graph Gr, the discriminator produces a probability of 'realness' by applying the sigmoid function to its logit. Following SeqGAN YYu et al. 2017), the log-sigmoid of the logit then acts as a terminal reward for the generative model. We emphasize that only the final graph Gr is presented to the discriminator.
Value Model. The value model uses the same backbone architecture as our generative model and regresses scalars from pooled node representations. is trained via least squares regression. The value model used to compute baselined reward-to-go values.
Training Outline. While Algorithm I provides a technical description of the training algorithm, also provide a rougher outline here. At the start of training stage 11, the generator is initialized with the weights Iearned in training stage I, while the discriminator and value model are initialized randomly. Before entering the main training loop, we pre-train the discriminator and value model to match the generator. Namely, we first pre-train the discriminator to classify graphs as either "real" or 'generated'. The log- lig-likel of "realness" acts as a terminal reward of the generative model. The discriminator is then pre-trained to regress the reward-to-go. After pre-training is finished, we proceed to the training loop, which consists of alternating training of (i) the generator and value model and (ii) the discriminator. As described above, the generator
36

---

Published in Transactions on Machine Learning Research (01/2026)
is trained via PPO to maximize the terminal reward provided by the discriminator. The value model is used to baseline the reward and is continuously trained to regress the reward-to-go. The discriminator, the other hand, contimues to be trained on generated and real graph samples via binary cross-entropy.
Algorithm Adversarial Finetuning
procedure TRA.NGEEEEEATOAAAAWWWAAAAAAODDOD de, vo) for i 1..., Nateps do
S []
List of sampled filtrations Terminal rewards
<- 0 E RaNapleee
for j = 1...,
L.....,.amiiil Nsamples do
G6 G t SAMPLEFIITRATIION()))
S. append ((b6...... ....,.. .f)
rj ld
Tj 4 max Rlower)
Reward clamping
end for r + WHITEN(F)
Whiten rewards using EMA of mean and std
9í.t 0 vj 1....... Nemples b4 = 0...., .....,T
> Rewards-to-ge to-go
for j = 1 ..., Naumpes do do
for O.....
95.t + r3 ui (G) G(1))
Compute baselined RTG
end for end for
TRAAIVALLUEMODRR
r)
for k 1........... Nepoch do (2)
j.t +- log G
Vj =
N samples 41 1,...,? T
1-11
U5 < exp(sg (1
(k)
Hj,t
c(1) +- - U3et --
Vj,t
1 +- clamp(uz,, 1 6, 1 + t) -j
4j.4
L - Σ ji max( j,t: 1 c!2)
+ 0 VVL
Backpropagate and update paramoters
end for end for end procedure
procedure GANTUNING(po, D)
> Takes generator from training stage I and graph dataset
dp + new GNN
> Initialize discriminator
TRAINDISCHUMINNOOR(((.. dp D)
> Pre-train discriminator
0g f- new mixer model
S < GEXERAAEEFI.TRAIIOONSSS
+ GRADESAMPLESS(,,d. dpp)
Pre-train value model
while not. converged do
TRAINGENERATORAAW VALUEMODEL(ps. vo) TRAINDSCHMINATORRRHH, de, D)
end while end procedure
37

---

Published in Transactions on Machine Learning Research (01/2026)
K Training Costs
In Table 29
we compare the computational costs of training the presented ANFM models (line Fiedler variant) to the costs of training the presented DiGress models. We note that the preparation of filtrations for the first training stage is CPU-bound and highly parallelizable. In comparison to the cost. of training, it is negligible.
Table 29: Training costs of ANFM and DiGress across datasels and training stages.
ANFM
DiGress
Dataset
Stage
Stage
Total H100 Hours
Total H100 Hours
Expanded Planar
2 H100s x 20h
1 H100 x 20h
60h
95h
Expanded SBM 2 H100s x 20h
1 H100 x 81h
121h
90h
Expanded Lobster H100s x 12h 1 H100 x 58h
82h
48h
We find that training of DiGress often cheaper than training of ANFM. Hence, ANFM trades efficiency during inference for increased computational costs during training.
L MMD vs Filtration Granularity
In this section, we supplement the results from Figure 2 illustrating how the MMD metrics evolve as the number of generation steps is varied ANFM and DiGress. Figure 7 shows that, in terms of MMD, ANFM generates higher-quality graphs than DiGress at the considered number of generation steps. This is consistent with findings from Figure] 2 We recall that the default DiGress variant uses 1000 generation steps.
Clustering MMD2
0.3
ANFM
Degree MMD
0.003
ANPM
DiGress
DeGress
0.002
0.1
0.001
0.000
40
50
20
4.
60
# Generation Steps
#
Generation Steps
(a) Clustering MMD
(b) Degree MMD
Orbit Orbit MMDs
0.15
DiCressx
ANFM
Spectral MMD2
0.015
ANFM
DiCrese
0.10
0.010
0.005
0.00
0.000
30
20
40
# Generation Steps
#
Generation Steps
(c) Orbit MMD
(d) Spectral MMD
Figure 7: Performance of ANEM and DiGress in terms of MMD on the expanded planar dataset as the
number of generation steps varies. The original (default) DiGress variant uses 1000 generation steps.
M Detailed Definition of the Line Fiedler Filtration Function
In this section, we provide more thorough definition the line Fiedler filtration function we have introduced in Sec. 4.1 Let. G (V, F) be undirected connected graph the nodes V with edges E c V V. We
38

---

Published in Transactions on Machine Learning Research (01/2026)
define its line graph as L(G) (E, E') where E' denotes the pairs of edges that share vertex in G:
E' = {(c,e') e, E, lene']=1]
42)
It is easy to verify that L(G) is connected. Let A I ExE be its adjacency matrix and define the associated symmetrically normalized Laplacian matrix as:
L=
(43)
where D ExE is the diagonal matrix with Di,i Di:=EjeR Arj- We may now find the eigenvectors associated to the second smallest cigenvalue. These are the Fiedler vectors L(G). One such vector v R with unit length provides the line Fiedler filtration function. We note that, similar to the DFS filtration function, the line Fiedler filtration function is not unique for given graph. Indeed, the Fiedler vector of the line graph is at most unique up sign.
39


Reviews:
[{"review_id": "imvYIEQfIB", "reviewer": "Reviewer_tqkU", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "Summary:\nThe paper presents Autoregressive Noisy Filtration Modeling (ANFM), an edge autoregressive framework for graph generation. During training, a filter function determines the order in which edges are gradually masked, working as a schedule. The generative model leverages a GNN that processes intermediate graph structures, and a transformer decoder to handle the temporal axis. Sampling is performed via mixtures of multivariate Bernoulli distributions. The model is shown to perform comparably to the state of the art while significantly reducing generation time.\n\nStrengths:\n1. The paper is generally well written, without typos (as far as I noticed), and easy to follow.\n2. The idea of using filtration to model the graph edge \"editing\" is interesting. The introduction of additional techniques, namely the use of noise and adversarial finetuning to counter exposure bias, is well motivated.\n3. The model is evaluated on many datasets from the graph generation literature, and I appreciated the introduction of at least one dataset with labels.\n\nWeaknesses:\n1. Some parts are missing motivation/explanation. See questions for details.\n2. The choice of the median to report results (across 3 runs) instead of the mean is a strange and not well-motivated choice. It could be in good faith, but using the median could allow for reporting higher results when only 2 of the runs are good, while 1 is bad. Additionally, I did not understand whether the maximum deviance is with respect to the mean or the median.\n3. Smaller issue: the code is missing. If possible and available, I would recommend sharing the code through anonymized github, or other means.\n\nQuestions regarding Weakness 1:\n1. What is the motivation behind the Line Fiedler Filtrations, apart from allowing non-induced subgraphs? Can you provide a more thorough explanation and motivation of the method, and, if possible, your opinion on different results with respect to Depth First Search?\n2. What is the KL Div in Table 4, and why is it the higher the better? Same for FCD.\n3. Why did you use the mixture of multivariate Bernoulli distributions instead of a single categorical/bernoulli, as is done in, e.g., DiGress?\n\nGeneral questions:\n4. Why was the median used instead of the mean?\n5. I'm interested in your opinion on the results of Transformer vs. First-Order, where the fully autoregressive variant performed better. Shouldn't all the information already be stored in \\tilde{G}_t? Does it have to do with the filtration strategy?\n6. Is the GNN (implemented as a Graph Transformer) propagating information in a fully connected fashion, or only through connected nodes? In the former case, is it still true that ANFM can generate sequences of induced subgraphs? (because nodes already existing can influence the generative process)\n7. Does the use of GAN finetuning on the last step influence all the features extracted throughout the generative sequence (by backprop through the transformer)?", "claims_and_evidence_yn": "No", "claims_explanation": "I did not find an explanation for the use of median instead of the mean (on 3 runs). Although in good faith, the use of median could hide a potentially bad run out of the 3. See Questions for more details. I will be happy to change my mind if an explanation on the use of median, or a switch to the mean (or alternatives) is done.", "audience_yn": "Yes", "audience_explanation": "The topic of graph generation, especially with the aim of high throughput, is very important.", "requested_changes": "Critical changes:\n1. Including a motivation for the use of median, or a switch to the mean\n2. Inclusion of the topics touched on in Q1-4\n\nMinor changes:\n1. Inclusion of the topics touched on in Q5-7\n2. Inclusion of the code", "broader_impact_concerns": "There are no concerns or ethical implications of the work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "ZfwWFT9Ocr", "reviewer": "Reviewer_Z8wQ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "**Summary**  \n\nThis paper introduces Autoregressive Noisly Filtration Modeling (ANFM), a new method for fast graph generation. Compared to recent diffusion-based graph generators its inference time is significantly shorter, while the graph quality remains comparable. Conceptually, there are three advances: (1) Using general graph filtrations for the autoregressive target sequence instead of relying on node order, (2) noise augmentations during a first teacher-forcing training stage that allow deletions, (3) a discriminator-based free-running second training stage. The latter two aim to mitigate exposure bias of the model during inference. The paper contains extensive experiments and ablations.\n\n**Strengths**  \nS1: The speed improvement relative to diffusion methods while maintaining decent quality is impressive.  \nS2: The paper is generally well-written and easy to follow.  \nS3: Apart from the main model, it is nice that the authors connect filtration-based sequences to classical node order-based sequences and that they comment on the variability of a classical evaluation method due to too few generated samples.  \nS4: The paper contains several ablations, extensive experiments, clear algorithm descriptions, and a list of used hyperparameters. This helps to judge the importance of individual method components and eases reproducibility.\n\n\n**Weaknesses**  \n*Major*  \nW1: Hyperparameter tweaking per dataset. My main concern with the paper is that several hyperparameters were tweaked for each dataset (Tables 10-12). Were hyperparameters similarly tweaked for competing methods? If not, this raises concerns about the fairness of the comparison.  \n\nW2: No clear performance gain from the general graph filtrations by Fiedler vector compared to DFS node-order. While I appreciate the graph-filtration formalism and the explanation that it is a strict generalization of node order-based approaches like DFS, it seems that empirical performance is not clearly better for the line Fiedler vector version. In several cases the DFS version is even better. I think a more detailed discussion and recommendation should be included and the emphasis on graph-filtrations in the abstract, method name, and main contributions should perhaps be reduced. \n\nW3: No code is provided.\n\n*Minor*  \nW4: Some overselling of results, see W2 and below.\n\nW5: No ablation of MLP Mixer architecture. While the ablations are in general fairly extensive, it would be interesting to see how much performance is due to the choice of the model architecture as opposed to the training process and the filtrations. I.e. keep the two stage-training mode but use a different autoregressive model, e.g., an LSTM.\n\nW6 LSTM performs very strongly in Table 4, but this is not discussed at all.\n\nW7 Uncertainties are only sometimes reported. At least for the very small datasets, it should be fast enough to rerun the methods for several random seeds and report performance variability.\n\n**Questions**  \nQ1: How does the Fiedler vector of the line graph relate to the Fiedler vector $v$ of the orignal graph and the corresponding filtration by $f(u,v) = max(v_i, v_j)$?  \nQ2: How exactly are the node-features $v_i^{(t)}$ computed?  \nQ3: From the complexity analysis it seems like the node-features $v_i^{(t)}$ contain eigenvectors, which makes the complexity of each each step's cubic in the number of nodes. Would it be possible to reuse the previous step's output features $u_i^{(t-1)}$ as $v_i^{(t)}$ instead?\n\nQ4: What is the unit of the reported inference times?\n\nQ5: Why is  ESGG* sometimes slower than DiGress in Table 2, even though it is optimized for inference speed? \n\nQ6: What are the metrics KL-Div and FCD in Table 4?\n\nQ7: The authors write that they removed the exponential moving average from ESGG and found training to be unstable (Appendix G5). Could the missing EMA not be a direct cause for the instability? Also, I do not get why the EMA slows down validation. Only one additional set of weights needs to be stored, right?\n\nQ8: It is a bit unclear how the proposed noise-augmentation of filtrations differs from teacher-forcing with data augmentations. Is the difference simply that a fixed number of augmented sequences are precomputed instead of augmenting on the fly?\n\n\n**Misc**  \nTypo \"N\"-->\"T\" in proof of Prop B1.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The central claim of fast, decent quality graph generation is well-supported (assuming hyperparameters were not tweaked more for ANFM than for other methods). Smaller claims like the importance of using graph filtrations \n\n> Our approach is fundamentally based on the concept of graph filtration.\n\nare less well supported (see W2).\n\nMoreover, I would recommend a more nuanced discussion of the empirical results. For instance, the authors write \n\n>They [our methods] perform slightly worse than DiGress (Vignac et al., 2023) and ESGG (Bergmeister et al., 2024). While the line Fiedler variant outperforms the DFS variant on the planar graph dataset, the DFS variant performs substantially better on the SBM dataset.\n\nBut the VUN score of ANFM is much, not slightly, worse than that of ESGG on the planar dataset in Table 1. Similarly the line Fiedler variant is worse in all MMD metrics on the planar graph dataset, but much better in VUN. So it neither out- nor underperforms compared to the DFS variant.", "audience_yn": "Yes", "audience_explanation": "A fast inference speed is important for using graph generation in practice at scale. The proposed method achieves a significant speed-up while only compromising quality somewhat.", "requested_changes": "In addition to the weaknesses above:\n\nC1: Include some illustration of the Fiedler vector filtration in the main paper (like Fig 6 a, b)\n\nC2: Please indicate best (/ second best) performing methods in bold (/ italics) in Tables 1-4 etc like it is done in Tables 20-26. \n\nC3: Please mention the default number of diffusion steps of DiGress in the caption of Fig 2 or extend the x-axis (logarithmically) to this default number.\n\nC4: Given the linear complexity of ESGG vs the cubic complexity of ANFM, it would be helpful to get a feeling for the size of graphs at which ESGG really becomes much faster. E.g. one could take an ESGG and an ANFM model trained on the small graphs from the paper and then ask these models to generate progressively larger graphs tracking the inference time.\n\nC5: I appreciate the discussion on evaluation variability in I.1. It would become even stronger if the authors included a table similar to Table 27, but directly for the validity estimates, showing that the std goes down with the number of model samples (but I expect the mean not decrease consistently as for MMD in Table 27, since even for a small number of samples the estimator is unbiased).", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "0pI4HaOGBh", "reviewer": "Reviewer_3vAw", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "### Sumary\nThis work introduces the Autoregressive Noisy Filtration Model (ANFM), an autoregressive framework for graph generation.\n\nThe core innovation is its use of graph filtrations, a concept from topological data analysis, to transform a target graph into a concise sequence of increasingly complex subgraphs. The procedure generates a short sequence of increasingly dense and detailed intermediate graphs, which interpolate the target graph and the fully disconnected graph. The authors compellingly argue that this filtration-based approach generalizes prior autoregressive methods by naturally enabling the construction of non-induced subgraphs.\n\nThe proposed ANFM is based on a two-stage training procedure designed to address challenges in generative modeling:\n\n- Stage I employs noise augmentation, which allows for both the addition and deletion of nodes and edges. This creates non-monotonic graph sequences.\n- Stage II further refines the model using a reinforcement learning (RL) based fine-tuning approach to improve sample quality.\n\nPresented results suggest that ANFM achieves a favorable trade-off between sample quality and inference speed, as ANFM can match the performance of state-of-the-art graph diffusion models while offering (in practice) faster generation times.\n\nThe **main strengths of the work** consist of:\n\n- The idea of employing graph filtrations for autoregressive generation. The theoretical insight that this framework generalizes prior methods to allow for non-induced subgraphs is a contribution.\n\n- The authors identify exposure bias as a primary hurdle for autoregressive graph generation models and propose a noise augmentation framework in Stage I and an adversarial RL fine-tuning approach in Stage II as solutions to mitigate this issue.\n    - The ablation study presented in Section 5.4 provides empirical evidence for the importance of both components.\n    - This validates the effectiveness of their proposed techniques.\n\nDespite these strengths, there are **a few weaknesses** to be clarified or strengthened:\n\n- My main concern is a potential disconnect between the proposed novelty (filtration) and the demonstrated sources of performance.\n    - While filtration is an elegant framing, the empirical results, particularly the ablation studies, suggest that the noise-augmentation and RL fine-tuning components are the primary drivers of the model's success. It remains unclear how much of the performance gain is directly attributable to the filtration-based sequence generation itself.\n\n- The analysis of computational complexity feels incomplete. The paper focuses on asymptotic inference complexity, arguing that a small number of steps (T) makes the method efficient.\n    - However, the training cost, which may be substantial ---due to filtration sequence creation, the main training loop, and the subsequent RL fine-tuning--- is not discussed.\n    - A more holistic view of the computational trade-offs seems warranted.", "claims_and_evidence_yn": "No", "claims_explanation": "See the weakness described above, mainly pertaining to disentangling the sources of performance (i.e, how much of the performance gain is directly attributable to the filtration-based sequence generation itself) and a more detailed analysis of the computational trade-offs between training and inference.", "audience_yn": "Yes", "audience_explanation": "This work presents both a practical solution to the problem of graph generation and a new theoretical framework based on filtration.\n\nWhat makes the work interesting is the core generative mechanism: a novel framework based on graph filtrations, which the authors show is a formal generalization of prior autoregressive techniques.\n\nThe authors effectively tackle the challenge of exposure bias in autoregressive models via a two-stage method of noise augmentation and RL fine-tuning, backed by ablation studies.", "requested_changes": "1. The most critical point is to better isolate and articulate the precise contribution of the filtration framework to the final performance. Currently, its benefits seem overshadowed by the noise augmentation and RL components. Could the authors elaborate on this interplay?\n    - A compelling way to disentangle these effects would be to conduct an experiment comparing ANFM to a variant that uses a more traditional autoregressive scheme (e.g., node-by-node addition) but still incorporates the same noise-augmentation and RL fine-tuning stages.\n\n2. The discussion on computational cost should be expanded to provide a complete picture.\n    1. Please report on the training costs. This should include a discussion and empirical reporting of the time required for creating graph filtration sequences, the main Stage I training, and the Stage II RL fine-tuning.\n    2. Regarding inference, can you provide empirical data on how execution time scales with T, rather than just the asymptotic analysis? \n        - In the Filtration Granularity analysis (Figure 2), why is T limited to 45?\n        - A thorough analysis (with comparison to diffusion-based baselines) showing the trade-off between sample quality (all metrics) and inference time as T increases would be very valuable.\n    3. The reporting of \"time needed to generate 1024 graphs... normalized to a per-graph cost\" is sensitive to implementation details. Please provide more context or justification for why this is a robust measure.\n\n3. To strengthen the submission, please discuss the following:\n    1. The authors identify SID (Boget, 2025) as a highly relevant discrete diffusion model, but it is not included as a baseline. Please clarify the reason for its omission. Comparing against this work would further situate ANFM in the current state-of-the-art landscape.\n    2. Expand on the importance of the filtration design choices and hyperparameters. For instance:\n        - A discussion on the choice of a fixed T for all graphs in a dataset would be beneficial. Have the authors considered whether an adaptive T (e.g., dependent on graph size or complexity) could be advantageous?\n        - The appendix contains a valuable investigation of different filtration strategies. A summary of the key takeaways ---highlighting the benefits and drawbacks of each strategy--- in the main paper would be an excellent addition for the reader.\n\n4. Minor Suggestions for Presentation and Clarity:\n    1. Given its centrality to the paper, consider adding a slightly more detailed background explanation of graph filtrations in the main text, to improve accessibility for a broader audience.\n    2. Please provide explicit inline definitions for key terms when they are first introduced (e.g., \"induced subgraphs,\" \"monotonic graph sequences\").\n    3. On all result tables, please use bolding to highlight the best-performing method for each metric, and perhaps underlining for the best in each model class (e.g., best autoregressive, best diffusion). This would greatly aid in the rapid interpretation of results.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)