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