In many real-world problems, one deals with input or output data that are structured. This thesis investigates the use of graphs as a representation for structured data and introduces relational learning techniques that can efficiently process them. We apply the techniques to two biological problems. On the one hand, we use decision trees to predict the functions of genes, of which the hierarchical relationships can be structured as a graph. On the other hand, we predict chemical activity of molecules by representing them as graphs. We show that, by exploiting graph properties, efficient learning techniques can be developed. It turns out that in both cases, the relational models are not only learned more efficiently, but their predictive performance significantly improves as well.