Neural Sheaf Diffusion: A Topological Perspective on Heterophily and Oversmoothing in GNNs
❤️ Become The AI Epiphany Patreon ❤️
https://www.patreon.com/theaiepiphany

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

In this video I cover "Neural Sheaf Diffusion:
A Topological Perspective on Heterophily and Oversmoothing in GNNs" paper. The paper takes ideas from the sheaf theory - a branch of algebraic topology - and combines them with GNNs, enriching them with a rich geometric structure (sheaves) achieving provably more expressive diffusion-based graph neural networks!

It took a lot of time to prepare this video and read everything that was necessary as a background reading - check out the resource section below for how to get started!

▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬ 
✅ Paper: https://arxiv.org/pdf/2202.04579.pdf

Truly gentle introduction to sheaves:
✅ A Very Elementary Introduction to Sheaves:
 https://arxiv.org/pdf/2202.01379.pdf
✅ Opinion dynamics on discourse sheaves: https://arxiv.org/pdf/2005.12798.pdf
✅ Sheaf Neural Networks: https://arxiv.org/pdf/2012.06333.pdf

Blogs:
✅ Blog accompanying the paper: https://towardsdatascience.com/neural-sheaf-diffusion-for-deep-learning-on-graphs-bfa200e6afa6
✅ Differential geometry and algebraic topology papers overview: https://towardsdatascience.com/graph-neural-networks-through-the-lens-of-differential-geometry-and-algebraic-topology-3a7c3c22d5f
✅ Beginner intro to topology: https://www.cantorsparadise.com/what-is-topology-963ef4cc6365
▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬ 

⌚️ Timetable: 
00:00:00 Gentle intro to sheaf theory and algebraic topology
00:12:00 Making it less abstract: examples from sheaf theory
00:23:50 Formal terminology
00:27:40 Sheaf Laplacian dissected
00:40:00 The separation power of sheaf diffusion
00:53:00 Dirichlet energy and converging to harmonic space
01:01:05 Neural Sheaf Diffusion GNN
01:06:00 Results and outro (feedback appreciated)

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

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

