Efficient and Scalable Graph Generation through Iterative Local Expansion

Thank you for the time and effort you have invested in reviewing our work. We appreciate your constructive feedback and have revised the manuscript in response to your comments. In the following, we would like address the concerns and questions you have raised.

Regarding weaknesses 1 and 2:

Thank you for highlighting these references. We have expanded the related work section of our manuscript to include a discussion on the following publications:

• Scalable Deep Generative Modeling for Sparse Graphs
• Improving Graph Generation by Restricting Graph Bandwidth
• GraphGen: A Scalable Approach to Domain-agnostic Labeled
• An Unpooling Layer for Graph Generation

For the first two papers listed, we have carried out experiments using our datasets under consideration and have included the findings in the updated manuscript. We recognize the value of conducting similar experiments for the last two papers mentioned and plan to incorporate these results into the final draft of our paper.

Regarding weakness 3:

Graph visualizations have been included in the supplementary material to demonstrate the quality of generation (Figures 7,8,9,10,11,12). As the MMD-based metrics correlate with our reported validity metrics, we have chosen to present only the latter for a more concise presentation.

Regarding weakness 4:

Protein and point cloud graphs represent real-world structures by encoding neighborhood information similar to molecular graphs. Therefore, we consider them to be non-synthetic datasets The reason we excluded molecular datasets from our evaluation is that they consist of smaller graphs with just a few dozen nodes, which do not align with our method's focus on efficiently generating larger graphs. We are optimistic that larger datasets with more nodes per graph will become available, providing further opportunities to evaluate our method on larger graphs.

Regarding question 1:

The validity metric is essential as it signifies whether the model has successfully captured the defining attributes of the target graph category. A low score in uniqueness and novelty can be indicative of overfitting, which is particularly important to consider since some models may display low MMD metrics, potentially giving a false impression of high performance. In reality, these models might be replicating the training dataset too closely, failing to generate new, valid structures, which is arguably the main task of generative models. Consequently, we emphasize the V.U.N. (Validity, Uniqueness, Novelty) metric to ensure that our model not only excels statistically but also produces graphs that are novel and characteristic of the intended class. We appreciate you bringing up this issue. To address this, we have included an explanatory note in the manuscript.

Thank you for your response and additional suggestions.

