PaperlayerView exact revision on arXiv

Source-linked AI summary

GraphMAS: A Systematic Benchmark of Multi-Agent Coordination for Graph Learning

Jiayi Yang, Yifang Chen, Yuanfu Sun, Xinyan Ge, Qiaoyu Tan

arXiv:2609.39777v1cs.LG

TL;DR

GraphMAS addresses the limited evidence on whether and how specialized agents should coordinate for graph learning, where useful graph perspectives vary by instance. It benchmarks coordination strategies over a shared specialist pool and finds that structured, adaptive coordination can improve performance without relying on richer interaction; coordination can also be learned and transfer to held-out graphs.

  • Problem

    LLM-based graph learning primarily relies on single-agent reasoning, while multi-agent coordination has mostly been studied in general reasoning, leaving open whether specialized agents help graph learning and how to coordinate them.

    Source: §1 · pp. 1–2

  • Method

    GraphMAS benchmarks seven coordination methods across four paradigms, coordinating a shared pool of graph specialists along interaction and runtime-adaptivity dimensions.

    Source: §1 · pp. 2–3

  • Results

    Across tasks, coordinating complementary specialists can outperform individual specialists and strong single-agent systems, while richer interaction does not reliably help and adaptive coordination offers a favorable accuracy–efficiency trade-off.

    Source: §1 · p. 3, §5 · p. 9

  • Takeaways & Limitations

    The value of multi-agent graph reasoning lies in how complementary perspectives are decomposed, specialized, and selectively coordinated, rather than simply adding agents or communication.

    Source: §5 · p. 9

Abstract

from arXiv · show

LLM-based multi-agent systems coordinate specialized reasoning through aggregation, interaction, and adaptive control, yet their potential for graph learning remains unexplored. Graph learning is a natural setting for such systems because useful evidence may arise from heterogeneous local, long-range, global structural, and semantic perspectives whose relevance varies across instances. Existing LLM-based graph learning approaches primarily rely on single-agent reasoning, while multi-agent coordination has been studied mainly in general reasoning settings. Consequently, it remains unclear whether multiple specialized agents can improve graph learning and how coordination strategies should be designed and evaluated. To address this gap, we introduce GraphMAS, a systematic benchmark of multi-agent coordination for graph learning. GraphMAS builds a shared pool of graph reasoning specialists and organizes coordination along two dimensions, inter-agent interaction and runtime adaptivity, yielding four paradigms and seven representative coordination methods. Under a unified protocol, we evaluate these methods across seven text-attributed graphs, three domains, and two graph learning tasks. We find that heterogeneous graph perspectives are complementary, and that coordinating specialists improves over individual specialists and single-agent graph reasoning, with gains from decomposing reasoning across specialists rather than from broader evidence access alone. However, richer inter-agent interaction does not reliably help, whereas instance-adaptive specialist selection yields the strongest accuracy-efficiency trade-off. We further show that coordination can be learned over a fixed specialist pool and transfers to held-out graphs. GraphMAS therefore provides a controlled evaluation framework and empirical principles for understanding when and how multi-agent coordination benefits graph learning.

1 INTRODUCTION

GraphMAS addresses the lack of controlled evidence on multi-agent coordination for graph learning, where useful graph perspectives vary by instance. Its benchmark finds complementary specialists can improve reasoning, while more interaction does not reliably help and adaptive selection offers a favorable accuracy–efficiency trade-off.

1 INTRODUCTION

  • Existing LLM graph-learning approaches primarily use one reasoning agent, while multi-agent coordination has mostly been studied in general reasoning settings.A single reasoning trajectory may give complementary structural and semantic evidence uneven attention.Source: §1 · pp. 1–2
  • Specialist success varies across instances, leaving coordination headroom because another graph perspective can resolve cases missed by the best individual specialist.The oracle is correct when any specialist is correct, whereas the best specialist is selected per dataset.Source: §1 · p. 2, Figure 1 · p. 2
  • Specialists show instance-dependent complementarity, and coordination improves over individual specialists and single-agent reasoning; adaptive selection offers a favorable accuracy–efficiency trade-off.Richer inter-agent interaction does not consistently improve performance or efficiency, and methods differentiate most under specialist disagreement.Source: §1 · p. 3
  • GraphMAS benchmarks seven coordination methods across four paradigms using a shared pool of specialists and a unified evaluation protocol.The evaluation spans seven text-attributed graphs, three domains, and node classification and link prediction, with strong non-agentic, agentic, and individual-specialist baselines.Source: §1 · pp. 2–3
  • The benchmark isolates evidence allocation, role specialization, and reasoning decomposition, and examines oracle gaps, agreement-stratified performance, and cost.These analyses address whether gains arise from broader evidence access, specialist roles, or coordination.Source: §1 · pp. 2–3
  • Coordination can be optimized while keeping graph specialists fixed, and the learned coordination behavior generalizes to unseen graphs.The paper presents learned routing as an extension of the benchmark.Source: §1 · p. 3

