PaperlayerView exact revision on arXiv

Source-linked AI summary

LLM-Based Multi-Agent Systems are Scalable Graph Generative Models

Jiarui Ji, Runlin Lei, Jialing Bi, Zhewei Wei, Xu Chen, Yankai Lin, Xuchen Pan, Yaliang Li, Bolin Ding

arXiv:2410.09824v6cs.CL

TL;DR

Existing graph-generation methods face limits in realism, generalization, and growth beyond observed datasets. GAG simulates text-attributed actor-item interactions with LLM agents; its generated graphs exhibit reported network properties and improvements in graph expansion, text-structure alignment, and scale.

  • Problem

    Rule-based graph generators lack realism and generalizability, while deep-learning methods require large training datasets and struggle to generate larger graphs that retain macroscopic properties.

    Source: §1 · p. 1

  • Method

    GAG uses LLM-based agents to simulate actor-item interactions and temporal graph growth from a seed graph, with S-RAG and parallel acceleration.

    Source: §1 · p. 2

  • Results

    GAG graphs exhibit seven real-world macroscopic characteristics, exceed the best baseline by 11% on specific graph-expansion metrics, and scale to nearly 100,000 nodes or 10 million edges.

    Source: §5 · p. 8

  • Takeaways & Limitations

    Node-classification benchmarking indicates that GAG captures intricate text-structure correlations, with an average 1.45 improvement in accuracy retention over baseline methods.

    Source: §4.2 · p. 8

    GAG is currently suitable only for social networks and is not directly applicable to domains such as point clouds, traffic networks, or molecular graphs.

    Source: Limitations · p. 9

Abstract

from arXiv · show

The structural properties of naturally arising social graphs are extensively studied to understand their evolution. Prior approaches for modeling network dynamics typically rely on rule-based models, which lack realism and generalizability, or deep learning-based models, which require large-scale training datasets. Social graphs, as abstract graph representations of entity-wise interactions, present an opportunity to explore network evolution mechanisms through realistic simulations of human-item interactions. Leveraging the pre-trained social consensus knowledge embedded in large language models (LLMs), we present GraphAgent-Generator (GAG), a novel simulation-based framework for dynamic, text-attributed social graph generation. GAG simulates the temporal node and edge generation processes for zero-shot social graph generation. The resulting graphs exhibit adherence to seven key macroscopic network properties, achieving an 11% improvement in microscopic graph structure metrics. Through the node classification benchmarking 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 https://github.com/Ji-Cather/GraphAgent.

1 Introduction

Existing graph generators struggle to combine realistic network growth, scale, and text-rich structure. GAG instead simulates human-item interactions with LLM-based agents, producing graphs with reported structural, text-alignment, and scalability results.

1 Introduction

  • Rule-based generators target specific macroscopic properties, while deep-learning methods struggle to scale beyond observed datasets and maintain macroscopic properties as networks grow.A single model for all entity interactions also misses the underlying process that forms social graphs.Source: §1 · p. 1
  • Human-item interaction dynamics drive social-network evolution, and LLM-based agents can simulate complex human activities and decision-making.The introduction frames this as an alternative to preset rules or fitting training data alone.Source: §1 · pp. 1–2
  • 11%: GAG surpasses the best-performing baseline on specific graph-expansion evaluation metrics, while improving average accuracy retention by 1.45 in node-classification benchmarking.The framework also generates graphs with seven real-world structural characteristics and supports nearly 100,000 nodes or 10 million edges, with a minimum 90.4% speed-up.Source: §1 · p. 2
  • GAG models actor-item interactions using LLM agents, expanding items from a real-world seed graph and simulating network growth with S-RAG and parallel acceleration.It generates diverse graphs by folding the affiliation network according to node and edge or relation types.Source: §1 · p. 2

2 Related Work

Prior graph-generation approaches use hand-crafted rules, training-based deep learning, or simulations of LLM-driven agents. The paper situates GAG against limits in scale, generalization, and realism across these approaches.

2 Related Work

  • Rule-based methods capture selected network properties, while deep-learning models require large-scale training data and struggle with out-of-distribution graphs and new contexts.Autoregressive methods predict edges incrementally; one-shot methods generate whole graphs at once.Source: §2 · p. 2
  • The related work contrasts rule-based and learned graph generators with simulation approaches that model interactions among agents.The framework illustration shows node formulation, interaction simulation, and graph projection as its three stages.Source: §2 · p. 2, Figure 1 · p. 3
  • Earlier LLM-agent graph simulations examined scale-free or other social-graph properties, but often simplified behavior and used fewer than 100 agents.AgentScope supports large-scale simulations of simplified behavior, and the paper builds on it for more complex behaviors.Source: §2 · p. 2

3 The GAG Framework

GAG formulates dynamic text-attributed social graph generation as simulation of actor-item interactions over time. It initializes nodes from a seed graph, simulates interactions and graph growth, then projects the evolving bipartite graph into analysis graphs.

3 The GAG Framework

  • GAG is designed to generate dynamic, large-scale text-attributed graphs through simulation rather than preset rules or training processes.Its target is the evolution of an actor-item bipartite graph while preserving macroscopic and microscopic properties.Source: §3 · p. 3, §3.1 · p. 3

3.1 Problem Setup

  • The task is to grow a seed actor-item bipartite graph over K rounds, expanding actors, items, or edges while preserving graph properties.Actors and items carry textual features, and interactions form the edges.Source: §3.1 · p. 3

3.2 Node Formulation

  • GAG initializes item nodes from the current graph and uses LLM-generated role-playing profiles to instantiate actor agents; agents also keep interaction memories and active or idle states.Item text may include features such as a paper’s title, topic, and abstract, optionally with one-hop actor-item edge attributes.Source: §3.2 · p. 4

3.3 Interaction Simulation

  • S-RAG gives active actors item observations, retrieves and reranks relevant items, then simulates actions that create labeled edges and may generate new item nodes.The simulation is accelerated by running actor-item-agent groups in parallel.Source: §3.3 · pp. 4–5

3.4 Graph Projection

  • Graph projection folds the evolving bipartite graph by selected node and edge types to produce unipartite or multipartite graphs for analysis.For example, folding an author-paper graph into paper-paper citation edges yields a paper citation network.Source: §3.1 · p. 3, §3.4 · p. 5

4 Experiment

GAG is evaluated across graph structure, text–structure alignment, and scalability, using simulations in scientific, technological, and sociological settings. Results cover graph expansion, node-classification benchmarks, and graph-generation scale and efficiency.

4 Experiment

  • Experiments span scientific author–paper, technological user–movie, and sociological user–tweet interactions, evaluating graph structure, text features, and scalability.The evaluation compares macro- and micro-level structure, uses node classification for textual features, and assesses generation scale and efficiency.Source: §4 · p. 6

4.1 Graph Structure Alignment

  • GAG's citation, author-citation, and action networks follow power-law degree distributions, with α ∈[1.90, 2.16] under the Dk < 0.1 criterion.The degree distribution is shown on a log-log scale.Source: §4.1 · p. 6, Figure 2 · p. 6
  • Generated follow, friend, and action networks have higher average clustering than random graphs; their effective diameter decreases over time, matching the trend in CAIDA.The decreasing-diameter trend is shown for 30 simulation rounds.Source: §4.1 · pp. 6–7, Table 1 · p. 7, Figure 3 · p. 7
  • Without ReRanking, effective diameter in the friend network trends upward from 2.6 to 2.96; the ablation indicates ReRanking fosters community-guided attachment.The figure compares the diameter trajectory with and without ReRanking.Source: §4.1 · p. 7, Figure 3 · p. 7
  • 11%: GAG surpasses the best-performing baseline on GEM in graph expansion; deep-learning models tend to overfit seed graphs and fail to generate power-law graphs.The comparison uses the CiteSeer graph expansion task.Source: §4.1 · p. 7, Table 2 · p. 8

