Towards Fast Graph Generation via Autoregressive Filtration Modeling

Thank you for your time and effort in providing such constructive feedback. We greatly appreciate your insights and have addressed the points you raised below.

Weaknesses

The authors made the assumption that only connected graphs are presented in the model during training

This assumption was made to ensure that the line graph of $G_T$ is connnected. Then, eigenvectors corresponding to the second smallest eigenvalue (i.e. line Fiedler vectors) will paint the edges of $G_T$ in a continuous gradient. If $G_T$ is disconnected, these eigenvectors may paint edges of only a single component in a continous gradient while edges of other components are assigned the constant value 0. Thus, without modification of the filtration function, AFM would have to generate whole connected components in a single generation step.

To rectify this and extend AFM to disconnected graphs, one has to adjust the line Fiedler filtration function. One simple approach would be defining the line Fiedler function separately per connected component.

Hence, the reason for this assumption was technical and modifications of the filtration function should allow applications on disconnected graphs.

The baselines that the authors compared with in Section 4.2 (expanded synthetic datasets) and Section 4.3 (real-world datasets) are too few.

We have added two baselines from the literature to Section 4.1. Unfortunately, due to limited computational resources and the strict timeline, we do not expect that we will be able to run additional baselines on our own datasets. However, we believe that our current evaluations already adequately demonstrate the quality and efficiency of our proposed model: AFM outperforms state-of-the-art autoregressive models, achieving generation quality comparable to that of diffusion baselines while being substantially faster during inference.

Questions

Is there any good theoretical or at least intuitive explanation as to why [the Fiedler vector of the line graph] might perform well?

Ultimately, the line Fiedler filtration function is a heuristic choice and we don't have a rigorous explanation as to why it works well. Intuitively, the line Fiedler function paints edges of a graph in a "continuous gradient", assigning similar values to neighboring edges. We hypothesize that this may simplify the task of learning to reverse the filtration, as edges are mostly added in locally confined regions that neighbor the edges that were added in the previous steps.

To guide your intuition, the illustration of the behavior of the line Fiedler filtration in the appendix may be helpful (Figure 5 titled "Visualization of different filtration functions on a planar graph").

How does the runtime of the AFM method change as the graph size N increases?

As noted in the common response, we have added a theoretical runtime analysis to the main text and an investigation of a first-order autoregressive variant to the appendix.

Questions

How could AFM be extended to handle node or edge attributes?

See the discussion above.

How to extend AFM to work on directed graphs?

While we do not present experiments on directed graph datasets, our presented method should naturally extend to directed graphs. We have updated the appendix ("A.7 Edge Decoder Architecture") to elaborate on this.

Can we solve the problem of high computational complexity of previous autoregressive and diffusion models with distributed computing resources?

Denoising diffusion models like DiGress are inherently sequential with a large number of denoising iterations, making parallelization challenging. Distributed computing resources can be used for data parallelism (e.g. generating large numbers of graphs). While this will surely increase throughput, it will naturally lead to proportionally large increases in computational costs. In our opinion, the need for efficient graph generative models remains.

Please justify why diversity and structural consistency are important for filtration function?

• Filtration functions that do not assign distinct values to different edges (i.e. are not diverse) may lead to graph filtrations in which large numbers of edges are added in a single step, regardless of the choice of $T$. Hence, one cannot steer the granularity of the filtration via the number of steps $T$.
• By "structural consistency", we refer to the notion that the ordering of edges imposed by the filtration function should carry some information on their relations to each other / their position in the graph. The line Fiedler function, for instance, tends to assign similar values to edges that are close to each other. We hypothesize that this simplifies the task of reversing the filtration.

What is in line 200?

In this line, we introduce alternative filtration functions based on the concept of betweenness. We provide a rigorous definition in the appendix (see "A.16 Additional Ablations"). We have added a reference to this appendix to improve clarity.

What does 'appropriate edges' in line 292 refer to?

By "appropriate edges", we refer to edges that are erroneously added in intermediate graphs $G_t$ with $t < T$. For instance, when generating trees, these could be edges that are part of a cycle. When generating planar graphs, these could be edges that are part of a $K_5$ or $K_{3, 3}$ sub-division. In order to obtain a valid graph sample $G_T$ (i.e., one that is cycle-free or planar), some of these edges must be deleted in subsequent steps.

Thank you for your time and effort in providing such constructive feedback. We greatly appreciate your insights and have addressed the points you raised below.

Weaknesses

The multi-step approach (including filtration, autoregressive modeling, noise augmentation, and adversarial fine-tuning) may be challenging to implement and tune, particularly for practitioners.

We agree that our method is technically complex. To facilitate adoption and ease of use, we provide additional practical advice on tuning hyper-parameters in the appendix of our revised paper (please see "A.5 Practical Advice on Hyperparameter Choice"). Additionally, we will publish our source code upon acceptance of the paper.

The focus on non-attributed graphs limits the model’s applicability to scenarios involving node or edge labels, a common requirement in many practical applications.

