Neural Algorithmic Reasoning with Causal Regularisation
- URL: http://arxiv.org/abs/2302.10258v2
- Date: Mon, 3 Jul 2023 17:08:05 GMT
- Title: Neural Algorithmic Reasoning with Causal Regularisation
- Authors: Beatrice Bevilacqua, Kyriacos Nikiforou, Borja Ibarz, Ioana Bica,
Michela Paganini, Charles Blundell, Jovana Mitrovic, Petar Veli\v{c}kovi\'c
- Abstract summary: We make an important observation: there are many different inputs for which an algorithm will perform certain intermediate computations identically.
This insight allows us to develop data augmentation procedures that, given an algorithm's intermediate trajectory, produce inputs for which the target algorithm would have exactly the same next trajectory step.
We prove that the resulting method, which we call Hint-ReLIC, improves the OOD generalisation capabilities of the reasoner.
- Score: 18.299363749150093
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Recent work on neural algorithmic reasoning has investigated the reasoning
capabilities of neural networks, effectively demonstrating they can learn to
execute classical algorithms on unseen data coming from the train distribution.
However, the performance of existing neural reasoners significantly degrades on
out-of-distribution (OOD) test data, where inputs have larger sizes. In this
work, we make an important observation: there are many different inputs for
which an algorithm will perform certain intermediate computations identically.
This insight allows us to develop data augmentation procedures that, given an
algorithm's intermediate trajectory, produce inputs for which the target
algorithm would have exactly the same next trajectory step. We ensure
invariance in the next-step prediction across such inputs, by employing a
self-supervised objective derived by our observation, formalised in a causal
graph. We prove that the resulting method, which we call Hint-ReLIC, improves
the OOD generalisation capabilities of the reasoner. We evaluate our method on
the CLRS algorithmic reasoning benchmark, where we show up to 3$\times$
improvements on the OOD test data.
Related papers
- On the Markov Property of Neural Algorithmic Reasoning: Analyses and
Methods [94.72563337153268]
We present ForgetNet, which does not use historical embeddings and thus is consistent with the Markov nature of the tasks.
We also introduce G-ForgetNet, which uses a gating mechanism to allow for the selective integration of historical embeddings.
Our experiments, based on the CLRS-30 algorithmic reasoning benchmark, demonstrate that both ForgetNet and G-ForgetNet achieve better generalization capability than existing methods.
arXiv Detail & Related papers (2024-03-07T22:35:22Z) - Discrete Neural Algorithmic Reasoning [21.852775399735005]
We propose to force neural reasoners to maintain the execution trajectory as a combination of finite predefined states.
We get perfect test scores on the SALSA-CLRS benchmark, where we get perfect test scores for all tasks.
arXiv Detail & Related papers (2024-02-18T16:03:04Z) - Triplet Edge Attention for Algorithmic Reasoning [16.130097693973845]
We introduce a new graph neural network layer called Triplet Edge Attention (TEA), an edge-aware graph attention layer.
Our algorithm works by precisely computing edge latent, aggregating multiple triplet messages using edge-based attention.
arXiv Detail & Related papers (2023-12-09T16:46:28Z) - Predictive Coding beyond Correlations [59.47245250412873]
We show how one of such algorithms, called predictive coding, is able to perform causal inference tasks.
First, we show how a simple change in the inference process of predictive coding enables to compute interventions without the need to mutilate or redefine a causal graph.
arXiv Detail & Related papers (2023-06-27T13:57:16Z) - Neural Algorithmic Reasoning Without Intermediate Supervision [21.852775399735005]
We focus on learning neural algorithmic reasoning only from the input-output pairs without appealing to the intermediate supervision.
We build a self-supervised objective that can regularise intermediate computations of the model without access to the algorithm trajectory.
We demonstrate that our approach is competitive to its trajectory-supervised counterpart on tasks from the CLRSic Algorithmic Reasoning Benchmark.
arXiv Detail & Related papers (2023-06-23T09:57:44Z) - Neural-prior stochastic block model [0.0]
We propose to model the communities as being determined by the node attributes rather than the opposite.
We propose an algorithm, stemming from statistical physics, based on a combination of belief propagation and approximate message passing.
The proposed model and algorithm can be used as a benchmark for both theory and algorithms.
arXiv Detail & Related papers (2023-03-17T14:14:54Z) - The Cascaded Forward Algorithm for Neural Network Training [61.06444586991505]
We propose a new learning framework for neural networks, namely Cascaded Forward (CaFo) algorithm, which does not rely on BP optimization as that in FF.
Unlike FF, our framework directly outputs label distributions at each cascaded block, which does not require generation of additional negative samples.
In our framework each block can be trained independently, so it can be easily deployed into parallel acceleration systems.
arXiv Detail & Related papers (2023-03-17T02:01:11Z) - Towards Better Out-of-Distribution Generalization of Neural Algorithmic
Reasoning Tasks [51.8723187709964]
We study the OOD generalization of neural algorithmic reasoning tasks.
The goal is to learn an algorithm from input-output pairs using deep neural networks.
arXiv Detail & Related papers (2022-11-01T18:33:20Z) - Benchmarking Node Outlier Detection on Graphs [90.29966986023403]
Graph outlier detection is an emerging but crucial machine learning task with numerous applications.
We present the first comprehensive unsupervised node outlier detection benchmark for graphs called UNOD.
arXiv Detail & Related papers (2022-06-21T01:46:38Z) - Robustification of Online Graph Exploration Methods [59.50307752165016]
We study a learning-augmented variant of the classical, notoriously hard online graph exploration problem.
We propose an algorithm that naturally integrates predictions into the well-known Nearest Neighbor (NN) algorithm.
arXiv Detail & Related papers (2021-12-10T10:02:31Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.