PaperlayerView exact revision on arXiv

Source-linked AI summary

Multi-Agent Agentic Graph Learning via Structural Signatures

Liang Qu, Jianxin Li, Hua Wang

arXiv:2609.09565v1cs.AI

TL;DR

Existing graph reasoning methods face shared policies across heterogeneous regions and costly, order-sensitive textual serialization of graph neighborhoods. MAAGL addresses these issues with community-specific agents, separate structural and semantic evidence representations, and confidence-triggered collaboration; ablation results identify the structural signature as especially important.

  • Problem

    Existing approaches use shared reasoning policies across graph regions, while textualizing neighborhoods can break permutation invariance and increase token costs.

  • Method

    MAAGL assigns independent agents to graph communities, summarizes structural evidence with a dynamic signature, filters semantic evidence by relevance, and triggers debate when confidence is low.

  • Results

    Removing the structural signature causes the largest performance degradation, supporting the separation of structural and semantic evidence.

  • Takeaways & Limitations

    MAAGL preserves structural and semantic evidence while avoiding arbitrary neighbor ordering and excessive token costs through specialized agents and compact evidence representations.

  • Takeaways & Limitations

    The structural signature dimensions are manually specified from commonly used graph statistics rather than automatically selected for each task.

Abstract

from arXiv · show

Agentic graph learning (AGL) has recently achieved promising results on graph reasoning tasks, where an agent powered by a large language model (LLM) sequentially samples the graph as evidence to support its final prediction. Existing methods either employ a single agent or orchestrate multiple role-based agents to reason and learn over the entire graph, but both essentially rely on a shared reasoning policy across different graph regions, which can be suboptimal for graphs with heterogeneous structural and semantic patterns. Inspired by the progress of multi-agent collaboration on complex reasoning tasks, a natural remedy is to let multiple agents own different memory and collaborate; however, applying this paradigm to graphs directly faces two challenges. First, existing AGL methods typically verbalize graph structures into natural-language descriptions for LLM agents, making the reasoning process sensitive to the ordering of structural information and thereby breaking the permutation-invariant nature of graphs. Second, incorporating increasingly large sampled neighborhoods leads to rapidly growing contexts. To address these challenges, this paper introduces a multi-agent agentic graph learning (i.e., MAAGL) framework. MAAGL partitions the graph into communities and assigns an independent agent to each community for region-specific specialization. MAAGL represents structural and semantic evidence separately. Structural evidence is summarized by a dynamically updated structural signature that is permutation-invariant and fixed in size, while semantic evidence is filtered to the top-k nodes ranked by relevance. Based on historical trajectories with similar signatures, agents estimate their confidence and trigger debate-style collaboration when needed. Extensive experiments on four benchmark datasets show that MAAGL outperforms SOTA AGL methods.

I. INTRODUCTION

Agentic graph learning uses LLM agents to collect graph evidence, but shared policies and textual serialization can be poorly suited to heterogeneous, unordered, and expanding graph neighborhoods. MAAGL addresses these issues by assigning agents to communities and separating compact structural signatures from relevance-filtered semantic evidence.

  • Graph learning setting: Text-attributed graphs combine relational structure with node-associated semantics, making joint learning from both information central to graph tasks.Examples include social networks, where edges encode social connections and profiles provide text, and citation networks, where papers and their textual attributes form the graph.
  • MAAGL framework: MAAGL partitions graphs into communities, assigns each community an independent agent, and separates structural evidence from semantically filtered node text.Structural evidence is summarized with a dynamically updated, fixed-size, permutation-invariant signature; semantic evidence retains only the top-k relevant nodes.
  • MAAGL framework: Agents use historical trajectories with similar structural signatures to estimate confidence and invoke debate-style collaboration selectively when confidence is low.The framework stores learned reasoning experiences in agent memory to guide subsequent reasoning.
  • Evaluation: MAAGL outperforms AGL methods on four benchmark datasets under both in-domain and zero-shot transfer settings while reducing token overhead.The supplied introduction reports this as the framework’s experimental outcome.
  • Existing limitations: GNNs and existing AGL methods commonly apply shared selection, aggregation, or reasoning policies across graph regions, which can be suboptimal when their structural and semantic patterns differ.AGL includes single-agent and orchestration-based approaches, while conventional GNNs use architecture-determined aggregation rules applied uniformly across nodes.
  • Existing limitations: Directly verbalizing graph evidence makes reasoning sensitive to arbitrary neighbor ordering and can sharply increase token costs as sampled multi-hop neighborhoods expand.The ordering issue conflicts with the inherently unordered nature of graph neighborhoods, while textual attributes compound context growth.

