Node Matching between Graphs

[dieser-max]

Hey, I have a problem and need help.

For my research experiment, I have to do some sort of node matching between graphs and I did not find an example that could help me, but I do not think I am the first with this Problem.

My Problem is that I have a few small Graphs with weighted edges. One for each lab run. All those Nodes have quite similar features, but sometimes nodes are missing. To compare my results, I need to match the nodes between the graphs. E.g: In Run/Graph 1 Node 3 corresponds to Node 5 in Graph 2 and is missing in Graph 3 up to 20 Graphs just based on the node embedding in their respective Graphs. The weights of the predicted Links do not matter.

I wanted to solve it by doing a Link prediction between the graphs. In the end, I want to have an adjacency matrix that tells me how the nodes are linked within their graph and between all the others (or just between the Graphs if this is better).

I am currently generating synthetic Data that is based on multiple different runs (I manipulate the node feature values and remove some nodes) to train the model, but I am not sure whether it is better to input the Graphs as pairs or as bigger groups.
If I input them as a big Group I would have an adjacency Matrix where on and near the diagonal I have the edges of Nodes within one Graph and on the sub-diagonals I would have the links between the Graphs. Or is there a better way, maybe with the DataLoader, but I can't think of a way that keeps the Links between the Graphs for Training.
If there is any research, frameworks, or repos with a similar problem, I would be delighted if you told me. Thanks in advance!

[rusty1s]

You might find https://github.com/rusty1s/deep-graph-matching-consensus interesting.

[rusty1s]

PyG should be able to handle varying node sizes, but the feature sizes need to be the same. Is this an issue in your case?

[dieser-max]

That´s odd, because all nodes have the same number of features. Only the number of nodes in the graph is different.
But the problem could be the way I concatenate the Data_sets the y values in particular.

[rusty1s]

Mh, okay. Can you find out for which of the data attributes the error happens exactly?

[dieser-max]

Yes, the problem was that I carried an y with a different shape in my Data Object, that I used for a visualization (and now where in the model). I removed it and it works.
Thank you for your help so far!
Could you tell me how I could optimize the model so that it can handle the case that a node is in the target graph and not in the source graph and vice versa? It really seems to struggle there.
And could you tell me your opinion on the case that the testing accuracy (over many tries) is higher than the training accuracy?

[rusty1s]

This is a bit tricky because the current code base is not designed for this. The idea would be that you map all non-existing mappings to a dummy node in the reverse graph (by modifying y, and by appending a "dummy node" with zero features and no connections to your graph). That should unblock you.