A Simple and Scalable Representation for Graph Generation

Dear reviewer aPij,

We sincerely appreciate your comments and efforts in reviewing our paper. We think our paper has much improved in terms of clarity and rigorous evaluation, thanks to your comment. We especially found your comment W3 to be critical to correct our unclear description of the computational environment!

We address your question as follows. We also updated our manuscript which is highlighted in $\color{red}{\text{red}}$.

---

W1. There is a problem in Appendix C.1 Table 11 (b) Large graphs (|V|max ≤ 187).

Thank you for pointing out the typo. We fixed this to $399 \leq |V|_{\max} \leq 5037$ in our manuscript.

---

W2. Provide the novelty and uniqueness rates achieved by GEEL in the molecular generation experiments.

Thank you for pointing out additional metrics for molecular graph generation. We provide the novelty and uniqueness in the following table and updated the performance of molecular graph generation in our manuscript. One can observe that our GEEL shows competitive novelty and uniqueness compared to the baselines. We updated Table 16 in Appendix F of our manuscript.

We note that the models make a tradeoff between the quality (e.g., NSPDK and FCD) and novelty of the generated graph since the graph generative models that faithfully learn the distribution put a high likelihood on the training dataset. In particular, the tradeoff is more significant in QM9 due to the large dataset size (134k) compared to the relatively small search space (molecular graphs with only up to nine heavy atoms). We also note that one can compensate for the non-unique and non-novel molecules by filtering them out and generating new molecules.

---

W3. It is hard to claim that GEEL outperforms BiGG. In Table 1, the performance is close. In terms of speed, BiGG runs on GeForce GTX 1080 Ti while GEEL runs on GeForce RTX 3090, which makes Table 2’s result unfair.

Thank you for pointing out the unclarity. We conducted the inference time analysis in Table 2 on the same computational environment (GTX 1080 Ti) for all the models including GEEL and BiGG. We have clarified this in our updated manuscript in Appendix B.3.

Hence, one can safely conclude that GEEL is faster than BiGG. Furthermore, we claim that GEEL slightly outperforms BiGG in Table 1 since GEEL is marked bold for 20 out of 24 metrics in Table 1, while BiGG is marked bold for 14 out of 24 metrics. As mentioned in Section 4.1, we mark the numbers in bold if it is comparable to the metrics of the training graphs.

---

Q1. If this paper includes some ablation study of replacing the intra- and inter-edge gap encoding with traditional encodings, it will be better. Table 6 could include more experiment results. The parameter size can be adjusted to avoid Out-Of-Memory.

The ablation study of replacing the intra- and inter-edge gap with traditional encodings (i.e., original edge list) is in Table 6. The edge list (second row) indicates the traditional encodings and the edge list + intra gap (third row) indicates employing only intra-edge gap. We updated our manuscript to clarify what each row in Table 6 means.

Notably, the traditional encoding encounters out-of-memory in our computational environment even after adjusting the parameters or even setting the batch size to 1. This supports the superiority of our GEEL, concerning the memory requirement.

I have read the responses from the authors. I maintain my rating. The responses only addressed some of my concerns.

BTW, it should be "Related Work", instead of "Related Works".

Thank you for acknowledging our response and the efforts to review our paper.

We would be grateful if you could let us know your unresolved concern. The concern might be something we could resolve easily, e.g., miscommunication during the rebuttal phase. It would also help us improve our work.

We were unsure of what you meant by it should be "Related Work", instead of "Related Work"., but we changed our "Related Works" to "Related Work" section. Please let us know if we wrongly interpreted your comment.

Dear reviewer RDfu,

We sincerely appreciate your comments and efforts in reviewing our paper. We address your question as follows. We also updated our manuscript which is highlighted in $\color{red}{\text{red}}$. We think our paper has much improved in terms of clarity and rigorous evaluation, thanks to your comment.

---

W1/Q1. It is not clear how many graphs were generated for evaluation.

Thank you for pointing out the unclarity. Following prior works [1, 2], we generated graphs with the same number of test graphs. We updated our manuscript to clarify this in Section 4.1.

---

