Edge Pooling
Edge Pooling is a graph neural network pooling method that operates on edges rather than nodes, iteratively contracting the highest-scoring edges to merge pairs of connected nodes into single super-nodes, progressively reducing the graph while preserving local connectivity patterns. Edge pooling computes a score for each edge based on the features of its endpoint nodes, then greedily contracts edges in order of decreasing score.
Why Edge Pooling Matters in AI/ML:
Edge pooling provides structure-preserving graph reduction that naturally respects the graph's topology by merging connected node pairs rather than dropping nodes, maintaining graph connectivity and local structural patterns that node-selection methods like TopK pooling may destroy.
• Edge scoring — Each edge (i,j) receives a score based on its endpoint features: s_{ij} = σ(MLP([x_i x_j])) or s_{ij} = σ(a^T [x_i x_j] + b), where denotes concatenation; the score predicts which node pairs should be merged
• Greedy contraction — Edges are contracted in order of decreasing score: when edge (i,j) is contracted, nodes i and j merge into a super-node with combined features (typically sum or weighted combination); edges incident to i or j are redirected to the super-node
• Feature combination — When merging nodes i and j via edge contraction, the super-node features are computed as: x_{merged} = s_{ij} · (x_i + x_j), where the edge score gates the merged representation, maintaining gradient flow through the scoring function
• Connectivity preservation — Unlike TopK pooling (which drops nodes and can disconnect the graph), edge pooling only merges connected nodes, ensuring the pooled graph remains connected if the original was connected
• Adaptive reduction — The number of contractions can be controlled by a ratio parameter or by thresholding edge scores, providing flexible control over the pooling aggressiveness; typically 50% of edges are contracted per pooling layer
| Property | Edge Pooling | TopK Pooling | DiffPool |
|---|---|---|---|
| Operates On | Edges | Nodes | Node clusters |
| Mechanism | Edge contraction | Node selection | Soft assignment |
| Connectivity | Preserved | May break | Preserved |
| Feature Merge | Sum of endpoints | Gate by score | Weighted sum |
| Memory | O(E) | O(N·d) | O(N²) |
| Structural Info | High (local topology) | Low (feature-based) | High (learned) |
Edge pooling provides a topology-aware approach to hierarchical graph reduction that naturally preserves graph connectivity through edge contraction, merging connected node pairs to create meaningful super-nodes while maintaining the local structural patterns that are critical for graph classification and regression tasks.