Latest / Strachey Lectures / Strachey Lecture: Symmetry and Similarity

Transcript

Strachey Lecture: Symmetry and Similarity · Strachey Lectures

• 0:00
  Okay. So welcome to this term strategy lecture.
• 0:18
  This is a distinguished lecture that we have once a term named after Professor Christopher Straight G who formed the programming research group here.
• 0:28
  I'm going to introduce our speaker.
• 0:30
  But before I do that, I would like to thank Oxford Assets Management, who have been generously funding this series of talks since 2015.
• 0:42
  And without their funding, we wouldn't be able to have excellent speakers as we do.
• 0:47
  So we're really grateful for that. And also, they brought coffee and doughnuts.
• 0:53
  So many students and researchers who might wonder about employment might want to go chat to them afterwards.
• 1:01
  And they they they're sitting. They'll be up at reception.
• 1:05
  So you might like to do that. The way we're going to do this is, as usual,
• 1:09
  Martin will give his talk and then we'll have some microphones afterwards that you can wander around and ask questions.
• 1:18
  So that brings me to introducing Martin Grillo, which is actually a brilliant pleasure.
• 1:24
  So Martin is the chair for Logic and the theory of discrete systems at the university are w t h ipa.
• 1:32
  But he says that somewhere there. Yeah. And he's well known actually for a bunch of different fields that intersect in our department.
• 1:42
  So Martin has written the key textbooks in multiple areas, including Parameterised complexity,
• 1:53
  which is pretty much the the scripture of Parameterised Complexity is Martin's book, which I think many of us actually own.
• 2:01
  He's also got a great book on descriptive descriptive complexity of graph structures.
• 2:06
  And actually. Martin, some years ago, I was talking to Martin at a workshop,
• 2:11
  and he told me I'm going to step back from the things that I'm doing and work exclusively on graphs and autism.
• 2:20
  And I remember being immediately jealous and thinking, what a great idea.
• 2:23
  What do I do that? MARTIN Someone who has worked on truly deep things.
• 2:30
  And so he had a lot of really great results about graphs and more them.
• 2:34
  But I know just by looking at your DLP that he's also done something I didn't predict,
• 2:41
  which is that after all that those kind of amazing theoretical results,
• 2:45
  you have a result in triple j lie about graphs amorphous on the neural net, which has about a thousand citations.
• 2:52
  So and I noticed also Martin's got a lot of new stuff about probabilistic databases, so lots to offer.
• 3:01
  I'm going to shut up. So I'm only going to mention two of Martin's many awards.
• 3:05
  So Martin is the recipient of the Hynes Meyer Leibniz Prize from the German
• 3:10
  Research Foundation for his work in mathematics and also fellow at the ACM.
• 3:16
  And we're super lucky to have him here today talking about symmetry and similarity.
• 3:22
  That's what. Oh, good afternoon, everybody.
• 3:33
  I'm also very happy to be here. Thank you for the introduction, Leslie.
• 3:38
  I will talk about symmetry and similarity.
• 3:41
  Just one thing to clarify before I heard the doughnuts are only for the students or people who look for employment.
• 3:48
  I was counting on them, so you may have to reconsider that.
• 3:54
  Okay, so today I'll speak about symmetry and similarity.
• 3:58
  Part of it is graph I, some of ism and indeed for a while I mainly worked on that.
• 4:05
  But then I mean,
• 4:06
  the nice thing about my job is that you can do different things whenever you feel like doing something else and nobody tells you what to do.
• 4:14
  So that's, that's what I do.
• 4:17
  And as Leslie said recently, I've done some other stuff, but at the end of my talk I will connect to that as well.
• 4:25
  So let's talk a little bit about symmetry.
• 4:29
  So symmetry is somehow something that has been ingrained in human thought for a long time.
• 4:36
  You see this phrase here, which has an obvious symmetry on there.
• 4:40
  I hope you can you can see it.
• 4:43
  It's 4000 years old. So even at that time, people were very aware of it and somehow found it's important enough to put on on there the pieces of art.
• 4:59
  And of course, actually, you find symmetry everywhere, not only in human thought, but in nature.
• 5:04
  That's probably where humans get it from also there.
• 5:08
  So it's good that I removed my slide with the butterfly,
• 5:12
  which in earlier versions of of talks about this was presence, but of course being in the Museum of Natural History.
• 5:25
  That fits. Okay, so we have that. And then of course, we have symmetry in the arts.
• 5:30
  We have already seen this on the first slide. He has a very nice and intricate example as well.
• 5:38
  And we have symmetry in mathematics. And that brings us closer to what I'll speak about.
• 5:44
  So what is symmetry in mathematics?
• 5:46
  It's basically invariance under certain operations, and typically we think of geometric operations like reflections or rotations.
• 5:56
  So in this octave we have we can basically turn it or we can flip it.
• 6:02
  And another very typical geometric thing which.
• 6:08
  At least I don't think about it immediately. But it's also something very familiar.
• 6:14
  It's a translation. So if you imagine this banner is infinite and you can shift it and there would also be some kind of symmetry.
• 6:23
  Okay. And I may I'm listing these different things just to make the point that symmetry has some some abstract properties,
• 6:33
  and they will be very important for what follows. So let me just fix them.
• 6:38
  So we have a mathematical object and the symmetry of this object, or depending on which area we are in, we may also call them or two or more.
• 6:48
  Phases of the objects are mappings from the object to itself and they are closed under composition.
• 6:58
  So if you take one symmetry, apply it and then you apply another one, you get a symmetry as well and they also inverted.
• 7:06
  You can always go back. I mean, these are the crucial properties they have and the mathematical structure they form.
• 7:15
  Is known as a group. Okay. And this will be important because as a general principle, we will think about computation or computing symmetries.
• 7:28
  Okay. And as soon as we have a mathematical structure, there's a chance that we can get efficient algorithms.
• 7:35
  As a general principle, I think that's that's fairly reliable.
• 7:40
  In particular, if you're in the range of kind of harder problems,
• 7:44
  you want to look for mathematical structure and you want to find ways to make it useful.
• 7:49
  And that's the guiding principle of much of the research on this stuff.
• 7:55
  I'll be I'll be talking about today. Okay.
• 7:58
  And now.
• 7:59
  Okay, we have a group and the group of old symmetries of an Object X is then known as Symmetry Group of the Object or the Automotive ISM Group.
• 8:08
  And actually in the area I'll be talking about, we would rather say automotive ISM Group.
• 8:14
  Okay. And just one last general remark.
• 8:19
  Autumn of isms. That's the symmetries of the objects are closely related to ISO Morph isms,
• 8:27
  which are basically mappings between two objects that preserve old structure.
• 8:33
  Okay. If you.
• 8:36
  If you forget all the geometry and everything, then an automotive business is a mapping from an object to itself that preserves structure.
• 8:45
  And I some of ism is between two objects and the the two for the purpose of this talk are more or less equivalent.
• 8:54
  Okay, if we understand the automotive isms, we understand ISO Molefe isms and the other way around.
• 9:01
  All right. So I want to talk about algorithmic aspects of symmetry.
• 9:07
  Okay. And they are mostly captured in an old problem in computer science and well-known problem.
• 9:14
  That's the graph. I am off isn't problem.
• 9:16
  So let me start by telling you what that is and then tell you a little bit about the history of this problem and what we know.
• 9:26
  And well, then we'll arrive at some more reason to work.
• 9:31
  Okay, so a graph, I assume you'll know what that is.
• 9:35
  We have a bunch of points and they are connected by lines, by bi edges.
• 9:41
  And then in automotive ISM or ISO morph ism is a mapping on the points on the vertices that preserves this edge relation.
• 9:52
  Okay. And the graph I am office and problem as an algorithmic problem is the following.
• 9:57
  We're given two graphs and we want to decide if they are similar, if they are basically capturing the same structure.
• 10:05
  Okay, but we may be given this the structure in different representations.
• 10:09
  That's why it's not trivial. And if you look at these four graphs here, they are fairly small, just eight vertices.
• 10:17
  Well, are they ISO morphic or not? It's it's not obvious.
• 10:23
  At least if you look at the last one, it's not obvious at all.
• 10:27
  Well, actually, they are all four of them are ISO morphic.
• 10:30
  So in some sense they are all the same graph just drawn differently.
• 10:36
  But it's not so easy to see this, but just to check a random one.
• 10:41
  How could we check this? The way I would do this just by hand is maybe, maybe number the vertices of the first one.
• 10:49
  Let's just do this. Okay.
• 10:53
  So that's the Burgesses. And now we want to map it to the vertices of the second one, the red one.
• 10:59
  Can you distinguish the colours? Well, uh, upper right corner in a way that basically the same numbering then has the same edges.
• 11:09
  So I would maybe start with the one here.
• 11:13
  Put the two here. Three.
• 11:17
  No, this should work for five. Six, seven, eight.
• 11:23
  So that's what we can try. Now, what we must check is, for example, here we have an edge between one and two.
• 11:31
  Okay. And we want to find that edge here as well. Okay.
• 11:35
  We also have one between one and two. Now, let's take a random one.
• 11:39
  Two and six. There's no edge. So I did something wrong.
• 11:45
  Okay. Yeah, that's the thing with these crafts.
• 11:52
  Um. Why did I do this wrong?
• 11:58
  So this. You should be six. Did I miss? Well, okay.
• 12:06
  No, I want to figure this out now. Sorry for wasting your time.
• 12:10
  So that was bad. Okay, let's.
• 12:14
  Let's try it this way. We have one.
• 12:18
  One is adjacent, so this should be maybe eight. Okay.
• 12:26
  Stop me after about half an hour. Okay.
• 12:31
  So we have one maybe, let's say this year is five and this is two.
• 12:37
  Then the three was wrong anyway.
• 12:43
  So five, eight. So the two we have one, two.
• 12:49
  Three. Three should be that. And then.
• 12:54
  Six should be there. That is good because it also fits to five.
• 13:01
  And this probably must be for. It's.
• 13:06
  Then it's between three and eight. No. Okay. I'm missing this up.
• 13:10
  Forget it. I leave this as an exercise to you and exercise to you to edit this from the film.
• 13:20
  But anyway. Okay, so you saw my point.
• 13:24
  It's a heart problem right here. And we need a computer to solve it.
• 13:29
  Good. So that's what we want to do. And we have this other problem.
• 13:33
  I talked about computing, this symmetry, the automotive ism of one graph, of course, that we can also do.
• 13:42
  There's only one problem. There can be too many. Okay. A graph with n vertices may have up to m factorial, many automotive isms.
• 13:52
  And just that's just too many to just to to list them all.
• 13:57
  Okay. So what we actually want to do, we want to continue to generating system for them.
• 14:03
  So a set of automotive isms such that all others can be obtained as compositions of these.
• 14:09
  Okay. And then it turns out that these two problems are equivalent in the sense that if you can solve one efficiently, you can solve the other.
• 14:18
  That's not completely trivial to see, but it's it's something that has been known for a long time.
• 14:25
  Okay. And we want to exploit this because mostly our approach will be to address the second problem,
• 14:32
  the automotive ISM problem, even though in practice we usually want to solve the first one.
• 14:38
  Okay.
• 14:39
  So the big open question is if is there an efficient algorithm solving this problem and our model of efficient algorithm is polynomial time algorithm.
• 14:51
  Now you can debate if that's a good model. Well, my answer to this is probably not, but it's the best we have.
• 14:58
  So we want to go for a polynomial time algorithm for this problem or the other.
