Linked Open Data initiatives have made available a diversity of scientific collections where scientists have  annotated entities in Linked Open datasets with controlled vocabulary terms from ontologies. Annotations encode scientific knowledge which is represented in knowledge graphs and that can be exploited to enhance to compute semantic similarity measures, as well as to improve different data management tasks, e.g., query answering, ranking, or data mining.  We tackle the problem of predicting associations between entities represented in knowledge graphs and illustrate the performance of our proposed approaches to discover interactions among drugs and targets.  We discuss two graph-based approaches named semEP and esDSG, to solve this prediction problem. The semEP approach relies on semantic similarity measures to partition graphs of interactions of drugs and targets into parts where graph density and the similarity values of drugs and targets are maximized. We devise a formalization of semEP as  the Vertex Coloring Problem in a way that interactions between similar drugs and targets are colored in the same color and novel interactions are predicted from each of these clusters.  An extension of the greedy algorithm DSATUR provides an approximate solution to semEP.  The semEP behavior is empirically compared with respect to machine learning-based  approaches for drug-target interaction prediction, and  the best novel predictions of all the methods are validated against the STITCH drug-target interaction resource.  The second esDSG approach extends a state-of-the-art approximate densest subgraph algorithm with knowledge about the semantic similarity of the nodes in the original graph, and then predicts potential novel interactions from the computed dense subgraph. Similarly, performance of esDSG is compared with existing drug-target interaction prediction approaches.  In both cases, the experimental results reveal how graph-based approaches that rely on semantic similarity measures in conjunction with topological information of the knowledge graph may have a great impact on pattern discovery tasks.