Graph Reinforcement Learning: A Practical Guide with TGraphX

Reinforcement learning on graphs is a research area where graphs appear in two roles: as the state that the agent perceives, or as the environment being optimized. A graph RL agent might navigate a road network, optimize a molecule's structure, schedule tasks on a compute graph, or route packets through a network.

TGraphX provides 13 graph RL algorithms, graph-specific environments, and policy/value network architectures — all labeled Experimental. This guide explains what graph RL is, what TGraphX implements, and what it does not cover.

Two Roles for Graphs in RL

Graph as state. The agent observes a graph at each timestep. The graph may change after each action (dynamic graph), or the agent moves through a fixed graph (navigation). Policy and value networks process node features and edge structure to produce action distributions or value estimates.

Graph as object being optimized. Evolutionary graph optimization uses a population of graphs as the search space. RL can also search graph space: each action modifies the graph structure (adds/removes nodes or edges) and the reward measures some graph property.

TGraphX covers both roles:

• Graph-as-state: GraphNavigationEnv, GraphPolicyNetwork, REINFORCEAgent, DQNAgent, PPOAgent
• Graph-as-object: run_graph_rl(env="maxcut") and similar one-liner APIs for structure-optimization RL

Core RL Concepts Applied to Graphs

State. A graph G = (V, E, x) with node features. In navigation, the state may include the current node position.

Action. Moving to a neighboring node, adding/removing an edge, or selecting a graph transformation.

Reward. Depends on the task: reaching a target node (+1), improving graph connectivity (density increase), reducing a cut value (MaxCut), or completing a chemical synthesis route.

Policy network. A GNN that processes the state graph and outputs an action distribution. TGraphX's GraphPolicyNetwork is a two-layer GNN followed by a softmax over the action space.

Value network. Estimates the expected cumulative reward from the current state.

REINFORCE: Simplest Graph RL

import torch
        from tgraphx.rl import (
            GraphNavigationEnv,
            GraphEnvConfig,
            GraphPolicyNetwork,
            REINFORCEAgent,
        )
        
        # 5-node chain graph: 0 → 1 → 2 → 3 → 4
        edge_index = torch.tensor([[0, 1, 2, 3], [1, 2, 3, 4]], dtype=torch.long)
        node_features = torch.randn(5, 8)  # each node has 8-dim feature
        
        env = GraphNavigationEnv(
            edge_index=edge_index,
            num_nodes=5,
            node_features=node_features,
            target_node=4,
            config=GraphEnvConfig(max_steps=20),
        )
        
        policy = GraphPolicyNetwork(
            node_in_dim=8,
            hidden_dim=32,
            num_actions=4,  # max degree in graph
        )
        agent = REINFORCEAgent(
            policy=policy,
            optimizer=torch.optim.Adam(policy.parameters(), lr=1e-3),
        )
        
        # Training loop
        for episode in range(100):
            trajectory = agent.collect_episode(env, max_steps=20)
            loss = agent.update(trajectory)
            if episode % 20 == 0:
                total_reward = sum(t[2] for t in trajectory.transitions)
                print(f"Episode {episode}: reward={total_reward:.2f}, loss={loss:.4f}")
        

DQN for Graph Navigation

from tgraphx.rl.algorithms.dqn import DQNAgent
        from tgraphx.rl import GraphPolicyNetwork
        from tgraphx.rl.config import RLTrainingConfig
        
        config = RLTrainingConfig(
            algorithm="dqn",
            gamma=0.99,
            learning_rate=1e-3,
            n_episodes=500,
            batch_size=32,
            replay_capacity=10000,
            target_update_freq=50,
            eps_start=1.0,
            eps_end=0.05,
            eps_decay=200.0,
            seed=42,
        )
        
        q_network = GraphPolicyNetwork(node_in_dim=8, hidden_dim=64, num_actions=4)
        target_network = GraphPolicyNetwork(node_in_dim=8, hidden_dim=64, num_actions=4)
        
        agent = DQNAgent(
            q_network=q_network,
            target_network=target_network,
            config=config,
        )
        
        # Training
        for episode in range(config.n_episodes):
            trajectory = agent.collect_episode(env)
            if len(agent.replay_buffer) >= config.batch_size:
                loss = agent.update()
        

