Uncovering the Spectrum of Graph Generative Models: From One-Shot to Sequential

We thank you for your review and for asking for further details. We are happy to resolve all doubts.

W1: Can the unification of one-shot and autoregressive graph generative models be a strong contribution? For instance, GRAN (Liao et al., 2019) can also be the unification between one-shot and autoregressive graph generative model by setting the block size as the number of nodes. What is the key difference of the work from GRAN except for the usage of diffusion models?

We lean towards a positive answer, as we not only unify the one-shot and autoregressive paradigms, but also show how one can be adapted to the other. We also provide a formal way of designing new graph generative models without having to strictly choose between autoregressive and one-shot: one could design a new one-shot model, and quickly try the same formulation with different levels of sequentiality, trading off computational time and memory usage, and looking at how it affects performances. In a way, we unlock the level of sequentiality as a hyperparameter that can be tuned in any model to further improve quality and resource factors.

We think the key difference between our IFH framework and GRAN is flexibility: GRAN makes a lot of assumptions, such as fixing the number of generated nodes to the maximum number of nodes in a dataset (actually the biggest multiple of the fixed block size), and cannot capture the true distribution on the number of nodes of a dataset. For this reason, there is a bias towards large graphs, as the biggest connected component is picked, and smaller graphs are not sampled.

W2: I wonder if it is proper to say the performance as the new state-of-the-art results as mentioned in the abstract. The FCD for QM9 and NSPDK for ZINC do not seem to be state-of-the-art results. Also, as the authors adapted DiGress, the performance comparison with DiGress can be meaningful.

We agree that for some metrics, the best one-shot baseline CDGS outperforms our approach. However, our sequential instances improve by a significant margin the autoregressive state-of-the-art, as shown in Table 2, while being competitive with CDGS. We thank you for recommending adding DiGress as a baseline, and we did so in the revised manuscript.

W3: Lack of detailed analysis on the sample quality-time trade-off. A more detailed analysis of the correlation between the sample quality and time (or memory consumption) is needed by comparing the one-shot and autoregressive versions of the IFH model.

Although we explored the subject in Section 5.1, we might not have been too detailed. For this reason, we added a more thorough discussion on the sample quality/time/memory trade-off in the new Discussion section 6. To summarize, we noticed an increase in memory consumption and decreased computational time as we moved away from the 1-node sequential model, as we expected in Section 4.3.

Q1: Which level of sequentiality did the authors use (I cannot find details in appx D.)? Does the degree of sequentiality imply the block size (or the number of steps)?

Thank you for noticing. We have updated the appendix referring to generic graphs, and moved it as Appendix A to make it more accessible from the main text, moving theoretical parts after. In particular, we added the "Sequentiality levels" Table (3a). You are right, the degree (or level) of sequentiality implies the sizes of blocks used, which in turn affects the number of steps. Consider the following with 53 nodes: one-shot inserts all 53 nodes in 1 step; sequential with categorical removal with blocks {1, 2, 8} will generate (with any permutation) 6 blocks of 8 nodes, 2 blocks of 2, and 1 of 1, as the insertion model is trained to pick the largest block size if needed, minimizing the number of steps, which in this case is 9; 1-node sequential model will take 53 steps. Notice that, even adding a block size of 2 to 1-node sequential makes it roughly halve its generation steps.

Q2: The generic graph generation results in appx B do not look good enough. Is there any particular reason that the model works okay for molecular graphs but not for non-attributed generic graphs?

Although we do not reach state-of-the-art on all metrics against the very strong one-shot model CDGS, the results on generic graphs beat all autoregressive baselines, and are competitive with one-shot baselines. However, as you said, we also noticed a drop in performance for non-attributed generic graphs, and we think that would be a promising direction to explore. Particularly for 1-node sequential models applied to big-sized graphs, we noticed that the halting signal's sparsity hinders the halting model's training process. We address this limitation in the Discussion section (numbered 6 in the revised version).

We thank you for the comments, and we are happy to resolve any doubts.

W1: This paper combines the ideas of autoregressive graph diffusion [1] and block generation [2]. Although the combination is natural, I am not clear on the main difference between the proposed method and GRAN. It seems that the unity of autoregression and one-shot is due to the design of block generation, rather than the diffusion of node removal.

We are happy to clarify the difference with GRAN. Although the idea of using block generation is shared between IFH and GRAN, it has been adopted even earlier and falls into the category of motifs generation. Ours is a way to generalize the concept and unify it with sequential and one-shot generation to reap the benefits of both. On the other hand, the GRAN paper does not provide any information nor a way of integrating one-shot models into the sequentiality spectrum. The block generation mechanism is a way of controlling the degree of sequentiality, yes, but it is fixed and built into the model. Our approach allows the design of any Markov scheme for adding blocks, also with varying sizes, and has a direct link with the distribution in the dataset (as the insertion and halting models are trained accordingly). On the other hand, GRAN does not provide an explicit way to model the distribution of the number of nodes, fixing this number to the maximum size in the dataset, and delegating to the mixture of Bernoullis the task of generating connected components with some size. Furthermore, the GRAN approach might work for datasets with similar-sized graphs. Still, when there is a considerable variance, smaller graphs are penalized due to picking the biggest connected component of a generated graph, changing the output distribution of the model.