III. PROBLEM FORMULATION

MAAGL formulates graph reasoning over text-attributed graphs as sequential evidence collection by independent agents with private policies and memories. Its observation design separates structural and semantic evidence, using a permutation-invariant fixed-dimensional signature and top-k relevant text to control ordering sensitivity and context growth.

  • III. PROBLEM FORMULATION: A text-attributed graph contains nodes, edges, textual attributes, and labels, requiring joint learning from structural and semantic information.Nodes represent entities, edges represent relations, and node text supplies semantic information.
  • III. PROBLEM FORMULATION: Multi-agent agentic graph learning models each agent as an LLM-powered sequential decision maker with its own reasoning policy and private memory.Agents observe accumulated evidence, choose evidence-collection or prediction actions, and record reasoning trajectories.
  • Agent Assignment: MAAGL partitions the graph into densely connected communities and assigns one independent agent to each community for region-specific reasoning experience.The framework comprises assignment, specialization, collaborative reasoning, and experience learning stages; Leiden is used for partitioning.
  • 1) Observation:: Existing verbalized-evidence approaches list sampled neighbors sequentially, making reasoning sensitive to arbitrary ordering and increasing token overhead as neighborhoods expand.The issue is especially pronounced for multi-hop neighborhoods whose sampled nodes and textual attributes grow with the context.
  • 1) Observation:: MAAGL represents structural evidence with a structural signature and semantic evidence with relevance-filtered textual attributes instead of verbalizing all sampled evidence.The signature summarizes graph statistics, while only the top-k semantically relevant sampled nodes are retained.
  • 1) Observation:: The structural signature combines deterministic graph statistics, including static connectivity measures and dynamic label-based dimensions updated as new labeled nodes are sampled.Static dimensions retain their initial values, whereas dynamic dimensions are recomputed when new labeled nodes appear.
  • 1) Observation:: The signature remains fixed in dimensionality while evolving with sampled evidence, and its statistics are computed from node sets rather than their enumeration.This makes the representation permutation-invariant and prevents observation size from growing directly with neighborhood size when combined with top-k semantic filtering.

2) Action:

MAAGL provides separate structural and semantic evidence-collection actions, updating the structural signature with sampled neighborhoods and retaining only textually relevant nodes.

  • 2) Action:: Evidence-collection actions sample structural neighborhoods or retrieve semantically similar nodes, and their outputs are represented through the corresponding evidence channels.Returned nodes provide labels and textual attributes, but structural information updates the signature while text is relevance-filtered.
  • 2) Action:: Local r-hop structural search samples nodes within radius r ∈ {1, 2} of the target using graph shortest-path distance.The sampled nodes update the structural signature, while their textual attributes may contribute to filtered semantic evidence.
  • 2) Action:: Global top-k semantic search retrieves the k nodes whose textual attributes are most similar to the target node’s textual attribute.Semantic evidence is selected by textual relevance rather than neighborhood enumeration.

3) Prediction:

MAAGL limits reasoning to a fixed action budget while allowing agents to stop early when their evidence is sufficient. Prompted self-review determines whether another search is needed before prediction.

  • 3) Prediction:: MAAGL permits at most T reasoning steps and uses the final step for prediction if the action budget is exhausted.The experiments set T = 3.
  • 3) Prediction:: Agents are prompted after each evidence-collection action to assess whether the collected evidence is sufficient before selecting another action.This adaptive termination behavior is implemented through prompting rather than reinforcement learning.

4) Memory:

Agents store reasoning trajectories in private memories after labeled-node reasoning, including structural signatures that support retrieval of similar historical cases. Specialization memories are built independently within communities and can be populated in parallel.

  • Trajectory memory: After reasoning on a labeled training node, the agent stores the resulting trajectory in private memory and assigns a binary reward based on prediction correctness.Stored trajectories include the prediction and reward information used for later retrieval and learning.
  • Trajectory memory: Each trajectory records the initial structural signature, which is later used to retrieve past cases with similar structural patterns.The stored signature is associated with the trajectory rather than only with the final prediction.
  • Private memory: After processing labeled nodes in a community, agent Ai obtains trajectory memory as part of its private memory Mi.The private memory is represented using trajectory-memory components, although the supplied passages truncate the full notation.
  • Private memory: Because agents reason only within assigned communities without communication during specialization, their memory-building processes can run in parallel.Algorithm 1 summarizes this independent specialization process.

