| Graphs are mathematical constructs for representing objects or systems which contain structural (i.e. relationship) information. Graphs have been used in many domains, from software engineering to artificial intelligence. However, the use of graphs in machine learning has been limited, compared to the more prevalent vector model which does not capture structural information. This can be attributed to the fact that until recently we have not had suitable graph-theoretic tools for dealing with graphs, and that comparing graphs for the purpose of evaluating structural matching is often of high time complexity. For these reasons, most machine learning approaches that deal with graph-based data introduce either restrictions on the type or related attributes of the graphs used, or they require a totally new mathematical foundation for handling graphs (such as probability theory). An unfortunate drawback of these types of methods is that existing machine learning algorithms either cannot be applied or require extensive modifications.
In this book, we present methods for utilizing graphs with well-known machine learning algorithms, such as fc-means clustering and fc-nearest neighbors classification, with virtually no significant modifications; the extensions for allowing these algorithms to use graphs is direct and intuitive. Further, we show how we can achieve polynomial time complexity with the restriction that the graphs contain unique node labels. This is the only restriction we place on the graphs, and we can even discard this limitation if we use a sub-optimal approximation approach for determining graph distance or if the graphs are relatively small. |
