Graph Pooling

Graph pooling creates a multi-scale representation of the input graph by iteratively grouping nodes into clusters. This mimics the spatial pooling in CNNs, allowing the network to capture both fine-grained local patterns and coarse global structures.

• DiffPool learns a differentiable soft cluster assignment matrix.
• gPool projects nodes onto a trainable vector and selects the top-k.
• SAGPool uses self-attention scores to determine which nodes to retain.

Pooling operations are categorized by their output granularity:

• Global Pooling: Aggregates all node features into a single graph-level vector using operations like sum, mean, or max. This is simple but loses all structural hierarchy.
• Hierarchical Pooling: Produces a sequence of progressively coarser graphs. This preserves topological information and is essential for tasks requiring an understanding of substructures, such as molecular property prediction.

Modern pooling methods use end-to-end differentiable clustering to learn how to coarsen the graph as part of the training process. A GNN generates an assignment matrix S that maps N original nodes to K clusters.

• New node features: X' = S^T * X
• New adjacency matrix: A' = S^T * A * S This allows the model to learn task-specific node groupings without pre-defined heuristics.

An alternative to clustering is top-k pooling, which drops less important nodes to form a smaller graph. This is analogous to pruning.

• A learnable score is assigned to each node.
• Only the top k nodes with the highest scores are retained.
• The adjacency matrix is masked accordingly. This method is computationally efficient but can discard potentially useful information from low-scoring nodes.

A valid graph pooling operator must be permutation invariant. The output of the pooling operation must not depend on the arbitrary ordering of the input nodes. This is a fundamental constraint for all graph neural network operations.

• Sum and max aggregators are naturally permutation invariant.
• Learned clustering methods maintain invariance by ensuring the assignment matrix S is computed in a permutation-equivariant manner before the final invariant aggregation step.

For graph classification and regression, a final readout layer collapses the entire graph into a single fixed-size vector. This is the ultimate pooling step.

• Set2Set uses an LSTM-based attention mechanism to iteratively aggregate node features.
• Global Attention computes a weighted sum of all node embeddings.
• Concatenation of max and mean pooling across all nodes provides a simple but effective statistical summary.

The low-dimensional vector representation of a node that encodes its structural position and feature information. Pooling operators aggregate these embeddings to create graph-level summaries.

• Shallow methods: Node2Vec, DeepWalk use random walks
• Deep methods: GNNs generate task-specific embeddings
• Supply chain example: A factory node embedding captures its production capacity, location, and supplier connections

A theoretically maximally powerful GNN architecture under the message-passing framework, proven to be as discriminative as the Weisfeiler-Lehman test. GIN's sum aggregation is often used before pooling layers.

• Uses multi-layer perceptrons for node updates
• Learnable parameter epsilon controls self-feature retention
• Preferred backbone when graph-level classification accuracy is critical

The downstream task that directly consumes pooled graph representations. Given a set of graphs and their labels, the model predicts the category of unseen graphs.

• Binary classification: Identifying supply chain disruption risk (high/low)
• Multi-class: Categorizing BOM graphs by product family
• Pooling quality directly determines classification accuracy

Techniques like GNNExplainer and Integrated Gradients identify which nodes and edges most influenced a pooled graph prediction. Essential for auditing autonomous supply chain decisions.

• Reveals if pooling over-emphasized irrelevant subgraphs
• Provides counterfactual explanations for why a graph was classified as high-risk
• Critical for regulatory compliance in automated procurement

The principle of learning multi-scale graph structures where pooling produces progressively coarser representations. Mirrors how supply chains have natural hierarchies.

• DiffPool: Learns differentiable soft cluster assignments
• Top-K Pooling: Selects most informative nodes at each level
• Enables analysis at supplier, regional, and global network scales simultaneously

The process of jointly optimizing graph topology and node features when the input graph is noisy or incomplete. Pooling on learned structures often outperforms pooling on raw, unrefined graphs.

• Supply chain graphs often have missing supplier relationships
• Structure learning infers latent connections before pooling
• Improves robustness when supplier data is fragmented across ERP systems