2 RELATED WORK

Prior work studies multi-agent coordination mainly in general reasoning and LLM-based graph learning mainly through single-agent or task-specific approaches. GraphMAS frames interaction and runtime adaptivity as distinct coordination choices and provides a shared overview of this design space.

2 RELATED WORK

  • General multi-agent systems vary in information exchange and execution control, making interaction and runtime adaptivity distinct dimensions.Fixed workflows may exchange intermediate outputs, while adaptive selection can preserve independent reasoning.Source: §2 · p. 3
  • LLM-based graph-learning methods integrate graph structure and text through tuning, prompting, exploration, or retrieval, while prior specialized-agent studies target particular architectures and tasks.Systematic comparisons across coordination paradigms and graph-learning tasks remain limited.Source: §2 · p. 3
  • Figure 2 presents GraphMAS as a shared pool of graph reasoning specialists coordinated across paradigms organized by interaction and runtime adaptivity.Its timeline places prior LLM-based graph learning alongside general multi-agent systems.Source: Figure 2 · p. 4

3 GRAPHMAS

GraphMAS studies node classification and link prediction using a shared pool of specialists with distinct structural and semantic evidence scopes. It represents coordination as execution structure, distinguishes interaction from runtime adaptivity, and instantiates representative methods across their combinations.

3 GRAPHMAS

  • GraphMAS provides a shared framework for studying multi-agent coordination in graph learning, with the specialist pool and coordination space developed in subsequent sections.The framework is illustrated in Figure 2.Source: §3 · p. 4

3.1 PRELIMINARIES

  • The benchmark considers node classification, which predicts a target node’s label, and link prediction, which predicts whether an edge exists between two nodes.A prediction instance is a target node or node pair, and its ground-truth label is unavailable during inference.Source: §3.1 · p. 4

3.2 GRAPH SPECIALISTS

  • Four specialists cover proximal and distal neighborhoods, graph-wide structural relevance, and semantic affinity, with a common interface returning predictions and textual reasoning.The same evidence scope is applied to both endpoints in link prediction; optional coordination context lets a specialist consider other responses while keeping graph evidence within its assigned perspective.Source: §3.2 · pp. 4–5

3.3 THE COORDINATION DESIGN SPACE

  • A typed coordination graph represents specialist and coordination-module invocations, with message edges encoding information flow and control edges encoding execution decisions.Interaction is defined by whether one specialist’s response enters another’s reasoning context; runtime adaptivity concerns model-generated decisions about execution.Source: §3.3 · p. 5

3.4 INSTANTIATED COORDINATION METHODS

  • GraphMAS instantiates seven methods across four paradigms, varying specialist participation, communication, adaptation, and final decision-making.Methods include independent specialist voting or aggregation, fixed interactive workflows, and dynamic routing or interaction methods such as DyLAN and Graph of Agents.Source: §3.3 · p. 5, §3.4 · p. 6
  • Dynamic Independent routing selects specialists sequentially or stops, while Dynamic Interactive methods can revise responses using peers and adapt participation or communication.DyLAN uses agreement-based stopping and ranking to retain specialists; Graph of Agents constructs a response-conditioned graph, passes messages, and uses a meta-agent to synthesize responses.Source: §3.4 · p. 6

4 EXPERIMENTS

The experiments compare seven coordination methods with single-agent and individual-specialist baselines across graph-learning tasks. They examine performance, sources of gains, efficiency, and learned coordination.

4.1 EXPERIMENTAL SETUP

  • The benchmark evaluates node classification and link prediction on seven text-attributed graph datasets spanning citation, e-commerce, and social domains.Baselines include direct LLM reasoning, agentic graph methods, four individual specialists, and seven coordination methods.Source: §4.1 · p. 7

4.2 PERFORMANCE OF MULTI-AGENT GRAPH LEARNING (RQ1)

  • On LP, all seven multi-agent methods beat the strongest individual specialist, improving the best average from 74.3% to 80.2%; on NC, six improve and one matches it, raising the best average from 67.7% to 69.1%.Multi-agent methods also achieve better overall ranks, 3.3–8.1 versus 8.4 for the strongest single-agent method.Source: §4.2 · p. 8

