A Large-scale Training Paradigm for Graph Generative Models

We sincerely appreciate the reviewer's great suggestions, and we have addressed them as follows:

W1. The approach relies primarily on existing discrete denoising diffusion techniques, which, while effective, lacks methodological innovation specific to large-scale graph generation. This reliance on existing methods may limit the theoretical foundation and originality of the model within the context of large-scale graph generation.

Our work focuses on exploring the potential of large-scale training for graph-generative tasks rather than specifically targeting the generation of large-scale graphs. Furthermore, our proposed large-scale gap training strategy can be equipped with any graph generative models, including that scalable version. For example, we equip EDGE[1], a scalable discrete graph diffusion model, with LGGM in Table 15. We can see better graph generation performance there as well. This showcases the generalizability of our approach across existing diffusion models.

[1] Chen, Xiaohui, et al. "Efficient and degree-guided graph generation via discrete diffusion modeling." arXiv preprint arXiv:2305.04111 (2023).

W2. The paper includes a comparison with only a single baseline, which is insufficient to evaluate the model’s performance thoroughly.

Thank you for the suggestion. We want to kindly note here that our proposed LGGM is a large-scale graph generation paradigm rather than a specific graph generation model. Therefore, this LGGM can be equipped with any existing discrete graph generation model. For example, we equip it with both DiGress in Table 2 and EDGE in Table 15, the performance of both of which has been lifted in both zero-shot and full training settings.

Q1. Are there any experiments or analyses conducted to evaluate the model's performance in relation to scaling law expectations?

We justify the effect of the size of the graph data from two perspectives:

From the zero-shot generation performance, we gradually increase the size of training graphs we use for all other domains ranging from ratio 0.1 to ratio 0.9 and show the results for the following two datasets: Road and Retweet. We can find on the road network that the performance gradually increases as the training graphs increase. This aligns with the data scaling law, which states that more training data leads to better zero-shot generation performance. However, although we observe a similar trend in Degree and Spectre metrics on Retweet, we do not observe a similar trend in Clustering and Orbit.

From the fine-tuned generation performance, we gradually increase the size of training graphs used for fine-tuning the pre-trained LGGM or used for directly training DiGress from scratch. In Figure 4(a)-(b), we can find the more fine-tuned graphs we use, the less the performance gap between the pre-trained-then-fine-tuned LGGM and the DiGress trained from scratch. This is because as more fine-tuned graphs are available, the benefit of pre-training becomes weaker and weaker.

W1. Fundamentally Weak Theoretical Foundation:

The theoretical analysis is superficial and merely combines existing results without meaningful insights. While Section 3.3 claims novel expressiveness results, the proofs follow directly from prior work [1,2] and ignore fundamental limitations established in recent literature [3]. The paper fails to provide any theoretical justification for why cross-domain pre-training should help, or how the sampling strategy preserves important graph properties. Most importantly, there's no analysis of how the multi-domain training affects model capacity and expressiveness.

We deeply appreciate the reviewer's thorough reading of our theoretical proof.

For Theorem 1, we borrow insights from DiGress and apply them to prove the posterior distribution of our setting. However, for Theorem 2, the insight here is that by following our proposed text2graph training paradigm, our diffusion model could be optimized towards maximizing the lower bound of the joint distribution of textual description and graph property. If the training data is prepared so that the textual description corresponds to the graph property, then we can at least guarantee the lower bound of our textual controllable graph generation.

W2. Limited Technical Innovation and Poor Design Choices: The core methodology is essentially DiGress [1] with small modifications. The sampling strategy for handling large graphs is ad-hoc and lacks theoretical guarantees, while all four pre-training tasks are directly borrowed from existing work without significant adaptation to graph-specific challenges. The architecture choices appear arbitrary rather than fundamental, and the text-to-graph component is a straightforward application similar to existing approaches TAPE[4] and GraphGPT[5] without addressing the unique challenges of graph generation. The text-to-graph mechanism is particularly concerning - it simply concatenates LLM embeddings with graph features without addressing the fundamental challenges of aligning textual and structural representations. This naive approach ignores significant prior work on text-attributed graphs, such as [4,5], which have developed sophisticated techniques for text-graph alignment.

We really appreciate reviewers who draw so much fantastic literature, and we have dedicatedly reviewed them with our discussion as follows. We admit that our model architecture is similar to DiGress. However, our motivation is not to propose a specific model architecture but to propose a large-scale training paradigm to equip with any graph diffusion model. We also include the result of equipping our LGGM with EDGE, another graph diffusion model. Even more, large generative models such as GPT3 and LAVAR do not include significant model architecture design. Therefore, we want to draw the reviewer's attention to our contribution, which is not focused on a new model.

Q1. What specific architecture is utilized for the reverse process mentioned in Line 193?

Following DiGress, we begin by sampling a batch of graphs from the global distribution of graphs across different domains, denoted as $\mathbb{E}_{G \sim P(\mathbb{G})}$.

