Positional Diffusion: Ordering Unordered Sets with Diffusion Probabilistic Models
This work addresses ordering problems in domains like puzzles and language, offering a novel plug-and-play method that is incremental in applying diffusion models to this specific bottleneck.
The paper tackles the problem of ordering unsorted sets into consistent structures, such as puzzles or sentences, using a diffusion probabilistic model called Positional Diffusion, achieving up to +18% improvement over the second-best deep learning method on puzzle datasets and performing on par with state-of-the-art methods on other tasks.
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/