4.3 SOURCES OF MULTI-AGENT GAINS (RQ2)

  • Combining agent-specific evidence with specialized roles yields the strongest results—80.0% on LP and 67.7% on NC—whereas either component alone is less effective.Specialized roles alone with shared evidence reduce LP accuracy from 73.0% to 69.9%.Source: §4.3 · p. 8, Table 3 · p. 8
  • With the same four evidence sources, multi-agent reasoning reaches 80.0% on LP and 67.7% on NC, versus 74.6% and 65.6% for one agent reasoning over them jointly.The comparison attributes gains to decomposing complementary perspectives across separate reasoning processes, beyond access to broader evidence alone.Source: §4.3 · p. 8, Table 3 · p. 8

4.4 EFFECTIVENESS AND EFFICIENCY OF COORDINATION (RQ3)

  • Adaptive Routing has the best overall average rank (3.3) and highest LP accuracy (80.2%), and is the only method on the accuracy–cost Pareto frontier; interaction-heavy methods cost more without corresponding accuracy gains.Static-independent LLM Aggregation remains competitive at 80.0% LP accuracy, while SOP Workflow and Multi-Agent Debate do not consistently outperform independent coordination.Source: Figure 3 · p. 8, §4.4 · p. 8
  • On LP, the accuracy range across methods grows from 4.4 points under unanimous specialist agreement to 19.3 points when agreement is at most 2/4; Adaptive Routing reaches 69.4% versus 50.1% for Multi-Agent Debate.NC shows the same pattern on a smaller scale, with the range increasing from 1.0 to 5.0 points; disagreement marks where the choice of coordination mechanism matters most, not guaranteed gains.Source: §4.4 · p. 9, Figure 4 · p. 9

4.5 EXTENDING GRAPHMAS TO LEARNED COORDINATION (RQ4)

  • PPO improves average LP accuracy from 79.6% to 87.3% and NC accuracy from 68.4% to 72.4% while keeping the four specialists frozen.The reported gains therefore reflect improved coordination rather than changes in specialist capability.Source: §4.5 · p. 9
  • The learned router raises average LP accuracy on Reddit, Sports, and arXiv-23 from 78.5% to 85.1%, and outperforms AgentGL-7B-GRPO on all seven datasets.These include held-out graphs beyond those used to train the router.Source: §4.5 · p. 9

5 CONCLUSION

The conclusion frames multi-agent graph learning as a coordination-design problem rather than a matter of scaling agents. GraphMAS offers a controlled framework and common foundation for studying how specialist reasoning can exploit complementary graph evidence.

5 CONCLUSION

  • The paper’s conclusion emphasizes decomposing, specializing, and selectively coordinating complementary graph perspectives over simply adding agents or communication.It reports that structured specialist reasoning can outperform individual specialists and strong single-agent systems, while adaptive coordination can reduce specialist computation.Source: §5 · p. 9
  • GraphMAS is presented as a controlled framework and common foundation for developing and evaluating coordination mechanisms across graph reasoning settings.The benchmark code and implementation, dataset, training, baseline, and prompt details are identified as reproducibility resources.Source: §5 · p. 9, REPRODUCIBILITY STATEMENT · p. 10
  • Generative AI tools were used only to proofread and improve manuscript readability, and the authors take responsibility for the final content.Source: AI USE STATEMENT · p. 10

A DATASET DETAILS

GraphMAS evaluates seven text-attributed graphs across citation, e-commerce, and social domains on node classification and link prediction. Evaluation uses fixed, shared samples of test instances, with link-prediction edges withheld from graph evidence.

A DATASET DETAILS

  • The benchmark covers seven text-attributed graphs from citation, e-commerce, and social domains, with node classification and link prediction tasks.Node classification predicts node labels; link prediction predicts whether an edge exists between a node pair.Source: A DATASET DETAILS · p. 13
  • Evaluation randomly samples 1,000 test instances per dataset–task pair, or uses all available instances when fewer qualify.The same sampled instances are used across methods; link-prediction sets are balanced between positive and negative pairs.Source: A DATASET DETAILS · p. 13
  • All evaluation edges are removed from the exposed graph so retrieval cannot directly reveal queried links.Positive link-prediction pairs are sampled from held-out edges, while negative pairs are sampled uniformly from unconnected node pairs.Source: A DATASET DETAILS · p. 13

B.1 GENERAL AND TRAINING-FREE METHODS

The methods use shared evaluation and inference controls, while the learned router selects specialists under a limited call budget. Router training jointly rewards accurate predictions and efficient specialist use.

