Graclus clusters graph vertices so large graphs can be coarsened into smaller, simpler graphs. In PyTorch Geometric, it provides the clustering stage: nearby or structurally similar nodes become super-nodes, then pooling combines their features and edges. Repeating clustering and pooling creates a hierarchy of progressively coarser graphs. section 7.10
Use Graclus in a coarsening pipeline:
- Prepare the graph structure, such as an undirected edge index. section 7.10
- Call graclus(edge_index) to obtain a cluster tensor mapping every node to a cluster. section 7.10
- Pass the clusters and graph data to max_pool() or avg_pool() to merge each cluster into a coarser graph. section 7.10
- Repeat the process when a multilevel graph hierarchy is useful. section 7.10
PyTorch Geometric workflow
A compact implementation applies Graclus and max pooling to the KarateClub graph: `edge_index = to_undirected(data.edge_index)`; `cluster = graclus(edge_index)`; `data_coarse = max_pool(cluster, data)`. In the shown run, the graph decreases from 34 nodes and 156 edges to 22 nodes and 98 edges. section 7.10
Traffic-network trade-off
A 50,000-node, 200,000-edge road graph became cheaper to analyze after Graclus and max_pool, but high-traffic detail and clustered labels suffered. Applying coarsening only at an intermediate state layer preserved finer city-level information while retaining efficiency. section 7.10.1
Figure 7.4 Graph coarsening process: The original graph (left) is progressively simplified through coarsening. The first stage (middle) merges nearby nodes to create a coarsened graph, while the second stage (right) further reduces the graph’s complexity, highlighting the essential structure for efficient processing.
Shows how repeated clustering and pooling progressively simplify an original graph into a multilevel hierarchy. section 7.10
