  Positional reasoning is the process of ordering unsorted parts contained in a
set into a consistent structure. We present Positional Diffusion, a
plug-and-play graph formulation with Diffusion Probabilistic Models to address
positional reasoning. We use the forward process to map elements' positions in
a set to random positions in a continuous space. Positional Diffusion learns to
reverse the noising process and recover the original positions through an
Attention-based Graph Neural Network. We conduct extensive experiments with
benchmark datasets including two puzzle datasets, three sentence ordering
datasets, and one visual storytelling dataset, demonstrating that our method
outperforms long-lasting research on puzzle solving with up to +18% compared to
the second-best deep learning method, and performs on par against the
state-of-the-art methods on sentence ordering and visual storytelling. Our work
highlights the suitability of diffusion models for ordering problems and
proposes a novel formulation and method for solving various ordering tasks.
Project website at https://iit-pavis.github.io/Positional_Diffusion/
