按年被提到
20222023 · 5 次2026
机器学习与深度学习›神经网络架构探索·arXiv:2203.15544 · cs.LG

Graph Neural Networks are Dynamic Programmers

Andrew Dudzik, Petar Veličković · 2022
开始阅读 ↗PDFalphaXiv 讨论
被提及 · 2 人首次 2023-05-14 · 最近 2023-09-19
2不同的人
2活跃月份
4讨论串
11被引(OpenAlex)
arXiv 摘要(候选层不写导读)

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.

候选层:至少 2 个不同的人、在 2 个不同月份提到过,还没到主书架的 3 人 3 个月。没有做立场标注,所以只写“被提及”。

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
评论chaxor · 2023-05

“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”

Chatbots Don’t Know What Stuff Isn’t原评论 ↗
评论chaxor · 2023-05

“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 be obvious. https://arxiv.org/abs/2203.15544”

OpenAI chief goes before US Congress to propose licenses for building AI原评论 ↗
评论chaxor · 2023-05

“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 programming, and therefore can do algorithmic reasoning. (2,3) 1) https://arxiv.o…”

It's not just statistics: GPT-4 does reason原评论 ↗
评论chaxor · 2023-05

“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) Additionally, there is a mathematical proof that these systems align with dyna…”

It's not just statistics: GPT-4 does reason原评论 ↗
评论stefanpie · 2023-09

“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: https://arxiv.org/abs/2202.11097 - Algorithmic Reasoning: https://arxiv.org/abs/2203.15544 - …”

Graph Neural Networks Use Graphs When They Shouldn't原评论 ↗