C. Collaborative Reasoning

Collaborative reasoning is activated when an owning agent lacks confidence on a target node, then selects experienced agents for debate. Participants independently gather evidence initially, exchange bounded rationales afterward, and determine the final label by voting.

  • Collaboration trigger: The owning agent estimates confidence from success rates on retrieved trajectories with structurally similar signatures and triggers collaboration when confidence falls below δ.The confidence score uses cosine similarity between the target’s initial signature and stored trajectory signatures.
  • Collaborator selection: When collaboration is triggered, agents with strong performance on structurally similar cases are selected as collaborators using their own trajectory memories.This reuses region-specific experience without additional training.
  • Debate process: In the first debate round, the owning agent and collaborators independently collect and represent structural and semantic evidence using their private policies and memories.This preserves specialization learned from each agent’s assigned community.
  • Debate process: After the first round, participants read previous predictions and rationales, reconsider their decisions without collecting additional graph evidence, and continue for subsequent rounds.The debate prompt supports iterative updates based on exchanged opinions.
  • Final decision: After D rounds, the final prediction is obtained by majority vote, with the highest-confidence participant resolving ties.The collaborative procedure returns the voted prediction after the debate rounds.
  • Communication cost: Communication cost does not grow with sampled-neighborhood size because agents exchange fixed-dimensional structural signatures and length-bounded rationales rather than full textual evidence.Sampled semantic evidence remains local to each agent during debate.

D. Experience Learning

MAAGL converts trajectory histories into reusable reasoning experiences expressed as quantitative structural conditions and recommended actions. Experiences become shared only after cross-agent validation shows sufficient improvement across other agents.

  • Experience generation: Trajectory memories reveal recurring relations between graph characteristics and effective reasoning strategies, providing reusable experience beyond individual successes or failures.These experiences guide subsequent reasoning.
  • Experience generation: MAAGL represents each generated experience as a structural metric g, threshold θ, and recommended strategy ρ applied when g > θ.This quantitative form avoids ambiguity in free-form natural-language recommendations.
  • Private experience memory: The trajectory memory stores concrete past cases, while the experience memory stores reusable reasoning guidance distilled from those cases.Together they form each agent’s private memory.
  • Cross-agent validation: An experience learned in one community is validated against other agents’ trajectories before it becomes globally available.This guards against experiences that reflect only local graph patterns.
  • Cross-agent validation: A positive Δj(ε) means that trajectories following the recommended strategy achieve a higher empirical success rate under the specified structural condition.The comparison is between trajectories taking and not taking the recommendation.
  • Cross-agent validation: Experiences enter the shared set only when the required improvement γ and minimum supporting-agent count κ are satisfied.Validated experiences can then guide all agents, while agent-specific experiences remain private.
  • Cross-agent validation: For example, an experience with Δ2(ε) = 0.27 and Δ3(ε) = 0.23 is shared when γ = 0.2 and κ = 2.The example shows support from two other agents exceeding the improvement threshold.
  • Computation cost: The structural-signature computation adds limited cost because static dimensions are cached, dynamic dimensions update incrementally, and validation reuses stored signatures and outcomes.The supplied passage states direct retrieval cost as O(|Mtraj_i|d) for agent Ai.

V. EXPERIMENTS

The experiments evaluate MAAGL against state-of-the-art AGL methods, analyze component contributions and hyperparameter sensitivity, and measure reasoning efficiency through four research questions.

  • Research questions: RQ1 evaluates how MAAGL compares with existing state-of-the-art AGL methods.This is the paper’s primary comparative evaluation question.
  • Research questions: RQ2 examines how each core component contributes to overall performance.The question targets component-level contribution rather than only end-to-end results.
  • Research questions: RQ3 studies sensitivity to key hyperparameters.The experiments include a dedicated hyperparameter-sensitivity question.
  • Research questions: RQ4 evaluates MAAGL’s efficiency in terms of reasoning cost.This question focuses on computational or interaction cost during reasoning.

A. Datasets