Next, we sample a specific perturbation step $t$ and apply the forward transition process to generate a noisy graph, represented as $\mathbb{E}_{G^t \sim q(\mathbb{G}^t|\mathbb{G})}$.

The resulting noisy graph $G^t$ and the corresponding clean graph $G$ are then used to train the graph neural network. Specifically, $G^t$ serves as the input, and $G$ is treated as the target label. The model is optimized using a cross-entropy loss, enabling the network to predict the clean graph from the noisy graph sampled during the forward process.

Q2. It remains unclear whether the performance improvements observed over DiGress are primarily due to the cross-domain pretraining or any enhancements in the pretraining architecture.

Our proposed large-scale training paradigm is a training strategy rather than a specific model architecture. Therefore, we do not introduce any enhancements in the pretraining architecture, and the improved performance is mainly due to the cross-domain pertaining.

Q3. How do the authors ensure these hyperparameters (best for certain domain training) are also optimal for cross-domain pretraining? Is there any empirical evidence or rationale behind their choice?

We select the default hyper-parameter setting from DiGress mainly due to the extensive computation resources required for hyperparameter tuning. Therefore, we select the default hyperparameter and already see the performance achievement. Our LGGM performance can be further boosted after hyperparameter tuning.

Q4. As the model scales to accommodate larger graph corpora, is there a scaling law that governs the architecture’s performance?

We justify the effect of the size of the graph data from two perspectives:

From the zero-shot generation performance, we gradually increase the size of training graphs we use for all other domains ranging from ratio 0.1 to ratio 0.9 and show the results for the following two datasets: Road and Retweet. We can find on the road network that the performance gradually increases as the training graphs increase. This aligns with the data scaling law, which states that more training data leads to better zero-shot generation performance. However, on Retweet, although we observe a similar trend in Degree and Spectre metrics, we do not observe a similar trend in Clustering and Orbit.

From the fine-tuned generation performance, we gradually increase the size of training graphs used for fine-tuning the pre-trained LGGM or used for directly training DiGress from scratch. In Figure 4(a)-(b), we can find the more fine-tuned graphs we use, the less the performance gap between the pre-trained-then-fine-tuned LGGM and the DiGress trained from scratch. This is because as more fine-tuned graphs are available, the benefit of pre-training becomes weaker and weaker.

Q5. The textual descriptions are limited to graph structure and domain type. Is it possible to extend to text-to-graph generation conditioned on certain categories, which will be more useful and applicable in real-world scenarios?

We really appreciate this great suggestion, and it is definitely possible to extend the current framework to conditioning on certain categories, which would be useful for conditional molecule generation. However, as this work mainly studies the large-scale training effect of graph generation and the text2graph control over graph structural property, we will leave it as one potential future work.

We sincerely appreciate the reviewer's great suggestion, and we have addressed them as follows:

W1. Novelty of our work:

Novelty in Cross-Domain Pretraining: To the best of our knowledge, no prior works on graph generative models have explicitly focused on cross-domain pretraining. While an exhaustive search has identified a few studies leveraging cross-dataset pretraining, it is important to note that cross-dataset pretraining is conceptually different from cross-domain pretraining. Cross-dataset pretraining involves training on datasets that may share similar characteristics or belong to the same domain, whereas cross-domain pretraining involves transferring knowledge across graphs from distinct domains with differing structural or application contexts. Our observation is particularly compelling: pretraining on graphs from diverse domains leads to improved performance in downstream tasks, demonstrating the potential of cross-domain strategies to capture richer, more transferable graph representations.

Novelty in Text-to-Graph Generation: In terms of text-to-graph generation, to the best of our knowledge, this approach has not been explored in the context of generative graph modeling for network statistics (e.g., clustering coefficient, network density). While text-to-graph techniques have been investigated in specific domains, such as molecule generation, these efforts predominantly focus on controlling molecular properties rather than the statistical properties of graphs. Similarly, generating knowledge graphs via relational extraction or simulating social networks with LLM-powered agents can also be considered forms of T2G generation. However, these approaches operate primarily at the textual or semantic level and do not provide control over the structural or statistical characteristics of the generated graphs. Our work uniquely contributes to this area by introducing a method explicitly incorporating network statistics into Text-to-Graph Generation generation.

W2. The computational complexity and scalability of our framework:

The primary motivation of our work is to explore the potential of large-scale training strategies for graph generation rather than focusing on generating large-scale graphs. We also appreciate the reviewer’s suggestion to discuss potential solutions for addressing the space and time complexity of discrete denoising diffusion models.

Addressing Space/Time Complexity in Discrete Diffusion