We acknowledge the concern that our current design does not explicitly support graphs with node and edge attributes. However, we want to emphasize that our primary focus is on developing efficient AR model for unattributed graphs and we present the first AR model that matches the performance of diffusion-based models while maintaining its speed advantage. Furthermore, un-attributed graph topologies are often of significant interest in various applications, such as protein structure modeling and design, where contact maps represent the spatial proximity between amino acids [1, 2].

As discussed in our conclusion and appendix, our method is naturally extendable to edge-labeled graphs. Regarding the modeling of node attributes, we propose two prospective approaches:

• Post-hoc node labeling: After generating the graph topology, node labels can be assigned based on the structural context, as suggested by Bergmeister et al. (2024). For example, in molecular graphs, valency constraints and local connectivity patterns may provide strong cues for determining atom types. Such an approach was used in [3].
• Extension of the Filtration Process: We can extend the filtration process to include node labels by representing them as labeled self-loops and incorporating them into the edge filtration. This approach allows the model to learn node attributes alongside the graph topology within the same generative framework.

We believe that integrating node and edge labels is a promising direction for future work, which can further enhance the applicability of our approach to a broader range of graph generation tasks.

The paper can be better motivated by stating why there is a need for graph generation algorithms especially for high-throughput applications

We have updated the introduction to highlight this point. Previous works have demonstrated that the spaces of drug-like molecules and protein conformations are practically infinte. Hence, high-throughput generation is emerging as a promising alternative to screening of pre-defined graph libraries.

The experimental results, among all, do not stand out the superiority of the proposed method against baselines.

We have demonstrated that our method achieves generation quality that is comparable to the quality achieved by state-of-the-art diffusion models while being two orders of magnitude faster. We do not aim to out-perform existing diffusion baselines in terms of quality, but aim to substantially improve efficiency without compromising on quality. To the best of our knowledge, our method is the first autoregressive graph generative model that can compete with diffusion models on the benchmarks we presented.

References

[1] Zeming Lin et al., Evolutionary-scale prediction of atomic-level protein structure with a language model. Science379, 1123-1130(2023). DOI:10.1126/science.ade2574

[2] Chen, Y., Xu, Y., Liu, D. et al. An end-to-end framework for the prediction of protein structure and fitness from single sequence. Nat Commun 15, 7400 (2024). https://doi.org/10.1038/s41467-024-51776-x

[3] Li, Yibo, 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, no. 1 (2020): 77–91. https://doi.org/10.1021/acs.jcim.9b00727.

Thank you for your time and effort in providing such constructive feedback. We greatly appreciate your insights and have addressed the points you raised below.

W1: The motivation is inconsistent with the proposed method. Section 3.1 states that a filtration has G_t ⊇ G_{t-1}. However, the proposed method in Section 3.2 both add and delete edges

While we do use noise-augmented filtrations in practice, they are still largely guided by the original monotonic filtration sequence. Indeed, for a given graph $G_t$ in the (monotonic) filtration sequence, we randomly perturb the presence of edges for at most 25% of all node pairs (in particular, we delete on average at most 25% of edges in $G_t$). The frequency of perturbations is governed by the noise schedule $\lambda(t)$, which is annealed from 25% at $t=1$ to 5% at $t=T - 1$.

We are happy to adjust nomenclature or phrasing if you have suggestions to improve clarity.

W1: It is more like a diffusion model except that they replace $p(G_t|G_{t-1})$ with $p(G_t|G_{t-1},...,G_0)$. The objective function looks the same as that of DiGress.

We agree that our method resembles diffusion in some aspects: Namely, we also aim to train a model to reverse a corruption process. However, our approach does not fit the formalism of denoising diffusion:

• In general, we do not restrict oursevels to a first-order autoregressive structure
• The corruption process (i.e. the noisy filtration) is in general not Markov
• Our training objective differs from the loss of DiGress.

We have added a discussion of this point to the extended related work section in the appendix.

Our loss resembles the DiGress loss in that we consider a cross-entropy. However, we note that DiGress uses a simplified diffusion loss under an "$x_0$-parametrization" (see here). Given a sequence of increasingly corrupted graphs $G_T, \dots, G_0$, their loss at timestep $t$ would be $-\log p_\theta(G_T | G_t)$ while our loss would be $-\log p_\theta(G_{t+1} | G_t, ..., G_0)$. I.e., we form a cross-entropy against $G_{t+1}$ while DiGress forms a cross-entropy against the "clean graph" $G_T$ (note that literature on diffusion models uses a reverse indexing for the sequence of graphs $G_t$).

While our loss bears more similarity to the VLB of DiGress (as opposed to the simplified diffusion loss), we maintain that our method does not fit into the formalism of denoising diffusion, as explained above.

W2: It seems that the speedup comes mainly from the small number of steps (i.e., T) of the proposed method AFM. [...] To provide a more meaningful comparison, the authors can plot a VUN-vs-time curve for each method (by varying T)

