graph pooling
**Graph Pooling** is a class of operations in graph neural networks that reduce the number of nodes in a graph to produce a coarser representation, analogous to spatial pooling (max/average pooling) in CNNs but adapted for irregular graph structures. Graph pooling enables hierarchical graph representation learning by progressively summarizing graph structure and node features into increasingly compact representations, ultimately producing a fixed-size graph-level embedding for classification or regression tasks.
**Why Graph Pooling Matters in AI/ML:**
Graph pooling is **essential for graph-level prediction tasks** (molecular property prediction, social network classification, program analysis) because it provides the mechanism to aggregate variable-sized graphs into fixed-dimensional representations while capturing multi-scale structural patterns.
• **Flat pooling methods** — Simple global aggregation (sum, mean, max) over all node features produces a graph-level embedding in one step; while simple, these methods lose hierarchical structural information and treat all nodes equally regardless of importance
• **Hierarchical pooling** — Progressive graph reduction through multiple pooling layers creates a pyramid of graph representations: DiffPool learns soft assignment matrices, SAGPool/TopKPool select important nodes, and MinCutPool optimizes spectral clustering objectives
• **Soft assignment (DiffPool)** — DiffPool learns a soft cluster assignment matrix S ∈ ℝ^{N×K} that maps N nodes to K clusters: X' = S^T X (pooled features), A' = S^T A S (pooled adjacency); the assignment is learned end-to-end via a separate GNN
• **Node selection (TopK/SAGPool)** — Score-based methods compute importance scores for each node and retain only the top-k nodes: y = σ(GNN(X, A)), idx = topk(y), X' = X[idx] ⊙ y[idx]; this is memory-efficient but may lose structural information
• **Spectral pooling (MinCutPool)** — MinCutPool learns cluster assignments that minimize the normalized min-cut objective, ensuring that pooled graphs preserve community structure; the cut loss and orthogonality loss are differentiable regularizers
| Method | Type | Learnable | Preserves Structure | Memory | Complexity |
|--------|------|-----------|-------------------|--------|-----------|
| Global Mean/Sum/Max | Flat | No | No (single step) | O(N·d) | O(N·d) |
| Set2Set | Flat | Yes | No (attention-based) | O(N·d) | O(T·N·d) |
| DiffPool | Hierarchical (soft) | Yes | Yes (assignment) | O(N²) | O(N²·d) |
| TopKPool | Hierarchical (select) | Yes | Partial (subgraph) | O(N·d) | O(N·d) |
| SAGPool | Hierarchical (select) | Yes | Partial (GNN scores) | O(N·d) | O(N·d + E) |
| MinCutPool | Hierarchical (spectral) | Yes | Yes (spectral) | O(N·K) | O(N·K·d) |
**Graph pooling bridges the gap between node-level GNN computation and graph-level prediction, providing the critical aggregation mechanism that transforms variable-sized graph representations into fixed-dimensional embeddings while preserving hierarchical structural information through learned node selection or cluster assignment strategies.**