TLDR

Heirarchical graph pooling approach meant to improve the interpretability of graph neural networks.
LaPool iteratively coarsens (collapses nodes to single one) graphs in order to allow for message passing updates to reach nodes that are distant in the original graph.
The main intuition is to use a node-level smoothness measure to determine which nodes to use as pooling centers.
Models which use this pooling layer outperform other pooling-based GNNs.

Methods

A graph Laplacian is \(\mathbf{L} = \mathbf{D} - \mathbf{A}\) where \(\mathbf{D}\) is a diagonal matrix storing the degree of each node in the graph, and \(A\) is a standard adjacency matrix.
Define a smoothness measure
\(s(\mathbf{f}) = (\mathbf{f}^T L \mathbf{f}) = \frac{1}{2} \sum_{i,j}^{n} \mathbf{A}_{i,j} (f_i - f_j)^2\).
where \(\mathbf{f}\) can be thought of as a vector signals \(f_i\) coming from each node.
Therefore \(s\) gives the difference in signal between each node and its neighbors. i.e. how much it stands out from its neighbors.