W2/Q2. Results on uniqueness and novelty metrics seem to be missing.

Thank you for such an insightful comment! Following your suggestion, we evaluated the validity, novelty, and uniqueness of GEEL and the considered baselines. We report the new results in Table 15 and Table 16 of Appendix F. We think our empirical results are now much more comprehensive and reliable, thanks to your review.

In our new experiments, GEEL achieves the 30% ~ 90% novelty, which is better than autoregressive models like GRAN and BiGG, but lower than the diffusion-based graph generative models as the reviewer anticipated. This is partially due to the inherent trade-off between novelty and the capability of generative models to faithfully learn the data distribution. Even diffusion models suffer from this trade-off, e.g., DiGress achieves 30% novelty for the QM9 dataset. We also note that this trade-off is less severe for harder problems, e.g., point cloud and ZINC250k, which is the main target of our work.

Finally, we note the minor modification of GEEL in the new experiments. Our GEEL now samples a new C-M ordering for a graph at each training step (instead of fixing a unique ordering per graph). We found this to improve novelty without a decrease in performance and changing the architecture. We updated all of our experimental results to incorporate this change. Note that the results for the Ego dataset are to be updated, as the experiments have not yet been completed.

---

W3/Q3-1. Could the authors clarify how scalability results are computed?

We conducted inference time analysis by setting the batch size to 10 and dividing the total inference time by 10 to compute the generation time for a single graph. Therefore, the reported inference time is not an outlier that shows the time for a single graph generation. We updated our manuscript to clarify this in Appendix B.

Q3-2. Since GraphGen works at the edge list level, I would expect the authors to compare with GraphGen in Table 6.

To incorporate your suggestion, we will add a comparison with GraphGen in our future manuscript. Please understand that we are unable to provide the result during the rebuttal phase. Unfortunately, we currently do not have the computational environment (GeForce GTX 1080 Ti) used for Table 6, which is necessary for a fair comparison.

References [1] Jo, J., et al., Score-based generative modeling of graphs via the system of stochastic differential equations. ICML 2022.

[2] Martinkus, K., et al., SPECTRE: Spectral conditioning helps to overcome the expressivity limits of one-shot graph generators. ICML 2022.

I thank the authors for the detailed feedback and rebuttal.

1. I am happy the authors added additional results on novelty and uniqueness. The metrics don't seem to be very good. So does that mean, they are replicating training data and not generating diverse samples?

2. I appreciate the authors for clarifying the novelty w.r.t BWR baseline of ICML 2023.

3. I don't see any comparison with BWR baseline for any tables in the appendix and Tab 2 and 4 in main paper. Is there any specific reason?

Can the authors clearly justify the gains their method has against BWR( in terms of quality and scalability demonstrating on multiple datasets under ) to make the manuscript more clear.

I am not sure if the manuscript is ready for publication yet. If the authors can better clarify things, it would be better.

I am changing my score to weak accept for now.

def evaluate_temperature(
        self, temp: float, real_graphs: list[nx.Graph],
        max_graph_len: int,
    ) -> dict[str, float]:
        samples = self.sample(len(real_graphs), steps=max_graph_len, temperature=temp)
        bf = BandFlatten(self.bw)
        sampled_graphs = []
        for sample in samples:
            sampled_no_start_token = sample[1:]
            stop_idx = sampled_no_start_token[:, 0].argmax()
            sampled_clean = sampled_no_start_token[:stop_idx, 1:].cpu()
            try:
                graph = graph_from_bandflat(sampled_clean, bf)
            except ValueError:
                continue
            sampled_graphs.append(graph)

def smiles_to_nx_no_features(sm: str) -> nx.Graph:
    mol = Chem.MolFromSmiles(sm)
    adj = Chem.GetAdjacencyMatrix(mol)
    return nx.from_numpy_matrix(adj)


def get_zinc_graphs(
    zinc_path: str = os.path.join(DATASET_PATH, "zinc.tab"),
) -> list[nx.Graph]:
    zinc = pd.read_csv(zinc_path)
    zinc_graphs = list(map(smiles_to_nx_no_features, zinc["smiles"].values))
    return zinc_graphs

