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


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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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