We agree that the small number of steps is the main contributor to the speedup compared to other methods. Following your suggestion, we have added this experiment to the main paper (see Figure 2). We vary $T$ both in AFM and DiGress and study the effect on quality and speed. We refer to the section "Effect of filtration granularity $T$" of the general response for a discussion of our findings.

W3: The time complexity of autoregressive generation is O(T^2). Thus, it might be inefficient if we seek to increase the generation quality by increasing T.

Please refer to the "Complexity Analysis" section in our general response.

W4: The ablation studies are a bit insufficient. The authors did not report the performence of using only stage II

Thank you for this interesting suggestion. We have added an ablation using stage II on a premature checkpoint of stage I ("A.16 Additional Ablations"). Convergence in stage I is necessary to obtain satisfactory performance in stage II.

W5: As the proposed adversarial finetuning (AF) is orthogonal to the generative model, comparing the proposed method with AF and baseline methods without AF is not an apple-to-apple comparison.

This is a fair point, as AF could also be applied to our autoregressive baseline (GRAN). However, we make the following two observations:

• In all of our experiments, AFM is faster during inference than GRAN. In particular on larger protein graphs, AFM is ten times faster. This is not affected by adversarial finetuning.
• As we demonstrate in the ablation experiment for your previous point (W4), adequate performance after the first training stage is a prerequisite for good performance after adversarial finetuning. After training stage I, we already observe that AFM outperforms GRAN substantially in terms of quality (VUN) on the expanded planar graph dataset (c.f. Table 4, "Stage I w/ Noise"). The same holds true for the expanded SBM dataset (c.f. Table 15, "A.16 Additional Ablations"). AFM without adversarial finetuning performs slightly worse than GRAN on the expanded lobster dataset (c.f. Table 16).

With this being said, we agree that studying the effect of AF on other autoregressive approaches would be interesting.

Thank you for your thorough response. Below are my further comments about your answers.

While we do use noise-augmented filtrations in practice, they are still largely guided by the original monotonic filtration sequence. Indeed, for a given graph $G_t$ in the (monotonic) filtration sequence, we randomly perturb the presence of edges for at most 25% of all node pairs (in particular, we delete on average at most 25% of edges in $G_t$). The frequency of perturbations is governed by the noise schedule $\lambda(t)$, which is annealed from 25% at $t=1$ to 5% at $t=T - 1$.

Thanks for your elaboration. However, I do not fully agree with this. What you call "noise-augmented filtrations" look more like a diffusion model to me. Diffusion models also have a noise schedule, and the generation process is also governed by the denoising process. The main difference seems to be the loss function. This weakens the motivation of using a filtration instead of a diffusion process.

We form a cross-entropy against $G_{t+1}$ while DiGress forms a cross-entropy against the "clean graph" $G_T$.

Thanks for your clarification. I agree that they do have some differences, but they are still more like variants than essential differences to me because theoretically speaking, they are just different upper bounds on $E[-\log p_\theta(G_T)]$. Why does your loss function perform better than DiGress' loss function? Also, I wonder what the performance will be like (i) when you train DiGress using your loss function and (ii) when you train AFM using DiGress' loss function.

We agree that the small number of steps is the main contributor to the speedup compared to other methods. Following your suggestion, we have added this experiment to the main paper (see Figure 2). We vary $T$ both in AFM and DiGress and study the effect on quality and speed. We refer to the section "Effect of filtration granularity $T$" of the general response for a discussion of our findings.

Thanks for the additional experiments. This clearly shows that AFM achieves a better tradeoff than DiGress. However, this comparison considered only discrete-time models but did not consider continuous-time models such as [1,2]. Continuous-time models can achieve a natural tradeoff between generation quality and generation steps by adjusting the discretization points. For example, Table 9 in [1] shows that their continuous-time model still achieves good performance even when using only 5 steps. How does AFM compare with these continuous-time models in terms of the tradeoff?

• [1] Xu et al. Discrete-state continuous-time diffusion for graph generation. arXiv:2405.11416. NeurIPS, 2024.
• [2] Siraudin et al. Cometh: A continuous-time discrete-state graph diffusion model. arXiv:2406.06449.

This is a fair point, as AF could also be applied to our autoregressive baseline (GRAN)...

Thanks for your clarification. As adversarial finetuning seems to offer a significant improvement as a standalone module, my point is that the adversarial finetuning might contribute more than the proposed filtration framework. If so, this would substantially weaken the motivation of this paper. Thus, to rule out this possibility, a better ablation study is to apply adversarial finetuning to stronger baselines like DiGress.

Thanks.

Questions

The proposed method learns the joint likelihood of the sequence. However, graph generative models aim to learn $p_\theta(G_T)$. The paper should clarify the relationship between these two

We have addressed this concern in the appendix of the revised paper for training stage I (see "A.4 A Bound on Model Evidence"). We show that the autoregressive loss in stage I serves as an evidence lower bound for the marginal $p_\theta(G_T)$. For training stage II, we note that we no longer consider the joint likelihood of the sequence but only present the final samples $G_T$ to the discriminator. It is known that the resulting training criterion is the Jensen-Shannon divergence between $p_\theta(G_T)$ and the data distribution (see, e.g., this paper).

