Scientist Stories Jie Gao, Network Analysis and Learning

We are going to start the next speaker. So we are having Professor Jia Gao from Rutgers University and She was previously in Stony Brook University, probably, yeah. And she's going to talk about graph BQFlow and its relationship to the network analysis and probably GNNs. Thank you.

All right, thank you. Thanks for including me. We have been doing this for a while, but I want to summarize and show you know, the geometry of graph problems and applications we have used. So to start, we are always fascinated by, you know, real-world data with this complex network with many, many interesting properties. You know, this goes from internet graph to the brain network, social network, transportation. And many of these graphs we see in reality have interesting properties. Model phenomena power law, community structures. So we often study this graph structures and interesting problems include, for example, how to understand a single network. So on a graph there are interesting structures such as clusters we call communities, or in graph learning we have labels on vertices we want to propagate the labels from a given dataset to the unknown vertices. And we are also interested in understanding the family of graphs. And if I gave you two networks, can you align them, compare them, find the response, or understand in terms of generative models to capture a family of graphs? So we work with the following hypothesis that in general, if you have a graph, you may think about these vertices to be staying in a high-dimensional latent space. In addition, these vertices, although in a super high dimension, they may actually stay in a much lower-dimensional manifold. And if you look at the graph, you can understand the graph to be capturing proximity information of these unknown underlying my results. So working on this hypothesis, we propose to use geometric tools to study these graphs. In particular, I want to share, you know, what we did with our Lydian Ricci coverage and also coverage flow for capturing interesting properties of these complex networks. So let me start with curvature in classical geometry. Basically, consider continuous surfaces, and we can define curvature for a point that basically measures how curved the space is at that point, how far away the surface is from something flat. So you can see this— there are different types of surfaces, and, uh, we use This analog from this classical notion of sectional curvature in geometry that basically look at, for example, if I have a point x and have a tangent vector xy, and now if we look at the other tangent vectors, you know, from x and translating y, we want to look at if this parallel vectors are going to travel roughly in parallel or start to converge or start to diverge. So the differences is captured in this notion of sectional curvature. And the question is, can we extend this to a discrete setting? For example, if I have a graph, then can we define curvature using a similar idea? So this is the definition of Euclidean curvature. Which is extending this notion to graph settings. So now let's take up edge XY and let's consider the distance from X's neighborhood to Y's neighborhood. And we want to calculate the average distance of traveling from X's neighborhood to Y's neighborhood, and we want to compare this with the distance from X to Y to see if it's larger or smaller or stay the same. Now, different from the continuous setting, in the continuous setting we have a nice correspondence of these tangent curvatures, but here we don't. So how to compute average distance? Basically, one idea is to use optimal transport. So to give the formal definition, here is the formula. So we have a vector space, we have two probability distributions defined on X and Y, and we look at the optimal transport distance of moving from the probability measure around X to the probability measure around Y. And this is the optimal transport distance, also called Wasserstein distance, WY., and divide by the distance from x to y, and use 1 minus this ratio to be the curvature of this edge x and y. Okay, let me give you some pictures to understand this better. So let's start with a simple setting of a grid, two-dimensional grid. Now I have x and y, their neighbors on grid, and then if I look at x neighborhood, which will be the 4 vertices around x, y step 1 will be again 4 vertices above y. Now if I consider this possibility, like, translate it from x to y, I can just basically move everything even 1, like, shift it, and that will be the optimal transport distance. So if I put it in the previous formula, I have 1 minus— what's at the distance which is 1? Divided by 1, so this is curvature 0. Makes sense? Okay, so that is perfect because it matches with our intuition that if I have an infinite 2-dimensional grid, it's flat everywhere, so I should have curvature 0 everywhere. Now, moving on, if I have a tree, we can actually write it down exactly what is the curvature. So the curvature for, in general, an edge (x, y) is actually -4, where dx and dy would be the degree. And in fact, apart from this vertex at the very end, for all of the other edges of a tree, you have negative curvature. Again, this matches with the intuition that if you have a tree, is the curvature negative? Basically everywhere. Okay. For complete graph, this is a highly clustered graph, very dense, coverage is positive everywhere. All right. So now let's look at some real-world graphs. So this is the picture of the Internet Autonomous System network. So we basically calculate curvature for all of the edges and then color the edges to be the red edges have negative curvature, the blue edges have positive curvature, the green edges have curvature roughly zero. So as you can see that basically there will be like local network that are positively curved and these are connected to each other through negatively curved edges. And these negatively curved edges are mostly the backbone edges. So the dataset comes with labels like which are backbone, which are not. And we compare these, we see backbone edges are almost always negatively curved. Again, matches with a lot of others' understanding of the internet topology that is tree-like hierarchical structure. So that matches very nicely. So okay, now we have coverage defined on edges. I want to move on to this notion of coverage flow or reaching flow. So reaching flow was initially introduced for the continuous setting. By Hamilton. And the study— if you have a surface, you have curvature on every point. Now let's have a dynamic procedure. So basically the metric is modified by the curvature with the objective of smoothing out the curvature everywhere. And so we could do the same thing for a discrete setting of finding the Ricci flow on the graph. And basically, I said that this procedure is going to shrink areas with positive curvature and enlarge areas with negative curvature until to a point— there is a critical point, a singularity, where it basically kind of breaks apart. And basically the same thing happens for the discrete setting. So let me show you the formula. So again, once we have the coverage defined for all the edges, we can start to modify the edge weights of the graph. So the way you do it is to take the original edge weight, subtract as small— it's just a step function— step size times the coverage and the current edge weight. And this whole thing is normalized so that we make sure, you know, the collection of edges has the total size or weight is fixed. So once we do this, we're going to basically start to stretch the negatively curved edges and start to compress the positively curved edges. And then what happens is the cluster or community Vertices are going to be basically put together, like, you know, brought closer, while the edges connecting communities are going to be stretched. So in particular, actually, it's very possible to use different kinds of distributions that we use to define coverage. We could go with the classical definition that is proposed in the original paper, which is uniform distribution the neighbors, or another distribution that basically favors vertices that are of smaller distance to X and Y. So the second one actually speeds up this procedure towards convergence. So, okay, before I show you all the experiments and data, I want to say a few words about what is known. Of this type of Ricci flow theoretically. So there are questions, these are fundamental questions that ask, does the Ricci flow converge and does it generate unique solutions? So people ask this question for different settings. For the classical medical setting, so answers to this question are connected to the proof of the Poincaré conjecture. And for the discrete setting, a different coverage of discrete Gaussian coverage, again, these questions are answered and convergent, and the solution is unique. And for the graph setting, it's still largely unknown. So lots of questions are still open. So we know, like, for a very special case, we are able to analyze the behavior of rigid flow which can basically show this phenomenon of communities moving away from each other, but only for a very special case. Now, for the continuous dynamics, there was convergence result, but with the assumption that the edge connecting like two vertices in B is always a shortest path. Like once we start to change the weight, This is no longer true, right? You know, you don't know where the shortest path really is. But with the assumption that suppose this is true, you know, this paper shows convergence of reaching flow in this continuous setting. But these are the only known results on this problem, and we don't know, like, you know, there's still generally the question is open. All right, I want to move on to say a few words of how we can use this coverage result. So I want to talk about 3 applications: immunity detection, network alignment, and graph neural network. So this is karate club. Everyone knows about karate club. So this is a graph with 2 communities labeled. So we start with the coverage packing limit on the edges., and we start to evaluate it well, right? So basically, after we evaluate it well, we realize that if we look at the edge weights, there are very clear 3 clusters. Basically, there are edges with very high weight, much higher than the others. And then what we could do is say, let's cut these edges that are really, really long. And after that, we naturally have two communities. In this case, there's another group of edges that are also slightly longer than the others. We could cut it again, and this will achieve that one of the communities further into smaller communities. So this is what happens when you run each flow on the graph, and you get this very clear structure of communities being stretched away, and you can easily cut them to get the community structure. Okay, now maybe on a larger network. This is again real-world dataset of Facebook Ego Network. So this would be like the 700 friends of somebody here, okay? And these friends are labeled as belonging to different friend circles. And again, well, we should go and partition them into like small communities. The colors represent if they belong to the same friend circle. We can see that there are certain cases where, you know, maybe it's a mix. But in general, we do partition this friend circle into meaningful groups that match the function's label. This is brain network. Again, we solve brain network. So again, this is fMRI data with resting state brain network. Edges represent parts of neurons that have high correlation. So again, we run this, we get different groups of neurons connected to each other. And we're going to do again multi-resolution thing to get different type of communities. So like on the side, we also have basically modularity tests just to see if we're cutting the graph to get communities with large modularity. Modularity means we're more likely to be connecting to vertices in the same community as opposed to vertices in different communities. So in these at the places that we place the cut is actually, for instance, very nicely to generating, you know, highest modularity after we remove these edges. Okay. Comparison with many other community detection methods. So this is such a classical problem. So No wonder a lot of work already on community detection. Basically what we see is that our method has a sharp transition, meaning I would like to have, you know, good community detection results when there is community structure. But when the graph doesn't have community structure, I want to say, you know, no, there's actually no community, or maybe the whole thing is a single community. So this sharp transition is indeed captured by our method. That's like a phase transition. Okay, questions so far? All right, moving on. I want to continue with two other applications that we worked on. One is network alignment. So basically we have two graphs and we want to compare these two graphs. And one of the ideas we use is to get some distance measurement, meaningful distance of vertices in the graph, and then want to use that to make the alignment. So let me first talk about What is a proper distance measure I could use for two vertices on the network? Okay, so there are many, many possible distances one can design for vertices on the graph. And typically, if you have the application, the application often gave you some very meaningful distance measure. So if I'm talking about the internet, I could measure the latency. Between two vertices. This is a very meaningful measure. But of course, this is costly. You may not always have it. On the other hand, if I have a social network, I could possibly measure tie strength. Again, this is, you know, something with physical meaning but may not be easy to get. On the other hand, if I have just a graph, one simple thing to use is just to count the number of hops. Okay, so this is easy to get, but there's another trouble with it. All of the networks we handle have small word property. So if I use just hop count, I'm going to get a number which is an integer between 0 to 6. So it's not very, very useful when I want to use this to, you know, distinguish if it's far or close by. Okay, so what we propose is to— oh, okay, one more thing. Yeah, I forgot to mention is one could also do all kinds of embedding, right? Once you have an embedding, you have a distance coming from the distance in the embedding space. Okay, and over here, like for example, spectral embedding, could do this kind of a scoring embedding. But sometimes you need to worry about sensitivity issues, that is, if you have edge insertion or deletion, how much does it change your embedding or change your distance? So what we want to propose is to say, let's use reaching flow for that. So before I show reaching flow, I just want to say a few more words about this robust recognition. So here, I'm showing you this is a karate club network. And I'm showing you this is spatial embedding. And this is a class of embedding called spring embedding, which is you fix some vertices. And you imagine the edges to be springs. And you just let it go. So the entire network will stabilize. And therefore, you have edge lengths coming from the embedding. And you could use that to measure distance between two vertices in the graph. Okay, so what happens on the picture is I'm measuring distance from head of the link to a face node. And I'm also painting like a few edges in the graph. I want to look at the distance before and after the change. Okay, actually I'm going to color the vertices Like basically pink means, you know, the darker the color, the higher the change. Okay, so as you can see, in both cases, vertices are somewhat pink, like some changes. Now I want to show two more pictures. The left side is actually just using Pop-Cuts. At the right side, this time, the distance measure we get from Reachability. So you can see, compared to what we had before where everything is almost pink, but here you get the colors to be like a lot lighter, right? No surprising, if I look at hop count, just because there are many, many, many shortest paths between a pair, So if you delete a couple edges, you still have other shortest paths that give you the same cost. So HopCount is super robust, in fact, for network dynamics. And that's, you know, validated from this picture. And what we have is also quite robust. So the truth is, before and after I remove the edges, the distance is still somewhat similar. So this is useful because whenever we use applications, we want our distances or even measures to be robust to small changes in the graph. And this nice property can be useful for, you know, this application of graph isomorphism for alignment. So when I talk about two graphs, One question I ask is, can we find correspondence? This is a classical problem of graph isomorphism. So if you look at these two graphs here, these, you know, although it looks very different, but they are exactly the same graph. So if you take the vertices of the same color in the very front, they have the same topology. So can we compare two graphs to basically find the first one. This is a very hard problem. Okay, so it's not known whether it's NP-hard. You know, like again, we don't have polynomial algorithm. There's some improvement, but still like very, very open. What we want to do is again take a geometric approach and try to find coordinates for vertices. By using these coordinates, we can try to match the two graphs. So for example, if I have two sets of points in the plane, how do we align these two sets of points? So one idea is I can map the— let's say I'm taking landmarks, I'm taking three landmarks, and every vertex I measure distance to the three landmarks. This is basically barycentric coordinates in a 2-dimensional setting. Now, if I manage to align the landmarks of these two sets of points, then I can match the other points just by the barycentric coordinates. If they have the same coordinates, they are the same point, and so on and so forth. Okay, so basically there is a representation of these sets of landmarks, and the perceptual word is actually similar, then we say they are likely the same. So we basically tried that, but on a graph. And the distance we use, again, we want to use a robust distance and also a distance that gave us lots of information. So we're using the distance we get from speech flow We also compare with some other distance measures. And then we try out two different experiments. One is we just take a random connected graph and randomly remove a node. And then we see whether we can align the two graphs before and after I remove one node. And another picture, I take a frozen protein network and randomly remove 10 edges to see if we can find the correspondence. Basically, I'm using a very small number of landmarks. So here it's only like 2, 3, 4 landmarks that you can easily pick in these networks because often you have high-degree vertices that will be naturally the landmarks, the choice of landmarks you want to use. And the robustness of the metric brings us benefits because we have much higher accuracy compared to alternative decent measures. All right, questions? Yeah. So you mentioned that you're using spectral embedding for speech, but if you use adaptive resistance embedding, is this going to be more robust to these? Good question. We haven't tested it yet. Yeah, we haven't tested that, so I don't know. Yeah, I don't know where it is. Yeah, the Spectral and Spurring are those. Spurring is actually not that bad. Spectral is very not at all. So Outcome, although it's super robust, but just because it's not very discriminative, so it doesn't give us a lot of information. All right, I want to in the last part talk about again this robustness property and for applications in graph neural networks. So basically we look at graph neural networks for node classification and then we ask the question of how robust is this model? That is, If you think about adversary that try to insert or delete edges in the input graph, you know, how much can we tolerate that kind of adversarial input perturbation? So basically in this setup, you have the quality, you have some features, you want to learn a model that predict features for the other like unknown labels. And we take this approach that goes back to this hypothesis that although we work on one single particular topology, but imagine these are actually vertices that stay in some underlying latent space, a manifold over there. So this graph is actually a one single concrete realization of the proximity information over there. So if we're trying to do some learning on the graph, We really care about this underlying manifold, and we want to get some knowledge about this proximity information in the underlying manifold. So that's the motivation that we should use this rich flow metric, which is I start with a graph, I try to do rich flow, I learn about proximity information. Now I define like basically a new distance measure between the vertices And now in the learning, I'm going to sample from this underlying distance matrix. And I want to sample independently for different episodes of the training part so that I will not be depending on this particular input, but I allow myself to try to discover this underlying proximity information in the latent space. So that is basically what we try here. So I wanted to show a couple of pictures. This is a stochastic block model. So the data is there are 5 communities, and then there will be still some edges connecting some pairs of communities, but There are no edges for like some other pairs. Now these red dots are actually adversarial input. So somebody tried to mess you up. So they just randomly placed some edges in the graph. So this is the reachable metric we learned from this graph with these adversarial edges. And then here is resampling from this graph from this metric. So you still have like lots of these dots from this adversarial input. And over here is actually an intersection of two different samplings from the same metric. And, you know, we are able to remove quite a lot of this adversarial edges and the influence of that in the topology. So again, the best to go with these are some numbers to see, okay, how much we can tolerate the adversarial changes to the graph. And basically we want higher numbers. So that's all what this figure is saying. Same thing, kind of depending on different type of graphs. So, you know, this graph might have different sparsity or density. So the performance varies a little bit. Okay. So I want to pause here. So basically, to conclude, there are very nice geometric notions for continuous setting, and there are ways of adapting that to the discrete graph setting that basically bring geometry into the picture. And, you know, here it's about distance measures and like coverage. And actually, we could look at embedding. This is the earlier talk that talked about embedding not necessarily in Euclidean space, but in hyperbolic space, or maybe some other kind of hybrid space. Another direction that we are very interested in is to answer questions about network evolution, because this network changes over time. We understand the graph now. We want to understand what will be the prediction of the graph of the future. And in particular, can we understand how this network evolves over time and more applications down the road? So for the last, I want to say this joint work with many wonderful colleagues and students. So we started this like 10 years ago, time flies. But like try to do different things. And if you want to read one paper, I recommend this one. It's probably the most thorough one. And we also have the code available on GitHub. Okay, last time I checked, it was downloaded something like 130,000 times. So I was amazed, like, wow. So we're happy that we're making contributions to the community. So please, if you want to play with it, this is carefully written code that you can use right away. And questions or comments?