• 15:03
  The automotive is ism problem as they are equivalence.
• 15:06
  Okay. Let me just remind you of a little bit.
• 15:13
  Complexity that you see probably in your first theory course, but that's important to you to set the stage for this problem.
• 15:20
  We have the class of polynomial time solvable problems, the ones that we can solve efficiently.
• 15:26
  Then we have this class MP which contains them and many other natural problems.
• 15:32
  And you can describe this class as the problems well, where you cannot find the solution efficiently.
• 15:38
  But at least once somebody suggests a solution, you can check efficiently if it is a solution.
• 15:44
  Okay. So that's MP.
• 15:48
  Many natural problems fall in there. But then we have the class of MP complete problem limbs on the top here, which are the hardest problems in MP.
• 16:01
  So if you can solve one of these efficiently, you can solve all the others in MP also efficiently.
• 16:07
  And what happens is that most natural problems that you see in the applications
• 16:13
  are either here they are in p complete or here they are never in between.
• 16:19
  Okay, now provide some of reasons. One of the very few problems where we don't know where it belongs.
• 16:25
  Okay. And we don't know for a long time now.
• 16:32
  So when I was a student, I was basically learning that probably it's a problem that is in between.
• 16:39
  Now, I don't believe this, and I think these days people don't believe this anymore.
• 16:43
  I think we we we all believe it should actually be in polynomial time.
• 16:47
  We only can't prove it. But anyway, what we can do.
• 16:51
  And that has been proved by bye bye 2016.
• 16:56
  So, so not so long ago. And that was a big result. We can prove that it comes close.
• 17:01
  It's solvable in what we call quasi polynomial time.
• 17:05
  It's it's still something that has a kind of exponential growth.
• 17:12
  But the x, the exponents of all of this is just growing logarithmic.
• 17:19
  So that's kind of close to a constant.
• 17:23
  And then it would be polynomial. Okay, so, so that's pretty good.
• 17:29
  It's a really nice paper. And so there is still progress in this area, but where does the whole thing come from?
• 17:38
  Actually, the first papers on computing I some of isms come from chemistry or chemical information systems to be precise.
• 17:48
  So the chemists have these graph representations of molecules like the one you see there, and so they stored them in databases.
• 17:58
  But then you can draw the same molecule in different ways. So when they find a new one, they want to know, is it already in our database or not?
• 18:06
  So they have to match it against those in the database. That's the problem they faced.
• 18:10
  That's the ISO morph isn't problem. So, so, so they came up with some heuristics and then computer sciences.
• 18:18
  So that's an early reference from the from the 1950s.
• 18:22
  Right. And then computer scientist, the first two papers from computer science about the problem are from 1964.
• 18:32
  But at least in theoretical computer science, which is my area.
• 18:38
  The problem gained prominence in the 1970s.
• 18:42
  Well, in the 1970s, this MP completeness I was talking about came up and there was an extremely influential paper by Karp,
• 18:51
  and he showed that many problems that people in combinatorial optimisation,
• 18:56
  mostly that people had been studied for a long time,
• 19:00
  all turned out to be NP complete OC and p completeness had just been introduced, but more as an abstract thing.
• 19:09
  And then Karp came and said, Oh, look, all these natural problems fall in there.
• 19:15
  Okay, great paper, extremely influential paper.
• 19:18
  And then he had an open problem. And that was what's with graph, I assume office.
• 19:22
  He didn't know. Okay. In 1979, Gary Johnson wrote a book about MP completeness and they still didn't know.
• 19:31
  And today we still don't know. It's one of the very few remaining open problems from that book.
• 19:38
  And well, then people got frustrated from this about this.
• 19:43
  So here you see a title of a paper that was also influential called the Graph ICM of ISM Disease, which is kind of funny because I mean,
• 19:53
  the problem had been explicitly stated five years earlier and even then people were tired of it.
• 20:01
  Now, I told you about Bob, I said algorithm from 2016, which is more than five years ago,
• 20:06
  and I am presenting it as as pretty much a new result, telling you that there's still a lot going on in the area.
• 20:14
  So, you know, if you work on a problem for long enough, I guess the time scales shift a little bit.
• 20:21
  Okay, so we have that and not so much was happening in the 1970s,
• 20:26
  but then starting in the 1980s, there was big progress and that's where group theory came in.
• 20:34
  Okay. So people had this idea, okay, we have this group structure, we must use it.
• 20:38
  And Bob was the first to have the idea. He suggested the general approach.
• 20:44
  And then the really important paper out of that period was Lux's paper,
• 20:50
  who showed that if the if the graphs have bounded degree, then you can solve it in polynomial time.
• 20:56
  Now this result in its its own is probably it's a nice result but not so important.
• 21:02
  But what makes this paper extremely important is that he introduced basically a strategy how to solve it,
• 21:10
  a method, how to to exploit this group structure.
• 21:13
  And that, for example, has been used also by Bobby for his quasi polynomial time algorithm, much research that follows Lux's paper.
• 21:22
  So that's that's an extremely important paper.
• 21:26
  And now we make a big step. Not that nothing happens in between, but we come to Bob's results.
• 21:33
  He showed that it's in quasi polynomial time. You see that the means of communication has changed over years from typewriter to YouTube.
• 21:44
  That was a presentation by Bobby on this results.
• 21:47
  He gave a couple of seminars at the University of Chicago when he announced this in fall 2015.
• 21:56
  And actually we had a doctoral meeting in December 2015.
• 22:00
  And basically the afternoons, all all afternoons he talked about this is an 80 page paper and he he tried to explain it.
• 22:08
  I remember that very well.
• 22:13
  Okay. So there we are. Let's a little bit talk about.
• 22:22
  Practical stuff. I will move towards more practical stuff towards the end of the talk now.
• 22:29
  My interesting graph I saw Wolf ism, I should say, is mainly the theoretical one.
