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

Authors: Jiarui Ji, Runlin Lei, Jialing Bi, Zhewei Wei, Yankai Lin, Xuchen Pan, Yaliang Li, Bolin Ding
Primary area: learning on graphs and other geometries & topologies
Keywords: LLM-based Agents, graph generation

Abstract:
Graph generation is a fundamental task that has been extensively studied in social, technological, and scientific analysis. 
For modeling the dynamic graph evolution process, traditional rule-based methods struggle to capture community structures within graphs, while deep learning methods only focus on fitting training graphs. 
This limits existing graph generators to producing graphs that adhere to predefined rules or closely resemble training datasets, achieving poor performance in dynamic graph generation.
Given that graphs are abstract representations arising from pairwise interactions in human activities, a realistic simulation of human-wise interaction could provide deeper insights into the graph evolution mechanism.
With the increasing recognition of large language models (LLMs) in simulating human behavior, we introduce GraphAgent-Generator (GAG), a novel simulation-based framework for dynamic text-attributed graph generation. Without training or fine-tuning process of LLM, our framework effectively replicates seven macro-level structural characteristics in established network science theories while surpassing existing baselines in graph expansion tasks by 11\% on specific evaluation metrics. Through node classification task, we validate GAG effectively captures the intricate text-structure correlations in graph generation. 
Furthermore, GAG supports generating graphs with up to nearly 100,000 nodes or 10 million edges through large-scale LLM-based agent simulation with parallel acceleration, achieving a minimum speed-up of 90.4\%.
The source code is available at \url{https://anonymous.4open.science/r/GraphAgent-2206}.

Decision: reject
Reviewer scores: 6, 5, 5, 3, 5

Reviews and discussion:
<thread>
creation date:
1730348833862

thread_type:
official_review

<thread_object>
creator: reviewer_lq7q

<content>
summary:
This paper introduces GraphAgent-Generator (GAG), a generative framework for text-attributed graphs based on the interaction of multiple LLM agents using prompting and retrieval-augmented generation (RAG). Without any training, empirical studies demonstrate the effectiveness of GAG in scenarios like modeling the common structural patterns of real-world networks in network science. This approach also demonstrates competitive scalability, allowing generating networks of up to about 100K nodes.

strengths:
**S1.** Using multiple LLM agents for graph generation is conceptually novel to the best of my knowledge.

**S2.** Generating graphs of up to 100K nodes demonstrates strong scalability of the approach.

**S3.** The authors consider multiple well-established structural patterns in network science for empirical studies.

weaknesses:
**W1.** The paper primarily considers network science as the downstream scenario. While it may be of interest to the network science community, it's unclear whether there is sufficient interest from the ICLR community.

**W2.** In terms of problem formulation, the paper claims to consider the generation of dynamic and text-attributed graphs. However, the empirical studies primarily focus on static graph structural patterns, which is the same as various previous works, despite using different metrics. To justify the use of terms like "dynamic", I expect to see a setting for temporal network generation which requires modeling distribution shifts over time.

**W3.** The use of multiple agents is not sufficiently justified and discussed. With expressions like 100K nodes with 100K LLM-based agents at L82, it seems that each agent corresponds to exactly a node and likely agents only differ in prompts/prompt templates. This makes the whole idea a bit uninteresting and also leads to potential concerns for scalability. It will be more interesting if the agents exhibit drastically different functionalities. For example, in a heterogeneous graph, different agents can be responsible for different node types or edge types.

**W4.** Empirical studies fail to show that GAG can outperform models trained on specific datasets, making the selling point barely training-free graph generation. In that case, the authors need to spend more efforts in justifying why training-free models incapable of capturing fine-grained dataset-specific patterns is useful and desirable.

**W5.** The discussion and comparison with respect to previous related works is insufficient. To name a few:

- Watts & Strogatz. Collective dynamics of 'small-world' networks. Barabási–Albert has been proven to be non-ideal for capturing clustering coefficients while the Watts–Strogatz model, also a random graph model, performs much better in that case. The empirical studies about clustering coefficient should compare against the Watts–Strogatz model.

- Yoon et al. Graph Generative Model for Benchmarking Graph Neural Networks. This paper proposes the use of GNNs for graph generation evaluation.

- Li et al. GraphMaker: Can Diffusion Models Generate Large Attributed Graphs? This paper generates text-attributed graphs with up to 10K nodes and also employs GNNs for evaluation.

*Minor*
- The title in the PDF is different from the one in the OpenReview page.

- The citation at the end of L58 is not properly formatted.

- Notations should be more carefully handled for better readability, e.g., the Cs' in section 3.3. 

- Table 7 in the appendix is not properly formatted.

questions:
See Weakness.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730491407398

thread_type:
official_review

<thread_object>
creator: reviewer_c4qw

<content>
summary:
This paper addresses a synthetic graph generation problem by simulating human behaviors. The proposed framework, GraphAgent-Generator (GAG), uses LLM-based agents for graph generation. Through the iterative interactions between the agents, it extracts diverse graphs as collections of interaction data. In the experiments, the authors demonstrate that generated graphs follow multiple graph properties that real graphs exhibit.

strengths:
- This paper proposes a graph generation method that simulates interactions among agents. Through the simulation, generated graphs are naturally dynamic and
- The authors generate large-scale graphs with 10 million edges and accelerate the graph generation process through parallel computing.
- The experiments demonstrate that the generated graphs are realistic in terms of both macro- and micro level evaluations.

weaknesses:
- Certain parts of the paper lack clarity or contain ambiguous explanations.
    - In Section 1, the authors claim that interpretability in graph generation is one of the main contributions of this paper. However, I found no discussion about interpretability beyond the Introduction. Which experiments, if any, demonstrate that the graph generation is indeed interpretable, and why? In my view, the behavior of LLM-based agents is inherently difficult to interpret, as it heavily depends on the prompt. The authors should provide a detailed discussion on how interpretability is addressed, including case studies or qualitative analysis to support the claim.
    - In lines 378 and 379, the paper says “in Table 4, The generated networks exhibit small diameter De ∈[1.17,11.66], comparable to the range of [4,35] in real-world networks”. However, the De values of seven out of ten graphs in Table 4 are smaller than 4, which are not in the range of real-world networks that the authors cited. The authors should clarify why they claim these values are "comparable" given these results.
- Several experimental results are unclear. I wrote questions for the unclear parts in the Question section below (scalability/efficiency and ReRanking).

Comments: 

- The main content of this paper is not self-contained. For example, Sections 3 and 4 lack the core technical information of the proposed approaches.
- $\mathcal{E}$ is defined twice in the paper: a set of edges and a set of embedding vectors.
- Some tables in Appendix are incomplete, e.g., Tables 7, 11, and 13 due to excessive width or inconsistent columns.

questions:
- Which experiments or discussions demonstrate that the proposal is really interpretable (see Weakness about the interpretability of the method)?
- While the authors show the time cost (min) for generating one interaction data in Tables 5 and 6, I am also curious about the total time for generating the largest graph in this work. So, my question is: How long does it take to create the largest graph, e.g., Action and Friend in Table 4? Please include the experimental setting such as the numbers of agents and ports in your response.
- Why is the blue line (w.o. ReRanking) in Figure 3b zero across all the time?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730619336948

thread_type:
official_review

<thread_object>
creator: reviewer_wtmu

<content>
summary:
This paper addresses the limitations of existing graph generation approaches, where rule-based models struggle to accommodate the complexity of real-world graphs, and deep learning methods face challenges in handling out-of-distribution scenarios. We propose an LLM-powered, agent-based simulation approach for graph generation to overcome these challenges. Our approach simulates interactions between agents based on their profile information, contributing to efficient and realistic graph generation through two key innovations:

**Relevance Filtering with RAG:** We leverage a Retrieval-Augmented Generation (RAG) framework to filter out irrelevant agents, ensuring that only pertinent agents are included in the simulation.

**Parallel Processing with Community Structure:** By using parallel processing techniques and incorporating community structure, we accelerate the generation process, making it feasible to handle large-scale, complex graphs.

strengths:
(1) The proposed LLM-based agent for graph generation is a promising direction for social network simulation, especially for large-scale networks.

(2) The proposed textual-graph generation and parallel generation to simulate a very large-scale network in a very short time are very important and novel problems to address in this type of graph generation.

(3) Extensive experiments are conducted to verify the effectiveness and efficiency of this work.

weaknesses:
(1) Some of the claims in this paper are not so accurate in terms of introduction and related work. See questions (1), (2), (3)  

(2) Using RAG to filter irrelevant candidates when generating social interactions based on textual similarity would limit the scope of the generated network to a homophily network. For example, taking dating networks as an example, if we only use gender information to retrieve, we might generate a lot of people sharing the same gender interacting with each other, which might not align well with real-world cases. 

(3) The experiment setting for node classification is very weird. Firstly, the generated graph expands upon the original graph; why can't we directly generate the new graph and compare its node classification performance with the original one? Secondly, the baseline is very weak; the performance would significantly drop if we randomly select a node feature to create a node feature or shuffle. It might be better to compare with some better baselines, such as the ones that can maintain network homophily.

questions:
(1) For deep-learning-based graph generative models, although it can only fit training graphs, why could this be a problem that motivated the investigation of LLM-based agent simulated graph generation?

(2) The motivation of this work, in terms of how existing graph generation models have problems, is a little bit inaccurate. . For example, several existing graph diffusion models [1] have demonstrated the capability to generate community structure (which is a macro property), which does not closely align with the claim in line 53, "struggle to capture macro properties." Furthermore, the claim in line 50, "when generating larger graphs beyond the size of the observed dataset," is inaccurate. It treats the graph generation as an OOD problem. However, the proposed method in this paper has also not been verified by the OOD experiment. 

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

(3) In line 100, the maximum size of the expanded graph is limited to 144 nodes. Actually, the recent scalable graph diffusion models could handle social networks up to thousands of nodes [2]. However, I think this is far less than the real-world social network, which can still motivate this proposed work. However, if only saying 144 nodes, it is still slightly inaccurate.

(4) In related work, a very important work "Chang, Serina, et al. "LLMs generate structurally realistic social networks but overestimate political homophily." arXiv preprint arXiv:2408.16629 (2024)." is missing. It is better to include some discussions over here.

(5) In line 770, how do you crawl the node attributes to enrich text information for Citeseer? I checked the reference thereafter, but it is merely a paper collecting the Citeseer dataset. It might be better to provide more details on obtaining real-world textual profile information to initialize the agent.

(6) In line 199, why the C only considers one neighbor of each node $E_i = \{(v_i, v_j)|v_i, v_j \in \mathcal{V}\}$. 

(7) RAG seems mainly based on textual similarity to pre-filter, which might only apply to homophily social networks. Is there any idea how it can be generalized to a heterophily network, e.g., a dating network? In this case, it might be difficult to retrieve based on gender information.

(8) How much cost does it take for one round of simulation?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730638264437

thread_type:
official_review

<thread_object>
creator: reviewer_8dun

<content>
summary:
This paper presents a method for generating dynamic graphs via agent-based simulation. Graphs considered in this work contain text-based attributes and agents are modelled through Large Language Models, a method that has been shown to produce simulations of human-like behaviour. Rather than focusing solely on the final static graph, this method allows simulating the dynamic, organic growth of a complex network. In addition, using an LLM as the center-piece for the graph generating process allows the authors to generate both the graph topology and textual attributes of the graph.

The authors test the generated graphs with network science based metrics, demonstrating power law behaviour, small world phenomenom and preferential attachment (through shrinking diameter) in the generated networks. The authors also show that generated graphs retain properties useful for downstream tasks, such as node classification. Finally, the generated graphs are shown to scale up to 10 million edges and almost 100,000 nodes.

strengths:
- **Method**: the method presented is an interesting take on graph generation, particularly the ability to generate both network structure and text attributes simultaneously, which naturally enhance the realism of the generated networks.
- **Large-scale**: even if the *large* label can be questioned ($10^5$ nodes is on the lower end of large scale), the paper presents a significant advancement to the size of networks generated by deep-learning + agent based methods.

weaknesses:
- **Presentation**: ignoring the multitude of typos, which are easily fixed for a camera-ready version, I think the paper does itself a disservice in the way it presents its major strengths. It is clear to me that the content of the contribution was too much to fit in a 10 page paper and the final output omits too much detail to the point where it is hard to understand what was actually done. Sections 3.4, 3.5 and 4.2 are the best examples of this issue.
- **Experimental setup**:
   - **Experiment 4.1**: the random network models the authors choose to compare with are too simple. There is wide literature of random networks that approximate characteristics like small-world behaviour (Watts-Strogatz, for example, albeit not dynamic) or combination thereof, so comparing the properties of generated graphs against a random network model like Erdos-Renyi is naturally going to favour the proposed model.
   - **Experiment 4.2**: there is a lack of comparison of the quality of generated graphs against other graph generation models in the literature. Even if other models were unable to generate both topology and text features simultaneously, a more convincing experiment would be generating the graph topology using other methods, generating the text features with an LLM based on the CiteSeer corpus and demonstrating that GAG is better than this mishmash.

questions:
- Have you considered using network comparison or network alignment to verify the quality of the networks you generated, even ignoring text features?
- Network motifs encode functional behaviour within the network and are extremely powerful at distinguishing networks with similar generation mechanisms, are motif fingerprints and graphlet distributions of real networks replicated by your graph generation method?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730693276348

thread_type:
official_review

<thread_object>
creator: reviewer_kygp

<content>
summary:
The paper introduces GAG, a framework for generating large-scale human interaction graphs. The framework includes an S-RAG algorithm to simulate human interactions and an N-ACTOR parallel processing component. The paper shows that GAG preserves real-world structural characteristic.

strengths:
- The paper effectively shows that GAG generates graphs that mathc structural characteristics found in real world graphs.
- GAG's frameweork of generating graphs via simulating human interactions using LLM-based agents is novel.

weaknesses:
- The paper only evaluates the micro-level structural characteristics of GAG on the Citeseer dataset. This greatly limits the scope of the evaluation, and the authors should expand this evaluation to other datasets across domains to increase the generalizability of the results.

questions:
- In Section A.1, the authors mention that "for the LLM backbone, we have chosen open source model of Llama-3 AI@Meta (2024)". Which Llama 3 model was chosen?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732546629297

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Response to Reviewers

comment:
We sincerely appreciate the time and effort all the reviewers have dedicated to evaluating our work. As we approach the end of the rebuttal process, I would greatly appreciate any comments or suggestions. If possible, please share your response at your earliest convenience so that we can further discuss the paper content. Your support and insights are valuable to us. Thank you once again for your assistance.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732686081828

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Response to Reviewers

comment:
To clearly indicate the modifications made to the original paper, we have highlighted all changes in blue in the revised version, which will facilitate the reviewers' assessment of the experimental results. We sincerely appreciate all the relevant comments provided by the reviewers. However, as the rebuttal deadline is approaching, we kindly request a prompt response based on the updated paper content and ask for a reconsideration of your evaluation score. Thank you for your support!
</content>
</thread_object>

</thread>


Metareview: