liveBook · Manning

Coarsened graph

As explained in Graph Neural Networks in Action

A simplified graph produced by aggregating nodes and edges from an original graph.

A coarsened graph simplifies a large graph by aggregating nodes and edges while preserving as much structural and relational information as possible. Fewer vertices and edges make the result easier to analyze and process. section 7.10

A typical coarsening workflow is:

  • Apply a coarsening algorithm to produce a normalized partition matrix, whose clusters become super-nodes. section 7.10
  • Construct the coarse graph and compute its node features and labels. section 7.10
  • Train on the coarsened graph, then test the resulting weight matrix on the original graph. section 7.10

PyTorch Geometric pipeline

In PyTorch Geometric, clustering can use graclus(), followed by pooling with max_pool() or avg_pool(). A KarateClub example makes edges undirected, creates a batch vector, computes cluster assignments with graclus(edge_index), and calls max_pool(cluster, data). The example reduces 34 nodes and 156 edges to 22 nodes and 98 edges. section 7.10

How Graph Neural Networks in Action covers it

How deep it goes
Explains partitioning, graph construction, feature computation, labels, training, clustering, and pooling, but not a universal algorithm.
Examples
Uses a KarateClub graph, graclus clustering, max_pool pooling, and a 34-node to 22-node reduction.
What you can do after
Apply it via PyTorch Geometric using clustering and pooling operations to produce a smaller graph.
How it connects
Connects graph coarsening with graph clustering, graph pooling, node features, labels, and graph learning.
Cover of Graph Neural Networks in Action
liveBookmanning.com
Read Graph Neural Networks in Action on liveBook Get the book at manning.com

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Graph Neural Networks in Action. The section links point to the parts of the book it draws on.