Graph Neural Networks Explained: From Graphs to GNNs

[00:00:01]What if someone told you that a machine has discovered an antibiotic that can treat previously untreatable strains of bacteria?

[00:00:09]Yes, you heard that right!

[00:00:12]The antibiotic is a chemical named Halicin, and it was discovered by a pioneering machine-learning approach  called Graph Neural Networks.

[00:00:22]The fairly straightforward approach can also be used to find new drugs for other diseases like cancer, improve transportation, solve problems related to social networks, and many others.

[00:00:34]But what is a Graph Neural Network, and how is it different from the neural networks that have been around for more than 5 years?

[00:00:41]Let's find out!

[00:00:54]Imagine that you're Cupid, and... Oh! Hi Andy!

[00:00:58]Ok, so you've been tasked to find a suitable match for Andy to fall in love with.

[00:01:04]How would you approach this?

[00:01:08]First, we know Andy's age, gender, occupation, that he reads fiction, loves cycling, and he can't dance.. Well that's a bit harsh, how about 'learning to dance'.

[00:01:21]Lets place all these features about Andy into a list as such.

[00:01:26]Next, lets gather information about his social interactions - who does he hang out with most often and who are some friends of those friends.

[00:01:36]Alright, we can now begin to analyze this web of information to find Andy a suitable match.

[00:01:43]This web of data can actually be viewed as what we call a Graph in computer science.

[00:01:48]But what is a Graph, exactly?

[00:01:51]A graph is a structured way to represent data.

[00:01:54]It consists of nodes to represent entities like people, and edges to represent the relationships between these entities.

[00:02:07]Like in Andy’s network, each node might also have a set of features which describe it.

[00:02:13]For edges, they could either be undirected - meaning two way, or directed - one way Extending from undirected to directed graphs is not difficult once we get the basic mechanisms.

[00:02:30]So lets stick with undirected edges for now.

[00:02:34]But, why Graph Neural Networks?

[00:02:38]If you’re watching this, I’m sure you’ve heard of the expansive success that Neural Networks has had on many problems They are able to learn a variety of desired outputs from several types of inputs such as numbers like stock prices, words that we use everyday or even images like this low resolution '4' over here.

[00:02:58]So, why don’t we just feed Andy’s network through the all-powerful neural network and let it tell us his best match?

[00:03:08]Well… It turns out that neural networks have mostly been successful on more structured data types.

[00:03:15]For example, numbers belong in a series, words that we use everyday are found in sentences, and images?

[00:03:25]Well they actually come as a grid of pixels.

[00:03:30]But neural networks still struggled with more complex data such as graphs, which do not have any fixed structure or ordering.

[00:03:44]So, in order to reasons with graphs, researchers went back to the drawing board to study what made neural networks so successful.

[00:03:52]The first layer in a common Convolutional Neural Network takes each pixel and extracts information about  its region by aggregating the pixel within the context of its neighborhood.

[00:04:13]The next layer then extracts information about that region within the context  of its neighboring regions.

[00:04:19]Doing this over enough layers, the network will be able to reason over different parts of the whole image.

[00:04:26]And then with some linear computations, it can finally identify the relevant object.

[00:04:33]Take a second to think how might you apply this mechanism to graphs?

[00:04:37]If we look closer at an image, we can actually view it as a special type of graph - a grid graph that is  structured, and every node is a pixel that is connected  to its 8 neighboring pixels.

[00:04:50]Seeing it like this, you might think to yourself - why don’t we just use the same aggregation mechanism  that we have seen before?

[00:04:58]And you're right!

[00:04:59]We can actually use that same intuition on graphs!

[00:05:03]Relaxing the properties of fixed structure and ordering, we can similarly gain a better understanding of each node by aggregating the messages received from all neighboring nodes.

[00:05:16]Now, hold on to your new message, Andy, as your friends complete their first round of message passing.

[00:05:25]Observe how the color of each message changes to represent the newly aggregated message.

[00:05:33]And, with each new round of message passing, more and more information gets passed around in the graph.

[00:05:40]Over sufficient rounds of message passing, we will eventually obtain a final representation of each node in the graph that well describe it given the larger context.

[00:05:52]We can also view the rounds of message passing as a series of layers just like in our convolutional neural network.

[00:06:01]Here we go from the input, to round one of message passing, and then round two of message passing.

[00:06:09]And this produces our final understanding of nodes.

[00:06:17]So… We now know how to understand each node better, but how does this allow us to help Andy again?

[00:06:24]Well, as humans, we might take a look at Andy's graph, and mentally or visually, we will process all the information  such that people who are more compatible with Andy will have a stronger association with him.

[00:06:38]In other words, in our mind, maybe people who have similar characteristics to Andy will be placed closer to him - and they are therefore stronger candidates.

[00:06:52]Similarly, in the process of reasoning over a graph, the graph neural network seeks to summarize all that information of each node into a numerical representation, where nodes which are more ‘similar’  will be closer to each other.

[00:07:09]We call this representation  of nodes - node embeddings, and we call the space of all possible representations - you guessed  it - the embedding space.

[00:07:20]But how does the network know how to come up with these embeddings, and where to place them in the embedding space?

