Sparse Training of Discrete Diffusion Models for Graph Generation

Dear reviewer,

Thank you for your thorough review of our paper and the valuable feedback provided. We highly appreciate your theoretical insights and have diligently addressed the mentioned typo errors.

To clarify the weaknesses mentioned in the reviews, we provide detailed responses to your comments below:

1. Regarding format issues: thank you for noticing the issues with citations, which have now been fixed. We are surprised by the mention of margin violations, as we followed the official latex package for ICLR2024.
2. Exchangeability: we thank the reviewer for this suggestion. Despite introducing some randomness in the model, SparseDiff is still an exchangeable method. The reason is that whenever we need to sample pairs, we do it uniformly on the set of all pairs so that it does not depend on one particular permutation. We will add a detailed proof in the Appendix. We are currently running experiments where we deliberately break exchangeability (as in SwinGNN) by introducing absolute positional encodings of the nodes. We will amend our current response and add the results in the Appendix when the experiments are complete, but it currently seems that breaking exchangeability tends to lead to overfitting on datasets with few graphs.
3. Definition clarification: Thank you for pointing this out. We have added a definition for the noise schedule.
4. Writing logic in the Method section: Thank you for your remark about the structure of the Method part. We took them into account in the revision of the manuscript, added the training algorithm, and improved the structure of this section.
5. Theoretical guarantee of the model: Establishing a solid theoretical foundation for discrete diffusion models on graphs is a challenging task. In addition to the challenges that are common to all denoising diffusion models, there are some challenges that are specific to graph generation. The biggest one is that graph neural networks (including graph Transformers) are not universal approximators of equivariant functions on graphs. As a result, even with infinite data, memory, and compute, it is not clear that standard denoising diffusion models for graphs can always recover the true data distribution. This is the case for SparseDiff as well, which explains why we only provide a limited theoretical analysis. We however believe that the experimental results are quite convincing and demonstrate the superior performance of SparseDiff.

We provide responses to your additional questions:

Continuous edge and node features We only treat discrete node features for the sake of simplicity. Continuous node features can be generated as well, except that they would use Gaussian noise rather than discrete diffusion. However, continuous edge features would be more challenging to handle, as they would require a continuous noise model that still maintains sparsity. This might be possible with truncated Gaussian distributions, but it is not a trivial extension.

Theoretical support for marginal transitions Two papers support the use of marginal transitions. In essence, they both build upon the idea that generation should be easier when the distribution of noisy graphs is close to the distribution of real graphs.

• Ingraham et al. 22, Appendix C.1: this section proves that, if $f(x) = x^T A x$ is a quadratic form that represents a property of data point x, then the expectation of $f(x_t)$ will be an interpolation of the expectation of $f(x_0)$ and $f(x_T)$. In the case of graphs, it implies that when marginal transitions are used, the noisy graphs at each time step have the same marginal distribution of node and edge types as the data.
• Vignac et al. 23, Theorem 4.1: DiGress indicates that marginal transitions can be seen as the product distribution that minimizes the l2 distance to the true data distribution.

Concerning distribution shift Thank you for pointing out this important aspect. We were careful to avoid distribution shifts in the design of SparseDiff:

• During training, the model randomly samples query edges from all node pairs and calculates loss for these query edges. As shown in Figure 2, query edges are uniformly sampled from all possible node pairs. Therefore, query edges can include both existing and non-existing edges.
• During sampling, query edges are sampled uniformly among all pairs as well. Some of these pairs will correspond to the noisy graphs, and some other pairs to the non-existing edges. The number of pairs that are sampled is the same as during training.

In both cases, the graph used for message-passing is the union of the query and noisy graphs, and this graph therefore has similar statistics during training and sampling.

Clarity of the paper Thank you very much for your suggestion. We do our best to include the algorithms in the main text within the page limit.

We appreciate your review of our work and look forward to better meeting the review requirements through revisions.

Dear Reviewer,

Thank you for your thorough review of our paper and the valuable feedback provided. We appreciate your insights and would like to offer clarification on some key issues:

Regarding the Incrementality of Contributions With SparseDiff, we purposely tried to design an algorithm that is very simple to understand, but that still matches the performance of the best scalable models. We believe that this is useful for future research, as SparseDiff’s simplicity makes it easier to combine with other ideas such as hierarchical generation. Your comments however helped us realize that we did not explain well the implementation challenges associated with our method. Things that look elementary such as sampling edges uniformly or adding noise turned out to be challenging to implement, due to the need to: i) avoid loops for computational efficiency; ii) respect the batching mechanism of PyTorch geometric, which does not use a extra batch size dimension in the tensors, and iii) handle graphs of varying sizes. We will add details regarding these challenges and the way we address them in the manuscript.

On the Theoretical Guarantee of SparseDiff Establishing a solid theoretical foundation for discrete diffusion models on graphs is a challenging task. In addition to the challenges that are common to all denoising diffusion models, there are some challenges that are specific to graph generation. The biggest one is that graph neural networks (including graph Transformers) are not universal approximators of equivariant functions on graphs. As a result, even with infinite data, memory, and compute, it is not clear that standard denoising diffusion models for graphs can always recover the true data distribution. This is the case for SparseDiff as well as for all other models, which explains why we only provide a limited theoretical analysis. We however believe that the experimental results are convincing in demonstrating the performance of the proposed model.

Empirical Study on Training Time Thank you for pointing out the analysis regarding efficiency. To better showcase SparseDiff's advantages over DiGress, we present results obtained from training on the large Ego dataset for varying durations. The ensuing table reveals that SparseDiff achieves significantly faster convergence than DiGress. Actually, SparseDiff achieved superior results compared to a DiGress model trained for 4 days, even after only 2 days of training.

Interpretation of Experimental Results Thank you for noticing the confusing part in experiments and we have diligently rectified the incorrectly bolded numbers. Regarding another concern that baselines for different datasets vary - this is because some results for some datasets are reported by certain baselines, making the baseline models inconsistent across datasets.

Scalability of the Model We selected Protein and Ego datasets, commonly used in scalable model references, to support our motivation. It's important to note that for these datasets, DiGress struggles to adopt even a very small batch size, making it even more challenging to converge effectively. As an additional result, we attempted training on the largest graph with 1045 nodes from the Facebook dataset and followed SaGess metrics for evaluation. Yet, employing the identical graph for both training and assessing test metrics holds potential risks. Achieving perfect metrics is possible through overfitting to this training graph. The table presents SaGess-RW's outcomes, the best-performing model among the proposed SaGess variants. SaGess forms small graphs, combining them to reach the desired edge count, while SparseDiff generates a single large graph based on the specified node count. Thus SparseDiff matches the 'num nodes' of the real graph, while SaGess approximates 'num edges' more closely. SparseDiff demonstrates scalability to 1000 nodes and excels in performance on single graph datasets, closely aligning with real data statistics, except for the clustering coefficient.

Thank you for reviewing our work. We look forward to meeting the requirements in the revised version.

Dear Reviewer,

Thank you for your thorough review of our paper and your positive feedback about our presentation. We have carefully considered your points and would like to provide clarification on some issues:

Comparison with DiGress

• We would like to clarify the potential confusion regarding the concept of sparsity discussed in both DiGress and our paper. In DiGress, sparsity is preserved throughout the diffusion, ensuring that the number of existing edges remains low compared to all node pairs. DiGress however uses a dense representation of graphs throughout training: it adds noise independently to each node pair, uses all pairs in the message-passing architecture, and computes a loss on all pairs as well. SparseDiff, while also preserving sparsity in noisy graphs, introduces 'computational sparsity' by reducing the noise model’s computational complexity from $O(n^2)$ to $O(m)$. As a result, it enables control over GPU usage that DiGress did not allow, which is key to scalability properties and good performance on large graphs.
• Besides, SparseDiff is much more than a simple adaptation of DiGress to a sparse library. The design of seemingly basic tasks, such as edge sampling and noise addition, presents significant challenges. These difficulties stem from the need to: i) optimize computational efficiency by avoiding loops; ii) align with PyTorch geometric's batching mechanism, lacking an extra batch size dimension in tensors; and iii) handle graphs of varying sizes. Our manuscript will provide detailed insights into these challenges and our strategies for overcoming them.

