Recurrent reasoners can flood early causing search errors in large graphs
Fitting Every Hint Is Not Enough: Premature Floods in Recurrent Algorithmic Reasoners
Machine LearningArtificial Intelligence
Summary
The paper finds that some algorithmic reasoners trained on small problems fail when applied to larger ones by marking nodes too early, a problem called premature flooding. The authors identify causes linked to specific inputs and how graphs’ features are processed, showing that common training methods can miss this error. They propose ways to detect and fix these floods by checking input ranges and testing on bigger, deeper graphs.
What this means in practice
- •For machine learning engineers: Prevent faulty node expansions in graph algorithms by auditing input ranges and training on larger graphs to detect premature flooding in recurrent reasoners.
- •For graph algorithm developers: Improve reliability of neural network-based graph search tools by applying fixes like clamping inputs and adding diverse training graphs to avoid early flooding.
Authors
Amin Najafgholizadeh, Mohsen Afsharchi
Abstract
Recurrent algorithmic reasoners are trained with per-step hints on small graphs and run for many more steps on large ones. On breadth-first search in SALSA-CLRS, we find that a reasoner can reproduce every training hint and still fail on deep graphs: after some exact steps, it declares nodes reached before the search gets there. We call this a premature flood and trace two routes to it. In our GRU processor with a degree input, the flood is carried in the hidden state and set off when that input is in the tail of the training distribution. Setting the input higher at inference brings the flood sooner, and none of the six flooding models counts steps. Without the input, summing the neighbors' states instead of averaging them also breaks the processor. In the benchmark's own GIN and PGN, trained with its code, some seeds instead flood from a fixed step, on sparse and dense graphs alike. Clamping the degree input or adding 200 dense training graphs removes every failure of the GRU processor. Detaching the state between steps avoids the flood in that processor (0 of 23 seeds, against 6 under full backpropagation) but not with sums or a residual update, and two published remedies leave floods. None of the benchmark's test sets is both deep and dense, but its deepest one shows the second route: on its Delaunay graphs at 1,600 nodes, one GIN seed floods from step 18. We therefore recommend auditing the range of every input and aggregate, which catches the first route, and testing on deep graphs, which catches both.