B.1 GENERAL AND TRAINING-FREE METHODS

  • Accuracy is the primary metric, and training-free methods use the same Qwen2.5-32B-Instruct checkpoint and decoding temperature of 0.7.Proximal and distal retrieval return three nodes from at most 200 candidates; semantic retrieval supplies three of the top ten neighbors, and global relevance uses APPNP-approximated PPR.Source: §B.1 · pp. 13–14
  • Specialists can make at most four search calls per instance, while Adaptive Routing can invoke at most four specialists before synthesis.Multi-Agent Debate runs at most two revision rounds; DyLAN and Graph of Agents retain three specialists.Source: §B.1 · p. 14

B.2 TRAINING DETAILS OF THE LEARNED ROUTER

  • The router observes target information, label space, prior specialist reports, and remaining call budget, then invokes a specialist or predicts.It makes at least one and at most four specialist calls; the four graph specialists remain frozen.Source: §B.2 · p. 14
  • Router reward jointly encourages prediction accuracy and efficient specialist use, rewarding call efficiency only on correct trajectories.This prevents reducing cost through premature stopping at the expense of accuracy.Source: §B.2 · p. 14
  • For each task, training uses 3,000 instances per graph from four in-domain graphs, with 256 disjoint validation instances per graph.Specialist responses are precomputed and replayed during training; frozen specialists are invoked online at evaluation.Source: §B.2 · p. 15
  • The router is initialized from Qwen2.5-7B-Instruct and optimized with PPO; checkpoints are selected on in-domain validation accuracy.Held-out transfer graphs are excluded from training and model selection.Source: §B.2 · p. 15

B.3 IMPLEMENTATION OF LEARNED BASELINES

Specialists show substantial complementary strengths, while the learned-system comparison uses held-out graphs and shared test instances. GraphMAS has greater inference-time model capacity than the learned baselines, so external-baseline comparisons are system-level references.

B.3 IMPLEMENTATION OF LEARNED BASELINES

  • Learned methods are evaluated on in-domain test instances and on Reddit, sports, and arXiv-23, which are held out from training and model selection.Transfer graphs receive no fine-tuning or adaptation, and methods share the same 1,000 test instances per dataset.Source: §B.3 · p. 15
  • GraphMAS and learned baselines share the Qwen2.5-7B-Instruct trainable backbone, but GraphMAS additionally queries four frozen Qwen2.5-32B-Instruct specialists at inference.Thus, trainable parameters match but inference-time model capacity does not; external-baseline comparisons are treated as system-level references.Source: §B.3 · p. 15
  • Baselines include conventional GNNs, trained LLM graph-learning methods, and AgentGL-7B-GRPO; learned GraphMAS is also compared with training-free routing under matched conditions.The routing comparison holds backbone, specialists, retrieval settings, temperature, and test instances constant.Source: §B.3 · p. 15

C.1 SPECIALIST COMPLEMENTARITY AND ORACLE GAP

  • The specialist oracle exceeds the best individual specialist by an average 16.9 percentage points on link prediction and 10.0 points on node classification.The oracle counts an instance as correct if any specialist is correct; the best specialist is selected separately for each dataset.Source: §C.1 · p. 16, Table 7 · p. 16

C.2 ADDITIONAL RESULTS FOR BASELINE VARIANTS

The evaluated variants alter neighborhood retrieval and aggregation choices. GraphSearch-R trails GraphSearch-F, while GoA-max improves link-prediction accuracy over GoA-mean but neither alternative surpasses the strongest multi-agent method.

C.2 ADDITIONAL RESULTS FOR BASELINE VARIANTS

  • GraphSearch-R recursively expands neighborhoods, while GraphSearch-F flexibly retrieves across local and global neighborhoods.GoA-mean aggregates refined responses; GoA-max selects the refined response of the most influential agent.Source: §C.2 · p. 16
  • GoA-max raises average link-prediction accuracy from 78.8% for GoA-mean to 79.7%, approaching LLM Aggregation at 80.0% and Adaptive Routing at 80.2%.Both GoA variants achieve 68.2% average node-classification accuracy.Source: §C.2 · p. 16
  • GraphSearch-R has lower average accuracy than GraphSearch-F on both tasks, and neither alternative exceeds the strongest multi-agent method on either task.The reported averages are across the seven datasets.Source: §C.2 · p. 16

C.3 DETAILED RESULTS FOR SPECIALIST DESIGN

The specialist-design analysis varies evidence allocation and role conditioning, compares single-agent with multi-agent reasoning over the same evidence, and examines coordination under different levels of specialist agreement.

