ReaGAN: Node-as-Agent-Reasoning Graph Agentic Network

TL;DR

Graph Neural Networks (GNNs) classify nodes (e.g., “what topic is this paper?”) by having every node mechanically average information from its direct neighbors, the same way, every layer. That one-size-fits-all rule wastes signal on information-rich nodes and starves sparse ones, and it only ever looks at structural neighbors — never at nodes that are topically similar but far away in the graph. ReaGAN reframes the problem: each node becomes an agent with memory, a planner (a frozen LLM), actions (local aggregate / global retrieve / predict / no-op), and a tool (RAG over the whole graph as a text database). At each of ~1–3 layers, every node asks the LLM “given what I know, what should I do next?” and acts independently. The headline result: on Cora, Citeseer, and Chameleon node-classification benchmarks, this frozen-LLM, no-training approach is competitive with fully-supervised GNNs (84.95% vs GCN’s 84.71% on Cora). The interesting part isn’t the accuracy — it’s that it got there with no gradient descent at all, purely through per-node planning and retrieval.

Problem & Motivation

Here is the concrete pain. A standard GNN (GCN, GAT, GraphSAGE) does message passing: every node looks at its immediate neighbors, combines their feature vectors with a shared learned weight matrix, and repeats this for a few layers. The procedure is globally synchronized and identical for every node — same function, same depth, same neighbors-only horizon.

That creates two specific failures:

1. Node informativeness is imbalanced, but the rule isn’t. Some nodes are content-rich and well-positioned; others are sparse, noisy, or ambiguous. Forcing the same aggregation on all of them means rich nodes get drowned in irrelevant neighbor input, while sparse nodes never gather enough support. Worse, homogeneous propagation amplifies noise (this is the “over-smoothing / over-squashing” problem — pile on enough layers and every node’s representation collapses toward the same blur).

2. Structural neighbors ≠ semantically relevant nodes. GNNs assume your graph neighbors are the nodes you should learn from (the “homophily” assumption). In real graphs — open-domain, heterogeneous — the paper most relevant to yours might be three hops away or in a totally disconnected component. Classic message passing literally cannot reach it. For sparsely-connected nodes this is fatal: their local neighborhood has almost no predictive value.

Prior LLM-for-graphs work (PromptGFM, In-context RAG) used the LLM as a passive inference engine — feed it neighbor text, ask for a label. Prior “agent on graph” work (AgentNet, GraphAgent) hardcoded the agent’s behavior or trained it end-to-end with fixed 1-hop views. Nobody had let each node autonomously decide its own message-passing behavior using an LLM as the decision-maker.

What’s New (Core Contribution)

Three things, and it’s worth separating the genuinely new from the repackaged.

• Node-as-autonomous-agent with LLM planning (genuinely new). Before: every node runs the same fixed aggregation rule, synchronized across the graph. Now: each node independently prompts a frozen LLM with its own memory and gets back a plan — which action(s) to take this layer. No shared weights, no synchronization, no global schedule. This is the real contribution: replacing the fixed aggregation function with per-node, in-context decision-making.

• Hybrid local + global aggregation via RAG (new combination). Before: aggregation = structural neighbors only. Now: a node can choose Global Aggregation, which treats the entire graph as a structure-free text database and retrieves the top-K semantically similar nodes (cosine similarity over embeddings) — regardless of graph distance. RAG-for-graph-nodes existed (In-context RAG); making it a selectable action the node chooses is the delta.

• Training-free competitiveness (the headline evidence). Before: matching GNN accuracy required gradient-trained parameters. Now: a frozen Qwen2-14B with no fine-tuning matches supervised GNNs. This is more a demonstration than a mechanism, but it’s the result that makes the framing land.

What’s repackaged / oversold: the “Memory, Planning, Action, Tool” four-module framing is standard agent vocabulary (it’s just the ReAct loop applied per node). The NoOp action is presented as a contribution but is really a regularizer — a node opting out to avoid noise accumulation.

How It Works (Technically)

The whole thing is one loop, run independently by every node, for L layers (typically 1–3). Let me trace it.

Setup. You have an attributed graph G = (V, E). Every node v has a text feature t_v (e.g., the paper’s title+abstract) and maybe a label y_v (e.g., its topic). The job: predict labels for the unlabeled nodes. Each node gets a memory buffer M_v, initialized to just its own text: M_v = {t_v}.

The per-layer cycle. At layer l, node v does:

1. Plan. Build a prompt from current memory and ask the frozen LLM what to do: a_v = LLM(Prompt_planning(M_v)) In plain English: “Here’s everything I know about myself and my context. What should I do next — aggregate locally, retrieve globally, predict, or wait?” The LLM returns one or more discrete actions. This is the line that replaces the fixed H = σ(ÂHW) matrix multiply of a GNN with a learned-at-pretraining, frozen decision policy. The “policy” here isn’t trained with RL — it’s whatever the LLM does when prompted. That’s the cleverness and the hand-wave at once.

