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