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 that synthesizes text-attributed graph (TAG) data in data-limited settings by decomposing the task into retrieval, generation, and evaluation sub-tasks executed in a closed-loop RAG pipeline. It addresses the dual failure modes of traditional graph augmentation (no semantic richness) and naive LLM application (context overflow, hallucination, structural incoherence). On six benchmark datasets, it consistently outperforms all prior TAG synthesis baselines.

Problem

Graph Foundation Models (GFMs) are bottlenecked by scarce large-scale graph corpora. Traditional synthesis methods (edge/node/graph-level mixing) manipulate structure without generating semantically coherent textual node attributes. Direct LLM application fails due to context window overflow on full graphs, hallucination, and inability to maintain structural consistency during generation.

Method

GraphMaster frames graph synthesis as iterative RAG: \(G_{\text{new}} = \Psi_{\text{RAG}}(G, Q, R, A_{\text{retrieve}}, A_{\text{generate}}, A_{\text{evaluate}})\). Four specialized agents run in a closed feedback loop:

  1. Manager Agent — selects synthesis mode \(M_t \in \{\text{semantic}, \text{topological}\}\) by maximizing a multi-objective utility \(\omega_t^* = \arg\max_{\omega}[\lambda_1 U_{\text{sem}} + \lambda_2 U_{\text{struct}} + \lambda_3 U_{\text{bal}}]\) with adaptive weights updated via gradient ascent on synthesis progress.

  2. Perception Agent — retrieves a context-bounded knowledge subgraph \(K_t\) via: (a) semantic-aware community detection using a modularity function \(Q_{\text{sem}}\) that blends cosine similarity and degree terms; (b) mode-adaptive seed selection (low-variance communities for semantic mode, minority-class nodes for topological); (c) Personalized PageRank diffusion with mode-conditional teleportation to sample \(|K_t| = N\) nodes within LLM context limits.

  3. Enhancement Agent — generates new nodes autoregressively conditioned on \(K_t\) (Eq. 10) and estimates edge probabilities using a sigmoid over semantic similarity, neighborhood overlap, and degree terms (Eq. 11), always producing both attributes and connections regardless of mode.

  4. Evaluation Agent — scores each candidate node \(v_s\) against an adaptive threshold \(\tau_t\) updated by quality gradient, accepts the subset \(V^t_{\text{accepted}}\), and signals convergence when \(\max_{j}|{\bar{F}_t - \bar{F}_{t-j}}| < \epsilon\) and the Manager's goal check passes.

The base LLM is QwQ-32B; context subgraph size \(N=30\), generation budget \(M\%=15\%\) per iteration.

Key Contributions

  • First multi-agent RAG framework specifically for TAG synthesis under data-limited conditions.
  • Six new "Sub" benchmark variants (SubCora, SubCiteseer, SubWikics, SubHistory, SubArxiv2023, SubChildren) designed to stress-test synthesis under realistic data scarcity.
  • Dual interpretability assessment: expert human evaluation combined with Grassmannian manifold-based geometric analysis of semantic coherence.
  • State-of-the-art node classification accuracy/F1 across all six datasets and four GNN architectures (GCN, JKNET, GraphSAGE, GAT).

Results

  • GCN on SubCora: GraphMaster 93.7±1.0 Acc / 92.5±1.0 F1 vs. best baseline (LLM4RGNN) 91.2±0.6 / 88.8±1.1.
  • GCN on SubCiteseer: 88.3±0.9 / 87.7±1.1 vs. Synthesis-LLM 84.5±1.0 / 82.7±1.1.
  • GCN on SubWikics: 87.9±0.8 / 86.8±0.9 vs. GAG/Mixed-LLM ~84.9.
  • GCN on SubHistory: 92.6±1.3 Acc / 63.4±1.4 F1 vs. Synthesis-LLM 89.4 / 53.4.
  • GCN on SubArxiv2023: 87.9±1.3 / 66.3±1.5 vs. Synthesis-LLM 81.0 / 62.3.
  • GCN on SubChildren: 68.8±1.4 / 47.8±1.3 vs. Synthesis-LLM 60.9 / 40.1.
  • KS statistic between original and synthesized degree distributions on Children: 0.357 (p=0.059, no significant difference); clustering coefficient similarity 0.835.
  • Several classic synthesis baselines (GraphSmote, G-Mixup, IntraMix) fall below the no-synthesis baseline, confirming semantic degradation under Sentence-BERT embeddings.

Limitations

  • Relies on a single large LLM (QwQ-32B) for all four agents via iterative role-switching; inference cost on 8×A100 GPUs is high and not ablated against simpler configurations.
  • Convergence criterion mixes LLM-judged goal attainment with a numeric gradient threshold, making reproducibility dependent on LLM stochasticity.
  • \(N=30\) subgraph context cap is a hard constraint; performance on very dense or heterogeneous graphs where 30 nodes are insufficient to capture structure is not discussed.
  • Evaluation is limited to node classification on TAGs; applicability to link prediction, heterogeneous graphs, or non-text-attributed graphs is untested.
  • The "Sub" benchmark variants are introduced by the authors themselves, making independent baseline comparisons harder.

Relevance to Harnesses / Meta-Harnesses

GraphMaster is a direct instance of a domain-specific multi-agent harness: a Manager agent acts as a meta-cognitive controller that orchestrates specialized sub-agents through an explicit state machine, adaptively selecting strategies and routing tasks in a closed feedback loop. The RAG-framed iterative refinement loop—where the Evaluation agent can re-trigger upstream agents until convergence—is structurally equivalent to retry/validation harness patterns seen in code-generation and scientific workflows. The explicit convergence detection via temporal quality gradients (Eq. 14) operationalizes a stopping criterion that harness designers commonly need. This paper provides a concrete, published template for multi-agent harnesses that blend graph-algorithmic retrieval with LLM generation under tight context budgets.