Large-Scale Dynamic Graph Generation via LLM-based Agent Simulation

First, thank you very much for your comments and advices. We'll address your comments in the following.

(1) Network science is a very broad field, and works on network science has been published in NIPS[1], WWW[2]. I think this kind of worry is unnecessary.

(2) First, we have considered both visualization of dynamic network evolution, as has been detailed in Page 9: https://anonymous.4open.science/r/GraphAgent-2206/visualization/ social network.mp4. Second, we also consider the evaluation of the dynamic evolution process of graph structure. As has been detailed in Section 4.1. Shrinking Diameter. Which is a surpursing property of graph evolution discovered in emperical studies. We have shown that the effective diameter of our generated graphs become smaller as the graph grows, successively replicating the shrinking diameter phenomenon.

(3) The use of multiple agents aligns with our goal of generating large-scale graphs. Additionally, our proposed N-ACTOR algorithm relies on multiple agents to enable accelerated simulations. Using a single agent would not support large-scale simulations, making it infeasible to generate large-scale graphs.

GAG is also capable of generating heterogeneous graphs. By defining different mapping functions (as detailed in Section 3.4), GAG can easily create heterogeneous graph structures. For example, in the RA setting, the Movie Rating Network (illustrated in Appendix A.3) includes a node set consisting of both movie watchers and movies.

Furthermore, using agents to exhibit drastically different functionalities is indeed a valuable approach. We have incorporated this concept by employing a control agent, which creates a control profile to manage and oversee the simulation process in GAG.

(4) For macro-level structural characteristic alignment, we examine three structural properties observed in real-world networks and demonstrate that they can be reliably replicated by GAG. This indicates that GAG, through human behavior simulation, effectively generates graph structures that align with real-world network characteristics. To further substantiate these findings, we have included additional macro-level structure alignment experiments in Appendix B.2 as part of the empirical studies you mentioned.

But, we have already considered comparisons with existing graph generation methods in terms of both graph structure and textual features:

1. Graph Structure Comparison:
   Detailed experiments are presented in Section 4.1, and to further enhance the persuasiveness of our results, we have included supplementary experiments and ablation studies in Appendix B.3.

2. Graph Textual Feature Comparison:
   Comprehensive comparisons are provided in Section 4.3, where we also expand the baseline graph generation models in the revised version. Additionally, to strengthen the evidence, we have included Ablation Experiments on LLMs in Appendix C.2.

(5) For weakness 5.

1. Adding More Random Graph Models as Baselines:
   We acknowledge the suggestion from other reviewers to include additional random graph generation models as baselines. In response, we have incorporated the small-world model as a baseline in Sections 4.2 and 4.3.

2. GNN Benchmarking on Graph Generation:
   Thank you for the suggestion. We have added relevant references in Section 4.3 to support GNN benchmarking in the context of graph generation.

3. Inclusion of GraphMaker as a Baseline:
   We have included GraphMaker as a baseline for both the Micro-level Structure Alignment and Textual-Attribute Alignment experiments. However, it is important to note that while GraphMaker is capable of generating attributed graphs, it cannot produce textual attributes for graphs, which remains a unique strength of our proposed method.

(6) For micro weaknesses. We change all the mentioned typos.

[1] Sorscher B, Geirhos R, Shekhar S, et al. Beyond neural scaling laws: beating power law scaling via data pruning[J]. Advances in Neural Information Processing Systems, 2022, 35: 19523-19536.

[2] Meusel R, Vigna S, Lehmberg O, et al. Graph structure in the web---revisited: a trick of the heavy tail[C] Proceedings of the 23rd international conference on World Wide Web. 2014: 427-432.

Sorry for the late reply. Thank you for the detailed response and updated experiment results. To help me better assess the contributions and significance and also refresh my memory, I would greatly appreciate it if you could provide concise and precise explanations to the following questions, supported by specific references to existing literature or your experiment results whenever appropriate.

1. What are concrete downstream applications where text-attributed graph generation would provide practical value? I expect specific answers beyond an umbrella term like network science.

2. Your work proposes GAG as a training-free approach to graph generation. Could you:

   • a) Identify the specific scenarios where a training-free approach offers advantages over training dedicated graph generative models

   • b) Explain how your experimental setup reflects these target scenarios for both 1 and 2 a)

   • c) Highlight the key results that demonstrate these benefits

3. Are training & inference efficiency/cost-effectiveness an important concern for the target scenarios? If so, what are the pros or cons of GAG?

4. Looking beyond the current work, what do you see as the most exciting possible directions for extending GAG that may inspire the graph ML/agent communities?

First, thank you very much for your comments and advices. We'll address your comments in the following.

(1) Regarding the interpretability of graph generation. Since we model the graph generation process as a simulation process, each added node and edge can be directly interpreted as paper writing, reference selection, retweet tweets and etc. Furthermore, we can directly gather reasons for paper referencing during the graph generation process. We provide a visualization of this process in Appendix. F.

