Equivariant Denoisers Cannot Copy Graphs: Align Your Graph Diffusion Models

We thank the reviewer for the insightful questions. Answers in order:

Why using the aborbing state distribution and not the marginal distributions introduced in DiGress (Vignac et al., 2022) ? While the transition matrix is an important design choice for the performance of diffusion models, this choice is less relevant when studying the properties of an equivariant denoiser. The absorbing state model [1] is somewhat simpler than alternatives, and has been empirically found to outperform other transitions [1,2,3,4], making it a good testing ground for our theory. In our early experiments, we tested the uniform, marginal, and absorbing state transitions and did not notice substantial difference in performance. The absorbing state transition gave marginally better results which motivated our final choice. We will make this point clearer in the text.

Redundant statements like clearly, easy to see, etc We thank the reviewer for pointing this out. This prompted us to go through our manuscript to streamline the language and replace all occurrences of these words with more precise descriptions. We also went through many similarly redundant phrases, like "should be possible".

Do you mean that it's a prerequisite or that is implies that the model has the ability to peform "the modulations". We agree this sentence is confusing. What we meant to say is that for many graph translation tasks, such as retrosynthesis, the optimal denoising function is close to the identity denoising function, motivating the choice of copying as a toy model. We have changed the text accordingly.

Overall, I felt that this subsection [3.2] conveys very little information. We agree that the writing should be improved here, and have merged Section 3.2 with Section 3.3 and removed superfluous parts. The point in the text of Section 3.2 was to: 1) present the graph copying task as a theoretical tool to study the limitations of equivariant models, and 2) explain that graph copying is a real bottleneck in graph translation.

The proposed aligning methods are insufficiently motivated. We agree that a clearer exposition of the underlying motivations would strengthen the paper, and we have expanded this section in the revision. Our choice of alignment methods follows a principled progression, building upon established concepts in deep learning and graph neural networks:

• Graph positional encodings are a standard tool to break permutation symmetry in GNNs, prompting us to examine their use in inducing aligned permutation equivariance. This turns out to be possible using node-mapped positional encodings. This enables leveraging all the existing graph positional encoding methods for graph translation.
• The 'skip connection' denoiser is motivated by two insights: (a) its ability to represent identity data minimally through a single parameter λ, and (b) the well-documented success of residual connections across deep learning applications, suggesting their potential effectiveness in our domain.
• The input alignment is a natural next step from the 'skip connection' alignment. Instead of aligning the graphs at the output, what if we align them at the input? This way, the neural net representations corresponding to the target graph edges and nodes are directly given all of the information about the corresponding conditioning edges and nodes at the very beginning of the neural network.

It is likely that many other methods exist, and we believe that proposing some of the simplest approaches is a good starting point for future research to develop even more sophisticated methods.

Questions

Difference between $D_{\theta}$ and $\tilde{p}_{\theta}$: $D_{\theta}$ is the output of the neural network, which consists of vectors of probabilities corresponding to each component in the graph (node or edge). $D_{\theta}(X) = (D_{\theta}(X)^N, D_{\theta}(X)^E)$ is a tuple of matrices. $\tilde{p}_{\theta}$ is the probability of a single graph $X_0$ under our model, which is parameterized by the probabilities $D_{\theta}$. Since the probability of the graph factorizes over the nodes and edges independently, we can formally write the connection between $D_{\theta}$ and $\tilde{p}_{\theta}$ for a single graph as: $\tilde{p}_{\theta}(X_0|X_t) = \prod_i (D_{\theta}(X_t)_i^N)^T \cdot X_{0,i}^N * \prod_{i,j} (D_{\theta}(X_t)_{ij}^E)^T \cdot X^E_{0,i,j}$ where $D_{\theta}(X_t)_i^N$ is the probability vector for a single node $i$ (resp. for edge $(i,j)$), $X^N_{0,i}$ is a onehot-encoded vector representing the ground truth label for node $i$ (resp. for $X^E_{0,i,j}$ and edge $(i,j)$), and we denote the transpose of a matrix $M$ and $M^T$. We have included this clarification, and an explanation regarding the output space of $D_\theta$ (as suggested by reviewer Gt4F) in our main text when introducing $D_{\theta}$.

