Hyperbolic Graph Convolutional Networks | Geometric ML Paper Explained
❤️ Become The AI Epiphany Patreon ❤️
https://www.patreon.com/theaiepiphany

👨‍👩‍👧‍👦 Join our Discord community 👨‍👩‍👧‍👦
https://discord.gg/peBrCpheKE

In this video we dig deep into the hyperbolic graph convolutional networks paper introducing a class of GCNs operating in the hyperbolic space. 

Hyperbolic GCNs give exceptional results for the class of scale-free/hierarchical/tree-like graphs. I dive deep into differential geometry theory and explain how the method works.

▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬ 
✅ Paper: https://arxiv.org/abs/1910.12933
▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬ 

⌚️ Timetable: 
00:00 Intro - why the hyperbolic space?
04:00 Graph Convolutional Networks recap
08:50 Hyperbolic space and curvature theory
15:25 Geodesics, exp, and log maps
23:00 Mapping from Euclidean to hyperbolic space
26:35 Feature transform in hyperbolic space
32:47 Aggregregation on the hyperboloid manifold
35:25 Non-linear activation with different curvatures
36:30 Holistic overview of the method
38:20 Results, Ablations, and curvature analysis
41:00 Why does curvature help?
42:05 Outro

▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬ 
💰 BECOME A PATREON OF THE AI EPIPHANY ❤️ 

If these videos, GitHub projects, and blogs help you,
consider helping me out by supporting me on Patreon! 

The AI Epiphany - https://www.patreon.com/theaiepiphany
One-time donation - https://www.paypal.com/paypalme/theaiepiphany 

Huge thank you to these AI Epiphany patreons:
Eli Mahler
Kevin Stone
Petar Veličković

▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬ 

💼 LinkedIn - https://www.linkedin.com/in/aleksagordic/ 
🐦 Twitter - https://twitter.com/gordic_aleksa 
👨‍👩‍👧‍👦 Discord - https://discord.gg/peBrCpheKE

📺 YouTube - https://www.youtube.com/c/TheAIEpiphany/
📚 Medium - https://gordicaleksa.medium.com/ 
💻 GitHub - https://github.com/gordicaleksa 
📢 AI Newsletter - https://aiepiphany.substack.com/

▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬

#graphs #graphconvolutionalnetwork #hyperbolicspace
 What's cracking guys? In this video I'll be covering hyperbolic graph convolutional neural networks by the authors from the Yura Leskovitz group at Stanford and we're going to see that hyperbolic keyword here in the title is what makes this paper particularly scary and math heavy and I'm gonna also argue that it's not just mathematics for the sake of mathematics. I'm gonna show you why they have chosen to use this exotic geometric space and use it to learn like useful embeddings later on for node classification and link prediction tasks. So let me start with abstract here and then I'm gonna show you a nice visualization that's gonna give you like a gut feeling for why we are using hyperbolic spaces in the first place and I'm gonna also get into the mathematical formulas and so if you're not familiar with what like curvature of spaces, what hyperbolic space is, don't worry. So we'll get there. Okay, so let's start here. Graph convolutional neural networks or GCNs for short embed nodes in a graph into Euclidean space which has been shown to incur a large distortion when embedding real-world graphs with scale-free or hierarchical structure, okay? And then they say we derive GCNs operations in the hyperboloid model of hyperbolic space and map Euclidean input features to embeddings in hyperbolic spaces with different trainable curvature at each layer. So my whole goal of this video will be to decode what like the thing they just said in this in this particular sentence here. Okay, so let me just read this one and then I'm gonna tell you what this scale-free graph is. So in particular scale-free graphs have tree-like structure and in such graphs the graph volume defined as the number of nodes with some radius to a center node grows exponentially as a function of radius. So basically scale-free networks are just a particular type of networks that have this this power law behavior where nodes that have a lot of connections become less and less frequent. As you can see here asymptotically we have K which is the number of nodes. We have that the probability of a node having K connections as K grows you can see that like basically that probability drops according to this power law here. So yeah, basically the main idea actually is that this exponential keyword and if we have like graphs that are crowded because of this exponential growth of neighbors that's when we want to use the hyperbolic space. So now let me give you like a visual intuition for why that may be. Okay, let's get to this chart here. Okay, so let's imagine we have our nodes and we have the associated node features and we can always basically visualize node features as points in like Euclidean space. So let's now imagine our Euclidean space is this plane here. We have the points here and you can imagine that if we have like exponentially more neighbors here if it's kind of crowded then mapping to this like geometric space which we call hyperbolic space is going to make them more spread out and like that's the basic intuition. Basically by spreading the points which are densely clustered together in the Euclidean space so by spreading them out in the hyperbolic space you make it easier to discern to discriminate between different node features and thus do better job at classification etc. So that's the main mental model I want you to have throughout this video. And having said that now let me dig into like mathematical formalisms and let me try and explain what the hyperbolic GCNs basically are. Okay, I'm gonna start with some basic notation and explanation of what GCNs are. If you've never watched graph ML videos so far go ahead and check out my playlist on graph ML. Like in particular go and watch the GCNs, so graph convolutional network paper as well as maybe graph attention and network paper, so GATT paper. So that's gonna get you up to speed. But here I'm just gonna briefly recap what we've seen in those videos. So first of all the whole point of graph like representation learning is to learn these useful representations of nodes and sometimes edges which we can then use to do classification tasks on nodes on graphs on edges etc. So let me just show you the formalism here. So graph representation learning is this mapping F. So from this set V of nodes, set E of edges and then we have associated node features. Sometimes we also have edge features but here I'm just gonna they just ignored the edge features. So you can see the notation is the following. So X of I which means node I. So these are the features at the raw features because basically zero means zero layer before we even started applying the graph neural network. So and also we have this symbol E which means these are Euclidean raw features of this particular node I. So that's how you treat this symbol here. Okay and the goal is to find like a mapping to this basically a representation Z which is of dimension the number of nodes times D prime which is the dimensionality of your output node features. Okay so the whole point is to find like a basically good features so that we can discriminate between different classes or do whatever arbitrary task. Okay so that's the graph representation learning. Now quickly on to how graph convolutional neural networks work. Let me just maybe draw a simple example graph here. So we have a node I here. We have a couple of neighbors. So we have some neighbors here. They are connected to node I. Of course these neighbors could have their own neighbors etc etc. But let's focus on this particular node I here and let's see how do we learn the representation of that particular node. Okay so what they first do is they create this intermediate representation H. So I can see here from layer L minus 1 which is the previous layer. We do the mapping using the weight matrix and then we add the bias. So we'll have like a separate set of these W's and B's in every single layer of the graph neural network of the GCN in this particular example. So once we form these intermediate representations what we do in order to update the feature vector of this node I is we simply sum. So we sum the this intermediate representation of node I with like a sum over neighbors of weighted intermediate representations. So let me just kind of break it down quickly. Basically what I've said there is the following. So let's imagine we have so these are the neighbors. We have three neighbors in this particular example. We have certain basically feature vectors associated with the neighbors. So something like that and let's imagine these are the H's. So these are the the representations that we have after we do this particular mapping here. So we just do weighted average of those of those particular feature vectors. We sum them up and then apply the nonlinear activation function in order to get basically novel so layer L representation of node I. So we're gonna finally end up having like H, I for layer L and these are just Euclidean features now. Okay now these W IJs depending on the architecture these could be learnable but that's now getting into the attention spectrum. What the original GCN did here is basically so this this W IJ was simply 1 over square root DI times DJ where D is just a degree of a node. So that means you basically normalize this particular presentation depending on the degree of this node and degree of your target node J. So let's say this is node J in this particular example. Okay so that's how they've done it in the original paper and that's the GCN formalism. Now for the more important part let me introduce you to that formalism of hyperbolic spaces and let's see what it's all about. Okay so hyperbolic spaces have different models the most famous ones is this so-called Lorentz model also known as the hyperboloid model as you can see here and there is also this Poincaré ball model of hyperbolic space. So here they are gonna work with the hyperboloid model because they showed it's more stable and so they basically stuck with it. So we are going to be working with the hyperboloid model of hyperbolic space. So they introduced this like inner product called Minkowski inner product. So it's a simple mapping of you map two topple of these D plus one dimensional points into the real basically into a real number and this is how Minkowski product is defined. Basically it's similar to your dot product to which you're used to and the only difference is basically this addition of a minus sign for the first coordinate of the points in this space. Okay next up they denote by this HDK they denote the hyperboloid manifold in D dimensions with constant negative curvature minus 1 over K where K is always bigger than 0. So briefly just what a curvature of space is that may seem like very scary but it's not. Basically you're usually used to working in the Euclidean space so let's imagine we have like a example of a Euclidean space a 2d space like a plane here. If we shoot parallel geodesics where geodesic is just a generalization of like a straight line to arbitrary spaces. So if we were to shoot them in the Euclidean space here in the plane you can see that the distance between these two lines is always going to be constant and these two lines will never intersect nor diverge. They'll always stay at the same distance from each other. That's not the case in every single space and that's why we have the notion of curvature. In the case of a sphere if you shoot two parallel geodesics you can see they are going to intersect at the North Pole in this particular example which means when the parallel geodesics intersect we call that space positively curved and on the other hand if the parallel geodesics diverge then we call that space negatively curved and you can see here an example of a hyperbolic space here. So you can imagine if I were to extrapolate these points here they are going to diverge each in its own direction here across this hyperbolic space. So that's the idea with curvature. It's not that fancy just once you have this visual mental picture then everything becomes much easier. Okay so next up they have this tangent space at point X of the manifold HDK and let me just now show you how they define those two formally. So again this hyperboloid model is defined as a set of D plus one dimensional points such that the Minkowski inner product between a point with itself is basically always going to be constant and equals to minus K and additionally the first coordinate of these points needs to be positive. So that's how we define the hyperboloid model. Following up we have this tangent space which is just like a set of perpendicular vectors. So a set of orthogonal vectors to your vector X. So again basically it's a set of vectors V, D plus one dimensional vectors V such that the inner product again Minkowski inner product equals zero. So tangent space is a concept you're familiar with like even though this is just like a let me give you a like an analogous case in the case of like a sphere. Let's imagine we have a sphere here. So we have a sphere here and basically this is like maybe North Pole, this is like South Pole. Tangent space to the North Pole would be just like a simple plane. It's a plane such that it touches the North Pole. It basically touches a sphere only at a single point and that's at the North Pole. And you can see here that all of the vectors in this particular plane, so let me draw a couple of vectors here, all of these vectors are going to be perpendicular. So if I take the center of the sphere as the origin and if I were to draw, so this is the point X in this formalism, so this is point X and so basically you can see that this vector here, so all of these vectors in the plane are perpendicular, are orthogonal to this particular vector X. So this is basically a nice way to form you to algebraically describe this notion of a tangent space. We'll soon see why it's convenient to instead of working on the manifold to be working on on a particular tangent space of that manifold. We'll see why that is convenient. Okay, let me continue here and let me introduce a couple more details. So I'm gonna quickly skim over over these formalisms because they're not as vital for this paper, but let me just introduce you to the mathematics. It may be interesting. So now for V and W which lie in the tangent space of the hyperboloid model at point X, we define this G of X which is basically something called a Riemannian metric tensor or it's a simple it's basically defined as a Minkowski inner product and it's gonna later on allow us to define distances in the tangent space. That's why it's an important contract and we call this tuple of the hyperboloid model and this Riemannian metric tensor, we call this a Riemannian manifold with negative curvature minus 1 over K. Okay, so not as important just like introducing you to some notation. So finally the tangent space is useful to perform Euclidean operations undefined in hyperbolic space and we denote by the norm of we basically induce the norm of a vector in tangent space by doing a square root of the inner product where inner product is Minkowski inner product and that's how we define the norm of vectors and by doing that we basically have a nice way to define a distance in tangent space of this particular hyperboloid manifold. Okay, so all of that formalism was basically so that we can understand what exponential and logarithmic maps are. So this is going to be the main construct we need to understand in order to understand how hyperbolic GCNs work. Before I get there I need to briefly introduce geodesics which are basically just and they say here which are generalizations of shortest paths in graphs or straight lines in Euclidean geometry. So that's just a generalization a notion of like a shortest path between two points in arbitrary spaces. So let me show you how they define it. Let X be a point on the hyperboloid manifold. Let U be like a basically a point in a vector in the tangent space of that point X. We call that U the unit speed and because they're going to basically make sure that the inner product here or the norm of that particular vector is going to be equal to 1. And then they say the unique unit speed geodesic denoted like this such that basically that geodesic at a point 0 equals to this point X on the manifold. Next up we have gamma dot which just basically means a velocity vector at point evaluated at 0 is going to be equal exactly to that U unit speed. Okay so let me give you like a mental model I have when I think about these geodesics. So imagine we have a curved space such as this one. So something like this and that's just like a basically imagine we had some type of like a sheet of paper or something and I'm looking at that sheet from this side and that's where we get something like this. So now now imagine we have point X which is the point we've been using in this formalism of the geodesics here and let's imagine we have like a unit vector unit speed vector U and now what geodesic is is and and that this U lies in the tangential plane of this point X. So imagine we have like a tangential plane here and U just lies in that plane. And so what the geodesic is is imagine we start from this point and we have this velocity vector and for some amount of time you basically shoot like a point from you shoot a point from X using this velocity vector V and you just trace out where that point will go on this on this curved space. So basically imagine if we were to travel for one second maybe we'd end up somewhere here. And we'll see why that is useful because that basically allows us to map vectors from tangent space as you can see here. So we basically just map this vector here we mapped it onto a particular point on the on the manifold here. And that's how I like to think about geodesics and exponential and logarithmic maps which I'm going to introduce in a second. So and now we have for this particular hyperboloid model we can see how the geodesic is defined here basically some complex equation using hyperbolic cosine and the hyperbolic sine and it's not even important you can treat this as a black box. So what is important for you to understand is that as we are as we are basically changing this parameter T we're going to be tracing a path along the manifold. So we're going to be tracing a point that's always going to belong to manifold and not to the tangent space. And here they show how you can calculate the distance between two points on this hyperboloid manifold. Again some complicated equation we have Minkowski inner product we have arc cosine hyperbolic so not that important you can treat it as a black box. So what is important is that we have like geodesic and we have a distance. Okay so now to the more important part and that's the exponential and logarithmic maps. Let's see how these are defined. So given a point on the manifold X and a tangent vector V that belongs to the tangent space as defined by point X. So the exponential map maps from the tangent space of X on to the manifold on to the hyperboloid manifold. And you can see how it assigns the point it's basically evaluated as as geodesic at when you set t equals to 1. And that's precisely what I just explained here. So you have basically let me just map this directly here. So here in this notation we have X and V which means this thing here we now call it so instead of U we call it V. So this is V this is X and we basically what we do is we trace out this geodesic. So gamma is a unique geodesic satisfying that at t equals 0 it equals X and the velocity is described by vector V. Which means as I said so we have a point here at X with the velocity V and we just trace out its path along the manifold and that's how we map vector V to a novel point on the manifold. So that's your exponential basically exponential map. Vice versa we can define a logarithmic map which has this property that if you then apply after applying exponential if you apply a log then you'll end up with the initial vector V. And then they say here in general Romanian manifolds these operations are only defined locally but in the hyperbolic space they form a bijection between the hyperbolic space and the tangent space at a point. Now this might not be apparent why this is relevant but like it is. I'm gonna briefly tell you what this means and that's the following. So for this particular hyperbolic model you can see it here this tangent space even if it was infinite we'd have a unique point so for every single point on this plane so we basically have a situation where we can map any arbitrary point here to some point unique point on this particular hyperbolic manifold. And that would not be the case for arbitrary general Romanian manifold. So let me for example show you a contra example. So let's imagine we have a sphere. So let's imagine we have a sphere here and let's imagine that at the North Pole we have like a tangent space and let's imagine it's just an infinite tangent space. And so you can imagine that if we had a vector such as this one okay so this vector would maybe if we were to trace out the geodesic here by doing exponential by applying the exponential map we'd end up maybe mapping this vector to this point here. Okay but now the thing is because of how this manifold looks like it's a sphere if we had like maybe like 3x the size of this vector we'd end up doing like doing a full circle and then one more half and we'd end up at the same point here which means we've basically mapped we don't have a projection anymore we map these two vectors from the plane on to the same point. So both of these map to the same point and we don't have a projection and that's a problematic property if you want to learn embeddings. Okay so that's everything you need to understand. Now they just show how these exponential and logarithmic maps look like for this particular example of using a hyperboloid manifold. You can just see they're using cosine hyperboloid cosines etc etc but the main idea is the thing I just explained to you. Okay now that we have this differential geometry under our belt let's now dig into the actual model and understand how it works. Okay so this should now be fairly straightforward. The first step we need to do is given our node feature vectors which are in the Euclidean space initially we first want to map them into hyperbolic space. Okay so how we do that is the following. So they define something called North Pole of this hyperboloid model and they define it like this. You can see this like bold O the first coordinate is a square root of K everything else is zero and this is the North Pole of the of the hyperboloid. And so why that is important is because if we were to construct a point if we were to augment our Euclidean feature vector here by just prepending zero as the zeroth dimension we can see that if we were to do inner product between this augmented Euclidean point with the origin we'd get a zero because basically we have zero here which means zero times zero is gonna be zero and because here we have all zeros no matter what we have in X we're gonna end up with zeros once you sum that up a bunch of zeros yields a zero and so that's why we have this fact here. Interesting property if you understand what this what's the semantics behind this expression that's that we we now know that this is a lot that this augmented point lies in the tangent space of this of this particular North Pole of the hyperboloid. Okay so that's what we have when we have zero that means we have orthogonal like vectors and they say therefore we interpret this point here as a point in the tangent space of the North Pole and basically then they show how how you can map from from the from that augmented point in the tangent space by just applying exponential map at North Pole to get the finally to get the hyperboloid embeddings. Okay let me quickly show you how you should think about this as it's fairly easy given the diagram up here so this is a tangent space of the North Pole imagine that this red dot here is the North Pole so this is the tangent space of the North Pole of this hyperboloid model here. Okay so now we want to map an arbitrary point from the tangent space on to the hyperboloid space. So what we are going to do is the following so imagine this is the point we're trying to to map so this is the one we're trying to find like a corresponding point on the manifold for this particular point here in the Euclidean space. So what we do is you can see we have this vector here and imagine this this plane is now touching this hyperboloid model at a single point so it's a tangent space as I said and then we just do the exponential map which is we shoot a point we start here from the North Pole and we just shoot a point in that direction with that velocity vector and then it's going to trace out this particular geodesic and we're gonna end up with this point here and that's why this point maps to this one. It's fairly easy really once you understand the visualization of this it should be fairly trivial. Okay so that's the first step of the hyperboloid GCN model we map from Euclidean points into hyperboloid points. Okay the next step is we need to now do we need to find equivalent operations in the hyperboloid space to what GCN is doing in Euclidean space. So that means we first need to understand how to do feature transforms in the hyperbolic space. Let's see what they say. So we now want to learn transformations of points on the hyperboloid manifold. However there is no notion of vector space structure in hyperbolic space. So I think the main thing here you should you should have in your mind is like the closure property is violated. What I mean by that is if you are on a plane and you were to add two arbitrary vectors you end up being in the plane still. So that's the closure property. So basically let me go up here again. So if you have two vectors here let's imagine we have this vector here and this vector here. If we add them up we'll end up with additional vector that lies in the plane. But if we were to do if we were to do the same thing for this hyperboloid model we'd basically be violating the closure property and that's why we don't have a notion of vector space on this on this hyperbolic space. That's how I understand it. I may be wrong here but like that's my best understanding of this thing. Okay so let's continue here. So the main idea is to leverage the exponential and log maps so that we can use the tangent space to perform Euclidean transformations. So let me break it down for you. What they now do is they're gonna use the log operator to now get from from the hyperboloid point on to the tangent space again of the North Pole. So we are always mapping on to the tangent space of the North Pole. Then we apply once we have a point there then we apply this this this linear mapping W which may be which may reduce or increase the dimension. So that's why we have D prime here. Finally we apply again exponential mapping which means we take this whatever this point here is and we form a vector between origin and this point here and we do the usual like the shooting metaphor and that's how we end up on the manifold again. So again we we get from the we map from manifold onto the tangent space we do the transform there the linear transform and then we map it back on to the manifold. I'm gonna stop explaining now the exponential and log maps and assume you understand how we map from manifold to tangent space and back. Now we need to add the concept of a bias and how we do that is the following. So bias is a vector that's so we they define B so the bias as an Euclidean vector located in the tangent space of the North Pole again of the hyperboloid model and so what they do is they do something called basically parallel transport and the parallel transport is going to take the bias vector that lies in the tangent space of the North Pole it's gonna transport it in a smart way and I will not get into the formalism of parallel transport. We can imagine just kind of shifting that bias vector from the tangent space of the North Pole into the tangent space of this point X the point of interest the point we're currently trying to transform and then we're just going to apply exponential map starting from that point X. Now this may be confusing but again it has a very like simple and simple visual interpretation and semantics. It's just hard to maybe understand it from the first attempt from this equation so let me try and get back to our diagram here. So imagine we have let me just delete a couple of things here so as to reduce the clutter. Let me delete all of this and let's now try and understand how the biasing works. Okay so let's imagine we have so this is the the tangent space of the North Pole and let's imagine we have a bias vector somewhere here so maybe it's something like this and it's a learnable vector remember that so we were trying to learn weights and biases. So what we do is the following so now imagine we have a point that we are trying to transform and I'm going to pick just a just a single one like let's take this one and basically that point is mapped onto this point on the manifold and you can now imagine that this point here we have associated tangent space I'm gonna try and do that it's gonna probably fail miserably so we have a tangent space that touches only this point so it's a tangent space of this particular point. Okay so what we're going to do is take this bias vector B and we're gonna transport it onto this tangent space of this point here okay so we're gonna transport it to here let's imagine maybe it's now going to lie maybe somewhere here and once we have that we just apply the exponential map which means we're going to shift which means we're gonna do the following we're gonna take this point and now because of the bias vector and applying the exponential map we're gonna end up here so we add it we just successfully added a bias in the hyperbolic space so that's what we've done. Okay let me try and explain this once more because it's hard to visualize this and I did not do a great job of drawing this so we have a bias vector here in the tangent space we map it we parallel transport it into this different tangent space that correspond to this particular point of interest and once we have the bias vector there then we do the shooting so that's the exponential map and we end up from this orange point we end up here and thus we as I said successfully managed to add a bias in the hyperbolic space. Okay that's the best I can do in one attempt. Okay so let's get back to the section 4.2 we've defined we've successfully defined a linear mapping in the tangent space and we've successfully defined bias as well. Next up we need to define neighborhood aggregation so I'm gonna just jump to the equations straight ahead so here is what they do given two notes XI and XJ we're gonna apply log mapping and that means we end up in the tangent space of the North Pole and once we are there we're going to concatenate them as you can see by the symbol here and then we just pass them into the MLP and we do that for all of the J's from the neighborhood of node I and then we just apply a softmax that's how we basically end up with WIJ's. Once we have those coefficients we use those coefficients to do the aggregation the following way so again we have these are the hyperbolic embedding vectors of neighbors XJ's we're going to do logarithmic map but this time the map starts the map is based in point XI and not the North Pole we're gonna see why that is and once we have that that means now we're in the tangent space now we can do the simple scaling with WIJ's we sum those up and finally we end up with some resultant vector in the tangent space and then we map it back using the exponential map and that's how we end up with a new representation for this particular vector XI. So because this was the first time we did not use the North Pole as the basis of mapping let me just kind of explain this part a bit better so know that our proposed aggregation is directly performed in the tangent space of each center point XIH as this is where the Euclidean approximation is best we show in our ablation experiments that this local aggregation outperforms aggregation in tangent space at the origin due to the fact that relative distances have lower distortion in our approach basically what this means is let me go back to the example I showed you before so let's again focus on this particular orange point and its tangent space so now we're gonna map all of the points on the manifold onto this particular tangent space and then do the basically aggregation in that tangent space instead of using the tangent space of the origin that's the difference and they as they said they've done ablations and it turns out that doing this is better than doing aggregation in the in the in this particular tangent space here okay so that's it let me go back here and let me end up explaining the nonlinear activations so here is how is how the nonlinearities defined on a curved space so we take the particular embedding vector of interest that lies on the hyperboloid model we do the log mapping which means we map it on to the tangent space of the North Pole then we apply the nonlinearity whatever that is like value usually and then we apply the x map returning it back onto the manifold the thing to notice here is that these curvatures so KL minus 1 and KL these curvatures might be different and they are actually learnable parameter in hyperbolic GCN model so they can do this because the mathematics adds up they say here fortunately 10 tangent spaces of the North Pole are shared across hyperboloid model manifolds of the same dimension that have different curvatures making equation 10 so this is this equation mathematically correct okay that's pretty much it now let's glue everything back together and try to get a holistic overview what's going on here I know this was a lot of mathematics differential geometry a lot of details let's try and get like a high level mental model of what just happened here okay so there is a couple of steps okay so first step is we map from the Euclidean space on to the hyperbolic space once we have the feature vectors in the hyperbolic space then we do these basically special types of feature transforms and bias so there is a lot of back and forth between manifold and tangent space we mostly do we do everything in tangent space so we map this feature from hyperbolic space into tangent space we apply the linear transformation we get we return it we map it back onto the manifold and then we just shift it using this particular bias vector and it still remains on the manifold so that's this first step once we have those features we do that for all of the node features of our graph once we have that we do the smart aggregation whereby again we're going to be mapping onto tangent spaces of those and and this time tangent space is defined by particular node I for which we're trying to find representation okay we're not using the North Pole tangent space this time we do the weighted sum in that tangent space and then we make the result we map the resultant point back onto the manifold that's how we get these wise and then finally we apply this nonlinear basically mapping again we have back and forth between tangent space and manifold and we just apply we kind of squeeze in the your your regular non-linearity between these mappings okay that's that's it it looks complicated it actually is not that complicated when you're familiar with differential geometry and and this kind of sinks in and yeah okay so let me now briefly walk you through the results they showed that for a particular class of graphs that have this low hyperbolicity value Delta which basically means it's a fancy way of saying these are graphs that are tree like in nature and they showed that basically HGCN so that's that this model in this introducing this paper outperforms all of the previous space lines so even GNN such as GCN and get and sage and SGC and as well as neural networks and some shallow embeddings so they show better results there and they show that as we go to higher hyperbolicity constant which means that the graphs are less and less exponentially nature and less tree like they show worse results here okay and final results I want to show you are here they've done some oblations basically the oblations they've done is doing this attention aggregation in the North Pole's tangent space instead of using X eyes to form the tangent space so that's the difference and here C just stands for whether they use trainable curvatures or not and they showed that by by by both using the trainable curvatures as well as using the aggregation in the tangent space of X eyes that gives them the best results across various different datasets so yeah just some oblations they've done additionally they showed that for some for this particular data set disease the harder curvature of the hyperboloid model basically the better the results let me just show you how to parse this this chart basically if K is large let's say 10 to the power of 3 so that's like thousand if you plug in 10 to the power of 3 you'll end up with minus 3 so that's means we are here and you can see that for BK for like thousand we have like lower metric here compared to if K was much smaller so if case maybe maybe 1 over 10 that would be 10 raised to power of minus 1 which means we map to here so that means for 1 over 10 for for for high curvature basically we have better performance and again this ties back nicely to the visualization to the explanation I started with basically if we have crowded points in the Euclidean space the more the so so so the higher the curvature of this particular hyper hyperboloid model I'm having such a hard time pronouncing that word so let me just draw it like this so if this was even more curved so something like this that means that basically the separation would be even bigger because you can imagine that us even a small perturbation here in the in the Euclidean space would cause those two points to be mapped onto very like distant points on the actual manifold so maybe this one here would be mapped here and this one here would be mapped even here so and the higher the curvature the bigger this distance will grow and so that's why you can kind of imagine that higher curvatures like in the negative direction basically help help us spread out the feature vectors okay that was my best attempt to explain this paper there is a lot of mathematics I'm not an expert in differential geometry I know enough to basically understand on an intuitive level how this works it's hard to visualize all of this I hope that this paper helped you understand basically this this this this model a bit better if it did consider sharing the video out also consider subscribing to this channel and finally join our discord community until next time bye bye
[{"start": 0.0, "end": 4.2, "text": " What's cracking guys? In this video I'll be covering hyperbolic graph"}, {"start": 4.2, "end": 9.200000000000001, "text": " convolutional neural networks by the authors from the Yura Leskovitz group at"}, {"start": 9.200000000000001, "end": 15.0, "text": " Stanford and we're going to see that hyperbolic keyword here in the title is"}, {"start": 15.0, "end": 20.28, "text": " what makes this paper particularly scary and math heavy and I'm gonna also argue"}, {"start": 20.28, "end": 23.28, "text": " that it's not just mathematics for the sake of mathematics. I'm gonna show you"}, {"start": 23.28, "end": 30.720000000000002, "text": " why they have chosen to use this exotic geometric space and use it"}, {"start": 30.720000000000002, "end": 36.24, "text": " to learn like useful embeddings later on for node classification and link"}, {"start": 36.24, "end": 41.2, "text": " prediction tasks. So let me start with abstract here and then I'm gonna show"}, {"start": 41.2, "end": 45.16, "text": " you a nice visualization that's gonna give you like a gut feeling for why we"}, {"start": 45.16, "end": 49.8, "text": " are using hyperbolic spaces in the first place and I'm gonna also"}, {"start": 49.8, "end": 53.64, "text": " get into the mathematical formulas and so if you're not familiar with what like"}, {"start": 53.64, "end": 58.28, "text": " curvature of spaces, what hyperbolic space is, don't worry. So we'll get there."}, {"start": 58.28, "end": 63.4, "text": " Okay, so let's start here. Graph convolutional neural networks or GCNs"}, {"start": 63.4, "end": 68.84, "text": " for short embed nodes in a graph into Euclidean space which has been shown to"}, {"start": 68.84, "end": 75.8, "text": " incur a large distortion when embedding real-world graphs with scale-free or"}, {"start": 75.8, "end": 81.44, "text": " hierarchical structure, okay? And then they say we derive GCNs operations in"}, {"start": 81.44, "end": 86.96, "text": " the hyperboloid model of hyperbolic space and map Euclidean input features to"}, {"start": 86.96, "end": 91.0, "text": " embeddings in hyperbolic spaces with different trainable curvature at each"}, {"start": 91.0, "end": 96.88, "text": " layer. So my whole goal of this video will be to decode what like the thing"}, {"start": 96.88, "end": 102.16, "text": " they just said in this in this particular sentence here. Okay, so let me"}, {"start": 102.16, "end": 106.67999999999999, "text": " just read this one and then I'm gonna tell you what this scale-free graph is."}, {"start": 106.67999999999999, "end": 111.47999999999999, "text": " So in particular scale-free graphs have tree-like structure and in such graphs"}, {"start": 111.47999999999999, "end": 116.08, "text": " the graph volume defined as the number of nodes with some radius to a center"}, {"start": 116.08, "end": 123.08, "text": " node grows exponentially as a function of radius. So basically scale-free"}, {"start": 123.08, "end": 128.68, "text": " networks are just a particular type of networks that have this this power law"}, {"start": 128.68, "end": 134.36, "text": " behavior where nodes that have a lot of connections become less and less"}, {"start": 134.36, "end": 138.08, "text": " frequent. As you can see here asymptotically we have K which is the"}, {"start": 138.08, "end": 143.08, "text": " number of nodes. We have that the probability of a node having K"}, {"start": 143.08, "end": 148.20000000000002, "text": " connections as K grows you can see that like basically that probability drops"}, {"start": 148.20000000000002, "end": 154.12, "text": " according to this power law here. So yeah, basically the main idea actually is"}, {"start": 154.12, "end": 160.16, "text": " that this exponential keyword and if we have like graphs that are crowded"}, {"start": 160.16, "end": 164.52, "text": " because of this exponential growth of neighbors that's when we want to use the"}, {"start": 164.52, "end": 168.4, "text": " hyperbolic space. So now let me give you like a visual intuition for why that may"}, {"start": 168.4, "end": 173.6, "text": " be. Okay, let's get to this chart here. Okay, so let's imagine we have our nodes"}, {"start": 173.6, "end": 178.6, "text": " and we have the associated node features and we can always basically visualize"}, {"start": 178.6, "end": 183.08, "text": " node features as points in like Euclidean space. So let's now imagine our"}, {"start": 183.08, "end": 187.84, "text": " Euclidean space is this plane here. We have the points here and you can"}, {"start": 187.84, "end": 192.8, "text": " imagine that if we have like exponentially more neighbors here if"}, {"start": 192.8, "end": 197.8, "text": " it's kind of crowded then mapping to this like geometric space which we call"}, {"start": 197.8, "end": 205.04000000000002, "text": " hyperbolic space is going to make them more spread out and like that's the"}, {"start": 205.04000000000002, "end": 209.96, "text": " basic intuition. Basically by spreading the points which are densely clustered"}, {"start": 209.96, "end": 214.28, "text": " together in the Euclidean space so by spreading them out in the hyperbolic"}, {"start": 214.28, "end": 219.12, "text": " space you make it easier to discern to discriminate between different node"}, {"start": 219.12, "end": 225.36, "text": " features and thus do better job at classification etc. So that's the"}, {"start": 225.36, "end": 232.36, "text": " main mental model I want you to have throughout this video. And having said"}, {"start": 232.36, "end": 237.52, "text": " that now let me dig into like mathematical formalisms and let me try"}, {"start": 237.52, "end": 242.56, "text": " and explain what the hyperbolic GCNs basically are. Okay, I'm gonna start"}, {"start": 242.56, "end": 248.88, "text": " with some basic notation and explanation of what GCNs are. If you've"}, {"start": 248.88, "end": 253.44, "text": " never watched graph ML videos so far go ahead and check out my playlist on graph"}, {"start": 253.44, "end": 257.92, "text": " ML. Like in particular go and watch the GCNs, so graph convolutional network"}, {"start": 257.92, "end": 264.0, "text": " paper as well as maybe graph attention and network paper, so GATT paper. So"}, {"start": 264.0, "end": 268.96, "text": " that's gonna get you up to speed. But here I'm just gonna briefly recap what"}, {"start": 268.96, "end": 274.12, "text": " we've seen in those videos. So first of all the whole point of graph like"}, {"start": 274.12, "end": 279.28, "text": " representation learning is to learn these useful representations of nodes"}, {"start": 279.28, "end": 283.92, "text": " and sometimes edges which we can then use to do classification tasks on nodes"}, {"start": 283.92, "end": 289.0, "text": " on graphs on edges etc. So let me just show you the formalism here. So graph"}, {"start": 289.0, "end": 295.44, "text": " representation learning is this mapping F. So from this set V of nodes, set E"}, {"start": 295.44, "end": 300.8, "text": " of edges and then we have associated node features. Sometimes we also have edge"}, {"start": 300.8, "end": 305.24, "text": " features but here I'm just gonna they just ignored the edge features. So you"}, {"start": 305.24, "end": 310.88, "text": " can see the notation is the following. So X of I which means node I. So these are"}, {"start": 310.88, "end": 317.14, "text": " the features at the raw features because basically zero means zero layer before"}, {"start": 317.14, "end": 322.47999999999996, "text": " we even started applying the graph neural network. So and also we have this"}, {"start": 322.47999999999996, "end": 327.68, "text": " symbol E which means these are Euclidean raw features of this particular node I."}, {"start": 327.68, "end": 333.2, "text": " So that's how you treat this symbol here. Okay and the goal is to find like a"}, {"start": 333.2, "end": 339.58, "text": " mapping to this basically a representation Z which is of dimension"}, {"start": 339.58, "end": 344.44, "text": " the number of nodes times D prime which is the dimensionality of your output"}, {"start": 344.44, "end": 351.52, "text": " node features. Okay so the whole point is to find like a basically good features"}, {"start": 351.52, "end": 355.56, "text": " so that we can discriminate between different classes or do whatever"}, {"start": 355.56, "end": 360.92, "text": " arbitrary task. Okay so that's the graph representation learning. Now quickly on"}, {"start": 360.92, "end": 366.68, "text": " to how graph convolutional neural networks work. Let me just maybe draw a"}, {"start": 366.68, "end": 372.24, "text": " simple example graph here. So we have a node I here. We have a couple of"}, {"start": 372.24, "end": 377.44, "text": " neighbors. So we have some neighbors here. They are connected to node I. Of course"}, {"start": 377.44, "end": 382.6, "text": " these neighbors could have their own neighbors etc etc. But let's focus on"}, {"start": 382.6, "end": 387.08, "text": " this particular node I here and let's see how do we learn the representation"}, {"start": 387.08, "end": 391.84000000000003, "text": " of that particular node. Okay so what they first do is they create this"}, {"start": 391.84000000000003, "end": 397.68, "text": " intermediate representation H. So I can see here from layer L minus 1 which is"}, {"start": 397.68, "end": 402.36, "text": " the previous layer. We do the mapping using the weight matrix and then we add"}, {"start": 402.36, "end": 408.16, "text": " the bias. So we'll have like a separate set of these W's and B's in every single"}, {"start": 408.16, "end": 413.64, "text": " layer of the graph neural network of the GCN in this particular example. So once"}, {"start": 413.64, "end": 417.4, "text": " we form these intermediate representations what we do in order to"}, {"start": 417.4, "end": 424.16, "text": " update the feature vector of this node I is we simply sum. So we sum the"}, {"start": 424.16, "end": 431.48, "text": " this intermediate representation of node I with like a sum over neighbors of"}, {"start": 431.48, "end": 435.64000000000004, "text": " weighted intermediate representations. So let me just kind of break it down"}, {"start": 435.64000000000004, "end": 439.92, "text": " quickly. Basically what I've said there is the following. So let's imagine we"}, {"start": 439.92, "end": 443.84000000000003, "text": " have so these are the neighbors. We have three neighbors in this particular"}, {"start": 443.84000000000003, "end": 448.92, "text": " example. We have certain basically feature vectors associated with the"}, {"start": 448.92, "end": 453.40000000000003, "text": " neighbors. So something like that and let's imagine these are the H's. So these"}, {"start": 453.4, "end": 458.35999999999996, "text": " are the the representations that we have after we do this particular mapping here."}, {"start": 458.35999999999996, "end": 463.4, "text": " So we just do weighted average of those of those particular feature vectors. We"}, {"start": 463.4, "end": 469.47999999999996, "text": " sum them up and then apply the nonlinear activation function in order to get"}, {"start": 469.47999999999996, "end": 475.84, "text": " basically novel so layer L representation of node I. So we're gonna"}, {"start": 475.84, "end": 484.44, "text": " finally end up having like H, I for layer L and these are just Euclidean"}, {"start": 484.44, "end": 491.15999999999997, "text": " features now. Okay now these W IJs depending on the architecture these"}, {"start": 491.15999999999997, "end": 495.91999999999996, "text": " could be learnable but that's now getting into the attention spectrum. What"}, {"start": 495.91999999999996, "end": 503.67999999999995, "text": " the original GCN did here is basically so this this W IJ was simply 1 over"}, {"start": 503.68, "end": 511.12, "text": " square root DI times DJ where D is just a degree of a node. So that means you"}, {"start": 511.12, "end": 517.32, "text": " basically normalize this particular presentation depending on the degree of"}, {"start": 517.32, "end": 521.52, "text": " this node and degree of your target node J. So let's say this is node J in this"}, {"start": 521.52, "end": 525.76, "text": " particular example. Okay so that's how they've done it in the"}, {"start": 525.76, "end": 530.26, "text": " original paper and that's the GCN formalism. Now for the more important"}, {"start": 530.26, "end": 534.52, "text": " part let me introduce you to that formalism of hyperbolic spaces and let's"}, {"start": 534.52, "end": 539.14, "text": " see what it's all about. Okay so hyperbolic spaces have different models"}, {"start": 539.14, "end": 543.48, "text": " the most famous ones is this so-called Lorentz model also known as the"}, {"start": 543.48, "end": 546.88, "text": " hyperboloid model as you can see here and there is also this Poincar\u00e9"}, {"start": 546.88, "end": 551.8, "text": " ball model of hyperbolic space. So here they are gonna work with the hyperboloid"}, {"start": 551.8, "end": 556.06, "text": " model because they showed it's more stable and so they basically stuck"}, {"start": 556.06, "end": 560.9599999999999, "text": " with it. So we are going to be working with the hyperboloid model of hyperbolic"}, {"start": 560.9599999999999, "end": 567.7199999999999, "text": " space. So they introduced this like inner product called Minkowski inner product."}, {"start": 567.7199999999999, "end": 574.78, "text": " So it's a simple mapping of you map two topple of these D plus one dimensional"}, {"start": 574.78, "end": 580.56, "text": " points into the real basically into a real number and this is how Minkowski"}, {"start": 580.56, "end": 585.56, "text": " product is defined. Basically it's similar to your dot product to"}, {"start": 585.56, "end": 590.4399999999999, "text": " which you're used to and the only difference is basically this addition"}, {"start": 590.4399999999999, "end": 596.92, "text": " of a minus sign for the first coordinate of the points in this space. Okay next up"}, {"start": 596.92, "end": 602.5999999999999, "text": " they denote by this HDK they denote the hyperboloid manifold in D"}, {"start": 602.5999999999999, "end": 608.1199999999999, "text": " dimensions with constant negative curvature minus 1 over K where K is"}, {"start": 608.1199999999999, "end": 613.8, "text": " always bigger than 0. So briefly just what a curvature of space is that may"}, {"start": 613.8, "end": 619.1999999999999, "text": " seem like very scary but it's not. Basically you're usually used to working"}, {"start": 619.1999999999999, "end": 624.28, "text": " in the Euclidean space so let's imagine we have like a example of a Euclidean"}, {"start": 624.28, "end": 630.56, "text": " space a 2d space like a plane here. If we shoot parallel geodesics where"}, {"start": 630.56, "end": 635.56, "text": " geodesic is just a generalization of like a straight line to arbitrary spaces."}, {"start": 635.56, "end": 640.04, "text": " So if we were to shoot them in the Euclidean space here in the plane you"}, {"start": 640.04, "end": 643.8399999999999, "text": " can see that the distance between these two lines is always going to be"}, {"start": 643.8399999999999, "end": 647.56, "text": " constant and these two lines will never intersect nor diverge. They'll always"}, {"start": 647.56, "end": 651.28, "text": " stay at the same distance from each other. That's not the case in every single"}, {"start": 651.28, "end": 655.2199999999999, "text": " space and that's why we have the notion of curvature. In the case of a sphere if"}, {"start": 655.2199999999999, "end": 659.24, "text": " you shoot two parallel geodesics you can see they are going to intersect at the"}, {"start": 659.24, "end": 664.48, "text": " North Pole in this particular example which means when the"}, {"start": 664.48, "end": 669.88, "text": " parallel geodesics intersect we call that space positively curved and on the"}, {"start": 669.88, "end": 675.16, "text": " other hand if the parallel geodesics diverge then we call that space"}, {"start": 675.16, "end": 679.48, "text": " negatively curved and you can see here an example of a hyperbolic space here. So"}, {"start": 679.48, "end": 684.24, "text": " you can imagine if I were to extrapolate these points here they are going to"}, {"start": 684.24, "end": 688.88, "text": " diverge each in its own direction here across this hyperbolic space. So that's"}, {"start": 688.88, "end": 693.0, "text": " the idea with curvature. It's not that fancy just once you have this"}, {"start": 693.0, "end": 698.4, "text": " visual mental picture then everything becomes much easier. Okay so"}, {"start": 698.4, "end": 704.56, "text": " next up they have this tangent space at point X of the manifold HDK and"}, {"start": 704.56, "end": 710.12, "text": " let me just now show you how they define those two formally. So again this"}, {"start": 710.12, "end": 716.4, "text": " hyperboloid model is defined as a set of D plus one dimensional points such that"}, {"start": 716.4, "end": 721.88, "text": " the Minkowski inner product between a point with itself is basically always"}, {"start": 721.88, "end": 726.6, "text": " going to be constant and equals to minus K and additionally the first coordinate"}, {"start": 726.6, "end": 731.64, "text": " of these points needs to be positive. So that's how we define the"}, {"start": 731.64, "end": 737.08, "text": " hyperboloid model. Following up we have this tangent space which is just like a"}, {"start": 737.08, "end": 743.52, "text": " set of perpendicular vectors. So a set of orthogonal vectors to your vector X. So"}, {"start": 743.52, "end": 749.44, "text": " again basically it's a set of vectors V, D plus one dimensional vectors V such"}, {"start": 749.44, "end": 753.52, "text": " that the inner product again Minkowski inner product equals zero. So tangent"}, {"start": 753.52, "end": 757.48, "text": " space is a concept you're familiar with like even though this is just like a let"}, {"start": 757.48, "end": 763.52, "text": " me give you a like an analogous case in the case of like a sphere. Let's"}, {"start": 763.52, "end": 771.12, "text": " imagine we have a sphere here. So we have a sphere here and basically this is like"}, {"start": 771.12, "end": 776.68, "text": " maybe North Pole, this is like South Pole. Tangent space to the North Pole"}, {"start": 776.68, "end": 783.7199999999999, "text": " would be just like a simple plane. It's a plane such that it touches the North"}, {"start": 783.7199999999999, "end": 787.1999999999999, "text": " Pole. It basically touches a sphere only at a single point and that's at the"}, {"start": 787.1999999999999, "end": 791.1999999999999, "text": " North Pole. And you can see here that all of the vectors in this particular plane,"}, {"start": 791.1999999999999, "end": 795.88, "text": " so let me draw a couple of vectors here, all of these vectors are going to be"}, {"start": 795.88, "end": 800.52, "text": " perpendicular. So if I take the center of the sphere as the origin and"}, {"start": 800.52, "end": 805.1999999999999, "text": " if I were to draw, so this is the point X in this formalism, so this is point X"}, {"start": 805.2, "end": 809.6, "text": " and so basically you can see that this vector here, so all of these vectors in"}, {"start": 809.6, "end": 813.8000000000001, "text": " the plane are perpendicular, are orthogonal to this particular vector X."}, {"start": 813.8000000000001, "end": 819.88, "text": " So this is basically a nice way to form you to algebraically describe this"}, {"start": 819.88, "end": 824.44, "text": " notion of a tangent space. We'll soon see why it's convenient to instead of"}, {"start": 824.44, "end": 829.36, "text": " working on the manifold to be working on on a particular tangent space of that"}, {"start": 829.36, "end": 834.8000000000001, "text": " manifold. We'll see why that is convenient. Okay, let me continue here and"}, {"start": 834.8, "end": 839.68, "text": " let me introduce a couple more details. So I'm gonna quickly skim over over"}, {"start": 839.68, "end": 843.3199999999999, "text": " these formalisms because they're not as vital for this paper, but let me just"}, {"start": 843.3199999999999, "end": 848.3599999999999, "text": " introduce you to the mathematics. It may be interesting. So now for V and W which"}, {"start": 848.3599999999999, "end": 853.3199999999999, "text": " lie in the tangent space of the hyperboloid model at point X, we define"}, {"start": 853.3199999999999, "end": 860.0, "text": " this G of X which is basically something called a Riemannian metric"}, {"start": 860.0, "end": 865.4, "text": " tensor or it's a simple it's basically defined as a Minkowski inner product and"}, {"start": 865.4, "end": 871.68, "text": " it's gonna later on allow us to define distances in the tangent space. That's"}, {"start": 871.68, "end": 876.08, "text": " why it's an important contract and we call this tuple of the"}, {"start": 876.08, "end": 882.72, "text": " hyperboloid model and this Riemannian metric tensor, we call this a Riemannian"}, {"start": 882.72, "end": 888.8, "text": " manifold with negative curvature minus 1 over K. Okay, so not as important just"}, {"start": 888.8, "end": 893.7199999999999, "text": " like introducing you to some notation. So finally the tangent space is"}, {"start": 893.7199999999999, "end": 898.7199999999999, "text": " useful to perform Euclidean operations undefined in hyperbolic space and we"}, {"start": 898.7199999999999, "end": 905.1999999999999, "text": " denote by the norm of we basically induce the norm of a vector in tangent"}, {"start": 905.1999999999999, "end": 909.3199999999999, "text": " space by doing a square root of the inner product where inner product is"}, {"start": 909.3199999999999, "end": 913.3199999999999, "text": " Minkowski inner product and that's how we define the norm of vectors and by"}, {"start": 913.3199999999999, "end": 918.7199999999999, "text": " doing that we basically have a nice way to define a distance in tangent space"}, {"start": 918.72, "end": 925.44, "text": " of this particular hyperboloid manifold. Okay, so all of that formalism was"}, {"start": 925.44, "end": 932.52, "text": " basically so that we can understand what exponential and logarithmic maps are. So"}, {"start": 932.52, "end": 936.28, "text": " this is going to be the main construct we need to understand in order to"}, {"start": 936.28, "end": 940.4, "text": " understand how hyperbolic GCNs work. Before I get there I need to briefly"}, {"start": 940.4, "end": 945.4, "text": " introduce geodesics which are basically just and they say here which are"}, {"start": 945.4, "end": 951.6, "text": " generalizations of shortest paths in graphs or straight lines in Euclidean"}, {"start": 951.6, "end": 956.9599999999999, "text": " geometry. So that's just a generalization a notion of like a shortest path"}, {"start": 956.9599999999999, "end": 962.4, "text": " between two points in arbitrary spaces. So let me show you how they define it."}, {"start": 962.4, "end": 967.92, "text": " Let X be a point on the hyperboloid manifold. Let U be like a basically a"}, {"start": 967.92, "end": 974.76, "text": " point in a vector in the tangent space of that point X. We call that U the unit"}, {"start": 974.76, "end": 978.96, "text": " speed and because they're going to basically make sure that the inner"}, {"start": 978.96, "end": 982.24, "text": " product here or the norm of that particular vector is going to be equal"}, {"start": 982.24, "end": 987.88, "text": " to 1. And then they say the unique unit speed geodesic denoted like this such"}, {"start": 987.88, "end": 994.48, "text": " that basically that geodesic at a point 0 equals to this point X on the"}, {"start": 994.48, "end": 998.84, "text": " manifold. Next up we have gamma dot which just basically means a velocity vector"}, {"start": 998.84, "end": 1004.48, "text": " at point evaluated at 0 is going to be equal exactly to that U unit speed."}, {"start": 1004.48, "end": 1008.4, "text": " Okay so let me give you like a mental model I have when I think about these"}, {"start": 1008.4, "end": 1014.5600000000001, "text": " geodesics. So imagine we have a curved space such as this one. So something like"}, {"start": 1014.5600000000001, "end": 1021.64, "text": " this and that's just like a basically imagine we had some type of like a sheet"}, {"start": 1021.64, "end": 1025.68, "text": " of paper or something and I'm looking at that sheet from this side and that's"}, {"start": 1025.68, "end": 1029.68, "text": " where we get something like this. So now now imagine we have point X which is the"}, {"start": 1029.68, "end": 1035.04, "text": " point we've been using in this formalism of the geodesics here and let's imagine"}, {"start": 1035.04, "end": 1044.16, "text": " we have like a unit vector unit speed vector U and now what geodesic is is and"}, {"start": 1044.16, "end": 1048.96, "text": " and that this U lies in the tangential plane of this point X. So imagine we"}, {"start": 1048.96, "end": 1053.8400000000001, "text": " have like a tangential plane here and U just lies in that plane. And so what the"}, {"start": 1053.8400000000001, "end": 1057.96, "text": " geodesic is is imagine we start from this point and we have this velocity"}, {"start": 1057.96, "end": 1063.4, "text": " vector and for some amount of time you basically shoot like a point from you"}, {"start": 1063.4, "end": 1069.28, "text": " shoot a point from X using this velocity vector V and you just trace out where"}, {"start": 1069.28, "end": 1073.92, "text": " that point will go on this on this curved space. So basically imagine if we"}, {"start": 1073.92, "end": 1079.96, "text": " were to travel for one second maybe we'd end up somewhere here. And we'll see why"}, {"start": 1079.96, "end": 1085.44, "text": " that is useful because that basically allows us to map vectors from tangent"}, {"start": 1085.44, "end": 1089.4, "text": " space as you can see here. So we basically just map this vector here we"}, {"start": 1089.4, "end": 1093.72, "text": " mapped it onto a particular point on the on the manifold here. And that's how I"}, {"start": 1093.72, "end": 1098.76, "text": " like to think about geodesics and exponential and logarithmic maps which"}, {"start": 1098.76, "end": 1103.3600000000001, "text": " I'm going to introduce in a second. So and now we have for this particular"}, {"start": 1103.3600000000001, "end": 1108.68, "text": " hyperboloid model we can see how the geodesic is defined here basically some"}, {"start": 1108.68, "end": 1115.64, "text": " complex equation using hyperbolic cosine and the hyperbolic sine and it's not"}, {"start": 1115.64, "end": 1119.16, "text": " even important you can treat this as a black box. So what is important for you"}, {"start": 1119.16, "end": 1123.48, "text": " to understand is that as we are as we are basically changing this parameter T"}, {"start": 1123.48, "end": 1128.24, "text": " we're going to be tracing a path along the manifold. So we're going to be"}, {"start": 1128.24, "end": 1132.04, "text": " tracing a point that's always going to belong to manifold and not to the"}, {"start": 1132.04, "end": 1135.8400000000001, "text": " tangent space. And here they show how you can calculate the distance between two"}, {"start": 1135.84, "end": 1139.48, "text": " points on this hyperboloid manifold. Again some complicated equation we have"}, {"start": 1139.48, "end": 1146.12, "text": " Minkowski inner product we have arc cosine hyperbolic so not that important"}, {"start": 1146.12, "end": 1150.56, "text": " you can treat it as a black box. So what is important is that we have like"}, {"start": 1150.56, "end": 1154.8, "text": " geodesic and we have a distance. Okay so now to the more important part and"}, {"start": 1154.8, "end": 1158.8, "text": " that's the exponential and logarithmic maps. Let's see how these are defined. So"}, {"start": 1158.8, "end": 1164.6, "text": " given a point on the manifold X and a tangent vector V that belongs to the"}, {"start": 1164.6, "end": 1170.6399999999999, "text": " tangent space as defined by point X. So the exponential map maps from the"}, {"start": 1170.6399999999999, "end": 1176.7199999999998, "text": " tangent space of X on to the manifold on to the hyperboloid manifold. And you can"}, {"start": 1176.7199999999998, "end": 1182.1999999999998, "text": " see how it assigns the point it's basically evaluated as as geodesic at"}, {"start": 1182.1999999999998, "end": 1187.36, "text": " when you set t equals to 1. And that's precisely what I just explained here. So"}, {"start": 1187.36, "end": 1192.3999999999999, "text": " you have basically let me just map this directly here. So here in this notation"}, {"start": 1192.4, "end": 1198.16, "text": " we have X and V which means this thing here we now call it so instead of U we"}, {"start": 1198.16, "end": 1205.92, "text": " call it V. So this is V this is X and we basically what we do is we trace out"}, {"start": 1205.92, "end": 1211.76, "text": " this geodesic. So gamma is a unique geodesic satisfying that at t equals 0"}, {"start": 1211.76, "end": 1217.72, "text": " it equals X and the velocity is described by vector V. Which means as I"}, {"start": 1217.72, "end": 1223.28, "text": " said so we have a point here at X with the velocity V and we just trace out"}, {"start": 1223.28, "end": 1228.8, "text": " its path along the manifold and that's how we map vector V to a novel point on"}, {"start": 1228.8, "end": 1233.64, "text": " the manifold. So that's your exponential basically exponential map."}, {"start": 1233.64, "end": 1238.76, "text": " Vice versa we can define a logarithmic map which has this property that if you"}, {"start": 1238.76, "end": 1243.72, "text": " then apply after applying exponential if you apply a log then you'll"}, {"start": 1243.72, "end": 1248.52, "text": " end up with the initial vector V. And then they say here in general Romanian"}, {"start": 1248.52, "end": 1252.64, "text": " manifolds these operations are only defined locally but in the hyperbolic"}, {"start": 1252.64, "end": 1256.44, "text": " space they form a bijection between the hyperbolic space and the tangent space"}, {"start": 1256.44, "end": 1262.6000000000001, "text": " at a point. Now this might not be apparent why this is relevant but like"}, {"start": 1262.6000000000001, "end": 1267.52, "text": " it is. I'm gonna briefly tell you what this means and that's the following. So"}, {"start": 1267.52, "end": 1273.64, "text": " for this particular hyperbolic model you can see it here this tangent space even"}, {"start": 1273.64, "end": 1277.8400000000001, "text": " if it was infinite we'd have a unique point so for every single point on this"}, {"start": 1277.8400000000001, "end": 1282.44, "text": " plane so we basically have a situation where we can map any arbitrary point"}, {"start": 1282.44, "end": 1287.96, "text": " here to some point unique point on this particular hyperbolic manifold. And"}, {"start": 1287.96, "end": 1293.68, "text": " that would not be the case for arbitrary general Romanian manifold. So let me for"}, {"start": 1293.68, "end": 1299.2, "text": " example show you a contra example. So let's imagine we have a sphere. So let's"}, {"start": 1299.2, "end": 1303.5200000000002, "text": " imagine we have a sphere here and let's imagine that at the North Pole we have"}, {"start": 1303.52, "end": 1308.08, "text": " like a tangent space and let's imagine it's just an infinite tangent space. And"}, {"start": 1308.08, "end": 1313.24, "text": " so you can imagine that if we had a vector such as this one okay so this"}, {"start": 1313.24, "end": 1319.2, "text": " vector would maybe if we were to trace out the geodesic here by doing"}, {"start": 1319.2, "end": 1324.56, "text": " exponential by applying the exponential map we'd end up maybe mapping this"}, {"start": 1324.56, "end": 1331.8799999999999, "text": " vector to this point here. Okay but now the thing is because of how this"}, {"start": 1331.88, "end": 1339.24, "text": " manifold looks like it's a sphere if we had like maybe like 3x the size of this"}, {"start": 1339.24, "end": 1345.64, "text": " vector we'd end up doing like doing a full circle and then one more half and"}, {"start": 1345.64, "end": 1350.64, "text": " we'd end up at the same point here which means we've basically mapped we don't"}, {"start": 1350.64, "end": 1354.48, "text": " have a projection anymore we map these two vectors from the plane on to the"}, {"start": 1354.48, "end": 1358.2800000000002, "text": " same point. So both of these map to the same point and we don't have a projection"}, {"start": 1358.28, "end": 1363.48, "text": " and that's a problematic property if you want to learn embeddings. Okay so"}, {"start": 1363.48, "end": 1368.84, "text": " that's everything you need to understand. Now they just show how these"}, {"start": 1368.84, "end": 1373.44, "text": " exponential and logarithmic maps look like for this particular example of using"}, {"start": 1373.44, "end": 1377.48, "text": " a hyperboloid manifold. You can just see they're using cosine hyperboloid cosines"}, {"start": 1377.48, "end": 1382.8799999999999, "text": " etc etc but the main idea is the thing I just explained to you. Okay now that we"}, {"start": 1382.88, "end": 1389.1200000000001, "text": " have this differential geometry under our belt let's now dig into the actual"}, {"start": 1389.1200000000001, "end": 1392.92, "text": " model and understand how it works. Okay so this should now be fairly"}, {"start": 1392.92, "end": 1398.92, "text": " straightforward. The first step we need to do is given our node feature vectors"}, {"start": 1398.92, "end": 1403.68, "text": " which are in the Euclidean space initially we first want to map them into"}, {"start": 1403.68, "end": 1408.44, "text": " hyperbolic space. Okay so how we do that is the following. So they define"}, {"start": 1408.44, "end": 1413.24, "text": " something called North Pole of this hyperboloid model and they define it"}, {"start": 1413.24, "end": 1418.4, "text": " like this. You can see this like bold O the first coordinate is a square root of"}, {"start": 1418.4, "end": 1423.6000000000001, "text": " K everything else is zero and this is the North Pole of the of the hyperboloid."}, {"start": 1423.6000000000001, "end": 1429.72, "text": " And so why that is important is because if we were to construct a point if we"}, {"start": 1429.72, "end": 1436.28, "text": " were to augment our Euclidean feature vector here by just prepending zero as"}, {"start": 1436.28, "end": 1441.68, "text": " the zeroth dimension we can see that if we were to do inner product between this"}, {"start": 1441.68, "end": 1447.96, "text": " augmented Euclidean point with the origin we'd get a zero because basically"}, {"start": 1447.96, "end": 1453.32, "text": " we have zero here which means zero times zero is gonna be zero and because here"}, {"start": 1453.32, "end": 1458.04, "text": " we have all zeros no matter what we have in X we're gonna end up with zeros once"}, {"start": 1458.04, "end": 1463.2, "text": " you sum that up a bunch of zeros yields a zero and so that's why we have this"}, {"start": 1463.2, "end": 1467.8600000000001, "text": " fact here. Interesting property if you understand what this what's the"}, {"start": 1467.8600000000001, "end": 1472.3600000000001, "text": " semantics behind this expression that's that we we now know that this is a lot"}, {"start": 1472.3600000000001, "end": 1478.68, "text": " that this augmented point lies in the tangent space of this of this particular"}, {"start": 1478.68, "end": 1483.68, "text": " North Pole of the hyperboloid. Okay so that's what we have when we have zero"}, {"start": 1483.68, "end": 1489.0, "text": " that means we have orthogonal like vectors and they say therefore we"}, {"start": 1489.0, "end": 1494.4, "text": " interpret this point here as a point in the tangent space of the North Pole and"}, {"start": 1494.4, "end": 1500.64, "text": " basically then they show how how you can map from from the from that augmented"}, {"start": 1500.64, "end": 1506.42, "text": " point in the tangent space by just applying exponential map at North Pole"}, {"start": 1506.42, "end": 1511.92, "text": " to get the finally to get the hyperboloid embeddings. Okay let me quickly show you"}, {"start": 1511.92, "end": 1517.44, "text": " how you should think about this as it's fairly easy given the diagram up here so"}, {"start": 1517.44, "end": 1521.8, "text": " this is a tangent space of the North Pole imagine that this red dot here is"}, {"start": 1521.8, "end": 1525.1200000000001, "text": " the North Pole so this is the tangent space of the North Pole of this"}, {"start": 1525.1200000000001, "end": 1531.2, "text": " hyperboloid model here. Okay so now we want to map an arbitrary point from the"}, {"start": 1531.2, "end": 1536.1200000000001, "text": " tangent space on to the hyperboloid space. So what we are going to do"}, {"start": 1536.1200000000001, "end": 1540.24, "text": " is the following so imagine this is the point we're trying to to map so this is"}, {"start": 1540.24, "end": 1545.04, "text": " the one we're trying to find like a corresponding point on the manifold for"}, {"start": 1545.04, "end": 1548.8, "text": " this particular point here in the Euclidean space. So what we do is you"}, {"start": 1548.8, "end": 1555.68, "text": " can see we have this vector here and imagine this this plane is now touching"}, {"start": 1555.68, "end": 1560.1599999999999, "text": " this hyperboloid model at a single point so it's a tangent space as I said and"}, {"start": 1560.1599999999999, "end": 1564.84, "text": " then we just do the exponential map which is we shoot a point we start here"}, {"start": 1564.84, "end": 1568.56, "text": " from the North Pole and we just shoot a point in that direction with that"}, {"start": 1568.56, "end": 1573.92, "text": " velocity vector and then it's going to trace out this particular geodesic and"}, {"start": 1573.92, "end": 1577.3600000000001, "text": " we're gonna end up with this point here and that's why this point maps to this"}, {"start": 1577.3600000000001, "end": 1583.3200000000002, "text": " one. It's fairly easy really once you understand the visualization of this it"}, {"start": 1583.3200000000002, "end": 1588.92, "text": " should be fairly trivial. Okay so that's the first step of the hyperboloid GCN"}, {"start": 1588.92, "end": 1595.3200000000002, "text": " model we map from Euclidean points into hyperboloid points. Okay the next step is"}, {"start": 1595.3200000000002, "end": 1601.24, "text": " we need to now do we need to find equivalent operations in the hyperboloid"}, {"start": 1601.24, "end": 1606.08, "text": " space to what GCN is doing in Euclidean space. So that means we first need to"}, {"start": 1606.08, "end": 1611.04, "text": " understand how to do feature transforms in the hyperbolic space. Let's see what"}, {"start": 1611.04, "end": 1614.36, "text": " they say. So we now want to learn transformations of points on the"}, {"start": 1614.36, "end": 1619.08, "text": " hyperboloid manifold. However there is no notion of vector space structure in"}, {"start": 1619.08, "end": 1624.04, "text": " hyperbolic space. So I think the main thing here you should you should have in"}, {"start": 1624.04, "end": 1629.84, "text": " your mind is like the closure property is violated. What I mean by that is"}, {"start": 1629.84, "end": 1635.72, "text": " if you are on a plane and you were to add two arbitrary vectors you end up"}, {"start": 1635.72, "end": 1640.56, "text": " being in the plane still. So that's the closure property. So basically let me go"}, {"start": 1640.56, "end": 1646.72, "text": " up here again. So if you have two vectors here let's imagine we have this vector"}, {"start": 1646.72, "end": 1650.9199999999998, "text": " here and this vector here. If we add them up we'll end up with additional vector"}, {"start": 1650.9199999999998, "end": 1655.9599999999998, "text": " that lies in the plane. But if we were to do if we were to do the same thing for"}, {"start": 1655.96, "end": 1662.28, "text": " this hyperboloid model we'd basically be violating the closure property and that's"}, {"start": 1662.28, "end": 1666.64, "text": " why we don't have a notion of vector space on this on this hyperbolic space."}, {"start": 1666.64, "end": 1671.0, "text": " That's how I understand it. I may be wrong here but like that's my"}, {"start": 1671.0, "end": 1678.28, "text": " best understanding of this thing. Okay so let's continue here. So the main idea is"}, {"start": 1678.28, "end": 1685.6000000000001, "text": " to leverage the exponential and log maps so that we can use the tangent space to"}, {"start": 1685.6, "end": 1689.6, "text": " perform Euclidean transformations. So let me break it down for you. What they now"}, {"start": 1689.6, "end": 1696.24, "text": " do is they're gonna use the log operator to now get from from the"}, {"start": 1696.24, "end": 1701.1599999999999, "text": " hyperboloid point on to the tangent space again of the North Pole. So we are"}, {"start": 1701.1599999999999, "end": 1705.4399999999998, "text": " always mapping on to the tangent space of the North Pole. Then we apply once we"}, {"start": 1705.4399999999998, "end": 1711.1599999999999, "text": " have a point there then we apply this this this linear mapping W which may be"}, {"start": 1711.1599999999999, "end": 1715.48, "text": " which may reduce or increase the dimension. So that's why we have D prime"}, {"start": 1715.48, "end": 1720.08, "text": " here. Finally we apply again exponential mapping which means we take this whatever"}, {"start": 1720.08, "end": 1727.3600000000001, "text": " this point here is and we form a vector between origin and this point here and"}, {"start": 1727.3600000000001, "end": 1732.4, "text": " we do the usual like the shooting metaphor and that's how we end up on the"}, {"start": 1732.4, "end": 1736.96, "text": " manifold again. So again we we get from the we map from manifold onto the"}, {"start": 1736.96, "end": 1741.26, "text": " tangent space we do the transform there the linear transform and then we map it"}, {"start": 1741.26, "end": 1746.32, "text": " back on to the manifold. I'm gonna stop explaining now the exponential and"}, {"start": 1746.32, "end": 1750.36, "text": " log maps and assume you understand how we map from manifold to tangent space"}, {"start": 1750.36, "end": 1757.16, "text": " and back. Now we need to add the concept of a bias and how we do"}, {"start": 1757.16, "end": 1763.92, "text": " that is the following. So bias is a vector that's so we they define B so the"}, {"start": 1763.92, "end": 1767.48, "text": " bias as an Euclidean vector located in the tangent space of the North Pole"}, {"start": 1767.48, "end": 1772.92, "text": " again of the hyperboloid model and so what they do is they do something called"}, {"start": 1772.92, "end": 1777.92, "text": " basically parallel transport and the parallel transport is going to take the"}, {"start": 1777.92, "end": 1781.4, "text": " bias vector that lies in the tangent space of the North Pole it's gonna"}, {"start": 1781.4, "end": 1785.3600000000001, "text": " transport it in a smart way and I will not get into the formalism of parallel"}, {"start": 1785.3600000000001, "end": 1789.16, "text": " transport. We can imagine just kind of shifting that bias vector from the"}, {"start": 1789.16, "end": 1796.04, "text": " tangent space of the North Pole into the tangent space of this point X the point"}, {"start": 1796.04, "end": 1799.52, "text": " of interest the point we're currently trying to transform and then we're just"}, {"start": 1799.52, "end": 1805.2, "text": " going to apply exponential map starting from that point X. Now this may be"}, {"start": 1805.2, "end": 1811.32, "text": " confusing but again it has a very like simple and simple visual interpretation"}, {"start": 1811.32, "end": 1816.68, "text": " and semantics. It's just hard to maybe understand it from the first"}, {"start": 1816.68, "end": 1824.04, "text": " attempt from this equation so let me try and get back to our diagram here. So"}, {"start": 1824.04, "end": 1829.0, "text": " imagine we have let me just delete a couple of things here so as to reduce"}, {"start": 1829.0, "end": 1834.28, "text": " the clutter. Let me delete all of this and let's now try and understand how"}, {"start": 1834.28, "end": 1839.52, "text": " the biasing works. Okay so let's imagine we have so this is the the tangent space"}, {"start": 1839.52, "end": 1842.84, "text": " of the North Pole and let's imagine we have a bias vector somewhere here so"}, {"start": 1842.84, "end": 1846.68, "text": " maybe it's something like this and it's a learnable vector remember that so we"}, {"start": 1846.68, "end": 1851.76, "text": " were trying to learn weights and biases. So what we do is the following so now"}, {"start": 1851.76, "end": 1856.4, "text": " imagine we have a point that we are trying to transform and I'm going to"}, {"start": 1856.4, "end": 1862.68, "text": " pick just a just a single one like let's take this one and basically that point"}, {"start": 1862.68, "end": 1865.98, "text": " is mapped onto this point on the manifold and you can now imagine that"}, {"start": 1865.98, "end": 1870.68, "text": " this point here we have associated tangent space I'm gonna try and do that"}, {"start": 1870.68, "end": 1875.04, "text": " it's gonna probably fail miserably so we have a tangent space that touches only"}, {"start": 1875.04, "end": 1879.36, "text": " this point so it's a tangent space of this particular point. Okay so what we're"}, {"start": 1879.36, "end": 1884.4399999999998, "text": " going to do is take this bias vector B and we're gonna transport it onto this"}, {"start": 1884.4399999999998, "end": 1890.84, "text": " tangent space of this point here okay so we're gonna transport it to here"}, {"start": 1890.84, "end": 1897.6599999999999, "text": " let's imagine maybe it's now going to lie maybe somewhere here and once we"}, {"start": 1897.6599999999999, "end": 1902.56, "text": " have that we just apply the exponential map which means we're going to shift"}, {"start": 1902.56, "end": 1906.4399999999998, "text": " which means we're gonna do the following we're gonna take this point and now"}, {"start": 1906.44, "end": 1910.64, "text": " because of the bias vector and applying the exponential map we're gonna end up"}, {"start": 1910.64, "end": 1917.14, "text": " here so we add it we just successfully added a bias in the hyperbolic space so"}, {"start": 1917.14, "end": 1921.8, "text": " that's what we've done. Okay let me try and explain this once more because it's"}, {"start": 1921.8, "end": 1926.04, "text": " hard to visualize this and I did not do a great job of drawing this so we have a"}, {"start": 1926.04, "end": 1930.56, "text": " bias vector here in the tangent space we map it we parallel transport it into"}, {"start": 1930.56, "end": 1934.28, "text": " this different tangent space that correspond to this particular point of"}, {"start": 1934.28, "end": 1938.68, "text": " interest and once we have the bias vector there then we do the shooting so"}, {"start": 1938.68, "end": 1943.2, "text": " that's the exponential map and we end up from this orange point we end up here"}, {"start": 1943.2, "end": 1948.2, "text": " and thus we as I said successfully managed to add a bias in the hyperbolic"}, {"start": 1948.2, "end": 1954.92, "text": " space. Okay that's the best I can do in one attempt. Okay so let's get back to"}, {"start": 1954.92, "end": 1962.16, "text": " the section 4.2 we've defined we've successfully defined a linear mapping"}, {"start": 1962.16, "end": 1967.92, "text": " in the tangent space and we've successfully defined bias as well. Next"}, {"start": 1967.92, "end": 1973.6000000000001, "text": " up we need to define neighborhood aggregation so I'm gonna just jump to"}, {"start": 1973.6000000000001, "end": 1980.5600000000002, "text": " the equations straight ahead so here is what they do given two notes XI and XJ"}, {"start": 1980.5600000000002, "end": 1986.52, "text": " we're gonna apply log mapping and that means we end up in the tangent space of"}, {"start": 1986.52, "end": 1990.96, "text": " the North Pole and once we are there we're going to concatenate them as you"}, {"start": 1990.96, "end": 1995.1200000000001, "text": " can see by the symbol here and then we just pass them into the MLP and we do"}, {"start": 1995.1200000000001, "end": 1999.28, "text": " that for all of the J's from the neighborhood of node I and then we just"}, {"start": 1999.28, "end": 2005.68, "text": " apply a softmax that's how we basically end up with WIJ's. Once we have those"}, {"start": 2005.68, "end": 2010.6000000000001, "text": " coefficients we use those coefficients to do the aggregation the following way so"}, {"start": 2010.6000000000001, "end": 2017.8, "text": " again we have these are the hyperbolic embedding vectors of neighbors XJ's"}, {"start": 2017.8, "end": 2024.3999999999999, "text": " we're going to do logarithmic map but this time the map starts the map is"}, {"start": 2024.3999999999999, "end": 2032.32, "text": " based in point XI and not the North Pole we're gonna see why that is and once we"}, {"start": 2032.32, "end": 2037.8799999999999, "text": " have that that means now we're in the tangent space now we can do the simple"}, {"start": 2037.8799999999999, "end": 2044.44, "text": " scaling with WIJ's we sum those up and finally we end up with some resultant"}, {"start": 2044.44, "end": 2048.44, "text": " vector in the tangent space and then we map it back using the exponential"}, {"start": 2048.44, "end": 2052.64, "text": " map and that's how we end up with a new representation for this particular"}, {"start": 2052.64, "end": 2060.2400000000002, "text": " vector XI. So because this was the first time we did not use the North Pole as"}, {"start": 2060.2400000000002, "end": 2066.64, "text": " the basis of mapping let me just kind of explain this part a bit better so know"}, {"start": 2066.64, "end": 2070.0, "text": " that our proposed aggregation is directly performed in the tangent space"}, {"start": 2070.0, "end": 2076.6, "text": " of each center point XIH as this is where the Euclidean approximation is"}, {"start": 2076.6, "end": 2081.08, "text": " best we show in our ablation experiments that this local aggregation outperforms"}, {"start": 2081.08, "end": 2085.08, "text": " aggregation in tangent space at the origin due to the fact that relative"}, {"start": 2085.08, "end": 2088.96, "text": " distances have lower distortion in our approach basically what this means is"}, {"start": 2088.96, "end": 2094.88, "text": " let me go back to the example I showed you before so let's again focus on this"}, {"start": 2094.88, "end": 2101.36, "text": " particular orange point and its tangent space so now we're gonna map all of the"}, {"start": 2101.36, "end": 2106.12, "text": " points on the manifold onto this particular tangent space and then do the"}, {"start": 2106.12, "end": 2110.92, "text": " basically aggregation in that tangent space instead of using the tangent space"}, {"start": 2110.92, "end": 2115.12, "text": " of the origin that's the difference and they as they said they've done"}, {"start": 2115.12, "end": 2119.84, "text": " ablations and it turns out that doing this is better than doing aggregation in"}, {"start": 2119.84, "end": 2125.08, "text": " the in the in this particular tangent space here okay so that's it let me go"}, {"start": 2125.08, "end": 2133.0, "text": " back here and let me end up explaining the nonlinear activations so here is"}, {"start": 2133.0, "end": 2138.1600000000003, "text": " how is how the nonlinearities defined on a curved space so we take the"}, {"start": 2138.1600000000003, "end": 2143.7200000000003, "text": " particular embedding vector of interest that lies on the hyperboloid model we do"}, {"start": 2143.7200000000003, "end": 2147.6400000000003, "text": " the log mapping which means we map it on to the tangent space of the North Pole"}, {"start": 2147.64, "end": 2152.8399999999997, "text": " then we apply the nonlinearity whatever that is like value usually and then we"}, {"start": 2152.8399999999997, "end": 2159.0, "text": " apply the x map returning it back onto the manifold the thing to notice here is"}, {"start": 2159.0, "end": 2166.92, "text": " that these curvatures so KL minus 1 and KL these curvatures might be different"}, {"start": 2166.92, "end": 2174.72, "text": " and they are actually learnable parameter in hyperbolic GCN model so"}, {"start": 2174.72, "end": 2177.9599999999996, "text": " they can do this because the mathematics adds up they say here"}, {"start": 2177.9599999999996, "end": 2183.0, "text": " fortunately 10 tangent spaces of the North Pole are shared across hyperboloid"}, {"start": 2183.0, "end": 2188.16, "text": " model manifolds of the same dimension that have different curvatures making"}, {"start": 2188.16, "end": 2192.68, "text": " equation 10 so this is this equation mathematically correct okay that's"}, {"start": 2192.68, "end": 2197.6, "text": " pretty much it now let's glue everything back together and try to get a holistic"}, {"start": 2197.6, "end": 2201.04, "text": " overview what's going on here I know this was a lot of mathematics"}, {"start": 2201.04, "end": 2205.8, "text": " differential geometry a lot of details let's try and get like a high level"}, {"start": 2205.8, "end": 2210.04, "text": " mental model of what just happened here okay so there is a couple of steps okay"}, {"start": 2210.04, "end": 2214.64, "text": " so first step is we map from the Euclidean space on to the hyperbolic"}, {"start": 2214.64, "end": 2220.7599999999998, "text": " space once we have the feature vectors in the hyperbolic space then we do these"}, {"start": 2220.7599999999998, "end": 2228.4, "text": " basically special types of feature transforms and bias so there is a lot of"}, {"start": 2228.4, "end": 2232.2400000000002, "text": " back and forth between manifold and tangent space we mostly do we do"}, {"start": 2232.2400000000002, "end": 2236.12, "text": " everything in tangent space so we map this feature from hyperbolic space into"}, {"start": 2236.12, "end": 2240.64, "text": " tangent space we apply the linear transformation we get we return it we"}, {"start": 2240.64, "end": 2245.44, "text": " map it back onto the manifold and then we just shift it using this particular"}, {"start": 2245.44, "end": 2250.7200000000003, "text": " bias vector and it still remains on the manifold so that's this first step once"}, {"start": 2250.7200000000003, "end": 2255.12, "text": " we have those features we do that for all of the node features of our graph"}, {"start": 2255.12, "end": 2259.92, "text": " once we have that we do the smart aggregation whereby again we're going to"}, {"start": 2259.92, "end": 2265.04, "text": " be mapping onto tangent spaces of those and and this time tangent space is"}, {"start": 2265.04, "end": 2269.56, "text": " defined by particular node I for which we're trying to find representation"}, {"start": 2269.56, "end": 2274.52, "text": " okay we're not using the North Pole tangent space this time we do the weighted"}, {"start": 2274.52, "end": 2279.2799999999997, "text": " sum in that tangent space and then we make the result we map the resultant"}, {"start": 2279.2799999999997, "end": 2284.12, "text": " point back onto the manifold that's how we get these wise and then finally we"}, {"start": 2284.12, "end": 2290.16, "text": " apply this nonlinear basically mapping again we have back and forth between"}, {"start": 2290.16, "end": 2295.7599999999998, "text": " tangent space and manifold and we just apply we kind of squeeze in the your"}, {"start": 2295.7599999999998, "end": 2302.96, "text": " your regular non-linearity between these mappings okay that's that's it it looks"}, {"start": 2302.96, "end": 2306.88, "text": " complicated it actually is not that complicated when you're familiar with"}, {"start": 2306.88, "end": 2313.04, "text": " differential geometry and and this kind of sinks in and yeah okay so let me now"}, {"start": 2313.04, "end": 2319.96, "text": " briefly walk you through the results they showed that for a particular class"}, {"start": 2319.96, "end": 2326.96, "text": " of graphs that have this low hyperbolicity value Delta which basically"}, {"start": 2326.96, "end": 2331.36, "text": " means it's a fancy way of saying these are graphs that are tree like in nature"}, {"start": 2331.36, "end": 2336.72, "text": " and they showed that basically HGCN so that's that this model in this"}, {"start": 2336.72, "end": 2341.96, "text": " introducing this paper outperforms all of the previous space lines so even GNN"}, {"start": 2341.96, "end": 2348.16, "text": " such as GCN and get and sage and SGC and as well as neural networks and some"}, {"start": 2348.16, "end": 2352.88, "text": " shallow embeddings so they show better results there and they show that as we"}, {"start": 2352.88, "end": 2360.7200000000003, "text": " go to higher hyperbolicity constant which means that the graphs are less and"}, {"start": 2360.7200000000003, "end": 2367.2, "text": " less exponentially nature and less tree like they show worse results here okay"}, {"start": 2367.2, "end": 2373.8799999999997, "text": " and final results I want to show you are here they've done some oblations"}, {"start": 2373.8799999999997, "end": 2381.06, "text": " basically the oblations they've done is doing this attention aggregation in the"}, {"start": 2381.06, "end": 2388.6, "text": " North Pole's tangent space instead of using X eyes to form the tangent space so"}, {"start": 2388.6, "end": 2392.62, "text": " that's the difference and here C just stands for whether they use trainable"}, {"start": 2392.62, "end": 2397.4, "text": " curvatures or not and they showed that by by by both using the trainable"}, {"start": 2397.4, "end": 2404.4, "text": " curvatures as well as using the aggregation in the tangent space of X eyes"}, {"start": 2404.4, "end": 2409.2, "text": " that gives them the best results across various different datasets so yeah just"}, {"start": 2409.2, "end": 2413.3199999999997, "text": " some oblations they've done additionally they showed that for some for this"}, {"start": 2413.3199999999997, "end": 2418.08, "text": " particular data set disease the harder curvature of the hyperboloid model"}, {"start": 2418.08, "end": 2422.14, "text": " basically the better the results let me just show you how to parse this this"}, {"start": 2422.14, "end": 2428.72, "text": " chart basically if K is large let's say 10 to the power of 3 so that's like"}, {"start": 2428.72, "end": 2434.08, "text": " thousand if you plug in 10 to the power of 3 you'll end up with minus 3 so that's"}, {"start": 2434.08, "end": 2439.6, "text": " means we are here and you can see that for BK for like thousand we have like"}, {"start": 2439.6, "end": 2448.7599999999998, "text": " lower metric here compared to if K was much smaller so if case maybe maybe 1"}, {"start": 2448.76, "end": 2454.4, "text": " over 10 that would be 10 raised to power of minus 1 which means we map to here so"}, {"start": 2454.4, "end": 2461.0400000000004, "text": " that means for 1 over 10 for for for high curvature basically we have better"}, {"start": 2461.0400000000004, "end": 2466.2000000000003, "text": " performance and again this ties back nicely to the visualization to the"}, {"start": 2466.2000000000003, "end": 2473.2400000000002, "text": " explanation I started with basically if we have crowded points in the Euclidean"}, {"start": 2473.24, "end": 2478.8799999999997, "text": " space the more the so so so the higher the curvature of this particular hyper"}, {"start": 2478.8799999999997, "end": 2484.3199999999997, "text": " hyperboloid model I'm having such a hard time pronouncing that word so let me"}, {"start": 2484.3199999999997, "end": 2488.9199999999996, "text": " just draw it like this so if this was even more curved so something like this"}, {"start": 2488.9199999999996, "end": 2493.6, "text": " that means that basically the separation would be even bigger because you can"}, {"start": 2493.6, "end": 2497.08, "text": " imagine that us even a small perturbation here in the in the Euclidean"}, {"start": 2497.08, "end": 2503.84, "text": " space would cause those two points to be mapped onto very like distant points on"}, {"start": 2503.84, "end": 2508.2799999999997, "text": " the actual manifold so maybe this one here would be mapped here and this one"}, {"start": 2508.2799999999997, "end": 2512.16, "text": " here would be mapped even here so and the higher the curvature the bigger this"}, {"start": 2512.16, "end": 2517.36, "text": " distance will grow and so that's why you can kind of imagine that higher"}, {"start": 2517.36, "end": 2523.04, "text": " curvatures like in the negative direction basically help help us spread"}, {"start": 2523.04, "end": 2529.72, "text": " out the feature vectors okay that was my best attempt to explain this paper there"}, {"start": 2529.72, "end": 2535.08, "text": " is a lot of mathematics I'm not an expert in differential geometry I know"}, {"start": 2535.08, "end": 2541.0, "text": " enough to basically understand on an intuitive level how this works it's hard"}, {"start": 2541.0, "end": 2545.08, "text": " to visualize all of this I hope that this paper helped you understand"}, {"start": 2545.08, "end": 2550.12, "text": " basically this this this this model a bit better if it did consider sharing"}, {"start": 2550.12, "end": 2554.92, "text": " the video out also consider subscribing to this channel and finally join our"}, {"start": 2554.92, "end": 2582.0, "text": " discord community until next time bye bye"}]