Firstly, while reconstructing high-dimensional node and edge categories may increase time and space requirements, the primary bottleneck lies in reconstructing the adjacency matrix, which has a time and space complexity that scales quadratically with the number of nodes. This is a well-recognized limitation in current discrete diffusion models for graphs. The general solutions proposed in the literature typically reduce the prediction space by focusing on specific node pairs rather than all possible pairs. Notable approaches include:

(1) EDGE [1]: This method predicts important nodes first and reconstructs edges selectively, reducing the quadratic computation. (2) SaGress [2]: This approach generates small subgraphs independently and assembles them into larger graphs, transforming the larger quadratic computation into several small quadratic computations.

[1] Chen, Xiaohui, et al. "Efficient and degree-guided graph generation via discrete diffusion modeling." arXiv preprint arXiv:2305.04111 (2023).

[2] Limnios, Stratis, et al. "Sagess: Sampling graph denoising diffusion model for scalable graph generation." arXiv preprint arXiv:2306.16827 (2023).

Large-scale network generation, particularly for social graphs, has seen a recent paradigm shift [3]-[4]. Instead of directly generating large social networks, researchers are increasingly simulating these networks using large language model (LLM)-powered agents. This approach is particularly effective for studying social dynamics, as it allows insights derived from simulated networks to be transferred to real-world applications. Discussing under the framework of these methods, the computational challenges of quadratic growth can be addressed by leveraging principles like preferential attachment, focusing only on the most relevant nodes when adding links rather than considering all possible node pairs.

For biochemistry graphs such as drug design, graph generation is not governed by a specific social rule, and hence, diffusion-based models will still be used. However, these graphs are generally smaller compared with social graphs, which do not have any scalability issues. We will include the above discussion in the revision.

[3] Gao, Chen, et al. "S $^ 3$: Social-network Simulation System with Large Language Model-Empowered Agents." arXiv preprint arXiv:2307.14984 (2023).

[4] Pine, Karleigh, et al. "Social Network Analysis and Validation of an Agent-Based Model." arXiv preprint arXiv:2308.05256 (2023).

We sincerely appreciate the reviewer's great suggestions, and we have addressed them as follows:

W1. The performance of zero-shot scenarios differs in different domains. On some domains, such as FB, the LGGM does not work well.

Based on the average degree and clustering coefficient distribution in Figure 1(a), FB only counts a tiny region among the whole graph universe. The average clustering coefficient of FB graphs ranges from 0.301 to 0.407, a narrow segment within the broader global graph spectrum from 0 to 1. This narrow range challenges the generalized large-scale training paradigm LGGM-X to specialize in learning the graph data distribution specific to the FB domain.

W2. The paper emphasizes that the LGGM is trained on over 5000 graphs. The number is not so large for a generative pre-trained model.

The claim is made under the context that we are comparing our training scheme with previous works focusing on generating graphs rather than in natural language processing and computer vision, such as GPT-series[1] and LLaVAR[2].

[1] Brown, Tom B. "Language models are few-shot learners." arXiv preprint arXiv:2005.14165 (2020).

[2] Liu, Haotian, et al. "Visual instruction tuning." Advances in neural information processing systems 36 (2024).

Within the graph generation domain, we are the very first to explore the multi-domain training setting where graphs from different domains are fused together to train the graph generative models. Furthermore, our multi-domain training considers 13 different domains, which are much more than the number of domains in previous work.

To avoid potential confusion, we clarify that our claim of "large" refers to the diversity and scale of domains considered in our training scheme rather than the absolute number of graphs.

W3. In the experiment of augmenting graph classification, the performance of LGGM is not promising (especially on the ENZYMES dataset).

Overall, training with generated graphs by LGGM lead to better graph classificaton performance. For the weaker improvement on ENZYMES, the potential reason is that our LGGMs are only trained on training graphs from different datasets and may still lack knowledge about testing graphs, which may not bring significant performance improvement over unseen testing graphs.

Q1. The time and space complexity is quadratic to the number of nodes. How can the method be applied to graphs with large numbers of nodes?

We admit that the time/space complexity of some existing graph diffusion models are quadratic to the number of nodes as analyzed in Appendix B in Table 6. However, our work is mainly to investigate the potential of large-scale training scheme and text2graph generation instead of scalable graph diffusion.

Furthermore, since our proposed method is a general strategy that can be paired with any existing graph diffusion model, we can pair LGGM with scalable graph diffusion models such as SiGress[3] and EDGE[4]. Specifically, we include the result in Table 15 in Appendix F.5 of pairing LGGM with EDGE, which demonstrates both better effectiveness in terms of generative performance than EDGE trained from scratch and better efficiency in terms of significantly shorter time compared with DiGress.

[3] Limnios, Stratis, et al. "Sagess: Sampling graph denoising diffusion model for scalable graph generation." arXiv preprint arXiv:2306.16827 (2023).

[4] Chen, Xiaohui, et al. "Efficient and degree-guided graph generation via discrete diffusion modeling." arXiv preprint arXiv:2305.04111 (2023).