Neural Algorithmic Reasoning with Causal Regularisation

• DOI: 10.48550/arxiv.2302.10258
• Publication Date: 2023-01-01
• Authors: Beatrice Bevilacqua; Kyriacos Nikiforou; Borja Ibarz; Ioana Bica; M. Paganini; Charles Blundell; Jovana Mitrovic; Petar Veličković
• Keywords: Semantic reasoner; Benchmark (surveying); Deep Neural Networks; Causal reasoning

Recent work on neural algorithmic reasoning has investigated the capabilities of networks, effectively demonstrating they can learn to execute classical algorithms unseen data coming from train distribution. However, performance existing reasoners significantly degrades out-of-distribution (OOD) test data, where inputs have larger sizes. In this work, we make an important observation: there are many different for which algorithm will perform certain intermediate computations identically. This insight allows us develop augmentation procedures that, given algorithm's trajectory, produce target would exactly same next trajectory step. We ensure invariance in next-step prediction across such inputs, by employing a self-supervised objective derived our observation, formalised causal graph. prove that resulting method, call Hint-ReLIC, improves OOD generalisation reasoner. evaluate method CLRS benchmark, show up 3$\times$ improvements data.