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 ...


2 Answers 2


I am aware of two typical strategies for outputting a "graph-wide" prediction.

  1. Augment every graph with a special "root" node, and add an edge between the root and every other vertex of the graph. Use this as your "chosen" vertex.

  2. Have every node output a prediction (typically logits, but could do direct probabilities as well), and average across all nodes in the graph.

I've not seen anyone try the "random node" approach but it sounds like a more stochastic form of (2).

I don't quite understand your question about backpropagation, as the algorithm doesn't require that the computation graph be fixed.



I think one of the more easier GNNs to understand is the. The data is separated into a adjacency and one feature matrix. Obviously, the adjacency matrix differs from Graph to Graph to due different number of nodes in the respective Graph. However, the number of features that are attributed to each node remain the the same for each Graph. And this GNN can work for different Graph Sizes.

For Graph Classification their is also the strategy of applying an invariant pooling function like the sum or mean over each feature. And the result will be a 1xf vector


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.