Feature-based methods
One very simple (yet powerful) method for applying ML on graphs is to consider the encoding function as a simple embedding lookup. When dealing with supervised tasks, one simple way of doing this is to exploit graph properties. In Chapter 1, Getting Started with Graphs, we learned how graphs (or nodes in a graph) can be described by means of structural properties, each “encoding” important information from the graph itself.
Let’s forget graph ML for a moment; in classical supervised ML, the task is to find a function that maps a set of (descriptive) features of an instance to a particular output. Such features should be carefully engineered so that they are sufficiently representative to learn that concept. Therefore, as the number of petals and the sepal length might be good descriptors for a flower, when describing a graph, we might rely on its average degree, its global efficiency, and its characteristic path length.
This naï...
