Recommended way to process disconnected graphs?

Questions
#1

I want to train a model for link prediction. The input would be one central graph + a set of smaller graphs, and I want to predict links between each smaller graphs’s nodes and the central graph’s nodes. However it is unclear to me how the graphs should be input to my model since disconnected graphs are used for batch processing. From what I understand a batch of graphs is meant to be processed as several separate instances of the same problem, not one instance made of several disconnected graphs.

Is there a recommended approach for such problems ? One idea I had was to use a heterograph instead, where each small graph and the central graph would have one dedicated node type. Additionally I would add one dummy node connected to every other node to make my heterograph connected.

Am I missing something or is it the right approach ?

Thanks in advance for the help !

#2

If you have multiple disconnected components, you can always batch them for parallel computation. For your setting, can you have a model that takes two arguments, one for a central graph and one for batched smaller graphs?

#3

Thanks for your answer.

Not really, because they are part of the same problem, e.g. having a link between a node from the central graph and a node from a smaller graph implies other nodes (from the same smaller graph or from any other) is less likely to have a link with this particular node. More specifically, central nodes have a limited amount of “resources” they can share with smaller graph.

If I understand your question, it would boil down to processing each couple (smaller graph + central graph) separately ? I do not think it would work, I really need to take the interactions between smaller graphs into account.
Maybe this could be done using a RNN fed with a progressively growing central graph, however this would not be ideal since full information about the instance would not be accessible before the last iteration.

Since I created this topic I found this paper which I think can help others working on similar problems. I only skimmed through it but fig 3(a), page 7 suggests they do exactly what I proposed in my initial post with heterograph, I might try that if there is no better way

EDIT: to be more precise, my doubt towards RNN or other sequence models is that there is no natural way to order my graphs, but maybe it is not a real problem

#4

This topic was automatically closed 30 days after the last reply. New replies are no longer allowed.