The Deep Equilibrium Algorithmic Reasoner

• URL: http://arxiv.org/abs/2402.06445v2
• Date: Tue, 9 Apr 2024 07:26:38 GMT
• Title: The Deep Equilibrium Algorithmic Reasoner
• Authors: Dobrik Georgiev, Pietro Liò, Davide Buffelli,
• Abstract summary: We show that graph neural networks (GNNs) can learn to execute classical algorithms. We conjecture and empirically validate that one can train a network to solve algorithmic problems by directly finding the equilibrium.
• Score: 20.375241527453447
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Recent work on neural algorithmic reasoning has demonstrated that graph neural networks (GNNs) could learn to execute classical algorithms. Doing so, however, has always used a recurrent architecture, where each iteration of the GNN aligns with an algorithm's iteration. Since an algorithm's solution is often an equilibrium, we conjecture and empirically validate that one can train a network to solve algorithmic problems by directly finding the equilibrium. Note that this does not require matching each GNN iteration with a step of the algorithm.

Related papers

• Deep Equilibrium Algorithmic Reasoning [18.651333116786084]
  We study neurally solving algorithms from a different perspective. Since the algorithm's solution is often an equilibrium, it is possible to find the solution directly by solving an equilibrium equation. Our approach requires no information on the ground-truth number of steps of the algorithm, both during train and test time.
  arXiv  Detail & Related papers  (2024-10-19T10:40:55Z)
• Benchmarking ChatGPT on Algorithmic Reasoning [58.50071292008407]
  We evaluate ChatGPT's ability to solve algorithm problems from the CLRS benchmark suite that is designed for GNNs. We find that ChatGPT outperforms specialist GNN models, using Python to successfully solve these problems.
  arXiv  Detail & Related papers  (2024-04-04T13:39:06Z)
• Generating Interpretable Networks using Hypernetworks [16.876961991785507]
  We explore the possibility of using hypernetworks to generate interpretable networks whose underlying algorithms are not yet known. For the task of computing L1 norms, hypernetworks find three algorithms: (a) the double-sided algorithm, (b) the convexity algorithm, (c) the pudding algorithm. We show that a trained hypernetwork can correctly construct models for input dimensions not seen in training, demonstrating systematic generalization.
  arXiv  Detail & Related papers  (2023-12-05T18:55:32Z)
• Latent Space Representations of Neural Algorithmic Reasoners [15.920449080528536]
  We perform a detailed analysis of the structure of the latent space induced by the GNN when executing algorithms. We identify two possible failure modes: (i) loss of resolution, making it hard to distinguish similar values; (ii) inability to deal with values outside the range observed during training. We show that these changes lead to improvements on the majority of algorithms in the standard CLRS-30 benchmark when using the state-of-the-art Triplet-GMPNN processor.
  arXiv  Detail & Related papers  (2023-07-17T22:09:12Z)
• The Clock and the Pizza: Two Stories in Mechanistic Explanation of Neural Networks [59.26515696183751]
  We show that algorithm discovery in neural networks is sometimes more complex. We show that even simple learning problems can admit a surprising diversity of solutions.
  arXiv  Detail & Related papers  (2023-06-30T17:59:13Z)
• 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)
• Graph Neural Networks are Dynamic Programmers [0.0]
  Graph neural networks (GNNs) are claimed to align with dynamic programming (DP) Here we show, using methods from theory and abstract algebra, that there exists an intricate connection between GNNs and DP.
  arXiv  Detail & Related papers  (2022-03-29T13:27:28Z)
• Evolving Reinforcement Learning Algorithms [186.62294652057062]
  We propose a method for meta-learning reinforcement learning algorithms. The learned algorithms are domain-agnostic and can generalize to new environments not seen during training. We highlight two learned algorithms which obtain good generalization performance over other classical control tasks, gridworld type tasks, and Atari games.
  arXiv  Detail & Related papers  (2021-01-08T18:55:07Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  This paper investigates the classical integer least-squares problem which estimates signals integer from linear models. The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning. We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
  arXiv  Detail & Related papers  (2021-01-07T08:00:02Z)
• Neural Bipartite Matching [19.600193617583955]
  This report describes how neural execution is applied to a complex algorithm. It is achieved via neural execution based only on features generated from a single GNN. The evaluation shows strongly generalising results with the network achieving optimal matching almost 100% of the time.
  arXiv  Detail & Related papers  (2020-05-22T17:50:38Z)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  Bipartite b-matching is fundamental in algorithm design, and has been widely applied into economic markets, labor markets, etc. Existing exact and approximate algorithms usually fail in such settings due to either requiring intolerable running time or too much computation resource. We propose textttNeuSearcher which leverages the knowledge learned from previously instances to solve new problem instances.
  arXiv  Detail & Related papers  (2020-05-09T02:48:23Z)

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.