What are the training complexity and sampling complexity of the proposed model?

Please refere to the "Complexity Analysis" section in our general response regarding the sampling complexity.

Regarding training complexity: In AFM, a forward and backward pass on a single graph sample is $\mathcal{O}(T^2N + TN^3)$ in stage II and $\mathcal{O}(T^2N +TN^2)$ in stage I, assuming that Laplacian positional encodings are pre-computed for stage I. However, we want to clarify that these complexities give no indication of how quickly the model can be trained, as the rate of convergence during training may be governed by various other factors.

AR models' sensitivity to node ordering is a known drawback, is the proposed AFM order equivariant?

Our proposed Mixer architecture is permutation equivariant. I.e., if $\pi \in S_N$ is a permutation of nodes, we have $p_\theta(\pi(G_t) | \pi(G_{t-1}), \dots, \pi(G_0)) = p_\theta(G_t | G_{t-1}, \dots, G_0)$. However, we do enrich the input node representations of the empty graph $G_0$ with positional embeddings derived from a pre-defined node ordering. During training, this ordering is extracted from the input graph $G_T$, while inference allows for arbitrary ordering due to the model's equivariance property. A detailed exploration of these input node representations can be found in the appendix (please see "A.6 Input Node Representations" for more details). We investigate the effect of this node ordering in our ablation studies ("A.16 Additional Ablations"). While, generally, we find it to improve performance after stage I training, it is not a critical component in all settings. We remain open to conducting additional stage II training with these ablation variants if you consider it essential.

While the paper mentions that the proposed AFM depends on the choice of edge ordering, this point requires additional clarification and empirical experimentation.

With "edge ordering", we refer to the order in which edges are deleted in the filtration process. Hence, this ordering is determined entirely by the filtration function. We present experiments on different choices in the appendix ("Additional Ablations").

"Edge ordering" is mentioned in our original manuscript in line 93 of the related work section. We attempt to improve clarity by explicitly stating that the edge ordering is induced by the choice of filtration function.

If you have concrete suggestions for further experiments on this question, we are open to conducting them.

Since the line Fiedler function outperforms the other two options and is preferred in your experiments, then does it infer that structural consistency is prioritized? How does it affect the graph generation?

Ultimately, the line Fiedler filtration function is a heuristic choice and we don't have a rigorous explanation as to why it works well. Intuitively, the line Fiedler function paints edges of a graph in a "continuous gradient", assigning similar values to neighboring edges. We hypothesize that this may simplify the task of learning to reverse the filtration, as edges are mostly added in locally confined regions that neighbor the edges that were added in the previous steps. To guide your intuition, we refer to Figure 5 ("Visualization of different filtration functions on a planar graph") for an illustration of the behavior of the line Fiedler function.

In Page 1, line 48 needs a citation.

We have added citations to Edelsbrunner et al. and Zomordian & Carlsson.

Weaknesses

The choice of filtration function may affect the scheduling method. Also, An analysis of different scheduling methods with various filtration functions is recommended to understand their interplay.

The extensive landscape of potential filtration and scheduling function combinations, coupled with their potential sensitivity to dataset and other hyperparameter selections, prevents definitive generalized recommendations. Nevertheless, we conduct separate ablation studies on the expanded planar graph dataset for both filtration and scheduling functions in Appendix A.16, providing some insights into their individual contributions when fixing the other hyperparamter. We find that (in combination with the linear schedule), the line Fiedler filtration function appears to perform best. In combination with the line Fiedler function, the concave schedule appears to perform best w.r.t. the VUN metric, followed by the linear schedule.

One potential limitation of this approach is its edge independence [4]. The proposed method's approach of adding many edges simultaneously could lead to the edge-independence issue.

Unfortunately, the reference [4] appears to be missing in your review. We suppose that you refer to the fact that the distribution $p_\theta(E_t | G_{t - 1}, \dots, G_{0})$ should not be decomposed as a product over all edges (i.e. the edge presence should not be independent). We agree with this statement, as edges may, for instance, exhibit mutual exclusivity constraints (e.g. in tree graphs that do not contain cycles). For this reason, we note that we approximate the distribution above as a mixture of multivariate Bernoulli distributions, thereby introducing dependencies.

More clarification is needed regarding the adversarial fine-tuning with RL

Following your suggestions, we have extended the section in the appendix to provide details on the adversarial fine-tuning (please see "A.18 Adversarial Finetuning Details"). We have added a reference to this appendix in Figure 1 of the main text. If you have any concrete suggestions on improving clarity further, we are happy to discuss and incorporate them.

Thank you for your time and effort in providing such constructive feedback. We greatly appreciate your insights and have addressed the points you raised below.

Weaknesses

Lack of Complexity Analysis

We have addressed this point in the "Complexity Analysis" section in our general response.

