Graph Neural Networks and Graph Kernels For Learning Heuristics: Is there a difference?

Graph neural networks (GNNs) have been used in various works for learningheuristics to guide search for planning. However, they are hindered by theirslow evaluation speed and their limited expressiveness. It is also a known factthat the expressiveness of common GNNs is bounded by the Weisfeiler-Lehman(WL) algorithm for testing graph isomorphism, with which one can generateshallow embeddings for graphs. Thus, one may ask how do GNNs compare againststatistical machine learning models such as linear regression and kernel methodswith WL features of planning problems represented as graphs? Our experimentsshow that simple linear regression is at least as competitive as GNN models forlearning heuristics for planning in the learning track of the recent 2023 InternationalPlanning Competition (IPC). Most notably, our models train in under a minute andachieves performance rivalling models which train for up to 24 hours. We alsodiscuss prevalent issues and open questions in the field of automated learning forplanning which need to be solved in order for the field to progress.