Deterministically coarsening in an autoencoder for a static graph?

[FinnOD]

Hi Matthias and the gang,

I wish to use an autoencoder to impute and cluster a set of edge weightings on a known static graph. To do so I have transposed the network to the linegraph, ie. node weighted, so I'm happy to address either problem (node or edge weightings).

I have had success using convolution layers and graclus clustering to create coarser representations copied from #2687 and #2786, however with this method I cannot create very coarse graphs. Even applying graculus 10 times only leads to a ~20% reduction in the number of nodes and edges. Here is an example with only one coarsening and upsampling step.

class GCN_coarsening(nn.Module):
    def __init__(self, input_shape, hidden_size=8):
        super(GCN_coarsening, self).__init__()
        
        self.N_nodes, self.N_features = input_shape[0], input_shape[1]

        self.conv1 = GCNConv(1, hidden_size)
        self.conv2 = GCNConv(hidden_size, 1)

    def forward(self, data):
        
        # Encode
        x = self.conv1(data.x, data.edge_index)
        x = torch.tanh(x)
        cluster = graclus(data.edge_index, num_nodes=x.size(0))
        coarsened_data = max_pool(cluster, Data(x=x, edge_index=data.edge_index))

        # Decode 
        cluster, perm = self.consecutive_cluster(cluster)
        upsampled_x = coarsened_data.x[cluster]
        x = self.conv2(upsampled_x, data.edge_index).view(-1, 1)
        return x


    def consecutive_cluster(self, src):
        unique, inv = torch.unique(src, sorted=True, return_inverse=True)
        perm = torch.arange(inv.size(0), dtype=inv.dtype, device=inv.device)
        perm = inv.new_empty(unique.size(0)).scatter_(0, inv, perm)
        
        return inv, perm

My other issue is with the dynamic nature of the clustering and the size of the latent vector. Since the most coarse graph represents the beginning of the decoder, I am having trouble implementing Matthias's solution to #2786. I've found either of these solutions will lead to a latent vector who's size is defined by the coarsest graph, and therefore is always a different shape, leading to issues for using this vector for other purposes, or as hkim716 ran into it is hard to define the suggested linear layer.

Therefore my question is either:
A. Is there a known better method for autoencoding features on a known graph than what hkim716 and I were proposing?
or
B. How can you achieve deterministic and more aggressive progressive clustering/coarsening in pytorch geometric?

Thank you for any help and for this excellent library.

[rusty1s]

I am not totally sure how your graph looks like, but at one point graclus will fail to coarsen the graph further if all your nodes are disconnected from each other. Might this be the case?

Also, the clustering is not really deterministic as the start nodes are picked randomly. I am not sure if setting a seed via torch.manual_seed works but worth a try.

What you can also do is use the clustering METIS routine from torch-sparse. See here for an example.