(2) Regarding Figure 3.b., upon removing ReRanking, $D_e$ stays at a ver small value across the graph evolution process, trending upwards from 2.6 to 2.96 (as mentioned in Line 395). We modify the legend in Figure 3.b.to clarify any misunderstanding. Moreover, to intuitively illustrate the graph evolution process modeled by GAG, we choose the SA simulation scenario and visualization in https://anonymous.4open.science/r/GraphAgent-2206/visualization/social_network.mp4

(2) Regarding the small diameter of citation networks, in power-law models, this diameter is often expressed as $\log \log(n)$, where $n$ is the number of nodes. We incorporate empirical studies of diameter measurements to demonstrate that GAG can produce citation networks with a small diameter. Both the diameter range [4, 35] from empirical studies[1] and [1.17, 11.66] generated by GAG are relatively small when compared to the overall scale of their respective networks, making them comparable. To avoid misunderstanding, we clarify that while these ranges may differ numerically, they are both indicative of citation networks with similarly small diameters relative to their size.

[1] Leskovec J, Kleinberg J, Faloutsos C. Graphs over time: densification laws, shrinking diameters and possible explanations[C] Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining. 2005: 177-187.

First, thank you very much for your acknowledgement and advices. We are very much appreciate it. We'll address your comments in the following.

(1) Regarding presentations of the technical details of this paper. Given the 10-page limit for this paper, some trade-offs were necessary in presenting technical details.

In Section 3.4, we provide additional details about the network evolution process in Appendix A.2 and Appendix A.3. The foundational idea of our model is that social networks comprise two types of entities: actors and items, connected through the affiliation of the former with the latter. This interaction is naturally represented as a bipartite graph, denoted as $B(Q, U)$, where $Q$ represents the actors and $U$ represents the items.

In the context of GAG, LLM-based agents constitute the set $Q$, consisting of $N$ agents simulating diverse actor roles, such as authors, movie watchers, or tweet users. Meanwhile, the set $U$, representing items, is initialized with $n$ entities such as papers, tweets, or movies, depending on the simulation setting.

To clarify the pairwise interaction process, we use the citation network as an example. In a citation network, the bipartite graph comprises authors ($Q$) and papers ($U$). The environment corpus ($C$) records the interactions between $Q$ and $U$, encapsulating their dynamic relationships. To initialize the environment corpus $C$, each node in $U$ is transformed into a textual format using an environment template ($T$). For instance (More examples available in Appendix.A.2.):

Node Features: Academic Paper  
Title: <Title> 
Topic: <Topic> 
Abstract: <Abstract> 
Author(s): <Author(s)> 
Edge Features: Citation relationships for paper node.

Our motivating example is a “social” network that emerges from search engine queries. For each simulation round, each author in $Q$ is provided with partial environmental information through queries. And author are prompted with action template $T_a$ to form new items, which are added to $U$; as well as links between $Q$ and $U$. For example, in citation networks, authors can write a new paper and cite other papers. The newly generated links and items are added to $C$. For instance (More examples available in Appendix.A.3.):

Action Template
Agent Profile: <Agent Profile\>
Agent Memory: <Agent Memory\>
Environment Observation: Partial Environmental Feedback provided by S-RAG, denoted as $o_l$. Abstract information for searched papers.
Human Instruction: <Instruction>...
Now write a version of your paper and cite the papers you need to cite.
------------------------------------------------------------------
Respond Example
Node Features: Academic paper. Title, Keywords, Abstract.
Edge Features: Paper references.

• For section 3.5. We need to obtain distinct types of graphs. Since after $k$ simulation rounds, the bipartite graph $B(Q,U)$ evolves, which gradually enriches $C$ into $C'$. Thus we define a range of mapping functions based on edge and node types to extract distinct graphs from $C'$. We incroporate the mapping functions in Appendix.A.3.

• For section 4.2, We add additional details about the GNN experiments in the Appendix.C.1, and add more details about the evaluation metrics in Section 4.2.

(2) Regarding adding more baselines for random networks. We add more baselines both in section 4.1. (Micro-level Evaluation). We add more datasets in Appendix.B. in the revision version.

(3) For structure alignment, we have done extensive experiment on both macro-level and micro-level properties of graph structure and we ignores text features. For macro-level, we focus on the power-law, small-world, shrinking diameter and other stucture properties. For micro-level, we focus on the degree-distribution, clustering coefficient and other micro-level properties. As detailed in section 4.1. and more details in Appendix.B. For both macro-level and micro-level structure alignment.

(4) About question 2, We generate the graph topology using existing graph generation methods, coupled with the text features generated with an LLM based on the CiteSeer corpus. We add the experiment details in Appendix.C. The experiment results are shown in Table 3 in Section 4.2. in the revision version.