Regarding your last point, you are partially correct, as the design of block generation and the diffusion of node removal are two faces of the same coin, which are the removal and insertion models. However, the block generation of GRAN is fixed and built into the model, and does not consider how the distribution of graph sizes of a dataset behaves.

W2: It's not clear to me what advantages 1-node IFH has over autoregressive methods. Does the benefit come from the prediction of the number of nodes?

Actually, the 1-node IFH is an autoregressive model, that is, any autoregressive model that generates one node at a time is a 1-node IFH (as pointed out in Section 4.1). In this case, the advantage is that, with our framework, we can adapt strong one-shot models for the 1-node generation modality, beating the autoregressive baselines, which usually implement tailored and simple models for inserting one node. We think this is one of the strongest capabilities of our IFH model.

W3: The time and memory costs of baselines are not reported in Tables 2 and 3. It is therefore impossible to see the trade-off between sampling quality and time.

Not quite, as our sampling quality/time trade-off analysis is intended for our framework, assessing what changes when we change the degree of sequentiality with the filler model in question. The comparison with the baselines in Table 2 aims to place our proposed approach in the state of the art, showing whether our framework is capable of generating performing models. To highlight this fact, we separated Table 2 into performance results and time/memory usage table.

Thank you for your comments and for asking for additional motivation for our work. We find that clarifying this point is of utmost importance. Let us start by answering your questions.

Q1: Among the five datasets presented, the proposed approach does not outperform other methods in majority of the metrics. Can the authors justify the utility of their approach given these results?

While it is true that the strongest one-shot baseline CDGS outperforms our approach in generic graphs datasets, our experiments show that increasing the degree of sequentiality with the chosen one-shot model DiGress leads to state-of-the-art results with respect to autoregressive generation, while also being competitive, if not better in many metrics, in molecular generation.

Metrics comparison versus other methods helps to answer whether our best instance of the IFH model can be useful for good quality generation. However, we argue that this is not the only criterion for choosing a good model, and through our sample quality/memory/time trade-off analysis we investigated other aspects. In particular, how the degree of sequentiality influences performance, computing time, and memory consumption. These latter aspects might be needed for some kinds of datasets, e.g. big sized graph datasets, where we showed an improvement of 50 times less memory usage.

Conceptually, we think one of the main take-home messages of our work is that, when designing new graph generative models, be it one-shot or autoregressive, there is always a way to explore the whole spectrum with it, trading off memory, time, and quality, and perhaps push its native performances. To do so, one can use our mathematical framework, which can be a way of standardizing techniques as building blocks.

Q2: How to select $r_s$ and what are the differences between seq, seq-small, and seq-big?

Actually, we don't manually select $r_s$ but design the process that stochastically generates $r_s$. Your question can be answered by our sample quality/time/memory trade-off analysis, in which we showed a significant improvement when using smaller block sizes concerning generation quality and memory, but not in time (due to not being able to parallelize during generation as well as one-shot models). When increasing the block sizes, we get the inverse, even though for larger datasets, we see that having larger blocks, but not too large, improves quality and time, so there must be a sweet spot depending on the size of the graphs in the dataset. To summarize, our empirical advice is to use one-shot models for smaller graphs, and go towards 1-node sequential models for bigger graphs. When graphs get too big, having a small block size requires a solid halting process, because the halting signal becomes very sparse in a setup with a huge number of steps. For this reason, increasing the block size to reduce the number of steps can help. We reported these points in the new Discussion section (numbered 6).

We thank you for inquiring about the meaning of the levels of sequentiality in generic graphs. We updated the appendix section to explain better what we are doing in those experiments.

We also would like to answer the proposed weaknesses which we did not answer above.

It is not clear why only the two datasets with good performance were shown in the main paper.

We made this choice due to page limitations (as generic graphs datasets tables occupy quite a lot of space) and because the related work from which we took major inspiration for our experimental setup (CDGS) put much more emphasis on molecular datasets. To address this as best as possible, we moved the generic graphs section to Appendix A to make it more accessible from the main text.

How about other datasets that have been used in prior work, such as Grid, Protein, and 3D point-cloud?

Thank you for the suggestion. We see that these are the datasets used in GRAN, which are not so widely adopted in more recent works. Although we already provided a wide range of datasets for evaluating our approach, we will add experiments for the Grid dataset, which is the one where the ablation study for GRAN was conducted. We consider this as a way of comparing our approach to theirs, and see whether we get an improvement. We will get back with the results soon.

Update: due to technical difficulties we were not able to finalize the additional experiments on the Grid dataset. However, we believe that our method has already been evaluated on a significantly wide array of popular datasets, among which molecular and generic graphs. To the best of our knowledge, the Grid dataset has only been used in GRAN.

Thank you for your valuable comments, which we found interesting discussion points.

W1: The proposed method shares certain similarity with GRAN, while being novel for adapting diffusion process inside.

