Comparing Graph Neural Networks Aggregation Strategies for Dynamic Programming-Based Reasoning Tasks

This paper investigates the reasoning capabilities of various Graph Neural Networks (GNN) on dynamic programming-based tasks, focusing on the impact of different aggregation strategies. The study evaluates five GNN architectures, Message Passing Neural Networks, Graph Convolutional Networks, Graph Attention Networks, Graph Sample and Aggregation, and Graph Isomorphism Networks—across three DP problems: Longest Increasing Subsequence (LIS), Coin Change, and 0/1 Knapsack. These tasks challenge the GNNs to simulate discrete functions and implicitly learn correct logical reasoning steps. Experiments are conducted to assess the reasoning accuracy and generalization ability of GNNs. The results demonstrate that GraphSAGE consistently outperforms other models in the LIS problem for relational understanding. However, all models struggle with the NP-Hard integer programming problem Coin Change, highlighting the need for more expressive aggregation mechanisms. This study provides theoretical insights into the effect of different GNN designs for algorithmic reasoning tasks. It suggests directions for future research, including exploring more algorithmic challenges and the influence of advanced network structure.