the complexity will increase quadratically if the algorithm needs to decide on all the possible edges

The computational complexity of AFM increases even cubically due to the computation of Laplacian positional embeddings. The DiGress model exhibits the same complexity w.r.t. $N$. While our asymptotic runtime complexity appears less favorable compared to other autoregressive models (e.g. GraphRNN, GRAN), our empirical findings challenge this theoretical limitation. Notably, on protein graphs with up to 500 nodes, our approach demonstrated substantially faster inference times than baseline models. Moreover, the efficient performance of AFM remains consistent across different dataset scales (they are all around 0.03s/graph), suggesting that its efficiency is primarily driven by its ability to use a small $T$.

Missing Citation and Comparison

In our revised version we discuss, among others, HiGen, GDSS, and EDGE in the related work section. We draw more detailed comparisons in the extended related work section of the appendix. We have also added results for HiGen and EDGE to Table 1. Our main conclusions remain unchanged.

In many cases, the performance of AFM falls short compared to diffusion models and sometimes even AR counterparts.

We respectfully disagree with the assertion that AFM falls short compared to AR counterparts. Our experimental results indicate that AFM generally outperforms existing AR methods. Below, we summarize our comparisons with other AR models:

• Protein graphs: AFM outperforms the state-of-the-art AR baseline (GRAN) w.r.t. all MMD metrics.
• Expanded synthetic datasets: Across all expanded synthetic datasets, AFM outperforms GRAN w.r.t. VUN and all MMD metrics.
• Small synthetic datasets: AFM outperforms both GraphRNN and GRAN in terms of the VUN metric. Regarding the MMD metrics, no AR method consistently dominates across all graph descriptors. It's important to note that MMD estimates on these small datasets have high variance due to the limited sample size (40 samples). As we demonstrate in Appendix "A.17.2 Bias and Variance of MMD Estimation", the standard deviation of the MMD estimates can be even comparable to the estimates themselves. This high variance was a primary motivation for studying the expanded synthetic datasets, where MMD metrics exhibit substantially lower variance and provide more reliable comparisons.

While this paper claims to improve efficiency, it lacks experiments for large graphs

We would like to clarify that some of the protein graphs used in our experiments are already moderately large, containing up to 500 nodes. Currently, we are not aware of publicly available datasets with a reasonable sample size that would allow us to properly benchmark our method on graphs consisting of more than 1K nodes.

• Point Cloud dataset by Liao et al. (2020): This dataset includes graphs with up to 5,000 nodes but contains only 26 graphs in the training set and 8 graphs in the test set. Training a generative model and performing a thorough evaluation on such a small dataset is challenging due to high variance and limited statistical significance.
• Single Large Graphs (e.g., EDGE with CiteSeer or Cora): Some works have trained models on individual large graphs. However, this approach focuses on generating a single graph rather than learning a distribution over graphs, which is the primary objective of our work.
• Subgraphs from Larger Networks (e.g., GraphARM): Other approaches sample subgraphs from larger citation networks. Unfortunately, these subgraphs are generally small, with sizes up to 87 nodes in the case of the Cora dataset used by GraphARM. This does not address the need for experiments on significantly larger graphs.

If there are specific datasets that you can recommend for evaluating generative models on larger graphs, we would be eager to consider them. However, we also want to clarify that our goal is to demonstrate the good balance between efficiency and generation quality of our method in high-throughput applications, rather than the scalability to generating larger graphs. To clarify this point, we have revised our manuscript to replace the term "scalability" with the more precise term "efficiency" and "high-throughput generation" (see lines 24, 64, 74 of original submission).

Investigating how a larger sequence of subgraphs affects performance and determining the optimal sequence length particularly for large graphs would be valuable.

Please refer to the "Effect of the filtration granularity $T$" section in our general response.

I would like to thank the authors for their detailed response and for providing an updated version which helps in addressing most of the concerns. However, I still have some concerns that still need consideration:

• Given the existence of other AR-based methods for graph generations, such as HiGen, with comparable to (or even better that) some diffusion models, I discourage using the repeated claim that this work is the *"first AR model that matches the performance of diffusion-based models while maintaining its speed advantage"*l.

• It is recommended to include the performance and sampling time of HiGen [1] on the Protein dataset, noting that the sampling speedup was reported in the appendix.

• As raised by another reviewer, the adversarial training stage (stage II) can be applied to other generative models for performance improvement, as it is not an integral part of this architecture. Therefore, a fairer comparison would involve comparing the proposed model with other models augmented with stage II, such as Digress+Stage II, Gran+stage II, HiGen+stage II, and others.

• To evaluate the sensitivity of the proposed model to node-ordering, it would be beneficial to observe its performance using canonical node orderings like BFS, DFS and so on.

Please also note that my initial review is updated to include the missing references.

References:
[1] M. Karami, “HiGen: Hierarchical Graph Generative Networks”, International Conference on Learning Representations, 2024.

Weaknesses

The designed method is a bit complicated: with many designs in autoregressive part, and additional adversarial training for further performance improvement.

