Graph Generation with $K^2$-trees

Dear reviewer XLS2,

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}}$.

W1. Motivation is not strong enough.

To alleviate your concern, we first restate our motivation stated in our introduction (development of compact and hierarchical representation) and then strengthen it by providing the underlying idea (exploiting large zero-filled submatrices) that is more explicit.

The motivation stated in our introduction is the benefits of compact and hierarchical representation for graph generation. Compact representation reduces the complexity of graph generation and simplifies the search space over graphs. Hierarchical representation allows generating the graph in a coarse-to-fine way, which aligns with the hierarchical nature of real-world graphs.

Our idea beneath this motivation is to map the patterns (zero-filled blocks) being repeated across the whole dataset into simple objects (nodes in the $K^2$-tree) that the model can easily generate. This mapping removes the burden of the generative model to learn how to generate large patterns and allows the model to focus on learning instance-specific details.

We also note that our $K^2$-tree being hierarchical allows us to handle various patterns (zero-filled blocks with varying sizes) in a systematic way. Our $K^2$-tree being compact for a dataset implies that the patterns (zero-filled blocks) indeed frequently appear across the whole dataset.

We believe this idea is strong enough to drive our work since similar ideas showed success in different domains in different forms.

• Most of the successful language models [1] generate a sentence word-by-word instead of character-by-character. Here, the recurring patterns of characters are mapped into word tokens.
• Several successful molecular generative models [2, 3] also generate molecules fragment-by-fragment. Here, the recurring patterns of atoms and bonds are mapped into fragments.

W2. Related works are missing, such as GraphARM and degree-guided diffusion.

Thank you for pointing out the references. We added the references about GraphARM and the degree-guided diffusion model in our updated manuscript.

• GraphARM (ICML 2023) is a very recent work that improves over the existing diffusion models based on the forward and reverse diffusion process that iteratively masks and unmasks the graph elements in an autoregressive way.
• Degree-guided diffusion (ICML 2023) is also a very recent work that improves the scalability of the diffusion models for graph generation. It exploits graph sparsity based on adding edges between only a small portion of nodes at each graph construction (reverse diffusion) step.

W3. The paper doesn't detail the computational resources.

We used a single GeForce RTX 3090 GPU to train and generate samples with HGGT. This was detailed in Appendix E.1 in our original manuscript. We added the description to our main paper for better visibility in the updated manuscript.

W4. Tokenization can sometimes lead to loss of information, and without details, it's uncertain how this impacts the overall graph representation.

We would like to clarify that our tokenization does not lose any information. Our tokenization is a mapping from $K^2$ binary digits to a vocabulary of size 24 where one can perfectly reconstruct any $K^2$-tree after the tokenization process. We systematically designed our tokenization process so that there is no unknown token (<UNK>) that may lead to loss of information as the reviewer mentioned.

References

[1] Devlin, J., et al., BERT: Pre-training of deep bidirectional transformers for language understanding. Association for Computational Linguistics 2018.

[2] Jin, W., et al., Junction tree variational autoencoder for molecular graph generation. ICML 2018.

[3] Jin, W., et al., Hierarchical generation of molecular graphs using structural motifs. ICML 2020.

W5. There exists some mis-explanation for molecular evaluation metrics.

Thank you for pointing this out. Indeed, the validity and the uniqueness are computed with the generated samples themselves and the novelty is computed by comparing with the training set. We fixed our description in Section 5.2. of our updated manuscript.

Otherwise, following the MOSES benchmark [3], FCD and NSPDK are measured between the 10,000 generated samples and the test set. It is also notable that we followed other prior works on graph generative models [4, 5] that reported FCD between generated samples and test sets.

Q1. Why do you choose the $2^{K^2} + 2^{K(K+1)/2}$ vocabulary instead of $2^{K^2}$ which leads to the larger vocabulary size?

Our main insight is that the semantics of the diagonal blocks are different from non-diagonal blocks in the $K^2$-tree, as described in the fourth paragraph of Section 4.1. To incorporate this idea, we assign different vocabulary for the diagonal (size $2^{K(K+1)/2}$) and non-diagonal blocks (size $2^{K^{2}}$), resulting in a larger vocabulary size. In practice, we choose $K=2$ and the increase in vocabulary size ($2^{K(K+1)/2}=8$) is not significant.

References

[1] Barik, R., et al., Vertex reordering for real-world graphs and applications: An empirical evaluation. IISWC 2020.

[2] Mueller, C., et al., Sparse matrix reordering algorithms for cluster identification. Machine Learning in Bioinformatics 2004.

[3] Polykovskiy, D., et al., Molecular sets (MOSES): a benchmarking platform for molecular generation models. Frontiers in pharmacology 2020.

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

[5] Luo, T., et al., Fast graph generative model via spectral diffusion. arXiv preprint 2022.

W3. It is not clearly explained in the paper why the proposed model significantly outperforms the baselines. Previous models also came up with different schemes to reduce the time and space complexity.

