Pard: Permutation-Invariant Autoregressive Diffusion for Graph Generation

Thank you for these detailed questions and feedback for improving the presentation. Let us provide detailed response to all your questions.

1. It is unclear how the diffusion model is employed in PARD. Sec 3.1 and the second part of Eq. 6 are not quite relevant to each other. Can you elaborate on that?

Sure! As you know, diffusion requires input and output to have exactly the same size (same number of nodes and edges), which is shown in Sec 3.1. Hence, to use diffusion for each block’s conditional distribution, we should pad the input (which has B blocks) to the same size of the output (which now has B+1 blocks), that is why in Eq. 6 the second part is actually conditional on the target block’s size, and the first part of Eq.6 captures the distribution of next (i.e. (B+1)-th) block’s size (|.| denotes size). The padding procedure is also shown in Fig. 2, where dashed edges and nodes are added (virtual nodes and edges). After padding, we use the second part of Eq. 6 to model the diffusion process, which is the same as procedures introduced in Sec. 3.1, except that we DO NOT modify all previously generated B blocks: noise is only introduced in the target (B+1)-th block. Please let us know whether this is clear, and we would like to hear your feedback on how to make this easier to understand. Note that you can also find/study the exact implementation in the provided anonymous repo, under pard/parallel/task.py.

2. Proof for the statement: 2-FWL expressivity for the proposed higher-order transformer.

