The Unreasonable Effectiveness of Spectral Graph Theory: A Confluence of Algorithms, Geometry & ...

yeah so uh there's a a bit of an ambitious agenda today because uh first of all I've made the talk for a sort of suited for a general scientific audience so um I see a number of experts uh hopefully you'll be uh you'll be entertained by my burgeoning mat lab skills uh even if you know all of the material um and then I also want to give uh an impression uh of sort of the breadth uh and the flavor and intensity of work that's gone on at The Institute over the semester as well of course as justifying the title of the talk as the unreasonable effectiveness of spectral graph Theory okay so towards that end here's the brief agenda uh the Talk's going to have three parts the first part will be the reasonable effectiveness of spectral graph Theory it will be uh about some beautiful classical things and it will serve as an introduction for those of you who who don't know much about about the subject uh of course then we'll move on to the unreasonable Effectiveness and we'll see some things that uh uh are true but but shouldn't be okay and uh and then the last part of the talk will uh will will concern uh using spectral graph Theory to uh uh to confront issues in complexity Theory like things like uh P versus NP uh and the unique games conjecture and uh which will uh will be introduced to in the third part okay so this is the agenda um you need a very small mathematics and physics background for the talk so let me go through the background now okay so here's what you need from the mathematics you just need to know that real symmetric matrices have real igen values and uh igen vectors okay so just to belabor the point let's write down a symmetric Matrix okay this is real because it has you know the entries are real numbers it's symmetric about the diagonal that looks good uh okay so then the claim is that it has real igen values and igen vectors and in fact here are the three igen values I've written them in finite precision these two are roots of some quadratic equation it doesn't matter and here are some corresponding igen vectors okay and uh this is just so that everybody is is on the same page and so that we establish some trust let me uh let's confirm that one of these is an IG Vector I'll just choose one at random okay let's take this one uh all right so you guys can all do the multiplication with me this is one okay that's that's this is zero okay and this is minus one all right so indeed minus one01 is an igen Vector with igen value minus one okay and in general if we have a symmetric Matrix of real entries we'll always be able to find such real IG vectors and real igen values and Associated IG vectors okay that's the math background you need now for the physics background which is somewhat less uh um restrictive you just need to have the intuition that if you that you shouldn't touch the end of this metal thing because it's hot and uh and heat tends to uh tends to go from hot things into things which are less hot okay all right so that brings us to now now we've those are the preliminaries that brings us to uh uh okay so uh sort of the more mathematical aspect of the talk okay so here is a is a cold this is a Taurus or donut okay at the moment it's cold except that we put a little bit of heat at this spot uh and then if we allow uh sort of the heat to diffuse in the in the Taurus it sort of looks like you might expect it's actually very satisfying it makes you feel warm inside uh so the the the the uh the heat disperses until it becomes uniform in the body okay so there's a there's a picture and uh if we had a somewhat sadder Taurus so this is a sadder donut which is which is sort of long and skinny um what you should think about right now what will happen if we if we allow the if we if we again put a little bit of heat there and then allow it to evolve for a bit you can think about sort of whether it should you know whether the heat should spread out faster or slower than in the in the fat Taurus probably people have some intuition and indeed your intuition is correct that uh it starts to spread out but then it gets a little bit trapped here it will get it will go to equilibrium eventually but uh it got trapped for a while because just I mean if we took the cross-section right then the the cross-section of this tus is very thin and it traps heat on one side of the Taurus for a while okay still we get the equilibrium but it took us longer this will be an important uh uh sort of a phenomenon in the talk but the talk is about computation so instead of uh and it's it's going to be about the street objects so instead of having this continuous heat flow we're going to talk about uh a distre version of the heat flow uh so here's a graph a graph is a bunch of vertices which are the yellow dots connected by edges um uh and uh and now we're going to define a sort of a discrete version of this uh of of sort of the way the heat flows but now in this graph okay so so just look at a single vertex and and here are its five neighbors okay this is just I've repeated this over here and maybe there's some initial configuration of heat at this vertex and its neighbors so the middle vertex has lots of heat the surrounding neighbors have somewhat less heat uh and so we expect that if we allow the heat to uh you know evolve for a few moments then uh since since the vertices are exchanging heat say along the edges you know uh the vertex in the middle here will have somewhat less heat after say one step of this discrete time proc process we're going to Define it formally in a second this is just for intuition and uh I don't know what happens at these vertices because of course uh we didn't draw I mean this vertex has other neighbors in the graph from with which it's exchanging heat so I didn't draw what happens there but at this vertex we expected the heat would go down because it has relatively more than its neighbors have um and uh one important point I should make is that okay this this vertex has five neighbors that's called the degree of the vertex and uh for the rest of the talk uh whenever we see a graph all of the vertices will have the same degree so this the degree will not matter but every vertex will have the same degree and that's just making so it makes it easier for us to normalize things that's not Material it's just a technical thing which you can remove in every everything I'll discuss okay um okay so now I want to Define formally what was this process that goes from one configuration to another um so to do that we need to give the vertices names they're not very clever names but we'll name them one up to n and uh and then we can describe a configuration of heat as just a vector right so the I vertex has an amount of heat which is U subi so this is just a vector in RN uh and then we need some way to operate on this Vector okay so this is going to be the discrete analog of the heat flow so it's going to be a you'll see in a minute why it's called the random walk matrix it's a real symmetric n byn Matrix um on the diagonals we'll put one2 down the diagonal and then uh for the off diagonal entries if i j is an edge so if I and J are connected by an edge in this graph we'll put 1 over 2D and otherwise we put zero okay and the important thing about this operator is that if we apply it to some configuration of heat U and then we look at the I coordinate so this is the amount of heat that's on vertex I after we evolve by one step of the heat flow then it's an average it's an average of What the the amount of heat that was there before which is UI and so it's half of that plus half of the average of the neighbors okay and the important thing here is this it's in green is the average of the neighbors these factors 1 half are not so important it's just the parameterization of of time if you wanted time to go more slowly you could make this one 0.99 and you could make this one .01 and do uh so this is these are not so important okay but this is the yeah so this this is what we mean by the sort of discrete uh time heat flow so we apply we multiply by this Matrix we go from one configuration to another all right so here's a I mean this graph was very simple let's now here's a more complicated graph okay so what's going on in this complicated graph um well uh i' I've I've heated up this one vertex here at the bottom and then we'll see what happens when uh when we allow heat to diffuse from this uh from this vertex into the rest of the graph so okay the graph is spinning try not to be alarmed by that uh it's just so you can see all the vertices but you'll notice that as it spins actually there is heat going into the graph some vertices are getting more red than others um the the the points in space that how we've embedded the vertices into R3 here uh is is uh basically completely at random and then there's a point to that which is that if I if I gave you this graph uh uh and I didn't tell you anything about it you know then you know somehow you're just given vertices and list of edges so okay so maybe it just looks like this complicated object to you right there's no at the moment you know sort of a prior you don't have any nice way of thinking about this graph okay so here we let the heat evolve for a little bit and you'll notice that uh some of the vertices are sort of very warm and comfortable uh but then there are lots of vertices that didn't get much heat okay and any of you were left to explain this phenomenon just from this graph it I mean okay it looks difficult at least to explain what's going on here this graph by the way is only on um 200 nodes uh so if you had a graph on a million nodes or 100 million nodes you can think that things would be even more complicated um okay but that's where the sort of the spectral part of things come in so why was it complicated to understand what happened in this graph well it's because if we start with some initial configuration of heat and then we apply this uh walk operator one time this is the this is sort of the resulting vector and if we apply it again then uh you know this Vector has a sum over pass of length one this Vector actually has sums over path of length two and if we applied it K times we would get sums over all the paths of length K between a vertex and all and sort of all the things that can be reached by passive length K and obviously this is getting very complicated so if you try to understand what's going on here from looking at this representation I mean um Good Luck right uh okay but of course since we're applying the same operator over and over again it makes sense to diagonalize it makes okay so let's let's put it in the spectral basis okay so uh remember this W is real and symmetric so it has igen values and IG vectors let's call the IG values mu1 up to Mu n and the I Valu is V1 up to VN okay and um good so now with a little bit of upfront work first we write this initial configuration U uh in the igen basis so now it's a linear combination of the igen vectors uh and but now things are really nice right now if we want to apply this W all that happens here is we just multiply by the corresponding igen values that's how you evolve and if you want to apply W again we just multiply Again by the I values and you know now it's very little effort to do this over and over so if we want to compute the K power for some general K again the representation is just uh you take the representation of U and multiply by the corresponding I values all right so of course this is the whole point of I mean this is this is why you know uh why diagonalizing matrices is really nice uh but we can actually read off a lot about what's going on here in this heat flow uh from this expression so if we if we arrange so that the igen values are decreasing okay then let me tell you uh sort of what's going on here the top IG value is is one okay and it corresponds to the the sort of the uniform distribution it corresponds to a vector that's the same in all the coordinates and this represents the fact that if we're at equilibrium and we and we operate by this W then we stay at equilibrium Okay so equ ibrium has I value one it doesn't change um and if the graph is connected then uh all of the rest actually the way we've defined the graph all the igen values are actually non- negative and uh and if the if the graph is connected then um all of these the rest of the I vales are strictly less than one okay so what you can so you can see that what happens sort of as you evolve here is that well the first IG value is one so sort of this column just stays the same and the rest of the UE vales are strictly less than one so so this this entire part is decaying as we increase K as we increase the time to Infinity okay and this just represents the fact that if the graph is connected then eventually we converge to equilibrium where the heat is uniformly distributed right um uh and now you can say okay well we saw for instance these two different Torah at the beginning one of sort of one of them converts the equilibrium somewhat faster than the other uh from here you can also read off how fast are converging equilibrium uh why okay so I mean you know I mean if all of these numbers we said they're less than one everything that's not mu1 mu2 up to mu1 if they were all much less than one then of course these terms would Decay very fast and you get to equilibrium at a very high speed but let's just look at the sort of the one that's closest to one but not equal to one you know if this if this one is very close to one then actually this mode will Decay slowly under the operation of the of the of the discrete heat flow and so it will take a long time for any contributions from this igen Vector uh to be pushed to zero okay and it turns out that if you if you care about sort of the the first order astics of how this heat spreads out then this uh V2 and mu2 are very important okay so let's just see uh a picture of that right so this was our complicated picture before where we let the heat flow for a long time and you know some some vertices appear to be doing well others are are having a hard time but it's not clear why from this embedding so what I'll do is is I'll take the second igen Vector okay the one which I said controls sort of the first order astics of how the heat spreads out and we'll just uh in this in this coordinate we'll map all the vertices according to their value in this uh in this I Vector okay so here you can see what happens it's very nice all right uh and now you say ah this is why the heat got trapped I mean everything got trapped on on this side because some jerk which is I guess I guess me you know made these guys really well connected and these really well connected and in the in the middle things are somewhat more sparse but the point is that the the spectral data reveals this to you whereas when when you were just confronted with the graph you would have you wouldn't have been able to see this very well um okay so the main point here is that I mean how did I design this this graph so that this this would happen I took a bunch of vertices uh and and uh split them into two sets inside I sampled with some large probability and between the two sets I sampled with some small probability right uh thereby creating this bottleneck that sort of like heat has a hard time to flow between these two sets because uh basically the density here is much higher than the density in between okay and in general you can think about these bottlenecks as objects you know to study for their own right so if I have a graph and I take a set of vertices in the graph um one can Define this Fe so this is the expansion of the set which is trying to get at how much of a bottleneck to set is okay so Fe is the ratio of the number of edges crossing the cut so these blue edges in this picture are the ones across the set s divided by the volume of s that's the expansion of Fe this is you can this is the surface area this is sort of the ratio of the surface area to the volume of s uh and intuitively you might expect that uh if I have a set for which this is small then heat might get trapped in this set because because the surface area compared to the volume is is not very large uh and you can Define for a graph sort of the you know the optimal let's try to find the the worst bottleneck so that's this F star of G okay so we go over all sets I mean uh if you look at it there's there's always sort of the set and also its complement set so that's why we restrict to B size at most half so we're only considering the smaller side of the of the two uh so F star of G represents the smallest bottleneck in the graph G okay so this is a natural thing I mean computationally you should think that uh there are many reasons we might like to study bottlenecks um uh one reason I mean you know bottlenecks are bad in a communication network but also bottlenecks are very good for many other things I mean if your graph is a social network and the edges represent friendships then uh bottlenecks correspond basically to communities to groups of people who communicate more internally than they do externally and uh even perhaps more fundamentally in computer science you know when you're presented with with some massive input uh one of the best things you can do algorithmically is divide and conquer you break the input into two pieces you solve some problem on each piece and then you combine those solutions back together uh and if you want to employ some divide and conquer algorithm then these bottlenecks are really great because it means that uh I can split my uh input into two pieces uh which are both substantial so I sort of substantially reduce the size of the problem I'm thinking about but also I'm reducing the interaction between the two pieces so that when I want to do the conquer step and and uh wait that's not how conquering works when I want to okay at the end once we've solved the two sub problems and we want to put them back together sort of the fact that the interaction between the two sides is small means that we don't have to do so much work to put them back together right they were somewhat independent sub problems okay so this actually turns out to be I would say uh in the modern theory of algorithms one of the most important Concepts we have if not the most uh sort of important concept this notion of expansion okay and uh now I'll tell you sort of the the most basic uh theorem of uh of uh at least this style of spectral graph Theory uh okay one second don't don't look at that yet um which uh is going to tell us something about when these bottlenecks exist and uh sort of what role they play okay before I do that I need to tell you that you know my favorite Matrix is not this walk Matrix W it's actually the Lan the corresponding line Matrix so theine is I minus W okay uh this doesn't do anything okay the igen vectors stay the same the igen values essentially stay the same except now that we just you know every igen value goes from being uh whatever it was to one minus whatever it was I just like this parameterization better because uh when you do it this way you can think about the ion values as energies of some sort so now the the equilibrium State the uniform distribution has I value zero and uh sort of this this bottleneck igen Vector with the one that was that I said was controlling how fast uh heat mixes or how fast heat converges to equilibrium in a graph uh that's sort of the the the lowest non-trivial energy State sort of the lowest non-trivial mode of vibration of the graph okay nothing matters here except that for the rest of the talk I'm going to deal with these things because I like this parameterization better okay so nothing changed except that we reversed the order of the IG values and okay subtracted them from one but here's now something which is uh not so hard to prove but very powerful it's the Cher inequality which says in words that the major obstructions to the heat uh convergent equilibrium fast are these bottlenecks okay so we said that the you know sort of the the the smallest nontrivial igen value uh controls at the first order how fast this uh the heat flow converges and this discrete sugar inequality tells you that you know this second igen value is small is close to zero if and only if there's a bottleneck in the graph okay okay it's in a quantitative sense right I mean okay what I said is qualitative you see quantitatively what happens if Lambda 2 is small of course it means this quantity is small and if this quantity is small it means this quantity is small and you should of course there's like a you know you can you can uh you can remake the world however you like you know in the space between between this uh Power one and this power one half so there's actually a ton of stuff going on there but at least qualitatively that's what this discrete sugar inequality says that uh that the only obstruction to uh to this heat convergent equilibrium uh at least sort of major obstructions are bottlenecks and and the nice thing is that I told you that for many reasons we care about actually being able to compute these bottlenecks uh so this tells us that uh sort of this spectral algorithm that we use to to sort of find the the bottleneck cut uh in this graph actually works in general okay so uh if you want to find the bottleneck cut and you know that one exists then you can use the second igen Vector to find it okay just by an analog of what we did uh to compute this embedding you just arrange things according to the the the igen vector corresponding to Lambda Lambda 2 and it tells you uh where this bottleneck cut is okay and the algorithm is actually very very fast and very simple okay so that's the that sort of concludes the reasonable effectiveness of spectral graph Theory this is the classical Theory it's very nice you know you understand uh you know how you can get control on these bottleneck cuts which as I I I claimed are very important computationally uh using part of the spectrum that's the reasonable part so now we go on to the okay the unreasonable part sort of uh things that happen that uh you wouldn't have expected early on okay so uh all right so we said this is this picture represents the reasonable part we said that when you you know this these uh this spectral information tells you for instance how heat diffuses in a in a graph that's great um there's another sort of viewpoint on on this heat flow process which is called the random walk okay so Random walk in a graph is just uh you started some vertex and then uh you do this random process that at every step just chooses a random neighbor so this you know these are you have to take my word for that these are random I mean they're not uh but you know in some world that they were my random choices uh okay so the random walk just at every point in time we're sitting at a Vertex we choose a okay a random neighbor and uh you know you can think about this is very closely related to the heat flow because if I think about heat as being carried by little particles that move around the graph then this random walk is this trajectory of one of those little particles right and maybe you know sort of uh okay so that's nice um so what's the what's the unreasonable part uh of all this well suppose I told you I mean you know suppose that sort of I felt a bit Jaded by this heat flow it's sort of it's about the large scale behavior of uh um you know tons of little entities moving around the graph and I said I want to sort of look more at like a character study I would like to just uh you know name my particle let's call her Sophia okay that's Sophia and uh and I want to know what happens to Sophia I want to follow Sophia around the graph okay so for instance if I you know here's a here's a trajectory Sophia this this this this is a path that Sophia might take on the Taurus we start her at some point and she walks around at random um and you could say Okay I I actually I want to know some kind of detailed information about the trajectory that Sophia takes okay so this does not fit into the framework that we just discussed in particular physically uh like if you have two particles carrying heat around the graph you know they're completely Anonymous when they uh when they exist at some vertex and go off their histories don't matter doesn't matter where they came from okay so it's it's sort of unreasonable that you would expect to say something about uh about this trajectory I mean really unreasonable there's like uh this is sort of this is a face palm it's like sort of it's it's almost embarrassing to ask the question of can you say something very precise about you know sopia's she's just one little particle of heat her path through the graph okay so okay let me give you an example of one of course I said it's unreasonable so this is you know you know okay so we're going to say something uh but let me give you an example of one such parameter okay so um uh it's the cover time of the graph okay so the cover time of a graph is just you start this random walk Okay so walks around the graph and uh and you look at how long it takes before Sophia has Vis visited every note of the graph at least once okay so it's very much about Sophia's story when has Sophia touched every uh uh every note okay and this was studied uh uh back in the late 70s uh in particular by in in the computer science Community by alus karp lip and loas and rockov oh let me say by the way the reason carp's name is in red here is uh all of the long-term visitors and workshop organizers and so on to the to the Institute I've highlighted their names in red just so you can sort of get a sense of sort of like what the kind of things people have been working on okay uh dick being the director gets his name highlighted as well uh okay so the cover time here's a here's a sort of a a little static picture to start so here here's this sort of uh Taurus graph and uh and the cover time again is going to be we run the random walk until Sophia has has touched every every Square okay and this is just a snapshot where we've run it for a little while and uh and this number is going to represent the number of uncovered squares left okay so here's the here's the random one we'll it'll speed up uh after a bit because other we don't have a there's a protest at five so we have to we have to get out of the room but I mean this is yeah so we're we're tracking Sophia's progress and and uh this is how many nodes are left uncovered okay and then there's one more thing you'll see here which is uh just to get a flavor for the the way in which this one particle say is imparting heat to the graph the uh a square gets colored by the number of visits to that square so you'll see some squares start to become you know much hotter than other squares because they've been visited more so here's the it'll speed up again so it'll I mean could take a bit it's a good chance to but I mean it's very this is this is a very simple graph but already the way that this graph gets covered is quite complex you know you have these big jumps where you cover whole clusters and there's a there's a while where you're not making any progress at all and then uh you know you know and then there's this sort of last phase where you have to really collect it's I guess we're not so close to the last phase you really have to collect all of the remaining uh particles uh this Taurus is slightly transparent so there you can see there's one particle right there that that will not be the last I mean that that's not going to be the last one actually I'm not sure where the last one occurs uh we're just down to seven now though I it say's one there one there interesting four it gets a little frustrating after a while you really wish you could jump in and help ah there were two particles there there's still one that's uncovered three I know that this stops eventually because this is actually a video and not a simulation uh okay and then okay and the sad thing about this video is that okay it stops at one uh because uh somehow there was a bug in my code but okay wait no no but okay there okay that's that was a that was a very cheap trick I mean I but okay so this is what it looks like at the end we've covered the whole graph it's it's down to zero but the point I want to emphasize that even on this very simple this very simple graph which has tons of symmetry and so forth you know the time at which you touch the last ver Vex is is okay it looks like a very complicated function of of Sophia's trajectory through I don't want to say through life I'm sure she has more to do but at least through the Taurus um okay so yeah so I've told you that it's unreasonable that we should be able to describe for instance this cover time the time it takes to touch every node of a graph in terms of spectral information because it doesn't you know it's sort of it's It's a naive question at first okay but let me just remind you what spectral information we have we have Lan we have it values we have it igen vectors uh and then we're going to need one more thing which is uh just a sequence of IID normal 01 random variables okay so these are just n independent random variables and then now we're just going to go crazy we just consider this quantity okay so what is this quantity this is a random sum from 2 to n okay the first I can value is zero so we don't want to divide by zero it's a random sum from 2 to n uh it's a it's a this this thing is an end dimensional Vector because these VI are vectors and then these are just numbers this is one over theot of the igen value and this is our random number so you just take this random sum of vectors uh with some coefficients given by the I values all right and now suppose that you uh took the max this is a nend dimensional vector vector take the maximum entry in the vector just the largest entry okay and then Square it and then multiply by the number of nodes in the graph all right so this is uh this is like one of those things where you you teach the course and the end that some very excited OV excited student comes up and says I wrote down this formula do you know what it means and you sort of like you just can't write down sequences of symbols and and hope they have some meaning but in this case actually uh this is a random quantity okay and it turns out that this random quantity is very very close to the cover time of the graph G not just for the tourist but for any graph G okay this is true uh so that was proved a few years ago in joint work with Gian Ding and um and yal Paris and in fact it's uh it's really really close so in fact the astics are that as you know as the size of the graph goes to Infinity uh this is a random value okay so uh but this random value uh goes to the cover time up to some little over one error so very you know very precisely to the cover time and so by the way the cover time was was is a number it's the expected number of steps so what do I mean that this random value is close to it well it turns out that this random value is also very concentrated so if you just do an experiment or let's say if you want to be even safer do this sample 10 times times from this sum and take the average it' be very very good estimate of the cover time okay and I should say that a grad student at Sanford Alex XI this year has has really nailed down the astics completely of this connection um okay so so now I want to highlight something about this uh about this random sum which is that it's sort of and this is a this is a key to understanding sort of the unreasonableness and and additional unreasonable things that will happen in a second uh which is that it doesn't just conern a single value or a sing Single igen Vector it contains sort of holistic spectral data right you know the coefficients here contain you know I mean we have all of the IG vectors and all the igen values and actually you can see that we are waiting igen values by by sort of the by their by their value so you know the the smallest igen value right we said that V2 is the one which controls mixing say well V2 is getting the largest weight in this random sum because we're dividing by square root of Lambda 2 and Lambda two is the smallest Dion value so we are sort of favoring the bottom half of the spectrum but we have terms here from all of the ion vectors uh okay so this thing is this this random sum this is a sort of an end this is random Vector is called the Gin free field and uh you can think about it as a sort of it's a it's like it's like of a random surface that sits on top of your graph okay so there this this field has all kinds of beautiful properties and connections uh and what we said on the previous slide is just that if you sample from this random field and then you look at the the the the highest peak of this random field then that Peak will describe to you very accurately the cover time of the graph okay that's what we that's what we said before um okay so there you might think uh that uh well okay we have some random process and then I have another random process and you could you could ask if anything became simpler but let me just say that you know we understand this thing very very well much better than we understood understand or at least understood before the connection cover times so you can prove lots of things about covered times from understanding that they're related to this this spectral data okay so that's one thing now another thing you might ask is okay you promised to prove things in uh like with pictures in this talk so I would like to prove this to you with a with a with an animation but actually proving this was an animation is a major open problem I mean literally like if you could design an animation that would convince the audience of the fact that it's true that would be a huge deal and it would be great to see it uh so instead uh I mean you know the reason this connection exists is uh of course it goes back to physics and uh it it deals with it sort of has to do with combinatorics of you know uh like uh findan integral sort of like integrating over all paths the particle could take and you get some cancellations and everything works out beautifully and there's a connection it is still as mysterious as it sounds um but let me but let me say one aspect of it that's less mysterious and relates to things that other people in the program have been doing quite a bit uh which is sort of another physical process that has spectral implications okay so this physical process is a uh electrical networks okay so here so here I have a graph now I want to think about the graph as an electrical Network so I'm going to think about all the edges as resistors just say with resistance one so I put resistors on all the edges and then uh we connect a battery we we create a a voltage difference of say one between two nodes A and B okay so I have an electrical network uh uh I create a a potential difference between a and b and this potential difference will induce current to flow from A to B through this network and the current you know what will the electrons do in the current well they will you know they will on you know in general they will they will try to follow some path of least resistance where the resistance is based on uh sort of like how much the edges are resisting their flow and also how many electrons are in on a particular Edge the more they get there the less additional electrons would like to go along that edge uh but if you remember High School physics the effective resistance between A and B is uh is uh is the inverse of the current that we induce when we create this potential difference okay and the point is that this uh effective resistance has a spectral interpretation so you can write the effective resistance in this way between two nodes A and B if I look at the you know I look at a sum divide by Lambda I this is the I Vector in the coordinate a and this is the ion Vector in coordinate B okay so this sum is equal to the effective resistance and you can see at least some relationship here okay so uh you know so one aspect that goes into this connection is uh deals with the fact that there's another interpretation of a physical process these uh electrical networks in terms of the spectral data okay uh so let me just uh say uh okay so now I'm going to tell you a few more things about unreasonableness um that have been going on to the program so the the first question you might ask is okay you have all these spectral objects you say that they're nice and they're useful can you compute them fast okay so this turns out to be the question of whether you can solve linear systems of the following form you're given L which is the Lan and you're given B and you want to solve the linear system LX equals B you want to find x x is the unknown okay I mean by the way this this problem is you know is so is incredibly important like in you know essentially it comes up in every physical simulation you know sort of a every discreation of a partial differential equation every simulation that Boeing wants to do to figure out how wind flows over a wing or people want to do to figure out how nanomaterials uh will act in the environment you end up solving systems like this they're remarkably important and the point is that starting with work of Spielman and tang in 2004 and then um sequence of works I just highlighted some of them uh kudus Miller Pang who really got this the the running time down to be very very fast now I mean you know now it's possible to solve these linear systems in time which is uh sort of okay so what what matters is the number of non-zero entries in PL in L but uh you can do it in time which is faster than the time unit to sort the entries of L like sorting takes now longer than solving uh these linear systems from an ASM totic analysis perspective um okay so that's one thing there's a ton of work uh there and then of course I said you can do unreasonable things so the idea that you can solve linear systems fast is is beautiful and it's very and the work there is is is remarkable but it's not so unreasonable okay uh but the point is that uh the answer is yes so in particular you can uh you can make progress on on one of the oldest problems in computer science sort of the problem of computing maximum flows and Min Cuts in a graph this goes back to the the 50s and earlier uh and uh okay so there's a sequence of work uh some of which I've highlighted on this slide let me just say what the basic idea there is which is that uh so a a maximum flow is like if you if you want to send flow between two nodes of a graph and you think about the graph as sort of a network of pipes and the flow is you know say oil sounds like a controversial thing let's say you want to send water that's also controversial in California okay all right you want to send some uh some fluid from A to B you know and you're you're you're limited by the capacity of these pipes so the way sort of you can send fluid maximally from A to B that's the maximum flow problem and uh uh so the way that these Works sort of starting with this work of Cristiano keler MRE bman and Tang for instance managed to solve maximum flows using this connection uh to electrical networks is that I mean when you set up this battery here it induces a flow of electrons from A to B okay that flow of electrons is not in any way a maximum flow in particular it's perfectly happy to violate the capacities of the edges and so on it's minimizing some quantity which is very different I mean it's iing a quanti is very different from what the maximum flow is but this just you know but it does give you sort of a hint as to sort of like how something is flowing in the graph and it turns out in many situations uh in life and also in this area that uh the hint is enough to solve the problem once you have a hint like once you have a an inkling of the right direction uh then you can do some kind of basically very clever gradient descent and uh and solve uh and and solve the max flow problem okay so this is this is unreasonable and let me just highlight the fact that even with with recent work of majri it gets even more unreasonable because uh majri is able to do this for directed graphs okay you know the notion of electrical flow and electrical networks is sort of fundamentally undirected okay I maybe if you're clever at physics you can come up with a directed model for a directed Network I don't know how to do it uh so the fact that you can use these things to solve directed flow problems this is very counterintuitive to me okay uh but it's true and it it's yet another sort of unreasonable thing that one can do with these sort of spectral data about a graph okay so now in our in our okay we have 10 minutes left uh so I want to go to the third part which is sort of the borders of intractability all right so here we were talking about sort of like a very efficient computation you know people in the room like Gary and Giannis when they say you know I think Giannis laughed at me once when I described a linear you know a linear system that had 100,00 variables because you know he's like things don't get interesting until you get into the millions uh right so these things can be used to solve uh problems very very fast okay and uh but now I want to switch perspectives and talk about sort of uh you know whether problems can be solved in an efficient manner at all okay so uh okay so uh so I'm going to tell you now about one problem which has had sort of hold a central place in algorithms in the past uh uh 10 to 15 years at least which is the the unique games problem okay so you're given a prime number P and you're given a bunch of linear equations in two variables okay over P so I have a bunch of variables X1 to xn and my equations are like x13 - X7 = 4 and okay I have a bunch of these equations okay and uh uh now I would like to find you know I'd like to I'd like to solve this system of equations if it has a solution uh and in fact the computational problem I want to think about is suppose I tell you that 99% of the equations are satisfiable okay what that means is that there exists a setting uh of numbers between Z and P minus one to X1 up to xn such that 99% of these equalities are satisfied okay so I'm telling you that the lots of them can be satisfied almost all of them and I just and I say look you know I know it's your first day on the job uh can you find a solution that satisfies 1% of the equations okay so if if they were all simultaneously satisfiable uh then it's actually easy you can use G elimination or at least in in this simple setting the way I've given you these things you know if I give you a value for x13 there's a unique value for X7 that's satisfies this equation so you can just go around plugging things in after you just guess one value okay uh but this is the computational problem if I if I give you a system which is not fully satisfiable but there's a little bit of noise can you do even a little better than trivial can you get a an assignment that satisfies 1% of the equations and code in 2002 conjectured this problem is not uh easy to solve uh like you will not be able to come up with an efficient algorithm to solve it that was his conjecture and in fact he won the nean lenina prize for many things but actually mainly for this conjecture and its implications this conjecture is very nice because uh as opposed to P versus NP which is sort of like a stark separation this conjecture basically inside it has a knob where you can sort of increase the computational difficulty of a problem and maybe you can hope that if sort of if you have such a knob and you can understand how well it affects the difficulty of a problem then you know this will help you to understand for instance what problems can be solved efficiently and not this you know that's but this is why the this conjecture is say different from P versus NP because it comes with this this knob and the knob appears to have a you a lot of useful properties okay so here's a here's a way you might solve this problem okay right I gave you I gave you this system I promise you that it's nearly almost satisfiable so how would you go about trying to find a solution here's one way okay you can associate a graph to this problem by you know if two if two variables appear in a constraint together you put an edge between them uh and then what you do is you sort of create what's called a lift of this graph so for every vertex in the graph you create P copies of the vertex above it and then if you okay now you want to fill in this lift actually what you do is you know uh for every value I can assign to a something on one of the variables it gives me a unique value to the other that satisfies the equation and that determines how you put edges in this graph you connect two things if they if if those two assignments would satisfy the corresponding constraint um and uh if you think about it for for a lack of time not be labored too much um but uh if you want to solve this then a good way to make progress is to try to find a set in this graph uh without too many edges Crossing it because edges you know okay um okay that that sort of makes sense except for the fact that uh you know if I want my set for instance to correspond to an assignment uh to the to these variables then from every fiber from every set of P variables sitting up here I should only select one for inclusion in my set okay so it's really less it's not so much a problem about finding a single bottleneck as it is and maybe this is unclear I'm not going to be labor it as I said because of lack of time but this turns out to be a problem about finding lots of disjoint bottlenecks right we talked about finding a single bottleneck before and now if you want to solve this problem one way to do it is to find lots of these joint bottlenecks um uh you know the one nice thing about having this joint box Bott NE is that the bottleneck sets have to be small and somehow the smallness of the set corresponds that you're only allowed to select one vertex from every fiber but let's not let's not go into that too much right now let me just talk about this problem more generally okay so we saw that uh you know the second I Vector can help us find you know partitions into two sets uh but something that people have studied for a long time in machine learning and in in vision and in image processing is you know suppose I want to I want to break things into more sets because generally data has more than has two interesting you know clusters in it okay uh so suppose I want to do something like this uh so I'm now I'm concerned not so much with finding a single bottleneck as finding a bunch of disjoint bottlenecks okay so sort of like this is the the new problem and here we said that there was a a quantitative parameter F star of G that describes the worst bottleneck in the same way you can have a there's a quantitative parameter you can Define I'm not going to Define it uh FK star of G which just says that the graph has k bottlenecks uh sort of K disjoint sets Each of which is a bottleneck this is what FK star of G is is describing and then if you want if you want to have some theoretical analysis of this connection then what you'd want is a is sort of a an an analog a higher order analog of the cheer inequality we saw before this inequality says that bottlenecks uh relate to uh sort of igen values and you might want something that looks like this where you say ah okay maybe having K bottlenecks relates to the you know having Cas small I values this might be this is a natural thing to try and do okay so here is uh here's the question and uh of course it turns out that this question was asked uh in uh in mathematical physics in the 70s okay people studying B Einstein condensation please don't ask me what that means um uh okay so B basically uh this paper posed this problem okay the connection realizing that this is the problem they were saying was much B later by lauron Miko uh and uh so really and and the question is not so much about finding what they need over here is not so much about finding disjoint bottlenecks what they need is the ability to find small bottlenecks of course if you can find many disjoint bottlenecks one of them will be small okay so it's a harder problem to find many dis joint ones um well I just let me say that this finding small bottleneck this is exactly sort of the small side expansion problem that we'll come to in the concluding uh slide okay okay and I should say that even in this paper they sort of they realized although they didn't prove it that you shouldn't be able to get you know this beautiful square root of two here you have to pay something over here that depends on K they they suspected that to be the case in the paper and it was confirmed later that you have to pay something depending on K here uh and let me just say Okay so uh in work with uh Cheyenne who's a and and Luca who were of course both at Simon's uh uh for the for the program Luka is here Luca is now research scientist at Simons and uh cheyen was here but he's joining Miss in Seattle uh we managed to prove that this is true okay uh so you can the C of K you can make to be K squ and uh okay and I should also say that uh Lewis ragavendra Tali and vanala proved a related statement which is also sufficient to resolve uh to resolve this conjecture okay so one thing I want to say is that uh you know the proof of this actually uh you know is algorithmic and the algorithm is taking a an algorithm proposed by in Jordan and Weiss uh about a decade ago and changing one step of it okay so I mean this is really this really is a problem that came from mathematical physics that people in machine learning studied uh and it has beautiful connection to spectral graph Theory and and spectral geometry uh and even I mean and Giannis is actually you know I mean and sort of using it you can talk to him using related this and related ideas for uh image segmentation uh at at The Institute this year but let me just say the one thing I wanted to to focus on is not this but this C of K okay and the reason is because if this C if this C of K could be made in something it doesn't depend on K uh that would uh that would refute this unique games conjecture okay um now you might say okay that's not very interesting because you told me that that uh it has to depend on K so okay so why are you belaboring this but the but the point is that Aurora Barack and store showed that in a certain regime actually you don't have to pay this dependence on K okay so the regime is the following one uh you give me say n to the 0.1 small igen values and then I can find a set uh which is non trly small say n to the99 which is a bottleneck set so it's a small bottleneck set and what I pay is say only a factor of 100 has no dependence on has no dependence on this number of I values okay and the the the reason this is weaker than what we said before is because this sort of only holds in this regime where you have many many many igen values if I give you 10 igen values you can't say anything but if I give you a very very large number of them then you can get rid of this dependence on K that's what they they proved so uh okay for experts you know why this is in quotes for the rest of us Let's ignore that it's in quotes but basically uh if you could improve this bound at all in other words if you could do this with fewer than n to the point1 igen values n to the you know some number which is going to zero slowly with n then you would disprove the any games conjecture okay uh okay so that's one nice approach you might say there's there's one slide left after this we're almost done that's you might say that this is a okay this is a you know it's a great approach but if the approach fails you know maybe this all this this spectral business was was nonsense but I but it you know okay we have evidence that it's not so for instance um uh in trying to find lower bounds so graphs that have many igen values but no small many small ion values but no small bottlenecks uh this group of uh authors came up with something called the short code okay which is a very nice Construction in complexity theory that has lots of implications like complexity theoretic implications so the point is that you know studying this spectral problem G you know gives you some way of thinking about the world that has implication you can actually prove things beyond the spectral framework okay so I mean usually when this happens it indicates that you're you're looking at the right phenomenon you know sort of like a you if you if you can if you can prove upper bounds you get something but also when you think about proving lower bounds you don't just limit this method you end up sort of limiting all efficient computational methods in some to some extent okay so uh yeah so I mean this is a huge open this this problem is still open whether you can improve this bound uh uh and it's incredibly interesting right so this is the last slide and the question is just what's next sort of you know we said uh there's reasonable spectral things you can do but then if you look at this holistic spectral package actually you can do lots of things that you wouldn't expected have expected uh initially maybe there's even a a richer package you can look at okay and as aliser said this richer package actually connects the two programs at the Simon's Institute um because Computing igen values and spectral information is just it's sort of one instance of uh of optimizing over using a semi-definite program or or a Spectra hedron this picture is stolen from from Baron sternfels this yellow thing is a picture of a threedimensional spectr hedron that he fondly calls the Samosa um uh but the point is that you know optimizing over such spectrahedra we can do it efficiently and uh you can see these spectral methods as just one you know optimizing over one particular set of spectral heed and it turns out that there's a canonical sort of uh increasingly complex set of spectrahedra given by What's called the sum of squares hierarchy okay and uh you know so so when you want to go beyond spectral methods you can sort of you can pass to this more General method using semi-definite programs and we know that assuming in new games conjecture this sum of squares method is optimal okay sort of like well for for a very wide class of problems you know sort of these these algorithms based on stps will be the best you can do and in in recent work at the actually The Institute this semester with Prasad and David we showed actually that unconditionally if you restrict yourself to semi-definite programs then uh then this this this sort of sum of of squares approach is optimal okay so we know that you can go a little further than spectral techniques but uh but there's a boundary there and we have a good idea of sort of like at least for a wide class of problems sort of like the limit of how far you can go okay and of course I mean understand whether these are really the limits or whether they are better algorithms is uh is still one of the main research directions in this area Okay so that's the end uh I keep saying that but this is now you now the second half of this slide will be the end if if this was incredibly compelling to you and you're wondering you know okay fine you told me all the stories now I'll move on with my life let me just say that you know if I had in hour three of the talk I would have told you about uh this remarkably compelling story that starts with dck and the foundations of quantum Computing and goes to solving linear systems and uh to the reman hypothesis and then ends up in recent work of uh done at the Institute uh on the traveling salesman problem uh so if you uh if you really want to know about this you should you should uh you should talk to these guys uh who are around or or go read their papers but basically through a you know a beautiful sequence of work that starts you know in a very abstract questions in the foundations of quantum mechanics uh recently uh at The Institute uh anari and uh and Cheyenne were able to uh give the first you know give give an improvement to the ATM metric traveling salesman problem which is sort of like one of the classical problems of comori optimization okay so like this is yet another example of sort of like physics and geometry and spectral techniques colliding in a completely unreasonable way okay all right so let me stop there [Applause] thanks yeah uh yeah so a spectran is just uh you take the cone of positive semidefinite matrices and intersect it with an a linear Subspace or an aine Subspace so it's it's really is just the feasible region of a semi-definite program you know there are lots of semi-definite programs one can write down though and so it's nice that maybe there is a theory that you don't have to consider all of them there's only very particular kind that you need to write down to solve your problem does anybody know where the protests are sorry getting go ahead getting where where people are congregating in spra okay yeah can you say a little yeah you just um so I mean you'll notice I mean okay uh you you need to be able to do something similar with the number of igen values that's end to the little low of one so for instance uh n to little low of one so say something similar where if I give you uh two to the square root log values uh then you can get a sequence of sets which are getting smaller and smaller and but which are bottlenecks and the and the important thing is that you know you get this bottleneck upper bound with something here it does not depend on the number of ion vales you use

Channel: Simons Institute

Views: 44,465

Keywords: Simons Institute, UC Berkeley, computer science, theory of computing, James R. Lee, Spectral Graph Theory

Id: 8XJes6XFjxM

Length: 56min 25sec (3385 seconds)

Published: Thu Dec 11 2014