(5) Indeed, network motifs and graphlets are ideal indicators for graph generation. Following [1], we add additional metrics for micro-level evaluation of graph structure. We add additional experiments in Table 2 and Table 15.

[1] Diamant N L, Tseng A M, Chuang K V, et al. Improving graph generation by restricting graph bandwidth[C] International Conference on Machine Learning. PMLR, 2023: 7939-7959.

First, thank you very much for your acknowledgement and advices. We are very much appreciate it. We'll address your comments in the following.

(1) For question 1 and 2. Indeed, we acknowledge that existing graph generation models can capture macro properties, but only if they're given high-quality training graphs.

• First, for existing graph generation models, we need to collecting the necessary large-scale graphs as datasets. Existing models typically require at least 50 graphs to train model. To generate citation networks with 10^5 nodes, this would require collecting at least 50 citation networks of similar scale—a clearly infeasible task. In contrast, GAG can simulate the evolution process of citation networks from small to large scales. As demonstrated in Experiment 4.2, the citation networks generated by GAG adhere to both the micro-level and macro-level properties observed in real-world citation networks. Existing deep learning-based graph generative models, however, struggle to transfer graph structures learned from small-scale citation networks to larger ones. This limitation is evident in their failure to reproduce the power-law distribution in generated graphs. Even in the absence of any graph datasets, GAG is able to generate citation graphs from scratch. We incoporate one example of generating online social networks from scratch, as shown in Section 4.3. However, existing deep-learning-based graph generative models cannot generate graphs from scratch.

• Additionally, these models cannot generalize to new settings where networks have not yet been observed. For instance, to generate citation networks in different domains, GAG requires only a change in the writing topics of LLM-based agents, easily generating citation networks for topics of computer science, physics, medicine, etc.

In summary, to generate large-scale citation networks with existing graph models, we would need to gather many large-scale citation networks at first. And the models cannot be generalized to new settings where networks are not yet observed.

(2) For question 3, we have added more discussions about recent scalable graph diffusion models.

(3) For question 4, we have added more discussions about "LLMs generate structurally realistic social networks but overestimate political homophily." in Section 2. This paper provide valuable results for evaluating political homophily of generated graphs, but it's limited to the social networks. Our framework is applicable to other domains, such as citation networks, movie networks, etc.

(4) For question 5, we crawl for the author information, abstract, citations and etc. for the CiteSeer and Cora Dataset. The Dataset is open-sourced in the GitHub repository.

(5) For question 6, we transform the node representations into textual format. We consider all neighbouring edges of node $v_i$, to enrich the tetual information of node $v_i$. This is detailed in Appendix.A.2.

(6) S-RAG retrives the most relvent environment information to the queries sent by agents, it doesn't necessarily mean GAG only retrieves homophily social networks. The foundational idea behind GAG is that social networks consist of two types of entities: actors and items, that are related by affiliation of the former in the latter. This interaction can naturally be modeled as a bipartite graph, denoted as $B(Q, U)$, where $Q$ represents the actors and $U$ represents the items. In GAG, LLM-based agents form the set $Q$, consiting of $N$ agents to simulate diverse actor roles, such as authors, movie watchers, or tweet users. Meanwhile, the $U$ set, representing items, is initialized with $n$ entities, such as papers, tweets, or movies, depending on the simulation setting. Through continouse simulation rounds, the bipartite graph $B(Q, U)$ evolves with generated interaction data.

For each simulation round, each author in $Q$ is provided with partial environmental information through S-RAG. The partial environmental information denotes the textual representation of subgraph from $U$. Authors are prompted with action template $T_a$ to form interaction data, which include new item nodes, which are added to $U$; as well as actor-item links. For example, in citation networks, authors can write a new paper and cite other papers. The newly generated links and items are added to $C$, where changes in $C$ correspond to the evolution of $B(Q, U)$.

The flexibility of GAG lies in its ability to model not only homophilous networks but also heterophilous ones. To achieve this, we modify the mapping functions to fold $B(Q, U)$ into graph $G$ that capture heterophily. For example, paper-author bipartite graph can be folded into citation graphs, co-authorchip graphs and etc. The details of these mapping functions are described in Section 3.4, with further implementation specifics provided in Appendix A.3.

(7) About cost, we add more details about the cost in Appendix D.

For macro-level structure alignment, we chose LLama-3-70B, while GPT-3.5-turbo was selected for micro-level alignment. In the ablation study of LLMs, we also included GPT-4o-mini and Qwen-2-72B. These details have been incorporated into the revised version for clarification.

The experiments for micro-level structure alignment requires text-rich dynamic graphs, which are highly scarce. To address this limitation, we enhanced the original Cora dataset by adding timestamps and text-rich attributes. The enriched datasets are available in our open-source GitHub repository. Additionally, we conducted further experiments on additional datasets, as detailed in Appendix B.3 (Table 15).

Thank you for your response. All my comments have been addressed, and I've increased my score as a result.