Graph Embedding for Job Shop Scheduling Problem disjunctive graph

[MattJud]

Hi,

recently I've been trying to learn about graph embedding. I'm trying to do graph embedding for disjunctive graph in Job Shop Scheduling Problem(JSSP). I have 4000+ graphs for a 6x6 JSSP. I'm trying to make a model that can learn how to do embedding for my dataset.

I've been looking around in this github and found the autoencoder example. However, from my understanding is that the autoencoder here is being trained for link prediction using only 1 graph as the input. In my case, I want the model to train on multiple graphs from my dataset and maybe use the lower latent dimension of the embedding to do a simple regression to predict the minimum makespan of my JSSP.

Can someone maybe give me some insight on where should I start and how to do it?

[rusty1s]

It is correct that the autoencoder currently only works on a single graph. There are some modifications necessary to apply it to batches of graphs.

Nonetheless, I don't think that the embeddings produced by the autoencoder model are of much use for other down-stream tasks other than link prediction. Instead, you can either train your model directly in an end-to-end fashion against your ground-truth regression values, or you may want to look at our Deep Graph Infomax example (see examples/dgi.py). However, this example currently also considers only a single graph as input. It shouldn't be that complex to convert it into a mini-batch scenario though.

[MattJud]

Hi Matthias,

Thank you for the suggestion. I'll look into Deep Graph Infomax and try to implement it for my problem.

I've also already tried to use GCN and do a simple regression task with it and get subpar results. Do you have any other suggestions as to which other GNN architecture I should try? At the end of the day, I want to find out if there is a way to do a compact representation for a disjunctive graph.

Another thing that I'm interested in would be to do an Ensemble Method with multiple GNN, do you have any suggestion as to how should I approach this idea? And from my understanding, right now there is no algorithm to do a whole graph embedding where the encoder encodes both node features and edge connection at the same time, would it be possible and make sense if I make 2 models that learn vertex embedding and graph structure embedding separately and then combine their encoded result to do a simple regression as its benchmark?

[rusty1s]

There are some GNN operators that can better capture graph structures as others, e.g., GINConv or PNAConv, and you may try if those produces better results. In some sense, PNAConv can be already seen as an ensembling technique, as it makes use of multiple towers and aggregation procedures.