HackerPapers

arXiv:2203.15544cs.LG

Graph Neural Networks are Dynamic Programmers

Andrew Dudzik, Petar Veličković

Abstract

Recent advances in neural algorithmic reasoning with graph neural networks (GNNs) are propped up by the notion of algorithmic alignment. Broadly, a neural network will be better at learning to execute a reasoning task (in terms of sample complexity) if its individual components align well with the target algorithm. Specifically, GNNs are claimed to align with dynamic programming (DP), a general problem-solving strategy which expresses many polynomial-time algorithms. However, has this alignment truly been demonstrated and theoretically quantified? Here we show, using methods from category theory and abstract algebra, that there exists an intricate connection between GNNs and DP, going well beyond the initial observations over individual algorithms such as Bellman-Ford. Exposing this connection, we easily verify several prior findings in the literature, produce better-grounded GNN architectures for edge-centric tasks, and demonstrate empirical results on the CLRS algorithmic reasoning benchmark. We hope our exposition will serve as a foundation for building stronger algorithmically aligned GNNs.

arXiv comments
To appear at NeurIPS 2022. 18 pages, 4 figures
Journal reference
DOI
Subjects
cs.LGMachine Learning cs.AIArtificial Intelligence cs.DSData Structures and Algorithms math.CTCategory Theory stat.MLMachine Learning (Statistics)

On Hacker News

Linked by 2 identifiable commenters in 5 comments across 4 threads, from May 2023 to Sep 2023.

Comments linking this paper, per year.

Discussed in comments4 threads

  1. Graph Neural Networks use graphs when they shouldn't 1 comment

    • I've work with GNNs. I have not explicitly looked into this, but in general, the dynamics of GNNs are really interesting and there are many different lenses in which one can study the behavior of GNNs and find interesting takeaways. - Explicit Message Passing…

      stefanpieView on HNParent context

  2. It's not just statistics: GPT-4 does reason 2 comments

    • There are substantial works already showing reasoning capabilities in GPT-4, which show that these models do reason extremely well - near human performance for many causal reasoning tasks. (1) Additionally, there is a mathematical proof that these systems align with dynamic…

      chaxorView on HNParent context

    • Perhaps, but taken with other works in the area, a better picture does emerge regarding this claim. Substantial works already showing reasoning capabilities in GPT-4, which show that these models do reason very well - near human performance for many causal reasoning tasks. (1)…

      chaxorView on HNParent context

  3. Sam Altman goes before US Congress to propose licenses for building AI 1 comment

    • You should read some of the papers referred to in the above comments before making that assertion. It may take a while to realize the overall structure of the argument, how the category theory is used, and how this is directly applicable to LLMs, but if you are in ML it should…

      chaxorView on HNParent context

  4. Language models still struggle with the concept of negation 1 comment

    • It's literally the title. Peter Velockovic is probably the most prolific author of this era regarding LLMs, and does not yet realize it. https://arxiv.org/pdf/2203.15544.pdf

      chaxorView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.