4.2 Textual Feature Alignment

  • 1.45 ∆Acc average improvement across GNNs: GAG consistently outperforms baselines, with ∆Acc values ranging from 0.09 to 3.61.The node-classification benchmark evaluates preservation of text–structure correlations.Source: §4.2 · pp. 7–8, Table 3 · p. 8

4.3 Scalability of GAG

  • 97.5%: with actor count held constant, parallel runs with P > 1 reduce the time per item–actor interaction by at least this amount versus P = 1.The runtime experiment used a machine with 96 CPU cores and 376 GB of memory.Source: Table 4 · p. 8, §4.3 · p. 8
  • GAG generates nearly 100,000 nodes in the action network or 12.2 million edges in the bibliographic-coupling network.The passage contrasts this scale with existing models limited to 5,000 nodes or sparse grid graphs.Source: §4.3 · p. 8

5 Conclusion

GAG is presented as a general framework for dynamic, large-scale text-rich graph generation through human interaction simulation. Its generated graphs exhibit seven macro-level characteristics, and the framework reports improvements in graph expansion and simulation speed.

5 Conclusion

  • GAG generates dynamic, large-scale text-rich graphs through human interaction simulation.The conclusion describes the framework as a novel, general approach.Source: §5 · p. 8
  • Generated graphs exhibit seven macro-level characteristics of real-world networks, including power law, small world, and shrinking diameter.Source: §5 · p. 8
  • GAG surpasses existing graph expansion baselines by 11% on specific evaluation metrics and achieves at least 90.4% simulation speed-up.The conclusion also reports graph generation up to nearly 100,000 nodes or 10 million edges.Source: §5 · p. 8

Limitations

GAG’s implementation simulates actor–item interactions across scientific, movie-rating, and social-media settings, then projects those interactions into domain-specific graphs. Its stated limitations are opaque agent behavior and applicability currently restricted to social networks.

Limitations

  • The mechanism by which in-context learning prompts produce heterogeneous agent behavior remains unclear.The authors identify behavior interpretability as an open limitation and propose layer-level explanations as future work.Source: Limitations · p. 9
  • GAG is currently suitable only for social networks, not directly applicable to point clouds, traffic networks, or molecular graphs.The authors suggest extending the simulation to other domains as LLM capabilities develop.Source: Limitations · p. 9

A Details of GAG

  • The experiments model authors interacting with papers, reviewers with movies, and users with a Twitter-like database.These settings generate citation and collaboration, movie-rating and user-projection, and follow, friend, and action networks, respectively.Source: A Details of GAG · p. 13

A.1 Node Formulation

  • Seed graphs initialize the actor and item nodes; Citeseer and MovieLens seed scientific and movie simulations, while SoC uses LLM-generated textual features.Citeseer attributes are crawled to add missing author and article information.Source: §A.1 · p. 13

A.2 Interaction Simulation

  • S-RAG retrieves candidate feedback, reranks it by core-agent origin and agent preferences, and prompts actors to act on their observations.Nested-ACTOR groups agents under supervisors assigned across CPU cores to parallelize simulation.Source: §A.2 · p. 14

A.3 Graph Projection

  • GAG projects the evolving actor–item interactions into domain-specific graphs, including citation, movie-rating, follow, and friend networks.The bipartite graph distinguishes actor and item nodes, action edges, and textual node attributes.Source: §A.3 · p. 15

B Graph Structure Alignment

  • The macro-level alignment experiments use Llama-3-70B, while micro-level alignment uses GPT-3.5-turbo and S-RAG uses a sentence encoder.The encoder is identified as 3.Source: B Graph Structure Alignment · p. 15

B.1 Graph Structure Metrics

The section defines structural metrics for graph size, clustering, degree mixing, and connectivity distance, then reports patterns consistent with real-world networks.