• 22:35
  It's a problem where we don't know the complexity we should.
• 22:39
  Okay. And also it's a lot of nice mathematics involved.
• 22:46
  But, but I'm also coming to the more practical things. Now, one thing to note around the same time that that Lots wrote this influential paper,
• 22:55
  Brendan McKay came up with a tool solving graph saw in office, and that's already in 1981 worked very well.
• 23:03
  It's called Naughty and it's still one of the best.
• 23:07
  I mean, he continued developing. It's it's still of the one of the best tools and you know, and in most practical situations,
• 23:16
  you can just solve some of this which distinguishes it from other and part problems.
• 23:22
  You can solve them sometimes, but usually it's also easy to come up with hard instances for this.
• 23:28
  It's very difficult to find examples where the tools don't work well.
• 23:33
  Okay, so the state of the art is probably a combination of naughty with a with another tool by uh, and also people know call traces.
• 23:47
  Okay. So we can solve it well in practice.
• 23:52
  Now you may ask why on earth would we want to solve it in the first place?
• 23:56
  So let me let me tell you a little bit about applications of this.
• 24:00
  And we have two different types of applications, which is interesting because they are really,
• 24:07
  really very different, but both builds on the same thing.
• 24:12
  And the first are called graph matching applications. You have different graphs, you want to match them, you want to know are they the same?
• 24:19
  OC The chemical information system thing I mentioned, what is of that type?
• 24:24
  You have two representations of a molecule you want to find.
• 24:28
  If it isn't the same, the same thing happens in computer vision.
• 24:32
  There's been a lot of practical work on this.
• 24:37
  They call it graph matching, actually in computer vision.
• 24:43
  Which is completely unrelated to the working theory, by the way.
• 24:50
  So, so anyway.
• 24:52
  So, so for example, what they do saying face recognition, they represent faces as graphs where they, they have a node for the nose and the eyes.
• 25:01
  So what do I know? And then they want to match the graphs.
• 25:04
  And then there's many applications like that in, uh, in computer vision.
• 25:08
  So they, they want to do this or static program analysis is another example.
• 25:13
  Malware detection. You may have flow graphs of code and you want to match them.
• 25:19
  So that's one typical type of application. And the second, as I said, is quite different that we want to use.
• 25:26
  Um. Symmetries to to simplify hard combinatorial problems.
• 25:35
  So we can try to use the symmetries of an input instance to a heart problem, say,
• 25:42
  to just simplify the instances, maybe collapsing equivalence classes of vertices.
• 25:49
  Or we can just prune such trees if we have backtracking algorithms.
• 25:53
  And again, this has many applications, for example, in set solving in integer linear programming and so on.
• 26:02
  Okay. So these are the types of applications and.
• 26:11
  One thing I noted when I I looked at this quite a while ago that actually in most of these applications,
• 26:19
  you don't require exact ISO malfeasance, exact matching.
• 26:24
  It's usually good enough in, say, in these computer vision things if if you have an approximate matching, okay, sometimes you want it to be exact.
• 26:34
  Probably the chemical information systems require exact matching the static program analysis or the computer vision.
• 26:43
  Probably not. Okay. And when then you you start to think, what is it, approximate I am office.
• 26:50
  And that leads to the second part of my talk on graph similarity.
• 26:54
  And actually that led me to think about what graph similarity could probably mean and so on.
• 27:00
  So I'll come to that.
• 27:01
  But now I want to continue with ISO Mathieson and then tell you a little bit about some algorithms and some recent work we've been doing there.
• 27:13
  But let's start with a, uh, simple old algorithm also from the 1960s which.
• 27:24
  Has somehow become quite important in recent years.
• 27:28
  That's the Vice Falla Lima algorithm, which is also known as colour refinements or not vertex classification.
• 27:36
  And what it does is it computes a colouring of the vertices of the graph in a very simple way, iteratively.
• 27:44
  Initially, all vertices get the same colour and then we repeatedly refine the colour colouring.
• 27:51
  And the way we do this is we look at two vertices that still have the same colour and we give them different
• 27:57
  colours if there's some other colour such that these two have a different number of neighbours of that colour.
• 28:04
  Okay, and we repeat this. So we basically get a partition of the vertices into colour classes and we repeat it as long as
• 28:13
  the partition gets finer and at some point that stops and then we return this stable partition.
• 28:20
  So I can just show you a little demo of that whole Gödel wrote this.
• 28:26
  So here we have some graph, random graph with parameters that turn out to be convenient in this context.
• 28:33
  Well, here it's actually a tree. Let's do a new one.
• 28:36
  Tree is too boring. Is this a tree again? No, we have a triangle at least.
• 28:40
  Okay. Anyway, let's look at this. Initially, all vertices have the same colour blue.
• 28:46
  Okay, so then we start the refinement. And what should happen now?
• 28:51
  For example, this one here has two blue neighbours, so it should get a different colour then.
• 28:58
  That's one which only has one blue neighbour or that one that has three blue neighbours.
• 29:04
  So let's see what happens now. Yeah.
• 29:08
  So here this one is red, this is some, some ugly greenish colour and that's another green.
• 29:16
  Okay. And now let's see, this one here has a purple neighbour and one of these greenish neighbours,
• 29:26
  whereas this one has one of those as well and a green one, so they should get different colours.
• 29:33
  Now we do another step and now if we had these three, they have all different colours.
• 29:40
  Now of course as the number of colours grows, they get harder to distinguish.
• 29:46
  So let me just click through this. We get more and more colours and at some point we're done.
• 29:52
  Nothing new happens. Okay, now we could try the same thing again, but basically the the partition of notes into colour classes stays the same.
• 30:02
  And that's, that's the stable colouring.
• 30:05
  Okay, that's the algorithm. Very simple. Before I tell you what we actually do with it,
