Skip to content

GraphMaster: Automated Graph Synthesis via LLM Agents in Data-Limited Environments

🕒 Published (v1): 2025-01-01 · Source: NeurIPS · Venue: NeurIPS 2025 · link

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

GraphMaster is a four-agent LLM framework (Manager, Perception, Enhancement, Evaluation) that synthesizes semantically rich, structurally valid text-attributed graphs (TAGs) in data-scarce settings to bootstrap Graph Foundation Model training. By framing synthesis as a RAG problem with iterative refinement, it overcomes context-window limits, hallucination, and structural inconsistency that block direct LLM application to graph generation. It sets new state-of-the-art on six data-limited graph benchmarks across four GNN architectures.

Problem

Graph Foundation Models are bottlenecked by scarce large-scale graph corpora. Traditional synthesis methods (edge/node/graph-level mixup) cannot generate semantically coherent textual node attributes. Naive LLM application to graph synthesis fails due to: (1) context-window constraints when graphs are large, (2) hallucination producing structurally inconsistent nodes, and (3) inability to jointly preserve topology and text semantics, especially in few-example regimes.

Method

GraphMaster casts graph synthesis as a RAG pipeline orchestrated by four specialized LLM agents in a closed loop:

  • Manager Agent: reads an environmental status report from the Perception Agent and selects a synthesis mode (semantic vs. topological) by optimizing a multi-objective utility over semantic coherence, structural integrity, and class balance (Eq. 5). Controls iteration state transitions.
  • Perception Agent: retrieves a bounded knowledge subgraph K (|K|=N, constrained to LLM context). Uses semantic-enriched modularity maximization (Eq. 6) to detect communities, mode-adaptive seed selection (minority-class or low-variance community), then Personalized PageRank diffusion with controlled stochasticity (Eq. 8) to sample a diverse, representative subgraph.
  • Enhancement Agent: generates new nodes and edges conditioned on K and the environmental report. Semantic mode uses autoregressive token generation (Eq. 10); topological mode estimates edge probabilities via a learned sigmoid over semantic similarity, neighborhood overlap, and degree (Eq. 11). New nodes are capped at M%=15% of K per iteration.
  • Evaluation Agent: scores each generated node against a dynamically adjusted quality threshold τ (Eq. 13) and checks convergence via temporal quality-gradient analysis (Eq. 14). Passes only accepted nodes back; otherwise triggers another iteration.

The backbone LLM is QwQ-32B; all four agents are realized through prompted calls to the same model with role-specific instructions.

Key Contributions

  • First multi-agent framework explicitly designed for text-attributed graph synthesis in data-limited environments, framed as a hierarchical RAG paradigm.
  • Six standardized "Sub" data-limited variants of Cora, Citeseer, Wikics, Arxiv2023, History, and Children benchmarks for reproducible evaluation.
  • Dual-perspective interpretability assessment: expert human evaluation (Tscore) + Grassmann manifold-based semantic coherence scoring, with strong human–algorithm correlation (r=0.78, p<10⁻⁵).
  • Ablation confirming each specialized agent is load-bearing (removing Perception −5.2%, removing Evaluation −4.1% average accuracy).

Results

  • Overall (GCN, Table 1): GraphMaster vs. best prior baseline on each dataset:
  • SubCora: 93.7% Acc vs. 91.2% (LLM4RGNN)
  • SubCiteseer: 88.3% Acc vs. 84.5% (Synthesis-LLM)
  • SubWikics: 87.9% Acc vs. 84.9% (GAG / Mixed-LLM tie)
  • SubHistory: 92.6% Acc, 63.4% F1 vs. 89.4% Acc, 55.8% F1 (Synthesis-LLM)
  • SubArxiv2023: 87.9% Acc, 66.3% F1 vs. 81.4% Acc, 62.3% F1 (Mixed-LLM)
  • SubChildren: 68.8% Acc, 47.8% F1 vs. 60.9% Acc, 40.1% F1 (Synthesis-LLM)
  • Structural fidelity (Children): KS statistic 0.357 (p=0.059, no significant difference), clustering coefficient similarity 0.835, label homogeneity similarity 0.988.
  • Interpretability: Tscore=0.92 vs. Mixed-LLM 0.66 and Synthesis-LLM 0.59.
  • LLM sensitivity: QwQ-32B outperforms Qwen-32B, DeepSeek-R1-32B, LLaMA-33B by 1.5–2.3%; architecture/pretraining matters more than parameter count.
  • Hyperparameters: N=30 and M=15% are optimal; larger N or M degrades quality.

Limitations

  • Relies on a single large reasoning model (QwQ-32B on 8×A100s); not lightweight or accessible at small compute budgets.
  • Evaluated only on node-classification downstream tasks; graph-level and link-prediction tasks are not tested.
  • The four-agent pipeline incurs iterative LLM calls; wall-clock cost for large or densely iterated graphs is not reported.
  • Convergence criteria depend on LLM self-assessment (LLMgoal), which may be unreliable or inconsistent across domains outside the tested benchmarks.
  • Limited baselines for LLM-based TAG synthesis; two key baselines (Mixed-LLM, Synthesis-LLM) were author-constructed.

Relevance to Agentic AI / LLM Agents

GraphMaster is a concrete instantiation of task decomposition in multi-agent systems: each agent owns one cognitive subtask (planning, retrieval, generation, verification) and the collective loop produces outputs that no single LLM pass can reliably deliver. The RAG framing — where retrieval shapes generation scope and an evaluator gates output quality — is a generalizable agentic pattern directly applicable to other structured-data generation settings. The iterative convergence loop with an adaptive quality threshold exemplifies self-refinement architectures studied in the broader LLM-agent literature. For researchers tracking agentic AI, this paper provides an empirically validated blueprint for using agent specialization to overcome fundamental LLM constraints (context window, hallucination) in a non-text domain.