Embedding Graphs with Deep Learning

Key Takeaways

this is a deep learning video from Henry AI labs this video is on embedding graphs with deep Lerner the motivation in this idea is to embed graphs which are typically represented as sparse adjacency matrices or lists into low dimensional continuous vector representations the picture shows the result of this you start out with this graph and then you embed it into a space such that you can do things like Euclidean distance cluster these low dimensional representations are also also really useful for building supervised learning models that do tasks like link prediction and motor classification so how can we construct low dimensional representations of grass some of the typical methods used are based on matrix decomposition such as a singular value decomposition and multi-dimensional scalar matrix factorization methods they're basically bottlenecked by the time complexity of matrix multiplication because they each require inverting matrices so this runs in order n-cubed and you know more clever implementations like Strassen and coopersmith Winograd can't reduce this running time but still it's problematic because and you have social graphs like Twitter users or Facebook users you have been insanely large n and in addition it doesn't adapt well to adding new edges and new notes in network so you'd have to redo singular value decomposition each time you add new users to the network so deep learning deep learning is well-known for reducing dimensionality of data deep learning is most frequently used in computer vision speech recognition and natural image processing so how can deep learning be extended to graph data so graph data and text are actually represented very similarly and the adjacency list encoding edges and a one hot including of text tokens have very similar structure and very similar sparsity so how the sparsity handled a text it's in text sparsity is handled with the Skip grant model so the high-level idea the skipper model is to slide a context window four sentences and construct these pairs such that you build a deep model that maps from input words to its context the intermediate representation in the scope Graham is used as the embedding of the text tokens so text data is naturally structured via sentences so how can we find a similar structure in graphs if so this is random walks so we can take random walks on ungraspable host and vertex neighbourhoods are used in the same way that sentences are used in the Skip grandma so deep walk it uses a skip Graham style vertex encoding this is done by treating vertex neighborhoods and sentences and deriving vertex neighbourhoods from random walks and then the representations of these vertices are used for downstream tasks like link prediction or classification so another interesting thing is that graph and text data both follow this power law distribution of frequency and degree so like in text words like the as in the appear really frequently and in social networks some users have much more connections than others so some of the important ideas in super M are hierarchical softmax and negative sampling hierarchical softmax is a really clever way of reducing the number of hidden units you need in your softmax output layer so if you imagine you're using a Facebook Network and you're trying to predict the contexts vertices which could contain millions of vertices you can divide this space by log 2 vertices by constructing it in a binary search tree so this example shows how eight nodes can be represented with three predictions of the binary search tree negative sampling is another one of the key idea isn't worked avec what this says instead of directly predicting the context words you just predict a binary label of whether this word appears in the context or not so in the sentence I am learning about using deep learning to represent graph data around deep learning and using both be a correct label and coffee and gorilla would be negative labels because they don't appear in the context so going further should we sample uniformly in deep walk we treat a B D and C all with the same probability of going to the next note but a note avec we're gonna parameterize how we traverse the read and walk so the final paper is that if you traverse the notes in a breadth-first way you'll capture the sense of home field which means that nodes which are near by to each other and the shortest path distances should be embedded in you know how below Euclidean distance me a better but if you do a depth first search traversal then the nodes will have a structural equivalence in their abetik so in the nodes in the graph above you and s6 don't share your neighbors but they both play a similar role their communities so embeddings that represent shortest path distance or home ability is shown here you can see that you know that it preserves this notion of how far away are its neighbors so in conclusion we've seen how deep walk and note two that are used to convert adjacency matrices into low dimensional representations this is done using random walks and the skip very model thanks for watching