Generating Graphs via Spectral Diffusion

We are sorry the reviewer feels that our work is incremental wrt DiGress and GSDM. As explained above, our work shares little with the mentioned works, except (1) the idea of using denoising diffusion models (or its SDE variant) for generation and (2) approaching the problem from the graph spectrum perspective. These two research areas are too broad to consider any work falling in their intersection just a trivial combination of the two. Moreover, considering the important limitations of previous spectral-based work for graph generation (discussed at length in the paper and in this rebuttal), not only there is still ample room for contribution in this research direction, but efforts (like the present work) to investigate this direction are clearly needed. As such, it's hard to see how our contribution fails to be novel.

In particular, we had to overcome the non-trivial problem of designing a score model architecture capable of handling both eigenvectors and eigenvalues in a principled way while avoiding the quadratic complexity and extracting an adjacency matrix from the Laplacian reconstructed from the truncated basis. Moreover, we show that our method is actually able to preserve the partial spectral characteristics of the eigenvectors/values used for conditioning, a major strength of our method compared with existing literature. This required the design of a novel approach and wouldn’t have been possible with just minor/incremental improvements of previous methods.

We would be happy to answer to any further comment on this aspect.

We thank the reviewer for the observations and trust that our responses to the points raised help clarify any doubts or concerns.

"Though combining DDPM and graph spectral decomposition is new to me, there are already works that use DDPM to generate graphs (e.g., DiGress) and works that use SDE diffusion on graph spectrum (e.g., GSDM). In my opinion, this paper is experimenting with a different combination of diffusion approach and signal domain, which can produce useful results but lacks significant novelty."

Our methodology adopts an approach completely different from DiGress and GSDM (which we previously referred to as “FAST” in the original manuscript), and the only part in common is the use of a denoising diffusion framework for generation. In particular, DiGress operates diffusion directly on the nxn adjacency matrix, with the drawback of introducing quadratic computational complexity in the iterative generation process. On the other hand, GSDM proposes to reduce the complexity by performing diffusion on the eigenvalues (not the eigenvectors), and possibly node features, while the eigenvectors for reconstructing the final adjacency matrix are uniformly sampled from the training set. While this strategy allows to speed-up the generation, it actually requires to store the training set as part of the model and limits the generative power of the methods since most of the information about the graph connectivity is contained on the eigenvectors, which are sampled from the training set. As such, the obtained graphs are not actually generated but rather slight modifications of the training set graphs, resulting in a novelty score of just 28% in the Planar dataset, where most of the methods obtain 100% novelty. From an application point of view, our method is the only one that allows consistent conditioning on both eigenvectors and eigenvalues.

"The model uses the graph eigendecomposition and performs diffusion on the eigenvectors and eigenvalues. However, it is well-known that eigendecomposition (of Laplacian) is highly unstable. I think the authors should theoretically address this issue."

It has become some sort of true-ism in spectral graph theory to state that the Laplacian is unstable, but we think that this has to be qualified a bit more as several spectral approaches have shown to be robust even under severe deformation. We have added a further section in the supplementary material (Appendix G) to discuss this from a theoretical point of view in more detail.

"Is it possible for the diffusion process to generate eigenvectors and eigenvalues that cannot be obtained from the eigendecomposition of any graph?"

Yes, this is actually an intended outcome of our approach. The diffusion process is designed to generate eigenvectors and eigenvalues that may not correspond to the eigendecomposition of any existing graph, allowing for the creation of novel structures.

"Using a part of the spectrum has the advantage of reducing complexity. However, information is lost. What is the balance between these two factors? Is it true that most of the high-frequency components are not important?"

"For some datasets (e.g., QM9), the proposed method does not seem to show a clear advantage with a few performance metrics, even though the entire graph spectrum is used. One may gain more insights if the authors can also show the results when a partial graph spectrum is used."

"How to choose k? Is there a principled approach?"

