Introduction to Graph Neural Networks and What We Can Implement in the Wolfram Language

I'm Mike Yeh, I'm from Warframe Research Technology Group. And yeah, so today I want to talk about introduction to Graph Neural Network and what we can do in Wolfram research. I mean Wolfram language. So yeah, this is my personal interest. So I try to explore it. I mean in this month but unfortunately I don't have enough time. Yeah but let's go out and see what can we do. And yeah, first let me give the overview of introduction. Can you hear me? So introduction to graphene unit. That's the presentation mode. And yes. So as we know in this year so there's a popular application I mean exploring in Graph Neural Net. And it will be okay depends on the test. So you will predict the node, the node will be related the span detection and fake news and some physical. Physical simulation also for age. So predict the relationships between the nodes or the target you're interested in. So it will be recommended system and traffic detection and also other applications within the graph itself. And yeah, so let's keep going. So the. Let me give a quick overview of graph data. So graph as we know it composed by the node and edges age define the relationship between the nodes. And as you can see so the graph looks like here and usually you each node maybe have some attributes also sometimes ag maybe have weight or some additional labels. And for some purpose there's also the global attribute for the whole net. So here's different conditions. So yeah, in graph Neural Net. So this attribute will be helpful for us initial input and will help GraphNet to learn the appropriate embedding in the end. So we start from attribute of a node and then app graphnel net we want to generate appropriate embedding to represent the property of each node. And here's another example of graph data. So image as we know images really image investigation in deep learning is quite exploring. Well so but actually the imagery can be considered a graph can be decomposed and graphed structure. So if you think of the grid structure of image and the channel intensities then the first part the structure can be considered graph itself. And the second part can be considered as the attributes of the nodes. And similarly like in transformer so they try to use the order consider order or position embedding to mark the position of each word. Of course each word has its own vocabulary embedding. So yeah, I just want to show okay, the everything can be decomposed into the graph structure and the attributes and here the sentences similarly. So let's go next. Okay, so let me introduce the simplest representation of graph. So as we know the graph has different types. So the depth part is the direction graph and right part is on direction graph. So the easy way to represent this is to use the adjacency matrix. So like for example there are four nodes and we can use each node as row and color matrix. And if the 1 and 4, if what the nodes are connect, they will be number one here. And because it's on direction, so this symmetric adjacent symmetrics and you can export it. And also the the matrix on the link between all the edge can be weighted. So the adjacency matrix will not only limit to 0 and 1 and so if there's other for the big data set you need some spot representation. So yeah, So in graph neural network so we first we need adjacency matrix. So usually we represent by n by n matrix like this. And also for the attributes or the features of the nodes, we assume the dimension will be, the feature space will be F and the total features of nodes will be dimension N times F. So we can do some operation with input X and based on the graph adjacent symmetrics here. Okay, so yeah, before go on the graph neural net, so let me just remind you some principle notation or ideas for graph. So as we know we have adjacent symmetrics n by n and first thing we have degree matrix. So just sum of a row or columns. And once we have degree matrix we can define the graph lap partial and the graph lap partial will define the property of the graph. Like if you check eigenvalue you can, you can check the zeros algorithm, determine the connectivities and yeah, let me skip this. And also so in graph neural net we need additional normalized lap partition which will deal with the gradients problems in the neural net. It's similar to idea to the the convolution in images. So yeah, we want to normalize so so such that the information can probably get longer. So just remember we defined the normalized lapacious like this and also we have another normalized lap partial. So so you can consider the adjacent adjacency matrix add by self loop. So originally so then the graph don't have cell loop. But for operational convenience we add cell loop and also we normalize it. Any question? Okay, let's keep going. And here is the best operation for graph neural net. So suppose we have graph input. So we will separate the graph structure. We call lapacian or adjacency matrix. Found the attribute. So yeah, and we go through the genetic box and we update the attribute or we Generated the embedding. We learn the embedding for each node or for each age, even for the global representation of the graph. And eventually we do classification. And so you can see okay, there are three types of the text. So yeah, the first one is classification of nodes and the second and third is the classification of whole graph and edges. For the graph classification we can say is image classification. So we need to supervise it. So it's inductive for the node classification dark image segmentation and is semi supervised. So we focus on the same next structure and some nodes as training point and other part as the test point. So we want to predict the rest of a point upper net. So if you have different net, you have to train again, train it again from the beginning and also the edge levels then kind of relationship prediction. So yeah, in this lecture I tried to construct the node classification in Wolfram language because I don't have much time if I maybe next time we'll try to explore the graph classification. But now I will focus on the node classification. Let's keep going. So yeah, first thing is okay, for the graph convolution, I mean for the graph neural net, first thing we'll think about how to apply the convolution to the graph. So think about this. So for the image when we do convolution we try to update the pixel we want based on the neighborhoods. So similar ideas we want to use based on given graph structure. We update the nodes now based on its neighborhood. So then we need some need adjacency matrix. So you can expect during the graph neural net training the graph structure is fixed but attribute will be changed based on the structure of graph and also the trainable parameters. So you can, you can think of okay, the first the previous day will be before the update and update is on the second the next layers and so on, so forth. Okay, so far so good. Yes, so that's why we need adjacency metrics. So let me, I will show you example later. So just. Yeah, it's based on the public view of adjusting matrix or Lapacian. So and yeah, so because time is limit. Let's keep going. And so the key point here is. Okay, so yeah, so as you know, for the image convolution we use because the filter convolution will preserve the translation symmetry and the graph there is no orientation, no specific orientation. So we need to do some operation in which you can preserve the permutation symmetry of neighborhood. Yeah, so just remind you. And so that's why they, they they they suggest the message passing like the idea here. So you do some operation associated matrix operation and pass to the information to the the next neighbor. So we call it one hoping and yes, so just I mentioned before. So after there we update the embedding space by one hoping or by one layer operation. And eventually the goals is to learn appropriate embedding of each attribute like for vertex or edge or global and sometimes for as I know so the global because yeah, it's similar to images. So if you do more layers, your perception field will be larger larger so you can catch some global effect. So but for nets for the network is graph also have similar issues. So get the net too big so that you cannot explore whole net at once. So the topology would be different. Yeah, so then the global embedding will be helpful. I mean to help the node to touch each other faster so they get better information. But I will not implement this in this talk. But yeah, let's keep going. And yes, so the information or the embedding information can pass not only limited to node to node, you can pass between the from the vertex to H or h to vertex or the globals. Okay, let me go faster and because. Okay, we'll see some results. Yes. So let's go to the topic of the convolution. So the grave convolution the simplest. Okay, simple simplest implement of graph neural net is graph convolution. So this is simplest type you can have. So assume you have just mentioned the normalized lap partial. And because we know the dimension of the attribute and once we tie this this is just equivalently to hopping to the nearest neighbor. So if you know the matrix operation. So yeah, then then the the W here is the the matrix. Try to convert the input into appropriate dimension or embedding. So that's the simplest part of graph unit convolution. Any question on this? So the key points because I'm remind I as we know the dimension of the axis is n times F and this dimension N times n. So you can think of adjacency matrix here and this just do one hoping of attributes. So after one operation your information publicly points to the neighbor and here are some basket metrics we all adjacency matrix we or the partial we will need in the following experiments. So just remind you. So these are normalized and additional normalized one. Yes and yes. So this is about the idea of graph convolution. And in the end we will use the nonlinear like sigmoid or the linear function like relu something like this. Yeah, so yeah, that's the principle ideas. So because we don't have much time so let me skip the code but you can see easily. So here so the Python operate on operation so it's quite easier. So you have. Once you. You have lapwashian and you and your input will times the linear operation W. Here's the W and then do another multiple multiplication and take as output. So let me skip this. Okay, so because this is more complicated but the idea is this is so called the spectrum operation. So it's kind of a global effect. Once you have that partition or adjustment metric you can diagonize it. The diagonal analysis is linear comparison between the nodes. So that's a global effect. So this kind of convolution will be act as the global convolution but in practice it's difficult so that's why we use this expansion and yes, my goal today is try to demonstrate how to implement the graph convolution and disk expansion in Wolfram language. And I just skipped the math details so and let me just go to the notebook. Yes. So basically I follow the steps exchange link here and do some exploration and so first thing I save the data in DAT and explore it in Warframe language. First things okay, we get the data and do some the metrics I just mentioned before. So like so these asymmetric normalized adjacent matrix and we have degree matrix and also we have Lapassian and this is for expansion purpose and yes, so these are rescale Lapacian so so on so forth. And this is the if you cannot remember so many. So we just keep my in this visible graph convolution. Yeah, so we add the adjacent matrix is added by cell group and normalized by the degree matrix and next we construct the net. Wait, let me. I need to run. So okay, let me run the net and show the structure. So yeah, so here we I just use two layers and each layer construct in this way so you. You can see there's a adjacent matrix and the input, the input will be the attribute or the previous embedding layers and we do the linear transformation and multiply the adjustment matrix to one hoping and then we do activation for the next year layers and here we construct a loss function because we do. Yeah, the test now is to node classification so we have to use the sendnet but I use part of the node for training set and part of node testing. So we need a mask to separate the for the nodes and yeah, then here's the next structure. So we have to use the mask to separate each. Okay, so let's go to the end. So I do some evaluation and yeah, so there are different matrices. I mean adjacency matrix. So in general the. Yeah, this one, this one is the graph convolution and this is a symmetry anomaly adjacency matrix. It's provided by a region no stack exchange. So they are really close. And of course I I do another study and like 1k hopping k equal to 1 expansion and k equal to 2 expansions of the, of the, of the spectrum convolution. And you can see the accuracy indeed increase. And let me see. Okay. Yes. Yeah. So the, the highest one I can reach is the accuracy about 0.8. So is so the expansion method get better accuracy than just convolution graph convolution. But I don't have much time to do more details. But hopefully that help to understand. Yes.