In computer vision, downsampling an input is straightforward. An image is a regular grid of pixels with a fixed spatial arrangement and a predictable number of neighbors. Standard max-pooling simply takes a $2 \times 2$ window of pixels, selects the maximum value, and slides across the grid. This operation works because the underlying Euclidean space provides a natural coordinate system and translation invariance.
Graphs, however, defy this regularity. As noted by Lu Bai et al. in Graph Complexity from the Jensen-Shannon Divergence, graphs lack a fixed-size vector representation or a natural vertex ordering. A single node might be connected to two neighbors or two thousand, meaning there is no consistent "sliding window" or global translation group (Joan Bruna et al., Spectral Networks and Locally Connected Networks on Graphs).
Without a regular metric, defining hierarchical operations like pooling and unpooling becomes a significant challenge (Moshe Eliasof et al., DiffGCN: Graph Convolutional Networks via Differential Operators and Algebraic Multigrid Pooling). To build multi-scale representations for complex graph classification or regression tasks, we must find a way to "zoom out" of a graph without destroying its underlying topological information.
To resolve this, researchers have developed two primary paradigms for downsampling irregular structures: Node Selection and Node Clustering.
Node Selection: Pruning the Topology
The most direct way to downsample a graph is to drop less important nodes entirely. The core challenge here is determining "importance" in a way that respects both the features of the nodes and the structure of the graph.
In Graph U-Nets, Hongyang Gao et al. introduced gPool, which projects node features onto a learnable vector to compute a scalar score for each node. The top $k$ nodes are retained, and the new adjacency matrix is formed simply by slicing the original matrix to keep only the connections between the surviving nodes. To make this selection process aware of the broader graph context, Junhyun Lee et al. proposed Self-Attention Graph Pooling (SAGPool), which utilizes graph convolutions to compute self-attention scores that reflect both node features and local topology simultaneously.
Node Selection (e.g., gPool / SAGPool):
[ Node 1 (Score: 0.9) ] -- (Keep) -----\
[ Node 2 (Score: 0.2) ] -- (Drop) +--> [ Node 1 ] ------- [ Node 3 ]
[ Node 3 (Score: 0.8) ] -- (Keep) -----/
Why it works, and where it struggles
Node selection is highly efficient because it preserves a subset of the original nodes and maintains a sparse representation. However, dropping nodes blindly can shatter a connected graph into isolated components, destroying the global topology.
To mitigate this, Hongyang Gao et al. later developed Topology-Aware Graph Pooling Networks (TAP). TAP adds a connectivity bonus to the selection mechanism, ensuring that the chosen nodes remain structurally cohesive and preventing the coarsened graph from falling apart.
Node Clustering: Condensing Communities
Instead of discarding nodes, an alternative approach is to group them into communities, treating each community as a single "super-node" in the coarsened graph.
A mathematically rigorous way to achieve this is by leveraging the spectral properties of the graph. In Spectral Clustering with Graph Neural Networks for Graph Pooling, Filippo Maria Bianchi et al. introduced MinCutPool. This method trains a Graph Neural Network to output a soft assignment matrix that minimizes a continuous relaxation of the classic normalized min-cut objective.
Node Clustering (e.g., MinCutPool):
[ Node 1 ] \
[ Node 2 ] -- Cluster A (Tightly bound) ----> [ Super-Node A ]
[ Node 3 ] / |
| (Weak connection / Min-Cut) | (Aggregated Edge)
[ Node 4 ] \ |
[ Node 5 ] -- Cluster B (Tightly bound) ----> [ Super-Node B ]
Why it works
The min-cut objective naturally identifies bottlenecks in the graph topology. By grouping nodes that share dense internal connections but sparse external connections, MinCutPool ensures that the downsampled graph preserves the global community structure.
Similarly, Davide Bacciu et al. proposed A Non-negative Factorization Approach to Node Pooling in Graph Convolutional Neural Networks (NMFPool). By decomposing the adjacency matrix into soft-assignment communities using Non-Negative Matrix Factorization, the network can capture long-range interactions and multi-scale structures without losing structural context.
Seeking Mathematical Equivalence to Grid Pooling
While selection and clustering provide practical ways to downsample graphs, researchers have also sought to establish a true mathematical generalization of image pooling that applies directly to irregular domains.
Distance Preservation via Independent Sets
In traditional image downsampling, a stride of 2 ensures that the remaining pixels are evenly spaced. To replicate this spatial spacing on irregular graphs, Davide Bacciu et al. introduced a method based on Maximal $k$-Independent Sets ($k$-MIS) in Generalizing Downsampling from Regular Data to Graphs. By selecting "centroids" that are strictly at least $k$ hops apart from one another, the algorithm provides explicit theoretical guarantees on distance preservation, mimicking the uniform coverage of grid-based strided sampling.
Continuous Graphon Spaces
Another elegant perspective bypasses the discrete irregularity of graphs by mapping them to a continuous domain. Alejandro Parada-Mayorga et al. proposed Graphon Pooling in Graph Neural Networks, which treats discrete graph layers as samples of an underlying continuous mathematical object called a graphon.
By performing the downsampling operations within this continuous graphon space, the method eliminates the ambiguity of node ordering and preserves the graph's spectral (frequency-domain) characteristics perfectly across scales.
Summary
Hierarchical downsampling on irregular graphs requires moving away from fixed spatial windows toward topology-aware operations. Whether by adaptively dropping nodes using self-attention, collapsing communities via spectral min-cuts, or mapping graphs to continuous graphon spaces, the goal remains the same: reducing structural complexity while preserving the essential geometric and topological properties of the data.
Key Foundational Work
Graph Complexity from the Jensen-Shannon Divergence (2012) — contributed 1 concept elements to this direction.
A discriminative prototype selection approach for graph embedding in human action recognition (2011) — contributed 1 concept elements to this direction.