Graph coarsening makes a large graph cheaper to process by merging nodes and edges into a smaller graph. The aim is to retain the structure needed for analysis or GNN training, not to reproduce every detail. It is a trade-off: lower memory and computational demands in exchange for a representation that may differ from the original. section 7.10 section 7.11
A coarsening workflow has three parts:
- Cluster nodes. A clustering algorithm groups nodes into super-nodes; a partition records which original nodes belong together. section 7.10
- Pool each cluster. Combine its node information to construct the smaller graph and its features. In PyTorch Geometric (PyG), graclus() or voxel_grid() can form clusters, while max_pool() or avg_pool() can pool them. section 7.10
- Handle targets before supervised training. The coarsened graph needs suitable labels; weights learned on it can then be tested on the original graph. Choosing how to consolidate labels is a separate decision. section 7.10 section 7.3.1
Listing 7.4 Graph coarsening using graclus and Max_Pool
import torch from torch_geometric.data import Data from torch_geometric.nn import graclus, max_pool from torch_geometric.utils import to_undirected from torch_geometric.datasets import KarateClub dataset = KarateClub() data = dataset[0] # Get the first graph edge_index = to_undirected(data.edge_index) #1 batch = torch.zeros(data.num_nodes, dtype=torch.long) #2 cluster = graclus(edge_index) #3 data_coarse = max_pool(cluster, data) #4
The PyG example makes the two-step workflow concrete: convert the graph to undirected edges, obtain clusters with graclus(), then pass those clusters and the original data to max_pool(). section 7.10
Table 7.4 Input and output graphs from listing 7.4
|
Input
|
Output
|
|---|---|
Data(x=[34, 34], edge_index=[2, 156], y=[34], train_mask=[34])
|
DataBatch(x=[22, 34], edge_index=[2, 98])
|
|
Nodes: 34 Edges: 156
|
Nodes: 22 Edges: 98
|
The example shrinks a 34-node, 156-edge graph to 22 nodes and 98 edges. Its displayed pooled output does not include labels, reinforcing the need to check target handling separately. section 7.10
Choosing where to coarsen
Consider a road network with 50,000 nodes and 200,000 edges. A trial using Graclus and max pooling across the whole graph reduced its size but lost high-traffic detail and produced poorly matched cluster labels, hurting model performance. A proposed alternative was to coarsen only an intermediate, state-level view while retaining a more detailed city-level view. The lesson is to test both speed and fidelity at the level where decisions will be made. section 7.10.1 section 7.11