Comparison with GraphARM and SaGess Thank you for proposing those two works for comparison. SaGess and our paper both fall under the category of sparse models. However, SaGess conducts experiments using single-graph datasets such as Cora. We believe that using the same graph for training and measuring test metrics is potentially dangerous, as perfect metrics can be obtained by simply overfitting this training graph. GraphARM, while it is a very interesting method, the graphs on why it is benchmarked are unattributed and are not very large. We preferred to showcase performance on molecules and larger graphs, which is why it is not included in the comparison.

For improved comparisons, however, we conducted an additional experiment on the largest graph from the Facebook dataset used by SaGess, which consists of 1045 nodes and 27, 755 undirected edges. It's worth noting that employing the identical graph for both training and evaluating test metrics carries risks, as overfitting the training graph can lead to the attainment of perfect metrics. In the table below, we compare SparseDiff with SaGess-RW, the best model among the three proposed SaGess models. Specifically, SaGess generates small graphs and combines them to meet the specified number of edges, while SparseDiff creates a singular large graph based on the given node number. This explains SparseDiff's superiority in the 'num nodes' metric and SaGess's advantage in the 'num edges' metric. Furthermore, SparseDiff is closer to real data statistics, except for the clustering coefficient. This confirms SparseDiff scalability to 1000 nodes and shows its excellent performance on single graph datasets.

Beta Distribution Datasets In common larger graph datasets like Protein and Ego, the graph size variance is not significant, we thus did not specifically consider this scenario during training. On small graph datasets (QM9/Moses/Planar), SparseDiff consistently achieves comparable or even superior results to DiGress. This confirms that SparseDiff maintains excellent performance when training on small graphs. Thus, in this scenario, SparseDiff's performance in small graph generation should be not inferior to DiGress's from an empirical perspective. We are eager to learn more about examples of datasets with beta distribution, as it would enable us to conduct further experiments and validate this in the upcoming version of the paper.

Thank you for reviewing our work. We look forward to meeting the requirements in the revised version. If you have further clarifications or suggestions, please feel free to inform us.

In response to your specific questions, we provide the following answers:

Specific Usage of PNA and FiLM We appreciate very much your careful reading. In the revised version, we will provide a more detailed explanation to address any confusion regarding the model architecture and the FiLM and PNA layers.

• FiLM layer: We utilize FiLM to combine features at different scales. Specifically, given two features $M_1$ and $M_2$, and trainable parameters $W_1$ and $W_2$, the FiLM layer output is calculated as $M_1 W_1 + (M_1 W_2) \odot M_2 + M_2$. As an illustration, within the convolutional layer, the graph feature $M_2$ is integrated with edge features $M_1$ to enhance predictions.
• PNA layer: We use the PNA layer as a specialized pooling layer to obtain information from different dimensions of a specific feature. Given the feature $X$, $PNA(X) = {cat}({max}(X), min(X), mean(X), std(X)) W$. For example, node features $X$ are forwarded to a PNA layer for extracting global information across different scales, which is subsequently added to the graph feature to enhance its representation.
• Model architecture: Our model architecture follows a similar yet much lighter version of DiGress. Its Transformer layers use the message-passing attention mechanism, rather than dense attention as in DiGress. It incorporates FiLM layers to harness distinct levels of information. For instance, FiLM helps leverage global graph features into both node and edge features. Simultaneously, the PNA layer is employed to conduct pooling operations on node, edge, and graph features, respectively. Besides, the model has been lightened by its Transformer layers using the message-passing attention mechanism, rather than dense attention as in DiGress. More details can be found at: https://anonymous.4open.science/r/SparseDiff-B861/.

Updating the Edge List We first consider all n(n-1)/2 indices representing pairs of nodes and randomly permute them. We cut the resulting array into equal-sized chunks that represent the query graph at each iteration. We then iterate over these blocks, while keeping the noisy graph $G^t$ fixed. This is explicitly stated in the revised manuscript.