#sheaftheory #algebraictopology #oversmoothing #heterophily
 What's up you guys, in this video I'll be covering neural sheaf diffusion, a topological perspective on heterophily and oversmoothing in GNNs. This is a paper by Christian Bodnar, Francesco Di Giovanni, Benjamin Chamberlain, Pietro Leo and Michael Bronstein. And like you'll probably notice here, like most of you are probably not familiar with this word sheaf, and there is a whole theory called sheaf theory that's coming from the field of algebraic topology, and all of that may sound mouthful, and that's because it is. And I'll first try and give you a lot of context and understanding of what this theory is about, and then we'll start digging into the paper. So let's start with the abstract, but you'll probably won't understand anything here, but still let's kind of read it out and work our way from there. So cellular sheaves equip graphs with a geometrical structure by assigning vector spaces and linear maps to nodes and edges. Graph neural networks, or GNNs for short, implicitly assume a graph with a trivial underlying sheaf. So this is an important point. So the neural graph neural networks just assume a trivial sheaf structure. So this choice is reflected in the structure of the graph laplation operator, the properties of the associated diffusion equation, and the characteristics of the convolutional models that discretize this equation. So one example would be the GCN model. So in this paper, we use cellular sheaf theory to show that the underlying geometry of the graph is deeply linked with the performance of GNNs in the heterophilic settings and their over-smoothing behavior, and you may be familiar with this already, but GNNs are usually not as great for the heterophilic setting. And what I mean by a heterophilic setting is that, okay, let me maybe explain the homophilic setting. So in homophilic setting, the nodes which are close together and connected usually share the same label. So there is a saying that goes like, birds of feather flock together. So that's basically your homophilic setting. So the heterophilic setting is different. So that basically means even though if some nodes are connecting, that doesn't mean they have the same label. They may have completely different labels. Traditionally, GNNs struggled with this setting, and that's what this paper is trying to tackle, as well as over-smooting, which is just a consequence of the fact that how most GNNs work is they take some type of an average of the neighborhood features. And by just doing that and iterating that through multiple GNN layers, you end up with feature vectors converging to some value. And that's the over-smoothing phenomena, like a very hand-wavy of explaining it. Okay, so let me start by just kind of showing you a couple of snippets from this paper that's called A Gentle Introduction to Sheaves on Graphs. And I want to stress the gentle part, because the paper is like, I could maybe understand the first couple of pages, and then it just kind of spiraled out. And basically, unless you're a mathematician that has some understanding of topology and algebraic topology, preferably, you'll have a tough time understanding this gentle introduction. So even though I consider myself to be very comfortable with various branches of mathematics, I still struggled a lot. So let me read you a couple of snippets anyways. So while these concepts may seem even more hopelessly abstract than the already abstract notions of sheaves and morphisms, the reader should rest assured that the exposition here is far simpler than nearly any other explanation of sheave cohomology or homological algebra. Okay. And then they proceed to say the interested reader might consult a book like this one, but a warning is in order. A typical prerequisite for reading and understanding a book on homological algebra is to have read and understood a book on homological algebra. Okay, so this kind of hopefully gives you some understanding of what's going on in this field is fairly abstract. And worst of all, there is not that many like beginner friendly resources out there. There is one paper I found which is absolutely great, and that's called A Very Elementary Introduction to Sheaves this time. So we can see the progression here. We have the classical theory, then we have the gentle introduction, and only the very elementary introduction will actually work. And it will give you some mental models of what's going on in this when we mention sheaves and we mention all of these abstract concepts. So I'll get to this a bit later. First of all, let me let me start and explain this like starting from a more specific setting, and that's the setting we'll actually care about. So that's the setting here. So we have a graph here. You can see two nodes. We have a node V and a node U. We have an edge connecting those two nodes. And what we do is we associate this algebraical structure. So in this particular case, we're going to use a vector space and we're going to associate a vector space to both of these nodes and as well as to the edge. So other than the vector spaces, we'll also associate these restriction maps. I mean, not associate, we'll define these restriction maps for for all of the incident node edge pairs. So that's on a high level what's going on. So we have a topological object, which is a graph in this in this particular example. So let me take a pen here. So this is our topological object and we associate certain algebraic objects with with our topology. So in this particular case, we associate I can see here a vector space in another vector space and yet another vector space with an edge with nodes and with nodes here as well. And we define these as I said, restriction maps, which are simple linear maps between these different vector spaces. So there is a nice basically analogy to if we go to the world of differential geometry and we start thinking about manifolds. And in this particular case, we have a 2D sphere embedded into a 3D space. Here we have a similar notion. So we have a we have a vector space associated with this particular point on the manifold. So this is the tangent space of that manifold. And this can be roughly treated as the as the vector space associated with this particular node here. So here we associate the tangent space with the point on the manifold and basically the optimal transport. So not the optimal, sorry, the parallel transport on this sphere is an equivalent of this not equivalent, but an analog of this restriction map in our in our setup here on the sheaf here. And you can see so the parallel transport is going to convert a vector from this tangent space to a vector in this other tangent space associated with some other vector space. So this is going to convert from this tangent space to some other point on the manifold. So there is a kind of loose analogy between these these two. So that's maybe worth mentioning. OK, so now let me step back and try and give you a bit more context and what this algebraic topology is about, because this is just a particular specific like setup of algebraic topology that we'll care about. So this is a vector from Michael Bronstein's blog, and it kind of introduces the wider terminology. So the idea is the following. So here you have like multiple stocks of grain which are like basically tied together. Getting back to our setup, these vector spaces here and algebraic structures more generally are called stocks. So this is going to be called a stock. And so that's that's the stock part. And then the restriction maps are what's tying together all of these stocks. So that's why you'll often see this like basically a bundle of grains used to represent ideas from from algebraic from from sheaf theory, which is a branch of this field of algebraic topology. And that may or may not help you memorize what the sheaf structure is about. OK, but let me generalize. Let me take even like a step further and let's generalize this even more. So this is how the what the informal definition of a sheaf would be. So we assign to each open subset of the underlying topological space a certain algebraic structure and we specify restriction maps between them. So what's a topological space? Well, topological space is a very, very general notion. So that can be anything from like a line from a real line to graphs, to manifolds, to simple complexes, which are themselves a generalization of specific types of graphs. We then have cellular complexes as another topological object, etc. Etc. You can see that by saying this sentence, you basically mean a lot of things. It's very general. It's very abstract. Then they see a certain algebraic structure. And most of you are probably familiar with vector spaces, but not that much with groups or rings. But like those are some other types of objects you could kind of associate with this open subset on your topological space. And finally, we specify the restriction maps so you can see that we get our set up by specifying a particular topological space. So we care about graphs and we care about vector spaces on those graphs. And even more specifically, we're going to be using vector spaces of the same dimensionality for each of our stocks. That's additional additional detail. OK, so again, briefly, topology is for those of you who are not familiar. This is a loose informal definition, but it will maybe help you create some some mental model. So what is important in topology is the connectivity and not the distances and or angles, whereas in geometry, we care about the distances and angles. So the connectivity is the name of the game. And that's why the donut and a coffee mug are the same thing for a topologist. So that's like a usual joke in for at least for mathematicians like the like basically a coffee mug and a donut are the same thing. But because as you can see here, both of these objects can be morphed into each other. So there are these mappings. I think they are called homomorphism, I guess, between like a coffee mug and a donut. And the reason is we only have a single hole here, and that's what what what makes a difference. So if we had two holes, then we have a different object or if we had zero holes, that would be a different object. But everything else can kind of be, as you can see, morphed from from one shape to another. And because of that, they are considered equivalent. I also mentioned these objects called simplicial complexes. If you take a simple graph, whereas by simple graph, what I mean is a graph that doesn't have any self edges nor does it have any multiple edges between two nodes. So this would be this would be a simple graph. Something like this would be a simple graph and a generalization of the simple graph is something called simplicial complexes. You'll probably see that term thrown around. So just to kind of make it to define it here. And finally, if we have graphs with self edges and with multiple edges between two nodes, this is known as a multigraph with self edges and a generalization of these is called cellular complex or cellular complexes. So, yeah, that's just additional context for you. Finally, there is this nice statement from from from Maurice Auslender saying that she theory is the subject in which you do topology horizontally and algebra vertically. OK, so that was kind of various terms and concepts related to this like branch of mathematics. And now let me try and make this a bit more concrete. OK, I already mentioned this paper, a very elementary introduction to sheaves. And I want to make like a huge shout out to the author of this paper. I think that like doing this is incredibly important, especially if you have some very abstract and for most people like alien type of a theory. You really want to create a paper where you dump all of your like mental models, all of your visualizations and all of the concrete examples you use to ground some abstract concepts from that theory and make them digestible to your like brain. I guess I would really love to see more of these papers for each of like different branches of more abstract pure mathematics. And I guess the reason people are not doing this usually is because it's not that rigorous and then maybe your peers will judge you or whatnot. But like like I urge you, this is like so important. This paper made it much like more visceral for me what she theory is about. So let's read this abstract and then let's see a couple of figures from from this particular paper. So here we give a simple and approachable explanation to the mathematical objects called sheaves. This paper presents tangible and concrete examples so that readers will be able to further explore these concepts on their own in more abstraction and application. So for me and I know for for many people, I know it's much easier to start from a concrete example and then abstract away rather than start in the abstract space and then try and understand what's going on and where can I relate this to. So I think this is that's why this paper is so important. So as they say here that the paper this paper is very is a very non rigorous. It's a non rigorous loose and extremely basic. And I would also add extremely useful introduction to sheaves. This is meant to be a guide to gaining intuition, which is so important about sheaves, what they look like and how they work. So after reading this paper, someone can jump into the extremely abstract definitions and examples seen in textbooks with this some idea of what is going on. OK, so let's get back to our particular example of a sheaf where we care about graphs as that underlying topological object and where we care about vector spaces with the same number of dimensions as our particular algebraic space object. OK, so here we can see that we have, for example, this this particular stock for this node is going to have two dimensions. It's going to be two one and this other stock is going to be minus two ten three. So in this particular example, they did use different dimensionalities, but that does not matter that much. Then we have they've specified a particular restriction maps. You can see they're just simple linear maps as represented by this matrix. We have a different one here. And if we take this vector and we map it, we get we end up with this vector here. OK, so let me just change the color. So we end up with this one here. And if we take this vector and we map it with its restriction map, we end up with this particular vector here. OK, and so the important thing I want you to notice here is that these two agree, which is not the case in general, obviously. And this is super like this is a vital idea in this in this sheaf theory. This agreement and to just to make this a bit more concrete, let me give you a particular interpretation of what this could mean. So imagine this graph represents a group of people, a social network, and imagine these stocks here. So the vectors associated with our nodes, which themselves are basically represent certain individuals in the society. So this stock is just opinion space. So you can imagine of this as an opinion vector. Basically, minus two would mean this particular person thinks negatively about some topic X. I don't know, whatever like politics. Then this means that this same person thinks extremely positively of some other topic Y and so on, etc. So we have three for some other topics. Same here. And what this this model does is by mapping by mapping this opinion vector into this so-called discourse space. So this thing here, they refer to this as a discourse space. Here we achieved an agreement. So even though the personal private opinion vectors are not the same after we express them, we get to an agreement. And that's pretty much the only way how a society can function. We have to roughly have similar like agreements across across certain topics. Otherwise, everything explodes. And so this could be one particular interpretation of what is going on and why it is important to find such vectors here. So such vectors, such stocks, such that we have an agreement across all of the edges of our graph. So that's the idea there. Okay, so now again, let me take a step back and just make this a bit more general because I assume that most of you have no idea of what algebraic topology is. And so that's why I'm giving you just a lot of examples and I also link a bunch of resources down in the video description. So do check them out. Okay, let me give you another example and then we'll get to the rest of the paper. And hopefully it's going to be easier to understand after this. So for a topological space X. So we are again now more general. We're not talking about graphs. We're talking about general topological spaces. A sheaf of a billion groups on X assigns each open set of X to an abelian group. Okay, so this time our abstract object is in a billion group and we have some open set of a topological space as our underlying horizontal object. So which a billion group you ask. So here it will be the group of continuous functions from U, which is the open set to R. That is for an open set U, which is a subset of our topological space. The stock of U is the group this one. So it's a set of functions F of continuous functions F that map from that open subset to R. Okay, just to make this a bit more concrete. Here is a particular example of what that means. We have an open subset here U as you can see here. And we you can see like us. This is a set of continuous functions defined there. So this thing here would be the stock and by picking so picking a particular function from this space here. So maybe picking this one is the same thing as picking a particular vector here. Okay, we're just dealing with different objects. But like this isn't a concrete instantiation on the vector space. And this is a concrete instantiation in this particular a billion group. Okay, so so along with the point wise addition, this is this is basically a group and for an open set V, which is a subset of U the restriction map from U to V as denoted like this is actually really simple for an element F of F of U, which is a continuous function. This restriction map is the restriction of F from U to V. Okay, so I'm going to stop there. So what it means is the following. So after we apply this restriction map, we end up so you basically map the following thing is you still map. So let me take a color like this. So you'll map this thing. On to this thing here. So basically you just constrain. So before that your function was defined. This was a domain of your function after this restriction map. You just redefine it here, but you have the same you have the same function in this in this particular domain. So it's kind of trivial, but we'll see why why that why that makes it makes sense. But again, by doing this, what we've done is we took this function, which is in this analogy like this particular vector. And then we mapped it all the way to here. So this time we don't have this intermediate step. We just map it. We just find the inverse mapping here and we map from here to here. Okay. Now with this definition, let's see how we define the agreement this time. So here you can see here is a bunch of a bunch of open sets, which you can see those were nodes in our previous example. And for each of those open sets, we associated a particular function. So that's a concrete instance from our group, which is the algebraic structure we care about in this example. So that will be a particular vector in this for this particular node. We'd associate a particular vector here for this particular open set. We associate a particular function. So how do we get to an agreement? So here is what the agreement looks like for this particular sheath. We basically get a continuous function. And if you think about it, it makes sense because so after you might say, let's take let's take one example. Let's take, for example, this this purple open space from here to here. And if we do the restriction map, if we apply the mapping to this other orange space, so this one here, let me just change the color. So if we map there, we know that the function needs to remain the same. So that's that's how we define our mapping is going to be here. And the only way that this small function agrees with this function here is that they perfectly align. And because you can have multiple of these open sets here which intersect with each other, the only solution where we have this agreement for this particular sheath is if we have a continuous function on this on this space. OK, so hopefully that gives you some understanding of what's going on. I did get into a bit more nitty gritty details than I needed. But like I just wanted you to understand the whole point. I want you to take out from this explanation is agreement in in in sheath theory is a very, very important concept. So agreement here leads to a very nice like continuous function agreement here leads to people and society being a functional society instead of just breaking apart because people are polarized. OK, guys, let me quickly give you one more take of how this works in case you did not understand it. I'm going to make it much more pictorial. So imagine we focus on on these two open sets. So we have this open set here. And we have this orange one here. OK, so imagine instead if on this orange open space, we had a function defined like this. So we pick a value from our stock and it looks like this. OK, and imagine for that this this bigger open subset, we have exactly this function here. So this is the value we took. So after we take so we take the function from you from this you three. So from this bigger open space, we apply the restriction map onto this smaller open space. And what do we get? Well, we get this we get this thing here because that's how we define the restriction map. And you can see here that there is no agreement between that and this thing here. OK, and the only way we can get an agreement is if we have a continuous function like this. And yeah, hopefully that now makes it a bit more visceral and understandable. Let's get back to the paper. Let me briefly just introduce you to the formal terminology here. So this is how it looks like. Definition one, a cellular sheaf, which is a tuple containing a graph and this big F, which is the sheaf structure on an undirected graph G, which consists of a set of vertices and set of edges consists of so one a vector space F of V for each node from the basically set of nodes, a vector space F of E for each edge in the set of edges. And these are called stocks again, a linear map as denoted like this. So it maps so that the this means edge E, which is incident. So that's this this this funny symbol with a triangle stuff. So this means they are incident. So this edge is incident to this node. So it maps from the stock of V onto the stock of E. So we define that for each incident node node edge pair. So this is what what the sheaf is. You define these maps, you define these spaces and you've got a sheaf. Okay, so again, I mentioned these are the stocks. These are the restriction maps. The linear map is a restriction map. And now we have this concept of a zero coaching. So zero coaching as denoted with C subscript zero is basically defined as this O plus, which is a direct sum of different stocks. And you can think of this as basically a concatenation of these various vector vector spaces. And then you can define a signal, an element of that zero coaching this bold X here, which is basically a collection of stocks for each of the nodes. Okay, that's one important space you need to to to have in mind. Let's continue on a particularly important subspace of this zero coaching space is the space of global sections. And we've seen this and you'll understand what this exactly means in a second. So this is the this is the agreement thing I was I was mentioning. So this global section space denoted as H zero, which stands for zero cohomology. That's also how you'll see this space referred to. So it's basically a set of these signals of these axes such that and those axes belong to this zero coaching. So it's a set of these axes such that we have an agreement along every single edge of our graph. OK, that's the that's the idea. So we have we apply the restriction map onto our feature vector associated with with with node V. And we apply a different restriction map to node use feature vector. And we have to have the same we have to have an equality here. That's when we achieve the agreement and then mention here containing those private opinions X for which all neighbors agree with each other in the discourse discourse space. So that will be one particular interpretation of what this whole abstract global section space means. So, again, remember this one space of global sections. So those are going to be all of the possible signals on our nodes that leads to the agreement across all of the edges on our graph. That's it. As simple as that. OK, let's continue here. Definition two. And this is very important. I'm going to spend some time here. So the sheaf loplation of a sheaf is a linear map from the space of zero coaching to the spaces your coachings defined node wise. Why this equation? And now this might seem scary, but it's not because if you know anything about graph, I'm only familiar with graph GCN's, for example. This is just going to be this is just a generalization of the very same thing we already saw there. If you if you're not familiar with with those like papers and with that theory, go check out my graph ML playlist. It's going to be immensely helpful for you to understand this video. So imagine if these restriction maps were just scalars. This was a one. If this was a one, if this was a one, you just have a sum containing differences between the central node V minus its neighbors. And that's something we've seen in the graph loplation matrix. So if you multiply your your your basically set of your feature vectors with all graph loplation, you end up with such an equation. So I'm going to make this a bit more complete. So let me give you a particular example to and let's kind of this is very important. This this shift location is one of the crucial objects in this paper. So let me give you a bit more concrete examples here. So let's imagine we have a graph like this. We have three nodes and they're connected like this. So this is a node one. This is no two. This is no three. Let's form a loplation matrix basically. So loplation is defined the following way. The plation is usually defined. There are multiple ways how you can define it. But this is one way. This is so-called I think combinatorial loplation. So we take the degree matrix D and you subtract away the adjacency matrix A. So what's the what's a let's make that more concrete. So let me give you for this particular example. This means the following. So D is going to be the following matrix. So it's going to be a three by three matrix. It's a diagonal matrix and on each of the diagonals you basically contain how many neighbors does that particular node has. So one has only one neighbor and we're going to have zeros here. So we're going to only have basically elements on the on the diagonal. So let me just kind of fill that in. So what does what goes here? So here we take a look at node two. It has only one neighbor. That's node three. That's why we input one here. And finally node three has two neighbors. And that's why the degree of this node is two. Okay, so we have two. So that's the degree matrix. The A matrix is just your adjacency matrix. So basically your connectivity who is connected to whom. So this is going to be a. So node one is only connected to node three. That's why we're going to have one here and we have zero and zero here. No two is only connected to node three again. So we have one here zero zero. And finally node three is connected to node one as you can see here and it's connected to node two and that's why we add ones here and we have zero here. Finally in order to get the loplation matrix. Let's see what we do. We just subtract away these two and we get the following thing. We basically end up with this matrix. Let me just kind of make it here. So we have one one two and then we have minus one here minus one here minus one minus one. And we have zeros elsewhere. Okay, so why is this important? Why is this interesting? Well, let's see what happens if we multiply the set of feature vectors of node feature vectors with this loplation. So this is L. Let's construct the X. So if we associate let's let's say for the sake of simplicity, we only have basically scalars associated with all of these like nodes. So we have scalar X one X two X three. Let's kind of stick them together here. We have X one. We have X two. We have X three. What do we get if we multiply these? So what do we get here? So we basically have and I'm going to just ignore the first two rows. I'm just going to focus on this one. So we have two X three. Okay, minus X one minus X two. And now for the moment, I've been trying to get to is let's make a comparison between this thing here. And this thing here. They have the same structure. This thing is just a generalization of this thing here. So as I said, if these restriction maps were just a simple scalars, so that means if our sheath structure is trivial in that particular case, we fall back to a graph loplation. So let's imagine this is one. This is one. This is one. And let's imagine we focus on node V. V equals three. So we end up with a sum where V is equal to three. And we look at the incident edges, which are going to be this edge and this edge here. So we have a sum. So we have here we have X three minus first edge. So minus X one. And then we have additional term. So plus X three minus this time X two. And as you can see, we end up with two X three minus X one minus X two, which is the same thing as this thing here. Okay, so hopefully now the connection is clear. By introducing this sheath structure, we generalized our graph loplation into this thing called sheath loplation. And that's everything you need to know for now. Let's see a bit more information about sheath loplation. So it's an ND times ND matrix. Why ND times ND? Well, in general, I mean, not in general. In this particular case where we have a trivial sheath structure, then we have N times N. So we saw that right here. So it's D because the dimensionality of a stock is D. That's why we have ND times ND. Okay. So then they say when the vector spaces are set to R, so the dimensionality is equal to one. And the linear maps are identity maps over R. The underlying sheath is trivial and one recovers the well-known N times N graph loplation matrix and its normalized version. And we'll care about the normalized version. And the same thing for, this is the normalized version of the graph of the sheath loplation. And what this sentence says is basically the thing I just explained. We just made this connection. This is a special case. The graph loplation is a special case of sheath loplation. Okay. Next up, they say the following, and this is important. Harmonic signals have perfect agreement of opinions with respect to the sheath structure, i.e. if you multiply those signals with the sheath loplation, you end up having a zero vector. And that makes sense, right? So if we have an agreement here, if X1 and X2 are in agreement with X3, then we'll have zeros here. So if we're in agreement, all of these are going to be, let me change the color. So all of these are going to be zero. Zero, zero, if we have agreement. And that's why, so L times X equals zero. That's what I state here. This is just like sheath loplation instead of a simple loplation. And the name is kind of, I guess, indicative. I'm not sure whether the name came from this fact, but like the fact that we have an agreement that all of these signals are kind of in equilibrium, that's why these are called harmonic signals. Not completely sure, but I suspect, I strongly suspect that may be the case. Theorem 3 just states that this space of global sections, which we saw a couple of minutes ago, and the kernel of this sheath loplation are isomorphic as vector spaces. So let me kind of break this down. Don't be scared here. So isomorphic just means a fancy way of saying these two vector spaces are the same. So these two objects are the same thing, really. So why the kernel space? So this is the kernel space. So basically the set of X's that are mapped by this map, by the sheath loplation into the zero vector, that's what's known as the kernel space. And that's how we define the H0 as well. If you remember, these basically mean the same thing. Okay, enough rambling. Let me try and make this a bit more concrete. And let's make some connections. This is how the sheath loplation looks like. So it's going to be a block matrix. And these blocks are D times D because the stock is D dimensional. And you can see how the structure looks like. So we have, so on the main diagonal, we're going to have these sums of basically, this is the restriction map, multiplied by the transpose of that restriction map. Off the main diagonal, we're going to have minus restriction map of node V. So this is V. And here we have a restriction map of node U, because here we have, this slot corresponds to UV. That's why we have these two. And if you think about it, this construct makes sense because that's how you end up with particular, with this equation here. That's how we end up with this whole expression here. So you can see that if you just kind of ignore the X's, we have the sum of these restriction maps and we have this minus restriction map of U and restriction map of V. And if you just kind of add a vector here, so if we add a vector here, and that's going to be our Rx from this zero co-chain space. So we'll have vectors here. So this is going to be D dimensional. So this is going to be D dimensional. This is D dimensional. And here we just have a single dimension. I kind of made it a bit wider, but like this is just a single element there. And then if you just kind of multiply this, you'll understand that you basically end up with this same equation here. And because here you have like X, V, and then a bit further down, maybe the penultimate slot is going to be X, U. And that's why this thing is going to multiply this thing, and this thing is going to multiply this thing, and that's how we end up with the equation. Sheaf loplation itself can be constructed from these co-boundary operators, and I'll not get into a lot of details there. You can check them out in your own time, but for now just be aware that these co-boundary maps exist, and they basically, as you can see here, they measure the discrepancy again in the discourse space, so in the edge stock. Okay, let's make it a bit more concrete. So here is a particular graph, and here is the sheaf structure. So here are the restriction maps. Here are the stocks, and you see the concrete numbers. And by using those numbers, you can plug them in into this co-boundary operator. So this is how you form the co-boundary matrix. You take the... So this is the restriction map F1, and this is the restriction map that corresponds to node 2, V2, and that's why we have, as you can see here, F1 minus F2, because once we multiply this with stocks, so we have X1, X2, we'll end up with F1, X1, minus F2, X2, and that's precisely measuring the disagreement along this particular edge. So this is how you form them, and you can see again a connection between this and this thing here. We get precisely this equation by forming a matrix such as this one. And if we were to multiply this co-boundary transpose times co-boundary, we end up with the sheaf, and you can kind of imagine that with these Fs here and F2s, if you kind of do your math, you're gonna end up with an equation such as this one, a sum of these Fs and stuff. Okay, I'm gonna stop there. I'm aware this is packed with details, but it is how it is. Hopefully this video is just gonna give you like a glimpse, an overview of this whole field, and you can go on and explore at your own pace, and then return back to this video and watch it again, I guess. Let's get to the actual neural networks now. So an important concept is this diffusion process. Okay, now, so all of those laplations and the sheaf laplations can be thought of as a discretization of this diffusion process. So it's basically a continuous process governed by a PDE, so a partial differential equation. So we can see that the rate of change of X equals minus sheaf laplation times the current values of X. And let me try and briefly explain what this diffusion process is about. So again, how it came to be, this whole theory, is I'm fairly sure it came from Fourier analyzing the dissipation on solid bodies, the heat dissipation on solid bodies. So imagine you have like a 3D solid object here, and you have a certain point inside here. So you have a certain point, and that certain point has associated temperature, so a certain scalar. And imagine now that you have around it, you have like a dense, like a minisphere around that point, the green point, and all of those points in the neighborhood are colder. So what's gonna happen is that, as you know from your real life, this red, the green point is gonna slowly cool down. And I should have probably used the red color to denote it as being hot. It's gonna slowly cool down. And the reason it cools down is because of this diffusion equation. So basically you can imagine what happens is, we subtract from this value, whatever that value is, so some T zero, we subtract the average of the temperatures in the neighborhood. And that means we're gonna subtract the average, so like a sum of the temperatures of the neighbors where I is gonna be from the neighbor set, just denoted as this very ugly N. And if you think about it, this is exactly the same thing we're doing with our graphs. So we just made this continuous, both in space and in time process, and we discretize it. So we're doing it in a discrete domain, which is a graph, and we do it in discrete steps. So in every iteration, we're gonna be doing the same thing. Okay, so what this eventually leads to is basically everything is gonna have the same temperature. Okay, that's the end goal of this process. And we just took the discretized version of this same process, and we are piggybacking that as we're using it as the workhorse for all of our, for most of these graph neural networks. Now they say here, it can be shown that in the time limit, each feature channel is projected into kernel of that sheaf laplation. Okay, that means again, that this X is gonna be, that these updates are gonna be zero vectors, and that means that we won't have any rate of change. So the diffusion stopped, the temperature is stable everywhere. And that means continuing here, as described above, this space contains the signals that agree with the restriction maps of the sheaf along all the edges. In what follows, we analyze the ability of certain classes of sheaves to linearly separate the features in the limit of the diffusion processes they induce. Okay, restating this again, by repeating this diffusion process, we'll eventually end up being a harmonic signal. So we'll eventually end up with these harmonic signals, i.e. signals that basically lead to alignment with their neighbors. Now, in general case, that signal might be trivial, so it might be all zeros, which is not that interesting, but like we're gonna now see specific classes and how for specific, if we pick specific sheaf structures, we'll end up with very interesting harmonic spaces. So what would constitute an interesting signal from that harmonic space? Well, a signal such that we can linearly separate our classes, so we can classify it, we care about like node classification, edge classification, regression, graph classification, whatnot. And so if this diffusion process eventually leads to such a harmonic signal, such that we have linear separability of our classes, then we're good, then we want to kind of ride the diffusion process all the way to this equilibrium point. Now, let's see a couple of sheaf structures and what the harmonic signals they result with, basically how powerful are those signals. Okay, so first class they consider is this very simple symmetric invertible class. Okay, it's defined the following way. It's such a sheaf structure such that we have the restriction map for two nodes that connect one edge. So these two nodes are gonna have the same, they're gonna be the same. These two restriction maps are gonna be the same and the determinant of those restriction maps is gonna be different than zero, which means this is invertible as it says here and it's symmetric because these two are equal, okay? Then they mentioned here, we note that for D equals one, so stock dimension equals one, the sheaf loplations induced by this class of sheaves coincides with the set of the well-known weighted graph loplations with strictly positive weights, which also includes the usual graph loplation. Therefore, this hypothesis class is of particular interest since it includes those graph loplations typically used by graph convolutional models such as GCN. So this is the minimal generalization we can make, okay? And we first show that this class of sheaf loplations can linearly separate the classes in binary classification settings under certain homophily assumptions. So that's very important. I'm gonna go through this proposition, but then I'll start slowly scheming some of the details because there is too many details and not all of them are equally important here. Let G be the set of connected graphs with two classes. We have two classes because it's a binary classification problem, so nodes A and nodes B belong into the set of nodes of the graph such that for each node from one class, there exists a node U from the same class and an edge connecting them. So that means that the nodes with the same label are connected to each other. And that's the homophily assumption they mentioned. Then this sheaf has linear separation power over this particular graph, okay? But then they show that it's not powerful enough to linearly separate two classes if basically we have heterophilic conditions. And that's what I show here. Basically, if let G be the set of connected bipartite graphs with partitions A and B forming two classes and being of, like, those two classes have the same number of elements, then this sheaf cannot linearly separate any graph in G for any initial conditions, okay? So that means that if we have something like this, so we have a bipartite graph such as this one, and we don't have any connections here. We just connect like this. We just have these connections, okay? And they can show that in this particular setup, this class of sheaf structures will not work. And that's why we have to resort to some more powerful sheaf classes. And let's see what those are. So then they introduce this non-symmetric invertible where we only have this constraint, so it's invertible, but we don't have the symmetry constraint. Here they show, I'm gonna skip reading this, but they basically say that even in heterophilic conditions, this sheaf class is gonna have the linear separation power over those graphs, which is super nice. So we're slowly, by adding more powerful sheaf structures, we can solve more difficult problems. So in this particular case, basically, binary classification in heterophilic setting, okay? And now they continue doing this. So here they state a fundamental limitation of sheaf diffusion when D equals one, so when we only have single-dimensional stocks. They basically say that let G be a connected graph with more than three classes, so three or more, then this previous class of sheafs cannot linearly separate any signal on that graph, and that's a powerful statement. So that means we need to go deeper. We need to have more dimensions along the stock, along the vector space dimension. So they say here, from a GNM perspective, this means that in the infinite-depth setting, sufficient stock width, i.e. dimension D, is needed in order to solve tasks involving more than two classes, so more than two classes. Note that D is different from the classical notion of feature, channels F. As a result, above shows, the letter has no effect on the linear separability of the classes in D equals one, whereas they showed that the former does. So you can still have, so this sheaf structure, this sheaf neural networks are still going to admit the usage of features. It's just that those do not help increase the expressivity of our models, whereas increasing the stock dimension on the other hand does. So next up, they introduce this diagonal, invertible family of sheafs where the restriction maps are diagonal, so basically, if you take a look at their representation of the matrix, you'll just see diagonal elements, and everything else is zero, and again, it's invertible, so we have this condition of the determinant condition. And they say that let G be the set of connected graphs with nodes belonging to more than three, so three or more classes, then for D equals, or greater or equal than the number of classes, this particular class of sheafs has linear separation power. So as long as the D is bigger than the, or equal to the number of classes, we have separation power. So again, more powerful than the previous families. Then they do the same thing for orthogonal families where basically the restriction maps now belong to this group of orthogonal matrices, which basically means they just do rotations, they don't do any scaling, they just rotate your vectors. And here they show that this class has even more powers in the sense that here you can have, for example, two for the dimensionality of the stock, and you can classify, you can correctly linearly separate up to four classes, so that means it's even more powerful. And the interesting part here is that the proof is crazy, like they use quaternions and complex numbers for two, and basically this statement here may hold even for higher dimensions, it's just that they did not make the proofs for those other dimensions. If you're curious in the very heavy mathematics, the appendix of the paper is full of various proofs of all of these propositions and theorems you saw here. So very, very mathematically rich paper. So finally, the summary. Different shift classes give rise to different behaviors of the diffusion process and consequently to different separation capabilities. Taken together, these results show that solving any node classification test can be reduced to performing diffusion with the right sheaf. A very powerful statement. So again, by taking a particular sheaf structure and by just constructing the corresponding sheaf loplation and by just iterating, applying the sheaf loplation in this diffusion process, we'll end up with certain harmonic signals and depending on the basically richness of the class you picked, those harmonic signals may lead to a very nice linear separability of your classes. So that's the idea here. Okay, we're slowly wrapping up this paper. So there is not a lot more, so maybe pause the video and stretch a bit, I know this was super heavy. So here you can see a previous sheaf neural network devised in one of the previous papers. And it again uses the diffusion process as the workhorse and just adds additional learnable parameters and non-linearities to this diffusion process to make these more powerful neural networks. But what they've done is they actually hard-coded the sheaf structure, so they are not learning the sheaf structure, whereas as we'll soon see in this paper, they're actually learning the sheaf structure as well. So let's see what this thing does. So we have X, which is basically, those are our signals, and the dimensionality of that matrix is gonna be basically Nd times F, so that means we'll have Nd dimensions here because we have N nodes, dimensionality of the stokes is D, and we have potentially F features here. That's why we have something like this. This is the structure of X. So what W2 does is first, you just linearly transform, you map these feature vectors into some other representations. That's the first transformation you do. Then what you do is you take this W1 matrix, which is of dimensionality D times D. This is gonna be D times D. You're gonna do a Kronecker product with identity matrix N, which is a fancy way of doing the following thing. So you're gonna end up with Nd times Nd matrix, which is basically necessary if you want to multiply, left multiply this particular structure here. So why does that happen? Well, you have a matrix that's T times D, and what this Kronecker product does is the following. By multiplying this by basically, just a second, sorry, it's on the other side, so it's gonna be from the left side. So by multiplying this with this identity matrix that has dimensions N times N, you're gonna end up with the following structure. Basically along this diagonal, we're gonna have, we're just gonna copy paste these matrices D. So where there was one in this matrix, we're gonna have a D times D matrix here. And that's why we end up with N times D matrix here, okay? So that matrix is gonna basically take the signals here. So let's assume this is one vector here, this is D. It's going to linearly transform stocks for each of the features. That's what this part is gonna do. And finally, we apply the shift-loplation here, which is going to do the, again, the averaging of the neighbors logic, and then you subtract that value from the node of interest. And then you just apply the non-linearity here. So again, you're basically in a way using this diffusion logic as your workhorse, and then you're building these learnable components and putting those learnable components around your diffusion logic. That's how this network works. And then they say it is natural to call this model a shift convolutional network, since when the shift-loplation is the usual normalized graph-loplation, W1 becomes a scalar and one recovers the GCN of Kipf and Welling, so that's the famous GCN paper. So this shows that GCNs and more generally SCNs are a non-linear parametric and discrete version of shift diffusion. In what follows, we analyze how expressive these non-linear models are compared to their base diffusion process, okay? So let's see a couple of things here. So first of all, they form something called Dirichlet energy. So for the sake of time, it's not even important for you to understand the exact details. What you need to know is that this Dirichlet energy basically measures how far is the current signal from being a harmonic signal. So from being, yeah, basically a harmonic signal. So then they state the following here. If we have a shift class belonging to this particular orthogonal symmetric shift class, which is fairly restricted, if we have a non-linearity that's either a ReLU or a Leaky ReLU, then they can show that the Dirichlet energy in the next state, so this is a signal, the transformed signal after we apply the logic from the neural network, is gonna be upper bounded by this expression here, and this is the old signal. This is the old energy of the old signal, okay? So in particular, this means that if this whole term here is smaller than one, that means that with every step, the energy will go down, and as I said, the energy going down means the signal is going towards becoming a harmonic signal, okay? So this means that the signal converges exponentially fast to the kernel of the shift laplation, i.e. to being the harmonic signal. Okay, and this is usually going to be the case because this lambda star is usually smaller than one, and because of the regularization and everything, in order to reduce the fitting, the norms here are gonna be also small, so this is usually satisfied, which means that for this particular class of sheaves, the signal is necessarily going to go towards the actual becoming a harmonic signal, and that's not always desirable. We'll see why that is. So let's see the proposition 17 here first. They mentioned that as soon as we have an asymmetric transport map, so here remember, this class had the symmetry constraint, so as soon as we have the asymmetric transport map, we can find an arbitrarily small linear transformation W that increases the energy, okay? So this means that this class is gonna be more powerful and does not necessarily need to monotonically go towards becoming a harmonic signal, and we need that flexibility because we are learning the sheave. We don't know the true sheave, like we don't know the ground truth sheave, and that means that we may end up with some bad sheave whose harmonic signals are not gonna end up becoming an interesting solution, meaning we will not have the linear separability, and that's why sometimes we want to actually go away, further away from becoming a harmonic signal. That's why we wanna have more powerful sheave classes. So they mentioned here for any connected graph G and epsilon bigger than zero, there exists a sheave class that is not symmetric, that's important, such that basically for arbitrarily small norm of this W matrix and feature vector X, the energy is gonna actually increase instead of decreasing, and that's the power of these more expressive, like basically sheave classes. So as a summary, not only the sheave diffusion is more expressive than heat diffusion, as shown in section four, but the sheave convolutional networks are also more expressive than GCNs in the sense that they are generally not constrained to decrease the Dirichlet energy. This gives them greater control over their asymptotic behavior than GCNs. And let's finally wrap up this paper. It's becoming a very, very long video. So here is the actual model they propose. So instead of using the sheave equation, diffusion equation we saw moments ago, which is, let me just find the one we were looking at before. So just a second here, where are you? Okay, here it is. This was the diffusion equation we were looking at. So now instead of this one, they actually generalize that diffusion equation and they end up with something like this. So you can easily show that by using particular values for W1 and W2. And for example, if you're in the linear regime of the allel nonlinearity, you can show that this is, you recover the original diffusion equation. So they, and then they start from, and then they take this continuous diffusion equation and they discretize it and they end up with the model that they use. And here it is. Here's the model they use. It's somewhat similar to the previous, like basically a sheave convolutional network we saw. There is a couple of important differences. So we still have this F times F matrix that's mapping the features. We have the D times D matrix that's like basically mapping the stock vectors into novel representations. We have the sheaf loplation. So important details are this. In contrast, we'll learn a sheaf, which makes our model applicable to any real world graph data set, even in the absence of a sheave structure. So the previous paper, they actually hard coded the sheave structure. So they manually set the restriction maps to certain values, et cetera. Whereas here they are learning the sheaf because we'll see in a couple of seconds that this contains additional matrix. So we'll basically have a three set of matrices, W1, W2, and the one that's hidden here, I'm gonna denote it as W3, for each of the layers of this neural network. And the second thing they mentioned is our model uses a more residual parameterization of the discretized diffusion process, which empirically improves its performance. Again, residual connections usually work. We know that since 2015, we'd resonate. Okay, so here is how the sheaf is actually learned. They parameterize these restriction maps like this. We have this phi of, and we basically input the two nodes. And depending on the features of those nodes, we're gonna basically output a particular restriction map. So it's a map that looks like this. Basically we concatenate the features of those two nodes. We linearly map them with W and then we apply some non-linearity. And that's how we end up with a restriction map. So now you're gonna use these to form the graph loplation matrix, which is gonna be your basically block type of a matrix that's gonna have some blocks here, some blocks here. So that's your sheaf loplation. And as I said, the parameters here are gonna be learnable this time. So you're learning the sheaf structure, which is very, very important. Okay, that's pretty much it. They then state here that if you let G be, so this is your graph. That's a final graph with features X. Then if basically the features are different for different edges. So if we have sufficiently different features and this phi is an MLP with sufficient capacity, they show that phi can learn any sheaf. So this is very, very probably very expressive architecture. Finally, they experimented with different sheaf classes. We saw why one would want to do something like that. And the ones they've used is diagonal. Then they've used again the orthogonal ones. And finally the general ones. And as you go towards the general ones, the computational cost becomes a bit greater. For the general one, you have something like this. So D cubed and plus M, whereas your regular GCNs, your GNNs will have M plus M, just this part here. So this is the number of nodes plus the number of edges. So yeah, cubed term, but in practice, you'll almost never have to use D that's huge. So D is gonna be a small number. So this can be considered in a way as a constant, a bigger one, but like still a constant. Here are the results. They showed that they pretty much on all of these data sets that are more heterophilic as basically determined by this homophily level. You can see 0.11 means this is a very, very heterophilic data set. They showed that they outperform all of the previous baselines pretty much. There are a couple of exceptions, maybe on Chameleon, this GDCN, which was particularly designed for heterophilic setting, actually outperforms their model. And also on homophilic data sets such as sites here, PubMed and Quora, they're outperformed by some of the other baselines, which have biases that bias them to perform well for the homophilic setting by design. And that's why it's hard to kind of compete with them, even though in theory, these networks can be able to learn even better representations and thus outperform these models. But that's, I guess, the same thing as with Resonance and like VGGs, like VGGs can theoretically learn something, but unless you provide these hints, like these identity mappings, the skip connections, you will basically not learn the desired representations. Okay, that was pretty much it. Please let me know if you watched this video all the way to the end, I would really appreciate that. If you did, please comment down below so that I know for the future videos where I wanna go into so much details and this video took so much time to prepare. Like I literally read a lot of papers, a lot of papers to get the decent knowledge so that I'm comfortable explaining this to you guys. So hopefully you found it useful. If you did, again, please leave a comment down below if you actually watched the video to the very end. If you did, congrats. Consider subscribing to this channel, share the video out and also consider joining our Discord community. Until next time, bye bye. Caitlin's