B.1 Graph Structure Metrics

  • The metrics include node and edge counts, average clustering coefficient, assortativity, and effective diameter.Effective diameter is the minimum number of hops reaching a specified fraction, typically 90% or 95%, of connected node pairs.Source: §B.1 · pp. 15–16
  • Generated citation networks show negative assortativity, co-authorship networks positive assortativity, and small diameters consistent with small-world structure.Across the generated networks, effective diameter De ranges from 1.17 to 11.66; high average clustering coefficient combined with small De supports the small-world characterization.Source: §B.1 · p. 16

B.2 Macro-Level Evaluation

Macro-level evaluations report periodic degree variation, growth of a giant connected component, the friendship paradox, and a densely connected core in generated social graphs.

B.2 Macro-Level Evaluation

  • Over 90% of nodes in the friend network lie above y = x, indicating that most users have fewer friends than their friends do.The network was generated through five simulation rounds with 1e5 agents.Source: Figure 6 · p. 16, §B.2 · pp. 16, 18
  • 12.79 dB: the generated movie-rating graph’s degree has periodic variation consistent with movie release dates, exceeding the 10 dB strong-periodicity threshold.The reported degree SNR is 12.79 dB.Source: §B.2 · p. 16, Figure 4 · p. 17
  • The largest connected component’s share grows steadily over time, indicating emergence of a giant community in a network generated with 7,000 actor agents.The result is shown in Figure 5.Source: §B.2 · p. 16, Figure 5 · p. 18
  • In the follow network’s densely connected core, higher-degree nodes have higher average clustering, while effective diameter grows sublogarithmically.The core comprises the 1%–10% highest-degree nodes; the reported network uses five rounds and 1e5 agents.Source: Figure 7 · p. 18, §B.2 · p. 18

B.3 Micro-Level Evaluation

The micro-level evaluation tests structural alignment and expansion beyond training graph sizes. GAG’s expanded graphs follow a power law, with comparable MMD results and reported validity across seed sizes and quality.

B.3 Micro-Level Evaluation

  • Evaluation compares degree and clustering-coefficient MMD, spectrum and orbit-count MMD, power-law exponent α, and degree-distribution distance Dk.The expanded graph’s alignment is summarized by GEM, averaging transformed MMD metrics and Valid.Source: §B.3 · p. 18
  • α = 2.1: GAG’s expanded graphs follow a power law, achieve MMD results comparable to other models, and capture validity alongside Barabási–Albert and L-PPGN.The authors report that L-PPGN’s performance is unstable across datasets, while GAG reliably generates real-world-like structures from seed graphs of varying sizes and quality.Source: Table 11 · p. 20, §B.3 · p. 21
  • Validity requires Dk < 0.1 and a power-law exponent α in [2, 3].The authors set kmin = 2 when calculating power-law fitness for both undirected and directed graphs.Source: §B.3 · pp. 18, 20
  • The expansion evaluation trains deep-learning baselines on 160 subgraphs of 64–512 nodes and tests on 20 sampled 1,000-node subgraphs.The subgraphs are partitioned by publication timeline using CiteSeer and Cora; the test graphs come from nodes and edges after the designated time point.Source: §B.3 · p. 20
  • Larger seed graphs produce expanded graphs with higher α, and α gradually stabilizes as expanded graph size increases.The authors report this pattern for seed graphs of 100, 445, and 2,840 nodes, plotting only valid data with Dk < 0.1.Source: §B.3 · p. 20, Figure 9 · p. 21
  • With Cora as the seed graph, GAG again generates an expanded graph following a power law, with α = 2.1.The supplementary comparison also reports MMD performance comparable to other models.Source: §B.3 · p. 21

C.1 Experiment Settings

The experiment compares GAG with shuffled feature/structure controls and graphs generated by other models, using Citeseer as the corpus for textual features. It also includes GAG-generated graphs in the comparison.