2. Act. Execute each action in the plan:

   • LocalAggregation — gather from direct graph neighbors N_local(v). Two effects:

     • Feature enhancement: t̃_v^(l) = TextAgg(t̃_v^(l-1), {t̃_u^(l-1) | u ∈ N_local(v)}). TextAgg is natural-language aggregation — concatenate or summarize the neighbors’ text into one snippet. This is the GNN’s “average your neighbors’ embeddings” step, but done in text space by stuffing neighbor descriptions together (or asking the LLM to summarize them), not in vector space.
     • Few-shot collection: E_v^(l) = {(t̃_u, y_u) | u ∈ N_local(v), y_u known}. Grab labeled neighbors as (text, label) examples and write them into memory. These become in-context examples for the eventual prediction — this is how a frozen model “learns”: few-shot, not fine-tune.

   • GlobalAggregation — invoke the RAG tool. Query the structure-free database with the node’s current text and get the top-K most semantically similar nodes anywhere in the graph: N_global(v) = RAG(t̃_v^(l-1), top=K) Then run the same feature-enhancement and few-shot-collection as local, but over these retrieved nodes. Operationally: RAG = TopK over all nodes by sim(t_v, t_u), where sim is cosine distance on embeddings (they use all-MiniLM-L6-v2 to embed). The database has no edges — each entry is just (text, optional label). This is the move that lets a node reach a topically-relevant paper 10 hops away.

   • Prediction — build a prediction prompt from memory and ask for the label: ŷ_v = LLM(Prompt_predict(M_v)). A node can predict early if it’s confident.

   • NoOp — do nothing. Memory unchanged. This exists to stop a node from over-collecting and drowning its own signal in noise. It’s a pacing/regularization knob.

3. Update memory. Append whatever the actions produced: M_v^(l) = M_v^(l-1) ∪ {t̃_v^(l)} ∪ E_v^(l). Memory only grows by agent actions — the RAG tool never silently mutates memory. That separation is deliberate: the node stays in control of its own state.

After L layers, the final memory drives the prediction prompt. Note what the memory holds at that point: (i) the node’s raw text (identity anchor, never overwritten), (ii) aggregated local + global summaries (multi-scale context), and (iii) a curated set of labeled (text, label) examples (the few-shot demonstrations). All three get selectively injected into the prediction prompt.

One concrete trace. Node A is a sparsely-connected paper on “graph attention.” Layer 1: A’s planner sees it has only one neighbor — picks GlobalAggregation, RAG returns 5 topically-similar papers (3 of them labeled), writes their summaries + (text,label) pairs to memory. Layer 2: now memory is rich; planner picks LocalAggregation to add its one real neighbor’s signal, then Prediction. Meanwhile node B (a hub with 40 good neighbors) just does LocalAggregation → Prediction and skips RAG entirely. Node D, already confident, does NoOp then Prediction. Same graph, three different computation paths — that’s the whole point.

Architecture & data flow

flowchart TD
  subgraph Node v as Agent
    MEM[Memory M_v<br/>raw text + aggregated summaries + labeled shots]
    PLAN[Planner: frozen LLM<br/>Prompt_planning M_v]
    MEM --> PLAN
    PLAN -->|returns action plan| ACT{Action}
  end
  ACT -->|LocalAggregation| LOCAL[Aggregate direct<br/>graph neighbors N_local]
  ACT -->|GlobalAggregation| RAG[RAG tool:<br/>top-K semantic<br/>neighbors N_global]
  ACT -->|Prediction| PRED[LLM predicts label y_v]
  ACT -->|NoOp| WAIT[do nothing]
  LOCAL --> WRITE[write summaries + labeled shots back]
  RAG --> WRITE
  WAIT --> WRITE
  WRITE --> MEM
  PRED --> OUT([Predicted label])
  GRAPH[(Whole graph as<br/>structure-free<br/>text DB)] -.semantic search.-> RAG

Schematic of one node's layer-wise loop. Click to step through layers; watch memory fill up and the planner pick different actions depending on how much context the node already has. Illustrative, not the paper's data.

The algorithm, simplified

