PRSim: Sublinear Time SimRank Computation on Large Power-Law Graphs
Wei, Zhewei
He, Xiaodong
Xiao, Xiaokui
Wang, Sibo
Liu, Yu
Du, Xiaoyong
Wen, Ji-Rong
it SimRank is a classic measure of the similarities of nodes in a graph. Given a node u in graph G =(V, E), a single-source SimRank query returns the SimRank similarities s(u, v) between node u and each node v in V. This type of queries has numerous applications in web search and social networks analysis, such as link prediction, web mining, and spam detection. Existing methods for single-source SimRank queries, however, incur query cost at least linear to the number of nodes n, which renders them inapplicable for real-time and interactive analysis. This paper proposes prsim, an algorithm that exploits the structure of graphs to efficiently answer single-source SimRank queries. prsim uses an index of size O(m), where m is the number of edges in the graph, and guarantees a query time that depends on the reverse PageRank distribution of the input graph. In particular, we prove that prsim runs in sub-linear time if the degree distribution of the input graph follows the power-law distribution, a property possessed by many real-world graphs. Based on the theoretical analysis, we show that the empirical query time of all existing SimRank algorithms also depends on the reverse PageRank distribution of the graph. Finally, we present the first experimental study that evaluates the absolute errors of various SimRank algorithms on large graphs, and we show that prsim outperforms the state of the art in terms of query time, accuracy, index size, and scalability.
 This is a joint work with Xiao Donghe who is my student, Xiao Kui Xiao from NUS, Si Bo Wang from CHK, and Yu Liu from PKU, and Xiao Yongdu and Jirong Wang from my university. I'm Zhe Weiwei. I'm a social professor at Remy University. So let's start with the problems and motivations. So we're interested in Simrank, which is a similarity measure between nodes in graphs based solely on the graph structures. So the idea of Simrank is very simple. A node is more similar to itself. So here the university is more similar to itself, and two nodes are similar if they are referenced by the same or similar objects. So the two professors are similar because they are referenced by the same university, and the two students are similar because they are referenced by similar professors. Simrank has this recursive definition, which essentially says the similarity between two nodes, u and v, is equal to 1 if u and v are the same nodes, and they are equal to the average of the similarities between the neighbors, in neighbors actually, times the defective factor c, where c takes value from 0 to 1, and c is usually 0.8 to 0.6. So we are going to look at Simrank at a different angle, which is the random work interpretation. So this is the square root c work, where at each step this random work terminates with probability 1 minus square root c, and move to a random enabler instead of an odd neighbor with probability square root c. So here c is just the defective factor I mentioned before. It takes value from 0 to 1. So what connects Simrank and the square root c work is that if we start two square root c works from u and v, and the Simrank similarity is just the probability that these two random works meet. By meeting, I mean they have the same node at the same steps. So if these two random works work like this, they both meet at node 8, but not on the same steps, so that doesn't count. This definition actually gives a very simple color algorithm for computing Simrank's of two nodes. That is, we can generate multiple pairs of square root c works, and count the percentage of pairs that meet at the same step, of course, and that percentage is going to be a good approximation of the similarity between u and v. But we are going to look a bit beyond this single pair problem, and we're going to consider single source and top k Simrank queries. That is, given a source node u, we want to compute the similarities between u and every other node in the graph. For top k queries, we want to return the top k most similar nodes to the given source node. We're going to allow an area of predetermined value epsilon, because it's generally very difficult to compute these values exactly. Single source Simrank queries have a lot of applications. For example, span detection, recommendation system, where you're supposed to find similar items to a given item and recommend to the user, and clustering, where you're supposed to find similar items and group them together. Because of its importance, it has been extensively studied for the past decades. And since obviously I don't have time to go through all this work, so let me just say this. They all suffer from two drawbacks. Most of all, they all take a linear query time, which is unexpected because you have n nodes and you have n similarities to report this. And some of these existing methods are random work-based. So what they do is they generate a bunch of random works from each node, and they compare this random work with the random work generated by the source node to see if they meet. And that way, the query time is the number of nodes times number of random works, which is a small number and it's not very scalable. For other methods that based on linear algebra, they also have to pay at least the number of nodes or number of edges. So the first question is, can we achieve sublinear query cost? Because we have an arrow that we can leap with. So the second drawback is that we don't yet understand the hardness of similar computations and graph structures. So take these two datasets as an example. They have similar number of nodes and they have similar number of edges. But if you run existing similar algorithms on these two datasets, you are going to get very different query times, even with the same parameter. So this means there's a lot of things going on in these two datasets that we don't fully understand. And there is a paper that says, OK, this may be caused by the data sets is locally dense and the IT data sets is locally sparse. So we really want quantifiable skin for this characterization for this phenomenon. So here are our results. First, can we achieve sublinear time on any graph? The short answer is no. Because if you look at the graph on the left side and you ask what are the similar nodes to node 1, then you are going to get that every node is similar to node 1. Because if you recall, the similarity of the node 1 and 4 is the random work probability from 1 and 4 that meet at the same steps. And if you start the random work from 1 and 4, they are going to meet at the central node, which means the similarity between them is the decay factor C. So therefore, the output size is a dense vector. It's of size n. So to simply output this vector already takes all of n computation. So it's not going to be possible to achieve sublinear time on this graph. And this would be the end of my talk, except I have to go deeper. So fortunately, the real world graph does not look like this. Real world graph looks like the one on the right side, where the degree distribution follows power law. So we are going to look at the power of these graphs. More precisely, like pk to be the percentage of nodes that has degree k, then pk is going to be proportional to k to the power minus gamma, where gamma is a power law exponent larger than 1. And what our algorithm does is that our algorithm PRC can achieve this following query time. If you look at this, it's going to be related to the power exponent gamma. But to make sense of this query time, let's look at the case where gamma is larger than 2 or equal to 2. In this case, our query time only depends on log n. So it's very much very, very sublinear log n. And for this case, where gamma takes value from 1 and 2, which is usually the case for most real world power graphs, the query time depends on n to the power 1 minus gamma or n to the power 2 minus gamma minus 1, whichever is smaller. If you take a close look at this, 1 over gamma is smaller than 1, since gamma is larger than 1. And 2 over gamma minus 1 is also smaller than 1, because again, gamma is larger than 1. So in both case, this term is sublinear to n, which means our algorithm is sublinear to the number of nodes. And that's a good thing. And this also gave us a hint that since our algorithm reversely depends on the value of gamma, maybe some other algorithm, similar algorithm, also have long internet, reversely depends on gamma. And it turns out to be true at least empirically, because if you look at these two data sets I mentioned before, they actually have very different gamma. The IT has a much smaller gamma, and Twitter has a much larger gamma. This might explain why these previous algorithms perform very differently on these two data sets. So next I will introduce a few highly-videos of how we can achieve sublinear time, a query cost. And the idea is very simple. So given a source node, our algorithm PRC starts a random work. And since it's a square root C work, it's going to terminate at some steps. And instead of computing random works from each node and see how these random works meet with these paths, we're going to reversely compute these so-called probability trees from the node on this path. And we are going to do this by probability tree. I mean that we want to compute, let's say, the probability that node W visits node C is 103 if you ignore the decay factor. And we're going to compute such probability tree based on pre-computations and sampling in an online fashion. So with pre-computation, we can build an index. But there is a problem of which node we should choose to compute index. And there's actually a previous work by Xiao Kui that suggests to compute, pre-comput the probability trees for all targeting nodes. But this would result in a huge index size over the end over epsilon. And it's going to be much larger than the graph size m if you want small epsilon. So our method is that we only pre-compute the probability trees for hub nodes. And by hub node, I mean node with high page ranks. Why is that? It's actually very simple because if you choose the source node randomly, then a random work from a random source node is more likely to read the node with high page ranks because that's the definition of page rank. And therefore, pre-computing such probability trees for hub nodes is going to be reduced the quality most efficiently. And in the online phase, where we are supposed to compute these probability trees for non-hub nodes, there's actually an algorithm called a probe algorithm that can do this. And the idea is that suppose we want to sample, we want to sample the nodes at the step three, for example, w with probability one third. And what we do is that we sample node i with probability one, since there's only one edge from i to c. And then we sample g and k with probability also one because it only has what degree one. And then we sample f with the probability one over three because it has three edges, incoming edges, and one of them is connected to c, to i. If we fail to sample f, then if we fail to sample f, then all these nodes under the subject of f is going to disappear and we don't have to deal with that node. Hence we can save a lot of time. But this algorithm alone is not going to give us sublinear time because it's not efficient for nodes with large degree, out-degris. For example, if we want to sample the out-neighbor of this degree, this w, then we have to read it, this all this node, before we can sample them. So we propose this backward work algorithm which can only read a very small fraction of the out-neighbor's every sample. And the idea is very simple. We sort the adjacency list by in-degree in the preprocessing phase. And we saw a random number r from zero to one and we only read the number, the nodes with in-degree smaller than one over. For example, here the random number is 0.3, so we only read the nodes with degree less than three. In this case, we only read IGHKL and that's a very small fraction of the entire neighbor. So with backward work algorithm, we can finally achieve sublinear time. And for experiment, we compare our algorithm on five datasets. One of them is actually very large. It consists of five billion edges. And we compare our algorithm with state-of-art competitors index-based or index-free-based. And we use this pulling idea to evaluate precision on large graphs, even though we don't have ground tools for single source queries. And these are the trade-offs between the query time and the error and the precision of top K queries. And as you can see, our algorithm is this pink line. And given the same amount of query time, we can achieve the smallest error and the highest precision. And for these are the trade-offs between the error and the index size and the error and the pre-processing time. We can also achieve the same amount of error using the smallest index size and the smallest pre-processing time. Finally, we did some experiment on synthetic datasets. We generate a bunch of power-lobed datasets with different power-exploring gamma. And we show that these all the similar hours indeed have a query time that is reversely related to this gamma, which confirms our suspicion. And we also did some experiment on random ER graphs, where we can see that our algorithm performs best compared to the average degree, when we increase the average degree. And this is due to the fact that with the backward work hours, we don't really have to visit all the nodes, all the neighbors. So in conclusion, we gave a sublinear time algorithm for single source similar queries on power graphs. And our algorithm outperforms the state of art on large graphs in terms of query time, accuracy, index space, and pre-processing time. And we empirically show that the hardness of similar computations depends on the power-lobed exponents gamma, and for future work, this might be interesting if we can actually show that mathematically, all similar hours is going to be depend on the power-exploring. And that will be all. Thank you.
 This is a joint work with Xiao Donghe who is my student, Xiao Kui Xiao from NUS, Si Bo  Wang from CHK, and Yu Liu from PKU, and Xiao Yongdu and Jirong Wang from my university.  I'm Zhe Weiwei.  I'm a social professor at Remy University.  So let's start with the problems and motivations.  So we're interested in Simrank, which is a similarity measure between nodes in graphs  based solely on the graph structures.  So the idea of Simrank is very simple.  A node is more similar to itself.  So here the university is more similar to itself, and two nodes are similar if they  are referenced by the same or similar objects.  So the two professors are similar because they are referenced by the same university,  and the two students are similar because they are referenced by similar professors.  Simrank has this recursive definition, which essentially says the similarity between two  nodes, u and v, is equal to 1 if u and v are the same nodes, and they are equal to the  average of the similarities between the neighbors, in neighbors actually, times the defective  factor c, where c takes value from 0 to 1, and c is usually 0.8 to 0.6.  So we are going to look at Simrank at a different angle, which is the random work interpretation.  So this is the square root c work, where at each step this random work terminates with  probability 1 minus square root c, and move to a random enabler instead of an odd neighbor  with probability square root c.  So here c is just the defective factor I mentioned before.  It takes value from 0 to 1.  So what connects Simrank and the square root c work is that if we start two square root  c works from u and v, and the Simrank similarity is just the probability that these two random  works meet.  By meeting, I mean they have the same node at the same steps.  So if these two random works work like this, they both meet at node 8, but not on the same  steps, so that doesn't count.  This definition actually gives a very simple color algorithm for computing Simrank's of  two nodes.  That is, we can generate multiple pairs of square root c works, and count the percentage  of pairs that meet at the same step, of course, and that percentage is going to be a good  approximation of the similarity between u and v.  But we are going to look a bit beyond this single pair problem, and we're going to consider  single source and top k Simrank queries.  That is, given a source node u, we want to compute the similarities between u and every  other node in the graph.  For top k queries, we want to return the top k most similar nodes to the given source  node.  We're going to allow an area of predetermined value epsilon, because it's generally very  difficult to compute these values exactly.  Single source Simrank queries have a lot of applications.  For example, span detection, recommendation system, where you're supposed to find similar  items to a given item and recommend to the user, and clustering, where you're supposed  to find similar items and group them together.  Because of its importance, it has been extensively studied for the past decades.  And since obviously I don't have time to go through all this work, so let me just say  this.  They all suffer from two drawbacks.  Most of all, they all take a linear query time, which is unexpected because you have  n nodes and you have n similarities to report this.  And some of these existing methods are random work-based.  So what they do is they generate a bunch of random works from each node, and they compare  this random work with the random work generated by the source node to see if they meet.  And that way, the query time is the number of nodes times number of random works, which  is a small number and it's not very scalable.  For other methods that based on linear algebra, they also have to pay at least the number  of nodes or number of edges.  So the first question is, can we achieve sublinear query cost?  Because we have an arrow that we can leap with.  So the second drawback is that we don't yet understand the hardness of similar computations  and graph structures.  So take these two datasets as an example.  They have similar number of nodes and they have similar number of edges.  But if you run existing similar algorithms on these two datasets, you are going to get  very different query times, even with the same parameter.  So this means there's a lot of things going on in these two datasets that we don't fully  understand.  And there is a paper that says, OK, this may be caused by the data sets is locally dense  and the IT data sets is locally sparse.  So we really want quantifiable skin for this characterization for this phenomenon.  So here are our results.  First, can we achieve sublinear time on any graph?  The short answer is no.  Because if you look at the graph on the left side and you ask what are the similar nodes  to node 1, then you are going to get that every node is similar to node 1.  Because if you recall, the similarity of the node 1 and 4 is the random work probability  from 1 and 4 that meet at the same steps.  And if you start the random work from 1 and 4, they are going to meet at the central node,  which means the similarity between them is the decay factor C.  So therefore, the output size is a dense vector.  It's of size n.  So to simply output this vector already takes all of n computation.  So it's not going to be possible to achieve sublinear time on this graph.  And this would be the end of my talk, except I have to go deeper.  So fortunately, the real world graph does not look like this.  Real world graph looks like the one on the right side, where the degree distribution  follows power law.  So we are going to look at the power of these graphs.  More precisely, like pk to be the percentage of nodes that has degree k, then pk is going  to be proportional to k to the power minus gamma, where gamma is a power law exponent  larger than 1.  And what our algorithm does is that our algorithm PRC can achieve this following query time.  If you look at this, it's going to be related to the power exponent gamma.  But to make sense of this query time, let's look at the case where gamma is larger than  2 or equal to 2.  In this case, our query time only depends on log n.  So it's very much very, very sublinear log n.  And for this case, where gamma takes value from 1 and 2, which is usually the case for  most real world power graphs, the query time depends on n to the power 1 minus gamma or  n to the power 2 minus gamma minus 1, whichever is smaller.  If you take a close look at this, 1 over gamma is smaller than 1, since gamma is larger  than 1.  And 2 over gamma minus 1 is also smaller than 1, because again, gamma is larger than 1.  So in both case, this term is sublinear to n, which means our algorithm is sublinear  to the number of nodes.  And that's a good thing.  And this also gave us a hint that since our algorithm reversely depends on the value of  gamma, maybe some other algorithm, similar algorithm, also have long internet, reversely  depends on gamma.  And it turns out to be true at least empirically, because if you look at these two data sets  I mentioned before, they actually have very different gamma.  The IT has a much smaller gamma, and Twitter has a much larger gamma.  This might explain why these previous algorithms perform very differently on these two data  sets.  So next I will introduce a few highly-videos of how we can achieve sublinear time, a query  cost.  And the idea is very simple.  So given a source node, our algorithm PRC starts a random work.  And since it's a square root C work, it's going to terminate at some steps.  And instead of computing random works from each node and see how these random works meet  with these paths, we're going to reversely compute these so-called probability trees  from the node on this path.  And we are going to do this by probability tree.  I mean that we want to compute, let's say, the probability that node W visits node C  is 103 if you ignore the decay factor.  And we're going to compute such probability tree based on pre-computations and sampling  in an online fashion.  So with pre-computation, we can build an index.  But there is a problem of which node we should choose to compute index.  And there's actually a previous work by Xiao Kui that suggests to compute, pre-comput the  probability trees for all targeting nodes.  But this would result in a huge index size over the end over epsilon.  And it's going to be much larger than the graph size m if you want small epsilon.  So our method is that we only pre-compute the probability trees for hub nodes.  And by hub node, I mean node with high page ranks.  Why is that?  It's actually very simple because if you choose the source node randomly, then a random  work from a random source node is more likely to read the node with high page ranks because  that's the definition of page rank.  And therefore, pre-computing such probability trees for hub nodes is going to be reduced  the quality most efficiently.  And in the online phase, where we are supposed to compute these probability trees for non-hub  nodes, there's actually an algorithm called a probe algorithm that can do this.  And the idea is that suppose we want to sample, we want to sample the nodes at the step three,  for example, w with probability one third.  And what we do is that we sample node i with probability one, since there's only one edge  from i to c.  And then we sample g and k with probability also one because it only has what degree one.  And then we sample f with the probability one over three because it has three edges,  incoming edges, and one of them is connected to c, to i.  If we fail to sample f, then if we fail to sample f, then all these nodes under the subject  of f is going to disappear and we don't have to deal with that node.  Hence we can save a lot of time.  But this algorithm alone is not going to give us sublinear time because it's not efficient  for nodes with large degree, out-degris.  For example, if we want to sample the out-neighbor of this degree, this w, then we have to read  it, this all this node, before we can sample them.  So we propose this backward work algorithm which can only read a very small fraction  of the out-neighbor's every sample.  And the idea is very simple.  We sort the adjacency list by in-degree in the preprocessing phase.  And we saw a random number r from zero to one and we only read the number, the nodes  with in-degree smaller than one over.  For example, here the random number is 0.3, so we only read the nodes with degree less  than three.  In this case, we only read IGHKL and that's a very small fraction of the entire neighbor.  So with backward work algorithm, we can finally achieve sublinear time.  And for experiment, we compare our algorithm on five datasets.  One of them is actually very large.  It consists of five billion edges.  And we compare our algorithm with state-of-art competitors index-based or index-free-based.  And we use this pulling idea to evaluate precision on large graphs, even though we  don't have ground tools for single source queries.  And these are the trade-offs between the query time and the error and the precision of top  K queries.  And as you can see, our algorithm is this pink line.  And given the same amount of query time, we can achieve the smallest error and the highest  precision.  And for these are the trade-offs between the error and the index size and the error and  the pre-processing time.  We can also achieve the same amount of error using the smallest index size and the smallest  pre-processing time.  Finally, we did some experiment on synthetic datasets.  We generate a bunch of power-lobed datasets with different power-exploring gamma.  And we show that these all the similar hours indeed have a query time that is reversely  related to this gamma, which confirms our suspicion.  And we also did some experiment on random ER graphs, where we can see that our algorithm  performs best compared to the average degree, when we increase the average degree.  And this is due to the fact that with the backward work hours, we don't really have  to visit all the nodes, all the neighbors.  So in conclusion, we gave a sublinear time algorithm for single source similar queries  on power graphs.  And our algorithm outperforms the state of art on large graphs in terms of query time,  accuracy, index space, and pre-processing time.  And we empirically show that the hardness of similar computations depends on the power-lobed  exponents gamma, and for future work, this might be interesting if we can actually show  that mathematically, all similar hours is going to be depend on the power-exploring.  And that will be all.  Thank you.
