Application of ideas from graph theory in machine learning
Graphs are a very flexible form of data representation, and therefore have been applied to machine learning in many different ways in the past. You can take a look to the papers that are submitted to specialized conferences like S+SSPR (The joint IAPR International Workshops on Structural and Syntactic Pattern Recognition and Statistical Techniques in Pattern Recognition) and GBR (Workshop on Graph-based Representations in Pattern Recognition) to start getting a good idea of potential applications. Some examples:


Within the Computer Vision field, graphs have been used to extract structure information that can later on be used on several applications, like for instance object recognition and detection, image segmentation and so on. 
Spectral clustering is an example of clustering method based on graph theory. It makes use of the eigenvalues of the similarity matrix to combine clustering and dimensionality reduction. 
Random walks may be used to predict and recommend links in social networks or to rank webpages by relevance.