I thank the authors for the clarifications. Most of my concerns have been resolved.

I keep my score to 6 and would recommend acceptance of the paper for their interesting ideas Overall it's a good paper :).

Dear reviewer EmZF,

We sincerely appreciate your comments and efforts in reviewing our paper. We think our paper has much improved in terms of comprehensive evaluation and clarity, thanks to your comment. We especially found your comment W1 very insightful!

We address your question as follows. We also updated our manuscript which is highlighted in $\color{red}{\text{red}}$.

---

W1/Q1. The novelty, uniqueness, and validity of the generated examples are not reported.

Thank you for such an insightful comment! Following your suggestion, we evaluated the validity, novelty, and uniqueness of GEEL and the considered baselines. We report the new results in Table 15 and Table 16 of Appendix F. We think our empirical results are now much more comprehensive and reliable, thanks to your review.

In our new experiments, GEEL achieves around 30% ~ 90% novelty, which is better than autoregressive models like GRAN and BiGG, but lower than the diffusion-based graph generative models as the reviewer anticipated. This is partially due to the inherent trade-off between novelty and the capability of generative models to faithfully learn the data distribution. Even diffusion models suffer from this trade-off, e.g., DiGress achieves around 30% novelty for the QM9 dataset. We also note that this trade-off is less severe for harder problems, e.g., point cloud and ZINC250k, which is the main target of our work.

Finally, we note the minor modification of GEEL in the new experiments. Our GEEL now samples a new C-M ordering for a graph at each training step (instead of fixing a unique ordering per graph). We found this to improve novelty without a decrease in performance and changing the architecture. We updated all of our experimental results to incorporate this change. Note that the results for the Ego dataset are to be updated, as the experiments have not yet been completed.

---

W2. A recent paper (SwinGNN) showed quite some improvements in the one-shot graph generators by using a known ordering.

Thank you for the suggestion. We provide the comparison below and in our updated manuscript.

Note that SwinGNN does not provide any novelty or uniqueness, hence it is unclear whether if SwinGNN bypasses the overfitting issue. For the considered metrics, both GEEL and SwinGNN showed high graph generation quality.

Additionally, we clarify that the usage of C-M ordering for autoregressive graph generation is first proposed by BwR [1], not by us. To avoid confusion, we updated our manuscript to clarify this.

[1] Diamant et al., Improving Graph Generation by Restricting Graph Bandwidth, ICML 2023.

Dear reviewer kVSU,

We sincerely appreciate your comments and efforts in reviewing our paper. We think our paper has much improved in terms of clarity and positioning our work, thanks to your comment.

We address your question as follows. We also updated our manuscript which is highlighted in $\color{red}{\text{red}}$.

---

W1. The work is perhaps not well-suited for ICLR since it does not include any learning representations.

