@inproceedings{
lachi2023graph,
title={Graph Pooling Provably Improves Expressivity},
author={Veronica Lachi and Alice Moallemy-Oureh and Andreas Roth and Pascal Welke},
booktitle={NeurIPS 2023 Workshop: New Frontiers in Graph Learning},
year={2023},
url={https://openreview.net/forum?id=lR5NYB9zrv}
}
In the domain of graph neural networks (GNNs), pooling operators are fundamental to reduce the size of the graph by simplifying graph structures and vertex features. 
Recent advances have shown that well-designed pooling operators, coupled with message-passing layers, can endow hierarchical GNNs with an expressive power regarding the graph isomorphism test that is equal to the Weisfeiler-Leman test. 
However, the ability of hierarchical GNNs to increase expressive power by utilizing graph coarsening was not yet explored. 
This results in uncertainties about the benefits of pooling operators and a lack of sufficient properties to guide their design.
In this work, we identify conditions for pooling operators to generate WL-*distinguishable* coarsened graphs from originally WL-*indistinguishable* but non-isomorphic graphs. 
Our conditions are versatile and can be tailored to specific tasks and data characteristics, offering a promising avenue for further research.
Graph Pooling Provably Improves Expressivity
Veronica Lachi Alice Moallemy-Oureh Andreas Roth Pascal Welke