• 30:13
  let me just mention that this can be implemented to run very efficiently in almost linear time, also no large quantities.
• 30:23
  So this works really, really well. So we have this well, almost linear time.
• 30:29
  We have a lock factor there. So a while back we were wondering if we can get rid of the lock factor and we could show that probably we can't,
• 30:39
  at least if we stick to somewhat reasonable algorithm. Now if you if you start to do arithmetic on the bits of some real numbers,
• 30:47
  I have no guarantees, but uh, so the lower bound applies to a fairly wide class of algorithms.
• 30:55
  Okay, so we have this very efficient thing, but what we want to do with it, how does it relate to what we're interested in?
• 31:04
  Well, basically it detects non symmetry. If two vertices get different colours, then there's no or then they are different, structurally different.
• 31:14
  So there's no automotive is mapping one to the other. Okay.
• 31:19
  And our goal would be to detect all structural differences between the vertices.
• 31:27
  Now, unfortunately, uh, this does not always happen.
• 31:32
  It actually does happen on, on random graphs. Okay, so on almost all graphs it happens, but then almost all graphs are not particularly interesting.
• 31:44
  So, uh, this tends to not cover, uh, the interesting graphs in particular.
• 31:52
  Well, it depends on what you are doing. Lastly, you may disagree on that, but anyway, now it fails on, on simple graphs such as this one,
• 32:03
  because if you look colour, refinement or vice element does nothing there.
• 32:08
  Every now the versus is all black every is has two black neighbours.
• 32:12
  So there's nothing to even start that's already a stable colouring.
• 32:17
  But then of course the vertices in the triangle are structurally different from those in the.
• 32:24
  The four cycles. So there it miserably fails.
• 32:28
  And that also happens now. Since it's so efficient, we still want to use it in practice and somehow turn it into a reasonable algorithm.
• 32:36
  That's what the practical tools do. Um, actually.
• 32:41
  Okay, one more thing I wanted to mention is that as in Ice and Wolf as in test,
• 32:48
  we would say the algorithm distinguishes two graphs if the colour histograms are different.
• 32:54
  OC If one graph has more red vertices than the other, they cannot be ISO Morpheus iso morphic.
• 33:03
  Now if four colours they have the same number of vertices, we don't know.
• 33:08
  So this is what we could regard as an incomplete ISO more for some test.
• 33:13
  Okay. Now I wanted to go to the practical stuff.
• 33:18
  Okay. So we have this algorithm and it's it's very efficient but incomplete.
• 33:23
  So what do we do?
• 33:25
  We basically integrate this in some kind of backtracking algorithms, and that's what all the tools that are successful in practice do.
• 33:36
  So let's just briefly explain how this works.
• 33:40
  So we have a graph here. We do colour refinements on the top one on this one.
• 33:45
  Okay, we have two colour classes, red and blue. Now that doesn't help us much.
• 33:51
  Now if every voters had a different colour that would help us because then we could take another graph and if it had a different
• 34:01
  colour pattern it would be nice and morphic and if it had the same colour pattern and all vertices have different colours,
• 34:07
  we know exactly what the only possible isam of ism can be and we can just check it.
• 34:13
  So our goal will be to somehow in a canonical way, find a colouring where all vertices have a different colour.
• 34:21
  That's what we're trying to do. Now here we have three red vertices that's bad.
• 34:27
  So what we say is, let's take one of the red vertices and individualise it.
• 34:33
  And that means just give it a random new colour purple here.
• 34:38
  Okay. So now of course, all three red vertices look the same for us.
• 34:43
  So we basically have two blondes. We build a search tree in the second branch.
• 34:49
  That vertex will be the new one and in the third branch it will be that one.
• 34:53
  Okay, so we are here and we run colour refinement again.
• 34:59
  Now since this vertex is purple, this one knows it's different than the other two.
• 35:04
  So it also gets a new colour light blue. Okay, that still doesn't help.
• 35:09
  We still have to read purchases and to dark blue and we do the same thing again.
• 35:15
  We say this now becomes pink,
• 35:18
  then the neighbour also gets a new colour and now suddenly we're in a situation where all vertices have the same colour and we expand the full tree.
• 35:27
  And then basically with this object we can compare two graphs.
• 35:32
  Now that alone wouldn't be very efficient, but then what we can do is we can,
• 35:38
  we can prune this tree and in clever ways I don't want to get into so that usually the tree is fairly small and then this works quite efficiently.
• 35:49
  So basically at every node of this tree we run this 1wl algorithm.
• 35:55
  But that's okay because it's so efficient. Good.
• 36:00
  So now let's move into the, uh, into the theory, uh, very firmly into theory.
• 36:09
  First of all, the algorithm has a higher dimensional version, which you could have guessed because I call the previous one one dimensional.
• 36:17
  So in the k dimensional version instead of vertices we call our k tuples of as well.
• 36:23
  We can also do this. Then the running time will be something like into the k, which is still polynomial.
• 36:31
  Okay, now as you do this for k equals three, then all algorithms people usually come up with are subsumed by this.
• 36:41
  This is stronger by every single algorithm that people suggest to me after my talks on graph I more fears and testing and so on.
• 36:48
  It's so so we, we always have this.
• 36:52
  So that's a very powerful algorithm. Actually, a while ago I showed that if you have a glass graph class that excludes some fixed graph as a minor,
• 37:01
  such as playing on graphs or graphs of bounded tree with so classes like this.
• 37:08
  Then actually there is a K such that this is a complete isomer of this test.
• 37:13
  On the other hand, it was known for a long time that on general graphs it's not okay.
• 37:21
  So that's combinatorial algorithm. And that's basically where we stand with combinatorial algorithms.
• 37:27
  Quite powerful, but not good enough. So let's finally move to the groups so we know the solution space to our problem.
• 37:37
  The automotive ISM group has a nice structure. Okay, we want to exploit this, but how do we do this?
