Use max pooling when a graph is too large to process at its original resolution and clusters of nodes can be represented by fewer nodes. In PyTorch Geometric (PyG), `max_pool()` takes an existing node-to-cluster assignment and produces a coarser graph. It is the pooling step, not the clustering algorithm. section 7.10
The workflow has two steps:
- Cluster nodes, for example with `graclus(edge_index)`. The resulting tensor maps each original node to a cluster. section 7.10
- Pass the clusters and graph data to `max_pool(cluster, data)`. Nodes in each cluster are pooled into a node of the coarser graph using maximum-valued features. section 7.10
Coarsen a Karate Club graph
With a PyG `Data` object named `data`, make its edges undirected, then run `cluster = graclus(to_undirected(data.edge_index))` and `data_coarse = max_pool(cluster, data)`. The shown run reduces the graph from 34 nodes and 156 edges to 22 nodes and 98 edges. section 7.10
Clustering and pooling can be repeated to form a hierarchy of progressively smaller graphs, but size reduction can discard important detail. For supervised or semi-supervised tasks, labels for pooled nodes need careful reconciliation with the original labels. A road-network trial lost detail in high-traffic areas and produced unsatisfactory clustered-node labels; applying coarsening only at an intermediate geographic layer offered a way to retain finer-level detail. section 7.10 section 7.10.1
Do not confuse graph-coarsening `max_pool()` with max aggregation elsewhere in a graph model. For example, Jumping Knowledge can select the maximum feature value across layer outputs; that combines representations rather than clustering nodes into a smaller graph. section 7.10 section 3.2.2