We used the entire graph spectrum for QM9 because graphs are small, making the use of a smaller k unnecessary. Nevertheless, we explored the difference between the use of the entire spectrum and a part of it in the community dataset, which is composed of graphs with 12-20 nodes. The results in Table 3 show that, in the case of smaller graphs, it is beneficial to use the full spectrum to reconstruct the adjacency matrix. On the other hand, analyzing the results in Figure 7, we can see that considering a larger number of eigenvectors does not always lead to better performance. In particular, when increasing the eigenvectors, the generative diffusion model struggles to generate significant eigenvectors leading to a decrease in performance. This may be due to the added estimated variance that comes with the increase in dimensionality of the estimation problem. Thus, the trade-off is not just about computational time, but also a classic bias-variance trade-off. For example, we experimentally observed that beyond 16/32 eigenvalues, the noise of the generated eigenvectors increases significantly, which impacts the quality of the generated graphs. This informed our choice of k in the experiments (as also discussed in Appendix D).

We thank the reviewer for the comments. We hope our answers below clarify all doubts and concerns raised in the review.

"Experimentally, some key metrics are missing for synthetic datasets, namely the VUN for the planar and for the SBM dataset. I also have some concerns about the VUN metrics for QM9 since the uniqueness does not seem to be very high while the novelty is outstanding. Both metrics do not overlap totally but reflect the diversity of generation from different perspectives. Would the codes be released later (till my review the given anonymous repo is empty) for checking this technically?"

