Henry AI Labs

DeepWalk

Applications of Deep Learning are frequently described as being relevant to ‘perceptual data’. This perceptual data includes things such as images and audio. Generally, Deep Learning is highly useful for any high-dimensional data such as text, and in this case, social networks. Social Networks are graph models which consist of a set of nodes and their connections to other nodes. Traditional machine learning models would try to model each node by a set of features such as ‘number of followers’ or ‘tweets per month’, however, the DeepWalk method aims to construct features from the connectivity in the graph.

Without a clever way of doing this, it is very difficult to use the connections in the graph as features for machine learning models. Adding features for connections will result in very sparse connections. This is a good point to begin to understand the similarity between graph connection modeling and text modeling. Probabilistic language models aim to take the textual context or some recently occurring words and predict the next word in the sequence. With an enormous vocabulary of words, this word is naively encoded in a very sparse form such as [0 0 .. 0 1 0 .. 0 0]. Connections to vertices is naively modelled in a very similar way with the 1 denoting vertices the node is connected to and 0 denoting vertices which are not connected. In this sense, graph modeling and language models are similar in that they are very sparsely represented.

The task of Probabilistic Language modeling was greatly facilitated with the development of the Word2Vec technique. The high-level idea behind this is to embed words based on their context with other words. For example, in the sentence “The quick brown fox jumps over the lazy dog.” Examples of contextual pairs fed to a supervised learning model would be (quick, fox), (brown, fox), and (jumps, fox). With an enormous corpus this method can embed words into a dense, low-dimensional space that is useful for building machine learning models.

Similar to Word2Vec, DeepWalk predicts vertices based on their context. DeepWalk constructs this context based on the other vertices which appear in a random walk. A random walk consists of a ‘walker’ randomly choosing an edge to travel at each time step. An example of a random walk could be v1 to v3 to v5 to v2 to v4, and then a context window of size 1 for v5 would be (v3, v5) and (v2, v5). Thus, a random walk on a graph is analogous to a sentence in a document.

The image above shows an example of how DeepWalk encodes vertices based on connectivity. On the left is a graph frequently used in social network modeling, the Karate network. On the right is this graph embedded into two-dimensional space via DeepWalk. The idea is that the clusters in Euclidean space will preserve information about shortest path distance and connectivity contained in the graph plot on the left. The authors of DeepWalk refer to these constructed representations as ‘social dimensions’.

Using the newly formed social dimensions, we can build machine learning models that predict characteristics such as community membership, (denoted in purple, red, green, and blue above).

The authors test the DeepWalk representation on three datasets BlogCatalog, Flickr, and YouTube. BlogCatalog is described a sa network of relationships between bloggers with the labels denoting the topic they are writing about, Flickr is a network between users in a photo sharing website with the labels denoting their interests as well, and finally, YouTube is a network between video viewers and the labels denote the videos they are interested in viewing. The following table provides more specific details about the network representation of these datasets:

Concluding thoughts from Henry AI Labs

At Henry AI Labs, we are interested in the DeepWalk paper to expand our understanding of what kinds of problems Deep Learning can be used to solve. It is very interesting to see the similarity between language modeling and connection modeling in graphs. Algorithms that can identify communities and predict attributes of vertices from a graph are highly applicable with the advancement of social media sites such as Facebook, Twitter, YouTube, Medium, and many more. DeepWalk graph embeddings provide an interface between these social networks and our machine learning models. It is interesting to see the generalization of the Word2Vec concept from language processing to graphical modeling of relations. This leads researchers to question if this kind of model could be used to predict context within images or to model patches of images according to some statistics about their pixel values and represent them as relational graphs rather than image matrices.

Related Articles

Simulated Ad Box