Curvature-based Pooling within Graph Neural Networks
Cedric Sanders Andreas Roth Thomas Liebig
Over-squashing and over-smoothing are two critical issues, that limit the
capabilities of graph neural networks (GNNs). While over-smoothing eliminates
the differences between nodes making them indistinguishable, over-squashing
refers to the inability of GNNs to propagate information over long distances,
as exponentially many node states are squashed into fixed-size representations.
Both phenomena share similar causes, as both are largely induced by the graph
topology. To mitigate these problems in graph classification tasks, we propose
CurvPool, a novel pooling method. CurvPool exploits the notion of curvature of
a graph to adaptively identify structures responsible for both over-smoothing
and over-squashing. By clustering nodes based on the Balanced Forman curvature,
CurvPool constructs a graph with a more suitable structure, allowing deeper
models and the combination of distant information. We compare it to other
state-of-the-art pooling approaches and establish its competitiveness in terms
of classification accuracy, computational complexity, and flexibility. CurvPool
outperforms several comparable methods across all considered tasks. The most
consistent results are achieved by pooling densely connected clusters using the
sum aggregation, as this allows additional information about the size of each
pool.