Understanding over-squashing and bottlenecks on graphs via curvature | Ricci Flow | Paper Explained
❤️ Become The AI Epiphany Patreon ❤️
https://www.patreon.com/theaiepiphany

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

In this video I cover the "Understanding over-squashing and bottlenecks on graphs via curvature" paper that introduces a new graph rewiring method that alleviates the problem of over-squashing by borrowing ideas from the field of differential geometry.

The main workhorse behind the method is the discrete version of Ricci curvature (balanced Froman curvature) and an analog of Ricci Flow as applied to graphs.

▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬ 
✅ Paper: https://arxiv.org/abs/2111.14522
✅ M. Bronstein's blog: https://towardsdatascience.com/over-squashing-bottlenecks-and-graph-ricci-curvature-c238b7169e16
✅Excellent Ricci-flow video: https://www.youtube.com/watch?v=PwRl5W-whTs&ab_channel=Aleph0
▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬ 

⌚️ Timetable: 
00:00 Bottlenecks and over-squashing in graphs
04:42 The concept of Ricci curvature and flow
11:10 Message passing neural networks and notation
16:45 Formalizing the concept of over-squashing
22:05 Balanced Forman Curvature
31:15 Connecting curvature with over-squashing
37:10 Connection with the Cheeger constant and spectral theory
41:20 SDRF - Stochastic Discrete Ricci Flow
47:47 Results, graph statistics, and limitations

▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬ 
💰 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/

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