We acknowledge that our proposed method involves multiple components and may appear technically complex. However, our ablation studies demonstrate that each of the introduced techniques is essential for achieving the observed performance improvements. We believe that these technical contributions not only enhance our model but could also have applications in other generative models within the field.

To facilitate adoption and ease of use, we have added a section to the appendix giving practical advice on the choice of hyperparameters ("A.5 Practical Advice on Hyperparameter Choice"). Additionally, we are committed to transparency and reproducibility; therefore, we will publish our source code upon acceptance of the paper. We hope that these resources will help the community in implementing and extending our work.

However, when comparing to baselines, I cannot find consistent and noticeable performance improvement, although the method is faster than diffusions.

We present an autoregressive model that achieves state-of-the-art performance on several benchmarks while being orders of magnitude faster than competing diffusion models. We do not aim to outperform these diffusion baselines in terms of quality but focus our efforts on matching their quality while substantially improving inference speed. To the best of our knowledge, our method is the first autoregressive graph generative model that can compete with diffusion models on the benchmarks we presented.

The author miss some important and highly related references and baselines, such as the [1]. They share many common parts and should be discussed.

Thank you for this suggestion. We discuss the similarities and differences of AFM and Pard in the extended related work section of the appendix ("A.1 Extended Related Work").

Limited experiments: only simple and small simulation graphs.

We would like to clarify that we presented our method on real-world protein graphs that contain up to 500 nodes. Currently, we are not aware of publicly available datasets with a reasonable sample size that would allow us to properly benchmark our method on graphs consisting of more than 1K nodes.

• Point Cloud dataset by Liao et al. (2020): This dataset includes graphs with up to 5,000 nodes but contains only 26 graphs in the training set and 8 graphs in the test set. Training a generative model and performing a thorough evaluation on such a small dataset is challenging due to high variance and limited statistical significance.
• Single Large Graphs (e.g., EDGE with CiteSeer or Cora): Some works have trained models on individual large graphs. However, this approach focuses on generating a single graph rather than learning a distribution over graphs, which is the primary objective of our work.
• Subgraphs from Larger Networks (e.g., GraphARM): Other approaches sample subgraphs from larger citation networks. Unfortunately, these subgraphs are generally small, with sizes up to 87 nodes in the case of the Cora dataset used by GraphARM. This does not address the need for experiments on significantly larger graphs.

If there are specific datasets that you can recommend for evaluating generative models on larger graphs, we would be eager to consider them. However, we also want to clarify that our goal is to demonstrate the good balance between efficiency and generation quality of our method in high-throughput applications, rather than the scalability to generating larger graphs. To clarify this point, we have revised our manuscript to replace the term "scalability" with the more precise term "efficiency" and "high-throughput generation" (see lines 24, 64, 74 of original submission).

Questions

can you provide some possibilities of extending the current method to attributed graphs

We have provided propspective avenues for future research above.

References

[1] Zeming Lin et al., Evolutionary-scale prediction of atomic-level protein structure with a language model. Science379, 1123-1130(2023). DOI:10.1126/science.ade2574

[2] Chen, Y., Xu, Y., Liu, D. et al. An end-to-end framework for the prediction of protein structure and fitness from single sequence. Nat Commun 15, 7400 (2024). https://doi.org/10.1038/s41467-024-51776-x

[3] Li, Yibo, 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, no. 1 (2020): 77–91. https://doi.org/10.1021/acs.jcim.9b00727.

Thank you for your time and effort in providing constructive feedback. We appreciate your insights and have addressed the points you raised below.

Weaknesses

eq. 7 left side is conditional on t+1 to T steps, which is not correct.

We thank the reviewer for pointing out this typo. It is corrected in our revised manuscript.

while figure 1 shows the illustration of training procedures, the generation procedure is not mentioned, as well as the detailed setting of the generator during GAN training.

The generation procedure follows the standard autoregressive approach: Namely, we start with the empty graph $G_0$ and iteratively sample $G_t$ from the learned distribution $p_\theta(G_t | G_{t - 1}, \dots, G_0)$.

We have updated the figure caption with a reference to the appendix in which we provide additional in-depth description of the GAN training, including the inference setting of the generator.

the mixer architecture design uses too many representations: T x N with N being the total number of nodes. This can cause significantly increased memory requirement.

We acknowledge the concern that the mixer architecture may require significant memory if $T$ is large. However, in our experiments, we have not found memory complexity to be an issue for the graph sizes we considered, due to our ability to use a small $T$. To address potential memory constraints, we have studied a simplified autoregressive structure with a memory complexity of $\mathcal{O}(N)$, assuming efficient implementations of attention mechanisms. This alternative is detailed in Appendix "A.3 A First-Order Autoregressive Variant." Our additional experiments demonstrate that this simplified structure is a viable option if memory consumption becomes a concern in practical applications. Please also refer to the "Complexity analysis" section in our response for a more detailed discussion.

