Conversational systems have become increasingly popular as a way for humans to interact with computers. To be able to provide intelligent responses, conversational systems must correctly model the structure and semantics of a conversation. In this paper, we introduce the task of measuring semantic (in)coherence in a conversation with respect to the background knowledge, which relies on identification of semantic relations between concepts introduced during a conversation. We propose and evaluate graph-based and machine learning approaches for measuring semantic coherence using knowledge graphs, their vector space embeddings and word embedding models, as sources of background knowledge. We demonstrate in our evaluation results how these approaches are able to uncover different coherence patterns in conversations on the Ubuntu Dialogue Corpus.