Understanding Pooling in Graph Neural Networks
This work provides a systematic understanding of graph pooling for researchers in graph machine learning, though it is incremental as it organizes existing methods rather than introducing new ones.
The paper tackles the problem of unifying the diverse literature on graph pooling by proposing a formal framework based on three operations (selection, reduction, connection) and introducing a taxonomy to categorize over thirty methods, with evaluation criteria used to investigate their behavior on various tasks.
Inspired by the conventional pooling layers in convolutional neural networks, many recent works in the field of graph machine learning have introduced pooling operators to reduce the size of graphs. The great variety in the literature stems from the many possible strategies for coarsening a graph, which may depend on different assumptions on the graph structure or the specific downstream task. In this paper we propose a formal characterization of graph pooling based on three main operations, called selection, reduction, and connection, with the goal of unifying the literature under a common framework. Following this formalization, we introduce a taxonomy of pooling operators and categorize more than thirty pooling methods proposed in recent literature. We propose criteria to evaluate the performance of a pooling operator and use them to investigate and contrast the behavior of different classes of the taxonomy on a variety of tasks.