• 37:45
  And that's the challenge, of course. And look, suggested a divide and conquer approach, okay.
• 37:53
  For solving this automotive ISM version. So you wants to compute the automotive ISM group, but it's equivalence to two isomers.
• 38:01
  All right. So the goal is to compute the Automotive ISM Group.
• 38:06
  And what we do is we take some some supergroup that contains all automotive isms that may be the group of all permutations of the vertex set,
• 38:17
  or it may be something that we obtain in a different way somehow easily.
• 38:22
  And then we we basically computed decreasing sequences of groups that get closer and closer to the axolotl more for some groups.
• 38:35
  And what we do is we kind of exploit the structures of the groups we see.
• 38:40
  And well, we in groups we can split them up along orbits or blocks if you know what these are.
• 38:48
  Otherwise, just believe me that when you use that, there are natural,
• 38:52
  natural ways to split up permutation groups and somehow reduce the problem size, move to smaller groups.
• 38:59
  But then at some point we get stuck and that's when we hit primitive permutation groups.
• 39:05
  They are the bottleneck. And then in Lux's setting, in the old paper, basically at that point he just said, okay.
• 39:13
  And now if the input graph has this simple structure bounded degree, I don't have to worry about them and I can just use brute force.
• 39:23
  And then Baba was much more refined in his algorithm and and used some heavy machinery to deal with the primitive groups.
• 39:31
  In the end, we know a lot about the classification of finite, simple groups.
• 39:36
  A monumental piece of work in mathematics tells us a lot about how these groups can look.
• 39:42
  And basically now we can look at the tables of groups that appear and see what we can do with them.
• 39:48
  And in a sense, that's what we're doing.
• 39:53
  All right. So let's look at the main results that's that builds on this group theoretic approach.
• 40:02
  And end is always the number of vertices of the input graph.
• 40:06
  And D is usually the maximum degree, the maximum number of neighbours a vertex may have.
• 40:13
  Okay, so luck's proof that I am more feasible for graphs of maximum degree d can be decided in time roughly into the D.
• 40:22
  Okay. A few years later this has been improved.
• 40:26
  Or actually just one year later to ensue the d overclock d oc.
• 40:34
  Bommai many years later proved that you can do quasi polynomial time and actually.
• 40:43
  In like the worst case runtime. There hasn't been much progress between these two papers.
• 40:48
  There have been many interesting papers on graphite. So Wolff is in the time between.
• 40:53
  But, uh, now in, in some sense, these, these papers really are immediate successors, if you will.
• 41:06
  Okay. So that's where we stand now. If you look at this, uh, let's say the maximum degree is log m.
• 41:15
  Okay, then what do we have? Logs tells us we need time into the log.
• 41:22
  M and Baba. He doesn't care about this and still tells us into the poly log.
• 41:29
  M And that's somehow bothered us.
• 41:33
  So we looked at this and kind of combined the two results and we proved the following.
• 41:39
  If you have graphs of maximum degree D, you can go to time into the poly log of the OC.
• 41:46
  So that's kind of, uh, the, the, the minimum of the two.
• 41:52
  And for example, photographs of logarithmic degree that improves both running times, uh, quite a bit.
• 42:00
  Okay. And I think I.
• 42:05
  Skip the proof of this or let me just tell you a little bit about the strategy.
• 42:10
  I wasn't going to tell you the whole truth anyway, but we basically proceed in three steps.
• 42:16
  The first is we just analyse the groups that are using the classification of finite, simple groups.
• 42:22
  We understand the structure of these groups that we need for this divide and conquer stuff.
• 42:28
  Then it turns out we can just apply the divide and conquer stuff.
• 42:31
  We need one intermediate step, and that may be the key innovation in our work.
• 42:37
  We somehow encoded parts of these automotive ism groups into the graphs, so we augment the graphs by certain tree structures that help us.
• 42:48
  Then in the third step to apply basically Bobby's techniques, unfortunately, we couldn't just use bubbles a result as a black box,
• 42:57
  but we had to looking into this stuff and then actually compute the group in the time we want.
• 43:04
  And now with this with this machinery, we could do a bit more.
• 43:09
  For example, if you have graph classes excluding a fixed graph as a miner and this graph has K vertices,
• 43:18
  then we also have an algorithm running in time ends with a poly log of K.
• 43:24
  All right, so if I've lost you here, good news.
• 43:29
  We started a completely new part of. Of my talk, and we have a nice picture here.
• 43:36
  Again, that one even older, uh, 5000 years.
• 43:41
  Uh, it's a very nice relief. And, and you see the symmetries again.
• 43:47
  Okay, so there's basically a symmetry axis in the middle.
• 43:50
  Okay. Now, one thing you note, of course, it's it's not an exact symmetry.
• 43:56
  Okay? So so if you look here, that's that's different than what you see.
• 44:00
  There's actually something something very funny about this.
• 44:04
  So basically, if you if you disregard these small in precisions, you have the symmetry along this axis,
• 44:13
  you will think if you look at the heads of the deer, but then if you look at the feet, it's the other way round.
• 44:19
  You would have to flip it over like that to match the feet, but then the hats would be wrong.
• 44:25
  Well, that's kind of puzzling.
• 44:29
  I wonder why they did it this way if they hadn't noticed or thought it was funny or didn't care.
• 44:35
  It's it's interesting. But anyway, my my point was, even though this is not a precise symmetry, it's good enough to convey the main, main point.
• 44:48
  The picture still looks fairly symmetric.
• 44:52
  Okay. So approximate symmetry is can also be good enough.
• 44:57
  And in many, many situations they are. Okay.
• 45:00
  Now let's look to to modern times and look at these three graphs again, showing chemical molecules.
• 45:11
  Now, which of these are almost similar? Well, you can think about it.
• 45:15
  They are all pretty similar in a way. So what's cell we say?
