Deepfake videos are increasingly used in spreading fake news or propaganda having a serious impact on people and society. Traditional deepfake detectors exploit spatial and/or temporal inconsistencies to differentiate between real and fake videos. Owing to the rapidly advancing deepfake creation algorithms, the latest detectors have made use of physiological and biological facial features to create more generic solutions. Our proposed solution uses facial landmarks as the physiological identifiers of a person’s face and through them develops a relationship between facial areas in normal speech and tampered speech. By creating a graph structure from the resulting sparse data, we were able to use a spatio-temporal graph convolutional network for classification, which has significantly fewer parameters and a shorter training time than traditional CNNs. We conducted a multitude of experiments on 3 datasets, utilizing spatio-temporal features. The results demonstrate that this technique has better generalization, and high performance compared to latest research in deepfake detection without the reliance on large deep learning models which are tuned to learning image discrepancies more than data patterns. Moreover, our use of facial landmark-based features with a graph structure paves the way for the development of an explainable AI model that can be relied on. •Deepfake video generation algorithms modify the data associated with facial landmarks to create fake images and videos which are used as a source for spreading fake news.•Facial landmarks represent an important structural representation of the face.•A feature vector can be found on each facial landmark to create a representation of the facial structure.•Facial structural data in form of landmarks and feature vectors can be classified using Graph CNNs to detect deepfakes since GCNs are better suited for sparse geometric data.