topk pooling

**TopK Pooling** is a graph neural network pooling method that learns a scalar importance score for each node and retains only the top-k highest-scoring nodes along with their induced subgraph, providing a simple and memory-efficient approach to hierarchical graph reduction. TopK pooling computes node scores using a learnable projection vector, selects the most important nodes, and gates their features by the learned scores to maintain gradient flow. **Why TopK Pooling Matters in AI/ML:** TopK pooling provides a **computationally efficient alternative to dense pooling methods** like DiffPool, avoiding the O(N²) memory cost of soft assignment matrices while still enabling hierarchical graph representation learning through learned node importance scoring. • **Score computation** — Each node receives a scalar importance score: y = X·p/||p||, where p ∈ ℝ^d is a learnable projection vector and X ∈ ℝ^{N×d} is the node feature matrix; the score reflects each node's relevance for the downstream task • **Node selection** — The top-k nodes (by score) are retained: idx = topk(y, k), where k = ⌈ratio × N⌉ for a predefined pooling ratio (typically 0.5-0.8); the remaining nodes and their edges are dropped, creating a smaller subgraph • **Feature gating** — Selected node features are element-wise multiplied by their sigmoid-activated scores: X' = X[idx] ⊙ σ(y[idx]), where σ is the sigmoid function; this gating ensures that gradient information flows through the score computation during backpropagation • **Edge preservation** — The adjacency matrix is reduced to the subgraph induced by the selected nodes: A' = A[idx, idx]; only edges between retained nodes are kept, which can disconnect the graph if important bridge nodes are dropped • **Limitations** — TopK pooling can lose structural information because dropped nodes and their edges are permanently removed; it may also disconnect the graph or remove nodes that are structurally important but have low feature-based scores | Property | TopK Pooling | DiffPool | SAGPool | |----------|-------------|----------|---------| | Score Method | Learned projection (Xp) | Soft assignment GNN | GNN attention scores | | Selection | Hard top-k | Soft assignment | Hard top-k | | Memory | O(N·d) | O(N²) | O(N·d + E) | | Structure Awareness | Low (feature-based) | High (learned clusters) | Medium (GNN-based) | | Connectivity | May disconnect | Preserved (soft) | May disconnect | | Pooling Ratio | Fixed hyperparameter | Fixed K clusters | Fixed hyperparameter | **TopK pooling provides the simplest and most memory-efficient approach to hierarchical graph pooling through learned node importance scoring and hard selection, trading structural preservation for computational efficiency and enabling deep hierarchical GNN architectures that would be impractical with dense assignment-based pooling methods.**