Our main intuition on why HGGT outperforms the baselines is that only our HGGT maps the recurring patterns in the dataset (large zero-filled block matrices) into a simple object (a zero-valued node in the $K^2$-tree) that the model can easily generate. This mapping allows the generative model to focus on learning instance-specific details rather than the generation of the whole pattern that is common across the dataset. The baseline space and memory reduction techniques do not yield this benefit, e.g., GRAN and GraphRNN propose parallel decoding and constraining the search space, respectively.

In what follows, we make the one-to-one comparison between our scheme and the existing space and memory reduction schemes. Note that we do not claim HGGT to strictly improve over the baselines in a conceptual way. In fact, it is hard to make an apple-to-apple comparison between the reduction techniques since the ideas are orthogonal, e.g., the $K^2$-tree can be generated via parallel decoding (like GRAN) and made smaller by constraining the adjacency matrix (like GraphRNN).

Comparison with GRAN. As already discussed in W2, GRAN employs block-wise parallel decoding to reduce the number of decoding steps for generating the whole adjacency matrix. The parallel decoding does not reduce representation size and the search space, hence lowering the performance for faster generation.

Comparison with GraphRNN. While GraphRNN also reduces the representation size (and alleviates the long-range dependency problem), our reduction is higher.

To be specific, GraphRNN limits the search space for adjacency matrices by constraining the "upper-corner" elements of the adjacency matrix to be consecutively zero, based on the maximum size of the BFS queue. See Figure 15 in Appendix H for an illustration.

In comparison, while our HGGT does not put constraints on the graphs being generated, both HGGT and GraphRNN reduce the representation size; this removes the burden of the graph generative models learning long-range dependencies. Empirically, our reduction is higher as shown in the below table that reports the average length of representations for the Community, Planar, Enzymes, and Grid datasets. Note that the representation size of HGGT and GraphRNN indicates the number of tokens and the number of elements limited by the maximum size of the BFS queue, respectively. While the comparison is not fair due to different vocabulary sizes, one could expect HGGT to suffer less from the long-range dependency problem due to the shorter representation.

This is incorporated in Appendix H of our updated manuscript.

W4. Why is the result on QM9 not very good, especially for Novelty? Does it indicate the inferiority of HGGT on novel graph generation?

We first note that graph generative models that faithfully learn the training dataset are more likely to assign high likelihoods on the training dataset, hence the trade-off between the quality and the novelty of graph generation is inevitable. This trade-off is especially significant for the QM9 dataset since it consists of a large number of molecules (134k) despite the small search space (molecules with up to only nine heavy atoms). Indeed, no baseline has successfully avoided this trade-off in the QM9 dataset, e.g., Digress achieves a good FCD at the cost of low novelty in Table 2. We chose to achieve high scores for faithfully learning the underlying distribution (FCD and NSPDK) since we consider them to be more meaningful as evidence for high-quality molecule generation.

Instead of the QM9 results, we would like to put more emphasis on the ZINC250k dataset with a larger search space and higher relevance to real-world applications (drug discovery). In the corresponding result, our HGGT achieves much better FCD and NSPDK metrics compared to the baselines, at the cost of a very small decrease in uniqueness and novelty. We also note that one can compensate for the non-unique and non-novel molecules by filtering them out and generating new molecules.

Dear reviewer K9N3,

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}}$.

W1. The claim "capturing the hierarchical graph structure" and the description "hierarchical representation" need rephrasing.

Thank you for the insightful comment. We agree that our claims on "capturing the hierarchical graph structure" can be ambiguous. In our updated manuscript, we added a discussion on how our HGGT does not necessarily capture the exact hierarchical community structure in Appendix H.

However, we believe it is still appropriate to describe our $K^2$-tree as a hierarchical representation, hence choose to precisely specify the terminology instead of entirely rephrasing it. Our precise description is incorporated in the updated manuscript and explained in what follows.

Nodes in the $K^2$-tree form a parent-child hierarchy between the nodes. To be specific, each node in our $K^2$-tree corresponds to a block (i.e., submatrix) in the adjacency matrix. Given a child and its parent node, the child node block is a submatrix of the parent node block, hence the tree also represents a hierarchical structure between the blocks. While this hierarchy may differ from the hierarchical community structure, the $K^2$-tree representation still represents a valid hierarchy present in the adjacency matrix.

Finally, we also point out prior works [1,2] that imply how the Cuthill–McKee node ordering (used in our HGGT) partially captures the underlying community structure. These prior works additionally support our statement that our $K^2$-tree representation is a hierarchical representation. This is incorporated in Appendix H of our updated manuscript.

W2. A detailed discussion of how HGGT differs from GRAN is missing.

Thank you for pointing this out. We compare our HGGT with GRAN in the updated manuscript (Appendix H) and in what follows.

First, the main conceptual difference is in the representation generated by HGGT and GRAN.