PPO for Graph Tasks

from tgraphx.rl.algorithms.ppo import PPOAgent
        from tgraphx.rl import GraphPolicyNetwork
        
        config = RLTrainingConfig(
            algorithm="ppo",
            gamma=0.99,
            gae_lambda=0.95,
            clip_eps=0.2,
            n_steps=128,
            n_epochs=4,
            value_loss_coef=0.5,
            entropy_coef=0.01,
            seed=42,
        )
        
        policy = GraphPolicyNetwork(node_in_dim=8, hidden_dim=64, num_actions=4)
        value_net = GraphPolicyNetwork(node_in_dim=8, hidden_dim=64, num_actions=1)  # value head
        
        agent = PPOAgent(policy=policy, value_net=value_net, config=config)
        

One-Liner Graph RL

For quick experiments, the high-level API:

import tgraphx as tgx
        
        # Train a random baseline on MaxCut
        rl_result = tgx.train_graph_rl(
            env="maxcut",
            algorithm="random",   # no-learn baseline
            episodes=5,
            seed=42,
        )
        print(rl_result.metrics)
        
        # Equivalent: run_graph_rl
        from tgraphx.rl.high_level_api import run_graph_rl
        result = run_graph_rl(
            algorithm="reinforce",
            env="navigation",
            num_nodes=10,
            n_episodes=50,
            seed=42,
        )
        

Supported Algorithms

TGraphX implements 13 graph RL algorithms:

All algorithms except Random and Greedy are labeled Experimental.

Graph RL Environments

TGraphX provides several built-in graph RL environments:

• GraphNavigationEnv: Navigate from a start node to a target node in a fixed graph.
• MaxCut-inspired: Modify edge assignments to maximize the cut value.
• Custom environments: Implement the GraphEnvBase interface to define your own.

The environments are intentionally simple — designed for testing RL algorithms and methodology, not for production graph optimization. For complex combinatorial optimization on graphs (TSP, VRP, graph coloring), dedicated operations research solvers or specialized RL libraries (torch-geometric-temporal, Combinatorial Optimization with RL) are better choices.

Limitations: What Graph RL in TGraphX Does Not Cover

No model-based RL. World models, planning, and MPC on graphs are not implemented.

No offline RL. Batch RL from pre-collected graph trajectories is not included.

No graph-level reward decomposition. When the reward is at the graph level but learning should propagate to node-level decisions, credit assignment is not automated.

Not competitive with dedicated CO solvers. For hard combinatorial optimization problems like TSP or graph coloring, CPLEX, Gurobi, or specialized RL solvers (L2I, POMO) will outperform TGraphX's built-in algorithms. TGraphX's graph RL is research tooling, not an optimization engine.

All algorithms are Experimental. APIs, algorithm implementations, and environments may change in future releases.

Performance numbers are not provided. Benchmark comparisons between TGraphX's RL algorithms and production RL libraries depend heavily on task, graph size, reward signal, and hyperparameters. See TGraphX benchmark disclaimers.

Comparison with the Evolutionary Approach

TGraphX also includes evolutionary graph optimization, which is often a more effective approach for structural optimization than RL:

import tgraphx as tgx
        
        # Evolutionary: genetic algorithm + NSGA-II for multi-objective optimization
        result = tgx.optimize_graph(
            objective="connectivity",
            algorithm="ga",
            num_nodes=30,
            seed=42,
        )
        print(f"Best fitness: {result.best_fitness:.4f}")
        

For graph structure optimization problems where the objective is a scalar graph property, evolutionary optimization often converges faster and more reliably than policy gradient RL. See evolutionary optimization of graph structures for the comparison.

Related Articles

• Graph reinforcement learning with TGraphX — the published introduction
• Evolutionary optimization of graph structures — alternative optimization approach
• Graph generation with tensor-valued node features — generating graphs as RL environment building blocks
• TGraphX benchmark disclaimers — honest interpretation of RL results
• What is a TGX graph — the graph data model RL agents operate on