As the higher-order transformer combines PPGN and Transformer, it shares the same expressivity as PPGN. The reason is simple: the Transformer part (with weaker expressivity) can implement identity mapping, and does not affect the expressivity of the PPGN part. For the 2-FWL expressivity of PPGN, please see the [paper] (https://arxiv.org/abs/1905.11136) for the detailed proof.

3. Please provide the results of other baselines on QM9 if possible.

For QM9, we adopt the more challenging setting that considers explicit hydrogens, as introduced in DiGress. We avoid the easier setting because most baselines, including DiGress and SwinGNN, can achieve 99% accuracy on it, rendering it an ineffective testbed due to the lack of distinction between models. However, we do not have the performance numbers for other baselines as they did not report their numbers in this more challenging setting. Given the time limitation of the rebuttal period, we apologize that re-running all baselines for the new setting is unrealistic, and hope you can understand.

4. The total number of diffusion steps is directly related to the number of blocks. I anticipate the generic graphs will have more blocks than QM9. Can you show the total number of diffusion steps for other datasets?

As shown in Appendix Table 6, we can achieve the same result using only 140 total diffusion steps in QM9. To demonstrate the number of blocks for a generic setting, we report the numbers for the grid dataset, which has the largest graph size (100~400). For this dataset, there is a maximum of 27 blocks, with an average of 18.625 blocks. With the default 40 steps we used, the total number of diffusion steps is 745. Note that we haven't conducted an ablation study to reduce the number of diffusion steps as shown in Table 6, and we expect that a smaller number of diffusion steps can be used without sacrificing performance.

5. Some of the discussions are redundant can be moved to appendix

Thank you for your suggestion, we fully agree that the part related to DiGress and GRAN can be moved to the appendix, and we will make this adjustment. Please let us know if you think other interesting results should be moved to the main section.

6. There is no discussion about the limitation in the manuscript.

We briefly discuss the limitation in the Neurips checklist section, but we would like to elaborate further here. One major limitation is that each block currently uses the same number of diffusion steps, which is not ideal and can result in unnecessary sampling steps. Empirical evidence shows that approximately 50% of blocks can be predicted directly without any sampling steps, as they do not encounter transformation problems (introduced in Sec. 3.3). It would be highly beneficial to develop a hardness measure (such as graph energy) for the symmetry problem and use this measure to determine the appropriate number of diffusion steps for each block. This approach could significantly reduce the total number of diffusion steps.

If you feel that we have addressed most of your concerns, please consider supporting us in achieving a better overall score. Thank you for your time.

Thank you for the response. I want to mention that one of the main contributions of this work is its improvement in the efficiency. Given the discussion, the inference time of the proposed method highly relies on the number of blocks and does not necessarily offer efficiency on large graphs in the current version. However, the idea it self is interesting and the results are promising. Therefore, I have increased my score to 6 to support this work.

Thank you for your further support. We want to mention that for larger graph, our Pard should still outperforms DiGress in both efficiency and performance. When consider larger graph, each block's number of diffusion steps can be further reduced as there can be dramatically less symmetry inside. In fact, we have found that DiGress struggle to perform good in the Grid dataset (the largest dataset we considered) given the rich symmetry inside. Our Pard breaks symmetry easily with the AR mechanism inside, such that later blocks will have less and less symmetry and lots of blocks does not need any diffusion steps (50% in QM9 dataset). In the final version of the paper, we will add the ablation study on Grid, to show that the effectiveness in both efficiency and performance comparing to single-block version DiGress. At the end, we appreciate the discussion you provided, and we are grateful for the feedback to improving our paper.

Thank you for giving positive feedback to our paper, we would like to address all your questions in detail.

1. Why does diffusion based on an equivariant network solve the flaw in equivariant modeling?

The underlying magic behind the randomness introduced in the diffusion process is relatively straightforward. During each training and inference step, noise is added to the current graph structure (assumed to have many symmetries) through resampling. This process modifies the graph to a different structure with fewer symmetries. Consequently, the number of sampling steps is crucial in controlling the degree of symmetry-breaking. A larger number of sampling steps increases the likelihood of successfully breaking the current symmetries, thereby making it easier to denoise to the target graph. This concept shares similarities with the findings of Abboud et al. in their paper "The surprising power of graph neural networks with random node initialization." We acknowledge the need for a formal proof of its connection to graph energy, and we have highlighted this in our paper to encourage future research. Note that our paper is the first work mentioning the issue of equivalent generative models, and pointing out the connection to diffusion. We hope this can motivate future research for equivalent generative modeling.

2. Ablation of PPGN is necessary to demonstrate its effectiveness.

We have done an ablation study on the QM9 dataset. Please see the following table.

Interestingly, this indicates that PPGN is essential for diffusion with autoregression. As the transformer architecture is used in full-graph diffusion like DiGress, we hypothesize that it is less sensitive when using diffusion directly without any autoregression. Hence, we did another ablation by setting maximum hops $K_h=0$. At $K_h=0$, all nodes have a fixed degree of 1, resulting in a single block per graph, equivalent to full graph diffusion (only) without autoregression.

The above result confirms that performance is not much sensitive to architecture when no autoregression is employed.

3. For experimental settings of GDSS, NSPDK is also an important metric for QM9 and ZINC250K.

We apologize for unintentionally missing the NSPDK metric. We now implemented the NSPDK metric, and computed it for QM9 and ZINC250K. Notice that we do not have the number for baselines in QM9 dataset, as we use the harder QM9 setting considering explicit hydrogens, which is introduced in DiGress. For reference, SwinGNN achieves 2.01e-4 NSPDK for a simpler setting without hydrogens. We will update the table in the final version to include the NSPDK metric.

4. Is there a reasonable explanation for the significant improvement of FCD on ZINC250K compared to other baselines? Similarly, why is there such a large difference in performance between Scaf. and baseline methods on MOSES?

Our method's superior performance on these metrics can be attributed to the synergistic combination of autoregressive (AR) and diffusion models, which allows us to better capture the underlying molecular distribution. For both ZINC250K and MOSES datasets, we used the standardized evaluation code provided in the MOSES repository to compute FCD and Scaf. metrics, ensuring consistency with baseline methods. We are confident in the reproducibility of our results and can provide model checkpoints.

However, we are not very familiar with some molecule-specific metric like Scaf. We acknowledge a deeper understanding of molecule-specific metrics like Scaf. would be beneficial. Future collaboration with domain experts in molecular science could provide valuable insights into these performance differences and help refine our approach further.

We hope we have addressed your concerns and questions, and thank you again for your detailed feedback. If you feel more confident with these additional ablations and explanations, please help us in achieving a better score. Thank you.

Thank you for your questions. We have conducted extensive new ablation studies. We want to show that our analysis/motivation is not just a fancy story, but indeed the primary driver behind performance.

1. Lack of justification: it is less clear about the advantage of designing a complex autoregressive model to satisfy the permutation-invariant property.

The reviewer questions why we introduce an autoregressive (AR) approach to a diffusion model, given that the default diffusion model already captures the permutation-invariant property. In DiGress, we observed that full-graph diffusion, while permutation-invariant, requires (1) many sampling/denoising steps to break symmetry and (2) additional features like eigenvectors to further break symmetry. This shows that directly capturing the FULL joint distribution and solving the transformation difficulty (in Sec. 3.3) via diffusion is challenging. Additionally, AR methods still dominate LLMs, indicating their potential to benefit diffusion models. As stated in the abstract, this paper aims to combine the strengths of both approaches: AR’s training and inference efficiency and diffusion’s data efficiency through permutation-invariance.

To verify our analysis quantitatively, we conduct an ablation study on the maximum hops $K_h$, which controls the degree of autoregression. At $K_h=0$, all nodes have a fixed degree of 1, resulting in a single block per graph, equivalent to full graph diffusion (only) without autoregression. Increasing $K_h$ produces more blocks with smaller average block size, indicating more AR steps.

This ablation study maintains 140 total diffusion steps across all trials, using the same model architecture, diffusion algorithm, and training settings. The significant improvement from $K_h=0$ to $K_h=1$ confirms that our enhancement stems from breaking the full joint distribution into several conditional distributions, effectively combining diffusion and AR approaches.

2. The likelihood calculation is more accurate with Chen[9]’s approach than a predetermined order. How does the work justify its advantage over such an approach?

The reviewer is concerned that the predefined partial order is not optimal, given that Chen[9] shows that a learned order can be better than a predefined node order like BFS and DFS. We want to clarify that we are not arguing that our predefined partial order is optimal, instead, we claim that partial order should be used to replace the absolute order in an autoregressive approach as it is fully deterministic and a canonical partial order can be easily defined, which is the cornerstone of the permutation-invariant property we achieved. On the contrary, the absolute node order contains randomness (as finding a canonical node order is as hard as solving a graph isomorphism test), cannot achieve permutation invariance and hence is data inefficient. Our experiments comparing with many AR methods already verified this.

Nevertheless, our predefined partial order may not be optimal. In future, a reasonable follow-up work could be to learn a task-dependent partial order based on graph structures, e.g. one can consider the variational approach in Chen[9]. We look forward to seeing better partial order(s) being discovered.

3. The analysis in 3.3 is well known, and it is not a concern for generative models, as the sampling process will break the symmetry.

The analysis in 3.3 is indeed known in the link prediction setting, but this is the first time being mentioned for graph generation. If you know some paper has mentioned it in generation, we are happy to add references.

Indeed, sampling breaks the symmetry and makes the transformation achievable in certain conditions. We have clearly stated this in Sec. 3.4, which motivates us to use diffusion for capturing block conditional distribution. Nevertheless, as sampling is the only way to help symmetry breaking, lots of sampling steps are needed for a symmetry-intense setting. Splitting a FULL joint distribution to several conditional distributions simplifies it, with each conditional distribution containing less symmetry, which is easier to capture. Hence we show not only a significant improvement in generation quality, but also a great reduction in sampling steps.

When $K_h=0$, more diffusion steps breaks symmetries more, thus one may argue that we just need to increase diffusion steps. Thus, we conduct an additional ablation for steps when $K_h=0$. As shown, there is still a large gap to Diffusion+AR.

4. Pard seems to have a long inference running time.

In diffusion, inference time depends on (1) total number of diffusion steps and (2) resource usage per step. Pard outperforms full-graph diffusion in both aspects:

1. Pard uses 1/4 steps (140 vs. 500) and significantly outperforms DiGress.
2. DiGress denoises the whole graph at each step, while Pard only denoises the next block (significantly smaller) with less resource per step.
3. Pard, with its AR mechanism, allows previously generated blocks to be cached, accelerating inference similar to KV cache in LLM inference.

We hope these ablations showcase the advantage of Pard and the intrinsic source of the performance improvement clearly. We are happy to address any concerns and hope you can consider reevaluating our work.

Thank you for the timely response. For your additional two questions:

1. Yes, each block only takes 1/20 of DiGress iterations. Please see the first ablation study table, you will find the 'Diffusion steps per block' indicates the number of steps we used for each block. Total diffusion steps = num of blocks * diffusion steps per block.

2. Yes, all generated blocks are fixed, and are used to be conditioned on to generate the next block. The noise and randomness is only introduced in the target block. In Section 4.2, we leverage this property to enable parallel training of all blocks, similar to how next-token predictions in LLM training are parallelized.

Please let us know for any further questions!

We realized that you may also have another question: the parallel version of our algorithm shares representations across blocks, hence the earlier generated blocks provided less information to the future block as their representation cannot be updated. Actually, we have fully described the answer to this question in our original paper's section 4.2: why we want to design a parallel version of our algorithm.

Initially, our algorithm is not parallel at all: representations are not shared across steps, and each step uses its own graph representation to gain the best performance. Nevertheless, we realized that this approach has a huge suffer in training time: assume that you have K blocks in total, you get roughly K times more training time than the DiGress as you have K times more input graphs by viewing each conditional step's input graph as an individual graph. We solve the training time issue with our proposed nontrivial, novel and critical parallel training algorithm, such that all steps share the same blocks representation. Notice that this is an extremely important design: the advantage of causal transformer over RNN is the ability to parallel train all next-token predictions. And of course, you get less information from the previous tokens for the future token predictions: that's why Bert is preferred for document embedding instead of decoder-only GPT. Nevertheless, given the efficiency of GPT for capturing the whole distribution and parallel training, it is still the dominant approach of LLM, and the problem you mentioned does not block its effectiveness.

We suggest the reviewer to take a look at the section 4.2 for the detailed designs and explanations.

Dear Reviewer adow, We hope this message finds you well.

As the discussion deadline is rapidly approaching (in approximately 10 hours), we are reaching out to respectfully request your final feedback on our rebuttal. You provided the lowest score with soundness 1 (poor) and contribution 2 in the category of "technical flaws, weak evaluation, inadequate reproducibility, or incompletely addressed ethical considerations." We greatly appreciate the thorough review and the numerous questions you raised, as they have helped us improve our work.

In response, we have diligently addressed all of your questions in detail in many rounds, providing extensive ablation studies to support our claims and clarify any potential misunderstandings. We believe this additional information directly addresses the concerns that led to the low score. Given the significance of your evaluation and the substantial effort we've put into addressing your queries, we kindly request that you review our responses and provide your updated assessment. Your feedback is crucial for a fair evaluation of our work and will greatly assist the area chair in making an informed decision.

We understand that time constraints can be challenging, but we would be incredibly grateful if you could take a moment to review our rebuttal and adjust your feedback accordingly. Your expertise and insights are invaluable to this process, and we look forward to your response.Thank you for your time and consideration. We appreciate your dedication to maintaining the high standards of our field.

Thank you for giving positive feedback to our paper, we would like to further answer your question in detail.

Provide some insights about the hyperparameter the maximum of hops $K_h$

Let us first lay out $K_h$'s impact on the model: There is a relation between $K_h$ and block-size (hence the number of autoregression steps). As $K_h$ increases, the "weighted degree" of nodes diversify more with fewer equivalences, which induces a partial order with smaller blocks (i.e. fewer number of nodes and edges inside each block). Thus, the larger the hops $K_h$ is, the larger is the number of blocks and hence the number of autoregression steps.

Originally, we did not do ablation on the maximum hops during our experiments. We have an intuition that there would be a tradeoff, such that the smaller the block size, the easier it would be to learn within block diffusion, but the harder the autoregressive (AR) generation of the next block would be due to the exposure bias and the consequent error propagation of AR methods (If a block is mistakenly predicted during inference, the error will be propagated and the future blocks conditioned on this one will be impacted---this is true for all AR methods like LLMs). As the maximum hops essentially controls the combination ratios of diffusion model and autoregressive approach, we would like to choose it to make the number blocks to be 3 to 5 times smaller than the total number of nodes (such that each block has 3 to 5 number of nodes on average). Hence, for all molecular graphs, we set $K_h=3$. For all non-molecular graphs, we set $K_h=1$, as this provides a reasonable number of blocks based on our intuition.

Nevertheless, we would also like to formally and quantitatively answer the influence of $K_h$. Hence we have conducted an ablation study on the QM9 dataset, changing $K_h$ from 0 to 4. Notice that when $K_h=0$, all nodes have a fixed degree 1, hence it only provides a single block, which is equivalent to full graph diffusion (only) without any autoregressive approach. As $K_h$, block size (count) tends to decrease (increase) and we have a diffusion-AR hybrid as proposed.

As you can see from this ablation on $K_h$, we have found:

1. Combining autoregressive and diffusion works significantly better than diffusion-only ($K_h$=0) approach.
2. The performance seems to be robust with respect to the maximum hops (at least in range 1-4).

We hope that we have fully addressed your concerns, and we are looking forward to your further input and your support of the paper in score.