An incongruent headline detection system receives a request to determine a headline incongruence score for an electronic document. The incongruent headline detection system determines the headline incongruence score for the electronic document by applying a machine learning model to the electronic document. Applying the machine learning model to the electronic document includes generating a graph representing a textual similarity between a headline of the electronic document and each of a plurality of paragraphs of the electronic document and determining the headline incongruence score using the graph. The incongruent headline detection system transmits, responsive to the request, the headline incongruence score for the electronic document.