This is the official code repository for Tackling GNARLy Problems: Graph Neural Algorithmic Reasoning Reimagined through Reinforcement Learning by Alex Schutz, Victor-Alexandru Darvariu, Efimia Panagiotaki, Bruno Lacerda, and Nick Hawes, published in TMLR. If you use this code, please consider citing our paper:
@article{schutz2026tackling,
author = {Schutz, Alex and Darvariu, Victor-Alexandru and Panagiotaki, Efimia and Lacerda, Bruno and Hawes, Nick},
title = {Tackling GNARLy Problems: Graph Neural Algorithmic Reasoning Reimagined through Reinforcement Learning},
journal = {Transactions on Machine Learning Research},
year = {2026},
url = {https://openreview.net/forum?id=3aeMfeKlKh}
}
Prerequisites:
- Python 3.10 or 3.11
- Boost libraries (for the C++ objective functions, required for robustness calculations)
- If these are not available, the main GNARL functionality will still work, but the Robust Construction environment will not work
pip install .
cd third_party/concorde && ./build_concorde.sh && cd ../..This project is licensed under the MIT License.
It also includes code from DEAR, which is licensed under the Apache License 2.0, and SALSA-CLRS, which is licensed under the Apache License 2.0. See LICENSE and NOTICE for details.
This repo uses the Concorde TSP Solver as a third-party executable.
See third_party/concorde/README.md for build and usage instructions.
To run all experiments from the paper, use the run_experiments.py script. This will train and evaluate models for all configurations in the configs directory.
python scripts/run_experiments.pyFor more fine-grained control, see below.
To generate data for a specific problem, run the generate_data.py script with the appropriate configuration file. For example, to generate data for the BFS problem:
python scripts/generate_data.py configs/bfs.yamlThe results in the paper rely on external datasets for the TSP, MVC, and Robust Graph Construction problems.
- To use the TSP data, generate the
tsp_largedataset here, then place it in thedata/tsp_largedirectory. Runpython scripts/generate_data.py configs/tsp.yamlto convert the data into the required format. - To use the MVC data, generate the "vertex_cover" dataset from here, and place it in the
data/mvcdirectory. Runpython scripts/generate_data.py configs/mvc.yamlto convert the data into the required format. - To use the RGC data, generate the dataset from here, then place it in the
data/graph-construction-datasetsdirectory. Runpython scripts/generate_data.py configs/rgc_er_r.yamlto convert the data into the required format.
To train a model, run the train.py script with the appropriate configuration file. For example, to train a model for the BFS problem using BC:
python scripts/train.py --config configs/bfs.yamlUse the optional -w flag to enable Weights & Biases logging.
After training a model, you can evaluate it using the eval.py script. For example, to evaluate a trained model for the BFS problem:
python scripts/eval.py --config configs/bfs.yaml --path path/to/trained/model.pthYou will find some pre-trained models in the checkpoints directory.
To solve a new problem type using GNARL, implement the following:
-
Add a new environment in
gnarl/envs/which inherits from thePhasedNodeSelectEnv. You must implement the following methods:_init_observation_space— define the state variables_reset_state— initialise the state variables_get_observation— implement the observation function for the state variables_step_env— implement the transition functionget_max_episode_steps— define the maximum number of steps for the episodeaction_masks— define the valid actions for the stateis_terminal— define the terminal states
BC:
expert_policy— implement the expert for imitation learningis_success(optional) — determine if the algorithm was completed successfully
PPO
objective_function— define the objective function to be maximisedpre_transform(optional) — add the expert objective function value to the dataset for comparison at test time
-
Register the new environment in
gnarl/envs/__init__.pyand add it to theENV_MAPPINGdict. -
Add an input spec for the problem type in
gnarl/envs/generate/specs.py. -
Add a sampler for the problem type in
gnarl/envs/generate/sampler.pyand add it toSAMPLERS. -
Create a configuration file for the problem in
configs, and then you should be ready to go!