MAAGL is evaluated on four text-attributed graph datasets spanning academic citation and e-commerce domains, with one in-domain dataset and one disjoint same-domain transfer dataset per domain.

  • A. Datasets: The evaluation covers four text-attributed graph datasets across academic citation and e-commerce domains.The datasets are OGB-Arxiv, Cora-full, OGB-Products, and Amazon-Computers.
  • A. Datasets: Each domain uses one dataset for in-domain training and evaluation and a second disjoint dataset for zero-shot transfer.Academic citation uses OGB-Arxiv for training and Cora-full for transfer; e-commerce uses OGB-Products for training and Amazon-Computers for transfer.
  • A. Datasets: Academic citation graphs connect papers through citations and use paper titles and abstracts as node text.
  • A. Datasets: E-commerce graphs connect frequently co-purchased products, using product titles and descriptions or user reviews as node text.

B. Baselines

The study compares MAAGL with conventional GNNs, single-agent AGL methods, and orchestration-based multi-agent methods that use predefined role-based workflows.

  • B. Baselines: The baselines span GNN methods, single-agent methods, and orchestration-based methods.
  • B. Baselines: GNN baselines learn node representations through message passing or graph transformers and train separately on each dataset.
  • B. Baselines: GCN aggregates normalized 1-hop neighbor features, GraphSAGE aggregates sampled neighbors with a learnable function, and GraphGPS combines local message passing with global attention.
  • B. Baselines: Single-agent baselines use one LLM-powered agent to adaptively collect graph evidence and reason, including Graph-CoT and ReaGAN.
  • B. Baselines: Orchestration-based baselines coordinate multiple role-specialized agents through predefined workflows, including GraphTeam and GraphAgent.

C. Experimental Setup

MAAGL is evaluated against GNN, single-agent, and orchestration-based baselines in in-domain and zero-shot settings, followed by component ablations on OGB-Arxiv node classification.

  • C. Experimental Setup: Zero-shot transfer evaluates 1,000 sampled test nodes on Cora-full and Amazon-Computers without training on the target graph.
  • D. Overall Performance (RQ1): MAAGL achieves the best Accuracy on all four datasets and the best Macro-F1 on OGB-Products and Amazon-Computers.It remains competitive with the best baselines on OGB-Arxiv and Cora-full for Macro-F1.
  • D. Overall Performance (RQ1): Agent-based methods generally outperform conventional GNN methods, particularly in Macro-F1, while remaining applicable to zero-shot transfer without retraining.
  • E. Ablation Study (RQ2): Removing the structural signature causes the largest performance degradation in the OGB-Arxiv ablation study.The ablation evaluates Accuracy on node classification.
  • E. Ablation Study (RQ2): Replacing structured experience with free-text experience consistently weakens performance, while removing collaboration also degrades performance.
  • E. Ablation Study (RQ2): Replacing debate-based collaboration with max-confidence merging causes a smaller performance drop.

F. Hyperparameter Sensitivity (RQ3)

MAAGL remains effective across community-partition choices, while moderate settings balance agent specialization, local experience, and selective collaboration. Its structural signature and adaptive termination also reduce communication and search costs.

  • Community partitioning: Leiden, Louvain, and random partition achieve comparable accuracy, with community-based partitioning providing a small advantage.The result suggests that assigning regions to independent agents matters more than the specific partitioning algorithm.
  • Number of communities: A moderate number of communities best balances agent specialization against sufficient local experience.Too few communities limit specialization, whereas too many divide the graph into overly small regions.
  • Debate rounds: A small number of debate rounds is sufficient, with additional rounds offering little benefit and potentially causing unnecessary reconsideration.Initial debate can improve predictions by incorporating complementary opinions.
  • Confidence threshold: A moderate confidence threshold best supports selectively triggering collaboration for uncertain instances.Low thresholds trigger too little collaboration, while high thresholds invoke it even when the owning agent is reliable.
  • Learning rounds: Performance improves across learning rounds and gradually approaches saturation as agents accumulate experience from historical reasoning trajectories.Diminishing gains in later rounds suggest convergence of the learning process.
  • Efficiency analysis: The structural signature substantially reduces cross-agent message tokens, while adaptive search termination consistently reduces search actions across all four datasets.The signature remains fixed in size, and termination avoids unnecessary exploration once sufficient evidence has been collected.
Loading 2609.09565v1…