This paper tackles the problem of detecting incongruities between headlines and body text, where a news headline is irrelevant or even in opposition to the information in its body. Our model, called the graph-based hierarchical dual encoder (GHDE), utilizes a graph neural network to efficiently learn the content similarity between news headlines and long body paragraphs. This paper also releases a million-item-scale dataset of incongruity labels that can be used for training. The experimental results show that the proposed graph-based neural network model outperforms previous state-of-the-art models by a substantial margin (5.3%) on the area under the receiver operating characteristic (AUROC) curve. Real-world experiments on recent news articles confirm that the trained model successfully detects headline incongruities. We discuss the implications of these findings for combating infodemics and news fatigue.