# One agent-node's full lifecycle. Run this independently for every node.
# llm(prompt) -> str    embed(t) -> vector    cosine(a,b) -> float
def reagan_node(v, graph, db, L=3, K=5):
    memory = {"text": v.text, "summaries": [], "shots": []}  # shots = (text,label) demos
    prediction = None

    for layer in range(L):
        plan = llm(planning_prompt(memory))      # frozen LLM decides: the "policy" is just prompting
        actions = parse(plan)                     # e.g. ["GlobalAggregation","Prediction"]

        for a in actions:
            if a == "LocalAggregation":
                nbrs = graph.neighbors(v)                       # structural neighbors only
                memory["summaries"].append(text_agg([n.text for n in nbrs]))  # NL-level aggregate
                memory["shots"] += [(n.text, n.label) for n in nbrs if n.label]

            elif a == "GlobalAggregation":
                # treat the ENTIRE graph as an edge-free text DB; retrieve by meaning, not distance
                hits = sorted(db, key=lambda u: cosine(embed(memory["text"]), embed(u.text)))[:K]
                memory["summaries"].append(text_agg([u.text for u in hits]))
                memory["shots"] += [(u.text, u.label) for u in hits if u.label]

            elif a == "Prediction":
                prediction = llm(predict_prompt(memory))        # few-shot label from memory
            # NoOp: intentionally do nothing -> avoids noise over-collection

    return prediction

The thing to internalize: there is no training loop. No loss, no gradients, no backprop. The “intelligence” is (a) the frozen LLM’s in-context reasoning and (b) the retrieval. Everything ReaGAN adds is orchestration around a frozen model.

Built on Prior Work

Results & Evidence

What they tested. Node classification on three standard citation/web graphs: Cora, Citeseer, Chameleon. Each node = a document with text; predict its category. 60/20/20 train/val/test split. Backbone: frozen Qwen2-14B served via vLLM, embeddings via all-MiniLM-L6-v2, no fine-tuning. Baselines: GCN, GAT, GraphSAGE, APPNP, GPRGNN, MixHop, MLP-2 — all trained supervised on the same splits.

Headline numbers (test accuracy %):

The honest read: ReaGAN wins on Cora and is genuinely competitive there, but on Citeseer (60.25 vs GraphSAGE’s 78.24) and Chameleon (43.80 vs GPRGNN’s 67.48) it clearly loses to the best trained GNNs. The abstract’s “competitive performance” is true only loosely — it ties or beats some baselines, not the strongest ones, on 2 of 3 datasets. For a training-free method that’s still notable, but don’t read it as “beats GNNs.”

Ablations (the more interesting evidence):

• No prompt planning (force a fixed action sequence) → big drops everywhere (Citeseer 60.25 → 35.87). The per-node planning is doing real work.
• Local Only / Global Only → both underperform Full. Local-only craters on sparse Citeseer; global-only craters on dense graphs. Confirms the hybrid is the point.
• Prompt memory strategy: always-include-global (A) wins on dense graphs (Cora, Chameleon); include-global-only-when-local-is-thin (B) wins on sparse Citeseer (60.25 vs 50.14). So the right strategy is data-dependent — a caveat for anyone deploying this.
• Label semantics hurt: showing real label names (“Machine Learning”) drops Cora from 84.95 → 76.83. The LLM overfits to label wording and guesses by vibes. Their fix: anonymize labels to “Label_2.” This is a sharp, practical finding — exposing your class names to a frozen LLM biases it.

What the evidence does NOT establish: only three small homogeneous-text citation/web graphs; only one LLM backbone (Qwen2-14B); no cost/latency numbers (this fires many LLM calls per node per layer — potentially thousands of calls for a small graph); no large-graph scaling test; no comparison against the strong LLM-for-graph baselines (In-context RAG, PromptGFM) in the main table. The framing (“plug-and-play alternative to GNNs”) is aspirational given the cost and the mixed accuracy.

How You’d Use It

For an AI-services shop, the value here is less “use ReaGAN to classify graphs” and more “this is a clean template for per-entity agentic reasoning with retrieval.” Concretely:

• Entity classification / enrichment with no training. A client has a knowledge graph (customers, products, documents, support tickets) and wants categories or tags but has almost no labeled data and no ML team. ReaGAN’s pattern — per-node planner + local relationships + global semantic retrieval + few-shot from labeled neighbors — is a buy-nothing, train-nothing way to get reasonable labels. You’re trading GPU training cost for inference cost.
• The “global aggregation” trick generalizes. The genuinely portable idea: when an entity’s direct relationships are thin, retrieve semantically similar entities from the whole corpus to enrich its context before reasoning. That’s useful in any per-record decision pipeline (lead scoring, ticket routing, document triage), not just graphs.
• NoOp / opt-out as a cost governor. In a per-entity agent fleet, letting each agent decide not to do expensive work (extra retrieval, extra LLM calls) when it’s already confident is a real production lever. Most naive agent pipelines do every step for every item.
• The label-anonymization finding is immediately actionable. If you’re doing few-shot classification with a frozen LLM, hide your human-readable class names and use opaque IDs — it measurably reduces the model guessing from label wording instead of evidence.

