Graph Pooling and Hierarchical Readout

Node classification ends where message passing ends: every node already holds a vector. Graph classification does not. A molecule with 14 atoms and one with 60 must both produce a single prediction, through a function that does not care about the order the nodes arrived in. That function is the readout, and the choice of readout is one of the few architectural decisions in graph learning with a clean theoretical answer and a messy empirical one.

Flat readout, and why the sum is not interchangeable with the mean

The simplest readout aggregates all node vectors at once: sum, mean or max. They are not equivalent. Summing preserves multiplicity and therefore graph size, and it is the only one of the three that is injective over multisets, which is why the WL-equivalent architecture uses it (Xu et al., 2019, How Powerful are Graph Neural Networks?, ICLR). Mean discards size: a graph of ten carbons and one of twenty average to the same vector. Max keeps only the extremes and collapses a multiset to a set.

The practical consequence is that mean readout is the right default when graph size is a nuisance variable and the wrong one when size is a feature. On molecular property prediction, where many targets scale with molecular weight, switching sum to mean can cost more accuracy than changing the convolution.

Hierarchical pooling in three steps

Flat readout throws away all intermediate structure. Hierarchical pooling instead coarsens the graph several times, in imitation of strided convolution on images. Every such operator, and there are dozens, decomposes into the same three functions: select nodes into groups called supernodes, reduce each group's attributes into one node, and connect the supernodes with edges (Grattarola et al., 2024, Understanding Pooling in Graph Neural Networks, IEEE TNNLS). The taxonomy is worth internalising, because it tells you exactly where any new method differs from the one you already know.

The families differ in the select step. Dense soft assignment learns a matrix \(S \in \mathbb{R}^{n \times m}\) mapping \(n\) nodes to \(m\) clusters and coarsens with \(X' = S^\top X\) and \(A' = S^\top A S\), trained end to end with auxiliary link-prediction and entropy terms to keep assignments local and confident; this is DiffPool, reported at 5 to 10 percent average accuracy improvement over flat readouts when it was introduced (Ying et al., 2018, Hierarchical Graph Representation Learning with Differentiable Pooling, NeurIPS). Spectral relaxation replaces the auxiliary losses with a continuous relaxation of the normalised min-cut objective, which gives the clusters a stated meaning (Bianchi et al., 2020, Spectral Clustering with Graph Neural Networks for Graph Pooling, ICML). Score-and-keep methods score every node with a learned projection, keep the top fraction and drop the rest, which is sparse and cheap (Lee et al., 2019, Self-Attention Graph Pooling, ICML).

The cost difference between the first two families and the third is the whole engineering story. A dense assignment matrix is \(n \times m\) per graph, so memory is quadratic in nodes and the pooled adjacency is dense even when the input was sparse. Score-and-keep is linear and keeps sparsity, at the price of discarding nodes outright.

When it breaks

Learned local pooling may not be doing what the papers claim. Replacing cluster assignments with random ones, or clustering on the complement graph, did not degrade performance across standard graph-classification benchmarks; the authors attribute the result to the convolutional layers, not the pooling, producing the representations that matter (Mesquita et al., 2020, Rethinking pooling in graph neural networks, NeurIPS). Any claim that a new pooling operator helps should be measured against random assignment at the same ratio, which is a baseline most papers omit.

A fixed keep-ratio is not size-adaptive. Keeping the top 50 percent of nodes coarsens a 1,000-node graph to 500 and a 10-node graph to 5. One of those is a hierarchy and the other is a lossy sum.

Sparse pooling can disconnect the graph. Dropping nodes by score deletes their edges, and the coarsened graph may fall into components that no longer exchange messages, so later layers mix nothing. Dense methods avoid this by construction and pay in memory.

The benchmarks may be too easy to resolve the question. Several standard graph-classification datasets are small enough, and dominated enough by node features, that structure-agnostic baselines are competitive with graph networks at all (Errica et al., 2020, A Fair Comparison of Graph Neural Networks for Graph Classification, ICLR). A pooling comparison run only on those datasets cannot distinguish a good operator from a harmless one.