many designs are not general, such as not supporting attributed graphs with node labels and edge labels, which are well supported by diffusion models and traditional AR graph generation methods.

We acknowledge the concern that our current design does not explicitly support graphs with node and edge attributes. However, we want to emphasize that our primary focus is on developing efficient AR model for unattributed graphs and we present the first AR model that matches the performance of diffusion-based models while maintaining its speed advantage. Furthermore, un-attributed graph topologies are often of significant interest in various applications, such as protein structure modeling and design, where contact maps represent the spatial proximity between amino acids [1, 2].

As discussed in our conclusion and appendix, our method is naturally extendable to edge-labeled graphs. Regarding the modeling of node attributes, we propose two prospective approaches:

• Post-hoc node labeling: After generating the graph topology, node labels can be assigned based on the structural context, as suggested by Bergmeister et al. (2024). For example, in molecular graphs, valency constraints and local connectivity patterns may provide strong cues for determining atom types. Such an approach was used in [3].
• Extension of the Filtration Process: We can extend the filtration process to include node labels by representing them as labeled self-loops and incorporating them into the edge filtration. This approach allows the model to learn node attributes alongside the graph topology within the same generative framework.

We believe that integrating node and edge labels is a promising direction for future work, which can further enhance the applicability of our approach to a broader range of graph generation tasks.

Weaknesses

Aside from running time, the experiments do not provide clear evidence that AFMs perform better than the baseline models.

As argued above, our experiments provide evidence that AFM substantially outperforms traditional autoregressive methods. We do not aim to out-perform the diffusion baselines in terms of quality but focus our efforts on matching their quality while substantially improving inference speed.

Questions

I strongly recommend that the authors include a paragraph analyzing the time complexity of AFM and diffusion models in depth.

Please refer to the "Complexity Analysis" section in our general response.

Additionally, the introduction of extra hyperparameters, such as T, K, gamma(t), and lambda_t, complicates the selection of appropriate hyperparameters for a given dataset.

Thank you for this suggestion. We have added a section with practical advice on hyperparameter tuning to the appendix ("A.5 Practical Advice on Hyperparameter Choice"). Additionally, we will publish our source code upon acceptance of the paper.

Thank you for your time and effort in providing such constructive feedback. We greatly appreciate your insights and have addressed the points you raised below.

Weaknesses

it is still unclear why these filtration sequences benefit the step-by-step graph generation compared to other possible sequences [...] if any theoretical guarantees regarding the rationale of the filtration sequences exist, they would significantly strengthen the justification for the use of graph filtration

One key difference between our method and other autoregressive models (such as GraphRNN, GRAN, GraphGen, etc.) is that AFM can model non-monotonic graph sequences. While traditional methods generate graphs $G_t$ by exclusively adding edges, our model allows for both the addition and deletion of edges. This flexibility enables AFM to adjust the graph structure dynamically, correcting errors that may occur during the generation process.

As we discuss in Sec. 3.2 (paragrah "Edge Decoder"), we hypothesize that the ability to both add and delete edges is crucial for avoiding the accumulation of errors during sampling (i.e., to mitigate exposure bias). If AFM samples an erroneous substructure in an intermediate step (e.g. a cycle when generating trees or a $K_5$-subdivision when generating planar graphs), it still has the opportunity to rectify this mistake in subsequent iterations.

Therefore, we argue that it is essential to train AFM on noise-augmented filtrations during Stage I. By exposing the model to imperfect transitions, we explicitly train it to perform both edge additions and deletions.

The results in the ablation studies section (Table 4) raise further concerns; specifically, the performance of "Stage I w/o Noise" appears to be not good, suggesting that the filtration sequences may not enhance performance. It seems that the randomness of perturbed generation sequences is what leads to improved outcomes

The filtration sequence is a fundamental building block of our autoregressive modeling, providing a general method to extract sequences from graphs. This filtration framework extends beyond existing autoregressive models, and we consider several natural choices for the filtration function in our work. We want to emphasize that the filtration is not a standalone component; rather, it works in conjunction with other elements, such as noise augmentation, to form our complete model. Therefore, we respectfully disagree with the hypothesis that "filtration sequences may not enhance performance."

We have conducted a study on different choices of the filtration function, detailed in Appendix "A.16 Additional Ablations." Our findings indicate that some choices perform better than others, demonstrating that selecting an appropriate filtration sequence is as important as incorporating noise augmentation. This suggests that the filtration sequence plays a significant role in the overall performance of our model and optimizing the filtration function could be interesting future research direction.

The diversity of baselines is limited. [...] There is a lack of representation of other general graph generation models, particularly those related to normalizing flows and variational autoencoders

To the best of our knowledge, there are currently no graph VAE models that can compete with the other baselines on the datasets we are considering. This observation aligns with recent related works in the field, which also do not report results for VAEs on these datasets. Moreover, we want to emphasize that running all the baselines on our datasets is time-consuming and resource-intensive; it takes up to one week to train a model on a single dataset using an A100 GPU. We have made every effort to include the most relevant methods that have demonstrated state-of-the-art performance on the small synthetic datasets from the literature.

