Scientist Stories: Vassilis Kalantzis, Quantum Graph Transformers

Um, yeah, thanks. Actually, the title of the talk is slightly behind, but no, uh, I, I just guess the things, um So, okay, let's see. Directed graph, autoencoders, and quantum graph transformers. I muted myself and I unmuted this laptop here. Is that okay? I just want to make sure that people online— Yeah, yeah, they hear. No problem. Yeah, so, okay. I know that the time is really limited, so I'll try to go as fast as possible. Actually, the talk is two parts.— it's a different quantum. The first one is direct graph autoencoder. The second one is some exploration of graph transformers on quantum computers. So I'll keep both parts short given the time constraint. So, okay, so for the first part, right, the idea is that you are given a graph and you want to do link prediction, right? You have a directed graph and you want to predict links. For both parts of the talk, really, the ideas are pretty simple. For the link prediction part, you just say the following, right? I will leverage the duality that is incorporated in directed graphs. And for example, the hits idea for ranking web pages to encode and to create some embeddings. And then I would just decode by forming an approximation of the adjacency matrix by using the embeddings that I just computed during the encoding part. And I'll just apply the sigmoid function, and that will be the idea. So link prediction, right? So what you want to predict is you're given a directed graph, and you want to say, is U connected with V? And if so, with what direction? Does U point to V or V point to U? And directed graphs arise in many applications. As an example, I'll give you citations and citation graphs. Obviously, a paper that was written in 2020 cannot cite a paper that was written in 2024. And many interesting applications that come to life. I mean, of course, the undirected graph part is way more recent. But this is starting to change. So yeah, about the algorithm that we're going to describe, and I'm going to describe really quickly, it's basically saying that its node points to other nodes and it's pointed to from other nodes. So you basically try to break the embedding vectors into the so-called source vectors and target vectors, right? So when I point to you, I am your source and you're my target, right? So there are different embeddings for source and targets. And the idea comes from hits where you run webpages and you have hubs and authorities, right? Hubs show to webpages and then authorities are being pointed to by hubs, right? So the name of the, of the album is Direct Graph Encoders, you know, with a D-I. And okay, without further ado, so the hits album, right? This is an album that I think was started in the '90s or around the zeros. It basically predates Patreon. Hits is query-based, it's a model-based album, right? So what you do is You input a query, you get some, the seed set, you get some related web pages, and then you incorporate some more and you build a smaller graph, right? A much smaller graph than the original one. And then basically try to say the following, which web pages are the hubs and which are the authorities? A good hub represents a page that's pointing to many other pages, while a good authority represents a page that is linked by many different hubs. Kind of, again, Pager does something slightly different, right? So an authority value is computed as the sum of the scaled hub values that point to that page. So in other words, if 3 of you point to me, then you are the hubs, I am the authority, and I get the contributions from you, but I scale because 3 different web pages. So for me, likewise, the hub value is the sum of the scaled authority values of the pages it points. So again, there is a direction. If I point to you, I am your hub, you are the authority, and then there are source and target scalars or vectors, if you like. So in the language of linear algebra, you can recover the source by doing the forward path, right? And you take the adjustment and modify it with the authority scores, and that's how the hubs are determined. And then you do the same with the transfer. So basically, outgoing links imply multiplication with A. Incoming links imply multiplication with the A transpose. So now, high-level idea of what we're going to see. We're not interested in ranking. We are interested in link prediction. However, for the first time in 2022, the paper that appeared at AAAI, the idea was to leverage ideas for kids for graph convolutional networks, right, for directed graphs. And we don't have having authority vectors, right, that we call source and target vectors in the link prediction problem. So if we were to enrich, let's say, a hits-like idea for graph neural networks, what would we do, right? I mean, we would replace the hard authority vectors with learnable weights, right? So this ST is s and t, or even one of them is just some initial bunch of feature vectors, right? The initial embedding. And then ts and w are learnable matrices that are going to be learned by the VNL network itself, right? So if you were to incorporate that in the previous slide, a hitslide approach will give your source of a times the target embedding times the learnable matrix w, t. And then likewise, the back. Now you can as well add non-linearities and self-links to finalize the encoder part. So from here you can go to an idea like a graph convolutional network, right? And you add self-links, that's the prevalent idea in graph convolutional networks. And if you know the non-linearities, I mean, by the random, for example, by that telegraph again, you have exactly that. And here you see some matrices alpha and beta. The idea from that comes from some recommender system work that we did at IBM, where you basically have the cosine similarity, but then, I mean, you have the dot product similarity, right? But then the dot product is between two vectors, a and b. You have to take the norms and then you have to take the other side. So by having, by scaling the norms by alpha and beta, you give different attenuation factors to the angle versus the magnitude and vice versa, right? So this part was not there, so we added learnable scales alpha and beta to balance the contribution of the in-degree and out-degree to the, to the output. And then to perform the link prediction, you can just apply a sigmoid to a neural function. So just for demonstration purpose, imagine you are an AI and you're being monitored by J. Then if you want to gather the information in a message passing manner from all Js that talk to you, you You just multiply with the agent. Now, what happens though when you're pointing to, by many different ways, or one J in particular shows to other points, to other nodes, and not only you, then you have to scale, right? So basically, you take one of the three parts of the data to give. So basically, this means that you divide by the out-degree of this node. This is the page rank idea. And then if you have a main page that you got, say here, say here, around you, you also have to scale with the incoming links to you, right? So you're being targeted to by different nodes. Now those nodes have an outgoing degree, but you also have an incoming degree. By those that form. So basically you start from here and then you go here and then you add one more scaling because you're scaling the incoming information. And so you end up with something like this that is almost a graph convolutional network if you add self-mates and if you scale. Now you do the same exactly for the outputs. So there's some— this is what I'm going to do. So when now, when you show someone and you don't consider what is in the input, you need to look only the output. When I now voice to say, why you multiply with A, because that's matrix A, so the output is, uh, right. And combining this, you got the hits, right?— So this is for the input. If you keep doing this, then the same information will go to the dominant aim, but obviously this will then transfer the parole to some other words. And okay, now combining all these again, the message passing from incoming names, outgoing names, and then the hidden layer you start forming big AI directly. So like I said, the idea now is that you have source and target vectors. So if you're being targeted from AI, for example, right, you have to update your target vector because you are the target from all the sources, from all the AI. So you gather Uh, let me actually go to the slide. So if you're here, it's the same thing, right? Your TI, right, uh, must be dependent on the S state. So you have two other basic states. You don't have one because now you're on the record, so I have another one here. So, uh, basically you update your target. The target method belongs to you, but the source is— but the source method of the node that's calling And so you do this, and then if you write it in a matrix notation, you end up with something like this, which is the encoding part, right? And then you decode by the identity, but getting the rank 1, actually the rank k updates. Actually, this is a better slide. So this is the direct graphical encoding. By leveraging ideas from graph convolutional neural networks, this is just a simple representation. You take your attention matrix, you add a self-reading layer by the identity matrix there, and you do the same thing with the output. So that's why, uh, B+ and B- makes the output read. B+ holds the output read on the diagonal, and B- holds the input read on the diagonal. So you do other things and then you scale by alpha and beta. And then you end up with an A hat matrix, right? It's again the sphere-based, the spherical density matrix. And the first layer, not even a nonlinearity at all, right? You just do straight matrix even before the neural networks. So you don't need— so you just modify the adjacency matrix, you have the PWD and SW, so WDWs are the local matrices. You have a loss function again, not generic, there is a way to differentiate it, and then you have a signal of some other 1-layer function choice, and then you form this matrix of the embeddings that you took to 1 layer of bigGAN, and this gives you probabilities about connections. It's asymmetric because this is not a symmetric mesh. Again, for the direct case, for the other case, you will have the same matrix here. And you can generalize this to multiple layers by just adding more denoising layers. Here, for example, there are 2 layers. Example, visual cousin in the United States, where you basically do what you did here. You apply and you have the, the kind of meetings again, and then you have another phase where you have 4 meetings in the, in the college. So right now, direct job, the direct job, basically with Liberty. At the time I played with Liberty for the first time, this idea of —source and target vectors for a graph convolution layer, a graph convolution in your view, respectively. And before I go to the experiments, well, there is not much theory to, to, to accompany this idea, right? However, there are parallels with the baseline Neiman test for graph action movement. So basically The reason why this is actually— so why one A is B and M and one W is L is because you have a cutoff. So when you apply the Wi-Fi limit method, you will return— you have something in your neighbors. So this is where it comes. So I am here, you point to me, so I take my label and the labels of the node that point to me, I hash it, and I come up with a new label, and that goes on and on. And this idea is similar to the Gaussian legacy in the sense that I consider my source vector, actually my target vector, and I take your source vectors And I basically do this. So if you want to know this for bipartite graph, basically you can apply a bound to the twice final minimum via two directed networks by just increasing— if you have n nodes, you have a 2n bipartite undirected network. Basically you can show the same bound. This is not useful for the actual implementation, it's just a parallelism that is interesting. And the very first experiments, so the very first offline data, I would think like we have Richard also the volunteer in the next slide. We use LAD which we are taking the dominant left singular vectors, okay, the dominant left singular vectors. For sure the paper has more Large datasets. Here I want to show the core, the neural science here, and those are citation graphs and machine learning and other disciplines. We also have class section for the authors, but this is very important. So, it's about how we train the network and what we use for validation and testing. So, okay, I mean, one takeaway message is that even something as simple as just putting the alpha and beta scalars and attaching different importance to the outgoing and the incoming can lead to performance variation. Now, larger values of alpha and beta, for example, alpha goes here, beta goes here, So that's why over 100 degrees of confusion, right? Because if they boost the drift, so the diagonal increases a little bit. So they generate smaller values for certain target encodings, and then if you apply the sigmod, actually many things have still small values, so you basically do not predict speech very well. So that's why I actually listed in the good case in the paper, in the appendix, You can see that when you have both alpha and beta large or small, you go to the bottom of the continuum. All right, so how much do you do this? It seems that the best results are for around alpha and beta about 0.5. Surprisingly, this is true even for models in recommender systems when you do something similar. There it seems that a small positive value was also the best performance. And then small values of alpha and beta under— right, so in general, larger spectral intervals. What I mean by that is that— so, so the blue, orange, and green line, right, we have alpha and beta equal to 0.5 and 0.8 respectively. So basically, when you, uh, when you use small alpha and beta, it doesn't kind of compress all of the information into a bunch of directions, and that is not talked about very well. So on the other hand, if you have qualified for both alpha and beta, this issue is— you have a smoother— but in any case, smaller outputs are important also for the project to make the connection, right? J1 by i, and then smaller values of beta are 0.5. So basically, why it works is because you can tune the network during training, can tune the network to give higher consideration to different things. And let me see. OK, and just to conclude this part, Here is a table against some other— Gravity and Short Circuit are in the same paper. Gravity introduces the concept of vertex mass, while Short Circuit is something less refined, less advanced. It uses an independent size group for its nodes. It stacks assertion and value vector at the same same training space. So basically, this is the one that is the most powerful to directly grab the encoder. Well, you will notice that the part without even the normalized paths, that's slightly better. It's not always the case. However, depending on the problem, you might not even need the full-blown part of neural network and the HITS-like idea. And I'll go quickly through this part. So the quantum graph transformer, right? So the idea here is that you want to perform graph analysis using AI models. Sure. Okay. I mentioned, I talked about graph transformers. We work on graph transformers. That was the original problem. I was planning to talk about, to do that online session and then something else. This paper, I think this was published at ICASP last year. And well, the idea is to take the graph transformer architecture that's been done by Muppet to a quantum computer. Now, when I say Muppet, I have to admit that I'm very optimistic, right? Almost everything that I'm going to talk about could be done and implemented in a very, very different way. So I say quantum black transformer, but take that with a pinch of salt because the topic is far from clear and, yeah, I mean, too complicated. So why do you want to address the quantum? Because they have— because due to the attention you have auto-autodetected. So you can discover latent connections that are not yet, are not there by extracting those from the advanced media. So they can potentially give better performance in terms of accuracy. How you train them and how long it takes, that's a completely different discussion. So at the time, I'm not even sure now, there was no related work. So we said, oh, maybe we can try it. Quantum computers, now I don't know how many of you are familiar, they are just non-classical computing paradigms, right? They don't use bits, 0 and 1, they use qubits, which can be in a superposition of 0 and 1. So basically you can be anywhere in the sphere, and by virtue of that they can supposedly compact and transfer much higher volumes of information They are post-quantum architecture, means they don't have memory. They carry information and compute on the fly. So the memory, yeah, it's also the— Now, what you need to know is that no matter how tough it is to deal with the notation or the architecture or hardware or devising sustainable algorithms for these devices, what they are really is matrix vector engines and basically they take a state and they apply gates, which is nothing else than unitary matrix vector products. So they transform an initial state to some other state, right, that you don't know, but you can measure collapse essentially, and that's it. And by say measure, the moment you open a quantum computer, you don't know what was in there, right? So, so basically you have a quantum state that you will have to collapse to 0, 1, 5 bits in the end. However, this is very probabilistic. You don't know if you will get 0 or 1. It depends on the other things that you never know. So you have to run the experiment again and again and again. So I'm not going to go through all these details. However, if you want to do a proper study of quantum graph— quantum transformers, uh, the subject will keep paying you. So, and so we try to work with the situation. So I say that what we're going to discuss next is far from exact science. And what I mean by that is that while sound, many things can be designed. So the idea, the idea that we have in graphoptics is you start with a graph section of the coating, right? That's embedding a pitch vector that you dump some position on the coating as well. And then you have the attention. So this is graph transforming 1, graph transforming 2. Then when you go to the quantum part, you have to encode this graph structure by the initial embedding with a quantum circuit. And then you also have to do the attention mechanism. Obviously, there is no attention mechanism in that quantum circuit. So we use a variational coding circuit parameter case. So you have the, the parameters here, right? So here we have positional encoding, global attention text, and then you model the one part of the encoding part and encode it one attribute, and then the variation one attribute. I mean, you know, I'll just say it the right way. And how do you encode the first part? How do you encode the bottom attribute Well, I don't know. We don't know what is the best way, right? But what we know is that you can start from this ground state and then apply some Hadamard gate, which means randomize your initial entry. So you just randomly flip things, right? That's all. Like a random distribution in a sense where you have entries plus minus 1, right? And then you apply some gates, some quantum gates, that basically what they do is they just change the phase at random. So you basically start from something deterministic and you poke it. You just add randomness, right? To create some, actually, yeah, to create some initial encoding. And then once you have that encoding, you try some, you try to do what the Nash-Poker does, right? You try the attention part of this all to all. So you have a circuit that you connect every qubit to every other qubit. You add some parameters there that you need to learn, and that's basically the attention. How you do that, you just add some angles around the y-axis. So to make things more clear, you start with a graph with 6 nodes, right? And this connectivity, In this particular case, it's unrectified, but it can even be different. So you have the encoding scene, right? So you have 1 qubit per node. So you have 6 nodes, you have 6 qubits, and then you enforce the structure dictated by the graph, right? So in other words, let's say 0 is connected to 1 and 5. So we see connection to 1, qubit 1, to be 5. So here's the Hadamard gates for the randomization part. And then you have the connectivity by having 2-to-2 gates passed on board by the network itself. So you do a forward pass for the encoding part. And then you have the variational circuit where you have the gates, different gates with different theta. And so in total, when I say it's not an exact science, because when you have more nodes, for n nodes, you will have 2n power, not n squared. Like a regular song. However, it will keep adding the same gates and see what comes up with. It's not clear how that will suit, but we found that this approach was the best. And basically, it's a— you encode your graph with a single vector. So the vector is one of the same embedding, but then you go and pass through the network and change all the other mixtures. Pairwise connected. And again, another example, just a few pipelines. So imagine that you have just a child, right? And you encode it, you encode the connection, you go through the quantum state, right? It's something like this. I mean, you cannot plot it when you actually run it, but I simulated it. Do something like that. And then you have the variational circuit, and then your variational circuit will go and be in one of the 2n— so for n qubits you have 2n states, right? And then you measure that. However, you, you measure only probabilistically because you don't know what state the qubit actually is. You can only sample again and again and again. Uh, so that's how quantum mechanics works, right? So it's nothing about a However, having this two-phase transformer, so you have both things at the transformer phase, you have embedding and then autoencoder. How you implement them in a quantum computer, we implemented them with two different circuits. And so here's a really toy example. Reminds me of, you know, you have, so you have QLSTs, so you have 1,000 nodes, which means you have 1,000 units using this idea you have, uh, 2 to the 1,000 states, it's impossible. So, so the idea where you have one node per qubit needs some work. So, uh, however, it's a start. Uh, so now we did graph classification, right? And the idea is, does the graph have a triangle link of 3 nodes? This one has, this one doesn't, right? So if it has, it's labeled 1. If it doesn't, it's labeled 0. And you want to understand whether the graph that I'm giving you belongs to class 0 or 1. I just have to mention that you can do decomposition, graph decomposition. So you don't even need a quantum computer that can run the entire graph, because then for the travel down the protocols, you can And there are specification techniques where we can give them sample subgraphs and then decode the skeleton and then do graph matching, right? I mean, if you know that certain graphs have a certain number of triangles, then you can do structural matching that you can easily do with a quantum computer and say, okay, I'm 90% similar to a graph with 5 triangles, so maybe I have 10% of triangles. So anyway, so we evaluate the training performance in terms of training loss and average precision. And well, the evolution of training, right? Clearly, it's not rapid. However, it does show that you can actually learn something. You do. Like with that quantum circuit, I mean, basically this, right? That you try by doing this encoding and by having rotate Y-axis rotation right in the beginning and then at the end, it actually learns something meaningful. So it imitates this. So imitating this transformer, graph transformer idea to a quantum computer can give you something. And this is the last slide. Yeah, so these are some of the different actual quantum computing protocols that IBM has, and we map the software. All this was done with Qiskit, right, with a Python simulator, and to do this different detection. And what he saw, how the precision shows, is that we took some slightly boosted random choices. That's why you see it fluctuating around 0.5, because we're starting with some angles and we're giving something better than 0.5. And then you incorporate the answers of what you learned with the quantum graph line solver and go first to one. Admittedly, the problem is not really tough, but it shows that you can actually learn something. And I don't know if other people have tried. And the quantum computing thing is— I mean, IBM supports the quantum system. We have quantum computers at IBM. So yeah, that was the main ideas. So that's all. Thank you. I do want to say a few words. Emmanuel also works on the directed graph in one of his— I think there are some similarities between your work when you— because in their work they are introducing the, let's say, one direction. So they learn in one direction and you do other direction. So you define these architectures. Yeah, yeah, we— you're separating the source and destination of that, which is just an idea. Our work, which was actually published last year, it's kind of an extension of MKNN, where you basically aggregate in both directions, but you have different weights. But then you kind of, you only have one vector for each node, so we don't separate. That's why it's interesting. Many look at classification, whereas you looked into predictions. So probably for predictions, I have a feeling it's more important to separate, right? Which then you can Yeah, yeah. So the reason why we started trying it, because it cannot be done tonight. I just took the kids' idea, both familiar, I mean, all of us were familiar. So we said we try it. Yeah, trying it, it kind of started to make sense, but it's in the sense that you could pick up some signals, right, to do the task. But yeah, I mean, what, what, what, what research is it? Uh, yeah, that's good. I really like the idea of, uh, I think it was, if I remember correctly, was your paper proving that if you split the— basically, you know, theoretically, if you have a graph with 2 nodes for each node, right, then you can represent, uh, any directed graph with non-directed graph with double the number of nodes, right? Yeah, for the W and the Yeah, yeah, that was a paper from the original foundation in 2019. And yes, we actually thought about how to do that. And the idea of the double parsing eventually, you know, because if I am source and you're the target, you know, if I do WGL directly to the case, it's like I'm mixing source and target. So we said, yeah, let's mix it. Let's have a Cool. Thanks. So I also have these quantum graph transformers. Are you looking into, let's say, the expressivity of the, let's say, hierarchy? Or yeah, so it makes sense to also extend Yeah, these ideas to— and first of all, you should— I mean, from the— from if you simulate the thing, maybe not that much, but if you were to actually be serious about in the future, like actually, you know, uh, if science takes us there, right, when you can use quantum computers for this, you will have to do what you say, because if not, then this is the whole secret you are having in your head, they're going to leak quickly and suddenly. So quantum computing You have to do things rather rapidly, right? Because then there's something called decoherence, and the qubits start becoming unstable. So you have to maintain them at freezing temperature, almost 0.2. So I think learning, yes. In practice, as a good method of doing things, if you were to ever be serious, you'd learn them, probably yes.