To improve the accuracy of event-based gait recognition, a method called voxel event graph neural network (VEGNN) is proposed. This method voxelizes the event stream and selects representative voxels as vertices of the graph. Then the edges are constructed based on spatio-temporal distance and temporal order constraints so that the event stream is constructed as a graph structure. Finally, a lightweight feature extraction network based on graph neural networks (GNNs) is used to efficiently capture spatio-temporal information and motion cues from the event graph. To evaluate our method, an event-based gait recognition dataset called Celex-Gait is created. Experimental results show that VEGNN achieves a gait recognition accuracy of 95.8% and 93.9% on the Celex-Gait dataset and the DVS128-Gait-Day dataset, respectively. Furthermore, compared to the state-of-the-art methods, VEGNN reduces the number of model parameters by 30%. This indicates that VEGNN achieves higher recognition accuracy with lower model complexity.