Performance Improvement of SparseDiff We agree that on small graphs, there should be no benefits of using sparse operations. We believe that the superior performance of SparseDiff over the version of DiGress with charges is due to small variations in the architecture (as explained above), but we were surprised by the results as well.

Ego Dataset Experiment Metrics We are very sorry for this mistaken information that we wrongly reported the SBM results instead of EDGE. The inaccuracies in this section have been corrected, and the revised results compared to SparseDiff are as follows.

Regarding the high result in Deg MMD, we were also surprised to observe that most methods performed poorly on this seemingly simple metric. As the reported results are from previous papers, we unfortunately do not have access to the degree distribution of the samples for the baselines, and cannot tell where the bad metrics come from.

Thank you for your review, and we look forward to meeting the requirements in the revised version. If you have further clarifications or suggestions, please inform us.

Dear Reviewer,

Thank you very much for your careful review of our paper and the valuable feedback. We have diligently addressed the typo errors you mentioned.

In response to the weaknesses identified in the paper, we would like to provide clarification to better address your concerns:

Contribution of the Model Your comments on the model contribution helped us realize that the challenging aspects of this work do not stand out well in the manuscript. We believe that the contribution is far from trivial, in the following aspects:

• While SparseDiff maintains a theoretical quadratic complexity, it presents a practical model that is not only straightforward to comprehend but also readily transferable, offering adaptability to diverse computing environments. The computational complexity of SparseDiff is on average $O(m+ \lambda n^2)$, as the model needs to process both the noisy graph and the query edges. By choosing $\lambda=O(m / n^2)$, it results in a $O(m)$ complexity as opposed to $O(n^2)$ for DiGress.

• SparseDiff is not only about porting DiGress to a sparse library so that it can use sparse computations. Things that look elementary such as sampling edges or adding noise turn out to be challenging to implement. This is due to the need to: i) avoid loops for computational efficiency; ii) respect the batching mechanism of PyTorch geometric, which does not use an extra batch size dimension in the tensors, and iii) handle graphs of varying sizes. We will add details regarding these challenges and the way we address them in the manuscript.

We are revising the text to clarify the challenges that are addressed as well as the contributions that are presented in our work.

Limitations of the Presentation Thank you very much for pointing out the issues in our presentation. In the revised version, we reorganized the paper structure to highlight better our contribution. This involves streamlining the introduction within the Method section and emphasizing the distinctions from DiGress, as well as a clearer description of the actual challenges in scaling up diffusion-based graph generation models.

Empirical Study on Sampling and Training Time We provide an empirical result here to better demonstrate the advantages of SparseDiff compared with DiGress. We report the result after being trained for different times with the Ego dataset. The following table demonstrates that SparseDiff converges much faster than DiGress on this large dataset. SparseDiff achieves superior results compared to a DiGress model trained for 4 days, even after only 2 days of training.

Finally, we acknowledge that our approach introduces higher time complexity during the sampling process. Our work focused on the ability to train denoising diffusion models without assuming specific characteristics of the data distribution, and we did not try the various techniques that exist to optimize sampling time.

Training on Larger Graphs We attempted training on the largest graph with 1045 nodes from the Facebook dataset, following the setting in SaGess. We also evaluated SparseDiff using SaGess metrics as a reference. However, using the same graph for both training and evaluating test metrics is potentially risky, as achieving perfect metrics can be accomplished through overfitting to this training graph. In the table below, we report SaGess-RW, which yields the best results among the three proposed SaGess models. For comparison, it is noteworthy that SaGess generates small graphs and concatenates them until reaching the required number of edges, whereas SparseDiff generates a single large graph based on the given node count. This accounts for the advantage of SparseDiff in the 'num nodes' metric and the advantage of SaGess in the 'num edges' metric. Additionally, SparseDiff aligns more closely with real data statistics, except for the clustering coefficient, which not only validates its scalability up to 1000 nodes but also underscores its high performance on such single-graph datasets.