#ricciflow #geometric #graphs
 What's up guys in this video I'm covering understanding over squashing and bottlenecks on graphs via curvature paper by Jake topping Francesco DiGiovanni Benjamin Tamboulin Xiao Wen Dong and Michael Bronstein So before we even start I guess it will only make sense for me to explain to you what over squashing Over squashing exactly means what our bottlenecks and finally what is curvature? So let's see this sentence in in the abstract that connects these these concepts And then I'm gonna give you an explanation of what those exactly are So we provide a precise description of the over squashing phenomena in graph neural networks and analyze how it arises from bottlenecks in the graph for this purpose we introduce a new edge based combinatorial Curvature and prove that negatively curved edges are responsible for the over squashing issue So negatively curved edges whatever that means I'm gonna explain that briefly Are responsible for the over squashing issue, okay? So let me first start with the preliminaries So let's first see what this bottleneck thing is in graph neural networks And what over squashing is which is a very connected phenomena So you may be familiar with the RNN so recurrent neural networks And you may know that we have this squashing phenomenon occurring in RNN as well, so So this is just a rolled out version of an RNN model And you can see that so some information some input is fed into the RNN here And then this information is passed on to the next step here where we have another piece of information Mixing together with this previous step and then in the third step We'll be having this additional information mixing with the information from the previous two steps and so as you can imagine so already here the like the this this information from from the first step Constitutes only like maybe roughly one-third of the informational content that you can be they can be find found in this particular Time step of RNN and so the more we go towards right the this this information from this step constitutes a minor and minor percentage of the informational content of that fixed size vector and Basically, that's what bottleneck is all about so as you can see here because we have this Bottleneck where all of these informations have to pass and be squeezed inside of this fixed size vector So that bottleneck causes the over squashing of information, so that's how these two concepts are related Okay, so we know that RNNs were susceptible to this particular problem, and we know the later some models such as LSTM or GRU's managed to basically focus on on some parts of the information more on some parts of the information less and Thus they managed to you know in a way avoid this bottleneck problem, but not completely Well with graph neural networks the problem is even more severe and the reason can be seen in this example here So you can see that like compared to RNNs we have exponentially more Informational vectors coming in in every single step so because of how the spatial GNNs work, and that's by basically aggregating One hop neighborhood. That's how usually GNNs are implemented So because of that if you had a graph such as maybe let me just draw some examples So if you have a graph like this where this node is connected to two more nodes, and then these two nodes are connected to two more nodes So like this so then if you were to start calculating features for this one so in the first step you'd be including So let me just draw this so you'd include information from these two and These two would include information from these two which means that information from this vector here from this node here will in the first step propagate here And then in the second step it will propagate all the way here, and that's what we can see visually on this graph exactly so basically for Topology such as this one where we have with every where every node will have two additional neighbors Will basically have exponential grow growth of Information content that we need to squeeze in ultimately into into a fixed size representation of this particular node here So that's the that's the bottleneck and over squashing problem And it's as you can see intimately related to the topology of a particular graph you're dealing with okay Next up second concept that I want to explain before we start analyzing the paper, and that's the curvature so Let me read this this Statement here so richie curvature of a manifold can be characterized by geodesic dispersion I whether two parallel geodesics shot from nearby points converge Which happens in a positively curved spaces locally resembling a sphere such as this example here Or they remain parallel in the flat or Euclidean case as you can see here Or they diverge negative curvature giving rise to hyperbolic geometry So most of you are probably just familiar with Euclidean geometry, but like back in I think 19th century already people such as Riemann and And others started devising these other types of geometry So you can see here that if you were to shot like two parallel lines so two geodesics where geodesic is just a fancy name Of saying like basically the shortest path on a particular geometry Which in the case of a Euclidean plane will be like like a straight line But in the case of like sphere or hyperbolic type of surfaces It's not going to be a straight line, so you can see here if you shoot two Two geodesics they're going to ultimately converge here on the North Pole And that's why so when the lines convert when the geodesics converge that space is basically described as being positively curved Here you can see that these geodesics are gonna. Let me just take a pen here, so they are going to diverge So this is going to track this line here, and this geodesic is going to be tracking this line here So you can see they are diverging and because of that this hyperbolic space has negative curvature, okay? So this is also so this Ricci curvature basically is a scalar that tells you whether the space is Positively curved in the case of a sphere or zero or negatively curved in the case of this particular geometric object here Okay, so aside from the Ricci curvature. We need to know a couple more concepts and the main one will be Ricci flow Which basically tells you the rate of change of a metric tensor? Is directly proportional to the Ricci curvature now that may seem and sound very complex because it probably is But I want to show you a short video that's going to give you like all the necessary intuition that you need to have before proceeding with this paper, so Just as a trivia. I want to mention a couple of people here, so this guy here called Gregorio Ricci Curbastro Was the guy who invented the Ricci curvature and after whom the Ricci curvature was named. This is Hamilton who discovered the Ricci flow Equation and finally this is Gregory Perelman a guy who managed to solve the famous Millennium problem in mathematics called the Poincare Conjecture and he solved it using basically building on top of Hamilton's work And he used Ricci flow to solve this Poincare conjecture also as a fun fact he decided to Basically decline both the Fields Medal which is an equivalent of a Nobel prize in in Mathematics as well as the Millennium prize like a one million dollar prize for solving one of these seven Millennium problems as proposed by the Clay Institute So Poincare Conjecture was one of those those. Okay, so Now check out this video where you'll understand what Ricci flow is a lobar and then we'll continue Ricci flow is a way of changing the metric tensor over time so that the manifold becomes rounder So how do we express Ricci flow concretely? I want you to focus on this region over here the Ricci flow inflates it like a balloon By convention, we say that it has negative Ricci curvature So if the curvature is negative the length increases Now focus on this region here Ricci flow deflates it So if the Ricci curvature is positive the length decreases If the Ricci curvature is positive the length decreases We can phrase this differently g decreases means the derivative of g is negative g increases just means the derivative of g is positive These two guys always have opposite sides So we might guess an equation like this And that's it That is the equation describing Ricci flow. Okay, cool So I strongly suggest you go ahead and watch the whole video as it's super informative And but this this clip I just showed you is enough for you to understand the paper so we can continue Cool. So as you just saw, we have Ricci flow is basically this differential equation connecting metric tensor with Ricci curvature And you can see so in the example of a body you can see here on the screen We have that this we see that this part has very negative curvature, which is denoted by this blue color And by by by applying Ricci flow because of the negative Like negative value of the curvature that part is going to be inflated Whereas this part which which has uh, like positive curvature is going to be deflated Basically, and we end up with something like this So we can see that Ricci flow in this continue on this continuous manifold can reduce these bottlenecks And now let's just translate this idea onto the discrete case Which are the graphs and we can see that intuitively what happens is is a similar thing So we can see we have a bottleneck here. So let me just change the color So we see a bottleneck here, which is denoted again by a blue edge and by inflating that space by adding Edges here, uh, basically we are making this part of the space more positive and we are also They are also removing some of the edges here Which means we'll have less edges here and then the statistics of the graph stays roughly the same But like we reduce bottleneck and you can see that the colors are Homogenized meaning that this became more reddish and this part that was super red now became Also has some blue Colors to it. So that's that's what we we managed to accomplish a similar thing to this Analogous thing to this what happened in the continuous space uh, cool So now let me just show you some preliminaries and then we'll we'll we'll uh, See how they formalize the notion of over squashing and then we'll see how they formalize the notion of negative curvature on graphs And finally how they connect the two so that they can devise an algorithm where they'll be picking these negative edges and rewiring the graph to get Uh, uh less problems with over squashing so, um Let's see some piece of notation here first this s sub r of i Is basically the the the neighborhood So it's a set of these j's of nodes j's that belong to the set of all nodes denoted as v That have this geodesic distance between i and j that's precisely equal to r So it's a fancy way of saying this is a set of nodes j which are exactly r hops away from node i okay Uh, and then this b sub r of i is the same thing but here we have like a smaller or equal Which means we'll be including all of the intermediate Intermediate nodes and thus this is uh, like a receptive field of this particular, uh node Okay, just to visualize the notation. It's going to be probably a bit easier so if this node 2 here is our node i then the The s1 neighborhood of i is basically nodes 3 and nodes 1 Uh, then the the the s2 neighborhood So if we were to draw s2 neighborhood of i that's going to be nodes 0 and 4 As you can see we need exactly the shortest path takes two Edges to get to node 0 and the same for node 4 Finally the the b neighborhood. So let's say we have uh neighborhood b2 of i Is going to encompass all of these nodes we saw so that's going to be b2 And let me just check whether I think it also includes. Yeah, it also includes node 2 as well So this every all of these nodes are now going to be b2 neighborhood of i and just an additional detail I assume b stands for ball and s stands for surface which makes intuitive sense As you can see here, we can include the whole volume all of these nodes Whereas in s we just take the front so we basically ignore all all of these inner nodes inside of the s sets cool, so next up, uh just a Short mention of message passing neural networks and if you're not familiar with graph neural networks I have a whole playlist i'm going to link it somewhere here. You can check it out. I'm going to just briefly Recap what this is all about And you can see that in order to calculate the features of a node i, uh in layer l plus one What we do is the following so we take the previous Feature of that node i so in the previous layer a layer l and we basically combine it So maybe concatenation with this expression here and then we we apply this function. That's called the update function phi Okay, so let me just now decouple What this term is all about so you can see we have a Some j goes from one to two n Which is basically n is the the cardinality of the node set So that means there's a fancy way of saying it's the number of nodes in your graph A hat ij is basically your adjacency matrix So the connectivity matrix, but this is with additional twist They added self edges and that means basically every node will have additionally uh implied edge like this Although if it's undirected it's going to be uh, like both directions basically so every node will have this self edge And plus they also have normalization using these d matrices, which are basically your um, well, yeah degree matrices and this just normalizes the adjacency the augmented adjacency matrix a tilde So what this will effectively do is filter out so this is going to be Um non-zero only for immediate nodes of node i so that means we're just going to look at the one hop neighborhood of node i and Otherwise this will be zero and thus we won't care about this thing Uh, whereas this is just your message passing function psi and these are the representations of node i and its neighbors node j Uh, so Let me just show you a diagram to make it a bit Uh easier so that means we're going to take a look at the one hop neighbors of node h of node 1 And we're going to aggregate somehow combine this feature with this feature using some uh function psi Which is usually like mlp like a multilayer perception We're going to form representations in such a way which are called messages and then we're going to aggregate them Uh like this so in this particular case they they've chosen a particular Uh permutation invariant function i sum in this particular case but in general it can be uh whatever like whatever function that's that's permutation invariant like maybe Uh like average or or even a max function is permutation invariant and so people usually denote that you'll probably see that in the literature as like o plus Uh which is a general a generic permutation invariant operator instead of using sum So that's some uh preliminaries uh the notation and uh and uh these generic message passing neural networks And now let me show you how they formalize the concept of over squashing Uh but before that why do we care like well the reason we care is because as we saw as soon as we have long dependencies The information is going to be over squashed and thus the two remote nodes cannot communicate effectively with each other And so they say here we say that a graph learning problem has long range dependencies when the output of a mpn n depends on representations of distant nodes interacting with each other And so in these types of graphs where which are called heterophilic uh as compared to homophilic Uh you basically want to have this uh remote communication going on if you want to have accurate predictions And so that's why we need to solve the over squashing problem if we are to be performant on these heterophilic types of graphs So let me show you how they formalize this this notion of over squashing Okay let's first uh let me show you the the notation here before I start parsing the equation uh the inequality So what they have is the following so they have nodes i and s from the set of nodes v such that s belongs to the set s sub r plus one of i Which means uh s is r plus one uh hops away from node i so that's something like this maybe we have a node i here And then we have a bunch of nodes here bunch of nodes and then somewhere here we have node s And this shortest path to get from from uh basically i to s is equal to r plus one So let me just draw that so that's r plus one length okay so we have node s here and node i here and um basically then they say if the If you can bound the gradient of the phi and psi functions which are the message and uh and update functions Basically if you can bound them by some some some scalars alpha and beta uh then uh they show that this here this expression here holds And this what this tells us is the following so the sensitivity of this representation of node i in layer r plus one Uh and sensitivity with respect to uh node s so to the raw features of node s is upper bounded So we take the absolute value of this of this uh derivative here and we can see it's bounded by alpha beta Raise to the power of r plus one times a hat raised to the power of r plus one and then we just take the uh index by i and s Okay so there is a couple of things worth mentioning here first of all if you're not familiar with taking powers of these adjacency matrices There is a special semantics behind uh a raised to the power r plus one namely if you index this matrix here with i s You'll get the number of shortest paths between i nodes i and nodes s which makes intuitive sense So basically the more such paths we had that means that s so the features from from from the information from node s Had multiple paths by which they could reach node i and thus you can intuitively understand that that means that this upper bound is going to become bigger Because the end the over squashing will will be uh like uh less um prominent That's observation number one observation number two here is the following so you do have to have uh you do have to to observe the representation of node i Uh only uh after applying r plus one uh layers of of your graph neural network the reason is underreaching If you were to just apply let's say if like less than r plus one then this information from node s would have not reached node i yet So that means maybe the information from from this node s only have reached until here and that means that this is going to be uh zero Because like there is no influence of hs of the of the raw vector of node s uh on the representation Because the information still hasn't propagated to node i so that's something to keep in mind So that means that here you have to have r plus one because then you're basically calculating non-zero sensitivity of node i And how the information from s influences node i so i think that's that's pretty much everything you need to understand about about this formula So it's a nice way of connecting over smoothing on one hand with topological uh topology of your graph on the other hand okay So as an example they show here for example if the uh shortest path between i and s is r plus one and the sub graph induced on on this uh b set is a binary tree Uh then this adjacency matrix uh like indexed at is is going to have this particular shape and what's interesting here is that as r grows Which means as you're looking at at further away nodes you're going to have exponential decrease of this term Which means in turn that you're going to have small this will be exponentially decreasing and thus the sensitivity will be exponentially decreasing Which means that the over squashing will become more and more prominent Okay now let's continue so let me show you now how they formalize how they calculate the curvature of a graph that may be unintuitive to some of you As well as to me on the first pass of reading this paper Okay so we saw how the how these curved spaces look like when they are continuous Now let's see how this thing works for discrete case i.e. for graphs So intuitively the the notion is the following so if you take these two nodes p and q and you take two edges you'll see that in graphs such as this one They'll tend to converge to this node k and thus form a triangle and basically triangles will be a feature that indicates that the space is positively curved in graphs On the other hand if you take two edges and they stay on the same distance then and they form four cycles by doing so then this space is going to be classified as having zero curvature And finally if we have edges that start diverging then in that case the space is negative Now this is kind of hand wavy because unless you attach geometric like information to these edges like the fact we just chosen to draw the graph like this doesn't mean anything But like you can imagine that also like you can see here that the path between this node and this node starts becoming larger and larger whereas here it's like zero and here it stays constant So that's maybe a better way to think about this but like just visually as well you can see that these two kind of converge these two stay parallel and these two diverge This is probably yeah probably better to explain it like this Okay so now intuitively what this curvature calculation needs to do is count these topological elements and by counting them decide on the actual curvature of an edge So let's see how they choose to do that So first worth mentioning there are two discrete variants of calculating rigid curvature for graphs one is known as the Olivier curvature denoted as this italic weird font K symbol And we also have this from a Foreman curvature denoted as big F here So there are trade-offs between these two curvature Olivier is much more expressive but much more computationally expensive Foreman has the opposite properties basically it's much more efficient computationally but it's not as expressive as Olivier's curvature What they've done is they've taken the Foreman curvature and they've upgraded it to this balanced Foreman curvature And in order to understand the equation let me first break down a couple of sets we'll need to take care about So the first set is this one which basically tells you the number of triangles that are formed on this edge ij And you can formally basically calculate that by finding an intersection between S1 sets of node i and node j So these are the triangles that are based at the edge ij So let me show you an example so if we have here this particular graph and let me just Okay so basically this is node i here and this is node j we find the S1 sets first so for node i so S1 of i is going to be this It's going to be this element here because you can see the distance is just one this one this one and this one as well as j so this is the S1 set On the other hand if we want to calculate S1 set for j that's going to be 5, 6 and 0 And what they do is they find an intersection and you can see that the only intersection we have in this particular example is node 6 So this one here and as you can see it does form a triangle and that's the only triangle we have in this particular graph So that's the first thing we need to care about triangles the second thing we need to care about is these four cycles And you can see here a formulaic description i'm going to just read you what it represents and that's that these are the neighbors of i forming a four cycle based at the edge ij without the diagonals inside Okay so basically let me again show you this for node i the four cycles are going to be so that those are going to be 2 and 3 because you can see here we have a four cycle here going from i to j and then back So it's a four cycle we have a second four cycle going over 3 as you can see here going to j and backwards so those are four cycles And you may wonder why have I excluded 4 from this set and the reason is because we have this diagonal here and that's why we will not include node 4 into this set of four cycles of node i Okay now let me try and connect that with the formula just for fun so you can see here what the formula states and let's check whether this why the node 4 basically will not belong to a set So we can see that this set of four cycles for node i is a set of these k's such that k is basically belongs to S1 set of node i but does not belong to S1 set of j neither can k be equal to j Okay let me now just delete this to make this clearer so let me delete everything here and let me basically show you how this is going to function so k belongs to S1 of i so that means k is one of these elements here okay It's going to be one of those elements here and then we exclude basically we exclude j which means we exclude this one and we also exclude everything that belongs to node S1 set of j so that means we're going to exclude this one as well So we end up with 2, 3 and 4 and we already saw that 2 and 3 do satisfy all of the conditions and thus we included those in this set but we for some reason we did not include number 4 and the reason is because of this other condition So that k needs to be such that there exists this node w that belongs so that means that this set here is non-zero not empty set so you can see that S1 of k so let's find S1 of k so k is 4 in our example so this is our k this is our potential candidate at this point of time So this is these are the S1 this is the S1 neighborhood of k and intersection with S1 of j is going to be just this node here so this is going to be the intersection But at the same time we need to find something that does not belong to S1 and because this thing belongs to S1 that's why we have to digit again and that's a very complicated way of telling you that hey if we have a diagonal here we cannot count in this 4 cycle that's the whole point Finally I'm going to skip this one basically gamma max tells you the number of these degenerate cycles i.e. cycles that pass over a common node and for this particular graph it's going to be 2 and that's because you can see that 2 cycles 2 4 cycles are passing over this node 5 here and that's why this gamma is going to be 2 for this particular example Okay so enough rambling let's see the formula so first in line with the discussion about geodesic dispersion one expects the number of triangles to be related to positive curvature complete graph number of 4 cycles to 0 curvature grid and the remaining outgoing edges to negative curvature 3 Our new curvature formulation reflects such an intuition and here is finally the formula so you can see the Ricci curvature to the balance form on curvature implementation of the Ricci curvature has this very very like detailed shape and so I'm not going to explain every single detail but you can understand basically that it sums You can see here we have a sum of triangles which is going to contribute to the positive value of this curvature and everything is normalized by the degrees of nodes i and j and a fun property that emerges from this is because we have this minus 2 is that the curvature is always going to be bigger than minus 2 So that's and I think it's also upper bounded because of the normalization by one but don't quote me on that one okay cool so now let's see a couple of very interesting theorems that are going to connect the this this negative curvature the curvature calculation with the over squashing So because of this theorem that the Olivier curvature is lower bounded by this balanced form on the curvature because of that there is a very interesting corollary that's very interesting for this paper and the corollary says the following thing if our curvature is positive For any edge i j and I'm really sure that you should state all here because you need to have this condition satisfied for every single edge which is a very strong condition but if you have that then there exists a polynomial P such that So that the B set of this of this node i so the the R hop receptive field is going to be upper bounded by a polynomial in R and that's super important because we just saw before that if we have for example like a binary tree type of branching then we're going to have exponentially growing receptive field Whereas here if the edges are positive we can have a guarantee that they are bounded by a polynomial and here we for the first time see the connection between over squashing and curvature so there is a notion that if your graph is positively curved then because of this polynomial thingy indirectly you're going to have less over squashing because you're going to have less bottlenecks and less over squashing Okay now let's take that one step forward and find an explicit connection between curvature on one hand side and over squashing on the other side and that's what this theorem for is all about so this is going to be probably the the the main the main contribution of the paper and let me start and dissect this theorem for you There is a huge proof in the appendix you can go and check it out if you're into math but like this is going to give you a rough intuitive understanding of what's going on here and why this works so consider a MPN so a message passing neural network so the one we saw in equation one that's the generic MPN Let I be connected with J and the degree of node I is smaller or equal than DJ and then assume two conditions so the first condition assumes that you can basically upper bound the gradient of the update function and the gradient of the psi function of the message function for any layer for any L between 0 and capital L minus 1 which is L is the number of layers in our MPN With the depth being at least two layers then they say in two there exists Delta such that Delta is bounded like this and bounded like this so this is the this gamma coefficient we saw a couple minutes ago and we have that the curvature is upper bounding by upper bounded by minus two plus Delta Okay so this is so far very like maybe not not that clear I'm going to give you the gist in a second so then there exists this set Q sub J which is a subset of S to set of five satisfying that the size of that set is bigger than one over Delta blah blah and for all of these L zeros between zero and capital L minus two we have this equation here Okay so what this tells us here is that if we sum over elements of that of that subset Q of S2 and if we if we basically sum up all of these sensitivities of various nodes K from that subset that's going to be upper bounded by this expression here so alpha beta raised to the power of two times Delta raised to the power of one over four so now let me let me try and visualize this and break it down so first of all we have node I here so let's say let's say we have node I here we have one hop neighborhood here and finally we have two hop neighborhood here so what this theorem states is that basically there exists a subset so this is S2 so this this thing here let me try and draw it this thing here is S2 and what they state is that there exists some subset of these nodes so let me just kind of take a subset such that if you were to sum so now take some nodes from from this subset and if we were to calculate their sensitivities they're going to be upper bounded by this expression here so you can also read this as over squashing so over squashing of that over squashing of that neighborhood so the I'm going to denote that as like over squashing OS for example yeah and now what you can see is that if the edge is very negative so if Delta goes down to zero if you start in the limit when Delta goes to zero this edge IJ is going to be very negative because it's going to be upper bounded by minus two plus a small number which means it's going to converge almost to minus two which is super negative edge if that happens that means that this expression here so Delta goes to zero here and that means that you can see this becomes the whole expression goes to zero and that means we have over squashing so again the the the chain of thoughts here is the following if we have negative edges that means that we directly have over squashing problem and that's the direct connection they made there is a lot of details which follow from many other theories there is a lot of math in the in the appendix but this is a roughly what they're they're saying I'm going to make one more connection here with this chigar constant which is very interesting constant in in graph theory and then I'm going to show you the final algorithm the rewiring algorithm they applied in this paper so back to chigar constant so chigar constant intuitively captures the notion of of how bottlenecked the the graph is so if I were to draw a simple graph like this so let's imagine we have some some some nodes inside of here which are densely connected and then we have another community of nodes which are densely connected and if we have a single edge here you can see intuitively that this barbell shaped graph has a very high like it's very bottlenecked like there is a like a huge bottleneck and that's the one here okay and you'll see that this a H J so this chigar constant correlates with our intuition here very nicely because how we calculated and there is a mistake here so this should not be here I had a discussion with one of the main authors of the paper francesco he told me this is just a typo so basically you can see that we take the number of elements in this set so this set is as you can see here those are the edges such that I belongs to S and J belongs to its complement so in this particular example that will mean the following so we're going to so this is if this is S and this is basically the complement then this edge here is going to be a part of this set so this is the only edge that belongs to this set here and that means we have one here so very small number here and then we have like a minimum of volume so whatever the minimal volume between these two sets is we find that thing and that we divide it and the volume itself is divide as the sum across all of the notes of that set S and we just sum up their degrees so you can see here is going to be like some huge number and we have a small number and that means this is going to go towards zero for this edge case of a very bottlenecked graph and as we start adding and you can imagine if we start adding more edges if I were to start more edges here add more edges this thing is going to grow up so it's going to explode not explode but like it's going to have more and more elements and thus this chigger constant is going to consequently rise up from zero to some bigger number and thus it correlates in a way with how bottlenecked the graph is and now you can see a bunch of problems it's a single scaler what if we had much more communities what if we had like what if we had even more communities here and they are connected so it fails to to capture more interesting topologies but like it's it's a number that give you gives you some global it's a global statistics some gives you a global understanding what's going on in the graph but it's not that detailed and and and and yeah and you want so then they show the following thing and that's that the basically spec like spectral gap of a graph is bounded by the chigger constant and this spectral graph gap again correlates with this how connected the graph is and what this spectral gap is and they say here so lambda one is the first non zero eigenvalue of the normalized graph laplacian often referred to as the spectral gap so that's a nice connection between the spectral theory and and this graph theory i.e. the chigger constant but more interestingly for us they show that if the curvature is positive for all of the edges then you can you can basically like lower bound the chigger constant and that and also the the the spectral gap by this k which is the same k as we have here which means that by controlling the curvature how positive it is we can control the the the chigger constant i.e. how bottlenecked the graph is and the spectral gap of the graph so that's some some nice connections not necessary to understand this paper but like i made a small tangent here hopefully you can appreciate it okay so finally let's get to the to the meat of the of the paper i mean at least procedurally this is the final rewiring algorithm before going to the details let me just tell you what those are so they say here that more recently there is a trend to decouple the input graph from the graph used for information propagation so that's an important thing to notice such methods are often generically referred to as graph rewiring and we see here an example so here on the left we have a graph on the left hand side we have the original graph and we have some coloring depending on the curvature so again blue means we have negative edges red means we have positive edges blah blah blah but more importantly you can see that if we apply some some other baseline and this is called deagle method so this is called deagle which stands for diffusion improves graph learning we can see it completely changes the statistics of this particular graph it adds a lot of edges and thus completely skews the degree distributions etc etc on the other hand this thing here is their proposed method which we're going to see in a second and you can see it preserves the statistics but manages to basically makes the curvature of these of this graph higher okay now let's see how the actual thing works and yeah the important part to notice is that now instead of operating your your graph neural network on top of this original graph you instead what you do is you rewire the graph and then you use these edges to do your message passing on your graph so that's that's the that's the idea behind these rewiring methods they serve such like some type of pre-processing steps okay so here is the stochastic discrete richie flow algorithm which is super fancy name but it's a very cool algorithm so let's see what happens here so we have as input we have a graph G is given we have temperature tau which is a positive temperature which is because we are going to be sampling in this algorithm that's why we have that the notion of temperature we have max number of iterations and optional optional curvature upper bound called C plus we're going to see what that means in a second okay so the algorithm proceeds as follows so we're going to repeat the following steps until convergence or the max max number of iterations has been reached let me just draw a company graph that's going to help us grasp this a bit better so let's say we have two edges here let's say they are maybe a it's a bridge between some densely connected communities maybe something like this and let's see how now the graph operates so for edge i j with minimal richie curvature which is in this example going to be this one here so this is going to be our our like negative the most negative edge here then they say calculate vector x where the element of that vector x denoted as x sub k l and define like this is basically the improvement to the curvature of this edge i j from adding edge k l where k is belongs to the b one set of five and l belongs to the b one set of j okay so let me again just explain what it means that means we're going to make the following thing so let's um i'm going to try and add so we're going to try and add an edge so basically here maybe and this one you can see so this is node i this is node j you can see that i took a node from the b one set of i and i connected with with a with a node from b one set of j and now i see how how how much of an improvement does this have on on the curvature of this edge and that's this term here okay so we're basically going to do the same thing so we're going to do this multiple times and we're going to exhaustively connect this one with this one and and and this one with this one etc etc and we're going to calculate this improvement for all of those and then we're going to sample with probability uh basically softmax of that vector x and we use tau to modulate the temperature and we're going to sample from that vector and then add add the edge that was sampled to the graph so maybe one of these edges is going to be sampled maybe i don't know maybe this one is going to be chosen and uh basically that will be the end of step one you can imagine that if you push tau to like positive infinity to some big number big positive number then you're going to have instead of of this uh like a smooth distribution you're going to have like a deterministic distribution distribution where the edge that had the highest uh improvement is going to be chosen sampled and added to the graph so you can kind of use tau to uh tweak your your algorithm in that sense okay so we've added the edge and that that increased uh the positivity of this uh initial uh curved edge uh denoted in blue and the second step is remove edge with maximal uh rigid curvature only if that curvature is bigger than this c plus so that's the upper bound i mentioned and again you have some control here if you make c plus arbitrary like very very big then at one point of time uh that will mean that you'll never be removing positive edges and you'll just be adding uh these edges that increase the positivity of the of the graph okay so the reason why they have this part here is in order to preserve the statistics of the graph so as much as you add and thus increase the number of edges you want to also remove and thus kind of balance out uh the the the the the number of edges and the degree of nodes are going to be uh less skewed in this way in that way cool and you do this until convergence uh and whereas convergence means sometimes whatever combination of edges you add you'll never have the improvement here and thus that's that's how convergence is defined and that's that's it that's the that's the uh stochastic uh discrete root flow algorithm uh fairly simple idea uh if you think about it very very neat because it has this awesome connection with uh differential geometry but uh but yeah okay so finally they do compare um how strf works compared to deagle which is this competitive approach which works much better on homophilic uh graphs but i'm going to skip this math and theorems because it's a it's a arguably a tangent not uh not necessary to understand the core of this paper and so i'm going to skip that part um this time so here are the results you can see uh on various different um graph data sets uh core sites here pubmed might be familiar to most of you who have who have had any exposure to graph ml field uh you can see we have the homophilic coefficient associated with each of these graph data sets as denoted by this uh add h uh of j and you can see these ones have low h which means low homophilic which means high heterophilic and these ones are much more homophilic and again homophilic just means uh birds of feather flock together i.e. if you have a node and it's connected to its neighboring nodes there is a high uh chance that basically they'll share the same label whereas in heterophilic data sets oftentimes very distant nodes so some nodes which are uh yeah more distant from each other are going to have the same label i'm going to share the label and you can imagine for these heterophilic data sets it's very important to have effective strategy of communicating over those long distances and over squashing is one of the things that's going to uh ruin that communication and that's what this paper is handling basically and that's why it's better for heterophilic data sets compared to homophilic data sets uh the results support the claim you can see that for these heterophilic data sets it basically outperforms all of the other baselines we have deagle here we have this uh plus fa approach which is uh basically just fully a full um adjacency matrix uh in the last layer of our graph neural network a very simple modification that kind of tries to cope with over squashing effect as well uh and yeah as as i said better performance on these heterophilic data sets and you can see not as great although competitive performance on on these uh homophilic data sets deagle seems to perform somewhat better uh compared to to strf which is expected okay so uh finally just some distributions here they show that their rewiring method is much uh better at preserving various statistics so you can see here that comparing the degree distributions you can see that the the blue one is the original one uh the green one is the strf and deagle is the orange one and you can see it completely changes the the degree distributions for various different data sets and also you can see that uh the number of edges that deagle adds is huge whereas it does not remove edges and on the other hand strf both adds and removes edges and that's why it preserves the statistics of the graph finally i'm gonna uh end it up on this note uh they mentioned the limitation which is very something to think about uh so one limitation of our work is that the theoretical results presented here do not currently extend to multi graphs okay that's one thing because uh this whole like thing of calculating the number of triangles four cycles all of that breaks down uh in the case of multi graphs where you can have multiple edges between nodes and finally they say even more importantly that in addition the current methodology is agnostic to information beyond the graph topology such as node features so why is that important so imagine you have a graph where for example like a social media graph and that graph represents who is following whom and if you were to start and just um based on the curvature of the edges start rewiring that you're changing the underlying semantics of the social media graph and that can lead to false predictions later in your pipeline so because you're not taking features node features and net features into account you are less nuanced in how you change the semantics of the underlying graph if that makes sense okay so on that note um this is a very very cool paper i loved it and uh if you found the video useful yourself uh consider sharing the video um and subscribe to this channel and finally do join our discord community you'll check you can find the links down in the description until next time bye bye
