Facial image super-resolution (SR) generates a high-resolution (HR) facial image from a low-resolution (LR) facial image. Compared with natural images, facial images are so highly structured that local patches at similar locations across different faces share similar textures. In this paper, a novel graph-based neural network (GNN) regression is proposed to leverage this local structural information for facial image SR. Firstly, the grid representation of an input face image is converted into its corresponding graph representation, and then a shallow neural network is trained for each vertex in the graph in order to regress the SR image. Compared with its grid-based counterpart, the graph representation combines both coordinate affinity and textural similarity. Additionally, the NN weights of a vertex are initialized with those converged ones from its neighbors, resulting fast convergence for training and accurate regression. Experimental comparison with the state-of-the-art SR algorithms including those based on deep convolutional neural networks (DCNN) on two benchmark face sets demonstrate the effectiveness of the proposed method in terms of both qualitative inspections and quantitative metrics. The proposed GNN is not only able to deal with facial SR, but also has the potential to apply to data examples with any irregular topology structure.