Deepfake detection plays a key role in preventing the misuses of artificial intelligence in video editing. Current deep learning-based deepfake detection methods often perform quite well in intra-dataset testing, but they may lose good performance in cross-dataset testing. In other words, generalization capability is still a crucial problem to be resolved. In this paper, we address deepfake detection by treating an image as non-Euclidean data and representing it as a graph so as to infer the informative connections between image patches/nodes to improve the detector's generalization capability. Specifically, we propose a graph neural network-based paradigm that casts deepfake detection as a graph binary classification problem. First, we propose a dual-branch network to extract node features from both RGB images and their color difference images (CDIs) via the Transformer-based trainable node encoder module (TNEM). Second, we adopt the adjacency matrix to establish the connections of the nodes and further optimize the graph representation by applying the adaptive threshold to the adjacency matrix. Third, multi-head graph convolutional neural networks are carried out for node feature extraction. RGB node features and CDI node features are concatenated and separately fed into the graph classifier and node classifier for forgery detection and forgery localization. Experimental results demonstrate that our method can overall outperform other state-of-the-art methods on 7 popular benchmark datasets. Notably, our model achieves the highest AUC values of 96.19%, 80.99% and 87.68% on Celeb-DF-V2, DFDC and DFDCP in turn when trained on FF++ (C23). The visualization of node classification results also provides good interpretability of our proposed approach.