DeepWalk Explained

Key Takeaways

hi welcome to Henry Aird labs this video is going to cover deep walk deep walk is a mechanism to encode social networks based on their connectivity and it was published in 2014 the idea behind deep walk is to use some of the advances in language modeling to do graph modeling so the way that this works is in language models you have text tokens which could be represented as these one hot encoded vectors that would have a 0 for every single word in the vocabulary and then a 1 for the word you're trying to represent so in this this diagram shows the cat representation would have many zeros on the left and right at the one so in a sense it's like a really sparse vector and it would be really hard to train a machine learning model in these sparse representations so similar to language vertices in a graph and their edges are encoded in in the same way you'd have one for the other vertex that it's connected to in the graph and then zeros for all the vertices it's not connected to so word Tyvek is this idea that you take these context windows of words such as in the sentence the quick brown fox jumps over the lazy dog you have these context pairs like quick fox brown fox and jumps fox and the it's like when you have enough data it's sort of like it'll become a semantic space because the context actually does give you a lot of information about the text and so somewhere to text you say that a random walk on vertices can construct a similar sequence that is like analogous to a sentence so you have these contexts like v 2 v 5 and V 3 V 5 and you use them to predict each other in the context and thus you construct like a dense continuous vector representation of this sparse data via the context prediction mechanism so this quickly shows like what a random walk is and how this is used to construct these like sentences to embed vertices similar to how language is done so when you are at one vertex you have these probabilities of transitioning to other vertices but in the case of of like a social network graph you wouldn't really wait transition probabilities like PQ and one minus P plus Q you just have like a uniform distribution and you randomly go oh you just randomly sample it to go to the next vertice so this is the formal definition of the walk algorithm on the left it shows you slide the context window what they do is they do something called hierarchical softmax to reduce the computational complexity of it but that's the scope of this video but so what they do is they slide the window and then they use the Skip Gramm model to encode the vertices into a low dimensional space so this plot shows what the point of doing this is the left you have the sparsely connected graph and you can see from this plot how each vertice is only connected you know like the most connected or like the highest degree of any vertices in this graph is maybe like six so to have in those thirty four nodes in the graph so it'd be like twenty eight zeros and six ones and the sparsely encoded vector that shows the connections it has so what they do is they take the graph on the left and they use deep walk and embed it into the plot on the right and the idea is that the plot on the right will preserve the shortest path distance between nodes on the left and then also hopefully it'll preserve the label so a similar to any machine learning model you label the vertices in the graph according to their communities and then you do some clustering in trying to preserve these labels with the embedding so in their study the authors who came up with deep walk they tested it on blog catalog Flickr and YouTube and these are all like social network datasets where users are connected to each other and they are labeled according to their interest like what kind of videos they're watching what kind of photos are sharing and these kinds of things so the idea behind deep walk is that you can take these sparsely encoded graphs and then you can construct a feature space based on their connectivity and this low dimensional space can be used to train machinery models to predict the interests of future users thanks for watching this video I check out the article on deep walk on hungry lives