3
$\begingroup$

I have a dataset and want to be able to construct a graph from it in a supervised fashion.

Let's assume I have a dataset with N nodes, each node has e.g. 10 features. Out of these N nodes, I want to learn a graph, i.e. an $N \times N$ adjacency matrix. So, I start with $N$ nodes and all I know is a 10-dimensional feature vector for each node. I have no knowledge about the relation between these nodes and want to figure it out.

Here is an example for $N=6$, but in practice $N$ is not fixed. enter image description here

So the output I would like to get here is a $6\times6$ adjacency matrix, representing the relations between the nodes (undirected).

Note: N is arbitrary and not fixed. So an algorithm should be able to perform on any given N.

My dataset is labeled. For the training dataset, I have the desired adjacency matrix for each collection of input nodes, which is filled with $0$s and $1$s.

However, the output of the algorithm could also be an adjacency matrix filled with non-integer numbers in $[0,1]$, giving some kind of probability of the nodes being connected (preferably close to $0$ or $1$ of course). So I could easily give a number as the label for each node. In the above example, the labels for the three connected nodes could be class $1$, and so on.

Is there any kind of supervised learning algorithm (e.g. some sort of graph neural network) that can perform these tasks?

Improve this question
$\endgroup$
3
  • $\begingroup$ Now, I cannot answer your question, but I can provide you some information about the application of deep learning to graphs. This is often called "geometric deep learning". And, yes, there are "graph neural networks". You may search for them on the web. There should already exist models for your use case. If you find a solution, feel free to provide an answer below to your own question for future readers ;) $\endgroup$
    – nbro
    Mar 21, 2020 at 16:50
  • $\begingroup$ Thanks a lot! I have already tried to search the web for this of course but I could not find any useful information, probably also partly due to the fact that I do not know the right terminology in this field. That's why I posted my question here. $\endgroup$
    – basti123
    Mar 21, 2020 at 16:54
  • $\begingroup$ See if this paper Junction Tree Variational Autoencoder for Molecular Graph Generation can be useful. I had read it several months ago and I even gave a presentation, but I forgot the details, but I remember that it was about generating graphs. $\endgroup$
    – nbro
    Mar 21, 2020 at 20:53

1 Answer 1

Reset to default
2
$\begingroup$

It's perfectly reasonable to apply 'traditional' Deep Learning approaches to try and learn an adjacency matrix (a matrix is just a vector of vectors, which can be flattened into a single output vector) but you might need a lot of training data as N gets larger.

Your outputs could certainly have the form of an adjacency matrix, as you describe. Whether it's more useful to have 'boolean' (either 0 or 1) or 'probabalistic' entries in the matrix depends both on the data and the specifics of your end application.

Improve this answer
$\endgroup$
4
  • $\begingroup$ And dealing with the variable input and output sizes would be done using some sort of RNN? $\endgroup$
    – basti123
    Mar 22, 2020 at 10:44
  • $\begingroup$ It's not clear that variable sizes are needed: just fix large enough N. $\endgroup$
    – NietzscheanAI
    Mar 24, 2020 at 12:18
  • $\begingroup$ N can easily be as large as 800 or 1200 or so. There must be a more efficient approach. $\endgroup$
    – basti123
    Jul 21, 2020 at 11:12
  • $\begingroup$ That's not large as far as deep learning is concerned. $\endgroup$
    – NietzscheanAI
    Jul 22, 2020 at 11:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .