Maximally Expressive GNNs for Outerplanar Graphs

We propose a linear time graph transformation that enables the Weisfeiler-Leman (WL)
algorithm and message passing graph neural networks (MPNNs) to be maximally expressive
on outerplanar graphs. Our approach is motivated by the fact that most pharmaceutical
molecules correspond to outerplanar graphs. Existing research predominantly enhances the
expressivity of graph neural networks without specific graph families in mind. This often
leads to methods that are impractical due to their computational complexity. In contrast,
the restriction to outerplanar graphs enables us to encode the Hamiltonian cycle of each
biconnected component in linear time. As the main contribution of the paper we prove that
our method achieves maximum expressivity on outerplanar graphs. Experiments confirm
that our graph transformation improves the predictive performance of MPNNs on molecular
benchmark datasets at negligible computational overhead.