• HGGT generates $K^2$-tree representation for graphs with large zero-filled blocks. This is based on summarizing the large zero-filled blocks into a single node in the $K^2$-tree.
• GRAN generates the conventional adjacency matrix representation. The block matrices are conceptually irrelevant for the graph representation and instead used for parallel decoding.

Next, as the reviewer mentioned, both HGGT and GRAN use block-wise decoding. However, the decoding processes of the block matrix elements are different.

• HGGT sequentially specifies the block matrix elements in a hierarchical way. It first specifies whether the whole block matrix is filled with zeros at the upper level of the $K^2$-tree, then proceeds to specify smaller submatrices in the lower levels of the $K^2$-tree.
• GRAN can optionally decode the block matrix elements in parallel. All the elements in the block matrices are generated at once to speed up the decoding process (at the cost of slightly lower performance).

Finally, the semantics and shapes of the block matrix in HGGT and GRAN are also different.

• The square-shaped HGGT block defines connectivity between a pair of equally-sized node sets.
• The rectangular-shaped GRAN block defines connectivity between a set of newly added nodes and the existing nodes at each decoding step.

This is incorporated in Appendix H of our updated manuscript.

Dear reviewer JeGt,

We sincerely appreciate your comments and efforts in reviewing our paper. We address your question as follows. We also updated our manuscript which are highlighted in $\color{red}{\text{red}}$.

W1/Q1. The performance of HGGT (Table 2) is not so satisfactory for molecular graph generation. Why is the performance not so good as that on the generic graph datasets?

We believe our molecular graph generation performance to be satisfactory since it achieves better NSPDK, FCD, QED, and SA as reported in Section 5.2 and Appendix G.2. However, we resonate with your concern since the HGGT scores low novelty and uniqueness for the QM9 dataset, which may yield the impression that our scores are not so satisfactory. To alleviate your concern, we explain why (a) low novelty is a natural consequence of faithfully learning the molecular distribution and (b) one should put more emphasis on the ZINC250k dataset when interpreting our results.

First, 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). It is noteworthy that no existing baseline has successfully avoided this trade-off on the QM9 dataset.

Instead of the QM9 results, we would like to put more emphasis on our results on the ZINC250k with a larger search space and higher relevance to the real-world application, i.e., drug discovery. Here, one can observe our HGGT to achieve better FCD and NSPDK metrics compared to the baselines, while trading off for a very small decrease in uniqueness and novelty.

Q2/W2. What is the time complexity of $K^2$-tree construction and graph construction from $K^2$-tree?

The time complexity of $K^2$-tree construction from the adjacency matrix is $O(N^2)$ where $N$ is the number of vertices in the graph, as stated in the original paper [1] that proposed the $K^2$-tree for graph compression. The adjacency matrix construction algorithm also takes $O(N^2)$ time complexity since it requires querying for each element in the adjacency matrix. This is incorporated in Apepndix A and B of our updated manuscript.

Q3. Is the $K^2$-representation still lossless after pruning, flattening and tokenization?

Yes. Given a $K^2$-tree, the pruning process iteratively removes each $(i, j)$-th child node associated with a redundant submatrix, i.e., a submatrix consisting of matrix elements positioned above the matrix diagonal. Each removal can be inverted by duplicating the $(j, i)$-th child node as a new $(i, j)$-th child node.

To implement the lossless reconstruction in a simple way, one could apply Algorithm 2 (in Appendix B) to the pruned $K^2$-tree to obtain an incomplete adjacency matrix $\hat{A}$ with zero entries above the diagonal. Then one can recover the full matrix by duplicating the entries below the diagonal, i.e., set the adjacency matrix by $A = \hat{A}+\hat{A}^{\top}$.

In addition, the flattening process is lossless since it flattens the tree with breadth-first traversal. The un-flattening process is defined by adding all the child nodes for each token to a uniquely defined parent node, i.e., the oldest node with label one and without a child node. This process is lossless since it uniquely maps a token to each sequence to a unique $K^2$-tree structure.

To further verify our claim, we conducted experiments on the reconstruction of the original adjacency matrices from the pruned $K^2$-trees, and the results showed a 100% reconstruction rate. This finding confirms that pruned $K^2$-tree is a lossless compression method.

References

[1] Brisaboa et al., $K^2$-Trees for Compact Web Graph Representation. International Symposium on String Processing and Information Retrieval 2009.

Dear reviewer Nzff,

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}}$.

Q1. Could it be possible to adopt the proposed graph generation algorithm to create graphs with specific topological properties (e.g., node degree or clustering coefficient)?

Thank you for the suggestion. Yes, one can train a conditional generative model (parameterized by a Transformer) on our representation with the specific topological properties as conditions. One could even extend our framework to controllable generation [1], which would be an interesting avenue for our future research.

References

[1] Keskar, N. S., et al., CTRL: A conditional transformer language model for controllable generation. arXiv preprint 2019.