Thank you for checking this. We would like to point out that ICLR 2024 mentions "generative models" as one of the relevant topics in its call for papers (https://iclr.cc/Conferences/2024/CallForPapers). Hence we believe our work (graph generative model) aligns with the context of ICLR.

We also provide a few examples of similar works in previous ICLRs:

• Shi, C., et al., GraphAF: a Flow-based Autoregressive Model for Molecular Graph Generation, ICLR 2020.
• Liu, M., et al., GraphEBM: Molecular Graph Generation with Energy-Based Models, ICLR 2021.
• Vignac, C., et al., DiGress: Discrete Denoising diffusion for graph generation, ICLR 2023.

---

W2-1. It is not mentioned that GEEL cannot generate graphs with unseen tokens, since it is a vocabulary-based approach.

We agree with your comment and mentioned this in our updated manuscript in Appendix G. Nonetheless, we believe the generalization capability of our GEEL is strong enough in practice. In all the experiments, we verified that our vocabulary obtained from the training dataset entirely captures the vocabulary required for generating graphs in the test dataset.

W2-2. It is not mentioned that GEEL depends on the bandwidth $B$, which can be $≈N$ for outliers.

We agree with your comment and mentioned this in our updated manuscript in Appendix G. As you mentioned, one could bypass this issue by removing the outlier graph or even removing the particular edge that increases the bandwidth. One also could consider (a) decomposing the graph into subgraphs with small bandwidth and (b) separately generating the subgraphs using GEEL. This would be an interesting future avenue of research.

Finally, as the reviewer mentioned, we would like to re-emphasize how the case $N\approx B$ is quite rare in practice.

---

Q1. What do the asterisks placed after Graphgen and Graphgen-redux in Table 1 mean?

Thank you for pointing out this typo. The asterisks indicated edge list-based graph generative models, but we deleted them since they are not very informative. We instead mention that Graphgen and Graphgen-redux are edge list-based graph generation methods in Section 4.

---

Q2. What is meant by "comparable" MMD? Which criteria is used to define two MMDs comparable?

The comparability of MMD values is determined by examining whether the MMD falls within a range of one standard deviation (reported in Table 11 of Appendix C.1). This was explained in the evaluation protocol in Section 4.1, but we also added this to the caption of Table 1 to further be more clear.

---

Q3. In Figure 4, what is the value of the c1 and c2 constants? Have they been explicitly calculated?

The constants $c_1$ and $c_2$ in Figure 4 are 0.5 and 2, respectively. We added the lines for visual alignment between the inference time and the theoretical computational complexity $O(M)$, where $M$ is the number of edges. We tried a few values to select the visually plausible constants.

---

Q4. What are the novelty and uniqueness rates achieved by GEEL in the molecular generation experiments?

Thank you for pointing out additional metrics for molecular graph generation. We provide the novelty and uniqueness in the following table and updated the performance of molecular graph generation in our manuscript. We can observe that our GEEL shows competitive novelty and uniqueness compared to the baselines. We reported the new results in Table 16 of Appendix F.

We note that the models make a tradeoff between the quality (e.g., NSPDK and FCD) and novelty of the generated graph since the graph generative models that faithfully learn the distribution put a high likelihood on the training dataset. In particular, the tradeoff is more significant in QM9 due to the large dataset size (134k) compared to the relatively small search space (molecular graphs with only up to nine heavy atoms). We also note that one can compensate for the non-unique and non-novel molecules by filtering them out and generating new molecules.

Thank you for the comments and for expressing your concern about our work. We are very disappointed and sorry to hear that our work does not put proper attribution on BwR, despite referring to it in the related work section. We sincerely hope to fix this issue regardless of the evaluation of our work.

Incorporating your concerns, we would like to clarify our contribution as follows: Our work proposes a new edge list representation with the vocabulary size of $B^2$ with gap encoding. We promote reducing the bandwidth $B$ using the C-M ordering, as proposed by BwR. Please note that our primary contribution, i.e., the gap encoding edge list, is orthogonal to BwR, since one could also consider the BFS ordering (used by GraphRNN) to reduce the vocabulary size $B^2$.

Importantly, most of the concerns seem to arise from our initial conception that BwR is about restricting the bandwidth for "reduction of the adjacency matrix representation for graph generation", hence not directly related to our edge list representation. This was partly due to the BwR description being focused on the adjacency matrix-based graph generative models. Now we would like to incorporate your viewpoint that "BwR is about constraining any graph generative model via the C-M node ordering".

To alleviate your concern, we revised the paper to fully attribute to your work whenever we use the C-M ordering. Our main updates (marked in $\color{magenta}{\text{magenta}}$) are as follows:

• Instead of promoting the bandwidth restriction via C-M ordering, we promote the bandwidth restriction via BwR.
• We updated Table 1 and 2 to incorporate all the BwR baselines.
• We will soon update other missing experiments that you pointed out.

In what follows, we reply to your comments one by one.

0. Most of the supplementary code for bandwidth ordering relies on BwR open-source repository.

Please note that we already included references to the public repository of BwR in our supplementary code. To make this more clear, we additionally added the code references in Appendix B.4. in the updated manuscript. If you are uncomfortable with this, we would be happy to implement our own C-M ordering algorithm.

1-1. "Applying bandwidth restriction" is mentioned as a key contribution without citation to our method, BwR.

We clarify that we mentioned that "BwR proposed to constrain the bandwidth via C-M ordering, bypassing the generation of out-of-bandwidth elements, which reduces the representation size to $NB$" in the second paragraph of Related works. Moreover, in our updated manuscript, we clarify that we fully attributed your BwR for reducing the maximum bandwidth using the C-M node ordering.

1-2. The first paragraph of page two reads, "We also promote the use of C-M ordering".

We clarified this to "We promote the use of C-M ordering as proposed by BwR".

1-3. Using a low bandwidth representation is listed as a key contribution, again without citation to our work. BwR did the same when applied to GraphRNN, resulting in asymptomatic runtime in O(NB) compared to GEEL's O(MB).

Using the gap-encoded edge list representation with vocabulary size (not representation size) bounded by the bandwidth is indeed our contribution. In our updated manuscript, we now refer to your work by stating that "Our representation further reduces the vocabulary size using the BwR scheme."

We also note that the number of iterations required for generating the representations is $M$ (not $O(MB)$) for GEEL while it is $NB$ for GraphRNN+BwR. The length of our representation is fixed regardless of the node ordering or the bandwidth.

1-4. The authors say, without citation, that "many real-world graphs exhibit low bandwidths as shown in Appendix C."

In our updated manuscript, we referred to your BwR on finding out real-world graphs have low bandwidth. Note that we do not claim to be the first to discover this fact.

2-1. The combination of bandwidth parameterization with an edge list-based representation proposed by GEEL appears to be an application of BwR to edge-list-based graph generation.

With all due respect, we disagree that GEEL is an application of BwR. While we now clarify that our C-M ordering stems from existing works including BwR in the updated manuscript, our new gap encoding (which is our main contribution) is not related to any concepts proposed by BwR. Our analysis of $B^2$ vocabulary size simply follows from the definition of graph bandwidth.

2-2. The authors should better clarify the novelty and main contribution of GEEL and its impact in isolation compared to previous edge list-based representations and in conjunction with BwR.

The main contribution of GEEL with respect to both edge list-representations is the gap-encoded edge list representation, of which the vocabulary size can be further reduced by the BwR scheme.

3. Lack of comparisons to prior work and opaque experiments.
   • Table 1 (generative performance) includes BwR without explaining which graph generative model BwR was applied to. BwR is a general framework to constrain the bandwidth of graph generative models that has been applied to autoregressive, VAE-based, and score-based methods in prior work [1]; it is not a model in itself.
   • This lack of explanation of how BwR was used is mirrored in the Appendix, which does not explain which generative model BwR was tested with. This means the results are not reproducible from the paper's text.
   • Table 1 (generative performance) has missing values for some model/dataset combinations (in particular, BwR). Additionally, Table 13 (additional experimental results) does not include BwR.
   • Table 2 (inference times) misleadingly leaves out BwR, which would be the natural comparison. For reference, Table 4 of Diamant et al. 2023 [1] shows how bandwidth restriction can improve inference time for nearly any graph generative modeling approach. The authors should consider quantifying the speed-up given by their proposed model without using BwR, and comparing it to the speed-up given by BwR.
   • The authors include an ablation study using different orderings (Section 4.3, Figure 5). However, these results only include training curves and not the impact on the generative performance (which would reflect the contribution of BwR to the method’s performance). The authors should consider separately evaluating their proposed model and the impact of adding BwR on top of it.

In conclusion, the authors designed GEEL by applying BwR to autoregressive edge-list generation, and used the BwR code to do so. The relevance of graph bandwidth and Cuthill-Mckee to molecular graphs was also an insight of Diamant et al. 2023. If the work were framed as focusing on the edge-gap encoding and applying BwR, we believe it would be a much more accurate representation of its novelty. In that case, the authors should separately introduce and evaluate the impact of the edge-gap encoding and potentially show synergies with the previously-introduced bandwidth parametrization. As is, the work claims many insights that are not its own.

We thank the reviewers for their time and consideration, Nathaniel Diamant, Alex M. Tseng, Kangway V. Chuang, Tommaso Biancalani, Gabriele Scalia

[1] Diamant et al., Improving Graph Generation by Restricting Graph Bandwidth, ICML 2023.