• 45:22
  Okay, let me be a bit more precise when it comes to designing synthetic fuels.
• 45:28
  Now, that's from a collaboration with chemical engineers at my university.
• 45:33
  So we looked at things like this and we want to understand which molecules may be good, good fuels in the end.
• 45:41
  Okay. It turns out that with respect to the properties we care about here, the two blue ones, some awesome similar.
• 45:51
  Okay, now that's something I don't understand why that is.
• 45:55
  I can't even pronounce the names of these, so how should I?
• 46:00
  But we worked on this. So, so basically what we did, we built a machine learning model that kind of tries to predict the properties of these.
• 46:09
  And the way this goes is we usually map the graphs into some vector space and there we can then
• 46:16
  use standard techniques from machine learning to distinguish between them and the mapping.
• 46:23
  If this is correct that the two blue ones are more similar should maybe be such that the two blue points are closer together.
• 46:31
  Okay. And this then also gives us a method for for quantifying similarity.
• 46:38
  We can just map two vector spaces in a way that that closeness in this space somehow corresponds to similarity.
• 46:49
  Okay. Um, let's leave it there and just think about what, how else we might approach graph similarity,
• 47:00
  because I'm sure that's not the first thing you would have thought of.
• 47:03
  And if you ask theoretical computer scientists, the first answer you get is or almost always what?
• 47:12
  Well, how to quantify similarity or distance between two graphs is you would want to count the number of edge mismatches.
• 47:20
  So you try to align the two graphs and then you have to delete a few edges
• 47:26
  and edges to the other and then you should get the same or ISO morphic ones.
• 47:31
  Okay. That's what you might call edit distance similar to edit distance of words.
• 47:38
  Okay. Now that's something that seems very natural for us, I think in theoretical computer science and algorithms and so on.
• 47:49
  On the other hand, if you think about it, let's say they are fairly close, you only have to flip 5% of the edges.
• 47:56
  Now if you flip 5% of the edges on a graph, it can look very, very different.
• 48:03
  So it's not clear at all that this is in any way a meaningful measure.
• 48:09
  Okay, um, let's look at.
• 48:13
  I was hoping to have more. But now I'm apparently stuck.
• 48:18
  That's annoying. Okay. Let me just try to.
• 48:25
  With the program. Okay.
• 48:31
  Oh, now we have to run through the whole thing.
• 48:34
  And I just hope that I wasn't just stuck at that slight.
• 48:41
  Okay. Okay. It's just for the vote.
• 48:47
  What was the best slide in the end? So take notes now.
• 48:52
  Uh. Okay. Huh?
• 48:58
  Worked. Okay, now, something people do in machine learning is what they call graph kernels.
• 49:03
  Basically, for all purpose. They extract features from a graph, maybe even infinitely many, and the features are coded as real numbers.
• 49:13
  So, for example, number of triangles in the graph, number of edges, whatever people come up with.
• 49:20
  And then you compare these, these vectors of the numbers.
• 49:23
  Okay, that gives you some similarity measure. And if the features are meaningful, it's they that should tell you something.
• 49:31
  Then there's another step now.
• 49:35
  As I described it, people select the features. Now, we could let machine learning select the features.
• 49:42
  Okay, so then we get learned embeddings of the graph.
• 49:46
  So the features would associate vectors with the graph.
• 49:49
  So we embed them in some vector space and we can kind of from examples we can tell them these two are similar, these are not similar, and so on.
• 50:00
  We can try to come up with a good, uh, a good measure.
• 50:05
  Okay. So techniques for this are graph neural networks, graph contrastive learning.
• 50:10
  So that's stuff we are working on, uh, these days in practice and many other people are as well.
• 50:18
  Um, them okay. I, I grew up as a logician.
• 50:23
  Uh, I, I did my Ph.D. in mathematical logic.
• 50:27
  So for me, in a fairly immediate thing to think about is logical equivalence.
• 50:33
  Uh, take equivalence is in increasingly stronger logics.
• 50:38
  That should give you a feeling of how close to graphs are okay by similarities equivalent to this and many people here will know what that is.
• 50:48
  If you don't. Never mind. It won't play a role in this talk.
• 50:53
  Okay, then we have this algorithm vice file alignment algorithm which was not a complete us so move isn't this.
• 51:00
  But maybe we could say if if it does not distinguish two graphs then at least they are similar.
• 51:06
  That's a and then we have this hierarchy of algorithm that gives us some kind of distance.
• 51:11
  That's something we could do, of course.
• 51:14
  Then if we're most more mathematically minded, we can say, okay, now we have these adjacency matrices of the graph.
• 51:21
  We can apply some matrix knobs to them that should give us the distance that's actually related to this edit distance thing.
• 51:29
  Oh, if you're more sophisticated, we can think of optimal transport distances.
• 51:35
  Okay, so we have all these approaches. Now, what do we do with this I.
• 51:44
  I think this similarity problem is really, really important for many practical means,
• 51:49
  mainly for machine learning, because machine learning has always been built on.
• 51:56
  Similarity in some way. So we should understand it, but there's almost no theory.
• 52:03
  So I try to think about it.
• 52:05
  And basically I came up with basically two different ways of thinking about similarity, and I just want to share them with you.
• 52:14
  And the first I call operational similarity. And under this view, two graphs are similar.
• 52:20
  If you can transform one easily into the other.
• 52:24
  Okay, that's a natural way. Thinking about is, for example,
• 52:27
  edit distances of this type you want to if you delete as few edges as possible and add as few edges to get from one to the other.
• 52:36
  And if you have few, a few operations, then they are close.
• 52:42
  So the optimal transport distances I mentioned also of this type.
• 52:47
  Now an additional thing that you get out of this is usually you even get an alignment of the graphs that somehow realises this,
• 52:56
  which may be useful sometimes. Then the other side I call declarative similarity.