That's it. The character for different kinds of— I mean, like, for the Chinese, we like structurally have the negative weights from different axis. I mean, there's like a relationship between the visual and the text recognition, right? So, together with the parser, that probably we can do some more interesting things, like we can decompose it like the Those long distance choices.

Right, right. Yeah. So it's a great question. So the question is about whether we can use coverage against maximization. It's a great question. I think, I think there are opportunities. In fact, I imagine that you want to get your vertices to be around edges of connected coverages inside each different communities. But embedding it inside a cluster is not a good idea. I don't think anyone's done it. It's a great idea.

Maybe a great paper. Yeah, I don't know. So yeah, that's a similar question. So we talk a lot about this curvature and how it relates to structures. We also know a lot about category, we also know about these things like compactness, modularity. Do you have some— would you recommend us to read some of the classical results that tell us the correlation between this?

Or maybe just briefly tell us. Yeah, so again, a wonderful question that is also related to the classical notion of spots or communities. Actually, this is one of the major open questions, as I see, that if we really want to say something like if my graph has community structure using some of the classical notions, I want to say this, you know, region coverage area can be tested. So we're able to say this for a very special type of graph, which is a complete graph, where I put another complete graph on each of the vertices. But that's it. We can write down, you know, what the region flow converges to. We can write it down in deep partition lists. But I think, you know, that is like very special. So It's open, so if something can be done in this direction, that would be great.

Thank you so much.

Thanks. All right, thank you.