Diffusion Models for Cayley Graphs
This addresses path-finding in mathematical structures like Cayley graphs, which is incremental as it applies an existing AI method (diffusion models) to a new domain.
The authors tackled the problem of finding paths in Cayley graphs of groups, using the Rubik's cube as an example, by formulating it within the diffusion model framework, where exploration uses the forward process and target node finding uses the inverse backward process, and they proposed a 'reversed score' ansatz that substantially improves over previous comparable algorithms.
We review the problem of finding paths in Cayley graphs of groups and group actions, using the Rubik's cube as an example, and we list several more examples of significant mathematical interest. We then show how to formulate these problems in the framework of diffusion models. The exploration of the graph is carried out by the forward process, while finding the target nodes is done by the inverse backward process. This systematizes the discussion and suggests many generalizations. To improve exploration, we propose a ``reversed score'' ansatz which substantially improves over previous comparable algorithms.