• 53:01
  Under this view, two graphs are similarly if they have similar properties.
• 53:07
  So the graph kernels where you collect certain features that the properties are of this type logical equivalence is of this type.
• 53:16
  The two graphs satisfy the same properties, express all in this logic.
• 53:21
  Now the advantage of this way of thinking about it, you can actually adapt it to a specific target.
• 53:27
  You know which properties are relevant in your practical application.
• 53:31
  So you choose these and look at these. Okay, now what do we do with this?
• 53:36
  So we can kind of separate the examples I gave you into these two categories?
• 53:43
  Now, the question is, are these related?
• 53:46
  Right? I actually think thinking in some way, they are just two sides of the same coin.
• 53:52
  They are dual to one another. And I just take this as a hypothesis and try to, uh, to, to turn it into theorems.
• 54:04
  And the remaining few minutes, I just want to show you a few results pointing in this direction that actually there is a relation.
• 54:15
  So again, now the next three slides or something will be a bit more technical.
• 54:22
  But then, then you're done and hopefully we all get a doughnut.
• 54:28
  Okay. So any distance I mentioned this, we can write it this way.
• 54:35
  So what do we do here? We have two graphs, adjacency matrices, A and B, and now what we can take.
• 54:42
  The adjacency matrix has a one if there's an edge, zero if there's no edge.
• 54:47
  But in the two matrices, the vertices may be ordered in different ways.
• 54:52
  So we apply a permutation to the first, then compare it to the second.
• 54:58
  So take the difference and then take the norm. Basically, count the number of ones or minus ones that remain.
• 55:05
  That's what edit distance is and we have to minimise overall these alignments.
• 55:10
  Okay, well we can write this in a pure matrix form.
• 55:16
  We minimise over permutation matrices and then take this expression.
• 55:21
  Just trust me that this is this is right.
• 55:24
  Okay. Now if you write it this way, one thing you see is you have to minimise overall permutations.
• 55:31
  This is incredibly hard in theory and in practice it's a really bad space to minimise over.
• 55:38
  So for example, one way to, to, to, to support this is that even if the two graphs are just trees,
• 55:48
  I mean, usually everything is easy on trees, but here is even an MP hard to compute this.
• 55:54
  Okay, so that's even if it was a good measure of similarity, it would be kind of useless because you can't compute it.
• 56:04
  Well, then you could say we can.
• 56:06
  We can relax it a little bit and we can take a convex problem that approximates it, and then we can solve efficiently.
• 56:13
  And the way we can do this is instead of minimising over permutation matrices, we minimise over doubly stochastic matrices.
• 56:23
  Again, the important thing is here. That's the convex relaxation of this problem and such problems we can solve.
• 56:32
  Okay, so that gives us a new distance measure.
• 56:36
  It's not clear what it actually means and what it tells us about the graphs, but we can try, right?
• 56:41
  At least we can compute it now. Okay.
• 56:45
  So that's one thing we can do. So that's on this operational side, right?
• 56:50
  We started from edit distance. Now let's start from the other side and what could be good features.
• 56:57
  Well, in general, what turns out to be good and also related to many other features that people use is we count home office.
• 57:08
  So what's a human wolf is and it's a mapping that preserves adjacency.
• 57:13
  Okay. So here we have two graphs that would be a home office.
• 57:17
  We mapped the middle vertex here, these two here.
• 57:21
  So they are both neighbours and here's an edge and that one here, there's also an edge.
• 57:26
  So that's a home office and now we want to count them.
• 57:30
  Okay. So for example, number of triangles would be the number of Homomorphic isms from a triangle to our graph divided by six.
• 57:40
  But who cares about dividing by six? Okay, so we can do that.
• 57:44
  And now this gives us a vector embedding. Say we have a class of graphs, the class of all cycles.
• 57:50
  Okay? And then we can collect all these homomorphic numbers in one vector.
• 57:57
  Could be finite dimensional could be infinite dimensional.
• 58:00
  Okay, that gives us an embedding. Okay.
• 58:04
  Here's an example for these two graphs. Okay.
• 58:08
  And once we have the embedding, then the distance in the vector space induces a distance on the graphs.
• 58:13
  I'm close to the end. Okay. So we can do that.
• 58:18
  That also gives us the distance would be routed on the declarative sides.
• 58:24
  And now here's a theorem. That says these things and many other things are the same in some sense.
• 58:33
  The precise statement is so for any to graphs, their distance in the star sense is zero.
• 58:40
  If and only if all the Home Office numbers are all the same.
• 58:43
  Okay. Now that happens. Interestingly.
• 58:47
  If and only if the one dimensional vice file element algorithm does not distinguish the two.
• 58:53
  So there we actually have a very efficient.
• 58:57
  We can also write this as a logical equivalence in a strange logic that has been studied a lot in descriptive complexity theory.
• 59:07
  And maybe the most interesting addition here is also this happens if and only if the two
• 59:14
  graphs cannot be distinguished by a graph neural networks or by a learned embedding.
• 59:19
  So that's quite nice how things fall together here. And I want to stop with that and just to one slide on very general research directions.
• 59:32
  So Rafael Wolff is there's still a lot happening.
• 59:36
  I mean, the problems are really hard and it's hard to make progress, but I think it's very interesting and worthwhile.
• 59:42
  So I still work on this, although not exclusively. So for example,
• 59:49
  one problem that is interesting and we're not much is known as the group I saw
• 59:53
  monotheism problem where you want instead of graphs you look at groups um similarity.
• 1:00:02
  Is. Kind of the opposite. It's practically extremely important.
• 1:00:07
  In theory, we know very little and there's a lot to do and probably a lot of easy progress to be to be made.
• 1:00:14
  Okay. And you're just two references of survey papers I wrote fairly recently.
• 1:00:21
  You can look it at these if you're interested, and that's pretty much it.