Graph Pooling Methods

What is Graph Pooling?

Graph pooling reduces graph size while preserving important structural and feature information. Similar to pooling in CNNs, it creates hierarchical representations by progressively coarsening the graph through node clustering or selection.

Pooling Methods

TopK Pooling

• Mechanism: Select top-k nodes by learned scores
• Advantages: Simple, efficient, parameter-light
• Limitations: May disconnect graph structure

SAGPool (Self-Attention Graph Pooling)

• Mechanism: Use self-attention to compute node importance
• Advantages: Structure-aware selection
• Trade-offs: Higher computational cost

DiffPool (Differentiable Pooling)

• Mechanism: Learn soft cluster assignments
• Advantages: End-to-end differentiable, preserves gradients
• Challenges: Dense assignment matrix, O(n²) memory

MinCutPool

• Mechanism: Minimize normalized cut objective
• Advantages: Preserves cluster structure
• Considerations: Complex optimization, orthogonality constraints

Hierarchical Architecture

Level 0: Original Graph (n nodes)
    ↓ Pool (ratio=0.5)
Level 1: Coarsened Graph (n/2 nodes)
    ↓ Pool (ratio=0.5)
Level 2: Abstract Graph (n/4 nodes)
    ↓ Global Pool
Level 3: Graph Representation (1 vector)

Readout Operations

Global Readout

• Mean: Average all node features
• Max: Take maximum across nodes
• Sum: Aggregate all features
• Attention: Weighted sum with learned weights

Hierarchical Readout

Concatenate representations from multiple levels:

h_graph = [h_level0 || h_level1 || h_level2]

Applications

1. Graph Classification: Molecular property prediction
2. Graph Regression: Protein function prediction
3. Graph Generation: Hierarchical graph synthesis
4. Graph Clustering: Community detection

Best Practices

• Choose pooling ratio based on graph size and task
• Use auxiliary losses (link prediction, entropy) for DiffPool
• Combine multiple readout strategies
• Monitor information loss across levels
• Consider graph connectivity preservation