Node classification with random labels for GNNs

Question

I decided to train GCN on the Cora dataset for the node classification task, however, with the random labels, i.e., applying np.random.shuffle(labels). For the default set of parameters, I am getting an accuracy of around 0.3 for the test set and 0.4 for the train set. I expect that for the random labels, the accuracy would be 1/number of classes. So in the case of Cora: 1/7 = 0.14.

Do you have any intuition why graph neural networks perform better than the random case? I am aware that in [1] authors trained the models on the random labels and achieved perfect results on the train set. However, for test size they still were around the 1/number of classes.

I checked simpler models such as RandomForests or SVC and the final accuracy for the test size is indeed 1/7.

[1] Zhang, C., Bengio, S., Hardt, M., Recht, B., & Vinyals, O. (2021). Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3), 107-115.

Answer 1

The Cora dataset is unbalanced (s. here). It's graph consists of 2708 nodes and the label distribution (for labels 1 to 7) is 818, 426, 418, 351, 298, 217, 180, i.e. there are 818 nodes labelled 0, 426 nodes labelled 1 and so on. If your network always predicts the label 0, then its accuracy should be $\frac{818}{2708} \approx 0.38$. Which roughly matches your number, probably this is the reason why the accuracy is not $\frac{1}{7}$.