C.1 Experiment Settings

  • The textual-feature alignment experiment uses Llama-3-70B, the complete Citeseer graph as the seed, and expands the citation graph to 5,000 nodes.Source: §C.1 · p. 21
  • F.shuffle randomizes seed-graph node features, while S.shuffle randomizes edges while preserving the seed graph’s edge count; SF.shuffle combines both controls.Source: §C.1 · p. 21
  • BWR.L, L-PPGN.L, BiGG.L, and GraphMaker.L pair graph structures from prior models with LLM-generated Citeseer textual features.Source: §C.1 · p. 21
  • GAG-generated graphs are included as a comparison condition.Source: §C.1 · p. 21

C.2 Ablation Study of LLM

The ablation compares LLM backbones for agents in GAG. LLaMA2-, GPT-3.5-turbo-, and GPT-4o-mini-based agents maintain seed-graph characteristics and support downstream performance transfer, unlike Qwen-2-based agents.

C.2 Ablation Study of LLM

  • The ablation compares four agent backbones: GPT-3.5-turbo, GPT-4o-mini, Llama-3-70B, and Qwen2-72B.Source: §C.2 · p. 21
  • LLaMA2-, GPT-3.5-turbo-, and GPT-4o-mini-based agents maintain seed-graph node and structural characteristics, supporting downstream performance transfer; Qwen-2-based agents do not guarantee that transfer.Source: §C.2 · pp. 21–22

D Scalability of GAG

GAG is described as generating dynamic, text-attributed graphs at scales beyond existing methods, including up to 100,000 nodes with intricate small-world structure. Runtime measurements report effects of parallelization and agent count across simulation settings.

D Scalability of GAG

  • GAG generates graphs with up to 100,000 nodes and intricate small-world structure without sparsity assumptions, while supporting dynamic and text-attributed graphs at scales unmatched by the compared methods.Source: D Scalability of GAG · p. 22, Table 13 · p. 23
  • Table 14 reports the time cost, in minutes, for agents to generate one interaction datum with P = 24.Source: Table 14 · p. 22
  • At fixed P, time per interaction datum decreases as N increases; the largest observed reduction is in SC simulations grouped by paper authorship.Source: Table 14 · p. 22, D Scalability of GAG · p. 24
  • Average simulation time per round is 0.46 hours for SC and 0.30 hours for TC with thousands of agents, and 11 hours for SoC with hundreds of thousands of agents.Source: Table 15 · p. 22, D Scalability of GAG · p. 24

E Ablation Study of S-RAG

The S-RAG ablations examine recall and reranking settings, including their reported relationships with generated-network structure. The later sections describe user control through simulation parameters and illustrate citation-network formation as an interpretable sequence of agent actions.

E Ablation Study of S-RAG

  • The S-RAG ablation varies search and reranking settings under SoC simulation with equal numbers of simulation rounds, and adds the largest-connected-component share as a structural metric.Source: E Ablation Study of S-RAG · p. 24

E.1 Recall Stage

E.2 Reranking Stage

  • Increasing the hub rate correlates with a larger largest-connected-component share, while increasing Nf raises clustering coefficient; friend filters have the strongest reported effect, followed by topic and follow.Source: §E.2 · p. 24, Table 17 · p. 25, Table 18 · p. 26
  • Fine ranking applies scenario-specific filters based on whether content relates to followed agents, friends, or topics of interest.Source: §E.2 · p. 24

F Human Interface Control

  • The control agent translates user instructions into a control profile; hub rate, Nr, Nf, and agents per round are linked respectively to hub share, degree distribution, clustering coefficient, and simulation time.Source: F Human Interface Control · p. 25

F.1 Case Study

  • In the citation-network case study, agents draft papers, search stored papers for relevant literature, then select and cite papers with justifications, making each citation edge correspond to an agent’s citation action.Source: §F.1 · p. 27, Figure 11 · p. 27
Loading 2410.09824v6…