How is $\varphi$ generated? $\varphi$, $\varphi$ can be any vector of numbers as long at the vectors are distinct between pairs of mapped nodes, per the description in Section 3.5 paragraph "Node-mapped positional encodings". For our experiments, we specifically use Laplacian eigenvector-based positional encodings [5]. These vectors are obtained by taking the eigendecomposition of the graph Laplacian matrix, and using these eigenvector values as node features. We have included this information in the section "Methods for Alignment in GNNs".

How is Y passed to the denoiser? I feel it's not clearly outlined anywhere except in the section "Aligning Y in the input" Thank you for pointing this out. We pass the node feature matrix $Y^N$ by concatenating $Y^N$ to $X^N$ along the node dimension, creating a node matrix of size $(N_X+N_Y, K_a)$ ($K_a$ is the node feature dimension). Correspondingly, we form an edge tensor of size $(N_X+N_Y,N_X+N_Y,K_b)$, where the edges between the conditioning graph and target graph are zero, and the edges within the conditioning and target graphs are the original $Y^E$ and $X^E$. We considered this to be the simplest way to include the conditioning graph information without breaking permutation equivariance. We have now explained this in Section 5, "Permutation equivariant denoisers cannot learn the identity function".

I don't get how you build the dataset for retrosynthesis. If it is standard benchmark, could you please provide more explanations or point out to a reference We use the standard USPTO-50k benchmark [8]. We added the following description to our "Experimental Setup" paragraph:

"We use the benchmark dataset USPTO-50k for our experiments. The dataset consists of 50000 chemical reactions, in SMILES format [7], carefully curated by [3] from an original 2 million reactions extracted through text mining by [6]. More information on the benchmark dataset USPTO and its various subsets can be found in \cref{app:uspto-data}.""

References:

[1] Austin et al., "Structured Denoising Diffusion Models in Discrete State-Spaces", NeurIPS 2021

[2] Lou et al., "Discrete Diffusion Modeling by Estimating the Ratios of the Data Distribution", ICML 2024

[3] Sahoo et al., "Simple and Effective Masked Diffusion Language Models", NeurIPS 2024

[4] Shi et al., "Simplified and Generalized Masked Diffusion for Discrete Data", NeurIPS 2024

[5] Dwivedi et al., "Benchmarking Graph Neural Networks", JMLR

[6] Lowe et al., "Extraction of Chemical Structures and Reactions from the Literature"

[7] Weininger, David, "SMILES, a chemical language and information system."

[8] Schneider et al., "What’s what: The (nearly) definitive guide to reaction role assignment"

Thanks for writting a detailed rebuttal.

There are two points that I consider require further clarification :

• Absorbing transitions perform better than marginal : even though it is true that most discrete diffusion models employ absorbing transitions, most graph discrete diffusion models employ marginal transitions successfully. It does not surprise me that absorbing transitions work well, but I'd like to see an ablation if you have the experimental results at hand. It's not a big deal, but it would make your work more complete.

• Concerning Section 8 : it looks a lot like the DiGress' conditional generation method. In what way is it novel ?

Reiterating the mathematics from Appendix E. Below we reiterate the similarities and differences between the two methods for completeness. This is included in Appendix E. We use our own notation throughout but point to the equivalent results in DiGress where appropriate. A quick reminder that $X_{t}$ is the noisy input graph at step $t$, $Y$ is the condition graph, and $y$ is the property we are using to guide generation.

\newcommand{\X}{\mathbf{X}} \newcommand{\Y}{\mathbf{Y}} \newcommand{\P}{\mathbf{P}}

The similar part: We start by using Bayes' rule: p_\theta(\X_{t-1}| \X_t, \Y, y) \propto p_\theta(\X_{t-1}| \X_t, \Y) p(y | \X_{t-1}, \X_t, \Y) $$$$ = p_\theta(\X_{t-1} | \X_t, \Y) p(y \mid \X_{t-1}, \Y) where the second equality is due to $\X_t$ and $\X_{t-1}$ being independent (Markov property). By interpreting the probabilities as tensors in the same space as $\X_{t-1}$ and $\X_{t}$, taking the log and applying a first-order Taylor expansion of $p(y \mid \X_{t-1}, \Y)$ around $\X_t$, we get: \log \P_\theta(\X_{t-1}\mid\X_t, \Y, y) \propto \log\P_\theta(\X_{t-1}\mid\X_t, \Y) + \log \P(y \mid\X_{t-1}, \Y) $$$$ \approx \log\P_\theta(\X_{t-1}\mid\X_t, \Y) + \log \P(y \mid\X_{t}, \Y)+ \nabla_{\X_t} \log \P(y \mid\X_{t}, \Y)(\X_{t-1} - \X_t) In DiGress, this result is given as the first equation after Lemma 5.1, while you can see it in our work in Appendix E eq 103 to 108. From here on, DiGress uses classifier guidance to approximate $\P(y \mid\X_{t}, \Y)$, while we further derive this to a reconstruction guidance-like method to incorporate arbitrary guiding signals at inference time.

