TRN-R1-Zero: Text-rich Network Reasoning via LLMs with Reinforcement Learning Only

1. Problem Statement

Text-Rich Networks (TRNs) are graphs where nodes contain textual data (e.g., scientific papers, social media posts, product descriptions) and edges represent semantic or functional relationships (e.g., citations, hyperlinks, co-purchases).

• The Challenge: Performing zero-shot node classification on TRNs is difficult because models must simultaneously integrate textual semantics with relational graph structures without task-specific supervision.
• Limitations of Existing Methods:
  • Encoder-based approaches: Treat Large Language Models (LLMs) merely as feature extractors, failing to leverage explicit reasoning capabilities.
  • Generative/Reasoning approaches: Often rely on Supervised Fine-Tuning (SFT) using Chain-of-Thought (CoT) data distilled from larger, external Large Reasoning Models (LRMs). This limits generalization, increases computational cost, and creates a dependency on external "teacher" models.
• Goal: Develop a framework that enables base LLMs to perform explicit relational reasoning on TRNs in a zero-shot setting, without SFT, distillation, or external LRMs.

2. Methodology: TRN-R1-Zero

The authors propose TRN-R1-Zero, a post-training framework that optimizes a base LLM solely via Reinforcement Learning (RL). The core innovation is a Neighbour-aware Group Relative Policy Optimisation (GRPO) objective.

A. Zero-Shot Node Classification as Token Generation

The task is reformulated as a next-token prediction problem. The input prompt includes:

1. Target Node Text: The content of the node to be classified.
2. Neighbourhood Sampling: Randomly sampled subgraphs (limited by width and depth) to control input length and act as data augmentation.
3. Candidate Labels: Descriptions of possible classes.
   The model is instructed to output a reasoning trace (internal monologue) followed by the answer token.

B. Neighbour-aware Policy Objective

Standard RL objectives (like PPO or GRPO) treat all training samples equally. TRN-R1-Zero introduces a Margin Gain Metric to dynamically adjust rewards based on the informativeness of the graph context.

1. Margin Gain Calculation ($\Delta_i$):

   • A frozen text encoder computes embeddings for the target node and labels.
   • A lightweight Simple Graph Convolution (SGC) aggregator is applied to the node and its neighbours to generate an aggregated embedding.
   • The Margin Gain is defined as the difference between the classification margin with neighbours and without neighbours:
     $$\Delta_i = m_i(\tilde{\ell}) - m_i(\ell)$$
     Where $m_i$ is the margin between the correct class logit and the highest incorrect class logit.
   • Interpretation:
     • $\Delta_i > 0$: Neighbours provide helpful context.
     • $\Delta_i < 0$: Neighbours are distracting.
     • $|\Delta_i|$: Magnitude of the influence.

2. Reward Reshaping:
   The base reward ($R_{base}$), which checks format and accuracy, is scaled by an exponential factor of the absolute margin gain:
   $$R_i = \exp(\alpha \cdot |\Delta_i|) \cdot R_{base}$$

   • This mechanism amplifies rewards for samples where the neighbourhood significantly shifts the decision boundary (either positively or negatively), forcing the model to learn how to effectively utilize (or filter) relational context.

C. Training Pipeline

• Base Model: Starts with a standard instruction-tuned LLM (e.g., Qwen2.5-7B).
• Optimization: Uses Dr.GRPO (a variant of GRPO that removes the standard deviation denominator for better reward shaping) combined with a KL-divergence penalty to prevent collapse.
• No SFT: The model is never fine-tuned on labeled CoT data; it learns reasoning purely through the RL loop.

3. Key Contributions

1. RL-Only Pipeline: The first framework to achieve zero-shot node classification on TRNs using only reinforcement learning, eliminating the need for distillation from larger LRMs or supervised CoT data.
2. Neighbour-Aware Reward Mechanism: Introduces a novel Margin Gain metric that quantifies the specific contribution of graph structure to reasoning, dynamically scaling rewards to guide the model toward effective relational inference.
3. Cross-Task Generalization: Demonstrates that training strictly on node-level tasks enables zero-shot inference on edge-level (link prediction) and graph-level tasks, proving the model learns transferable relational reasoning principles.

4. Experimental Results

Experiments were conducted on nine datasets across four domains: Citation (Cora, Citeseer), Hyperlink (WikiCS), Social (Instagram), and Co-purchase (Photo, History).

• Zero-Shot Node Classification:
  • TRN-R1-Zero (7B parameters) achieved the highest average Accuracy and Macro-F1 across all datasets, outperforming larger models (GPT-4o, Qwen2.5-14B) and specialized Graph Foundation Models (ZeroG, LLaGA).
  • It significantly outperformed Graph-R1 (a state-of-the-art reasoning model trained with SFT and distillation), despite Graph-R1 being larger (14B) and trained with more complex supervision.
• Generalization to Edge/Graph Tasks:
  • Without any edge-level training, TRN-R1-Zero achieved substantial gains on link prediction tasks (e.g., +16.10% on WikiCS-Link), surpassing Graph-R1.
• Efficiency:
  • TRN-R1-Zero (7B) produced significantly shorter reasoning traces (avg. ~150 tokens) compared to Graph-R1 (14B, avg. ~930 tokens) while achieving higher accuracy.
  • This indicates the RL process promotes concise and efficient reasoning rather than verbose "thinking."
• Ablation Studies:
  • Removing the neighbour-aware reward scaling led to unstable training and lower performance.
  • The method generalized well across different model backbones (Llama-3, Qwen, 3B to 14B scales).

5. Significance and Conclusion

TRN-R1-Zero represents a paradigm shift in graph-based reasoning:

• Decoupling from Distillation: It proves that base LLMs can learn complex relational reasoning directly from the environment (the graph) via RL, removing the dependency on expensive, large-scale "teacher" models.
• Intrinsic Reasoning: By optimizing the reward based on the impact of neighbours, the model learns to intrinsically understand when and how to use graph structure, rather than just memorizing patterns from CoT data.
• Scalability: The approach is highly efficient, achieving superior results with smaller models and shorter inference times, making it viable for real-world applications where computational resources are constrained.

The code is publicly available, facilitating further research into RL-based graph reasoning without the overhead of supervised fine-tuning.