ICLR 2023 - Rethinking the Expressive Power of GNNs via Graph Biconnectivity

In this episode we discuss Rethinking the Expressive Power of GNNs via Graph Biconnectivity by Bohang Zhang, Shengjie Luo, Liwei Wang, Di He. This paper introduces a new approach called Generalized Distance Weisfeiler-Lehman (GD-WL) to study the expressive power of Graph Neural Networks (GNNs). The authors show that most existing GNN architectures are not expressive for certain metrics related to graph biconnectivity, except for the ESAN framework. They demonstrate that GD-WL is provably expressive for all biconnectivity metrics and outperforms previous GNN architectures in practical experiments.