  In Graph Neural Networks (GNNs), hierarchical pooling operators generate
local summaries of the data by coarsening the graph structure and the vertex
features. While considerable attention has been devoted to analyzing the
expressive power of message-passing (MP) layers in GNNs, a study on how graph
pooling affects the expressiveness of a GNN is still lacking. Additionally,
despite the recent advances in the design of pooling operators, there is not a
principled criterion to compare them. In this work, we derive sufficient
conditions for a pooling operator to fully preserve the expressive power of the
MP layers before it. These conditions serve as a universal and theoretically
grounded criterion for choosing among existing pooling operators or designing
new ones. Based on our theoretical findings, we analyze several existing
pooling operators and identify those that fail to satisfy the expressiveness
conditions. Finally, we introduce an experimental setup to verify empirically
the expressive power of a GNN equipped with pooling layers, in terms of its
capability to perform a graph isomorphism test.