While it is true that our proposed method shares similarities with GRAN regarding block generation, our framework is capable of capturing every aspect of the data distribution, in particular the size of sampled graphs, thanks to learning a node-insertion and halting model. A notable limitation of GRAN is that it fixes the size of blocks as a hyperparameter, and the number of nodes generated to the maximum size of the dataset. This warps the output distribution, favoring bigger graphs, and making it challenging to generate smaller graphs. Additionally, IFH can be used to design any autoregressive block generation scheme, GRAN included.

W2: The goal of combining autoregressive method and one-shot generation is to combine their strength together while eliminate their shortcomings. However I think the proposed method is not ideal for this goal. For example, one-shot diffusion is a permutation equivariant generation model that is invariant to node permutation, here the designed model becomes ordering sensitive, which needs a careful ablation over node removing process. And autoregressive method has the problem of being hard to parallel during training, hence the designed model will be even slower in training comparing with one-shot generation. Last, the reported experimental result doesn't show a significant benefit of adapting sequential generation to one-shot diffusion.

While we agree that autoregressive models have the added burden of having to select the best node ordering, we found empirically that choosing the BFS order was enough to make our approach competitive with the best one-shot baselines.

Regarding the fact that autoregressive models are hard to parallel during training: not entirely, as we sample the entire sequences from a batch of graphs, and train on the collected examples in parallel, because no hidden states are passed between steps. This characteristic was also implemented in GRAN, as it avoids the problem you mentioned. Following your suggestion, we added the time/memory tables for the training processes (Tables 2b, 2e, 3d) to show how sequentiality affects the time to reach convergence: our 1-node sequential model takes longer to train for a fixed amount of epochs, but reaches optimal validation performance much faster.

On the last point, we showed in our experiments that adapting the one-shot model in question (DiGress) consistently improves performance for some degree of sequentiality (mostly 1-node sequentiality). One notable example is ZINC, where our 1-node sequential model surpasses CDGS on many metrics, and the original DiGress on all metrics.

Motivated by these findings, we hypothesize that having a permutation equivariant model is not the only ingredient for a good-performing generative model. For example, breaking the sampling process into smaller steps might help reduce each atomic step's complexity. We have seen a similar phenomenon for diffusion models, sequentially denoising a sample in many steps, which beat fully one-shot models like VAEs and GANs.

Our answer continues in the below comment.

We thank you for the review and for acknowledging our work's main points. We are glad to resolve any doubt in the following.

W1: The proposed framework does not provide insightful knowledge regarding choosing one-shot or sequential generation methods.

We thank you for bringing up this point. We added a new "Discussion" section (numbered 6) to discuss further the empirical results, and how one might choose one-shot, sequential, or an in-between option. To summarize, our advice is to use one-shot models for smaller graphs, and go towards 1-node sequential models for bigger graphs to improve performance. When the graphs reach very large sizes, however, the halting signal becomes sparser, making the halting model harder to train. For these cases, going back to a hybrid solution can help, also in terms of memory and time consumption.

Our proposed framework makes it possible to compare one-shot and sequential models that share the same architecture and generative model, with the degree of sequentiality becoming a hyperparameter. In fact, our experiments suggest that for different distributions of graphs, different levels of sequentiality will improve performance and resource usage. This is useful for the future design of graph generative models, as new architectures can be seamlessly adapted to sequential or one-shot generation, pushing their performances further than their native modality. Additionally, we discussed in Section 4.3 the complexity in time and memory of increasing sequentiality. Experimental results are consistent with the above statements.

W2: Only one base model is tested in the proposed IFH framework.

This is certainly a valid observation. One of our work's aims is to prove the feasibility of adapting a one-shot model to act in a sequential setup and observing whether this leads to an improvement. In the case of adapting DiGress, we got competitive results with the state-of-the-art one-shot models while beating by a significant margin autoregressive baselines, so we can say that the initial claim has had a positive outcome. We think adapting other one-shot models would be the next step, but we preferred to postpone it in favor of a more extended explanation of the framework.

W3: Experiments are not sufficient. Ablation studies are missing. The comparisons of time/memory cost with baselines are missing.

Regarding your first concern, we think we disguised the reader in dubbing the ablation study "Selection study". Actually, in that section we perform a similar study (on block generation formulation and different orders) as the one done in the GRAN paper under the section dubbed "Ablation study". If this is not resolving your issue, we would be happy to receive more information about what additional experiments we should perform.

We gladly answer the second concern by referring to our selection study, which we clarified in Section 5.1, commenting on Table 1. There, we compared several instances of our model changing the removal process and node ordering in a grid. This is a selection study from the perspective of choosing the best combination of the two. At the same time, we are also isolating the contributions of the two factors, making it also an ablation study. In Section 5.1, we commented on such contributions, noting that both BFS and categorical removal independently improve performance, computational time, and memory. This latter analysis is characteristic of an ablation study. Furthermore, in the remainder of the experiments, we explore how the degree of sequentiality affects results.

Regarding your last concern, in this work, we want to compare time/memory cost within a given model (DiGress in our case), varying the degree of sequentiality. With this analysis, we can actually understand the contribution of changing the degree of sequentiality.