Machine learning for graphs
The world of machine learning and data analytics has never been more exciting than the last 5 years or so. Most importantly, there seems to be no end to the good times. The digitization of human activities generates vast amounts of valuable data. These data need advanced algorithms to make sense of and capable data scientists and machine learning engineers to guide them in finding the needle in the haystack.
Data come in many forms. Some data are static and others dynamic. The former can easily and conveniently be represented in tabular form and fed into advanced machine learning algorithms to find patterns and make predictions. The former can be represented as time series and understood using similarly advanced algorithms.
There exists, however, another kind of data with special structure that are increasingly becoming more common and require new machine learning methods to understand them. These new data have special structure that cannot be adequately captured in tabular format or as a time series.
The new data come with a graph, or equivalently network, structure. Each data point can no longer be thought of as an i.i.d. sample from the same distribution. If your background is in Computer Science then you are very likely familiar with the graph data structure. If not, the basic concepts are straightforward; a good resource for learning about the graph data structure and graph algorithms is Robert Sedgewick’s book.
A graph is made of nodes that represent different entities and edges that denote links or relationships between pairs of entities. Both nodes and edges can have a type and one or more properties. A familiar example of a graph is a social network such as Facebook (see figure). The nodes are people with properties such as their name, location, date of birth, etc. Edges in a social network denote relationships between people such as friendship. A property of such an edge could be the date the relationship was established.
A network with only a single node and edge type is called homogeneous. The above social network example is a homogeneous network. If we add at least one more node type or edge type then we will have a heterogeneous network. If for example we add ‘group’, and ‘business’ nodes and new ‘married to’ and ‘works for’ relationships, then our social network becomes a heterogeneous network. Most realistic graph-structured data will be heterogeneous.
Finally, we can distinguish graph structured data into static and dynamic. Static networks do not change meaning that no new nodes or edges are added. Dynamic networks do change either because new nodes or new edges are added in time. Facebook as a social network is an example of a dynamic graph; new people are always joining and many users establish new friendships.
We know that for traditional machine learning or predictive analytics tasks the goal is classification or regression. For example, a retailer might be interested in predicting the expected total revenue for a person visiting his online store. As another example, a credit union might want to make a prediction as to whether a potential customer will default on a loan or not. What kind of predictive analytics problems can we address for graph-structured data?
Well, for one, we can tackle the same problems as in traditional analytics. However, the terminology we use might be a bit different. For example, assuming that the credit union organized their customer data into a graph, say by representing customers, private and commercial, as nodes and relationships such as ‘works for’, ‘married to’, ‘lives in city’, etc, into edges, then the same question about the probability of loan default can be asked. We can specify a binary attribute with every node to denote whether a customer has defaulted on a loan before or not. For new customers, we can try and predict the probability that this binary variable will be one, or default in common language. In graph analytics we refer to such problems as node attribute inference. The attributes we want to predict can be binary or continuous requiring that we solve a classification or regression problem respectively. We can similarly predict edge attributes.
There are also new types of questions that are more appropriate to ask of graph-structured data. One such problem is link prediction. For example, for a social network, we might want to predict whether two people will become friends in the future. Why do we want to know that? Because we can use our predictions to recommend people to connect with. In fact, many social networks such as Facebook and LinkedIn tdo exactly this. However, recommendations don’t have to be limited to social networks.
An e-commerce website such as Amazon wants to predict what product a customer is more likely to want to buy next and recommend them to her. Similarly, a video streaming service provider might want to recommend TV shows and movies that customers might enjoy and, of course, purchase. Building such recommender systems is not new and much research has been devoted to it. However, re-phrasing the problem as that of link prediction in graphs is a new approach that is steadily becoming more and more popular because of the potential for the new approach to make better predictions and also because the old methods do not scale gracefully with big data but the graph-based approaches do.
Another important problem suitable for graph machine learning is community detection. The goal here is to determine groups of nodes that belong to the same community. What makes a community needs to be defined but often is data specific. For example, for a social network, a community could be a group of members who have a common interest such as woodworking or comic books. In a criminal network, a community would be a group of people who belong to the same crime syndicate. In a network of research papers connected with other papers based on citations, a community could be papers that study the same subject such as machine learning, theory of algorithms, computation chemistry, etc.
So where should one begin for working with graph-structured data and where can one find information about state-of-the-art methods? One resource is this blog as over the next few weeks, we will provide an overview of traditional and newer machine learning methods applied to graph-structured data. Furthermore, there exist a significant number of libraries for working with graphs for the two most popular programming languages for data scientists, e.g., NetworkX for Python, and iGraph for R. Finally, the excellent Stellargraph and PyTorch Geometric libraries for Python implements a number of state-of-the-art graph machine learning algorithms including graph convolutional networks.