Classifier guidance (Digress): DiGress assumes $\P(y \mid\X_{t}, \Y) = \mathcal{N}(g_{n}(\X_t), \sigma_y I)$, where $g_n$ is a regressor estimating $y$ for a noisy graph $\X_{t}$. The gradients $\nabla_{\X_t'} \log \P(y \mid\X_{t}', \Y)|_{\X_t'=\X_t}$ can thus be computed using automatic differentation and the assumption of normality means we can replace the log with a squared difference (see Algorithm 3 in DiGress).

Reconstruction guidance (Us) The idea here is that we can compute $p(y\mid\X_t, \Y)$ directly if we have access to a property predictor $p(y\mid\X_0)$ from a clean graph. p(y\mid\X_t, \Y) = \sum_{\X_0} p(\X_0\mid\X_t, \Y) p(y\mid\X_0)$$$$\approx \sum_{\X_0} \tilde p_\theta(\X_0\mid\X_t, \Y) p(y\mid\X_0), Here $p(\X_0\mid\X_t, \Y)$ is the true, intractable distribution given by going through the entire sampling process and $\tilde p(\X_0\mid\X_t, \Y)$ is the factorized distribution that is given by the denoiser output, and 'jumps to' $X_0$ directly. This leads to the following update step:

$\log \P_\theta(\X_{t-1}\mid\X_t, \Y, y) \propto \nabla_{\X_t} \log \left(\sum_{\X_0} \tilde p_\theta(\X_0\mid\X_t, \Y)p(y\mid\X_0)\right)\X_{t-1} + \log\P_\theta(\X_{t-1}\mid\X_t, \Y).$

where we can bypass the sum over all possible $\X_0$ (i.e.,in the expectation) by sampling from $\tilde p_\theta(\X_0\mid\X_t, \Y)$ using the Gumbel-softmax trick, or by relaxing the definition of the likelihood to take a continuous vector $\tilde p_\theta(\X_0\mid\X_t, \Y)$ instead of a discrete value $\X_0$.

We thank again the help in improving the paper, and are open to further discussion.

References

[1] Chung et al. "Diffusion Posterior Sampling for General Noisy Inverse Problems." ICLR 2023

[2] Ho et al. "Video diffusion models." NeurIPS 2022

[3] Song et al. "Pseudoinverse-guided diffusion models for inverse problems." ICLR 2023

[4] Vignac, Clement, et al. "DiGress: Discrete Denoising diffusion for graph generation." ICLR 2023

[5] Sohl-Dickstein et al, "Deep unsupervised learning using nonequilibrium thermodynamics", ICML 2015

[6] Dhariwal and Nichol, "Diffusion Models Beat GANs on Image Synthesis", NeurIPS 2021

Thank you once again for your detailed feedback and for taking time to discuss our answers. This is a kind reminder that tomorrow is the last day reviewers can post replies on openreview. We would love to know if our answers so far have addressed your concerns and if there is anything else we can do to clarify matters further.

References

[1] Niu et al, "Permutation invariant graph generation via score-based generative modeling", AISTATS 2020

[2] Eijkelboom et al., "Variational Flow Matching for Graph Generation", NeurIPS 2024

[3] Lou et al., "Discrete Diffusion Modeling by Estimating the Ratios of the Data Distribution", ICML 2024

[4] Sahoo et al., "Simple and Effective Masked Diffusion Language Models", NeurIPS 2024

[5] Shi et al., "Simplified and Generalized Masked Diffusion for Discrete Data", NeurIPS 2024

[6] Shi et al., "A Graph to Graphs Framework for Retrosynthesis Prediction", ICML 2020

[7] Somnath et al., "Learning Graph Models for Retrosynthesis Prediction", NeurIPS 2021

[8] Liu et al. "MARS: a motif-based autoregressive model for retrosynthesis prediction." Bioinformatics, 2024

We thank the reviewer for the effort put in reading our manuscript and suggesting points for improvements. We would like to start highlighting the following points regarding the raised weaknesses (elaborated in more detail later):

• Our Theorem 1 is applicable to all standard discrete diffusion priors, including uniform and marginal (from Digress [1]). Further, it is not difficult to extend it to Gaussian diffusion models. We argue that the theoretical understanding is important, because it enabled us to propose new types of alignment that lead to improved results.
• We achieve significant improvements over Retrobridge. Retrobridge used a non-standard evaluation scheme, and the difference becomes larger with when adopting RetroBridge's evaluation scheme. Furthermore, our model achieves much better results with much less diffusion steps.
• We have now added numerical results for inpainting, showing that side information from a chemist interacting with the system can improve the accuracy significantly.

Detailed answers:

Alignment has been used previously..., Is the contribution limited to "why alignment is necessary for a discrete diffusion model with an absorbing-state prior"

As noted in Section 2, alignment has been used in a diffusion-like approach previously in the code of Retrobridge, which we noticed while preparing the first draft of our paper. This design choice was neither analysed nor explicitly discussed in the paper. In contrast, a main contribution of our work is the theoretical understanding of the problem and formalizing the solution through aligned equivariance. Understanding the core of the issue through the theory enabled us to propose new types of alignment methods that result in significant improvements over Retrobridge (see comparisons in next section). This showcases how the formalization of aligned equivariance is a useful conceptual tool in developing new models. Aside from Retrobridge, we are not aware of work that overlaps with our discussion of alignment for graph diffusion.

Further, our Theorem 1 applies to all standard discrete diffusion priors, not just the absorbing state diffusion. It would not be difficult to extend it to Gaussian diffusion models [1] as well or even flow matching [2], since the core insight is that the nodes in the noisy graph $X_T$ are in a symmetric position, and the equivariant denoiser is unable to break these symmetries.

"When compared to RetroBridge in the retrosynthesis task, it is difficult to find a significant performance gap between the proposed model and RetroBridge."

Although this was not as apparent from the initial submission, we do achieve a significant improvement over Retrobridge when following their evaluation scheme. Retrobridge was evaluated in a non-standard manner, where charges and stereochemistry were not taken into account when calculating the top-k scores, inflating the results and making a direct comparison difficult. We trained another model using the same training data as Retrobridge (not including charges), and conducted the evaluation in the same way. The results are in the following table:

Many recently published methods for retrosynthesis have capped out their top-1 scores in the 49%-53% range (see our Table 2), indicating that an increase of over 5% is quite significant. Furthermore, we achieve this with 5 times less denoising steps (100 instead of 500). For a closer look at the performance at different step counts, see also their Figure 5 compared to our Figure 5b, showing that Retrobridge top-1 score decreases to almost 0 at a step count of more than 10. In contrast, our top-1 is close to 50% even at 5 steps, and higher than Retrobridge at 100 steps. We attribute this improvement to our more careful analysis of alignment, and utilising multiple alignment techniques.

Numerical comparisons on inpainting. In order to quantify the benefits of inpainting, we conducted the following experiment: fix one of the reactants in multi-molecule reactant sets, and generate the other reactants based on the fixed reactant+product. This scenario corresponds to a chemist selecting one precursor (based on availability for example) and wanting to explore synthesis routes incorporating their choice. Below we report our results, which we also added to Appendix E.

Our best model reached a top-1 accuracy of 68.88 and an MRR of 0.753 with just 10 diffusion steps, showcasing the potential for high accuracy and speed in an interactive setup. Also note that we are able to achieve these results without a need to retrain a model specifically on this task, which most of the baselines we compare to are not able to do at all.

Questions

The paper assumes that the prior distribution is absorbing state. Does the proposed model still effective even on the uniform distribution prior? Yes, our model is effective with other priors. In fact, changing the prior distribution (or transition matrix), while an important design choice for diffusion models, is irrelevant to our study of the limitations of equivariant denoisers. In our early experiments, we tested the uniform, marginal, and absorbing state transitions, and noticed the marginal and absorbing state models to perform similarly while uniform was slightly worse. The absorbing state model is somewhat simpler and is the preferred choice in most modern discrete diffusion literature [3,4,5], motivating our choice. We have now made this point more clear at the end of the diffusion formulation section.

What happens if the node-mapping matrix has uncertainty and is not a binary matrix?

Our method requires node-mapping information to align the source and target graphs. While a complete and correct mapping matrix is ideal, the method is robust to noisy mappings up to a limit. Therefore, one way would be to convert a nonbinary mapping matrix to a binary one via argmax (or potentially even sampling) works for our purposes. To follow up on this, we performed a small toy experiment on the graph copying task and noisy node mappings, and added the results in Appendix G. For low levels of noise, results remain the same, but for a higher node mapping noise level, the performance can drop.

How does the performance compare when using only direct skip connections without positional encoding? We thank the reviewer for an interesting suggestion. We are currently training such a model and will try to get the results for the rebuttal period. Likely the results will not be as good since the skip connection does not add a lot of expressivity aside from the ability to copy graphs effectively. The positional encodings, on the other hand, are given as input to the neural network and as such may allow for more expressivity.

How does the performance differ from graph translation methods in Related Works, such as G2gt?

We list our top-k scores and mean reciprocal rank compared to the G2G [6] graph translation based retrosynthesis method below:

We outperform G2G by a clear margin across all top-k metrics. We have now also moved a full comparison to other methods as Table 2 in the main text. Other aspects to keep in mind when comparing against G2G is that

1. It is particularly designed for retrosynthesis, with a multi-stage procedure for identifying reaction centers, breaking the product into reactants and filling out missing parts with an autoregressive model
2. This approach inherently limits the model to chemical reactions where a reaction center exists. We added a figure Figure A11 in Appendix D demonstrating a type of reaction which cannot be handled by methods like G2G, but for which our model returns correct predictions. This also applies to other previous work such as [7] and [8].

Thank you once again for taking time to review our paper and provide valuable suggestions. This is a kind reminder that tomorrow is the last day reviewers can post replies on openreview. We would love to know if our answers so far have addressed your concerns and if there is anything else we can do to clarify matters further.

Questions

DPS, MRR These refer to the diffusion posterior sampling [1] guidance method and the mean reciprocal rank. We have added the descriptions in the text.

Do the authors need the node mapping matrix for this task? We need some kind of mapping information between the nodes in the input and output graphs. Such information is often available (such as the atom mapping information in chemical reaction modelling), or could be obtained with graph matching algorithms. We formally represent this information in the node mapping matrix to enable mathematical analysis and to allow us to define the concept of aligned equivariance. We expect alignment to be useful when the node mapping is informative of the structural similarities in the two graphs: If there is an edge between two mapped nodes in the initial graph, there should be a high probability of an edge between the corresponding nodes in the target graph.

Why do the authors present Theorem 1 for fixed t=T? Theorem 1 uses a fixed t to provide intuitive understanding and highlight the main issue of equivariant denoisers. Note that it does apply to other forward processes aside from the absorbing state transition as well, although it is easiest to see for the absorbing state diffusion. We extend the results to other t<T in Appendix A.6. for a simplified setup. We have revised the main text in Methods to clarify this point.

If the authors use P and Y as input into the denoiser, then these two terms already form the full information about X. In the identity data case, the conditioning graph $Y$ in itself already contains full information about the graph $X$, up to permutation. While this is restrictive, our aim in the section was to then argue the following:

• Although one could expect the task to be trivial even without node mapping, we show that a permutation equivariant diffusion model is unable to represent the graph-copying operation effectively.
• We then show that the class of aligned equivariant functions is able to represent the copying operation
• Importantly, it does not matter which $P^{Y\to X}$ matrix we use during sampling. We can choose a random mapping matrix, which will result in the model to output a correspondingly random permutation of the conditioning graph $Y$. Thus, the effect of $P^{Y\to X}$ is to break symmetries, not to provide additional information.

During training, however, we need actual mapping information so that the model will learn to associate structurally similar nodes from one graph to the other.

A more comprehensive explanation of "This makes it impossible for the model ... some random permutation of $Y$" An expanded version of the same comment goes as follows:

• Because the equivariant denoiser outputs a factorized marginal distribution of nodes and edges in the graph, sampling from it will result in a highly noisy graph where the edges and nodes are uncorrelated.
• However, with multiple steps, correlations can emerge. The extreme case is that if $T$ is very large, only a single dimension of $X$ will change at once. The factorized output distribution does not cause issues here, since we are only changing one dimension at a time, turning the model into an autoregressive model that generates the dimensions in a random order. This is very slow, however.

We have updated the description in the submission to be in line with this explanation, as we believe it is more precise. We are happy to answer any further concerns.

References

[1] Chung et al., "Diffusion Posterior Sampling for General Noisy Inverse Problems"

We thank the reviewer for taking the time to write a detailed review and for pointing out places where our text could be improved. Below we answer their questions, clarify minor misunderstandings, and implement the improvements they suggested.

Note that the reviewer mentions references [1] and [2] but their text is missing the corresponding citations. We deduced from the context the following references. Let us know if they are not correct.

[1] Vignac et al. "DiGress: Discrete Denoising diffusion for graph generation", ICLR 2023.

[2] Austin et al. "Structured Denoising Diffusion Models in Discrete State-Spaces", NeurIPS 2021.

Major concerns

...which parts are background and which are novel contributions? We do not claim any significant novelty in the discrete diffusion framework used, and agree that the discussion on diffusion models is better organised into a separate background section. The methods section now contains the novel contributions, including the theoretical analysis on limitations of equivariant denoisers, the concept of aligned permutation equivariance, and the methods for inducing aligned equivariance.

The output space of $D_{\theta}$ not matching with the one-hot encoding of $X^N$ and $X^E$ in $D_{\theta}= P^{Y \rightarrow X} Y$

We agree that a clarification is in place, and we have made the following changes to the presentation of the paper:

• Spaces of $X^N$ and $X^E$: We have now defined the node and edge vectors to be in the vertices of the probability simplex $\Delta^{K_a-1}$ and $\Delta^{K_b-1}$, where $K_a$ and $K_b$ are the amount of node and edge types, respectively. Formally, for the entire tensor $X^N\in$ (vert$(\Delta^{K_a-1}))^{N_X}$ and $X^E\in$ (vert$(\Delta^{K_b-1}))^{(N_X\times N_X)}$.
• The output space of $D_\theta(X,Y)=(D_\theta(X,Y)^N,D_\theta(X,Y)^E)$ is the probability simplex for each node and edge, that is, $D_\theta(X,Y)^N\in (\Delta^{K_a-1})^{N_X}$ and $D_\theta(X,Y)^E\in (\Delta^{K_b-1})^{(N_X\times N_X)}$.
• Thus, the output space of $D_\theta(X,Y)^N$ is a strict superset of the space of $X^N$, and the denoiser can output one-hot values as well. $D_\theta(X,Y)=P^{Y\to X}Y$ means that the denoiser outputs probability vectors that are entirely peaked at a specific permutation of $Y$, and the entropy of the distribution is zero. This would also mean that the denoiser has learned to copy the graph, up to a permutation.

We have now gone through the text and clarified the notation everywhere. We are happy to address any further comments on this point.

Minor concerns

why graph-to-graph translation is important in practical applications. We agree that more motivation would be helpful, and have now added a few sentences to the introduction to strengthen it. The new sentences are highlighted in teal. To summarise, application areas are molecular editing and property optimisation, chemical reaction modeling, and tasks in which the objective is to predict a future state of a graph.

Use of uncertain phrases We have now revised our text to replace all uncertain language with clear and concise descriptors. For instance:

• In Section 4.1: "a model that is capable of copying graphs from one side of the reaction to the other should also be extendable to modulations..."" -> we removed the sentence and gave a more descriptive motivation
• In Section 4.1: "while the copy-paste task should be solvable..." -> "The optimal unconstrained denoiser in this situation is always $D_\theta(X_t, Y) = P^{Y\to X}Y$"

Typos, and minor improvements We fixed the following typos and minor mistakes per the reviewer's request: Line 50, Figure 1, respectively taken out of line 217, bolding in line 244, DPS -> Diffusion Posterior Sampling, MMR in line 374 -> included a brief description of the metric earlier, changed the definition of retrosynthesis in line 374, swapped table a3 with figure 8.

Y on the left side of (2). Consequently, how does this density differ from (3)? Thank you for pointing out the missing $Y$. Eqs. (2) and (3) refer to the same density, but the point of (3) is to provide a method to calculate the single-step transition given a network that has been trained to predict $X_0$.

We thank the reviewer for the further clarifications. It seems that we are now getting towards a shared understanding in most questions, with perhaps room for some minor clarifications.

On the relation between (2) and (3). We now understand better what the reviewer meant in the previous message, and agree that a clarification is useful here. We have now added new Equations (4) and (5) in the text that clearly show the factorization over dimensions, mirroring equations (1) and (2).We list the new equations below:

$q\big(X_{t-1} \mid X_t, X_0 \big) = \prod_i^{N_X} q\big(X_{t-1}^{N,i} \mid X_t^{N,i}, X_0^{N,i} \big) \prod_{i,j}^{N_X} q\big(X_{t-1}^{E,i,j} \mid X_t^{E,i,j}, X_0^{E,i,j} \big)$

$\tilde p_{\theta}\big(X_0 \mid X_t, Y\big) = \prod_i^{N_X} \tilde p_{\theta}\big(X_0^{N,i} \mid X_t, Y\big) \prod_{i,j}^{N_X} \tilde p_{\theta}\big(X_0^{E,i,j} \mid X_t, Y\big)$

EDIT: It is unfortunately not possible to edit the paper at the moment, but we can add these two lines later for a camera-ready version. Of course, it does not make a significant difference for the main content of the paper.

No alignment and only Laplacian positional encodings. We are glad that the reviewer is happy with the additional experiments, but also better understand the remaining suggestion. We understood the intent of the question to be about what is the comparative effect of Laplacian PEs vs. alignment, but now realise that the intent is to understand whether Laplacian PEs without alignment can be useful. We can see a couple of ways to formalise this, but perhaps the following procedure is the most meaningful:

1. Create the Laplacian PE for $Y$ in the same manner as before.
2. Instead of copying the $Y$ positional encodings to $X$, we create new Laplacian PEs based on the noisy graph $X_t$. The caveat that this does not contain any structural information in the beginning of generation when the graph is in the absorbing state.

We are now trying to run this experiment, and will get back to you soon. We are sending this response now to leave more time for discussing the latter point.

Ignoring the $X_t$ input in the denoiser.

We thank the reviewer for the clarification. It seems that the miscommunication is easier to spot now. We list subquestions / comments that had the most tangible opportunities for clarification, and our answers to them below. Perhaps this resolves some of the issues? Let us know also if there is an additional experiment that you think would be useful to run regarding this.

• "How does the performance change when the authors keep $X_t=X_T$ during the training?"
  • In fact, this experiment is implicitly included in Figure 6b, which shows the top-k scores for different sampling step counts. In the case where of a single sampling step, the model only gets as input $X_T$ and $Y$ and $P^{Y\to X}$, and directly outputs the estimate of $X_0$. Although the model has technically been trained on other $t$ values as well, they are not used here and the model is mathematically equivalent to one that was trained solely on $X_t=X_T$ (assuming that the other $t$ do not interfere significantly with the training). The results are clearly worse, although it does perform better than the 100-step unaligned model.
• "This case of ignoring the noisy input while having full access to $X$ (directly or via the product of $P^{Y\rightarrow X}$ and $Y$) concerns me the most."
  • We would like to stress that the model never has full access to $X$, aside from the identity data experiment. As such, this scenario can not occur. It only has access to $Y$, which can significantly overlap with $X$, but not entirely.

Let us know if this sheds light on the matter.

We thank the reviewer for taking the time to review our work and for recognizing the value of our contribution. Below we address their concerns.

Justification for design choices. For studying the equivariance properties of the denoiser, the exact choice of the transition matrix does not matter. We initially focused on the absorbing state transitions due to prior empirical evidence of it performing better than alternatives [1,2], and being the transition of choice in many recent works [2,3,4]. We also noted in our earlier experiments that the marginal transition was similar or performed marginally worse than the absorbing state transition.

[...] the statement regarding the model's capability to handle graph transformations requires clearer elaboration. We have revised this sentence in our text (highlighted in teal). We have replaced it with

"The motivation is that for many graph translation tasks, such as retrosynthesis, the optimal denoising function is close to the identity denoising function due to the inductive bias of structural similarity between the graphs."

We believe that this reflects more accurately the reason why the identity data is a useful toy model.

The experimental validation, while promising, lacks sufficient quantitative comparisons to existing methods (e.g., RetroBridge). [...] Upon the request of reviewer Gt4F, we have moved Table A.3 comparing our method to other retrosynthetic baselines from Appendix A to the main text (now Section 9, Table 2). In addition, we included results highlighting our performance compared to RetroBridge [6] in particular, following their evaluation scheme (i.e. discarding formal charges and stereochemical information from the generated samples).

As seen from the table above, we outperform RetroBridge significantly on top-1 and MRR with considerably less denoising steps. Comparing our Figure 5.b to RetroBridge's Figure 5 also highlights that our results are barely affected by lowering the denoising steps, while RetroBridge's top-1 accuracy is close to 0 for steps < 10. These results and more comments are available in Appendix A, Table A.4.

References

[1] Austin et al., "Structured Denoising Diffusion Models in Discrete State-Spaces", NeurIPS 2021

[2] Lou et al., "Discrete Diffusion Modeling by Estimating the Ratios of the Data Distribution", ICML 2024

[3] Lou et al., "Discrete Diffusion Modeling by Estimating the Ratios of the Data Distribution", ICML 2024

[4] Sahoo et al., "Simple and Effective Masked Diffusion Language Models", NeurIPS 2024

[5] Shi et al., "Simplified and Generalized Masked Diffusion for Discrete Data", NeurIPS 2024

[6] Igashov et al., "RetroBridge: Modeling Retrosynthesis with Markov Bridges", ICLR 2024

Prompted by the discussion with reviewers Gt4F and gPTC, we did the following additional ablations:

1. Comparison of our absorbing-state model against different transition matrices (uniform and marginal)
2. Comparison of our absorbing-state skip connection + Laplacian PE model with a model that only uses the skip connection as an alignment method.
3. An ablation disentangling the effect of the inductive bias brought by using the graph positional encodings and the inductive bias of matching the positional encodings across the conditioning graph $Y$ and the output graph $X$. This is done by comparing a model with only Laplacian positional encodings as alignment to a model with random Gaussian vectors matched across $X$ and $Y$ as alignment.

For a fair and quick comparison, all of the models were evaluated at roughly 10% of the full training budget (80 epochs) and 512 samples from the test set.

The ablation on transition matrices shows that while the uniform transitions perform the least well and the absorbing transitions perform the best, all of them can work with a reasonable accuracy.

The ablation on using only the skip connection alignment method. Below, we see that the model with only the skip connections as alignment does not perform well, although it is better than the entirely unaligned model (4% top-1 in our Table 1). This is likely due to limited expressivity: the neural network does not get the alignment information at all as input in this case.

The ablation with the Gaussian positional encodings vs. Laplacian positional encodings (disentangling graph inductive biases from alignment). Below, we see that the difference of using the graph Laplacian positional encodings vs. matched Gaussian noise vectors as the positional encodings is not large in practice. This is evidence for the proposition that the alignment is the key inductive bias here, and the specific type of graph positional encoding is less important.

We would like to thank everyone for the discussion and the constructive suggestions on additional experiments. We believe it has significantly improved the paper.