[00:07:28]Neural networks need an appropriate measurable objective to guide the network into learning something useful for our task.

[00:07:36]In Andy's case, one way is to tell the network that embeddings of people who Andy spends a lot of time with, should be closer to him Rearranging the expressions, we can quantify our objective into a loss function to tell the network how well is it doing.

[00:07:55]Adding in all the other objectives from other nodes and taking the average, we now have a working loss function.

[00:08:04]We are finally ready to see how all these come together to find Andy's match!

[00:08:10]Firstly, from the input, we forward propagate through the message passing layers to get a final representation of each node.

[00:08:20]We then tabulate the loss, and backpropagate it through the  network to tell it where it went wrong.

[00:08:28]The network changes its computations, and tries again, this time hopefully with a better performance.

[00:08:40]We can do this as many times as we want, and, after the network has learned embeddings of Andy's graph that are good enough to meet our objective, we could simply shortlist a bunch of people who are in a certain radius from him, maybe filter out some Andy deal breakers, and rank them as potential matches according to numerical distance.

[00:09:04]And, we are done!

[00:09:08]Our hopefully successful matchmaking task is actually a form of link prediction, where we task the network to recommend new potential edges between nodes.

[00:09:19]Another popular task Node classification - where we use the representation of each node to predict a certain class.

[00:09:28]We also have Clustering - where we break up the embedding space into different groups.

[00:09:36]And finally, we have Graph classification - where we do some form of aggregation over all node representations of a graph, and compare it with other graphs.

[00:09:46]This last task was used to discover Halicin!

[00:09:49]You might notice that the key component of these strategies involves the need to learn good node embeddings.

[00:09:56]Going back, hopefully you can see that this actually hinges a lot on how we perform message passing between the nodes.

[00:10:04]So, lets dive in to take a closer look at each round of message passing.

[00:10:09]Message passing is actually a mathematical function, which we call 'f', to update the receiver node using the  messages from each neighboring sender node.

[00:10:19]In this case, the receiver node is Andy.

[00:10:22]Note that the aggregation includes the receiver node itself.

[00:10:27]In most cases we would want to give different importance values to each neighbor.

[00:10:32]For Andy’s case, this could be based on the number of connections that each node has We express these as constants, since they are fixed by the graph's structure.

[00:10:43]Similarly, depending on the final task, we might want to weigh each feature  of the nodes differently.

[00:10:50]For Andy’s match-finding example, maybe a combination of age and education is more important.

[00:10:57]Instead of hand-picking which features are more important, we can leverage on the power of neural networks and learn them through backpropagation as represented by weights 'W'.

[00:11:07]In order to learn more complex patterns, we would also want to add some non-linearity to the function output.

[00:11:15]Going one step further, must we only use the sum operation to aggregate the messages?

[00:11:21]Well, since changing the permutation of the nodes don't change the node’s neighbors, what we really want is a permutation-invariant function which consistently aggregates information from a node’s neighborhood regardless of ordering.

[00:11:38]Lets now express this slightly differently, to generalize it to any other  node and not just Andy's.

[00:11:45]Firstly, all the neighbors can be denoted as j, and so we can group all these terms and denote the weights as a function.

[00:11:54]Since we are updating the receiver node, we might want to treat its node's features  differently from the rest.

[00:12:01]We can also denote the outermost non-linear function as a general learnable function.

[00:12:10]And here, we arrive at one of the three general “flavors” of graph neural network layers - Convolutional - where the weights of neighbors are fixed based on the structure of the graph Previously, we discussed that the weights for each feature can be learned.

[00:12:28]So, could we also learn the weight given to each neighbor according to their features?

[00:12:33]Turns out we can, bringing us to our second flavor - Attentional - where the weights of neighbors are learned based on the interactions of the features between the nodes.

[00:12:44]Finally, so far, we have been aggregating a weighted combination of neighbors, but the most general form of message passing would be that each pair of nodes collaborate to produce a specific message between them.

[00:12:57]One final note - recall this form of convolutional message passing?

[00:13:02]Computing the updates for each node sequentially like this sounds slow, doesn't it?

[00:13:07]In practice we actually leverage on linear algebra!

[00:13:12]A graph's edges can actually we summarized using a table which we call an adjacency matrix.

[00:13:18]Note that for our case, we would need the nodes to connect to themselves.

[00:13:23]We can also stack all node features of a graph in a matrix like this.

[00:13:29]And we now have our three main elements, including the learnable weights, 'W', with all these dimensions.

[00:13:38]But wait, do you notice something missing?

[00:13:41]You got it, the importance weights for each neighbor is actually computed by changing the adjacency matrix accordingly.

[00:13:49]And now, hopefully you can see how these functions are exactly the same!

[00:13:54]With this, we can use some highly optimized matrix multiplication library, to perform message passing for all the nodes at once.

[00:14:03]Isn't that amazing?!

[00:14:05]With that, we have come to the end of our introductory graph neural network video!

[00:14:10]I really hope that it was helpful to you in some ways, and if it was, do give a like or subscribe, so that youtube's neural network can matchmake this video to people similar to you.

[00:14:22]Alright, till next time, bye!