Wei_He_Xiao_Wang_Liu_Du_Wen_0_143.png Wei_He_Xiao_Wang_Liu_Du_Wen_144_275.png Wei_He_Xiao_Wang_Liu_Du_Wen_276_371.png Wei_He_Xiao_Wang_Liu_Du_Wen_372_587.png Wei_He_Xiao_Wang_Liu_Du_Wen_588_647.png Wei_He_Xiao_Wang_Liu_Du_Wen_648_2243.png Wei_He_Xiao_Wang_Liu_Du_Wen_2244_5171.png Wei_He_Xiao_Wang_Liu_Du_Wen_5172_5351.png Wei_He_Xiao_Wang_Liu_Du_Wen_5352_5759.png Wei_He_Xiao_Wang_Liu_Du_Wen_5760_7367.png Wei_He_Xiao_Wang_Liu_Du_Wen_7368_8831.png Wei_He_Xiao_Wang_Liu_Du_Wen_8832_8891.png Wei_He_Xiao_Wang_Liu_Du_Wen_8892_10379.png Wei_He_Xiao_Wang_Liu_Du_Wen_10380_10547.png Wei_He_Xiao_Wang_Liu_Du_Wen_10548_11327.png Wei_He_Xiao_Wang_Liu_Du_Wen_11328_13319.png Wei_He_Xiao_Wang_Liu_Du_Wen_13320_13871.png Wei_He_Xiao_Wang_Liu_Du_Wen_13872_14027.png Wei_He_Xiao_Wang_Liu_Du_Wen_14028_14159.png Wei_He_Xiao_Wang_Liu_Du_Wen_14160_16907.png Wei_He_Xiao_Wang_Liu_Du_Wen_16908_20111.png Wei_He_Xiao_Wang_Liu_Du_Wen_20112_20783.png Wei_He_Xiao_Wang_Liu_Du_Wen_20784_22787.png Wei_He_Xiao_Wang_Liu_Du_Wen_22788_23747.png Wei_He_Xiao_Wang_Liu_Du_Wen_23748_23892.png
This is a joint work with Xiao Donghe who is my student, Xiao Kui Xiao from NUS, Si Bo Wang from CHK, and Yu Liu from PKU, and Xiao Yongdu and Jirong Wang from my university. I'm Zhe Weiwei. I'm a social professor at Remy University. So let's start with the problems and motivations. So we're interested in Simrank, which is a similarity measure between nodes in graphs based solely on the graph structures. So the idea of Simrank is very simple. A node is more similar to itself. So here the university is more similar to itself, and two nodes are similar if they are referenced by the same or similar objects. So the two professors are similar because they are referenced by the same university, and the two students are similar because they are referenced by similar professors. Simrank has this recursive definition, which essentially says the similarity between two nodes, u and v, is equal to 1 if u and v are the same nodes, and they are equal to the average of the similarities between the neighbors, in neighbors actually, times the defective factor c, where c takes value from 0 to 1, and c is usually 0.8 to 0.6. So we are going to look at Simrank at a different angle, which is the random work interpretation. So this is the square root c work, where at each step this random work terminates with probability 1 minus square root c, and move to a random enabler instead of an odd neighbor with probability square root c. So here c is just the defective factor I mentioned before. It takes value from 0 to 1. So what connects Simrank and the square root c work is that if we start two square root c works from u and v, and the Simrank similarity is just the probability that these two random works meet. By meeting, I mean they have the same node at the same steps. So if these two random works work like this, they both meet at node 8, but not on the same steps, so that doesn't count. This definition actually gives a very simple color algorithm for computing Simrank's of two nodes. That is, we can generate multiple pairs of square root c works, and count the percentage of pairs that meet at the same step, of course, and that percentage is going to be a good approximation of the similarity between u and v. But we are going to look a bit beyond this single pair problem, and we're going to consider single source and top k Simrank queries. That is, given a source node u, we want to compute the similarities between u and every other node in the graph. For top k queries, we want to return the top k most similar nodes to the given source node. We're going to allow an area of predetermined value epsilon, because it's generally very difficult to compute these values exactly. Single source Simrank queries have a lot of applications. For example, span detection, recommendation system, where you're supposed to find similar items to a given item and recommend to the user, and clustering, where you're supposed to find similar items and group them together. Because of its importance, it has been extensively studied for the past decades. And since obviously I don't have time to go through all this work, so let me just say this. They all suffer from two drawbacks. Most of all, they all take a linear query time, which is unexpected because you have n nodes and you have n similarities to report this. And some of these existing methods are random work-based. So what they do is they generate a bunch of random works from each node, and they compare this random work with the random work generated by the source node to see if they meet. And that way, the query time is the number of nodes times number of random works, which is a small number and it's not very scalable. For other methods that based on linear algebra, they also have to pay at least the number of nodes or number of edges. So the first question is, can we achieve sublinear query cost? Because we have an arrow that we can leap with. So the second drawback is that we don't yet understand the hardness of similar computations and graph structures. So take these two datasets as an example. They have similar number of nodes and they have similar number of edges. But if you run existing similar algorithms on these two datasets, you are going to get very different query times, even with the same parameter. So this means there's a lot of things going on in these two datasets that we don't fully understand. And there is a paper that says, OK, this may be caused by the data sets is locally dense and the IT data sets is locally sparse. So we really want quantifiable skin for this characterization for this phenomenon. So here are our results. First, can we achieve sublinear time on any graph? The short answer is no. Because if you look at the graph on the left side and you ask what are the similar nodes to node 1, then you are going to get that every node is similar to node 1. Because if you recall, the similarity of the node 1 and 4 is the random work probability from 1 and 4 that meet at the same steps. And if you start the random work from 1 and 4, they are going to meet at the central node, which means the similarity between them is the decay factor C. So therefore, the output size is a dense vector. It's of size n. So to simply output this vector already takes all of n computation. So it's not going to be possible to achieve sublinear time on this graph. And this would be the end of my talk, except I have to go deeper. So fortunately, the real world graph does not look like this. Real world graph looks like the one on the right side, where the degree distribution follows power law. So we are going to look at the power of these graphs. More precisely, like pk to be the percentage of nodes that has degree k, then pk is going to be proportional to k to the power minus gamma, where gamma is a power law exponent larger than 1. And what our algorithm does is that our algorithm PRC can achieve this following query time. If you look at this, it's going to be related to the power exponent gamma. But to make sense of this query time, let's look at the case where gamma is larger than 2 or equal to 2. In this case, our query time only depends on log n. So it's very much very, very sublinear log n. And for this case, where gamma takes value from 1 and 2, which is usually the case for most real world power graphs, the query time depends on n to the power 1 minus gamma or n to the power 2 minus gamma minus 1, whichever is smaller. If you take a close look at this, 1 over gamma is smaller than 1, since gamma is larger than 1. And 2 over gamma minus 1 is also smaller than 1, because again, gamma is larger than 1. So in both case, this term is sublinear to n, which means our algorithm is sublinear to the number of nodes. And that's a good thing. And this also gave us a hint that since our algorithm reversely depends on the value of gamma, maybe some other algorithm, similar algorithm, also have long internet, reversely depends on gamma. And it turns out to be true at least empirically, because if you look at these two data sets I mentioned before, they actually have very different gamma. The IT has a much smaller gamma, and Twitter has a much larger gamma. This might explain why these previous algorithms perform very differently on these two data sets. So next I will introduce a few highly-videos of how we can achieve sublinear time, a query cost. And the idea is very simple. So given a source node, our algorithm PRC starts a random work. And since it's a square root C work, it's going to terminate at some steps. And instead of computing random works from each node and see how these random works meet with these paths, we're going to reversely compute these so-called probability trees from the node on this path. And we are going to do this by probability tree. I mean that we want to compute, let's say, the probability that node W visits node C is 103 if you ignore the decay factor. And we're going to compute such probability tree based on pre-computations and sampling in an online fashion. So with pre-computation, we can build an index. But there is a problem of which node we should choose to compute index. And there's actually a previous work by Xiao Kui that suggests to compute, pre-comput the probability trees for all targeting nodes. But this would result in a huge index size over the end over epsilon. And it's going to be much larger than the graph size m if you want small epsilon. So our method is that we only pre-compute the probability trees for hub nodes. And by hub node, I mean node with high page ranks. Why is that? It's actually very simple because if you choose the source node randomly, then a random work from a random source node is more likely to read the node with high page ranks because that's the definition of page rank. And therefore, pre-computing such probability trees for hub nodes is going to be reduced the quality most efficiently. And in the online phase, where we are supposed to compute these probability trees for non-hub nodes, there's actually an algorithm called a probe algorithm that can do this. And the idea is that suppose we want to sample, we want to sample the nodes at the step three, for example, w with probability one third. And what we do is that we sample node i with probability one, since there's only one edge from i to c. And then we sample g and k with probability also one because it only has what degree one. And then we sample f with the probability one over three because it has three edges, incoming edges, and one of them is connected to c, to i. If we fail to sample f, then if we fail to sample f, then all these nodes under the subject of f is going to disappear and we don't have to deal with that node. Hence we can save a lot of time. But this algorithm alone is not going to give us sublinear time because it's not efficient for nodes with large degree, out-degris. For example, if we want to sample the out-neighbor of this degree, this w, then we have to read it, this all this node, before we can sample them. So we propose this backward work algorithm which can only read a very small fraction of the out-neighbor's every sample. And the idea is very simple. We sort the adjacency list by in-degree in the preprocessing phase. And we saw a random number r from zero to one and we only read the number, the nodes with in-degree smaller than one over. For example, here the random number is 0.3, so we only read the nodes with degree less than three. In this case, we only read IGHKL and that's a very small fraction of the entire neighbor. So with backward work algorithm, we can finally achieve sublinear time. And for experiment, we compare our algorithm on five datasets. One of them is actually very large. It consists of five billion edges. And we compare our algorithm with state-of-art competitors index-based or index-free-based. And we use this pulling idea to evaluate precision on large graphs, even though we don't have ground tools for single source queries. And these are the trade-offs between the query time and the error and the precision of top K queries. And as you can see, our algorithm is this pink line. And given the same amount of query time, we can achieve the smallest error and the highest precision. And for these are the trade-offs between the error and the index size and the error and the pre-processing time. We can also achieve the same amount of error using the smallest index size and the smallest pre-processing time. Finally, we did some experiment on synthetic datasets. We generate a bunch of power-lobed datasets with different power-exploring gamma. And we show that these all the similar hours indeed have a query time that is reversely related to this gamma, which confirms our suspicion. And we also did some experiment on random ER graphs, where we can see that our algorithm performs best compared to the average degree, when we increase the average degree. And this is due to the fact that with the backward work hours, we don't really have to visit all the nodes, all the neighbors. So in conclusion, we gave a sublinear time algorithm for single source similar queries on power graphs. And our algorithm outperforms the state of art on large graphs in terms of query time, accuracy, index space, and pre-processing time. And we empirically show that the hardness of similar computations depends on the power-lobed exponents gamma, and for future work, this might be interesting if we can actually show that mathematically, all similar hours is going to be depend on the power-exploring. And that will be all. Thank you.
similarity measure between nodes in graphs based between two nodes, u and v, is equal to 1 if u the average of the similarities between the queries have a lot of applications. For example, it has been extensively studied for the past from each node, and they compare this random work is the number of nodes times number of random scalable. For other methods that based on linear algebra, they also have to pay at least the number of nodes or number of edges. So the first as an example. They have similar number of nodes run existing similar algorithms on these two node, which means the similarity between them is achieve sublinear time on this graph. And this the one on the right side, where the degree distribution follows power law. So we are going graphs, the query time depends on n to the power term is sublinear to n, which means our algorithm time, a query cost. And the idea is very simple. efficiently. And in the online phase, where we smallest index size and the smallest pre-processing time. Finally, we did some power-exploring gamma. And we show that these all graphs. And our algorithm outperforms the state of art on large graphs in terms of query time, accuracy, index space, and pre-processing time.