It is true that the performance of BiGG is slightly worse than the performance indicated in the original paper. We utilized the official implementation (https://github.com/google-research/google-research/tree/master/bigg), and for both the protein and point cloud datasets, we applied the same hyperparameters as those documented in the original study. The models were trained until the validation loss stabilized, after which we reported the performance based on the test set. For the final version of the paper we will test what happens when we train them longer. We used a different training split though, as described in the paper, which may explain the difference in performance Our method is slower than BiGG by a constant factor. The primary objective of the comparison was to demonstrate the asymptotic scaling behavior to support our theoretical analysis, wherein our method exhibits similarities to BiGG. As we aim to improve diffusion models, which provide state-of-the-art generation quality for smaller graphs, but have very poor asymptotics that prevents their use for larger graphs. We successfully remedy this.

It is indeed correct that the protein and point cloud datasets do not constitute attributed graphs. Our current methodology is not equipped to generate attributed graphs; rather, we focus solely on constructing the topological structure. We appreciate your suggestion to test our model on polymers. This would certainly be a valuable extension.

Thank you for your detailed review and constructive feedback. We appreciate your time and effort in evaluating our work.

We would like to address your concerns and questions in the following:

Regarding weakness 1:

In response to the difficulty in discerning the source of performance improvement due to multiple design choices, we have included further commentary in the main text to elucidate the significance of each design choice. To avoid misconceptions about the role of spectrum preservation, we will amend the title to "Iterative Local Expansion" in the camera-ready version (per ICLR guidelines). These changes aim to provide a clearer insight into the importance and contribution of individual design elements.

Regarding weaknesses 2 and 3 as well as questions 4 and 5:

Thank you for your attention to detail. Let us elaborate on the concerns mentioned, as this provides a good opportunity to clarify some aspects of our method and highlight its strengths.

Utilizing a fixed random coarsening sequence for each graph in the dataset indeed introduces sensitivity to the chosen ordering, which can lead to overfitting when the training set is small. Consequently, we adopted a strategy of sampling different coarsening sequences during model training. This is reflected in the formulation of our method, where importance sampling is employed instead of maximizing the likelihood of a single coarsening sequence, in contrast to other hierarchical graph generation approaches.

Although random coarsening can perform quite well, the spectrum-preserving coarsening proposed reduces the variability of the coarsening sequence and aids in increasing the convergence speed and generative performance.

As stated in the paper, we limited the maximum training time for all experiments to 48 hours. Typically, our method achieves faster convergence compared to baseline one-shot methods due to its efficiency.

Regarding the concern about convergence speed on larger datasets, we experimented by expanding the synthetic planar dataset tenfold and observed no substantial change in the loss convergence rate. However, the generative performance improved, with all generated graphs being valid planar graphs. This improvement is likely because the training data in this case provides better coverage of the ground-truth distribution.

The robust performance on small synthetic datasets underscores the promise of our method. This is particularly noteworthy because several autoregressive methods tend to overfit these datasets and fail to generate valid new graphs.

The reason we excluded molecular datasets from our evaluation is that they consist of smaller graphs with just a few dozen nodes, which do not align with our method's focus on efficiently generating larger graphs. We are optimistic that larger datasets with more nodes per graph will become available, providing further opportunities to evaluate our method on larger graphs.

Regarding weakness 4:

You are correct in your observation that the marginalization of the likelihood of a graph was incorrectly expressed. This has been corrected in the revised version. Thank you for pointing this out.

Regarding weakness 5:

Node expansion indeed depends on the preceding refinement step; that is, $\mathbf{v_l}$ is dependent on $\mathbf{e_l}$. However, as we model a joint distribution $p(\mathbf{v_l}, \mathbf{e_l} | \tilde{G}_l)$, this dependence is captured. The assumption we make is that $\mathbf{v_l}$ is conditionally independent of the expanded graph $\tilde{G}_l$ given the refined graph $G_l$.

Regarding weakness 6:

You are correct in your observation that the equality in the equation above (3) is essentially importance sampling and requires $q(\pi|G)>0$ when $p(\pi)>0$. In scenarios where a random cost function is employed during the sampling of coarsening sequences, it holds that the distribution $q$ supports all possible coarsening sequences. With a deterministic cost function, the introduction of the randomization parameter $\lambda$ within the "Randomized Greedy Min-Cost Partitioning" algorithm is intended to ensure a similar support for $q$. However, our primary focus is on employing the variational interpretation to derive a valid lower bound for training purposes rather than evaluating likelihoods. Therefore, to remain general and keep the paper simple, we replace the equality in the equation above (3) with an inequality. This makes our lower bound applicable even in the absence of full support from $q$. Consequently, we have not included a formal argument and refrain from asserting the use of importance sampling in our methodology.

Regarding question 1:

Your observation regarding the model's use of two iterative processes is accurate. For each refinement and expansion step, we sample corresponding expansion and refinement vectors using denoising diffusion, which is an iterative process. We have updated Section 3.3 on denoising diffusion in the main text to more explicitly point this out.

Regarding question 2:

You are correct in your observation that the marginalization of the likelihood of a graph was incorrectly expressed. Furthermore, you are correct that the first equation under the variational interpretation section should be an inequality rather than an equality. Both of these errors have been corrected in the revised version - thank you for pointing them out.

Regarding question 3

Our method supports any coarsening scheme that operates by contracting connected subgraphs.

Coarsening that preserves the Laplacian spectrum ensures that the resulting graphs share structural similarities with the original dataset graphs, which may ease the learning process. Our ablative studies indicate that such preservation can enhance model performance, when compared to random coarsening, albeit modestly. We invite further research to investigate alternative coarsening strategies within our framework.

Regarding question 4

Indeed, there are additional scenarios. Consider the expansion of a triangular graph into a fully connected four-node graph, followed by an edge removal (refinement) that results in a line graph. This refined graph cannot revert to the original triangular structure through coarsening by contracting any connected subgraph. Generally, expansion and refinement may not be reversible when the refinement step eliminates edges in such a way that nodes originating from the same parent node no longer share a common candidate contraction set.

Regarding question 5

The incorporation of randomness in the expansion process primarily serves to mitigate overfitting, which is particularly advantageous for synthetic datasets comprising only 128 training samples. We added a comment to the "Perturbed Expansion" section to clarify this point.

Regarding question 6

As documented in the paper, edge contractions were utilized for all experiments. This approach limits the graph's maximum expansion factor to 2, which in turn means that L is upper bounded by \log_2(n), where n represents the number of nodes in the graph. For the purpose of model training, coarsening sequences were constructed, with each step reducing the graph's size by a random fraction ranging from 10% to 30% (Details are provided in Algorithm 1). For instance, for the synthetic graphs of size 64, L ranges from 12 to 22.

Addressing your question about the scenario in which the initial node is directly expanded to the target graph using a one-shot approach: Our method employs the same denoising diffusion framework as "SwinGNN" by Yan et al. However, while they apply a non-permutation invariant transformer architecture to graph edges, we utilize the introduced Local PPGN model—which, in this case of a dense graph, would match the original PPGN model by Haggai et al.

Regarding question 7:

In the refinement step, we selectively remove some edges from the expanded graph $\tilde{G}$. To do this, we sample a refinement vector using denoising diffusion. This vector is represented as edge features of the expanded graph $\tilde{G}$, where each edge feature indicates whether the corresponding edge should be kept or removed during the refinement step. Consequently, noise is added to all edge features of the expanded graph during training.

Thank you for the time and effort you have invested in reviewing our work. We appreciate your constructive feedback and have revised the manuscript in response to your comments. In the following, we would like to address the concerns and questions you have raised.

Regarding weaknesseses 1 and 4:

We appreciate your attention to these references. We have revised our related work section to include a discussion of the cited publications, specifically addressing the following studies:

• Molgrow: A graph normalizing flow for hierarchical molecular generation
• HiGen: Hierarchical Graph Generative Networks
• Autoregressive diffusion model for graph generation
• Efficient and degree-guided graph generation via discrete diffusion modeling
• Td-gen: Graph generation using tree decomposition

For the work "Efficient and degree-guided graph generation via discrete diffusion modeling", we have conducted experiments on the considered datasets and report the results in the revised manuscript. We recognize the value of conducting additional experiments on the other mentioned works and plan to incorporate these in the final version of the paper. Note that following the suggestion of Reviewer 38QF, we also conducted experiments with two other methods: "Scalable Deep Generative Modeling for Sparse Graphs" and "Improving Graph Generation by Restricting Graph Bandwidth".

In terms of employing random GNNs for evaluation, we recognize its potential significance. However, due to time limitations, we are currently unable to expand our experimental evaluations to include this measure. Nevertheless, we believe that the structural properties captured by the random GNN metric would likely show a correlation with the MMD values we have reported.

Regarding weaknesses 2:

We recognize your concerns regarding the potential limitations of our method, which arise from keeping the number of eigenvalues $k$ constant during the expansion process. However, it appears there might be a misunderstanding about how our model operates and the role of spectral conditioning.

To clarify, our Local PPGN model functions across the entire graph rather than on isolated local subgraphs, enabling it to capture global structural characteristics. The term "local" indicates that the model resembles the PPGN model within local dense subgraphs, which results in enhanced discriminative power in these areas compared to message-passing models. The expressiveness of our GNN at the global scale is at least the same as usual message-passing models. Spectral conditioning is not crucial for capturing global structural attributes; rather, its aim is to enhance the model's performance by providing useful node embeddings. We have revised the "Spectral Conditioning" section to more clearly explain this aspect.

Regarding weaknesses 3:

In response to your comment regarding the absence of a comprehensive complexity analysis, we have incorporated a new section in Appendix H. We clearly outline the assumptions that allow for the achievement of subquadratic complexity in relation to the number of nodes. This section also includes a new chart that illustrates empirical sampling speeds, benchmarked against alternative methods.

Regarding weaknesses 5:

Thank you for your detailed suggestions. We have revised the manuscript to address the concerns you highlighted. In particular, we use "q" to denote the probability distribution over coarsening sequences, to avoid confusion with the model parameters.

The revised version avoids the term "autoregressive" to describe the method. Furthermore, it explicitly notes the Markov property assumption in the factorization of the joint distribution.

We have elucidated the representation of the expansion and refinement vectors $\mathbf{v}_l,\mathbf{e}_l$ as node and edge features, respectively, of the expanded graph $\tilde{G}_l$, in response to the query raised by reviewer mLXw. Consequently, we maintain that boldface notation for these vectors is appropriate and have chosen to retain it.

The symbol $\mathcal{F}(G)$ is exclusively used to denote the set of candidate contraction sets for a given graph $G$. While we recognize that this may not be the most conventional notation for contraction families, its meaning is unambiguous within the context provided.

We acknowledge that a considerable amount of methodological detail has been relegated to the appendix. Given the constraints of page limits, our intention was to succinctly present the core aspects of our methodology in the main text while offering comprehensive elaboration in the appendix.

Thank you for your detailed review and constructive feedback. Although our paper provides a high-level summary and visual aids, we understand that technical details can be difficult to follow. We hope that the reworked algorithms in the appendix will help clarify the method.

In response to your comments on local spectral preservation, we concur that it does not represent the primary focus of our work. As such, we will amend the title to "Iterative Local Expansion" in the camera-ready version (per ICLR guidelines), which more accurately encapsulates the essence of our method. While spectrum-preserving graph coarsening does contribute to the method's enhanced performance, it is not a critical component.

Furthermore, we have expanded the related work section to provide a clearer context within the current state-of-the-art landscape, thereby highlighting our contributions more effectively. We have also enriched the experimental section with additional comparisons to underscore the method's efficacy and impact.

In the following, we would like to give answers to your specific questions:

Regarding questions 1 and 3:

The expansion vector records the size of the expansion cluster for each node in the graph $\tilde{G_t}$, whereas the refinement vector specifies whether each edge of this graph should be kept or removed in the refinement step. Consequently, we represent these two vectors as node and edge features of the graph $\tilde{G_t}$. This is why we refer to them as features. We have clarified this in the text. Thank you for pointing this out.

Regarding question 2:

The marginalization of the likelihood of a graph has been corrected in the revised version. You are correct in your observation a graph is defined by an expansion sequence resulting in it. Thank you for raising this concern.

Regarding question 4:

We discretize the diffusion process into 256 steps. The second-order method employed necessitates two gradient evaluations per step, leading to a total of 512 model evaluations for each sample. Although this procedure multiplies the sampling time by a constant factor, it does not alter the asymptotic complexity. A comment stating this has been added to Section 3.3 in the revised manuscript.