Data mining is the study of how to extract interesting information from data. The related domain of machine learning studies how to learn from data to improve the performance on a given task. Traditional approaches assume data can be represented with one table of independent tuples. However, in practical applications (e.g. biology, chemistry, the internet, social networks, robotics, ...) data is often very complex and can not be represented in such a format without loss of information. Therefore, more expressive formalisms have been considered. Recently, there is increasing agreement that graphs hit the right balance between expressivity and efficiency. Even though the principles of traditional mining and learning approaches can be transferred to some extent to graph mining, there is need for theoretical foundations for this emerging field. This project aims at developing a sound theoretical understanding of mining and learning with graphs, and to exploit this theory to construct effective algorithms for significant real-life applications. To realize this objective, this project will propose a consistent framework for mining and learning with graphs, develop the necessary theory and representations for constructing effective algorithms in this framework and describe their complexity, and apply these algorithms to achieve significant contributions in the studied application domains. Key features of the methodology include the integration of insights from graph theory in data mining and learning approaches, the development of efficient prototype algorithms, and the interdisciplinary collaboration with application domain experts to validate the practical value of the work,