How does 'graclus' cluster nodes in graphs?

[hkim716]

Hi Matt, I'm trying to understand mnist_graclus.py, which used SplineConv and graclus.
I know that graclus is used for graph coarsening but I'm not sure how it clusters nodes.
For example, when the first pooling is used, graclus clustered 38 clusters from 75 nodes (input nodes).

I saw graclus used edge weights (pseudo coordinates in your paper) as one of arguments here below.
cluster = graclus(data.edge_index, weight, data.x.size(0))

Does this edge weight determine which nodes are going to be selected?

Then how does this cluster determine the number of clusters, e.g. 38 in my example?

And after the clusters are determined, how can we define newly defined edge information, e.g. new edge_index and new edge_attr?

If I am wrong, feel free to correct my understanding.

Thanks!

[rusty1s]

The Graclus pooling is described in Section 2.2 here and proceeds as follows:

1. We select a random node and connect it to a random neighbor/the neighbor with the highest edge weight to form a cluster.
2. If a node does not have a unclustered neighbor, it will form a cluster only containing itself.

As such, the number of resulting nodes is approximately reduced by half, but might be slightly higher in cases where a node needs to form a cluster solely with itself.

The new edge_index is then given by the union of edges of this cluster, and other information such as edge_attr or pos are averaged.