Algorithmic Reasoning

Simulate seven graph algorithms through node regression, node classification, or edge classification: topological sorting, maximum flow, minimum spanning tree, bridge finding, Steiner tree, maximum clique, and maximum matching.

Each algorithm has easy, medium, and hard synthetic datasets whose train and test graphs differ in generator distribution. Training graphs have 16 nodes while held-out graphs include 128 nodes, with additional size-generalization tests up to 512 nodes in the published experiments.

Inputs encode the graph, algorithm-specific weights or designated vertices, and task-relevant node or edge attributes. Unlike CLRS-style processor supervision, these datasets focus on final outputs rather than providing a full sequence of algorithmic hints.

Fixed 98%/1%/1% splits contain about one million graphs per difficulty for each algorithm. Classification tasks use accuracy and F1; flow and topological-order targets use MAE.

Difficulty changes both generator distribution and graph size, so failures cannot be attributed to only one axis. Edge tasks are transformed for some node-token baselines. The old YAML’s 21-million count is the approximate total across seven tasks, not the size of every individual task.