Where it does not fit: anything latency-sensitive or high-volume. One LLM call per node per layer means a 2,700-node graph at 3 layers with planning+actions is easily 10k+ LLM calls. This is a batch/offline tool, not a real-time one.

Build Your Own (Minimal Recipe)

You can build an 80% version in a day. Components and order:

1. Embed every node’s text once (sentence-transformers all-MiniLM-L6-v2) and shove the vectors into a vector store (FAISS, Chroma, or even sklearn NearestNeighbors for small graphs). This is your RAG tool and your “structure-free database.” (1–2 hrs)
2. Hold the graph adjacency in a dict {node: [neighbors]} for LocalAggregation. (15 min)
3. Write two prompt templates: a planning prompt (“given this memory, output one or more of: LOCAL, GLOBAL, PREDICT, NOOP”) and a prediction prompt (memory + few-shot shots → label ID). Anonymize the labels. (1 hr)
4. Write the loop from the pseudocode above. Memory is just a dict you keep appending to. (1 hr)
5. Run per node, L=2 or 3. Cache LLM calls aggressively. (ongoing)

The two genuinely hard parts:

• TextAgg (natural-language aggregation). Concatenation blows up context length fast; summarization adds an LLM call and can lose signal. Getting this to compress neighbor text without dropping the discriminative bits is the real engineering. Start with truncated concatenation; upgrade to summarization only if context overflows.
• Making the planner’s output reliable. A frozen LLM asked “pick actions” will hallucinate formats. You need strict output parsing (JSON mode / function calling) and a fallback default action. The paper glosses this; in practice it’s where your time goes.

Models to reach for: any instruct LLM you can serve cheaply (Qwen2, Llama-3.x-8B) via vLLM or just an API; MiniLM or BGE for embeddings; FAISS for retrieval.

How to Improve It

Limitations as leverage — five concrete, testable directions:

1. Actually train the planner with RL. Right now the “policy” is a frozen LLM prompted to pick actions — it’s never optimized for the task. Treat each node’s action sequence as a trajectory, reward = correct final prediction (minus a cost per LLM call), and fine-tune the planner with GRPO/PPO. This directly targets the weak Citeseer/Chameleon numbers and could make NoOp/global-retrieval decisions cost-aware. Highest-upside idea here.
2. Inter-node communication. Nodes currently act in isolation — they read neighbors’ text but don’t pass messages or decisions. Let a node’s plan be conditioned on neighbors’ recent actions (true multi-agent message passing). This is literally the MAS coordination problem applied to graph nodes, and the authors flag it as future work.
3. Learned-vs-fixed K and adaptive retrieval depth. Top-K is a fixed knob; let the node decide K and even do multi-round retrieval (retrieve, read, retrieve again) — agentic RAG instead of one-shot RAG.
4. Cache and amortize across nodes. Many nodes will retrieve overlapping global neighbors and ask near-identical planning questions. A shared summary cache + planning-prompt cache could cut the call count by an order of magnitude — the missing piece for the scalability claim.
5. Attack the cost head-on with a router. Use a cheap model (or a heuristic) for the planning decision and reserve the big LLM only for prediction. Most planning calls don’t need a 14B model to decide “LOCAL then PREDICT.”

Glossary

• GNN (Graph Neural Network) — model that learns node representations by repeatedly averaging each node’s neighbors’ features through trained weights.
• Message passing — the GNN operation of aggregating neighbor information; “synchronized” means every node does it identically each layer.
• Node classification — predicting a category label for each node (here, the topic of a document).
• Over-smoothing / over-squashing — pathologies where stacking GNN layers makes all node representations collapse toward each other (smoothing) or bottlenecks distant info through few edges (squashing).
• Homophily — the assumption that connected nodes are similar/share labels; often false in real graphs.
• RAG (Retrieval-Augmented Generation) — fetch relevant text by similarity and feed it to an LLM; here used to find semantically similar nodes regardless of graph distance.
• Frozen LLM — a pretrained language model used as-is, with no fine-tuning or weight updates.
• Few-shot / in-context learning — giving the LLM example (input, answer) pairs in the prompt so it “learns” the task without parameter updates.
• Embedding / cosine similarity — turning text into a vector; cosine measures how aligned two vectors are (proxy for semantic similarity).
• TextAgg — ReaGAN’s natural-language aggregation: combine neighbor texts by concatenation or summarization (instead of vector averaging).
• NoOp — an explicit “do nothing this layer” action that prevents a node from over-collecting noisy context.
• Memory buffer (M_v) — per-node store of raw text, aggregated summaries, and labeled examples that drives every prompt.
• ReAct loop — the standard agent pattern of alternating reasoning and tool-using actions; ReaGAN runs one per node.
• L (layers) — number of plan→act→update cycles per node (typically 1–3).