I am reading the paper The Graph Neural Network Model by Scarselli et al. I understand how node classification works. I am having trouble understanding how graph classification works however. In particular, in the section titled The Learning algorithm, the authors mention that

Learning in GNNs consists of estimating the parameter such that w approximates the data in the learning data set

enter image description here

where qi is the number of supervised nodes in Gi. For graph focused tasks, one special node is used for the target (qi = 1 holds), whereas for node-focused tasks, in principle, the supervision can be performed on every node.

The node focused task approach makes sense to me; you would essentially compare the ground truth to each output of the "local output function" for each node, and backprop accordingly. However, based on the above description, I do not understand what you would do to classify the graph as a whole, given its label. What do they mean by "one special node is used for the target (qi = 1 holds)"? Why are they talking about a "special node"? Why is there no mention of the graph's label? Isn't that what we want to predict?


After reading through the entire paper, and specifically looking at the Mutagenesis example, I got a better understanding of how graph classification works (as described in this paper at least). However, my understanding is still not complete. I will explain what I understand, and raise a followup question below.

As the text above suggests, a particular node in the graph is chosen (I believe this can be done at random), and it will be the only node in the graph that is "supervised." All other nodes will be unsupervised (so we will not make any predictions on those nodes). We choose the local output function in such a way as to have it output a number between -1 and 1 (although I'm unsure as to whether or not you could pick a function that instead outputs a number between 0 and 1. I believe you can, and it's just a matter of what activation function you would like to choose i.e sigmoid vs tanh in this example). If the output is < 0, we predict the graph has label -1, and 1 otherwise.

Now we just do what we did with node prediction, except we only backpropagate on this single node that we chose.

This, however, raised a followup question for me. If you are training on multiple graphs (for graph classification), each of which has a different connectivity (which is usually the case, and is the case in the Mutagenesis example), how do you backpropagate? Each graph (in this case, molecule) represents a different neural network ...


1 Answer 1


The equation you pointed out in the paper has posed the graph learning problem based only on the nodes of the graph. Therefore, to perform graph level tasks like graph classification, one would need a 'special node' which introduces a node that represents the entire graph. This is all just to make the equation hold for graph level tasks which are not dependent on just one node.

The paper which you are reading is quite old and the new GNN formulations are based on the kipf-GCN (https://arxiv.org/abs/1609.02907). It is much simpler to understand, implement and has become the standard GCN. If you want to keep with the current hot topic of GNN, I would recommend you having a look at Kipf's blog (https://tkipf.github.io/graph-convolutional-networks/) for a simple intuition for the modern-day GCNs.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.