[{"start": 0.0, "end": 6.66, "text": " What's up guys in this video I'm covering understanding over squashing and bottlenecks on graphs via curvature paper"}, {"start": 7.16, "end": 9.06, "text": " by Jake topping"}, {"start": 9.06, "end": 13.74, "text": " Francesco DiGiovanni Benjamin Tamboulin Xiao Wen Dong and Michael Bronstein"}, {"start": 14.02, "end": 21.26, "text": " So before we even start I guess it will only make sense for me to explain to you what over squashing"}, {"start": 21.900000000000002, "end": 26.86, "text": " Over squashing exactly means what our bottlenecks and finally what is curvature?"}, {"start": 26.86, "end": 32.28, "text": " So let's see this sentence in in the abstract that connects these these concepts"}, {"start": 32.28, "end": 35.34, "text": " And then I'm gonna give you an explanation of what those exactly are"}, {"start": 35.54, "end": 43.1, "text": " So we provide a precise description of the over squashing phenomena in graph neural networks and analyze how it arises from"}, {"start": 43.3, "end": 49.08, "text": " bottlenecks in the graph for this purpose we introduce a new edge based combinatorial"}, {"start": 49.6, "end": 55.56, "text": " Curvature and prove that negatively curved edges are responsible for the over squashing issue"}, {"start": 55.56, "end": 59.260000000000005, "text": " So negatively curved edges whatever that means I'm gonna explain that briefly"}, {"start": 59.980000000000004, "end": 63.78, "text": " Are responsible for the over squashing issue, okay?"}, {"start": 64.62, "end": 67.46000000000001, "text": " So let me first start with the preliminaries"}, {"start": 67.46000000000001, "end": 72.56, "text": " So let's first see what this bottleneck thing is in graph neural networks"}, {"start": 72.56, "end": 76.9, "text": " And what over squashing is which is a very connected phenomena"}, {"start": 77.18, "end": 81.86, "text": " So you may be familiar with the RNN so recurrent neural networks"}, {"start": 81.86, "end": 87.58, "text": " And you may know that we have this squashing phenomenon occurring in RNN as well, so"}, {"start": 88.38, "end": 92.26, "text": " So this is just a rolled out version of an RNN model"}, {"start": 92.26, "end": 97.06, "text": " And you can see that so some information some input is fed into the RNN here"}, {"start": 97.06, "end": 102.92, "text": " And then this information is passed on to the next step here where we have another piece of information"}, {"start": 103.3, "end": 107.36, "text": " Mixing together with this previous step and then in the third step"}, {"start": 107.36, "end": 115.5, "text": " We'll be having this additional information mixing with the information from the previous two steps and so as you can imagine so already here"}, {"start": 115.62, "end": 119.74, "text": " the like the this this information from from the first step"}, {"start": 120.42, "end": 128.02, "text": " Constitutes only like maybe roughly one-third of the informational content that you can be they can be find found in this particular"}, {"start": 128.57999999999998, "end": 135.74, "text": " Time step of RNN and so the more we go towards right the this this information from this step"}, {"start": 135.74, "end": 141.26000000000002, "text": " constitutes a minor and minor percentage of the informational content of that fixed size vector and"}, {"start": 142.3, "end": 147.54000000000002, "text": " Basically, that's what bottleneck is all about so as you can see here because we have this"}, {"start": 148.54000000000002, "end": 153.62, "text": " Bottleneck where all of these informations have to pass and be squeezed inside of this fixed size vector"}, {"start": 154.26000000000002, "end": 160.52, "text": " So that bottleneck causes the over squashing of information, so that's how these two concepts are related"}, {"start": 160.52, "end": 167.96, "text": " Okay, so we know that RNNs were susceptible to this particular problem, and we know the later some models such as LSTM or GRU's"}, {"start": 169.08, "end": 170.72, "text": " managed to"}, {"start": 170.72, "end": 171.92000000000002, "text": " basically"}, {"start": 171.92000000000002, "end": 177.52, "text": " focus on on some parts of the information more on some parts of the information less and"}, {"start": 178.04000000000002, "end": 183.76000000000002, "text": " Thus they managed to you know in a way avoid this bottleneck problem, but not completely"}, {"start": 183.76, "end": 191.07999999999998, "text": " Well with graph neural networks the problem is even more severe and the reason can be seen in this example here"}, {"start": 191.07999999999998, "end": 192.92, "text": " So you can see that"}, {"start": 192.92, "end": 195.56, "text": " like compared to RNNs we have"}, {"start": 196.07999999999998, "end": 198.07999999999998, "text": " exponentially more"}, {"start": 198.23999999999998, "end": 205.18, "text": " Informational vectors coming in in every single step so because of how the spatial GNNs work, and that's by basically aggregating"}, {"start": 205.84, "end": 210.23999999999998, "text": " One hop neighborhood. That's how usually GNNs are implemented"}, {"start": 210.24, "end": 215.92000000000002, "text": " So because of that if you had a graph such as maybe let me just draw some examples"}, {"start": 215.92000000000002, "end": 221.92000000000002, "text": " So if you have a graph like this where this node is connected to two more nodes, and then these two nodes are connected to two"}, {"start": 221.92000000000002, "end": 223.52, "text": " more nodes"}, {"start": 223.52, "end": 230.28, "text": " So like this so then if you were to start calculating features for this one so in the first step you'd be including"}, {"start": 230.44, "end": 234.48000000000002, "text": " So let me just draw this so you'd include information from these two and"}, {"start": 235.08, "end": 238.96, "text": " These two would include information from these two which means that information"}, {"start": 238.96, "end": 245.16, "text": " from this vector here from this node here will in the first step propagate here"}, {"start": 245.16, "end": 251.64000000000001, "text": " And then in the second step it will propagate all the way here, and that's what we can see visually on this graph exactly so"}, {"start": 252.68, "end": 254.12, "text": " basically for"}, {"start": 254.12, "end": 258.84000000000003, "text": " Topology such as this one where we have with every where every node will have two additional neighbors"}, {"start": 259.36, "end": 262.96000000000004, "text": " Will basically have exponential grow growth of"}, {"start": 262.96, "end": 270.59999999999997, "text": " Information content that we need to squeeze in ultimately into into a fixed size representation of this particular node here"}, {"start": 270.79999999999995, "end": 274.68, "text": " So that's the that's the bottleneck and over squashing problem"}, {"start": 275.12, "end": 282.71999999999997, "text": " And it's as you can see intimately related to the topology of a particular graph you're dealing with okay"}, {"start": 283.67999999999995, "end": 289.67999999999995, "text": " Next up second concept that I want to explain before we start analyzing the paper, and that's the curvature so"}, {"start": 290.24, "end": 292.24, "text": " Let me read this this"}, {"start": 292.24, "end": 298.32, "text": " Statement here so richie curvature of a manifold can be characterized by geodesic dispersion"}, {"start": 298.32, "end": 303.78000000000003, "text": " I whether two parallel geodesics shot from nearby points converge"}, {"start": 304.04, "end": 309.56, "text": " Which happens in a positively curved spaces locally resembling a sphere such as this example here"}, {"start": 309.56, "end": 314.44, "text": " Or they remain parallel in the flat or Euclidean case as you can see here"}, {"start": 314.44, "end": 319.16, "text": " Or they diverge negative curvature giving rise to hyperbolic geometry"}, {"start": 319.16, "end": 324.96000000000004, "text": " So most of you are probably just familiar with Euclidean geometry, but like back in I think 19th century already"}, {"start": 325.68, "end": 327.68, "text": " people such as Riemann and"}, {"start": 328.28000000000003, "end": 331.68, "text": " And others started devising these other types of geometry"}, {"start": 331.68, "end": 338.0, "text": " So you can see here that if you were to shot like two parallel lines so two geodesics where geodesic is just a fancy name"}, {"start": 338.0, "end": 341.96000000000004, "text": " Of saying like basically the shortest path on a particular geometry"}, {"start": 342.16, "end": 346.3, "text": " Which in the case of a Euclidean plane will be like like a straight line"}, {"start": 346.3, "end": 351.18, "text": " But in the case of like sphere or hyperbolic type of surfaces"}, {"start": 351.38, "end": 354.86, "text": " It's not going to be a straight line, so you can see here if you shoot two"}, {"start": 355.22, "end": 359.78000000000003, "text": " Two geodesics they're going to ultimately converge here on the North Pole"}, {"start": 359.78000000000003, "end": 367.1, "text": " And that's why so when the lines convert when the geodesics converge that space is basically described as being"}, {"start": 367.82, "end": 369.26, "text": " positively curved"}, {"start": 369.26, "end": 374.62, "text": " Here you can see that these geodesics are gonna. Let me just take a pen here, so they are going to diverge"}, {"start": 374.62, "end": 379.98, "text": " So this is going to track this line here, and this geodesic is going to be tracking this line here"}, {"start": 379.98, "end": 385.78000000000003, "text": " So you can see they are diverging and because of that this hyperbolic space has negative curvature, okay?"}, {"start": 385.94, "end": 391.42, "text": " So this is also so this Ricci curvature basically is a scalar that tells you whether the space is"}, {"start": 391.66, "end": 398.46, "text": " Positively curved in the case of a sphere or zero or negatively curved in the case of this particular"}, {"start": 399.14, "end": 400.78000000000003, "text": " geometric object here"}, {"start": 400.78, "end": 407.38, "text": " Okay, so aside from the Ricci curvature. We need to know a couple more concepts and the main one will be Ricci flow"}, {"start": 407.94, "end": 412.38, "text": " Which basically tells you the rate of change of a metric tensor?"}, {"start": 412.97999999999996, "end": 420.21999999999997, "text": " Is directly proportional to the Ricci curvature now that may seem and sound very complex because it probably is"}, {"start": 420.26, "end": 425.44, "text": " But I want to show you a short video that's going to give you like all the necessary intuition that you need to have"}, {"start": 426.05999999999995, "end": 428.26, "text": " before proceeding with this paper, so"}, {"start": 428.26, "end": 432.98, "text": " Just as a trivia. I want to mention a couple of people here, so this guy here called"}, {"start": 433.7, "end": 435.7, "text": " Gregorio Ricci Curbastro"}, {"start": 436.42, "end": 443.21999999999997, "text": " Was the guy who invented the Ricci curvature and after whom the Ricci curvature was named. This is Hamilton who"}, {"start": 443.86, "end": 445.86, "text": " discovered the Ricci flow"}, {"start": 447.06, "end": 453.06, "text": " Equation and finally this is Gregory Perelman a guy who managed to solve the famous Millennium"}, {"start": 453.62, "end": 456.42, "text": " problem in mathematics called the Poincare"}, {"start": 456.42, "end": 461.86, "text": " Conjecture and he solved it using basically building on top of Hamilton's work"}, {"start": 462.34000000000003, "end": 468.18, "text": " And he used Ricci flow to solve this Poincare conjecture also as a fun fact he decided to"}, {"start": 468.90000000000003, "end": 474.58000000000004, "text": " Basically decline both the Fields Medal which is an equivalent of a Nobel prize in in"}, {"start": 475.14, "end": 480.66, "text": " Mathematics as well as the Millennium prize like a one million dollar prize for solving one of these seven"}, {"start": 481.22, "end": 484.58000000000004, "text": " Millennium problems as proposed by the Clay Institute"}, {"start": 484.58, "end": 487.7, "text": " So Poincare Conjecture was one of those those. Okay, so"}, {"start": 488.41999999999996, "end": 495.14, "text": " Now check out this video where you'll understand what Ricci flow is a lobar and then we'll continue"}, {"start": 500.18, "end": 506.02, "text": " Ricci flow is a way of changing the metric tensor over time so that the manifold becomes rounder"}, {"start": 507.7, "end": 510.02, "text": " So how do we express Ricci flow concretely?"}, {"start": 510.02, "end": 515.78, "text": " I want you to focus on this region over here the Ricci flow inflates it like a balloon"}, {"start": 516.74, "end": 520.26, "text": " By convention, we say that it has negative Ricci curvature"}, {"start": 520.9, "end": 525.06, "text": " So if the curvature is negative the length increases"}, {"start": 526.5, "end": 528.5, "text": " Now focus on this region here"}, {"start": 529.14, "end": 531.14, "text": " Ricci flow deflates it"}, {"start": 531.78, "end": 535.62, "text": " So if the Ricci curvature is positive the length decreases"}, {"start": 535.62, "end": 539.14, "text": " If the Ricci curvature is positive the length decreases"}, {"start": 541.0600000000001, "end": 546.58, "text": " We can phrase this differently g decreases means the derivative of g is negative"}, {"start": 547.62, "end": 551.62, "text": " g increases just means the derivative of g is positive"}, {"start": 552.66, "end": 554.98, "text": " These two guys always have opposite sides"}, {"start": 555.62, "end": 557.62, "text": " So we might guess an equation like this"}, {"start": 558.58, "end": 560.02, "text": " And that's it"}, {"start": 560.02, "end": 562.98, "text": " That is the equation describing Ricci flow. Okay, cool"}, {"start": 562.98, "end": 568.26, "text": " So I strongly suggest you go ahead and watch the whole video as it's super informative"}, {"start": 568.5, "end": 573.14, "text": " And but this this clip I just showed you is enough for you to understand the paper so we can continue"}, {"start": 573.62, "end": 580.9, "text": " Cool. So as you just saw, we have Ricci flow is basically this differential equation connecting metric tensor with Ricci curvature"}, {"start": 581.38, "end": 584.98, "text": " And you can see so in the example of a body you can see here on the screen"}, {"start": 585.3000000000001, "end": 590.9, "text": " We have that this we see that this part has very negative curvature, which is denoted by this blue color"}, {"start": 590.9, "end": 595.4599999999999, "text": " And by by by applying Ricci flow because of the negative"}, {"start": 596.66, "end": 600.02, "text": " Like negative value of the curvature that part is going to be inflated"}, {"start": 600.26, "end": 604.8199999999999, "text": " Whereas this part which which has uh, like positive curvature is going to be deflated"}, {"start": 605.22, "end": 607.54, "text": " Basically, and we end up with something like this"}, {"start": 607.6999999999999, "end": 613.06, "text": " So we can see that Ricci flow in this continue on this continuous manifold can reduce these bottlenecks"}, {"start": 613.22, "end": 616.5, "text": " And now let's just translate this idea onto the discrete case"}, {"start": 616.5, "end": 621.54, "text": " Which are the graphs and we can see that intuitively what happens is is a similar thing"}, {"start": 621.62, "end": 625.54, "text": " So we can see we have a bottleneck here. So let me just change the color"}, {"start": 625.86, "end": 633.54, "text": " So we see a bottleneck here, which is denoted again by a blue edge and by inflating that space by adding"}, {"start": 633.94, "end": 639.62, "text": " Edges here, uh, basically we are making this part of the space more positive and we are also"}, {"start": 640.26, "end": 642.5, "text": " They are also removing some of the edges here"}, {"start": 642.5, "end": 647.38, "text": " Which means we'll have less edges here and then the statistics of the graph stays roughly the same"}, {"start": 648.18, "end": 651.54, "text": " But like we reduce bottleneck and you can see that the colors are"}, {"start": 652.16, "end": 657.3, "text": " Homogenized meaning that this became more reddish and this part that was super red now became"}, {"start": 658.34, "end": 660.34, "text": " Also has some blue"}, {"start": 660.42, "end": 664.82, "text": " Colors to it. So that's that's what we we managed to accomplish a similar thing to this"}, {"start": 665.38, "end": 667.86, "text": " Analogous thing to this what happened in the continuous space"}, {"start": 668.74, "end": 670.26, "text": " uh, cool"}, {"start": 670.26, "end": 675.22, "text": " So now let me just show you some preliminaries and then we'll we'll we'll uh,"}, {"start": 675.3, "end": 681.62, "text": " See how they formalize the notion of over squashing and then we'll see how they formalize the notion of negative curvature on graphs"}, {"start": 681.78, "end": 689.38, "text": " And finally how they connect the two so that they can devise an algorithm where they'll be picking these negative edges and rewiring the graph to get"}, {"start": 689.54, "end": 692.02, "text": " Uh, uh less problems with over squashing"}, {"start": 693.22, "end": 694.5, "text": " so, um"}, {"start": 694.5, "end": 698.74, "text": " Let's see some piece of notation here first this s sub r of i"}, {"start": 698.74, "end": 701.86, "text": " Is basically the the the neighborhood"}, {"start": 702.34, "end": 708.9, "text": " So it's a set of these j's of nodes j's that belong to the set of all nodes denoted as v"}, {"start": 709.54, "end": 714.66, "text": " That have this geodesic distance between i and j that's precisely equal to r"}, {"start": 715.14, "end": 722.9, "text": " So it's a fancy way of saying this is a set of nodes j which are exactly r hops away from node i"}, {"start": 723.46, "end": 724.66, "text": " okay"}, {"start": 724.66, "end": 732.5, "text": " Uh, and then this b sub r of i is the same thing but here we have like a smaller or equal"}, {"start": 732.74, "end": 735.62, "text": " Which means we'll be including all of the intermediate"}, {"start": 736.26, "end": 741.86, "text": " Intermediate nodes and thus this is uh, like a receptive field of this particular, uh node"}, {"start": 742.26, "end": 745.86, "text": " Okay, just to visualize the notation. It's going to be probably a bit easier"}, {"start": 746.02, "end": 750.26, "text": " so if this node 2 here is our node i then the"}, {"start": 750.26, "end": 755.86, "text": " The s1 neighborhood of i is basically nodes 3 and nodes 1"}, {"start": 756.26, "end": 758.9, "text": " Uh, then the the the s2 neighborhood"}, {"start": 758.98, "end": 764.58, "text": " So if we were to draw s2 neighborhood of i that's going to be nodes 0 and 4"}, {"start": 764.8199999999999, "end": 769.06, "text": " As you can see we need exactly the shortest path takes two"}, {"start": 769.86, "end": 772.5, "text": " Edges to get to node 0 and the same for node 4"}, {"start": 773.38, "end": 776.74, "text": " Finally the the b neighborhood. So let's say we have"}, {"start": 776.74, "end": 779.54, "text": " uh neighborhood b2 of i"}, {"start": 780.58, "end": 785.54, "text": " Is going to encompass all of these nodes we saw so that's going to be b2"}, {"start": 786.02, "end": 791.46, "text": " And let me just check whether I think it also includes. Yeah, it also includes node 2 as well"}, {"start": 791.54, "end": 796.9, "text": " So this every all of these nodes are now going to be b2 neighborhood of i and just an additional detail"}, {"start": 797.14, "end": 801.7, "text": " I assume b stands for ball and s stands for surface which makes intuitive sense"}, {"start": 801.78, "end": 805.14, "text": " As you can see here, we can include the whole volume all of these nodes"}, {"start": 805.14, "end": 809.62, "text": " Whereas in s we just take the front so we basically ignore all all of these"}, {"start": 810.18, "end": 813.06, "text": " inner nodes inside of the s sets"}, {"start": 814.34, "end": 816.02, "text": " cool, so"}, {"start": 816.02, "end": 818.02, "text": " next up, uh just a"}, {"start": 818.26, "end": 822.9, "text": " Short mention of message passing neural networks and if you're not familiar with graph neural networks"}, {"start": 822.9, "end": 827.38, "text": " I have a whole playlist i'm going to link it somewhere here. You can check it out. I'm going to just briefly"}, {"start": 828.1, "end": 830.1, "text": " Recap what this is all about"}, {"start": 830.1, "end": 836.9, "text": " And you can see that in order to calculate the features of a node i, uh in layer l plus one"}, {"start": 837.5400000000001, "end": 840.98, "text": " What we do is the following so we take the previous"}, {"start": 841.38, "end": 847.22, "text": " Feature of that node i so in the previous layer a layer l and we basically combine it"}, {"start": 847.3000000000001, "end": 854.58, "text": " So maybe concatenation with this expression here and then we we apply this function. That's called the update function phi"}, {"start": 854.82, "end": 857.72, "text": " Okay, so let me just now decouple"}, {"start": 857.72, "end": 861.0, "text": " What this term is all about so you can see we have a"}, {"start": 861.72, "end": 864.28, "text": " Some j goes from one to two n"}, {"start": 864.6800000000001, "end": 868.84, "text": " Which is basically n is the the cardinality of the node set"}, {"start": 868.84, "end": 872.2, "text": " So that means there's a fancy way of saying it's the number of nodes in your graph"}, {"start": 873.1600000000001, "end": 877.48, "text": " A hat ij is basically your adjacency matrix"}, {"start": 877.48, "end": 880.12, "text": " So the connectivity matrix, but this is with additional twist"}, {"start": 880.12, "end": 886.52, "text": " They added self edges and that means basically every node will have additionally"}, {"start": 886.52, "end": 888.52, "text": " uh implied edge like this"}, {"start": 889.0, "end": 894.84, "text": " Although if it's undirected it's going to be uh, like both directions basically so every node will have this self edge"}, {"start": 894.84, "end": 900.52, "text": " And plus they also have normalization using these d matrices, which are basically your"}, {"start": 901.24, "end": 908.76, "text": " um, well, yeah degree matrices and this just normalizes the adjacency the augmented adjacency matrix a tilde"}, {"start": 909.96, "end": 915.16, "text": " So what this will effectively do is filter out so this is going to be"}, {"start": 915.16, "end": 925.3199999999999, "text": " Um non-zero only for immediate nodes of node i so that means we're just going to look at the one hop neighborhood of node i and"}, {"start": 926.04, "end": 929.8, "text": " Otherwise this will be zero and thus we won't care about this thing"}, {"start": 929.8, "end": 937.8, "text": " Uh, whereas this is just your message passing function psi and these are the representations of node i and its neighbors node j"}, {"start": 937.8, "end": 939.8, "text": " Uh, so"}, {"start": 939.8, "end": 941.9599999999999, "text": " Let me just show you a diagram to make it a bit"}, {"start": 941.96, "end": 950.0400000000001, "text": " Uh easier so that means we're going to take a look at the one hop neighbors of node h of node 1"}, {"start": 950.0400000000001, "end": 956.6800000000001, "text": " And we're going to aggregate somehow combine this feature with this feature using some uh function psi"}, {"start": 956.6800000000001, "end": 959.72, "text": " Which is usually like mlp like a multilayer perception"}, {"start": 959.72, "end": 965.1600000000001, "text": " We're going to form representations in such a way which are called messages and then we're going to aggregate them"}, {"start": 965.1600000000001, "end": 970.6, "text": " Uh like this so in this particular case they they've chosen a particular"}, {"start": 970.6, "end": 981.4, "text": " Uh permutation invariant function i sum in this particular case but in general it can be uh whatever like whatever function that's that's permutation invariant like maybe"}, {"start": 981.4, "end": 991.72, "text": " Uh like average or or even a max function is permutation invariant and so people usually denote that you'll probably see that in the literature as like o plus"}, {"start": 991.72, "end": 997.4, "text": " Uh which is a general a generic permutation invariant operator instead of using sum"}, {"start": 997.4, "end": 1006.76, "text": " So that's some uh preliminaries uh the notation and uh and uh these generic message passing neural networks"}, {"start": 1006.76, "end": 1011.24, "text": " And now let me show you how they formalize the concept of over squashing"}, {"start": 1011.24, "end": 1019.4, "text": " Uh but before that why do we care like well the reason we care is because as we saw as soon as we have long dependencies"}, {"start": 1019.4, "end": 1025.96, "text": " The information is going to be over squashed and thus the two remote nodes cannot communicate effectively with each other"}, {"start": 1025.96, "end": 1039.48, "text": " And so they say here we say that a graph learning problem has long range dependencies when the output of a mpn n depends on representations of distant nodes interacting with each other"}, {"start": 1039.48, "end": 1046.28, "text": " And so in these types of graphs where which are called heterophilic uh as compared to homophilic"}, {"start": 1046.28, "end": 1052.3600000000001, "text": " Uh you basically want to have this uh remote communication going on if you want to have accurate predictions"}, {"start": 1052.36, "end": 1059.8, "text": " And so that's why we need to solve the over squashing problem if we are to be performant on these heterophilic types of graphs"}, {"start": 1059.8, "end": 1063.8, "text": " So let me show you how they formalize this this notion of over squashing"}, {"start": 1063.8, "end": 1070.36, "text": " Okay let's first uh let me show you the the notation here before I start parsing the equation uh the inequality"}, {"start": 1070.36, "end": 1079.8799999999999, "text": " So what they have is the following so they have nodes i and s from the set of nodes v such that s belongs to the set s sub r plus one of i"}, {"start": 1079.88, "end": 1087.48, "text": " Which means uh s is r plus one uh hops away from node i so that's something like this maybe we have a node i here"}, {"start": 1088.5200000000002, "end": 1094.44, "text": " And then we have a bunch of nodes here bunch of nodes and then somewhere here we have node s"}, {"start": 1095.0, "end": 1103.24, "text": " And this shortest path to get from from uh basically i to s is equal to r plus one"}, {"start": 1103.24, "end": 1113.32, "text": " So let me just draw that so that's r plus one length okay so we have node s here and node i here and um basically then they say if the"}, {"start": 1113.32, "end": 1121.96, "text": " If you can bound the gradient of the phi and psi functions which are the message and uh and update functions"}, {"start": 1122.6, "end": 1132.36, "text": " Basically if you can bound them by some some some scalars alpha and beta uh then uh they show that this here this expression here holds"}, {"start": 1132.36, "end": 1140.28, "text": " And this what this tells us is the following so the sensitivity of this representation of node i in layer r plus one"}, {"start": 1141.0, "end": 1149.3999999999999, "text": " Uh and sensitivity with respect to uh node s so to the raw features of node s is upper bounded"}, {"start": 1149.3999999999999, "end": 1155.3999999999999, "text": " So we take the absolute value of this of this uh derivative here and we can see it's bounded by alpha beta"}, {"start": 1155.4, "end": 1164.2800000000002, "text": " Raise to the power of r plus one times a hat raised to the power of r plus one and then we just take the uh index by i and s"}, {"start": 1164.2800000000002, "end": 1171.4, "text": " Okay so there is a couple of things worth mentioning here first of all if you're not familiar with taking powers of these adjacency matrices"}, {"start": 1172.0400000000002, "end": 1180.52, "text": " There is a special semantics behind uh a raised to the power r plus one namely if you index this matrix here with i s"}, {"start": 1180.52, "end": 1188.12, "text": " You'll get the number of shortest paths between i nodes i and nodes s which makes intuitive sense"}, {"start": 1188.12, "end": 1195.48, "text": " So basically the more such paths we had that means that s so the features from from from the information from node s"}, {"start": 1195.48, "end": 1204.92, "text": " Had multiple paths by which they could reach node i and thus you can intuitively understand that that means that this upper bound is going to become bigger"}, {"start": 1204.92, "end": 1211.8000000000002, "text": " Because the end the over squashing will will be uh like uh less um prominent"}, {"start": 1211.8000000000002, "end": 1221.88, "text": " That's observation number one observation number two here is the following so you do have to have uh you do have to to observe the representation of node i"}, {"start": 1221.88, "end": 1230.76, "text": " Uh only uh after applying r plus one uh layers of of your graph neural network the reason is underreaching"}, {"start": 1230.76, "end": 1240.52, "text": " If you were to just apply let's say if like less than r plus one then this information from node s would have not reached node i yet"}, {"start": 1240.52, "end": 1250.12, "text": " So that means maybe the information from from this node s only have reached until here and that means that this is going to be uh zero"}, {"start": 1250.12, "end": 1257.48, "text": " Because like there is no influence of hs of the of the raw vector of node s uh on the representation"}, {"start": 1257.48, "end": 1262.52, "text": " Because the information still hasn't propagated to node i so that's something to keep in mind"}, {"start": 1262.52, "end": 1271.48, "text": " So that means that here you have to have r plus one because then you're basically calculating non-zero sensitivity of node i"}, {"start": 1271.48, "end": 1278.76, "text": " And how the information from s influences node i so i think that's that's pretty much everything you need to understand about about this formula"}, {"start": 1278.76, "end": 1288.04, "text": " So it's a nice way of connecting over smoothing on one hand with topological uh topology of your graph on the other hand okay"}, {"start": 1288.04, "end": 1299.8, "text": " So as an example they show here for example if the uh shortest path between i and s is r plus one and the sub graph induced on on this uh b set is a binary tree"}, {"start": 1299.8, "end": 1309.72, "text": " Uh then this adjacency matrix uh like indexed at is is going to have this particular shape and what's interesting here is that as r grows"}, {"start": 1309.72, "end": 1315.96, "text": " Which means as you're looking at at further away nodes you're going to have exponential decrease of this term"}, {"start": 1315.96, "end": 1324.2, "text": " Which means in turn that you're going to have small this will be exponentially decreasing and thus the sensitivity will be exponentially decreasing"}, {"start": 1324.2, "end": 1327.3999999999999, "text": " Which means that the over squashing will become more and more prominent"}, {"start": 1327.4, "end": 1338.6000000000001, "text": " Okay now let's continue so let me show you now how they formalize how they calculate the curvature of a graph that may be unintuitive to some of you"}, {"start": 1338.6000000000001, "end": 1341.8000000000002, "text": " As well as to me on the first pass of reading this paper"}, {"start": 1342.6000000000001, "end": 1348.8400000000001, "text": " Okay so we saw how the how these curved spaces look like when they are continuous"}, {"start": 1348.8400000000001, "end": 1353.48, "text": " Now let's see how this thing works for discrete case i.e. for graphs"}, {"start": 1353.48, "end": 1367.48, "text": " So intuitively the the notion is the following so if you take these two nodes p and q and you take two edges you'll see that in graphs such as this one"}, {"start": 1367.48, "end": 1379.48, "text": " They'll tend to converge to this node k and thus form a triangle and basically triangles will be a feature that indicates that the space is positively curved in graphs"}, {"start": 1379.48, "end": 1393.48, "text": " On the other hand if you take two edges and they stay on the same distance then and they form four cycles by doing so then this space is going to be classified as having zero curvature"}, {"start": 1393.48, "end": 1401.48, "text": " And finally if we have edges that start diverging then in that case the space is negative"}, {"start": 1401.48, "end": 1415.48, "text": " Now this is kind of hand wavy because unless you attach geometric like information to these edges like the fact we just chosen to draw the graph like this doesn't mean anything"}, {"start": 1415.48, "end": 1427.48, "text": " But like you can imagine that also like you can see here that the path between this node and this node starts becoming larger and larger whereas here it's like zero and here it stays constant"}, {"start": 1427.48, "end": 1435.48, "text": " So that's maybe a better way to think about this but like just visually as well you can see that these two kind of converge these two stay parallel and these two diverge"}, {"start": 1435.48, "end": 1439.48, "text": " This is probably yeah probably better to explain it like this"}, {"start": 1439.48, "end": 1451.48, "text": " Okay so now intuitively what this curvature calculation needs to do is count these topological elements and by counting them decide on the actual curvature of an edge"}, {"start": 1451.48, "end": 1455.48, "text": " So let's see how they choose to do that"}, {"start": 1455.48, "end": 1470.48, "text": " So first worth mentioning there are two discrete variants of calculating rigid curvature for graphs one is known as the Olivier curvature denoted as this italic weird font K symbol"}, {"start": 1470.48, "end": 1476.48, "text": " And we also have this from a Foreman curvature denoted as big F here"}, {"start": 1476.48, "end": 1492.48, "text": " So there are trade-offs between these two curvature Olivier is much more expressive but much more computationally expensive Foreman has the opposite properties basically it's much more efficient computationally but it's not as expressive as Olivier's curvature"}, {"start": 1492.48, "end": 1501.48, "text": " What they've done is they've taken the Foreman curvature and they've upgraded it to this balanced Foreman curvature"}, {"start": 1501.48, "end": 1509.48, "text": " And in order to understand the equation let me first break down a couple of sets we'll need to take care about"}, {"start": 1509.48, "end": 1517.48, "text": " So the first set is this one which basically tells you the number of triangles that are formed on this edge ij"}, {"start": 1517.48, "end": 1525.48, "text": " And you can formally basically calculate that by finding an intersection between S1 sets of node i and node j"}, {"start": 1525.48, "end": 1529.48, "text": " So these are the triangles that are based at the edge ij"}, {"start": 1529.48, "end": 1535.48, "text": " So let me show you an example so if we have here this particular graph and let me just"}, {"start": 1535.48, "end": 1549.48, "text": " Okay so basically this is node i here and this is node j we find the S1 sets first so for node i so S1 of i is going to be this"}, {"start": 1549.48, "end": 1558.48, "text": " It's going to be this element here because you can see the distance is just one this one this one and this one as well as j so this is the S1 set"}, {"start": 1558.48, "end": 1567.48, "text": " On the other hand if we want to calculate S1 set for j that's going to be 5, 6 and 0"}, {"start": 1567.48, "end": 1577.48, "text": " And what they do is they find an intersection and you can see that the only intersection we have in this particular example is node 6"}, {"start": 1577.48, "end": 1584.48, "text": " So this one here and as you can see it does form a triangle and that's the only triangle we have in this particular graph"}, {"start": 1584.48, "end": 1590.48, "text": " So that's the first thing we need to care about triangles the second thing we need to care about is these four cycles"}, {"start": 1590.48, "end": 1604.48, "text": " And you can see here a formulaic description i'm going to just read you what it represents and that's that these are the neighbors of i forming a four cycle based at the edge ij without the diagonals inside"}, {"start": 1604.48, "end": 1619.48, "text": " Okay so basically let me again show you this for node i the four cycles are going to be so that those are going to be 2 and 3 because you can see here we have a four cycle here going from i to j and then back"}, {"start": 1619.48, "end": 1627.48, "text": " So it's a four cycle we have a second four cycle going over 3 as you can see here going to j and backwards so those are four cycles"}, {"start": 1627.48, "end": 1643.48, "text": " And you may wonder why have I excluded 4 from this set and the reason is because we have this diagonal here and that's why we will not include node 4 into this set of four cycles of node i"}, {"start": 1643.48, "end": 1659.48, "text": " Okay now let me try and connect that with the formula just for fun so you can see here what the formula states and let's check whether this why the node 4 basically will not belong to a set"}, {"start": 1659.48, "end": 1676.48, "text": " So we can see that this set of four cycles for node i is a set of these k's such that k is basically belongs to S1 set of node i but does not belong to S1 set of j neither can k be equal to j"}, {"start": 1676.48, "end": 1695.48, "text": " Okay let me now just delete this to make this clearer so let me delete everything here and let me basically show you how this is going to function so k belongs to S1 of i so that means k is one of these elements here okay"}, {"start": 1695.48, "end": 1712.48, "text": " It's going to be one of those elements here and then we exclude basically we exclude j which means we exclude this one and we also exclude everything that belongs to node S1 set of j so that means we're going to exclude this one as well"}, {"start": 1712.48, "end": 1728.48, "text": " So we end up with 2, 3 and 4 and we already saw that 2 and 3 do satisfy all of the conditions and thus we included those in this set but we for some reason we did not include number 4 and the reason is because of this other condition"}, {"start": 1728.48, "end": 1750.48, "text": " So that k needs to be such that there exists this node w that belongs so that means that this set here is non-zero not empty set so you can see that S1 of k so let's find S1 of k so k is 4 in our example so this is our k this is our potential candidate at this point of time"}, {"start": 1750.48, "end": 1762.48, "text": " So this is these are the S1 this is the S1 neighborhood of k and intersection with S1 of j is going to be just this node here so this is going to be the intersection"}, {"start": 1762.48, "end": 1780.48, "text": " But at the same time we need to find something that does not belong to S1 and because this thing belongs to S1 that's why we have to digit again and that's a very complicated way of telling you that hey if we have a diagonal here we cannot count in this 4 cycle that's the whole point"}, {"start": 1780.48, "end": 1805.48, "text": " Finally I'm going to skip this one basically gamma max tells you the number of these degenerate cycles i.e. cycles that pass over a common node and for this particular graph it's going to be 2 and that's because you can see that 2 cycles 2 4 cycles are passing over this node 5 here and that's why this gamma is going to be 2 for this particular example"}, {"start": 1805.48, "end": 1825.48, "text": " Okay so enough rambling let's see the formula so first in line with the discussion about geodesic dispersion one expects the number of triangles to be related to positive curvature complete graph number of 4 cycles to 0 curvature grid and the remaining outgoing edges to negative curvature 3"}, {"start": 1825.48, "end": 1848.48, "text": " Our new curvature formulation reflects such an intuition and here is finally the formula so you can see the Ricci curvature to the balance form on curvature implementation of the Ricci curvature has this very very like detailed shape and so I'm not going to explain every single detail but you can understand basically that it sums"}, {"start": 1848.48, "end": 1871.48, "text": " You can see here we have a sum of triangles which is going to contribute to the positive value of this curvature and everything is normalized by the degrees of nodes i and j and a fun property that emerges from this is because we have this minus 2 is that the curvature is always going to be bigger than minus 2"}, {"start": 1871.48, "end": 1890.48, "text": " So that's and I think it's also upper bounded because of the normalization by one but don't quote me on that one okay cool so now let's see a couple of very interesting theorems that are going to connect the this this negative curvature the curvature calculation with the over squashing"}, {"start": 1890.48, "end": 1912.48, "text": " So because of this theorem that the Olivier curvature is lower bounded by this balanced form on the curvature because of that there is a very interesting corollary that's very interesting for this paper and the corollary says the following thing if our curvature is positive"}, {"start": 1912.48, "end": 1928.48, "text": " For any edge i j and I'm really sure that you should state all here because you need to have this condition satisfied for every single edge which is a very strong condition but if you have that then there exists a polynomial P such that"}, {"start": 1928.48, "end": 1950.48, "text": " So that the B set of this of this node i so the the R hop receptive field is going to be upper bounded by a polynomial in R and that's super important because we just saw before that if we have for example like a binary tree type of branching then we're going to have exponentially growing receptive field"}, {"start": 1950.48, "end": 1976.48, "text": " Whereas here if the edges are positive we can have a guarantee that they are bounded by a polynomial and here we for the first time see the connection between over squashing and curvature so there is a notion that if your graph is positively curved then because of this polynomial thingy indirectly you're going to have less over squashing because you're going to have less bottlenecks and less over squashing"}, {"start": 1976.48, "end": 1998.48, "text": " Okay now let's take that one step forward and find an explicit connection between curvature on one hand side and over squashing on the other side and that's what this theorem for is all about so this is going to be probably the the the main the main contribution of the paper and let me start and dissect this theorem for you"}, {"start": 1998.48, "end": 2016.48, "text": " There is a huge proof in the appendix you can go and check it out if you're into math but like this is going to give you a rough intuitive understanding of what's going on here and why this works so consider a MPN so a message passing neural network so the one we saw in equation one that's the generic MPN"}, {"start": 2016.48, "end": 2045.48, "text": " Let I be connected with J and the degree of node I is smaller or equal than DJ and then assume two conditions so the first condition assumes that you can basically upper bound the gradient of the update function and the gradient of the psi function of the message function for any layer for any L between 0 and capital L minus 1 which is L is the number of layers in our MPN"}, {"start": 2045.48, "end": 2068.48, "text": " With the depth being at least two layers then they say in two there exists Delta such that Delta is bounded like this and bounded like this so this is the this gamma coefficient we saw a couple minutes ago and we have that the curvature is upper bounding by upper bounded by minus two plus Delta"}, {"start": 2068.48, "end": 2094.48, "text": " Okay so this is so far very like maybe not not that clear I'm going to give you the gist in a second so then there exists this set Q sub J which is a subset of S to set of five satisfying that the size of that set is bigger than one over Delta blah blah and for all of these L zeros between zero and capital L minus two we have this equation here"}, {"start": 2094.48, "end": 2120.48, "text": " Okay so what this tells us here is that if we sum over elements of that of that subset Q of S2 and if we if we basically sum up all of these sensitivities of various nodes K from that subset that's going to be upper bounded by this expression here so alpha beta raised to the power of two times Delta"}, {"start": 2120.48, "end": 2141.48, "text": " raised to the power of one over four so now let me let me try and visualize this and break it down so first of all we have node I here so let's say let's say we have node I here we have one hop neighborhood here and finally we have two hop neighborhood here so what this theorem states is that basically there exists a subset so this is"}, {"start": 2141.48, "end": 2170.48, "text": " S2 so this this thing here let me try and draw it this thing here is S2 and what they state is that there exists some subset of these nodes so let me just kind of take a subset such that if you were to sum so now take some nodes from from this subset and if we were to calculate their sensitivities they're going to be upper bounded by this expression here so you can also read this as over squashing so over squashing of that"}, {"start": 2170.48, "end": 2199.48, "text": " over squashing of that neighborhood so the I'm going to denote that as like over squashing OS for example yeah and now what you can see is that if the edge is very negative so if Delta goes down to zero if you start in the limit when Delta goes to zero this edge IJ is going to be very negative because it's going to be upper bounded by minus two plus a small number which means it's going to converge almost to minus two which is super negative edge if that happens"}, {"start": 2199.48, "end": 2221.48, "text": " that means that this expression here so Delta goes to zero here and that means that you can see this becomes the whole expression goes to zero and that means we have over squashing so again the the the chain of thoughts here is the following if we have negative edges that means that we directly have over squashing problem and that's the direct connection they made"}, {"start": 2221.48, "end": 2250.48, "text": " there is a lot of details which follow from many other theories there is a lot of math in the in the appendix but this is a roughly what they're they're saying I'm going to make one more connection here with this chigar constant which is very interesting constant in in graph theory and then I'm going to show you the final algorithm the rewiring algorithm they applied in this paper so back to chigar constant so chigar constant intuitively captures the notion of of how bottlenecked the the graph is"}, {"start": 2250.48, "end": 2279.48, "text": " so if I were to draw a simple graph like this so let's imagine we have some some some nodes inside of here which are densely connected and then we have another community of nodes which are densely connected and if we have a single edge here you can see intuitively that this barbell shaped graph has a very high like it's very bottlenecked like there is a like a huge bottleneck and that's the one here okay and you'll see that this"}, {"start": 2279.48, "end": 2309.48, "text": " a H J so this chigar constant correlates with our intuition here very nicely because how we calculated and there is a mistake here so this should not be here I had a discussion with one of the main authors of the paper francesco he told me this is just a typo so basically you can see that we take the number of elements in this set so this set is as you can see here those are the edges such that I belongs to S and J belongs to its complement so in this particular example that will mean the following so we're going to"}, {"start": 2309.48, "end": 2338.48, "text": " so this is if this is S and this is basically the complement then this edge here is going to be a part of this set so this is the only edge that belongs to this set here and that means we have one here so very small number here and then we have like a minimum of volume so whatever the minimal volume between these two sets is we find that thing and that we divide it and the volume itself is divide as the sum"}, {"start": 2338.48, "end": 2360.48, "text": " across all of the notes of that set S and we just sum up their degrees so you can see here is going to be like some huge number and we have a small number and that means this is going to go towards zero for this edge case of a very bottlenecked graph and as we start adding and you can imagine if we start adding more edges if I were to start more edges here"}, {"start": 2360.48, "end": 2390.48, "text": " add more edges this thing is going to grow up so it's going to explode not explode but like it's going to have more and more elements and thus this chigger constant is going to consequently rise up from zero to some bigger number and thus it correlates in a way with how bottlenecked the graph is and now you can see a bunch of problems it's a single scaler what if we had much more communities what if we had like what if we had even more communities here and they"}, {"start": 2390.48, "end": 2407.48, "text": " are connected so it fails to to capture more interesting topologies but like it's it's a number that give you gives you some global it's a global statistics some gives you a global understanding what's going on in the graph but it's not that detailed and and and and yeah and you want"}, {"start": 2407.48, "end": 2437.48, "text": " so then they show the following thing and that's that the basically spec like spectral gap of a graph is bounded by the chigger constant and this spectral graph gap again correlates with this how connected the graph is and what this spectral gap is and they say here so lambda one is the first non zero eigenvalue of the normalized graph laplacian often referred to as the spectral gap so that's a nice connection between the"}, {"start": 2437.48, "end": 2466.48, "text": " spectral theory and and this graph theory i.e. the chigger constant but more interestingly for us they show that if the curvature is positive for all of the edges then you can you can basically like lower bound the chigger constant and that and also the the the spectral gap by this k which is the same k as we have here which means that by controlling the curvature how positive it is we can control the the the"}, {"start": 2466.48, "end": 2480.48, "text": " chigger constant i.e. how bottlenecked the graph is and the spectral gap of the graph so that's some some nice connections not necessary to understand this paper but like i made a small tangent here hopefully you can appreciate it"}, {"start": 2480.48, "end": 2510.48, "text": " okay so finally let's get to the to the meat of the of the paper i mean at least procedurally this is the final rewiring algorithm before going to the details let me just tell you what those are so they say here that more recently there is a trend to decouple the input graph from the graph used for information propagation so that's an important thing to notice such methods are often generically referred to as graph rewiring and we see here an example so here on the left we have a graph"}, {"start": 2510.48, "end": 2540.48, "text": " on the left hand side we have the original graph and we have some coloring depending on the curvature so again blue means we have negative edges red means we have positive edges blah blah blah but more importantly you can see that if we apply some some other baseline and this is called deagle method so this is called deagle which stands for diffusion improves graph learning we can see it completely changes the statistics of this particular graph it adds a lot of edges and thus completely skews the degree"}, {"start": 2540.48, "end": 2570.4, "text": " distributions etc etc on the other hand this thing here is their proposed method which we're going to see in a second and you can see it preserves the statistics but manages to basically makes the curvature of these of this graph higher okay now let's see how the actual thing works and yeah the important part to notice is that now instead of operating your your graph neural network on top of this original graph you instead what you do is you rewire"}, {"start": 2570.4, "end": 2600.4, "text": " the graph and then you use these edges to do your message passing on your graph so that's that's the that's the idea behind these rewiring methods they serve such like some type of pre-processing steps okay so here is the stochastic discrete richie flow algorithm which is super fancy name but it's a very cool algorithm so let's see what happens here so we have as input we have a graph G is given we have temperature tau which is a positive temperature which is because we are going to be"}, {"start": 2600.4, "end": 2630.4, "text": " sampling in this algorithm that's why we have that the notion of temperature we have max number of iterations and optional optional curvature upper bound called C plus we're going to see what that means in a second okay so the algorithm proceeds as follows so we're going to repeat the following steps until convergence or the max max number of iterations has been reached let me just draw a company graph that's going to help us grasp this a bit better so let's say we have two edges here let's say they are maybe"}, {"start": 2630.4, "end": 2660.2400000000002, "text": " a it's a bridge between some densely connected communities maybe something like this and let's see how now the graph operates so for edge i j with minimal richie curvature which is in this example going to be this one here so this is going to be our our like negative the most negative edge here then they say calculate vector x where the element of that vector x denoted as"}, {"start": 2660.24, "end": 2684.7999999999997, "text": " x sub k l and define like this is basically the improvement to the curvature of this edge i j from adding edge k l where k is belongs to the b one set of five and l belongs to the b one set of j okay so let me again just explain what it means that means we're going to make the following thing so let's"}, {"start": 2684.8, "end": 2714.0800000000004, "text": " um i'm going to try and add so we're going to try and add an edge so basically here maybe and this one you can see so this is node i this is node j you can see that i took a node from the b one set of i and i connected with with a with a node from b one set of j and now i see how how how much of an improvement does this have on on the curvature of this edge and that's this term here okay"}, {"start": 2714.08, "end": 2734.56, "text": " so we're basically going to do the same thing so we're going to do this multiple times and we're going to exhaustively connect this one with this one and and and this one with this one etc etc and we're going to calculate this improvement for all of those and then we're going to sample with probability"}, {"start": 2734.56, "end": 2764.48, "text": " uh basically softmax of that vector x and we use tau to modulate the temperature and we're going to sample from that vector and then add add the edge that was sampled to the graph so maybe one of these edges is going to be sampled maybe i don't know maybe this one is going to be chosen and uh basically that will be the end of step one you can imagine that if you push tau to like positive infinity to some big number"}, {"start": 2764.48, "end": 2782.2400000000002, "text": " big positive number then you're going to have instead of of this uh like a smooth distribution you're going to have like a deterministic distribution distribution where the edge that had the highest uh improvement is going to be chosen sampled and added to the graph so you can kind of use tau to"}, {"start": 2782.24, "end": 2809.7599999999998, "text": " uh tweak your your algorithm in that sense okay so we've added the edge and that that increased uh the positivity of this uh initial uh curved edge uh denoted in blue and the second step is remove edge with maximal uh rigid curvature only if that curvature is bigger than this c plus so that's the upper bound i mentioned and again you have some control here if you make c plus arbitrary like very very big"}, {"start": 2809.76, "end": 2839.6800000000003, "text": " then at one point of time uh that will mean that you'll never be removing positive edges and you'll just be adding uh these edges that increase the positivity of the of the graph okay so the reason why they have this part here is in order to preserve the statistics of the graph so as much as you add and thus increase the number of edges you want to also remove and thus kind of balance out uh the the the the the number of edges and the degree of nodes are going to be uh less skewed in this way"}, {"start": 2839.68, "end": 2869.52, "text": " in that way cool and you do this until convergence uh and whereas convergence means sometimes whatever combination of edges you add you'll never have the improvement here and thus that's that's how convergence is defined and that's that's it that's the that's the uh stochastic uh discrete root flow algorithm uh fairly simple idea uh if you think about it very very neat because it has this awesome connection with uh differential geometry but uh but yeah okay so finally they do compare"}, {"start": 2869.52, "end": 2888.08, "text": " um how strf works compared to deagle which is this competitive approach which works much better on homophilic uh graphs but i'm going to skip this math and theorems because it's a it's a arguably a tangent not uh not necessary to understand the core of this paper"}, {"start": 2888.08, "end": 2903.84, "text": " and so i'm going to skip that part um this time so here are the results you can see uh on various different um graph data sets uh core sites here pubmed might be familiar to most of you who have who have had any exposure to graph ml field"}, {"start": 2903.84, "end": 2933.76, "text": " uh you can see we have the homophilic coefficient associated with each of these graph data sets as denoted by this uh add h uh of j and you can see these ones have low h which means low homophilic which means high heterophilic and these ones are much more homophilic and again homophilic just means uh birds of feather flock together i.e. if you have a node and it's connected to its neighboring nodes there is a high uh chance that basically they'll share the same label"}, {"start": 2933.76, "end": 2963.5200000000004, "text": " whereas in heterophilic data sets oftentimes very distant nodes so some nodes which are uh yeah more distant from each other are going to have the same label i'm going to share the label and you can imagine for these heterophilic data sets it's very important to have effective strategy of communicating over those long distances and over squashing is one of the things that's going to uh ruin that communication and that's what this paper is handling basically and that's why it's better for heterophilic data sets compared to homophilic data sets"}, {"start": 2963.52, "end": 2986.88, "text": " uh the results support the claim you can see that for these heterophilic data sets it basically outperforms all of the other baselines we have deagle here we have this uh plus fa approach which is uh basically just fully a full um adjacency matrix uh in the last layer of our graph neural network a very simple modification that kind of tries to cope with over squashing effect as well"}, {"start": 2986.88, "end": 3014.96, "text": " uh and yeah as as i said better performance on these heterophilic data sets and you can see not as great although competitive performance on on these uh homophilic data sets deagle seems to perform somewhat better uh compared to to strf which is expected okay so uh finally just some distributions here they show that their"}, {"start": 3014.96, "end": 3038.32, "text": " rewiring method is much uh better at preserving various statistics so you can see here that comparing the degree distributions you can see that the the blue one is the original one uh the green one is the strf and deagle is the orange one and you can see it completely changes the the degree distributions for various different data sets and also you can see that"}, {"start": 3038.32, "end": 3056.7200000000003, "text": " uh the number of edges that deagle adds is huge whereas it does not remove edges and on the other hand strf both adds and removes edges and that's why it preserves the statistics of the graph finally i'm gonna uh end it up on this note uh they mentioned the limitation which is very something to think about"}, {"start": 3056.72, "end": 3076.9599999999996, "text": " uh so one limitation of our work is that the theoretical results presented here do not currently extend to multi graphs okay that's one thing because uh this whole like thing of calculating the number of triangles four cycles all of that breaks down uh in the case of multi graphs where you can have multiple edges between nodes"}, {"start": 3076.96, "end": 3106.88, "text": " and finally they say even more importantly that in addition the current methodology is agnostic to information beyond the graph topology such as node features so why is that important so imagine you have a graph where for example like a social media graph and that graph represents who is following whom and if you were to start and just um based on the curvature of the edges start rewiring that you're changing the underlying semantics of the social media"}, {"start": 3106.88, "end": 3136.8, "text": " graph and that can lead to false predictions later in your pipeline so because you're not taking features node features and net features into account you are less nuanced in how you change the semantics of the underlying graph if that makes sense okay so on that note um this is a very very cool paper i loved it and uh if you found the video useful yourself uh consider sharing the video um and subscribe"}, {"start": 3136.8, "end": 3157.44, "text": " to this channel and finally do join our discord community you'll check you can find the links down in the description until next time bye bye"}]