C.3 DETAILED RESULTS FOR SPECIALIST DESIGN

  • The specialist-design ablation crosses shared versus agent-specific evidence with generic versus specialized roles, holding agent count, backbone, budget, and coordination fixed.It evaluates all seven coordination methods on 100 sampled instances per dataset and task.Source: §C.3 · pp. 16–17, Table 9 · p. 17

C.4 DETAILED RESULTS FOR REASONING DECOMPOSITION

  • Table 10 compares per-dataset accuracy for single-agent reasoning over all four evidence sources with multi-agent LLM Aggregation on the same 100 sampled instances.The single agent receives all sources jointly in one reasoning context; multi-agent reasoning uses LLM Aggregation.Source: §C.4 · p. 17

C.5 COORDINATION UNDER SPECIALIST DISAGREEMENT

  • Coordination has little effect under unanimous specialist agreement, while method differences grow as agreement decreases.Agreement is the largest number of specialists making the same initial prediction.Source: §C.5 · p. 17

C.6 ADDITIONAL BACKBONE ABLATION

The backbone ablation tests whether multi-agent gains persist with smaller and different-family LLMs, using a compact subset of datasets and sampled instances.

C.6 ADDITIONAL BACKBONE ABLATION

  • The ablation uses Reddit, Sports, and Computers, randomly sampling 100 instances per dataset and task because of computational resource constraints.It tests Qwen2.5-7B and GLM-4-32B alongside the main Qwen2.5-32B setting.Source: §C.6 · p. 17
  • Adaptive Routing leads both tasks under both backbones; versus the strongest single-agent baseline, it gains 6.4 NC and 7.3 LP points with Qwen2.5-7B.The reported values are three-dataset averages.Source: §C.6 · pp. 17–18, Table 12 · p. 18
  • For GLM-4-32B, the reported results show 8.0 points on NC and 12.0 points on LP, indicating that graph-specialist coordination benefits are not restricted to the backbone used.Table 12 reports accuracy (%) using 100 randomly sampled instances per dataset and task.Source: §C.6 · p. 18, Table 12 · p. 18

C.7 COMPUTATIONAL COST RESULTS

The section defines per-question cost measures and documents the core prompts used to reproduce GraphMAS specialists and coordination methods.

C.7 COMPUTATIONAL COST RESULTS

  • Per-question costs cover specialist operations, LLM calls, input and output tokens, and allocated A100 GPU-seconds for node classification and link prediction.Operations count rollouts and standalone revision, message, or peer-judgment attempts; token totals include repeated histories and discarded responses but exclude retrieval encoder tokens. GPU-seconds include inference, retrieval, queueing, and accounting overhead, but exclude startup, warmup, pre-allocation waiting, and precomputed corpus embeddings.Source: §C.7 · pp. 18–19, Table 13 · p. 19

D PROMPT TEMPLATES

  • Core prompt templates omit mechanically inserted task inputs, candidate labels, and output schemas; blue text marks method-specific content instantiated at inference time.Majority Vote is omitted because it requires no additional LLM prompt.Source: D PROMPT TEMPLATES · p. 19

D.1 GRAPH REASONING SPECIALISTS

  • Graph specialists share a reasoning protocol and differ only in their admissible retrieval scope.Table 14 summarizes the shared prompt and role-specific search instructions.Source: §D.1 · p. 19, Table 14 · p. 20

D.2 STATIC COORDINATION

  • LLM Aggregation combines independent responses, whereas SOP and Debate expose specialists to intermediate peer judgments.Aggregation uses a separate coordinator; SOP and Debate append peer information to the specialist prompt.Source: §D.2 · p. 19, Table 15 · p. 20

D.3 ADAPTIVE ROUTING

  • Adaptive Routing consults specialists sequentially, adapting participation and stopping to the instance based on collected specialist reports.Newly invoked specialists remain independent of the routing history.Source: §D.3 · p. 20, Table 16 · p. 21

D.4 DYLAN

  • In the DyLAN instantiation, ranking and revision occur only when initial specialist responses fail the early-agreement criterion.Revision reuses initially retrieved evidence and performs no additional graph retrieval.Source: §D.4 · p. 20, Table 17 · p. 21

D.5 GRAPH OF AGENTS

  • Graph of Agents uses peer scoring, bidirectional message passing, and final pooling.Message-passing calls reuse the specialists’ initially retrieved graph evidence.Source: §D.5 · p. 20, Table 18 · p. 21
Loading 2609.39777v1…