We verified using multiple devices that the code is indeed available/accessible in the repository (https://anonymous.4open.science/r/grasp-D237/), as it was since the submission deadline. We are not sure where the issue may be.

We are running new experiments to compute the VUN metrics on the synthetic datasets. We will add a further comment with the results as soon as they are available and we will include them in the revised paper.

As for the VUN metrics on QM9, we observe that a few small (not novel) molecules tend to be easily generated, which lowers the uniqueness score of our method. Since the novelty is computed only on unique molecules (i.e., duplicated molecules will be considered just once), this does not affect the novelty score much.

"The introduction / related work emphasizes a lot on traditional graph generation - which may not be the most critical or related work here. More background for the spectra-based method (SPECTRE is included but it would help if there are discussions with more relevant works) can help to clarify the storyline. Generally, the writing/clarity should be improved. Another branch of method that may be related to GRASP is the 'latent diffusion' for graphs - where people may encode a graph to node features, and, different from GRASP, they may denoise based on those learned features and reconstruct the graph based on it. This method in terms of structure is very similar, and the comparison of using learned graph features, and using spectral information directly is an interesting question to check or mention in the writing."

We revised the manuscript by expanding our discussion about what we believe to be the two most relevant spectrum-based graph generative models (i.e., SPECTRE and GSDM) to better highlight the contribution of our method. We would be happy to discuss more methods if the reviewer has specific inputs to other relevant work.

Following your suggestion, we have revised the manuscript by adding a brief discussion on two recent latent diffusion methods for graphs, i.e., “Graphusion: Latent Diffusion for Graph Generation” and “Unifying Generation and Prediction on Graphs with Latent Graph Diffusion”. Indeed, eigenvectors can be seen as a node embedding into a lower dimensional latent space, with eigenvalues bringing in global structure information, allowing to draw a parallelism between our method and these related work.

We thank the reviewer for the positive feedback and insightful suggestions, which helped us better frame our work in comparison to other spectral methods.

"Q1: From my understanding, the authors replace the GAN module in the pipeline of SPECTRE with the diffusion model. Therefore, it would be better to highlight the difference of the two methods. For example in section 6.4, is there any explanation why GRASP works better in preserving the network community when conditional on the spectral than SPECTRE, since both methods are based on spectral decomposition? In addition, in SPECTRE it was mentioned that conditional on the spectra the performance (section 5.1 therein) can be boosted. How is the performance of GRASP in terms of MMD compared to SPECTRE?"

While both our approach and SPECTRE leverage the graph spectrum, there are significant differences between the two, which are not limited to the replacement of the GAN module.

SPECTRE focuses on the generation of the adjacency matrix, conditioned on a set of eigenvectors (which may or may not have been generated themselves). Our experiments show that, while this conditioning improves the metrics of the generated graphs, it does not guarantee that these spectral conditioning properties themselves are present in the generated graphs (Figure 3, Figure 5, and Table 4). Our method instead directly generates eigenpairs (not an adjacency matrix) using a specifically designed backbone neural network. This is a significant contribution and a major difference from SPECTRE. As a result, our method is capable of generating graphs that respect the given spectral properties (i.e., the eigenvectors of the generated graphs are similar to those used to condition the generation).

We have revised the text to make this important distinction clearer.

The subpar performance of SPECTRE in preserving the network community structure may be due to its particular generation mechanism. Specifically, SPECTRE learns some reduced orthogonal bases during training, which are left and right-rotated according to a rotation matrix generated by a PointNetST network based on some input (generated) eigenvalues. This requires an alignment of the graphs to the learned bases, which makes the training more complex. Our approach, on the other hand, is fully covariant.

We have revised the text to stress this point.

The performance of SPECTRE and our method in terms of MMD metrics is reported in Tables 1 & 2. As shown in the tables, our performance is comparable to that of SPECTRE while at the same time better preserving the spectral properties (as discussed above).

"Q2: For methods based on spectral decomposition, it is key to choose the number of non-zero eigenvalues k. I noticed that in SPECTRE relatively smaller k such as 2 and 4 can achieve good performance, while for GRASP large k's are needed. Specifically, for the dataset, QM9 SPECTRE only used k=2, while GRASP used all the eigenvalues. How is the performance of GRASP compared to that of SPECTRE when the number of non-zero eigenvalues is the same? How will the number of non-zero eigenvalues affect the computational time?"

As discussed above, the two approaches are fundamentally different. While, in principle, SPECTRE can generate a graph even without spectral information, our method directly generates eigenvectors and eigenvalues from which the adjacency matrix can be recovered. As such, we require a larger number of eigenvectors to obtain a good initial reconstruction. However, note that the computational complexity of our model is linear wrt the number of eigenvectors considered (k).

"Q3: Could other fast sampling algorithms of diffusion models such as DEIS, DPM-Solver++, UniPC, and so on be leveraged to improve the quality or speed of GRASP?"

Indeed our approach is based on DDPM, so any of these faster sampling algorithms could be used, likely improving the speed of GRASP. However, we are somewhat doubtful about their impact on the quality of the generated graphs, which would require further investigation.

"Q4: Figure 8 is a bit confusing. The first two graphs in the right panel seem to be the same. Some explanations may help the readers to understand why k=12 for the community and k=64 for the SBM are compared."

The graphs in the community dataset have between 12 and 20 nodes, which led us to set k=12 for this dataset. For SBM, values beyond k=64 appear to lead to a degradation in performance, as can be seen from the trend shown in Figure 7. We have revised the text to make this clearer.

"Q5. For Figure 7, it is unclear what the authors mean by ‘average errors’. In the caption, it is said that Degree, Cluster, and Spectral metrics are calculated."

We have revised the caption of Figure 7 to clarify the meaning of ‘average errors’.

We thank the reviewer for the constructive remarks. Here below, we answer the questions raised in the review.

"Experimental validations in Section 6 are correct albeit limited due to a small number of datasets. For real-world datasets, it would be good to have examples which are not only related to molecules. Currently, the applications seem too specific."

We agree that expanding the pool of real-world datasets beyond molecules and proteins would make the work more complete. We plan to include datasets such as Reddit or IMDB to explore broader applications, however, we are unsure if the experiments will be completed by the end of the rebuttal period. Finally, we note that the datasets we considered are those that are commonly used by competing methods, and thus we focus on them to ensure a fair and robust comparison.

"The baselines used are ok, yet many results are not computed anew and taken from the published articles. Given the modest number of examples, and the small number of baselines (6 at most), the authors could have tried to re-implement all of them for better control of the reproducibility of the baselines and comparison to the present work."

We retrained all the baseline models using the code provided by the authors of the corresponding papers, with the exception of the QM9 dataset, where the results were taken from the original publications (as specified in the caption of Table 2). This is due to the fact that QM9, unlike the other datasets, also contains edge features, with some of the methods not providing the code to train on this dataset. By using the results reported in the literature (for QM9), we were able to still provide a fair comparison.

"Performance is decent, yet not far above (or not above in some cases) the competitors. Some more lines should be devoted to understand why that, and what works better in some other works for some cases."

We have indeed observed that the performance of our approach appears to be lower on planar graphs. Note that one issue with this dataset is that there is no clear class structure but rather the graphs in the dataset are related by a (hard) global graph property. In this context, similar spectra can lie on opposite sides of the discrimination boundary, e.g., between planar and non-planar graphs. As such, the addition/removal of an edge can easily break the planarity of the graph without significantly affecting its spectral representation. We have revised the text of the manuscript accordingly.

Consider for example a planar graph containing a subgraph composed of 5 nodes connected by 9 edges. Adding the missing connection (10th) between these 5 nodes will make this subgraph a 5-clique, thus rendering the whole graph non-planar. Yet, this is clearly a local transformation that does not affect the spectrum of the graph significantly (see Appendix G in the revised manuscript).

We are glad the reviewer enjoyed reading our work. Below, we respond to the concerns highlighted in the review.

"I did not find this paper to suffer from any glaring weaknesses, but I do have one concern about the idea of using a small portion of the spectrum to reconstruct the entire graph structure. As pointed out, different parts of the spectrum correspond to different aspects of the graph structure, that is, local vs. global features. Of course, this is remarked upon as a limitation by the authors, but I would appreciate some more discussion on the sorts of graphs that can be generated in light of this. Suppose we have a family of graphs that statistically vary in both their global and local properties, in a way where those properties (global vs. local) do not have strong correlations. I would imagine that such a family of graphs could not be captured by merely choosing to restrict generation to the lowest or highest set of eigenpairs. I suspect that this concern points to a deeper question about spectral graph theory than is within the scope of this paper, but I would still be interested to hear from the authors what sorts of graphs they expect the proposed method is able to capture. For instance, SBMs are largely characterized by their global structure, where the local connections follow an Erdos-Renyi pattern -- thus, it makes sense to generate such graphs by focusing on the lower spectrum. On the other hand, expander graphs are known to be very sparse, while also exhibiting certain properties that are global in nature -- such as being well-connected in some sense. It would be helpful to have some experiments to see if such a class of graphs could be generated by the proposed method."

Thank you for the positive feedback on our work. For future work, we are exploring methods for automatically selecting eigenvalues, aiming to dynamically adapt the spectrum used based on the dataset characteristics. Regarding the suggestion about expander graphs, it is currently out of scope for this work, but the idea is indeed interesting, and we will look into it in the future.

"I would be interested to hear the authors' response to my main point in the weaknesses section: what sorts of graphs do you think the method, as it is presented in the paper, would have a hard time generating?"

Our experimental results suggest that planar graphs appear to be more challenging for our approach. Note that one issue with this dataset is that there is no clear class structure but rather the graphs in the dataset are related by a (hard) global graph property. In this context, similar spectra can lie on opposite sides of the discrimination boundary, e.g., between planar and non-planar graphs. As such, the addition/removal of an edge can easily break the planarity of the graph without significantly affecting its spectral representation. We have revised the text of the manuscript accordingly.

Consider for example a planar graph containing a subgraph composed of 5 nodes connected by 9 edges. Adding the missing connection (10th) between these 5 nodes will make this subgraph a 5-clique, thus rendering the whole graph non-planar. Yet, this is clearly a local transformation that does not affect the spectrum of the graph significantly (see Appendix G in the revised manuscript).