[{"start": 0.0, "end": 8.4, "text": " What's up you guys, in this video I'll be covering neural sheaf diffusion, a topological perspective on heterophily and oversmoothing in GNNs."}, {"start": 8.4, "end": 16.8, "text": " This is a paper by Christian Bodnar, Francesco Di Giovanni, Benjamin Chamberlain, Pietro Leo and Michael Bronstein."}, {"start": 16.8, "end": 23.8, "text": " And like you'll probably notice here, like most of you are probably not familiar with this word sheaf,"}, {"start": 23.8, "end": 33.2, "text": " and there is a whole theory called sheaf theory that's coming from the field of algebraic topology, and all of that may sound mouthful, and that's because it is."}, {"start": 33.2, "end": 41.6, "text": " And I'll first try and give you a lot of context and understanding of what this theory is about, and then we'll start digging into the paper."}, {"start": 41.6, "end": 49.8, "text": " So let's start with the abstract, but you'll probably won't understand anything here, but still let's kind of read it out and work our way from there."}, {"start": 49.8, "end": 58.599999999999994, "text": " So cellular sheaves equip graphs with a geometrical structure by assigning vector spaces and linear maps to nodes and edges."}, {"start": 58.599999999999994, "end": 65.0, "text": " Graph neural networks, or GNNs for short, implicitly assume a graph with a trivial underlying sheaf."}, {"start": 65.0, "end": 71.8, "text": " So this is an important point. So the neural graph neural networks just assume a trivial sheaf structure."}, {"start": 71.8, "end": 76.6, "text": " So this choice is reflected in the structure of the graph laplation operator,"}, {"start": 76.6, "end": 85.0, "text": " the properties of the associated diffusion equation, and the characteristics of the convolutional models that discretize this equation."}, {"start": 85.0, "end": 88.19999999999999, "text": " So one example would be the GCN model."}, {"start": 88.19999999999999, "end": 98.6, "text": " So in this paper, we use cellular sheaf theory to show that the underlying geometry of the graph is deeply linked with the performance of GNNs in"}, {"start": 98.6, "end": 109.39999999999999, "text": " the heterophilic settings and their over-smoothing behavior, and you may be familiar with this already, but GNNs are usually not as great for the heterophilic setting."}, {"start": 109.39999999999999, "end": 114.6, "text": " And what I mean by a heterophilic setting is that, okay, let me maybe explain the homophilic setting."}, {"start": 114.6, "end": 120.6, "text": " So in homophilic setting, the nodes which are close together and connected usually share the same label."}, {"start": 120.6, "end": 125.39999999999999, "text": " So there is a saying that goes like, birds of feather flock together."}, {"start": 125.4, "end": 130.6, "text": " So that's basically your homophilic setting. So the heterophilic setting is different."}, {"start": 130.6, "end": 135.4, "text": " So that basically means even though if some nodes are connecting, that doesn't mean they have the same label."}, {"start": 135.4, "end": 137.4, "text": " They may have completely different labels."}, {"start": 137.4, "end": 143.8, "text": " Traditionally, GNNs struggled with this setting, and that's what this paper is trying to tackle, as well as over-smooting,"}, {"start": 143.8, "end": 151.4, "text": " which is just a consequence of the fact that how most GNNs work is they take some type of an average of the neighborhood features."}, {"start": 151.4, "end": 160.4, "text": " And by just doing that and iterating that through multiple GNN layers, you end up with feature vectors converging to some value."}, {"start": 160.4, "end": 165.6, "text": " And that's the over-smoothing phenomena, like a very hand-wavy of explaining it."}, {"start": 165.6, "end": 175.70000000000002, "text": " Okay, so let me start by just kind of showing you a couple of snippets from this paper that's called A Gentle Introduction to Sheaves on Graphs."}, {"start": 175.7, "end": 185.0, "text": " And I want to stress the gentle part, because the paper is like, I could maybe understand the first couple of pages, and then it just kind of spiraled out."}, {"start": 185.0, "end": 194.0, "text": " And basically, unless you're a mathematician that has some understanding of topology and algebraic topology, preferably,"}, {"start": 194.0, "end": 197.39999999999998, "text": " you'll have a tough time understanding this gentle introduction."}, {"start": 197.39999999999998, "end": 204.79999999999998, "text": " So even though I consider myself to be very comfortable with various branches of mathematics, I still struggled a lot."}, {"start": 204.8, "end": 206.9, "text": " So let me read you a couple of snippets anyways."}, {"start": 206.9, "end": 214.20000000000002, "text": " So while these concepts may seem even more hopelessly abstract than the already abstract notions of sheaves and morphisms,"}, {"start": 214.20000000000002, "end": 223.8, "text": " the reader should rest assured that the exposition here is far simpler than nearly any other explanation of sheave cohomology or homological algebra."}, {"start": 223.8, "end": 233.4, "text": " Okay. And then they proceed to say the interested reader might consult a book like this one, but a warning is in order."}, {"start": 233.4, "end": 242.0, "text": " A typical prerequisite for reading and understanding a book on homological algebra is to have read and understood a book on homological algebra."}, {"start": 242.0, "end": 248.3, "text": " Okay, so this kind of hopefully gives you some understanding of what's going on in this field is fairly abstract."}, {"start": 248.3, "end": 254.4, "text": " And worst of all, there is not that many like beginner friendly resources out there."}, {"start": 254.4, "end": 261.6, "text": " There is one paper I found which is absolutely great, and that's called A Very Elementary Introduction to Sheaves this time."}, {"start": 261.6, "end": 270.40000000000003, "text": " So we can see the progression here. We have the classical theory, then we have the gentle introduction, and only the very elementary introduction will actually work."}, {"start": 270.40000000000003, "end": 281.20000000000005, "text": " And it will give you some mental models of what's going on in this when we mention sheaves and we mention all of these abstract concepts."}, {"start": 281.20000000000005, "end": 283.8, "text": " So I'll get to this a bit later."}, {"start": 283.8, "end": 292.0, "text": " First of all, let me let me start and explain this like starting from a more specific setting, and that's the setting we'll actually care about."}, {"start": 292.0, "end": 294.90000000000003, "text": " So that's the setting here. So we have a graph here."}, {"start": 294.90000000000003, "end": 298.6, "text": " You can see two nodes. We have a node V and a node U."}, {"start": 298.6, "end": 300.7, "text": " We have an edge connecting those two nodes."}, {"start": 300.7, "end": 304.40000000000003, "text": " And what we do is we associate this algebraical structure."}, {"start": 304.40000000000003, "end": 313.3, "text": " So in this particular case, we're going to use a vector space and we're going to associate a vector space to both of these nodes and as well as to the edge."}, {"start": 313.3, "end": 320.0, "text": " So other than the vector spaces, we'll also associate these restriction maps."}, {"start": 320.0, "end": 328.40000000000003, "text": " I mean, not associate, we'll define these restriction maps for for all of the incident node edge pairs."}, {"start": 328.40000000000003, "end": 330.0, "text": " So that's on a high level what's going on."}, {"start": 330.0, "end": 334.7, "text": " So we have a topological object, which is a graph in this in this particular example."}, {"start": 334.7, "end": 336.40000000000003, "text": " So let me take a pen here."}, {"start": 336.4, "end": 343.7, "text": " So this is our topological object and we associate certain algebraic objects with with our topology."}, {"start": 343.7, "end": 354.2, "text": " So in this particular case, we associate I can see here a vector space in another vector space and yet another vector space with an edge with nodes and with nodes here as well."}, {"start": 354.2, "end": 362.7, "text": " And we define these as I said, restriction maps, which are simple linear maps between these different vector spaces."}, {"start": 362.7, "end": 372.9, "text": " So there is a nice basically analogy to if we go to the world of differential geometry and we start thinking about manifolds."}, {"start": 372.9, "end": 377.2, "text": " And in this particular case, we have a 2D sphere embedded into a 3D space."}, {"start": 377.2, "end": 383.59999999999997, "text": " Here we have a similar notion. So we have a we have a vector space associated with this particular point on the manifold."}, {"start": 383.59999999999997, "end": 386.3, "text": " So this is the tangent space of that manifold."}, {"start": 386.3, "end": 392.09999999999997, "text": " And this can be roughly treated as the as the vector space associated with this particular node here."}, {"start": 392.1, "end": 399.5, "text": " So here we associate the tangent space with the point on the manifold and basically the optimal transport."}, {"start": 399.5, "end": 406.8, "text": " So not the optimal, sorry, the parallel transport on this sphere is an equivalent of this not equivalent,"}, {"start": 406.8, "end": 412.90000000000003, "text": " but an analog of this restriction map in our in our setup here on the sheaf here."}, {"start": 412.90000000000003, "end": 421.90000000000003, "text": " And you can see so the parallel transport is going to convert a vector from this tangent space to a vector in this other tangent space associated with some other vector space."}, {"start": 421.9, "end": 428.0, "text": " So this is going to convert from this tangent space to some other point on the manifold."}, {"start": 428.0, "end": 433.5, "text": " So there is a kind of loose analogy between these these two."}, {"start": 433.5, "end": 443.5, "text": " So that's maybe worth mentioning. OK, so now let me step back and try and give you a bit more context and what this algebraic topology is about,"}, {"start": 443.5, "end": 450.0, "text": " because this is just a particular specific like setup of algebraic topology that we'll care about."}, {"start": 450.0, "end": 458.3, "text": " So this is a vector from Michael Bronstein's blog, and it kind of introduces the wider terminology."}, {"start": 458.3, "end": 467.7, "text": " So the idea is the following. So here you have like multiple stocks of grain which are like basically tied together."}, {"start": 467.7, "end": 476.3, "text": " Getting back to our setup, these vector spaces here and algebraic structures more generally are called stocks."}, {"start": 476.3, "end": 482.2, "text": " So this is going to be called a stock. And so that's that's the stock part."}, {"start": 482.2, "end": 487.2, "text": " And then the restriction maps are what's tying together all of these stocks."}, {"start": 487.2, "end": 497.3, "text": " So that's why you'll often see this like basically a bundle of grains used to represent ideas from from algebraic from from sheaf theory,"}, {"start": 497.3, "end": 500.3, "text": " which is a branch of this field of algebraic topology."}, {"start": 500.3, "end": 507.1, "text": " And that may or may not help you memorize what the sheaf structure is about."}, {"start": 507.1, "end": 511.90000000000003, "text": " OK, but let me generalize. Let me take even like a step further and let's generalize this even more."}, {"start": 511.90000000000003, "end": 517.9, "text": " So this is how the what the informal definition of a sheaf would be."}, {"start": 517.9, "end": 529.6, "text": " So we assign to each open subset of the underlying topological space a certain algebraic structure and we specify restriction maps between them."}, {"start": 529.6, "end": 534.8000000000001, "text": " So what's a topological space? Well, topological space is a very, very general notion."}, {"start": 534.8000000000001, "end": 546.1, "text": " So that can be anything from like a line from a real line to graphs, to manifolds, to simple complexes, which are themselves a generalization of specific types of graphs."}, {"start": 546.1, "end": 550.4, "text": " We then have cellular complexes as another topological object, etc."}, {"start": 550.4, "end": 557.2, "text": " Etc. You can see that by saying this sentence, you basically mean a lot of things. It's very general. It's very abstract."}, {"start": 557.2, "end": 563.9000000000001, "text": " Then they see a certain algebraic structure. And most of you are probably familiar with vector spaces, but not that much with groups or rings."}, {"start": 563.9000000000001, "end": 571.1, "text": " But like those are some other types of objects you could kind of associate with this open subset on your topological space."}, {"start": 571.1, "end": 578.0, "text": " And finally, we specify the restriction maps so you can see that we get our set up by specifying a particular topological space."}, {"start": 578.0, "end": 582.6, "text": " So we care about graphs and we care about vector spaces on those graphs."}, {"start": 582.6, "end": 590.2, "text": " And even more specifically, we're going to be using vector spaces of the same dimensionality for each of our stocks."}, {"start": 590.2, "end": 591.9, "text": " That's additional additional detail."}, {"start": 591.9, "end": 598.4, "text": " OK, so again, briefly, topology is for those of you who are not familiar."}, {"start": 598.4, "end": 603.1, "text": " This is a loose informal definition, but it will maybe help you create some some mental model."}, {"start": 603.1, "end": 611.8000000000001, "text": " So what is important in topology is the connectivity and not the distances and or angles, whereas in geometry, we care about the distances and angles."}, {"start": 611.8, "end": 614.1999999999999, "text": " So the connectivity is the name of the game."}, {"start": 614.1999999999999, "end": 618.9, "text": " And that's why the donut and a coffee mug are the same thing for a topologist."}, {"start": 618.9, "end": 628.0, "text": " So that's like a usual joke in for at least for mathematicians like the like basically a coffee mug and a donut are the same thing."}, {"start": 628.0, "end": 632.3, "text": " But because as you can see here, both of these objects can be morphed into each other."}, {"start": 632.3, "end": 633.9, "text": " So there are these mappings."}, {"start": 633.9, "end": 638.5999999999999, "text": " I think they are called homomorphism, I guess, between like a coffee mug and a donut."}, {"start": 638.6, "end": 643.2, "text": " And the reason is we only have a single hole here, and that's what what what makes a difference."}, {"start": 643.2, "end": 649.2, "text": " So if we had two holes, then we have a different object or if we had zero holes, that would be a different object."}, {"start": 649.2, "end": 654.6, "text": " But everything else can kind of be, as you can see, morphed from from one shape to another."}, {"start": 654.6, "end": 657.2, "text": " And because of that, they are considered equivalent."}, {"start": 657.2, "end": 660.9, "text": " I also mentioned these objects called simplicial complexes."}, {"start": 660.9, "end": 669.5, "text": " If you take a simple graph, whereas by simple graph, what I mean is a graph that doesn't have any self edges nor does it have any multiple edges between two nodes."}, {"start": 669.5, "end": 671.9, "text": " So this would be this would be a simple graph."}, {"start": 671.9, "end": 679.8, "text": " Something like this would be a simple graph and a generalization of the simple graph is something called simplicial complexes."}, {"start": 679.8, "end": 682.3, "text": " You'll probably see that term thrown around."}, {"start": 682.3, "end": 686.3, "text": " So just to kind of make it to define it here."}, {"start": 686.3, "end": 692.9, "text": " And finally, if we have graphs with self edges and with multiple edges between two nodes,"}, {"start": 692.9, "end": 702.0999999999999, "text": " this is known as a multigraph with self edges and a generalization of these is called cellular complex or cellular complexes."}, {"start": 702.0999999999999, "end": 705.3, "text": " So, yeah, that's just additional context for you."}, {"start": 705.3, "end": 716.0999999999999, "text": " Finally, there is this nice statement from from from Maurice Auslender saying that she theory is the subject in which you do topology horizontally and algebra vertically."}, {"start": 716.1, "end": 724.2, "text": " OK, so that was kind of various terms and concepts related to this like branch of mathematics."}, {"start": 724.2, "end": 728.3000000000001, "text": " And now let me try and make this a bit more concrete."}, {"start": 728.3000000000001, "end": 731.9, "text": " OK, I already mentioned this paper, a very elementary introduction to sheaves."}, {"start": 731.9, "end": 735.2, "text": " And I want to make like a huge shout out to the author of this paper."}, {"start": 735.2, "end": 746.0, "text": " I think that like doing this is incredibly important, especially if you have some very abstract and for most people like alien type of a theory."}, {"start": 746.0, "end": 761.8, "text": " You really want to create a paper where you dump all of your like mental models, all of your visualizations and all of the concrete examples you use to ground some abstract concepts from that theory and make them digestible to your like brain."}, {"start": 761.8, "end": 770.4, "text": " I guess I would really love to see more of these papers for each of like different branches of more abstract pure mathematics."}, {"start": 770.4, "end": 777.8, "text": " And I guess the reason people are not doing this usually is because it's not that rigorous and then maybe your peers will judge you or whatnot."}, {"start": 777.8, "end": 781.4, "text": " But like like I urge you, this is like so important."}, {"start": 781.4, "end": 788.0, "text": " This paper made it much like more visceral for me what she theory is about."}, {"start": 788.0, "end": 792.3, "text": " So let's read this abstract and then let's see a couple of figures from from this particular paper."}, {"start": 792.3, "end": 797.8, "text": " So here we give a simple and approachable explanation to the mathematical objects called sheaves."}, {"start": 797.8, "end": 807.3, "text": " This paper presents tangible and concrete examples so that readers will be able to further explore these concepts on their own in more abstraction and application."}, {"start": 807.3, "end": 820.3, "text": " So for me and I know for for many people, I know it's much easier to start from a concrete example and then abstract away rather than start in the abstract space and then try and understand what's going on and where can I relate this to."}, {"start": 820.3, "end": 823.0, "text": " So I think this is that's why this paper is so important."}, {"start": 823.0, "end": 828.0, "text": " So as they say here that the paper this paper is very is a very non rigorous."}, {"start": 828.0, "end": 832.2, "text": " It's a non rigorous loose and extremely basic."}, {"start": 832.2, "end": 835.4, "text": " And I would also add extremely useful introduction to sheaves."}, {"start": 835.4, "end": 844.4, "text": " This is meant to be a guide to gaining intuition, which is so important about sheaves, what they look like and how they work."}, {"start": 844.4, "end": 853.1999999999999, "text": " So after reading this paper, someone can jump into the extremely abstract definitions and examples seen in textbooks with this some idea of what is going on."}, {"start": 853.1999999999999, "end": 871.0, "text": " OK, so let's get back to our particular example of a sheaf where we care about graphs as that underlying topological object and where we care about vector spaces with the same number of dimensions as our particular algebraic space object."}, {"start": 871.0, "end": 879.6, "text": " OK, so here we can see that we have, for example, this this particular stock for this node is going to have two dimensions."}, {"start": 879.6, "end": 883.9, "text": " It's going to be two one and this other stock is going to be minus two ten three."}, {"start": 883.9, "end": 889.0, "text": " So in this particular example, they did use different dimensionalities, but that does not matter that much."}, {"start": 889.0, "end": 892.7, "text": " Then we have they've specified a particular restriction maps."}, {"start": 892.7, "end": 896.1, "text": " You can see they're just simple linear maps as represented by this matrix."}, {"start": 896.1, "end": 897.6, "text": " We have a different one here."}, {"start": 897.6, "end": 902.2, "text": " And if we take this vector and we map it, we get we end up with this vector here."}, {"start": 902.2, "end": 904.7, "text": " OK, so let me just change the color."}, {"start": 904.7, "end": 906.4, "text": " So we end up with this one here."}, {"start": 906.4, "end": 913.8000000000001, "text": " And if we take this vector and we map it with its restriction map, we end up with this particular vector here."}, {"start": 913.8000000000001, "end": 921.7, "text": " OK, and so the important thing I want you to notice here is that these two agree, which is not the case in general, obviously."}, {"start": 921.7, "end": 927.5, "text": " And this is super like this is a vital idea in this in this sheaf theory."}, {"start": 927.5, "end": 935.4, "text": " This agreement and to just to make this a bit more concrete, let me give you a particular interpretation of what this could mean."}, {"start": 935.4, "end": 942.6, "text": " So imagine this graph represents a group of people, a social network, and imagine these stocks here."}, {"start": 942.6, "end": 952.0, "text": " So the vectors associated with our nodes, which themselves are basically represent certain individuals in the society."}, {"start": 952.0, "end": 955.0, "text": " So this stock is just opinion space."}, {"start": 955.0, "end": 958.3, "text": " So you can imagine of this as an opinion vector."}, {"start": 958.3, "end": 964.3, "text": " Basically, minus two would mean this particular person thinks negatively about some topic X."}, {"start": 964.3, "end": 966.3, "text": " I don't know, whatever like politics."}, {"start": 966.3, "end": 975.7, "text": " Then this means that this same person thinks extremely positively of some other topic Y and so on, etc."}, {"start": 975.7, "end": 978.1, "text": " So we have three for some other topics."}, {"start": 978.1, "end": 978.8, "text": " Same here."}, {"start": 978.8, "end": 989.1999999999999, "text": " And what this this model does is by mapping by mapping this opinion vector into this so-called discourse space."}, {"start": 989.1999999999999, "end": 994.1999999999999, "text": " So this thing here, they refer to this as a discourse space."}, {"start": 994.1999999999999, "end": 995.8, "text": " Here we achieved an agreement."}, {"start": 995.8, "end": 1004.5999999999999, "text": " So even though the personal private opinion vectors are not the same after we express them, we get to an agreement."}, {"start": 1004.5999999999999, "end": 1007.6999999999999, "text": " And that's pretty much the only way how a society can function."}, {"start": 1007.7, "end": 1013.0, "text": " We have to roughly have similar like agreements across across certain topics."}, {"start": 1013.0, "end": 1014.6, "text": " Otherwise, everything explodes."}, {"start": 1014.6, "end": 1024.2, "text": " And so this could be one particular interpretation of what is going on and why it is important to find such vectors here."}, {"start": 1024.2, "end": 1032.4, "text": " So such vectors, such stocks, such that we have an agreement across all of the edges of our graph."}, {"start": 1032.4, "end": 1033.6000000000001, "text": " So that's the idea there."}, {"start": 1033.6, "end": 1044.8, "text": " Okay, so now again, let me take a step back and just make this a bit more general because I assume that most of you have no idea of what algebraic topology is."}, {"start": 1044.8, "end": 1050.1999999999998, "text": " And so that's why I'm giving you just a lot of examples and I also link a bunch of resources down in the video description."}, {"start": 1050.1999999999998, "end": 1051.6999999999998, "text": " So do check them out."}, {"start": 1051.6999999999998, "end": 1055.8, "text": " Okay, let me give you another example and then we'll get to the rest of the paper."}, {"start": 1055.8, "end": 1058.0, "text": " And hopefully it's going to be easier to understand after this."}, {"start": 1058.0, "end": 1061.0, "text": " So for a topological space X."}, {"start": 1061.0, "end": 1063.1999999999998, "text": " So we are again now more general."}, {"start": 1063.2, "end": 1064.4, "text": " We're not talking about graphs."}, {"start": 1064.4, "end": 1068.0, "text": " We're talking about general topological spaces."}, {"start": 1068.0, "end": 1075.5, "text": " A sheaf of a billion groups on X assigns each open set of X to an abelian group."}, {"start": 1075.5, "end": 1086.5, "text": " Okay, so this time our abstract object is in a billion group and we have some open set of a topological space as our underlying horizontal object."}, {"start": 1086.5, "end": 1088.8, "text": " So which a billion group you ask."}, {"start": 1088.8, "end": 1097.3, "text": " So here it will be the group of continuous functions from U, which is the open set to R."}, {"start": 1097.3, "end": 1102.3, "text": " That is for an open set U, which is a subset of our topological space."}, {"start": 1102.3, "end": 1105.6, "text": " The stock of U is the group this one."}, {"start": 1105.6, "end": 1113.2, "text": " So it's a set of functions F of continuous functions F that map from that open subset to R."}, {"start": 1113.2, "end": 1115.8, "text": " Okay, just to make this a bit more concrete."}, {"start": 1115.8, "end": 1118.8999999999999, "text": " Here is a particular example of what that means."}, {"start": 1118.8999999999999, "end": 1124.8, "text": " We have an open subset here U as you can see here."}, {"start": 1124.8, "end": 1127.1, "text": " And we you can see like us."}, {"start": 1127.1, "end": 1130.8, "text": " This is a set of continuous functions defined there."}, {"start": 1130.8, "end": 1138.5, "text": " So this thing here would be the stock and by picking so picking a particular function from this space here."}, {"start": 1138.5, "end": 1144.3999999999999, "text": " So maybe picking this one is the same thing as picking a particular vector here."}, {"start": 1144.4, "end": 1147.4, "text": " Okay, we're just dealing with different objects."}, {"start": 1147.4, "end": 1151.0, "text": " But like this isn't a concrete instantiation on the vector space."}, {"start": 1151.0, "end": 1155.1000000000001, "text": " And this is a concrete instantiation in this particular a billion group."}, {"start": 1155.1000000000001, "end": 1164.0, "text": " Okay, so so along with the point wise addition, this is this is basically a group and for an open set V,"}, {"start": 1164.0, "end": 1173.7, "text": " which is a subset of U the restriction map from U to V as denoted like this is actually really simple for an"}, {"start": 1173.7, "end": 1178.9, "text": " element F of F of U, which is a continuous function."}, {"start": 1178.9, "end": 1184.5, "text": " This restriction map is the restriction of F from U to V."}, {"start": 1184.5, "end": 1185.9, "text": " Okay, so I'm going to stop there."}, {"start": 1185.9, "end": 1187.4, "text": " So what it means is the following."}, {"start": 1187.4, "end": 1194.8, "text": " So after we apply this restriction map, we end up so you basically map the following thing is you still map."}, {"start": 1194.8, "end": 1196.5, "text": " So let me take a color like this."}, {"start": 1196.5, "end": 1199.8, "text": " So you'll map this thing."}, {"start": 1199.8, "end": 1204.7, "text": " On to this thing here. So basically you just constrain."}, {"start": 1204.7, "end": 1207.2, "text": " So before that your function was defined."}, {"start": 1207.2, "end": 1210.2, "text": " This was a domain of your function after this restriction map."}, {"start": 1210.2, "end": 1217.3, "text": " You just redefine it here, but you have the same you have the same function in this in this particular domain."}, {"start": 1217.3, "end": 1221.3, "text": " So it's kind of trivial, but we'll see why why that why that makes it makes sense."}, {"start": 1221.3, "end": 1229.6, "text": " But again, by doing this, what we've done is we took this function, which is in this analogy like this particular vector."}, {"start": 1229.6, "end": 1233.1999999999998, "text": " And then we mapped it all the way to here."}, {"start": 1233.1999999999998, "end": 1235.1, "text": " So this time we don't have this intermediate step."}, {"start": 1235.1, "end": 1236.1999999999998, "text": " We just map it."}, {"start": 1236.1999999999998, "end": 1239.6999999999998, "text": " We just find the inverse mapping here and we map from here to here."}, {"start": 1239.6999999999998, "end": 1241.1, "text": " Okay."}, {"start": 1241.1, "end": 1245.1999999999998, "text": " Now with this definition, let's see how we define the agreement this time."}, {"start": 1245.1999999999998, "end": 1254.5, "text": " So here you can see here is a bunch of a bunch of open sets, which you can see those were nodes in our previous example."}, {"start": 1254.5, "end": 1259.3, "text": " And for each of those open sets, we associated a particular function."}, {"start": 1259.3, "end": 1264.6, "text": " So that's a concrete instance from our group, which is the algebraic structure we care about in this example."}, {"start": 1264.6, "end": 1269.8, "text": " So that will be a particular vector in this for this particular node."}, {"start": 1269.8, "end": 1274.5, "text": " We'd associate a particular vector here for this particular open set."}, {"start": 1274.5, "end": 1276.8, "text": " We associate a particular function."}, {"start": 1276.8, "end": 1278.6, "text": " So how do we get to an agreement?"}, {"start": 1278.6, "end": 1283.2, "text": " So here is what the agreement looks like for this particular sheath."}, {"start": 1283.2, "end": 1286.3999999999999, "text": " We basically get a continuous function."}, {"start": 1286.4, "end": 1292.9, "text": " And if you think about it, it makes sense because so after you might say, let's take let's take one example."}, {"start": 1292.9, "end": 1299.5, "text": " Let's take, for example, this this purple open space from here to here."}, {"start": 1299.5, "end": 1306.9, "text": " And if we do the restriction map, if we apply the mapping to this other orange space, so this one here, let me just change the color."}, {"start": 1306.9, "end": 1311.3000000000002, "text": " So if we map there, we know that the function needs to remain the same."}, {"start": 1311.3000000000002, "end": 1314.4, "text": " So that's that's how we define our mapping is going to be here."}, {"start": 1314.4, "end": 1320.4, "text": " And the only way that this small function agrees with this function here is that they perfectly align."}, {"start": 1320.4, "end": 1324.9, "text": " And because you can have multiple of these open sets here which intersect with each other,"}, {"start": 1324.9, "end": 1332.6000000000001, "text": " the only solution where we have this agreement for this particular sheath is if we have a continuous function on this on this space."}, {"start": 1332.6000000000001, "end": 1335.8000000000002, "text": " OK, so hopefully that gives you some understanding of what's going on."}, {"start": 1335.8000000000002, "end": 1338.5, "text": " I did get into a bit more nitty gritty details than I needed."}, {"start": 1338.5, "end": 1341.5, "text": " But like I just wanted you to understand the whole point."}, {"start": 1341.5, "end": 1349.7, "text": " I want you to take out from this explanation is agreement in in in sheath theory is a very, very important concept."}, {"start": 1349.7, "end": 1362.7, "text": " So agreement here leads to a very nice like continuous function agreement here leads to people and society being a functional society instead of just breaking apart because people are polarized."}, {"start": 1362.7, "end": 1368.0, "text": " OK, guys, let me quickly give you one more take of how this works in case you did not understand it."}, {"start": 1368.0, "end": 1369.5, "text": " I'm going to make it much more pictorial."}, {"start": 1369.5, "end": 1372.9, "text": " So imagine we focus on on these two open sets."}, {"start": 1372.9, "end": 1375.8, "text": " So we have this open set here."}, {"start": 1375.8, "end": 1377.3, "text": " And we have this orange one here."}, {"start": 1377.3, "end": 1385.5, "text": " OK, so imagine instead if on this orange open space, we had a function defined like this."}, {"start": 1385.5, "end": 1388.1, "text": " So we pick a value from our stock and it looks like this."}, {"start": 1388.1, "end": 1394.7, "text": " OK, and imagine for that this this bigger open subset, we have exactly this function here."}, {"start": 1394.7, "end": 1396.1, "text": " So this is the value we took."}, {"start": 1396.1, "end": 1401.1999999999998, "text": " So after we take so we take the function from you from this you three."}, {"start": 1401.1999999999998, "end": 1407.6999999999998, "text": " So from this bigger open space, we apply the restriction map onto this smaller open space."}, {"start": 1407.6999999999998, "end": 1408.6, "text": " And what do we get?"}, {"start": 1408.6, "end": 1414.6, "text": " Well, we get this we get this thing here because that's how we define the restriction map."}, {"start": 1414.6, "end": 1420.1999999999998, "text": " And you can see here that there is no agreement between that and this thing here."}, {"start": 1420.1999999999998, "end": 1425.6, "text": " OK, and the only way we can get an agreement is if we have a continuous function like this."}, {"start": 1425.6, "end": 1430.6999999999998, "text": " And yeah, hopefully that now makes it a bit more visceral and understandable."}, {"start": 1430.6999999999998, "end": 1432.3999999999999, "text": " Let's get back to the paper."}, {"start": 1432.3999999999999, "end": 1437.1, "text": " Let me briefly just introduce you to the formal terminology here."}, {"start": 1437.1, "end": 1439.3, "text": " So this is how it looks like."}, {"start": 1439.3, "end": 1446.1999999999998, "text": " Definition one, a cellular sheaf, which is a tuple containing a graph and this big F,"}, {"start": 1446.1999999999998, "end": 1453.5, "text": " which is the sheaf structure on an undirected graph G, which consists of a set of vertices"}, {"start": 1453.5, "end": 1463.3, "text": " and set of edges consists of so one a vector space F of V for each node from the basically set of nodes,"}, {"start": 1463.3, "end": 1469.5, "text": " a vector space F of E for each edge in the set of edges."}, {"start": 1469.5, "end": 1475.5, "text": " And these are called stocks again, a linear map as denoted like this."}, {"start": 1475.5, "end": 1481.8, "text": " So it maps so that the this means edge E, which is incident."}, {"start": 1481.8, "end": 1487.8, "text": " So that's this this this funny symbol with a triangle stuff."}, {"start": 1487.8, "end": 1489.5, "text": " So this means they are incident."}, {"start": 1489.5, "end": 1492.1, "text": " So this edge is incident to this node."}, {"start": 1492.1, "end": 1497.5, "text": " So it maps from the stock of V onto the stock of E."}, {"start": 1497.5, "end": 1501.7, "text": " So we define that for each incident node node edge pair."}, {"start": 1501.7, "end": 1503.8, "text": " So this is what what the sheaf is."}, {"start": 1503.8, "end": 1509.3, "text": " You define these maps, you define these spaces and you've got a sheaf."}, {"start": 1509.3, "end": 1513.2, "text": " Okay, so again, I mentioned these are the stocks."}, {"start": 1513.2, "end": 1514.6, "text": " These are the restriction maps."}, {"start": 1514.6, "end": 1516.6, "text": " The linear map is a restriction map."}, {"start": 1516.6, "end": 1519.2, "text": " And now we have this concept of a zero coaching."}, {"start": 1519.2, "end": 1528.3, "text": " So zero coaching as denoted with C subscript zero is basically defined as this O plus,"}, {"start": 1528.3, "end": 1531.1, "text": " which is a direct sum of different stocks."}, {"start": 1531.1, "end": 1538.2, "text": " And you can think of this as basically a concatenation of these various vector vector spaces."}, {"start": 1538.2, "end": 1544.9, "text": " And then you can define a signal, an element of that zero coaching this bold X here,"}, {"start": 1544.9, "end": 1549.2, "text": " which is basically a collection of stocks for each of the nodes."}, {"start": 1549.2, "end": 1556.3, "text": " Okay, that's one important space you need to to to have in mind."}, {"start": 1556.3, "end": 1564.0, "text": " Let's continue on a particularly important subspace of this zero coaching space is the space of global sections."}, {"start": 1564.0, "end": 1568.6, "text": " And we've seen this and you'll understand what this exactly means in a second."}, {"start": 1568.6, "end": 1571.9, "text": " So this is the this is the agreement thing I was I was mentioning."}, {"start": 1571.9, "end": 1580.6, "text": " So this global section space denoted as H zero, which stands for zero cohomology."}, {"start": 1580.6, "end": 1585.0, "text": " That's also how you'll see this space referred to."}, {"start": 1585.0, "end": 1593.0, "text": " So it's basically a set of these signals of these axes such that and those axes belong to this zero coaching."}, {"start": 1593.0, "end": 1600.1, "text": " So it's a set of these axes such that we have an agreement along every single edge of our graph."}, {"start": 1600.1, "end": 1610.6, "text": " OK, that's the that's the idea. So we have we apply the restriction map onto our feature vector associated with with with node V."}, {"start": 1610.6, "end": 1617.3, "text": " And we apply a different restriction map to node use feature vector."}, {"start": 1617.3, "end": 1620.5, "text": " And we have to have the same we have to have an equality here."}, {"start": 1620.5, "end": 1632.1, "text": " That's when we achieve the agreement and then mention here containing those private opinions X for which all neighbors agree with each other in the discourse discourse space."}, {"start": 1632.1, "end": 1640.6, "text": " So that will be one particular interpretation of what this whole abstract global section space means."}, {"start": 1640.6, "end": 1645.5, "text": " So, again, remember this one space of global sections."}, {"start": 1645.5, "end": 1656.1, "text": " So those are going to be all of the possible signals on our nodes that leads to the agreement across all of the edges on our graph."}, {"start": 1656.1, "end": 1658.5, "text": " That's it. As simple as that."}, {"start": 1658.5, "end": 1661.0, "text": " OK, let's continue here."}, {"start": 1661.0, "end": 1663.0, "text": " Definition two. And this is very important."}, {"start": 1663.0, "end": 1665.0, "text": " I'm going to spend some time here."}, {"start": 1665.0, "end": 1674.9, "text": " So the sheaf loplation of a sheaf is a linear map from the space of zero coaching to the spaces your coachings defined node wise."}, {"start": 1674.9, "end": 1676.3000000000002, "text": " Why this equation?"}, {"start": 1676.3000000000002, "end": 1682.9, "text": " And now this might seem scary, but it's not because if you know anything about graph,"}, {"start": 1682.9, "end": 1686.7, "text": " I'm only familiar with graph GCN's, for example."}, {"start": 1686.7, "end": 1691.9, "text": " This is just going to be this is just a generalization of the very same thing we already saw there."}, {"start": 1691.9, "end": 1698.5, "text": " If you if you're not familiar with with those like papers and with that theory, go check out my graph ML playlist."}, {"start": 1698.5, "end": 1703.2, "text": " It's going to be immensely helpful for you to understand this video."}, {"start": 1703.2, "end": 1706.7, "text": " So imagine if these restriction maps were just scalars."}, {"start": 1706.7, "end": 1718.3, "text": " This was a one. If this was a one, if this was a one, you just have a sum containing differences between the central node V minus its neighbors."}, {"start": 1718.3, "end": 1722.7, "text": " And that's something we've seen in the graph loplation matrix."}, {"start": 1722.7, "end": 1730.3, "text": " So if you multiply your your your basically set of your feature vectors with all graph loplation, you end up with such an equation."}, {"start": 1730.3, "end": 1732.8, "text": " So I'm going to make this a bit more complete."}, {"start": 1732.8, "end": 1736.5, "text": " So let me give you a particular example to and let's kind of this is very important."}, {"start": 1736.5, "end": 1740.7, "text": " This this shift location is one of the crucial objects in this paper."}, {"start": 1740.7, "end": 1745.6, "text": " So let me give you a bit more concrete examples here."}, {"start": 1745.6, "end": 1747.7, "text": " So let's imagine we have a graph like this."}, {"start": 1747.7, "end": 1751.8999999999999, "text": " We have three nodes and they're connected like this."}, {"start": 1751.8999999999999, "end": 1754.6, "text": " So this is a node one. This is no two."}, {"start": 1754.6, "end": 1760.3999999999999, "text": " This is no three. Let's form a loplation matrix basically."}, {"start": 1760.4, "end": 1762.8000000000002, "text": " So loplation is defined the following way."}, {"start": 1762.8000000000002, "end": 1764.3000000000002, "text": " The plation is usually defined."}, {"start": 1764.3000000000002, "end": 1766.3000000000002, "text": " There are multiple ways how you can define it."}, {"start": 1766.3000000000002, "end": 1770.0, "text": " But this is one way. This is so-called I think combinatorial loplation."}, {"start": 1770.0, "end": 1776.0, "text": " So we take the degree matrix D and you subtract away the adjacency matrix A."}, {"start": 1776.0, "end": 1778.7, "text": " So what's the what's a let's make that more concrete."}, {"start": 1778.7, "end": 1781.2, "text": " So let me give you for this particular example."}, {"start": 1781.2, "end": 1785.0, "text": " This means the following. So D is going to be the following matrix."}, {"start": 1785.0, "end": 1787.2, "text": " So it's going to be a three by three matrix."}, {"start": 1787.2, "end": 1792.8, "text": " It's a diagonal matrix and on each of the diagonals you basically contain"}, {"start": 1792.8, "end": 1796.0, "text": " how many neighbors does that particular node has."}, {"start": 1796.0, "end": 1799.9, "text": " So one has only one neighbor and we're going to have zeros here."}, {"start": 1799.9, "end": 1803.3, "text": " So we're going to only have basically elements on the on the diagonal."}, {"start": 1803.3, "end": 1805.7, "text": " So let me just kind of fill that in."}, {"start": 1805.7, "end": 1807.3, "text": " So what does what goes here?"}, {"start": 1807.3, "end": 1809.3, "text": " So here we take a look at node two."}, {"start": 1809.3, "end": 1810.5, "text": " It has only one neighbor."}, {"start": 1810.5, "end": 1812.8, "text": " That's node three. That's why we input one here."}, {"start": 1812.8, "end": 1815.0, "text": " And finally node three has two neighbors."}, {"start": 1815.0, "end": 1817.9, "text": " And that's why the degree of this node is two."}, {"start": 1817.9, "end": 1819.7, "text": " Okay, so we have two."}, {"start": 1819.7, "end": 1821.0, "text": " So that's the degree matrix."}, {"start": 1821.0, "end": 1823.5, "text": " The A matrix is just your adjacency matrix."}, {"start": 1823.5, "end": 1826.4, "text": " So basically your connectivity who is connected to whom."}, {"start": 1826.4, "end": 1829.3, "text": " So this is going to be a."}, {"start": 1829.3, "end": 1832.3, "text": " So node one is only connected to node three."}, {"start": 1832.3, "end": 1835.6, "text": " That's why we're going to have one here and we have zero and zero here."}, {"start": 1835.6, "end": 1837.8, "text": " No two is only connected to node three again."}, {"start": 1837.8, "end": 1840.0, "text": " So we have one here zero zero."}, {"start": 1840.0, "end": 1843.2, "text": " And finally node three is connected to node one as you can see here"}, {"start": 1843.2, "end": 1847.5, "text": " and it's connected to node two and that's why we add ones here and we have zero here."}, {"start": 1847.5, "end": 1850.1000000000001, "text": " Finally in order to get the loplation matrix."}, {"start": 1850.1000000000001, "end": 1851.2, "text": " Let's see what we do."}, {"start": 1851.2, "end": 1854.5, "text": " We just subtract away these two and we get the following thing."}, {"start": 1854.5, "end": 1858.0, "text": " We basically end up with this matrix."}, {"start": 1858.0, "end": 1859.6000000000001, "text": " Let me just kind of make it here."}, {"start": 1859.6000000000001, "end": 1867.6000000000001, "text": " So we have one one two and then we have minus one here minus one here minus one minus one."}, {"start": 1867.6000000000001, "end": 1869.1000000000001, "text": " And we have zeros elsewhere."}, {"start": 1869.1000000000001, "end": 1872.2, "text": " Okay, so why is this important?"}, {"start": 1872.2, "end": 1873.2, "text": " Why is this interesting?"}, {"start": 1873.2, "end": 1881.2, "text": " Well, let's see what happens if we multiply the set of feature vectors of node feature vectors with this loplation."}, {"start": 1881.2, "end": 1882.8, "text": " So this is L."}, {"start": 1882.8, "end": 1884.6000000000001, "text": " Let's construct the X."}, {"start": 1884.6000000000001, "end": 1888.5, "text": " So if we associate let's let's say for the sake of simplicity,"}, {"start": 1888.5, "end": 1895.0, "text": " we only have basically scalars associated with all of these like nodes."}, {"start": 1895.0, "end": 1898.7, "text": " So we have scalar X one X two X three."}, {"start": 1898.7, "end": 1901.4, "text": " Let's kind of stick them together here."}, {"start": 1901.4, "end": 1902.7, "text": " We have X one."}, {"start": 1902.7, "end": 1903.9, "text": " We have X two."}, {"start": 1903.9, "end": 1905.3000000000002, "text": " We have X three."}, {"start": 1905.3000000000002, "end": 1907.1000000000001, "text": " What do we get if we multiply these?"}, {"start": 1907.1000000000001, "end": 1908.8000000000002, "text": " So what do we get here?"}, {"start": 1908.8000000000002, "end": 1912.4, "text": " So we basically have and I'm going to just ignore the first two rows."}, {"start": 1912.4, "end": 1914.0, "text": " I'm just going to focus on this one."}, {"start": 1914.0, "end": 1916.7, "text": " So we have two X three."}, {"start": 1916.7, "end": 1921.8000000000002, "text": " Okay, minus X one minus X two."}, {"start": 1921.8000000000002, "end": 1925.6000000000001, "text": " And now for the moment,"}, {"start": 1925.6, "end": 1932.1999999999998, "text": " I've been trying to get to is let's make a comparison between this thing here."}, {"start": 1932.1999999999998, "end": 1934.0, "text": " And this thing here."}, {"start": 1934.0, "end": 1935.3999999999999, "text": " They have the same structure."}, {"start": 1935.3999999999999, "end": 1939.1, "text": " This thing is just a generalization of this thing here."}, {"start": 1939.1, "end": 1939.8999999999999, "text": " So as I said,"}, {"start": 1939.8999999999999, "end": 1943.3999999999999, "text": " if these restriction maps were just a simple scalars,"}, {"start": 1943.3999999999999, "end": 1947.8999999999999, "text": " so that means if our sheath structure is trivial in that particular case,"}, {"start": 1947.8999999999999, "end": 1950.6999999999998, "text": " we fall back to a graph loplation."}, {"start": 1950.6999999999998, "end": 1953.8, "text": " So let's imagine this is one."}, {"start": 1953.8, "end": 1954.5, "text": " This is one."}, {"start": 1954.5, "end": 1955.5, "text": " This is one."}, {"start": 1955.5, "end": 1958.2, "text": " And let's imagine we focus on node V."}, {"start": 1958.2, "end": 1959.7, "text": " V equals three."}, {"start": 1959.7, "end": 1964.0, "text": " So we end up with a sum where V is equal to three."}, {"start": 1964.0, "end": 1966.2, "text": " And we look at the incident edges,"}, {"start": 1966.2, "end": 1969.1, "text": " which are going to be this edge and this edge here."}, {"start": 1969.1, "end": 1970.2, "text": " So we have a sum."}, {"start": 1970.2, "end": 1975.5, "text": " So we have here we have X three minus first edge."}, {"start": 1975.5, "end": 1977.4, "text": " So minus X one."}, {"start": 1977.4, "end": 1978.9, "text": " And then we have additional term."}, {"start": 1978.9, "end": 1983.3, "text": " So plus X three minus this time X two."}, {"start": 1983.3, "end": 1987.3, "text": " And as you can see, we end up with two X three minus X one minus X two,"}, {"start": 1987.3, "end": 1990.1, "text": " which is the same thing as this thing here."}, {"start": 1990.1, "end": 1995.2, "text": " Okay, so hopefully now the connection is clear."}, {"start": 1995.2, "end": 1997.1, "text": " By introducing this sheath structure,"}, {"start": 1997.1, "end": 2001.6, "text": " we generalized our graph loplation into this thing called sheath loplation."}, {"start": 2001.6, "end": 2004.1, "text": " And that's everything you need to know for now."}, {"start": 2004.1, "end": 2006.3, "text": " Let's see a bit more information about sheath loplation."}, {"start": 2006.3, "end": 2009.5, "text": " So it's an ND times ND matrix."}, {"start": 2009.5, "end": 2011.1, "text": " Why ND times ND?"}, {"start": 2011.1, "end": 2013.5, "text": " Well, in general, I mean, not in general."}, {"start": 2013.5, "end": 2017.3999999999999, "text": " In this particular case where we have a trivial sheath structure,"}, {"start": 2017.3999999999999, "end": 2019.3999999999999, "text": " then we have N times N."}, {"start": 2019.3999999999999, "end": 2021.1, "text": " So we saw that right here."}, {"start": 2021.1, "end": 2024.6999999999998, "text": " So it's D because the dimensionality of a stock is D."}, {"start": 2024.6999999999998, "end": 2026.8, "text": " That's why we have ND times ND."}, {"start": 2026.8, "end": 2028.5, "text": " Okay."}, {"start": 2028.5, "end": 2031.8999999999999, "text": " So then they say when the vector spaces are set to R,"}, {"start": 2031.8999999999999, "end": 2034.6999999999998, "text": " so the dimensionality is equal to one."}, {"start": 2034.6999999999998, "end": 2038.0, "text": " And the linear maps are identity maps over R."}, {"start": 2038.0, "end": 2042.5, "text": " The underlying sheath is trivial and one recovers the well-known N times N"}, {"start": 2042.5, "end": 2045.5, "text": " graph loplation matrix and its normalized version."}, {"start": 2045.5, "end": 2047.6, "text": " And we'll care about the normalized version."}, {"start": 2047.6, "end": 2049.6, "text": " And the same thing for,"}, {"start": 2049.6, "end": 2053.7, "text": " this is the normalized version of the graph of the sheath loplation."}, {"start": 2053.7, "end": 2057.6, "text": " And what this sentence says is basically the thing I just explained."}, {"start": 2057.6, "end": 2058.9, "text": " We just made this connection."}, {"start": 2058.9, "end": 2060.1, "text": " This is a special case."}, {"start": 2060.1, "end": 2063.1, "text": " The graph loplation is a special case of sheath loplation."}, {"start": 2063.1, "end": 2064.2, "text": " Okay."}, {"start": 2064.2, "end": 2066.4, "text": " Next up, they say the following, and this is important."}, {"start": 2066.4, "end": 2072.6, "text": " Harmonic signals have perfect agreement of opinions with respect to the sheath"}, {"start": 2072.6, "end": 2079.3, "text": " structure, i.e. if you multiply those signals with the sheath loplation,"}, {"start": 2079.3, "end": 2082.4, "text": " you end up having a zero vector."}, {"start": 2082.4, "end": 2083.5, "text": " And that makes sense, right?"}, {"start": 2083.5, "end": 2085.2000000000003, "text": " So if we have an agreement here,"}, {"start": 2085.2000000000003, "end": 2090.8, "text": " if X1 and X2 are in agreement with X3, then we'll have zeros here."}, {"start": 2090.8, "end": 2093.5, "text": " So if we're in agreement, all of these are going to be,"}, {"start": 2093.5, "end": 2094.5, "text": " let me change the color."}, {"start": 2094.5, "end": 2095.7000000000003, "text": " So all of these are going to be zero."}, {"start": 2095.7, "end": 2097.7999999999997, "text": " Zero, zero, if we have agreement."}, {"start": 2097.7999999999997, "end": 2100.3999999999996, "text": " And that's why, so L times X equals zero."}, {"start": 2100.3999999999996, "end": 2101.6, "text": " That's what I state here."}, {"start": 2101.6, "end": 2105.2999999999997, "text": " This is just like sheath loplation instead of a simple loplation."}, {"start": 2105.2999999999997, "end": 2108.3999999999996, "text": " And the name is kind of, I guess, indicative."}, {"start": 2108.3999999999996, "end": 2111.1, "text": " I'm not sure whether the name came from this fact,"}, {"start": 2111.1, "end": 2115.0, "text": " but like the fact that we have an agreement that all of these signals are"}, {"start": 2115.0, "end": 2119.7999999999997, "text": " kind of in equilibrium, that's why these are called harmonic signals."}, {"start": 2119.7999999999997, "end": 2124.8999999999996, "text": " Not completely sure, but I suspect, I strongly suspect that may be the case."}, {"start": 2124.9, "end": 2128.7000000000003, "text": " Theorem 3 just states that this space of global sections,"}, {"start": 2128.7000000000003, "end": 2131.1, "text": " which we saw a couple of minutes ago,"}, {"start": 2131.1, "end": 2136.7000000000003, "text": " and the kernel of this sheath loplation are isomorphic as vector spaces."}, {"start": 2136.7000000000003, "end": 2138.0, "text": " So let me kind of break this down."}, {"start": 2138.0, "end": 2139.4, "text": " Don't be scared here."}, {"start": 2139.4, "end": 2143.8, "text": " So isomorphic just means a fancy way of saying these two vector spaces are the same."}, {"start": 2143.8, "end": 2146.4, "text": " So these two objects are the same thing, really."}, {"start": 2146.4, "end": 2148.9, "text": " So why the kernel space?"}, {"start": 2148.9, "end": 2150.1, "text": " So this is the kernel space."}, {"start": 2150.1, "end": 2155.2, "text": " So basically the set of X's that are mapped by this map,"}, {"start": 2155.2, "end": 2157.9, "text": " by the sheath loplation into the zero vector,"}, {"start": 2157.9, "end": 2160.0, "text": " that's what's known as the kernel space."}, {"start": 2160.0, "end": 2163.1, "text": " And that's how we define the H0 as well."}, {"start": 2163.1, "end": 2166.9, "text": " If you remember, these basically mean the same thing."}, {"start": 2166.9, "end": 2169.5, "text": " Okay, enough rambling."}, {"start": 2169.5, "end": 2172.2999999999997, "text": " Let me try and make this a bit more concrete."}, {"start": 2172.2999999999997, "end": 2175.2999999999997, "text": " And let's make some connections."}, {"start": 2175.2999999999997, "end": 2177.7999999999997, "text": " This is how the sheath loplation looks like."}, {"start": 2177.8, "end": 2180.3, "text": " So it's going to be a block matrix."}, {"start": 2180.3, "end": 2185.9, "text": " And these blocks are D times D because the stock is D dimensional."}, {"start": 2185.9, "end": 2188.3, "text": " And you can see how the structure looks like."}, {"start": 2188.3, "end": 2191.1000000000004, "text": " So we have, so on the main diagonal,"}, {"start": 2191.1000000000004, "end": 2196.0, "text": " we're going to have these sums of basically,"}, {"start": 2196.0, "end": 2197.5, "text": " this is the restriction map,"}, {"start": 2197.5, "end": 2201.8, "text": " multiplied by the transpose of that restriction map."}, {"start": 2201.8, "end": 2207.5, "text": " Off the main diagonal, we're going to have minus restriction map of node V."}, {"start": 2207.5, "end": 2211.1, "text": " So this is V. And here we have a restriction map of node U,"}, {"start": 2211.1, "end": 2215.2, "text": " because here we have, this slot corresponds to UV."}, {"start": 2215.2, "end": 2216.7, "text": " That's why we have these two."}, {"start": 2216.7, "end": 2219.8, "text": " And if you think about it, this construct makes sense"}, {"start": 2219.8, "end": 2222.5, "text": " because that's how you end up with particular,"}, {"start": 2222.5, "end": 2224.4, "text": " with this equation here."}, {"start": 2224.4, "end": 2227.9, "text": " That's how we end up with this whole expression here."}, {"start": 2227.9, "end": 2233.8, "text": " So you can see that if you just kind of ignore the X's,"}, {"start": 2233.8, "end": 2236.6, "text": " we have the sum of these restriction maps"}, {"start": 2236.6, "end": 2242.0, "text": " and we have this minus restriction map of U and restriction map of V."}, {"start": 2242.0, "end": 2245.5, "text": " And if you just kind of add a vector here,"}, {"start": 2245.5, "end": 2249.9, "text": " so if we add a vector here,"}, {"start": 2249.9, "end": 2255.7999999999997, "text": " and that's going to be our Rx from this zero co-chain space."}, {"start": 2255.7999999999997, "end": 2257.9, "text": " So we'll have vectors here."}, {"start": 2257.9, "end": 2260.9, "text": " So this is going to be D dimensional."}, {"start": 2260.9, "end": 2263.7999999999997, "text": " So this is going to be D dimensional."}, {"start": 2263.7999999999997, "end": 2264.7999999999997, "text": " This is D dimensional."}, {"start": 2264.7999999999997, "end": 2266.2999999999997, "text": " And here we just have a single dimension."}, {"start": 2266.3, "end": 2267.8, "text": " I kind of made it a bit wider,"}, {"start": 2267.8, "end": 2270.0, "text": " but like this is just a single element there."}, {"start": 2270.0, "end": 2272.9, "text": " And then if you just kind of multiply this,"}, {"start": 2272.9, "end": 2280.2000000000003, "text": " you'll understand that you basically end up with this same equation here."}, {"start": 2280.2000000000003, "end": 2284.0, "text": " And because here you have like X, V,"}, {"start": 2284.0, "end": 2286.8, "text": " and then a bit further down,"}, {"start": 2286.8, "end": 2290.6000000000004, "text": " maybe the penultimate slot is going to be X, U."}, {"start": 2290.6000000000004, "end": 2292.8, "text": " And that's why this thing is going to multiply this thing,"}, {"start": 2292.8, "end": 2294.3, "text": " and this thing is going to multiply this thing,"}, {"start": 2294.3, "end": 2296.1000000000004, "text": " and that's how we end up with the equation."}, {"start": 2296.1, "end": 2300.2999999999997, "text": " Sheaf loplation itself can be constructed from these co-boundary operators,"}, {"start": 2300.2999999999997, "end": 2303.7, "text": " and I'll not get into a lot of details there."}, {"start": 2303.7, "end": 2306.2999999999997, "text": " You can check them out in your own time,"}, {"start": 2306.2999999999997, "end": 2309.4, "text": " but for now just be aware that these co-boundary maps exist,"}, {"start": 2309.4, "end": 2311.2999999999997, "text": " and they basically, as you can see here,"}, {"start": 2311.2999999999997, "end": 2316.6, "text": " they measure the discrepancy again in the discourse space,"}, {"start": 2316.6, "end": 2318.6, "text": " so in the edge stock."}, {"start": 2318.6, "end": 2320.5, "text": " Okay, let's make it a bit more concrete."}, {"start": 2320.5, "end": 2323.0, "text": " So here is a particular graph,"}, {"start": 2323.0, "end": 2326.0, "text": " and here is the sheaf structure."}, {"start": 2326.0, "end": 2327.7, "text": " So here are the restriction maps."}, {"start": 2327.7, "end": 2329.8, "text": " Here are the stocks,"}, {"start": 2329.8, "end": 2332.1, "text": " and you see the concrete numbers."}, {"start": 2332.1, "end": 2334.0, "text": " And by using those numbers,"}, {"start": 2334.0, "end": 2337.0, "text": " you can plug them in into this co-boundary operator."}, {"start": 2337.0, "end": 2340.0, "text": " So this is how you form the co-boundary matrix."}, {"start": 2340.0, "end": 2341.1, "text": " You take the..."}, {"start": 2341.1, "end": 2345.1, "text": " So this is the restriction map F1,"}, {"start": 2345.1, "end": 2349.7, "text": " and this is the restriction map that corresponds to node 2, V2,"}, {"start": 2349.7, "end": 2354.8, "text": " and that's why we have, as you can see here, F1 minus F2,"}, {"start": 2354.8, "end": 2359.0, "text": " because once we multiply this with stocks,"}, {"start": 2359.0, "end": 2360.8, "text": " so we have X1, X2,"}, {"start": 2360.8, "end": 2365.3, "text": " we'll end up with F1, X1, minus F2, X2,"}, {"start": 2365.3, "end": 2367.3, "text": " and that's precisely measuring the disagreement"}, {"start": 2367.3, "end": 2369.1000000000004, "text": " along this particular edge."}, {"start": 2369.1000000000004, "end": 2370.3, "text": " So this is how you form them,"}, {"start": 2370.3, "end": 2372.4, "text": " and you can see again a connection"}, {"start": 2372.4, "end": 2375.1000000000004, "text": " between this and this thing here."}, {"start": 2375.1000000000004, "end": 2377.2000000000003, "text": " We get precisely this equation"}, {"start": 2377.2000000000003, "end": 2380.3, "text": " by forming a matrix such as this one."}, {"start": 2380.3, "end": 2384.3, "text": " And if we were to multiply this co-boundary transpose"}, {"start": 2384.3, "end": 2386.9, "text": " times co-boundary, we end up with the sheaf,"}, {"start": 2386.9, "end": 2390.5, "text": " and you can kind of imagine that with these Fs here and F2s,"}, {"start": 2390.5, "end": 2392.4, "text": " if you kind of do your math,"}, {"start": 2392.4, "end": 2395.8, "text": " you're gonna end up with an equation such as this one,"}, {"start": 2395.8, "end": 2398.3, "text": " a sum of these Fs and stuff."}, {"start": 2398.3, "end": 2399.9, "text": " Okay, I'm gonna stop there."}, {"start": 2399.9, "end": 2402.8, "text": " I'm aware this is packed with details,"}, {"start": 2402.8, "end": 2404.2000000000003, "text": " but it is how it is."}, {"start": 2404.2000000000003, "end": 2406.3, "text": " Hopefully this video is just gonna give you"}, {"start": 2406.3, "end": 2408.5, "text": " like a glimpse, an overview of this whole field,"}, {"start": 2408.5, "end": 2411.1000000000004, "text": " and you can go on and explore at your own pace,"}, {"start": 2411.1000000000004, "end": 2412.7000000000003, "text": " and then return back to this video"}, {"start": 2412.7, "end": 2415.2999999999997, "text": " and watch it again, I guess."}, {"start": 2415.2999999999997, "end": 2418.3999999999996, "text": " Let's get to the actual neural networks now."}, {"start": 2418.3999999999996, "end": 2423.0, "text": " So an important concept is this diffusion process."}, {"start": 2423.0, "end": 2426.3999999999996, "text": " Okay, now, so all of those laplations"}, {"start": 2426.3999999999996, "end": 2429.5, "text": " and the sheaf laplations can be thought of"}, {"start": 2429.5, "end": 2434.5, "text": " as a discretization of this diffusion process."}, {"start": 2434.5, "end": 2438.2999999999997, "text": " So it's basically a continuous process governed by a PDE,"}, {"start": 2438.2999999999997, "end": 2440.0, "text": " so a partial differential equation."}, {"start": 2440.0, "end": 2442.0, "text": " So we can see that the rate of change of X"}, {"start": 2442.0, "end": 2446.9, "text": " equals minus sheaf laplation times the current values of X."}, {"start": 2446.9, "end": 2450.1, "text": " And let me try and briefly explain"}, {"start": 2450.1, "end": 2452.1, "text": " what this diffusion process is about."}, {"start": 2452.1, "end": 2455.6, "text": " So again, how it came to be, this whole theory,"}, {"start": 2455.6, "end": 2458.2, "text": " is I'm fairly sure it came from Fourier"}, {"start": 2458.2, "end": 2462.5, "text": " analyzing the dissipation on solid bodies,"}, {"start": 2462.5, "end": 2464.5, "text": " the heat dissipation on solid bodies."}, {"start": 2464.5, "end": 2469.5, "text": " So imagine you have like a 3D solid object here,"}, {"start": 2469.5, "end": 2473.3, "text": " and you have a certain point inside here."}, {"start": 2473.3, "end": 2474.7, "text": " So you have a certain point,"}, {"start": 2474.7, "end": 2477.1, "text": " and that certain point has associated temperature,"}, {"start": 2477.1, "end": 2478.8, "text": " so a certain scalar."}, {"start": 2478.8, "end": 2481.5, "text": " And imagine now that you have around it,"}, {"start": 2481.5, "end": 2485.7, "text": " you have like a dense, like a minisphere"}, {"start": 2485.7, "end": 2488.3, "text": " around that point, the green point,"}, {"start": 2488.3, "end": 2493.3, "text": " and all of those points in the neighborhood are colder."}, {"start": 2493.9, "end": 2496.1, "text": " So what's gonna happen is that,"}, {"start": 2496.1, "end": 2498.9, "text": " as you know from your real life,"}, {"start": 2498.9, "end": 2503.9, "text": " this red, the green point is gonna slowly cool down."}, {"start": 2504.2000000000003, "end": 2506.9, "text": " And I should have probably used the red color"}, {"start": 2506.9, "end": 2508.5, "text": " to denote it as being hot."}, {"start": 2508.5, "end": 2510.8, "text": " It's gonna slowly cool down."}, {"start": 2510.8, "end": 2512.7000000000003, "text": " And the reason it cools down is because"}, {"start": 2512.7000000000003, "end": 2514.7000000000003, "text": " of this diffusion equation."}, {"start": 2514.7000000000003, "end": 2517.5, "text": " So basically you can imagine what happens is,"}, {"start": 2517.5, "end": 2521.0, "text": " we subtract from this value, whatever that value is,"}, {"start": 2521.0, "end": 2525.9, "text": " so some T zero, we subtract the average"}, {"start": 2525.9, "end": 2528.3, "text": " of the temperatures in the neighborhood."}, {"start": 2528.3, "end": 2531.8, "text": " And that means we're gonna subtract the average,"}, {"start": 2531.8, "end": 2536.1000000000004, "text": " so like a sum of the temperatures of the neighbors"}, {"start": 2536.1000000000004, "end": 2540.0, "text": " where I is gonna be from the neighbor set,"}, {"start": 2540.0, "end": 2543.1000000000004, "text": " just denoted as this very ugly N."}, {"start": 2543.1000000000004, "end": 2546.9, "text": " And if you think about it, this is exactly the same thing"}, {"start": 2546.9, "end": 2548.5, "text": " we're doing with our graphs."}, {"start": 2548.5, "end": 2551.9, "text": " So we just made this continuous,"}, {"start": 2551.9, "end": 2555.8, "text": " both in space and in time process, and we discretize it."}, {"start": 2555.8, "end": 2557.8, "text": " So we're doing it in a discrete domain,"}, {"start": 2557.8, "end": 2560.5, "text": " which is a graph, and we do it in discrete steps."}, {"start": 2560.5, "end": 2563.0, "text": " So in every iteration, we're gonna be doing the same thing."}, {"start": 2563.0, "end": 2566.5, "text": " Okay, so what this eventually leads to is basically"}, {"start": 2566.5, "end": 2568.9, "text": " everything is gonna have the same temperature."}, {"start": 2568.9, "end": 2572.5, "text": " Okay, that's the end goal of this process."}, {"start": 2572.5, "end": 2574.5, "text": " And we just took the discretized version"}, {"start": 2574.5, "end": 2577.8, "text": " of this same process, and we are piggybacking that"}, {"start": 2577.8, "end": 2581.1000000000004, "text": " as we're using it as the workhorse for all of our,"}, {"start": 2581.1000000000004, "end": 2583.9, "text": " for most of these graph neural networks."}, {"start": 2583.9, "end": 2586.4, "text": " Now they say here, it can be shown that in the time limit,"}, {"start": 2586.4, "end": 2589.2000000000003, "text": " each feature channel is projected into kernel"}, {"start": 2589.2000000000003, "end": 2591.3, "text": " of that sheaf laplation."}, {"start": 2591.3, "end": 2596.3, "text": " Okay, that means again, that this X is gonna be,"}, {"start": 2596.7000000000003, "end": 2598.9, "text": " that these updates are gonna be zero vectors,"}, {"start": 2598.9, "end": 2602.4, "text": " and that means that we won't have any rate of change."}, {"start": 2602.4, "end": 2604.6, "text": " So the diffusion stopped,"}, {"start": 2604.6, "end": 2607.6, "text": " the temperature is stable everywhere."}, {"start": 2607.6, "end": 2610.8, "text": " And that means continuing here, as described above,"}, {"start": 2610.8, "end": 2613.3, "text": " this space contains the signals that agree"}, {"start": 2613.3, "end": 2618.2000000000003, "text": " with the restriction maps of the sheaf along all the edges."}, {"start": 2618.2000000000003, "end": 2620.6000000000004, "text": " In what follows, we analyze the ability of certain classes"}, {"start": 2620.6000000000004, "end": 2623.2000000000003, "text": " of sheaves to linearly separate the features"}, {"start": 2623.2000000000003, "end": 2626.9, "text": " in the limit of the diffusion processes they induce."}, {"start": 2626.9, "end": 2628.6000000000004, "text": " Okay, restating this again,"}, {"start": 2629.9, "end": 2632.2000000000003, "text": " by repeating this diffusion process,"}, {"start": 2632.2000000000003, "end": 2635.2000000000003, "text": " we'll eventually end up being a harmonic signal."}, {"start": 2635.2000000000003, "end": 2638.0, "text": " So we'll eventually end up with these harmonic signals,"}, {"start": 2638.0, "end": 2643.3, "text": " i.e. signals that basically lead to alignment"}, {"start": 2643.3, "end": 2645.5, "text": " with their neighbors."}, {"start": 2645.5, "end": 2649.1, "text": " Now, in general case, that signal might be trivial,"}, {"start": 2649.1, "end": 2652.0, "text": " so it might be all zeros, which is not that interesting,"}, {"start": 2652.0, "end": 2655.7, "text": " but like we're gonna now see specific classes"}, {"start": 2655.7, "end": 2660.3, "text": " and how for specific, if we pick specific sheaf structures,"}, {"start": 2660.3, "end": 2663.7, "text": " we'll end up with very interesting harmonic spaces."}, {"start": 2663.7, "end": 2665.7, "text": " So what would constitute an interesting signal"}, {"start": 2665.7, "end": 2666.9, "text": " from that harmonic space?"}, {"start": 2666.9, "end": 2670.0, "text": " Well, a signal such that we can linearly separate"}, {"start": 2670.0, "end": 2671.8, "text": " our classes, so we can classify it,"}, {"start": 2671.8, "end": 2674.0, "text": " we care about like node classification,"}, {"start": 2674.0, "end": 2675.6, "text": " edge classification, regression,"}, {"start": 2675.6, "end": 2677.0, "text": " graph classification, whatnot."}, {"start": 2677.0, "end": 2679.8, "text": " And so if this diffusion process eventually leads"}, {"start": 2679.8, "end": 2681.4, "text": " to such a harmonic signal,"}, {"start": 2681.4, "end": 2684.3, "text": " such that we have linear separability of our classes,"}, {"start": 2684.3, "end": 2687.2000000000003, "text": " then we're good, then we want to kind of ride"}, {"start": 2687.2000000000003, "end": 2691.9, "text": " the diffusion process all the way to this equilibrium point."}, {"start": 2692.9, "end": 2696.5, "text": " Now, let's see a couple of sheaf structures"}, {"start": 2696.5, "end": 2701.5, "text": " and what the harmonic signals they result with,"}, {"start": 2702.6, "end": 2705.1, "text": " basically how powerful are those signals."}, {"start": 2705.1, "end": 2707.2, "text": " Okay, so first class they consider"}, {"start": 2707.2, "end": 2710.2, "text": " is this very simple symmetric invertible class."}, {"start": 2710.2, "end": 2712.0, "text": " Okay, it's defined the following way."}, {"start": 2712.9, "end": 2717.5, "text": " It's such a sheaf structure such that we have"}, {"start": 2717.5, "end": 2723.6, "text": " the restriction map for two nodes that connect one edge."}, {"start": 2723.6, "end": 2726.3, "text": " So these two nodes are gonna have the same,"}, {"start": 2726.3, "end": 2727.2000000000003, "text": " they're gonna be the same."}, {"start": 2727.2000000000003, "end": 2729.4, "text": " These two restriction maps are gonna be the same"}, {"start": 2729.4, "end": 2733.5, "text": " and the determinant of those restriction maps"}, {"start": 2733.5, "end": 2735.3, "text": " is gonna be different than zero,"}, {"start": 2735.3, "end": 2739.3, "text": " which means this is invertible as it says here"}, {"start": 2739.3, "end": 2742.9, "text": " and it's symmetric because these two are equal, okay?"}, {"start": 2742.9, "end": 2745.8, "text": " Then they mentioned here, we note that for D equals one,"}, {"start": 2745.8, "end": 2747.8, "text": " so stock dimension equals one,"}, {"start": 2747.8, "end": 2750.7000000000003, "text": " the sheaf loplations induced by this class of sheaves"}, {"start": 2750.7000000000003, "end": 2753.8, "text": " coincides with the set of the well-known weighted"}, {"start": 2753.8, "end": 2756.6000000000004, "text": " graph loplations with strictly positive weights,"}, {"start": 2756.6000000000004, "end": 2759.4, "text": " which also includes the usual graph loplation."}, {"start": 2759.4, "end": 2763.1000000000004, "text": " Therefore, this hypothesis class is of particular interest"}, {"start": 2763.1000000000004, "end": 2765.3, "text": " since it includes those graph loplations"}, {"start": 2765.3, "end": 2768.5, "text": " typically used by graph convolutional models such as GCN."}, {"start": 2768.5, "end": 2772.5, "text": " So this is the minimal generalization we can make, okay?"}, {"start": 2772.5, "end": 2775.7000000000003, "text": " And we first show that this class of sheaf loplations"}, {"start": 2775.7000000000003, "end": 2777.9, "text": " can linearly separate the classes"}, {"start": 2777.9, "end": 2780.5, "text": " in binary classification settings"}, {"start": 2780.5, "end": 2783.6000000000004, "text": " under certain homophily assumptions."}, {"start": 2783.6, "end": 2784.7999999999997, "text": " So that's very important."}, {"start": 2784.7999999999997, "end": 2786.2, "text": " I'm gonna go through this proposition,"}, {"start": 2786.2, "end": 2788.7999999999997, "text": " but then I'll start slowly scheming some of the details"}, {"start": 2788.7999999999997, "end": 2790.0, "text": " because there is too many details"}, {"start": 2790.0, "end": 2792.7, "text": " and not all of them are equally important here."}, {"start": 2792.7, "end": 2795.7, "text": " Let G be the set of connected graphs with two classes."}, {"start": 2795.7, "end": 2797.9, "text": " We have two classes because it's a binary classification"}, {"start": 2797.9, "end": 2801.9, "text": " problem, so nodes A and nodes B belong into the set of nodes"}, {"start": 2801.9, "end": 2805.4, "text": " of the graph such that for each node from one class,"}, {"start": 2805.4, "end": 2810.0, "text": " there exists a node U from the same class"}, {"start": 2810.0, "end": 2811.6, "text": " and an edge connecting them."}, {"start": 2811.6, "end": 2814.9, "text": " So that means that the nodes with the same label"}, {"start": 2814.9, "end": 2816.7, "text": " are connected to each other."}, {"start": 2816.7, "end": 2819.4, "text": " And that's the homophily assumption they mentioned."}, {"start": 2819.4, "end": 2824.4, "text": " Then this sheaf has linear separation power"}, {"start": 2824.7, "end": 2826.7, "text": " over this particular graph, okay?"}, {"start": 2826.7, "end": 2829.7, "text": " But then they show that it's not powerful enough"}, {"start": 2829.7, "end": 2831.2999999999997, "text": " to linearly separate two classes"}, {"start": 2831.2999999999997, "end": 2834.7999999999997, "text": " if basically we have heterophilic conditions."}, {"start": 2834.7999999999997, "end": 2836.5, "text": " And that's what I show here."}, {"start": 2836.5, "end": 2841.5, "text": " Basically, if let G be the set of connected bipartite graphs"}, {"start": 2842.3, "end": 2844.6, "text": " with partitions A and B forming two classes"}, {"start": 2844.6, "end": 2848.4, "text": " and being of, like, those two classes"}, {"start": 2848.4, "end": 2850.2, "text": " have the same number of elements,"}, {"start": 2850.2, "end": 2854.4, "text": " then this sheaf cannot linearly separate any graph in G"}, {"start": 2854.4, "end": 2856.2, "text": " for any initial conditions, okay?"}, {"start": 2856.2, "end": 2859.3, "text": " So that means that if we have something like this,"}, {"start": 2859.3, "end": 2863.6, "text": " so we have a bipartite graph such as this one,"}, {"start": 2863.6, "end": 2867.7999999999997, "text": " and we don't have any connections here."}, {"start": 2867.7999999999997, "end": 2869.2999999999997, "text": " We just connect like this."}, {"start": 2869.2999999999997, "end": 2871.1, "text": " We just have these connections, okay?"}, {"start": 2871.1, "end": 2875.6, "text": " And they can show that in this particular setup,"}, {"start": 2875.6, "end": 2879.6, "text": " this class of sheaf structures will not work."}, {"start": 2879.6, "end": 2881.2999999999997, "text": " And that's why we have to resort"}, {"start": 2881.2999999999997, "end": 2883.9, "text": " to some more powerful sheaf classes."}, {"start": 2883.9, "end": 2886.0, "text": " And let's see what those are."}, {"start": 2886.0, "end": 2889.1, "text": " So then they introduce this non-symmetric invertible"}, {"start": 2889.1, "end": 2892.0, "text": " where we only have this constraint,"}, {"start": 2892.0, "end": 2895.9, "text": " so it's invertible, but we don't have the symmetry constraint."}, {"start": 2895.9, "end": 2898.5, "text": " Here they show, I'm gonna skip reading this,"}, {"start": 2898.5, "end": 2903.5, "text": " but they basically say that even in heterophilic conditions,"}, {"start": 2904.5, "end": 2909.5, "text": " this sheaf class is gonna have the linear separation power"}, {"start": 2909.7, "end": 2913.1, "text": " over those graphs, which is super nice."}, {"start": 2913.1, "end": 2916.6, "text": " So we're slowly, by adding more powerful sheaf structures,"}, {"start": 2916.6, "end": 2919.2, "text": " we can solve more difficult problems."}, {"start": 2919.2, "end": 2922.7, "text": " So in this particular case, basically,"}, {"start": 2922.7, "end": 2925.7, "text": " binary classification in heterophilic setting, okay?"}, {"start": 2926.7, "end": 2928.0, "text": " And now they continue doing this."}, {"start": 2928.0, "end": 2931.7, "text": " So here they state a fundamental limitation"}, {"start": 2931.7, "end": 2933.8999999999996, "text": " of sheaf diffusion when D equals one,"}, {"start": 2933.8999999999996, "end": 2937.2999999999997, "text": " so when we only have single-dimensional stocks."}, {"start": 2939.2999999999997, "end": 2941.7, "text": " They basically say that let G be a connected graph"}, {"start": 2941.7, "end": 2945.7, "text": " with more than three classes, so three or more,"}, {"start": 2945.7, "end": 2950.2, "text": " then this previous class of sheafs cannot linearly separate"}, {"start": 2950.2, "end": 2955.2, "text": " any signal on that graph, and that's a powerful statement."}, {"start": 2956.5, "end": 2958.7, "text": " So that means we need to go deeper."}, {"start": 2958.7, "end": 2963.3999999999996, "text": " We need to have more dimensions along the stock,"}, {"start": 2963.3999999999996, "end": 2965.5, "text": " along the vector space dimension."}, {"start": 2965.5, "end": 2967.5, "text": " So they say here, from a GNM perspective,"}, {"start": 2967.5, "end": 2970.0, "text": " this means that in the infinite-depth setting,"}, {"start": 2970.0, "end": 2973.0, "text": " sufficient stock width, i.e. dimension D,"}, {"start": 2973.0, "end": 2975.8, "text": " is needed in order to solve tasks involving"}, {"start": 2975.8, "end": 2978.8, "text": " more than two classes, so more than two classes."}, {"start": 2978.8, "end": 2981.1, "text": " Note that D is different from the classical notion"}, {"start": 2981.1, "end": 2983.1, "text": " of feature, channels F."}, {"start": 2983.1, "end": 2986.2, "text": " As a result, above shows, the letter has no effect"}, {"start": 2986.2, "end": 2989.8, "text": " on the linear separability of the classes in D equals one,"}, {"start": 2989.8, "end": 2991.8, "text": " whereas they showed that the former does."}, {"start": 2991.8, "end": 2995.8, "text": " So you can still have, so this sheaf structure,"}, {"start": 2997.6, "end": 3001.2, "text": " this sheaf neural networks are still going to admit"}, {"start": 3001.2, "end": 3003.0, "text": " the usage of features."}, {"start": 3003.0, "end": 3006.7999999999997, "text": " It's just that those do not help increase the expressivity"}, {"start": 3006.7999999999997, "end": 3010.0, "text": " of our models, whereas increasing the stock dimension"}, {"start": 3010.0, "end": 3011.5, "text": " on the other hand does."}, {"start": 3011.5, "end": 3013.6, "text": " So next up, they introduce this diagonal,"}, {"start": 3013.6, "end": 3018.6, "text": " invertible family of sheafs where the restriction maps"}, {"start": 3019.0, "end": 3021.2999999999997, "text": " are diagonal, so basically, if you take a look"}, {"start": 3021.2999999999997, "end": 3023.7999999999997, "text": " at their representation of the matrix,"}, {"start": 3023.7999999999997, "end": 3025.3999999999996, "text": " you'll just see diagonal elements,"}, {"start": 3025.3999999999996, "end": 3028.0, "text": " and everything else is zero, and again, it's invertible,"}, {"start": 3028.0, "end": 3030.3999999999996, "text": " so we have this condition of the determinant condition."}, {"start": 3030.4, "end": 3034.5, "text": " And they say that let G be the set of connected graphs"}, {"start": 3034.5, "end": 3037.6, "text": " with nodes belonging to more than three,"}, {"start": 3037.6, "end": 3042.0, "text": " so three or more classes, then for D equals,"}, {"start": 3042.0, "end": 3045.5, "text": " or greater or equal than the number of classes,"}, {"start": 3045.5, "end": 3050.5, "text": " this particular class of sheafs has linear separation power."}, {"start": 3050.6, "end": 3053.9, "text": " So as long as the D is bigger than the,"}, {"start": 3053.9, "end": 3056.4, "text": " or equal to the number of classes,"}, {"start": 3056.4, "end": 3058.1, "text": " we have separation power."}, {"start": 3058.1, "end": 3061.2999999999997, "text": " So again, more powerful than the previous families."}, {"start": 3061.2999999999997, "end": 3063.7, "text": " Then they do the same thing for orthogonal families"}, {"start": 3063.7, "end": 3067.9, "text": " where basically the restriction maps now belong"}, {"start": 3067.9, "end": 3072.9, "text": " to this group of orthogonal matrices,"}, {"start": 3073.7999999999997, "end": 3075.9, "text": " which basically means they just do rotations,"}, {"start": 3075.9, "end": 3078.9, "text": " they don't do any scaling, they just rotate your vectors."}, {"start": 3078.9, "end": 3081.4, "text": " And here they show that this class has even more powers"}, {"start": 3081.4, "end": 3084.0, "text": " in the sense that here you can have, for example,"}, {"start": 3084.0, "end": 3087.7, "text": " two for the dimensionality of the stock,"}, {"start": 3087.7, "end": 3092.2, "text": " and you can classify, you can correctly linearly separate"}, {"start": 3092.2, "end": 3096.0, "text": " up to four classes, so that means it's even more powerful."}, {"start": 3096.0, "end": 3099.3999999999996, "text": " And the interesting part here is that the proof is crazy,"}, {"start": 3099.3999999999996, "end": 3103.5, "text": " like they use quaternions and complex numbers for two,"}, {"start": 3103.5, "end": 3108.3999999999996, "text": " and basically this statement here may hold"}, {"start": 3108.3999999999996, "end": 3110.8999999999996, "text": " even for higher dimensions, it's just that they did not"}, {"start": 3110.8999999999996, "end": 3114.0, "text": " make the proofs for those other dimensions."}, {"start": 3114.0, "end": 3118.3, "text": " If you're curious in the very heavy mathematics,"}, {"start": 3118.3, "end": 3121.9, "text": " the appendix of the paper is full of various proofs"}, {"start": 3121.9, "end": 3125.3, "text": " of all of these propositions and theorems you saw here."}, {"start": 3125.3, "end": 3129.0, "text": " So very, very mathematically rich paper."}, {"start": 3129.0, "end": 3130.7, "text": " So finally, the summary."}, {"start": 3130.7, "end": 3133.4, "text": " Different shift classes give rise to different behaviors"}, {"start": 3133.4, "end": 3136.3, "text": " of the diffusion process and consequently"}, {"start": 3136.3, "end": 3138.7, "text": " to different separation capabilities."}, {"start": 3138.7, "end": 3141.7, "text": " Taken together, these results show that solving"}, {"start": 3141.7, "end": 3143.8, "text": " any node classification test can be reduced"}, {"start": 3143.8, "end": 3146.5, "text": " to performing diffusion with the right sheaf."}, {"start": 3146.5, "end": 3149.3, "text": " A very powerful statement."}, {"start": 3149.3, "end": 3153.4, "text": " So again, by taking a particular sheaf structure"}, {"start": 3153.4, "end": 3158.6000000000004, "text": " and by just constructing the corresponding sheaf loplation"}, {"start": 3158.6000000000004, "end": 3161.5, "text": " and by just iterating, applying the sheaf loplation"}, {"start": 3161.5, "end": 3163.9, "text": " in this diffusion process, we'll end up"}, {"start": 3163.9, "end": 3166.9, "text": " with certain harmonic signals and depending"}, {"start": 3166.9, "end": 3170.7000000000003, "text": " on the basically richness of the class you picked,"}, {"start": 3170.7, "end": 3175.7, "text": " those harmonic signals may lead to a very nice"}, {"start": 3175.7999999999997, "end": 3178.5, "text": " linear separability of your classes."}, {"start": 3178.5, "end": 3181.2, "text": " So that's the idea here."}, {"start": 3181.2, "end": 3183.2999999999997, "text": " Okay, we're slowly wrapping up this paper."}, {"start": 3183.2999999999997, "end": 3186.8999999999996, "text": " So there is not a lot more, so maybe pause the video"}, {"start": 3186.8999999999996, "end": 3190.1, "text": " and stretch a bit, I know this was super heavy."}, {"start": 3190.1, "end": 3195.1, "text": " So here you can see a previous sheaf neural network"}, {"start": 3195.2999999999997, "end": 3198.3999999999996, "text": " devised in one of the previous papers."}, {"start": 3198.4, "end": 3203.1, "text": " And it again uses the diffusion process as the workhorse"}, {"start": 3203.1, "end": 3206.2000000000003, "text": " and just adds additional learnable parameters"}, {"start": 3206.2000000000003, "end": 3210.3, "text": " and non-linearities to this diffusion process"}, {"start": 3210.3, "end": 3213.8, "text": " to make these more powerful neural networks."}, {"start": 3213.8, "end": 3216.4, "text": " But what they've done is they actually hard-coded"}, {"start": 3216.4, "end": 3218.2000000000003, "text": " the sheaf structure, so they are not learning"}, {"start": 3218.2000000000003, "end": 3220.8, "text": " the sheaf structure, whereas as we'll soon see"}, {"start": 3220.8, "end": 3222.5, "text": " in this paper, they're actually learning"}, {"start": 3222.5, "end": 3224.3, "text": " the sheaf structure as well."}, {"start": 3224.3, "end": 3227.1, "text": " So let's see what this thing does."}, {"start": 3227.1, "end": 3232.1, "text": " So we have X, which is basically, those are our signals,"}, {"start": 3232.2999999999997, "end": 3236.7, "text": " and the dimensionality of that matrix is gonna be basically"}, {"start": 3236.7, "end": 3241.7, "text": " Nd times F, so that means we'll have Nd dimensions here"}, {"start": 3244.2, "end": 3248.1, "text": " because we have N nodes, dimensionality of the stokes is D,"}, {"start": 3248.1, "end": 3250.6, "text": " and we have potentially F features here."}, {"start": 3250.6, "end": 3252.1, "text": " That's why we have something like this."}, {"start": 3252.1, "end": 3253.7, "text": " This is the structure of X."}, {"start": 3253.7, "end": 3258.7, "text": " So what W2 does is first, you just linearly transform,"}, {"start": 3258.7, "end": 3262.1, "text": " you map these feature vectors into some other representations."}, {"start": 3262.1, "end": 3264.2999999999997, "text": " That's the first transformation you do."}, {"start": 3264.2999999999997, "end": 3267.7, "text": " Then what you do is you take this W1 matrix,"}, {"start": 3267.7, "end": 3270.1, "text": " which is of dimensionality D times D."}, {"start": 3270.1, "end": 3271.7999999999997, "text": " This is gonna be D times D."}, {"start": 3271.7999999999997, "end": 3275.7999999999997, "text": " You're gonna do a Kronecker product with identity matrix N,"}, {"start": 3275.7999999999997, "end": 3277.8999999999996, "text": " which is a fancy way of doing the following thing."}, {"start": 3277.8999999999996, "end": 3281.2, "text": " So you're gonna end up with Nd times Nd matrix,"}, {"start": 3281.2, "end": 3285.8999999999996, "text": " which is basically necessary if you want to multiply,"}, {"start": 3285.8999999999996, "end": 3288.3999999999996, "text": " left multiply this particular structure here."}, {"start": 3288.3999999999996, "end": 3289.6, "text": " So why does that happen?"}, {"start": 3289.6, "end": 3293.3999999999996, "text": " Well, you have a matrix that's T times D,"}, {"start": 3293.3999999999996, "end": 3297.0, "text": " and what this Kronecker product does is the following."}, {"start": 3297.0, "end": 3302.0, "text": " By multiplying this by basically, just a second,"}, {"start": 3302.1, "end": 3303.8999999999996, "text": " sorry, it's on the other side,"}, {"start": 3303.8999999999996, "end": 3305.8999999999996, "text": " so it's gonna be from the left side."}, {"start": 3306.7, "end": 3310.5, "text": " So by multiplying this with this identity matrix"}, {"start": 3310.5, "end": 3312.5, "text": " that has dimensions N times N,"}, {"start": 3312.5, "end": 3315.5, "text": " you're gonna end up with the following structure."}, {"start": 3315.5, "end": 3317.9, "text": " Basically along this diagonal,"}, {"start": 3317.9, "end": 3321.7, "text": " we're gonna have, we're just gonna copy paste"}, {"start": 3321.7, "end": 3323.3, "text": " these matrices D."}, {"start": 3323.3, "end": 3326.6, "text": " So where there was one in this matrix,"}, {"start": 3326.6, "end": 3328.7, "text": " we're gonna have a D times D matrix here."}, {"start": 3328.7, "end": 3332.0, "text": " And that's why we end up with N times D matrix here, okay?"}, {"start": 3333.2, "end": 3338.2, "text": " So that matrix is gonna basically take the signals here."}, {"start": 3338.2, "end": 3343.2, "text": " So let's assume this is one vector here, this is D."}, {"start": 3344.3999999999996, "end": 3349.3999999999996, "text": " It's going to linearly transform stocks"}, {"start": 3350.1, "end": 3351.7999999999997, "text": " for each of the features."}, {"start": 3351.7999999999997, "end": 3353.7999999999997, "text": " That's what this part is gonna do."}, {"start": 3353.7999999999997, "end": 3358.2, "text": " And finally, we apply the shift-loplation here,"}, {"start": 3358.2, "end": 3360.2, "text": " which is going to do the,"}, {"start": 3360.2, "end": 3363.1, "text": " again, the averaging of the neighbors logic,"}, {"start": 3363.1, "end": 3367.2999999999997, "text": " and then you subtract that value from the node of interest."}, {"start": 3367.3, "end": 3369.9, "text": " And then you just apply the non-linearity here."}, {"start": 3369.9, "end": 3373.3, "text": " So again, you're basically in a way"}, {"start": 3374.5, "end": 3378.0, "text": " using this diffusion logic as your workhorse,"}, {"start": 3378.0, "end": 3382.0, "text": " and then you're building these learnable components"}, {"start": 3382.0, "end": 3383.7000000000003, "text": " and putting those learnable components"}, {"start": 3383.7000000000003, "end": 3386.2000000000003, "text": " around your diffusion logic."}, {"start": 3386.2000000000003, "end": 3388.6000000000004, "text": " That's how this network works."}, {"start": 3388.6000000000004, "end": 3391.8, "text": " And then they say it is natural to call this model"}, {"start": 3391.8, "end": 3393.8, "text": " a shift convolutional network,"}, {"start": 3393.8, "end": 3397.4, "text": " since when the shift-loplation is the usual"}, {"start": 3397.4, "end": 3400.0, "text": " normalized graph-loplation,"}, {"start": 3400.0, "end": 3403.6000000000004, "text": " W1 becomes a scalar and one recovers the GCN"}, {"start": 3403.6000000000004, "end": 3407.5, "text": " of Kipf and Welling, so that's the famous GCN paper."}, {"start": 3407.5, "end": 3411.5, "text": " So this shows that GCNs and more generally SCNs"}, {"start": 3411.5, "end": 3414.3, "text": " are a non-linear parametric and discrete version"}, {"start": 3414.3, "end": 3415.9, "text": " of shift diffusion."}, {"start": 3415.9, "end": 3418.0, "text": " In what follows, we analyze how expressive"}, {"start": 3418.0, "end": 3420.5, "text": " these non-linear models are compared to their"}, {"start": 3420.5, "end": 3424.1, "text": " base diffusion process, okay?"}, {"start": 3424.1, "end": 3427.3, "text": " So let's see a couple of things here."}, {"start": 3427.3, "end": 3432.5, "text": " So first of all, they form something called"}, {"start": 3432.5, "end": 3433.7, "text": " Dirichlet energy."}, {"start": 3433.7, "end": 3437.7, "text": " So for the sake of time, it's not even important"}, {"start": 3437.7, "end": 3440.8, "text": " for you to understand the exact details."}, {"start": 3440.8, "end": 3443.4, "text": " What you need to know is that this Dirichlet energy"}, {"start": 3443.4, "end": 3446.9, "text": " basically measures how far is the current signal"}, {"start": 3446.9, "end": 3449.2, "text": " from being a harmonic signal."}, {"start": 3449.2, "end": 3452.6, "text": " So from being, yeah, basically a harmonic signal."}, {"start": 3452.6, "end": 3455.7999999999997, "text": " So then they state the following here."}, {"start": 3455.7999999999997, "end": 3460.7999999999997, "text": " If we have a shift class belonging to this particular"}, {"start": 3461.1, "end": 3462.8999999999996, "text": " orthogonal symmetric shift class,"}, {"start": 3462.8999999999996, "end": 3465.8999999999996, "text": " which is fairly restricted, if we have a non-linearity"}, {"start": 3465.8999999999996, "end": 3469.0, "text": " that's either a ReLU or a Leaky ReLU,"}, {"start": 3469.0, "end": 3473.1, "text": " then they can show that the Dirichlet energy"}, {"start": 3473.1, "end": 3476.3999999999996, "text": " in the next state, so this is a signal,"}, {"start": 3476.3999999999996, "end": 3479.1, "text": " the transformed signal after we apply the logic"}, {"start": 3479.1, "end": 3482.7999999999997, "text": " from the neural network, is gonna be upper bounded"}, {"start": 3482.7999999999997, "end": 3485.7, "text": " by this expression here, and this is the old signal."}, {"start": 3485.7, "end": 3489.2999999999997, "text": " This is the old energy of the old signal, okay?"}, {"start": 3489.2999999999997, "end": 3492.7999999999997, "text": " So in particular, this means that if this whole term here"}, {"start": 3492.7999999999997, "end": 3497.2, "text": " is smaller than one, that means that with every step,"}, {"start": 3497.2, "end": 3500.2999999999997, "text": " the energy will go down, and as I said,"}, {"start": 3500.2999999999997, "end": 3503.0, "text": " the energy going down means the signal is going towards"}, {"start": 3503.0, "end": 3505.7999999999997, "text": " becoming a harmonic signal, okay?"}, {"start": 3505.7999999999997, "end": 3508.7999999999997, "text": " So this means that the signal converges exponentially"}, {"start": 3508.8, "end": 3511.6000000000004, "text": " fast to the kernel of the shift laplation,"}, {"start": 3511.6000000000004, "end": 3513.9, "text": " i.e. to being the harmonic signal."}, {"start": 3513.9, "end": 3515.7000000000003, "text": " Okay, and this is usually going to be the case"}, {"start": 3515.7000000000003, "end": 3520.7000000000003, "text": " because this lambda star is usually smaller than one,"}, {"start": 3520.8, "end": 3524.1000000000004, "text": " and because of the regularization and everything,"}, {"start": 3524.1000000000004, "end": 3525.6000000000004, "text": " in order to reduce the fitting,"}, {"start": 3525.6000000000004, "end": 3527.3, "text": " the norms here are gonna be also small,"}, {"start": 3527.3, "end": 3531.2000000000003, "text": " so this is usually satisfied, which means that"}, {"start": 3531.2000000000003, "end": 3534.8, "text": " for this particular class of sheaves,"}, {"start": 3534.8, "end": 3539.8, "text": " the signal is necessarily going to go towards"}, {"start": 3540.2000000000003, "end": 3543.8, "text": " the actual becoming a harmonic signal,"}, {"start": 3543.8, "end": 3545.8, "text": " and that's not always desirable."}, {"start": 3545.8, "end": 3547.5, "text": " We'll see why that is."}, {"start": 3547.5, "end": 3552.2000000000003, "text": " So let's see the proposition 17 here first."}, {"start": 3553.6000000000004, "end": 3556.4, "text": " They mentioned that as soon as we have"}, {"start": 3556.4, "end": 3559.7000000000003, "text": " an asymmetric transport map, so here remember,"}, {"start": 3559.7000000000003, "end": 3562.7000000000003, "text": " this class had the symmetry constraint,"}, {"start": 3562.7, "end": 3566.6, "text": " so as soon as we have the asymmetric transport map,"}, {"start": 3566.6, "end": 3569.8999999999996, "text": " we can find an arbitrarily small linear transformation W"}, {"start": 3569.8999999999996, "end": 3571.8999999999996, "text": " that increases the energy, okay?"}, {"start": 3571.8999999999996, "end": 3576.0, "text": " So this means that this class is gonna be more powerful"}, {"start": 3576.0, "end": 3579.2, "text": " and does not necessarily need to monotonically go towards"}, {"start": 3579.2, "end": 3583.0, "text": " becoming a harmonic signal, and we need that flexibility"}, {"start": 3583.0, "end": 3585.3999999999996, "text": " because we are learning the sheave."}, {"start": 3585.3999999999996, "end": 3587.8999999999996, "text": " We don't know the true sheave,"}, {"start": 3587.8999999999996, "end": 3589.7999999999997, "text": " like we don't know the ground truth sheave,"}, {"start": 3589.8, "end": 3593.5, "text": " and that means that we may end up with some bad sheave"}, {"start": 3593.5, "end": 3596.6000000000004, "text": " whose harmonic signals are not gonna end up"}, {"start": 3596.6000000000004, "end": 3598.8, "text": " becoming an interesting solution,"}, {"start": 3598.8, "end": 3601.4, "text": " meaning we will not have the linear separability,"}, {"start": 3601.4, "end": 3604.6000000000004, "text": " and that's why sometimes we want to actually go away,"}, {"start": 3604.6000000000004, "end": 3608.4, "text": " further away from becoming a harmonic signal."}, {"start": 3608.4, "end": 3611.8, "text": " That's why we wanna have more powerful sheave classes."}, {"start": 3611.8, "end": 3614.8, "text": " So they mentioned here for any connected graph G"}, {"start": 3614.8, "end": 3617.0, "text": " and epsilon bigger than zero,"}, {"start": 3617.0, "end": 3619.8, "text": " there exists a sheave class that is not symmetric,"}, {"start": 3619.8, "end": 3622.8, "text": " that's important, such that basically"}, {"start": 3622.8, "end": 3627.2, "text": " for arbitrarily small norm of this W matrix"}, {"start": 3627.2, "end": 3632.2, "text": " and feature vector X, the energy is gonna actually increase"}, {"start": 3632.4, "end": 3635.6, "text": " instead of decreasing, and that's the power"}, {"start": 3635.6, "end": 3640.6, "text": " of these more expressive, like basically sheave classes."}, {"start": 3641.0, "end": 3644.1, "text": " So as a summary, not only the sheave diffusion"}, {"start": 3644.1, "end": 3646.5, "text": " is more expressive than heat diffusion,"}, {"start": 3646.5, "end": 3647.9, "text": " as shown in section four,"}, {"start": 3647.9, "end": 3650.5, "text": " but the sheave convolutional networks"}, {"start": 3650.5, "end": 3652.6, "text": " are also more expressive than GCNs"}, {"start": 3652.6, "end": 3655.3, "text": " in the sense that they are generally not constrained"}, {"start": 3655.3, "end": 3657.7, "text": " to decrease the Dirichlet energy."}, {"start": 3657.7, "end": 3659.4, "text": " This gives them greater control"}, {"start": 3659.4, "end": 3662.9, "text": " over their asymptotic behavior than GCNs."}, {"start": 3664.0, "end": 3666.4, "text": " And let's finally wrap up this paper."}, {"start": 3666.4, "end": 3669.0, "text": " It's becoming a very, very long video."}, {"start": 3669.0, "end": 3671.8, "text": " So here is the actual model they propose."}, {"start": 3671.8, "end": 3676.8, "text": " So instead of using the sheave equation,"}, {"start": 3676.8, "end": 3680.1000000000004, "text": " diffusion equation we saw moments ago,"}, {"start": 3680.1000000000004, "end": 3682.6000000000004, "text": " which is, let me just find the one"}, {"start": 3682.6000000000004, "end": 3686.5, "text": " we were looking at before."}, {"start": 3686.5, "end": 3689.6000000000004, "text": " So just a second here, where are you?"}, {"start": 3692.5, "end": 3694.0, "text": " Okay, here it is."}, {"start": 3694.0, "end": 3696.5, "text": " This was the diffusion equation we were looking at."}, {"start": 3697.4, "end": 3699.2000000000003, "text": " So now instead of this one,"}, {"start": 3699.2, "end": 3701.7999999999997, "text": " they actually generalize that diffusion equation"}, {"start": 3701.7999999999997, "end": 3704.8999999999996, "text": " and they end up with something like this."}, {"start": 3704.8999999999996, "end": 3709.8999999999996, "text": " So you can easily show that by using particular values"}, {"start": 3710.3999999999996, "end": 3712.2999999999997, "text": " for W1 and W2."}, {"start": 3712.2999999999997, "end": 3715.3999999999996, "text": " And for example, if you're in the linear regime"}, {"start": 3715.3999999999996, "end": 3717.7, "text": " of the allel nonlinearity,"}, {"start": 3717.7, "end": 3719.7999999999997, "text": " you can show that this is,"}, {"start": 3719.7999999999997, "end": 3724.7999999999997, "text": " you recover the original diffusion equation."}, {"start": 3725.0, "end": 3726.7999999999997, "text": " So they, and then they start from,"}, {"start": 3726.8, "end": 3729.6000000000004, "text": " and then they take this continuous diffusion equation"}, {"start": 3729.6000000000004, "end": 3731.8, "text": " and they discretize it and they end up"}, {"start": 3731.8, "end": 3733.3, "text": " with the model that they use."}, {"start": 3733.3, "end": 3735.0, "text": " And here it is."}, {"start": 3735.0, "end": 3736.2000000000003, "text": " Here's the model they use."}, {"start": 3736.2000000000003, "end": 3738.5, "text": " It's somewhat similar to the previous,"}, {"start": 3738.5, "end": 3742.7000000000003, "text": " like basically a sheave convolutional network we saw."}, {"start": 3743.6000000000004, "end": 3745.5, "text": " There is a couple of important differences."}, {"start": 3745.5, "end": 3750.5, "text": " So we still have this F times F matrix"}, {"start": 3750.6000000000004, "end": 3752.2000000000003, "text": " that's mapping the features."}, {"start": 3752.2000000000003, "end": 3753.9, "text": " We have the D times D matrix"}, {"start": 3753.9, "end": 3758.8, "text": " that's like basically mapping the stock vectors"}, {"start": 3758.8, "end": 3760.2000000000003, "text": " into novel representations."}, {"start": 3760.2000000000003, "end": 3762.3, "text": " We have the sheaf loplation."}, {"start": 3762.3, "end": 3763.7000000000003, "text": " So important details are this."}, {"start": 3763.7000000000003, "end": 3765.4, "text": " In contrast, we'll learn a sheaf,"}, {"start": 3765.4, "end": 3766.9, "text": " which makes our model applicable"}, {"start": 3766.9, "end": 3769.1, "text": " to any real world graph data set,"}, {"start": 3769.1, "end": 3771.2000000000003, "text": " even in the absence of a sheave structure."}, {"start": 3771.2000000000003, "end": 3772.9, "text": " So the previous paper,"}, {"start": 3772.9, "end": 3775.1, "text": " they actually hard coded the sheave structure."}, {"start": 3775.1, "end": 3777.1, "text": " So they manually set the restriction maps"}, {"start": 3777.1, "end": 3778.7000000000003, "text": " to certain values, et cetera."}, {"start": 3778.7000000000003, "end": 3780.7000000000003, "text": " Whereas here they are learning the sheaf"}, {"start": 3780.7, "end": 3784.6, "text": " because we'll see in a couple of seconds"}, {"start": 3784.6, "end": 3787.7, "text": " that this contains additional matrix."}, {"start": 3787.7, "end": 3790.8999999999996, "text": " So we'll basically have a three set of matrices,"}, {"start": 3790.8999999999996, "end": 3794.2, "text": " W1, W2, and the one that's hidden here,"}, {"start": 3794.2, "end": 3796.6, "text": " I'm gonna denote it as W3,"}, {"start": 3796.6, "end": 3800.5, "text": " for each of the layers of this neural network."}, {"start": 3800.5, "end": 3802.7, "text": " And the second thing they mentioned is"}, {"start": 3802.7, "end": 3805.2, "text": " our model uses a more residual parameterization"}, {"start": 3805.2, "end": 3807.7999999999997, "text": " of the discretized diffusion process,"}, {"start": 3807.7999999999997, "end": 3809.7999999999997, "text": " which empirically improves its performance."}, {"start": 3809.8, "end": 3813.6000000000004, "text": " Again, residual connections usually work."}, {"start": 3813.6000000000004, "end": 3817.1000000000004, "text": " We know that since 2015, we'd resonate."}, {"start": 3818.0, "end": 3823.0, "text": " Okay, so here is how the sheaf is actually learned."}, {"start": 3824.3, "end": 3828.7000000000003, "text": " They parameterize these restriction maps like this."}, {"start": 3828.7000000000003, "end": 3830.8, "text": " We have this phi of,"}, {"start": 3830.8, "end": 3833.7000000000003, "text": " and we basically input the two nodes."}, {"start": 3833.7000000000003, "end": 3836.1000000000004, "text": " And depending on the features of those nodes,"}, {"start": 3836.1000000000004, "end": 3838.2000000000003, "text": " we're gonna basically output"}, {"start": 3838.2, "end": 3840.3999999999996, "text": " a particular restriction map."}, {"start": 3840.3999999999996, "end": 3843.0, "text": " So it's a map that looks like this."}, {"start": 3843.0, "end": 3846.8999999999996, "text": " Basically we concatenate the features of those two nodes."}, {"start": 3846.8999999999996, "end": 3850.7, "text": " We linearly map them with W"}, {"start": 3850.7, "end": 3852.7, "text": " and then we apply some non-linearity."}, {"start": 3852.7, "end": 3855.8999999999996, "text": " And that's how we end up with a restriction map."}, {"start": 3855.8999999999996, "end": 3857.7, "text": " So now you're gonna use these"}, {"start": 3857.7, "end": 3861.7, "text": " to form the graph loplation matrix,"}, {"start": 3861.7, "end": 3866.7, "text": " which is gonna be your basically block type of a matrix"}, {"start": 3866.7, "end": 3870.0, "text": " that's gonna have some blocks here, some blocks here."}, {"start": 3870.0, "end": 3872.2999999999997, "text": " So that's your sheaf loplation."}, {"start": 3872.2999999999997, "end": 3874.5, "text": " And as I said, the parameters here"}, {"start": 3874.5, "end": 3875.8999999999996, "text": " are gonna be learnable this time."}, {"start": 3875.8999999999996, "end": 3877.7, "text": " So you're learning the sheaf structure,"}, {"start": 3877.7, "end": 3879.3999999999996, "text": " which is very, very important."}, {"start": 3879.3999999999996, "end": 3880.3999999999996, "text": " Okay, that's pretty much it."}, {"start": 3880.3999999999996, "end": 3884.0, "text": " They then state here that if you let G be,"}, {"start": 3884.0, "end": 3885.7999999999997, "text": " so this is your graph."}, {"start": 3885.7999999999997, "end": 3887.8999999999996, "text": " That's a final graph with features X."}, {"start": 3887.8999999999996, "end": 3892.8999999999996, "text": " Then if basically the features are different"}, {"start": 3893.0, "end": 3894.5, "text": " for different edges."}, {"start": 3894.5, "end": 3897.3, "text": " So if we have sufficiently different features"}, {"start": 3897.3, "end": 3900.4, "text": " and this phi is an MLP with sufficient capacity,"}, {"start": 3900.4, "end": 3903.6, "text": " they show that phi can learn any sheaf."}, {"start": 3903.6, "end": 3907.6, "text": " So this is very, very probably very expressive architecture."}, {"start": 3908.6, "end": 3912.1, "text": " Finally, they experimented with different sheaf classes."}, {"start": 3912.1, "end": 3916.0, "text": " We saw why one would want to do something like that."}, {"start": 3916.0, "end": 3919.9, "text": " And the ones they've used is diagonal."}, {"start": 3919.9, "end": 3923.1, "text": " Then they've used again the orthogonal ones."}, {"start": 3923.1, "end": 3926.0, "text": " And finally the general ones."}, {"start": 3926.0, "end": 3928.9, "text": " And as you go towards the general ones,"}, {"start": 3928.9, "end": 3931.9, "text": " the computational cost becomes a bit greater."}, {"start": 3931.9, "end": 3934.2999999999997, "text": " For the general one, you have something like this."}, {"start": 3934.2999999999997, "end": 3938.4, "text": " So D cubed and plus M, whereas your regular GCNs,"}, {"start": 3938.4, "end": 3941.6, "text": " your GNNs will have M plus M, just this part here."}, {"start": 3941.6, "end": 3944.2, "text": " So this is the number of nodes plus the number of edges."}, {"start": 3944.2, "end": 3947.2, "text": " So yeah, cubed term, but in practice,"}, {"start": 3947.2, "end": 3949.9, "text": " you'll almost never have to use D that's huge."}, {"start": 3949.9, "end": 3951.2999999999997, "text": " So D is gonna be a small number."}, {"start": 3951.3, "end": 3954.8, "text": " So this can be considered in a way as a constant,"}, {"start": 3954.8, "end": 3957.0, "text": " a bigger one, but like still a constant."}, {"start": 3958.0, "end": 3959.2000000000003, "text": " Here are the results."}, {"start": 3960.2000000000003, "end": 3963.8, "text": " They showed that they pretty much on all of these data sets"}, {"start": 3963.8, "end": 3968.0, "text": " that are more heterophilic as basically determined"}, {"start": 3968.0, "end": 3970.5, "text": " by this homophily level."}, {"start": 3970.5, "end": 3974.2000000000003, "text": " You can see 0.11 means this is a very,"}, {"start": 3974.2000000000003, "end": 3975.7000000000003, "text": " very heterophilic data set."}, {"start": 3975.7000000000003, "end": 3978.2000000000003, "text": " They showed that they outperform all of the previous"}, {"start": 3978.2000000000003, "end": 3979.7000000000003, "text": " baselines pretty much."}, {"start": 3979.7, "end": 3982.7, "text": " There are a couple of exceptions, maybe on Chameleon,"}, {"start": 3982.7, "end": 3985.2999999999997, "text": " this GDCN, which was particularly designed"}, {"start": 3985.2999999999997, "end": 3989.2999999999997, "text": " for heterophilic setting, actually outperforms their model."}, {"start": 3989.2999999999997, "end": 3993.1, "text": " And also on homophilic data sets such as sites here,"}, {"start": 3993.1, "end": 3996.2, "text": " PubMed and Quora, they're outperformed by some"}, {"start": 3996.2, "end": 3999.6, "text": " of the other baselines, which have biases that bias them"}, {"start": 3999.6, "end": 4003.2999999999997, "text": " to perform well for the homophilic setting by design."}, {"start": 4003.2999999999997, "end": 4005.7999999999997, "text": " And that's why it's hard to kind of compete with them,"}, {"start": 4005.7999999999997, "end": 4009.6, "text": " even though in theory, these networks can be able to learn"}, {"start": 4009.6, "end": 4013.1, "text": " even better representations and thus outperform these models."}, {"start": 4013.1, "end": 4015.1, "text": " But that's, I guess, the same thing as with Resonance"}, {"start": 4015.1, "end": 4018.9, "text": " and like VGGs, like VGGs can theoretically learn something,"}, {"start": 4018.9, "end": 4022.6, "text": " but unless you provide these hints, like these identity"}, {"start": 4022.6, "end": 4027.2999999999997, "text": " mappings, the skip connections, you will basically not learn"}, {"start": 4027.2999999999997, "end": 4030.5, "text": " the desired representations."}, {"start": 4030.5, "end": 4033.1, "text": " Okay, that was pretty much it."}, {"start": 4033.1, "end": 4035.7999999999997, "text": " Please let me know if you watched this video all the way"}, {"start": 4035.7999999999997, "end": 4037.7999999999997, "text": " to the end, I would really appreciate that."}, {"start": 4037.8, "end": 4040.6000000000004, "text": " If you did, please comment down below so that I know"}, {"start": 4040.6000000000004, "end": 4043.8, "text": " for the future videos where I wanna go into so much details"}, {"start": 4043.8, "end": 4046.0, "text": " and this video took so much time to prepare."}, {"start": 4046.0, "end": 4050.1000000000004, "text": " Like I literally read a lot of papers, a lot of papers"}, {"start": 4050.1000000000004, "end": 4054.0, "text": " to get the decent knowledge so that I'm comfortable"}, {"start": 4054.0, "end": 4055.7000000000003, "text": " explaining this to you guys."}, {"start": 4055.7000000000003, "end": 4057.7000000000003, "text": " So hopefully you found it useful."}, {"start": 4057.7000000000003, "end": 4060.0, "text": " If you did, again, please leave a comment down below"}, {"start": 4060.0, "end": 4063.1000000000004, "text": " if you actually watched the video to the very end."}, {"start": 4063.1000000000004, "end": 4065.1000000000004, "text": " If you did, congrats."}, {"start": 4065.1000000000004, "end": 4067.1000000000004, "text": " Consider subscribing to this channel,"}, {"start": 4067.1, "end": 4069.5, "text": " share the video out and also consider joining"}, {"start": 4069.5, "end": 4071.0, "text": " our Discord community."}, {"start": 4071.0, "end": 4072.7, "text": " Until next time, bye bye."}, {"start": 4072.7, "end": 4099.7, "text": " Caitlin's"}]