To provide a comparison to a more diverse range of baselines on the small synthetic datasets, we have included results for HiGen and EDGE to Table 1 in the revised manuscript.

In terms of running time, AFMs only outperform diffusion models. However, the efficiency difference between AFMs and GRAN (another autoregressive model) is minimal

Our proposed model outperforms GRAN substantially in terms of generation quality on all datasets we studied. This is consistent with results in the literature indicating that GRAN underperforms in comparison to diffusion models. While AFM is only slightly faster than GRAN on the synthetic datasets, we note that it is 10 times faster on the larger protein graphs. To the best of our knowledge, we present the first autoregressive graph generative model that can compete with diffuison baselines on the benchmarks we studied while being orders of magnitude faster.

Questions

Have you explored how varying the number of filtration steps might impact generation quality

As noted in the common response, we have added this experiment to the main text.

It would be interesting to see how well the approach performs on larger graphs, such as Cora, Citeseer, or Polblogs

We would like to clarify that some of the protein graphs used in our experiments are already moderately large, containing up to 500 nodes. Currently, we are not aware of publicly available datasets with a reasonable sample size that would allow us to properly benchmark our method on graphs consisting of more than 1K nodes.

• Point Cloud dataset by Liao et al. (2020): This dataset includes graphs with up to 5,000 nodes but contains only 26 graphs in the training set and 8 graphs in the test set. Training a generative model and performing a thorough evaluation on such a small dataset is challenging due to high variance and limited statistical significance.
• Single Large Graphs (e.g., EDGE with CiteSeer or Cora): Some works have trained models on individual large graphs. However, this approach focuses on generating a single graph rather than learning a distribution over graphs, which is the primary objective of our work.
• Subgraphs from Larger Networks (e.g., GraphARM): Other approaches sample subgraphs from larger citation networks. Unfortunately, these subgraphs are generally small, with sizes up to 87 nodes in the case of the Cora dataset used by GraphARM. This does not address the need for experiments on significantly larger graphs.

If there are specific datasets that you can recommend for evaluating generative models on larger graphs, we would be eager to consider them. However, we also want to clarify that our goal is to demonstrate the good balance between efficiency and generation quality of our method in high-throughput applications, rather than the scalability to generating larger graphs. To clarify this point, we have revised our manuscript to replace the term "scalability" with the more precise term "efficiency" and "high-throughput generation" (see lines 24, 64, 74 of original submission).

References

[1] Zeming Lin et al., Evolutionary-scale prediction of atomic-level protein structure with a language model. Science379, 1123-1130(2023). DOI:10.1126/science.ade2574

[2] Chen, Y., Xu, Y., Liu, D. et al. An end-to-end framework for the prediction of protein structure and fitness from single sequence. Nat Commun 15, 7400 (2024). https://doi.org/10.1038/s41467-024-51776-x

[3] Li, Yibo, 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, no. 1 (2020): 77–91. https://doi.org/10.1021/acs.jcim.9b00727.

Thank you for your time and effort in providing such constructive feedback. We greatly appreciate your insights and have addressed the points you raised below.

Weaknesses

A comparative analysis with other approaches, such as the autoregressive model by Kong et al. (2023) and the EDGE graph diffusion model by Chen et al. (2023), would be helpful.

We have added a detailed discussion of the similarities and differences of absorbing state diffusion (particularly GraphARM and EDGE) and AFM to our extended related work section in the appendix (A.1).

Additionally, we have added results of EDGE to table 1. Unfortunately, Kong et al. have not released official code for GraphARM.

An analysis on the impact of filtration steps is missing; it would be insightful to see how generation quality changes as the number of filtration steps varies.

As noted in the common response, we have added this experiment to the main text.

Exploring ways to incorporate attribute information could be beneficial.

We acknowledge the concern that our current design does not explicitly support graphs with node and edge attributes. However, we want to emphasize that our primary focus is on developing efficient AR model for unattributed graphs and we present the first AR model that matches the performance of diffusion-based models while maintaining its speed advantage. Furthermore, un-attributed graph topologies are often of significant interest in various applications, such as protein structure modeling and design, where contact maps represent the spatial proximity between amino acids [1, 2].

As discussed in our conclusion and appendix, our method is naturally extendable to edge-labeled graphs. Regarding the modeling of node attributes, we propose two prospective approaches:

• Post-hoc node labeling: After generating the graph topology, node labels can be assigned based on the structural context, as suggested by Bergmeister et al. (2024). For example, in molecular graphs, valency constraints and local connectivity patterns may provide strong cues for determining atom types. Such an approach was used in [3].
• Extension of the Filtration Process: We can extend the filtration process to include node labels by representing them as labeled self-loops and incorporating them into the edge filtration. This approach allows the model to learn node attributes alongside the graph topology within the same generative framework.

We believe that integrating node and edge labels is a promising direction for future work, which can further enhance the applicability of our approach to a broader range of graph generation tasks.