RedisGraph Adopts GraphBLAS Sparse Matrix Math to Cut Query Latency

RedisGraph采用GraphBLAS稀疏矩阵数学计算大幅降低查询延迟 将openCypher查询转换为半环上的稀疏矩阵运算，消除了串行逐节点指针遍历，减少了CPU缓存抖动，并在数毫秒内完成复杂搜索。 本演讲介绍了RedisGraph通过集成SuiteSparse:GraphBLAS实现的架构转型。传统图引擎通过串行、深度优先的指针追踪来处理遍历，这常常导致CPU缓存失效并产生随机内存访问开销。通过将图拓扑重新构建为稀疏邻接矩阵，并将图运算映射到自定义代数半环上，该引擎将包括多跳过滤和变长路径在内的查询执行为经过优化的矩阵与矩阵、矩阵与向量乘法。Tim Davis解释了GraphBLAS的内部工作机制（包括掩码、惰性求值以及诸如zombies和pending tuples等更新机制），而Roi Lipman则展示了openCypher查询如何编译为结合律矩阵链，从而在拥有数百万条边的图上显著降低延迟。 RedisGraph采用SuiteSparse:GraphBLAS将Cypher查询直接映射为稀疏邻接矩阵上的线性代数运算。 (26:05) 稀疏矩阵克服了二次方内存瓶颈，使像拥有20亿用户的Facebook网络这样的现实世界图谱能够追踪非零关系，而无需分配数万亿个空单元格。 (2:35) GraphBLAS使用可自定义的半环对线性代数进行推广，将标准矩阵乘法转换为广度优先搜索和最短路径等算法。 (3:38) 在包含100万个节点、300万条边的数据集基准测试中，RedisGraph在50毫秒内完成了全量邻居发现，并在1毫秒内完成了100个目标的BFS遍历。 (31:58)

[0:00] all right hello everyone my name is Li [0:06] Lippmann I work at Redis labs and I've [0:11] been working for the past almost two [0:14] years on Redis graph and this talk is [0:19] about matrices or JSON C matrices and [0:24] linear algebra and how we can use these [0:27] ideas within graph databases so just to [0:31] make sure that everybody here is on the [0:33] same page let's give a formal definition [0:36] of what a graph is so a graph basically [0:40] is just a set of nodes where each node [0:44] basically can represent some entity and [0:48] a set of edges connecting those nodes [0:50] where each edge can represent some [0:53] relation so take for example Facebook [0:56] where nodes basically represents users [0:59] and edges represents friendship [1:02] connections between those users and so [1:07] once you have a graph you have couple of [1:12] options of how you would store that [1:14] graph within memory or on disk [1:17] so there are non traditional or non [1:21] formal ways that would be using tables [1:25] like sequel tables or JSON documents [1:28] like the one has to store graphs [1:32] obviously those structures were not [1:35] meant to store graphs but you can use [1:38] them to hold your graphs and there are [1:41] those for always like adjacency list and [1:45] adjacency matrix this talk will focus on [1:49] adjacency matrices and so the idea [1:54] behind an adjacency matrix is that you [1:57] have this matrix where the rows and the [2:00] columns basically represents your notes [2:02] so row I can represent node with ID I [2:06] and column J will represent node J [2:12] if node i is connected to no j than the [2:16] entry within row I column J would have a [2:19] 1 in it otherwise a 0 at some entry IJ [2:26] would tell you that note I is not [2:30] connected to node J and so if we try to [2:35] create such an adjacency matrix and try [2:39] to keep it size to a minimum we will use [2:42] a 1 bit entry for yeah we will use 1 bit [2:46] for every entry and so to perform matrix [2:53] operations like addition or [2:55] multiplication we can use bitwise [2:58] operation and that's really great [3:01] because bitwise operations are really [3:05] fast the only problem with that is for [3:09] us to have a graph with 1 million nodes [3:13] this will take a matrix with 1 million [3:18] rows and 1 million columns summing up to [3:22] 125 gigabytes of space which basically [3:27] kills the idea of using matrices to [3:29] represent graphs luckily for us real [3:35] graphs are sparse and by sparse I mean [3:38] that the number of own entries entries [3:42] where the value is nonzero is relatively [3:45] small to the number of entries within [3:51] that matrix so take for example Facebook [3:54] Facebook has roughly about 2 billion [3:57] users each user has an average number of [4:01] 338 friends so if we're looking at the [4:06] friendship matrix of Facebook we will [4:09] only have 2 billion times 338 nonzero [4:14] entries out of 2 billion raised to the [4:17] power of 2 so the matrix utilization is [4:20] really slim [4:23] and so we would like to use what is [4:26] known as a sparse matrix to represent [4:28] that type of graph and the idea behind [4:31] sparse matrix is that we're only keeping [4:34] track over the nonzero values so for [4:38] example if we worried the matrix at [4:41] position I column J the IJ entry and we [4:45] see that this position is not tracked we [4:49] can immediately conclude that the value [4:52] of that entry is 0 and so graph class is [4:58] a software library which allows you to [5:00] perform matrix operation on sparse [5:03] matrices and like I would like to [5:05] welcome to the stage Professor Tim Davis [5:07] to talk to you about graph class well [5:11] thank you Roy appreciate the invitation [5:13] to come and talk with you all about this [5:17] so this is graph plus graph Blas I gave [5:20] a really short intro to this at the [5:22] keynote it's a community led effort [5:24] there are people involved in this with [5:26] from academia from government labs I'm [5:29] working closely with MIT link Lincoln [5:31] lab at MIT IBM Intel is involved with [5:35] this and what it is it's a it's a [5:39] community driven effort to to exploit a [5:42] kiva key observation that's been made [5:45] actually quite a while back the idea of [5:48] this close connection between graph [5:50] algorithms and linear algebra and if you [5:54] just take matrix computations and you [5:56] say ok well I'm not going to do an ad [5:58] I'm not going to multiply I'm gonna rip [6:00] that out I'm gonna put in another [6:02] operator like a min operator instead of [6:05] the plus and I'll put a plus instead of [6:08] the times operator and I'll multiply [6:11] these two matrices together or matrix [6:13] and a vector and I get a shortest path [6:15] in a graph bellman-ford or a minimum [6:18] spanning tree connecting the components [6:20] breadth-first search that first well def [6:23] for search is tricky I didn't say that [6:25] there's there's I'm working on it [6:28] there's lots of algorithms that can be [6:32] recast as matrix operations and then the [6:35] beauty of this [6:36] is that then you get all of the [6:38] beautiful power and expressiveness of [6:40] linear algebra and and you get the same [6:43] time complexity as well so here's an [6:46] example breadth-first search you're at [6:50] you walk through the the graph one level [6:52] at a time you started a source node four [6:54] you want to know what nodes can you [6:56] reach and how far away in terms of [6:57] number of edges are they from the from [6:59] the source node well in a conventional [7:01] breadth-first search if you code this up [7:02] and you say a graph library perhaps or [7:05] create your own graph data structure [7:08] you'd have to write code that walks [7:10] across every node in the current level [7:12] for every edge do something check [7:14] something is it in the if you've seen it [7:15] before oh you haven't and so what you're [7:17] doing here in this middle iteration of [7:20] this breadth first search is you're [7:21] you're looking at your neighbors and [7:23] you're deciding [7:24] let's form a set Union of the neighbors [7:26] I have not yet seen so there's an if [7:27] condition in that test turns out you can [7:30] then recast this in a matrix vector [7:31] multiply using a different semi ring in [7:34] this case it's the boolean some semi [7:36] ring or you rip out the multiply and you [7:38] put in an and you rip out the or and you [7:40] put in a I'm sorry rip out the add you [7:42] put in a or and then the zero now is [7:45] false so zero can change as well and the [7:47] min plus semi ring that the zero is is [7:50] plus infinity the number that's not [7:52] there is called the additive identity of [7:54] the mono of the semi ring for which [7:56] we're working with basically it's the [7:58] number that X plus zero gives you X [8:00] whatever the plus operator is if it's x [8:02] then it's x times one is X is the is the [8:05] value that you that's not there that you [8:08] don't have to store in the matrix so [8:11] here I've got depicted a matrix vector [8:13] multiply in which you can say let's take [8:17] the the column which is the center the [8:20] one here that's not highlighted and the [8:23] dots are zeros just to make it easier to [8:25] see and the the the non zeros in that [8:29] column or one in three it so you pick [8:31] out those one third first and third [8:33] column or them together and you get that [8:35] output column in red which is the nodes [8:38] two four and six oh but we want to take [8:41] out node four so that's a mask operator [8:44] that that that is a bulk if operator [8:46] that tells us which we will work on so [8:49] the advantage of this [8:50] replace a conventional graph algorithm [8:53] at walking across nodes and edges kind [8:55] of low-level stuff with higher-level [8:57] more expressive things that then a user [8:59] doesn't have to worry about the [9:00] low-level details just code up in a [9:02] higher level API and then that gives me [9:05] the library writer a lot of scope for [9:07] optimization yeah I can I can take your [9:10] request and graph Blas has a notion of [9:12] non blocking mode you can say oh you can [9:14] say as a user hey oh do this and do this [9:17] and call this and call this and I'll say [9:19] oh that's nice thank you very much thank [9:20] you thank you I'm not gonna do this I'm [9:22] lazy and then when you're ready to do [9:25] something I can't be lazy about it it's [9:27] like oh I better go back and do all this [9:28] work but see I've I've got a bulk of [9:31] work now that I can I can do as a group [9:33] as a large collection and I can do this [9:36] as much as I like because the data [9:37] structure is opaque to the to the to the [9:39] user through the API and that gives me a [9:42] lot of scope for for instance if we [9:44] decide hey you got a GPO oh cool I'll [9:46] run it all I'll call CUDA blah [9:48] kukuku sparse and run run that under the [9:51] hood but the API stays the same it could [9:55] be parallel it could be distributed and [9:57] let us handle the performance and then [10:00] we give to you the user this beautiful [10:02] composable language like like to think [10:05] of a MATLAB for graphs okay where you [10:07] can do associate it distributed you can [10:09] do the product of two matrices transpose [10:12] is the part transposed reverse product [10:14] and such so that's the idea of graph [10:17] algorithms in the language of linear [10:19] algebra you've a time matrix [10:21] multiplication on a semi ring and I [10:23] guess I've already explained some of [10:24] these points already I've gotten ahead [10:26] of myself where you these matrices are [10:30] adjacency matrices of graphs and they're [10:32] stored in a sparse format and with note [10:35] with a zeros or not are not present this [10:39] is a community effort I'm not I'm the [10:41] one who've written this code so about [10:43] its efforts gone back about ten years [10:45] five years ago they started to put this [10:46] API together a year ago they asked me to [10:48] write the code for it and which I did [10:51] and it's now in Linux distros Debian and [10:55] Ubuntu and it's it's starting to find [10:57] some use so I'm going to talk to you [11:00] about how its implemented and what kind [11:02] of performance side I get out of it [11:04] so this gives us powerful way of [11:09] expressing graph algorithms these large [11:12] bulk operations no need to chase nodes [11:14] and edges the linear algebra with some [11:17] rings as composable lower software [11:20] complexity the user code is a lot [11:21] simpler and let us write the the graph [11:26] core graph kernels and it it's a very [11:28] simple object and closed under mat these [11:31] mathematical operations as well it's [11:33] just a sparse anything matrix [11:35] in fact there's user-defined matrix [11:37] types if you want a scalar to be a 4x4 [11:40] matrix and a string why not well you [11:44] just tell me what operators you can give [11:46] me the operator and I'll call your [11:48] operator to do your add or you multiply [11:50] or whatever that might mean on that [11:52] datatype graph plots for instance [11:54] doesn't have complex matrices in it took [11:57] me five hundred lines of code to add it [11:58] that's not part of graph plus not even [12:01] have to be meaning to recompile graph [12:02] laws and it does that so it's very [12:05] simple mathematically well-defined in [12:08] the performance right now it's just [12:10] serial but I'm looking towards parallel [12:12] and GPU computing to be able to make [12:14] this still go faster so I want to show [12:16] you an example of breadth-first search [12:17] so here's here's some code and I live VI [12:20] so it's in vim colored and this is a [12:23] complete breadth-first search in graph [12:25] blas and it almost no longer looks like [12:28] c but it is and so you it basically [12:33] creates the takes in a graph a matrix [12:36] takes in a source node and it's going to [12:39] return a whoops a oops push the wrong [12:42] button not to click or not to it's going [12:44] to return a vector of the levels of each [12:48] node that can be reached and that would [12:50] be a sparse vector because you may not [12:52] be able to reach the whole graph so it [12:55] just walks across the level and each [12:57] level of the search [12:58] there's just three things to do there's [12:59] no chasing of nodes or edges in here at [13:01] all there's no loop that says for every [13:04] node do this for every neighborhood do [13:06] this so here's how this works start do [13:08] with this matrix on the right and [13:12] there's the representation on the left [13:14] and I've drawn it so that the columns [13:16] are the adjacency lists [13:17] and yes I do use a Jason's List [13:20] internally every column here so for in [13:22] some for instance column for asked [13:24] connections to call it two nodes one in [13:27] three so the first and third entry in [13:29] column four here are none are non zero [13:33] are true so it's a binary matrix and so [13:37] the initialization in pseudo MATLAB [13:39] notation here just creates a empty [13:41] vector V and I the the current node the [13:45] current vector Q which tells you the [13:47] nodes in the current level it's true or [13:49] false true if you're in the level false [13:51] if you're not and so the source node is [13:53] set to true and so there's the outcome [13:55] and then then this is a mask assignment [14:00] so it's like an if test it says well if [14:03] you're in the current level set your [14:04] level this doesn't take order n time it [14:07] only operates on time proportional to [14:09] number of non-zeros in the mask so it's [14:11] very nth very efficient and then here's [14:14] two steps of this matrix vector multiply [14:16] broken into two slides the first one is [14:18] to do the matrix vector multiply and so [14:21] this is this is multiplying this one [14:23] vector QQ times the graph a to get this [14:26] vector T which is your neighbors know [14:28] the neighbors have nodes 1 & 3 is [14:30] neighbors of node 4 is just one in three [14:33] and then then here's the mask operation [14:36] that says well only do this for nodes [14:38] that are haven't been seen yet well this [14:40] is everybody so no one's no one's turned [14:41] off so this process continues and so [14:44] here for instance there's the matrix [14:46] vector multiply but then the mask turns [14:49] knopf node four because node four here [14:52] has been has been seen in its assignment [14:55] as two-level one has been made already [14:56] and so that's one line of see to call [15:00] that matrix vector multiply with the the [15:03] mask being V and the descriptor telling [15:05] you to invert the mask because it's to [15:07] make sure it's not been seen and so on [15:10] the the the process continues until [15:12] finally it decides that okay I've [15:14] searched at the very last there's [15:15] nothing it finds a bunch of neighbors of [15:17] the last node but they're all searched [15:18] so the graph is the vector is empty and [15:21] then the code terminates the kinds of [15:24] things you can do in graph Blas here on [15:27] the Left I get the amount lab analogs of [15:31] matrix multiplication element-wise you [15:33] can add two graphs together where they [15:35] add operators anything you like and then [15:37] you have a the the result is the set [15:39] Union in terms of the structure you can [15:42] do a set wise intersection or a dot star [15:44] in MATLAB equivalent you can do [15:47] reductions on a graph [15:48] apply unary operators transposes all of [15:51] this work is is is equally I wrote the [15:53] sparse matrix multiply in MATLAB and [15:56] also wrote backslash I've written a lot [15:58] of codes for the math works that they [15:59] use internally and for other companies [16:01] so this these codes are fast they're [16:04] just as fast as what I did for the math [16:06] works inside MATLAB but Mallett only has [16:08] four matrix multiplications real times [16:10] real complex times complex times I'm [16:13] complex and so forth just with [16:15] typecasting is just for graph baz built [16:17] in can do 1.3 million different variants [16:20] including typecasting if you don't [16:22] include typecasting it's 960 different [16:25] summer rings that are built into the [16:26] package and you can then make up your [16:27] make up your own your own operators that [16:30] dough like you want to set the parent of [16:32] a tree whenever this something happens [16:34] that could be part of your multiply [16:36] function all those things can be done [16:38] and all these are just as fast as as a [16:41] as a highly-tuned matrix matrix multiply [16:46] different objects it's got that you can [16:49] create you can you can use built-in [16:50] types or predefined types you can create [16:53] operators create Manos which is like the [16:55] additive entity you can create that then [16:58] the semi-ring vectors and matrices and [17:00] the descriptor which is a parameter [17:01] setting and all these are opaque so i [17:04] can very easily then say if i say hey i [17:07] need to add a new descriptor i can do [17:09] that without breaking the current api is [17:11] there's a lot of thought going into [17:12] making this in Upper compatible as we [17:16] add features to this to this API [17:20] internally my matrices are stored and [17:22] compressed sparse column form that's [17:23] because that's what I do for MATLAB and [17:26] then this non-blocking mode I've told [17:28] you about the matrix can have pending [17:30] operations as well and how much time [17:33] should i target is about five minutes [17:35] left I guess for me yeah so these are [17:39] this is the notation on the far right [17:42] corner of how we write how we [17:45] these operations mathematically where [17:48] you can do things like the first line as [17:51] a matrix-matrix multiply well it's a [17:53] major to make just multiply across the [17:54] semi-ring but it's also got an [17:55] accumulator operator like plus you could [17:57] say say C equals C plus a times B for [18:00] instance oh but there's a mask that says [18:02] oh wait no no don't touch those entries [18:04] only touch these because that's the bulk [18:07] if that says this is important that I [18:09] don't do stuff I've already done or only [18:11] want to change certain parts and that [18:14] mask can be very sparse so for example [18:16] the cool thing is what if you do a [18:17] matrix multiply but you really want one [18:19] number well I know how to do that I can [18:21] just compute the one number I don't have [18:22] to compute the whole matrix multiply and [18:24] oh this looks like NQ work no it's like [18:27] constant time or something like that [18:29] it's extremely fast to compute these [18:32] kinds of things if you can exploit the [18:34] structure some of the things that [18:38] internally are I want to give you an [18:41] insight into sorts of things that have [18:43] to be done to make this fast [18:45] sub matrix or sub graph of Simon you've [18:47] got this huge graph and you want to say [18:49] to those 10,000 nodes no you don't have [18:52] that graph you've got this graph instead [18:54] sub graph so in in in matrix notation in [18:58] MATLAB you could write this CIJ equals a [19:00] and IJ then are the vectors of the rows [19:02] and columns you're wanting to modify [19:04] it's a very difficult function for was [19:07] difficult one for me to implement I [19:09] don't know it's several thousands of [19:11] lines of code it modifies the matrix in [19:13] place but this is costly to do to tweak [19:17] a dis data structure one tweak at a time [19:20] so I have a notion in the data structure [19:22] of zombies and pending tuples zombies [19:25] are things that are dead but they're [19:27] still there they're edges that have been [19:29] marked for deletion but they haven't [19:31] been deleted yet because if I did it [19:33] would I'd have to massage my entire data [19:35] structure and that's costly so I'm going [19:37] to leave the dead bodies lying around [19:38] and I call them zombies because they can [19:41] come back to life because if you [19:42] reassigned to them they just pop back in [19:44] and no worse for wear and the zombies [19:48] also helped quite a bit for binary [19:49] search with my adjacency list that's [19:51] sorted if I do a deletion in the middle [19:54] and I've got a hole there well then I [19:55] can that zombie is there to tell me [19:58] where to do the buying [19:58] research I just have it flagged but I [20:01] can then still have it sorted pending [20:03] tuples are object are edges that are [20:05] pending to be added to the graph that [20:08] are not yet in the graph data the main [20:10] part of the data structure so I have [20:12] basically a hierarchy of data structures [20:15] what this means is you can do this on [20:17] the top side in in graph Blas very [20:20] efficiently just iterate through you can [20:23] create a whole list of non-zeros [20:24] build them all at once and in MATLAB you [20:26] can do the same thing just as fast so [20:29] I'm about as fast as MATLAB can do this [20:33] but I can also build a graph [20:35] incrementally you build a graph and they [20:37] say toss in an entry toss in a hundred [20:39] entries toss in a thousand entries I can [20:42] do this [20:42] on the top is see it almost looks like [20:45] MATLAB and down the bottom if you were [20:47] to try to do this in MATLAB you'd be [20:48] four here for a day to try build a [20:50] matrix that's that's big it's way too [20:52] slow so as a result this sub matrix [20:54] performance even though without this [20:57] time at the bottom that's without me [21:00] cheating this is per this is without [21:02] exploiting the non blocking mode this [21:04] sub matrix assignment is a hundred times [21:07] faster than what MATLAB can can do so [21:10] it's a very efficient implementation of [21:12] these graph algorithms so to summarise [21:15] graph algorithms in the language of [21:17] linear algebra sparse anything matrices [21:19] including user-defined types it's you [21:23] can redefine matrix operations across [21:25] the semi-ring things like linear algebra [21:29] can be can be exploited then as a result [21:31] all your nice beautiful elegant linear [21:34] algebra tricks of associativity and [21:37] distributive laws and it's got this [21:40] really nice feature of accumulator mask [21:43] combination that you can act as a bulk [21:46] if statement which graph algorithms [21:48] often have to do walk across a graph and [21:50] do something or not depending on what [21:52] they see and the performance all these [21:54] many that most these operations are just [21:56] as fast as MATLAB some of them are [21:59] hundreds of times faster and I don't [22:02] think very many of them are very much [22:03] slower maybe 20% but you didn't hear [22:06] that the code is already available it's [22:10] it's highly robust [22:12] bug-free and I don't say that lightly as [22:18] far as I know it's bug free I mean I [22:20] that's what I that's that's what I do i [22:22] write bug-free code it's it's in Linux [22:26] Debian Ubuntu and and Mac homebrew so [22:30] back to Roy all right [22:40] so before we'll see how Redis graph is [22:43] using graph blasts I wanted to just show [22:47] you how the old version of Redis graph [22:50] and other graph databases are actually [22:53] executing a given query so the query [22:56] that we'll be looking at is one of the [22:59] most popular graph queries out there [23:03] we're trying to find friends of friends [23:06] and this query specifically is looking [23:09] at every person in the graph who is over [23:13] 30 years old and we're interested in [23:16] finding their friends of friends [23:18] all right so given that query the old [23:23] version of Redis graph will compose an [23:27] execution plan specifically for this [23:30] query the execution plans begins with an [23:33] index scan followed by an X an expansion [23:38] or traversal follow another expansion [23:41] and finally projection meaning taking [23:43] the result and adding it to the final [23:46] result set so let's see the actual [23:49] execution of this plan so the index [23:54] scans tell us oh look I found a person [23:57] his his ID is ID number 5 and he is over [24:01] 30 so ID number 30 is advanced to the [24:08] first expansion expansion and so we're [24:12] looking at the friends of person number [24:14] 5 and the expansion tells us that number [24:18] 5 is connected to person number 2 and so [24:21] we're moving on to the next step with [24:24] person number 2 [24:26] this time the expansion will find us [24:29] friends of friends so looking at person [24:31] number two we can see that it is [24:33] connected to person with ID number nine [24:36] and we want to have that person within [24:39] our result set so nine gets promoted [24:42] into the projection step and then we're [24:46] backtracking we're going back to the [24:49] expansion because it might be so that [24:52] person number two has additional friends [24:54] in this case we can see that person [24:57] number two is also friends with person [24:59] number one so number one is a friend of [25:02] a friend of person number five the one [25:04] that we've started traversing from and [25:07] so one is also added into the result set [25:10] and so once again we're backtracking and [25:13] in that case we can see that we have [25:16] traverse all the friends of person [25:18] number two so that operation is depleted [25:22] backtracking once again number five [25:25] doesn't have any additional friends so [25:27] that operation is depleted backtracking [25:30] back to the index scan and we're giving [25:33] a new ID and this process basically it [25:36] repeats itself a couple of problems with [25:39] this module as you have seen it is [25:42] serial another problem is that there's a [25:45] lot of random memory access so we're all [25:48] the time in violating the CPU cache and [25:53] lastly the discovery of the result set [25:57] or the traversal of the graph is [25:59] performed one node at the time and so [26:05] we're using graph class in order to [26:08] improve all of these operations [26:12] basically because Reddy's graph is using [26:16] open cipher or cipher as its primary [26:19] query language we needed a way of [26:22] translating queries in cipher into [26:25] linear algebra expressions so take for [26:28] example the query that we've just ran [26:31] we're translating it into a linear [26:35] algebra expression in this case once [26:38] again we're in [26:39] in finding friends of friends of people [26:42] who are over 30 and so we will have a [26:45] filter matrix filtering out all of the [26:48] people within the graph who are younger [26:51] than 30 and then we will multiply that [26:55] matrix by the friendship matrix [26:59] multiplied by itself because we're [27:01] interested in performing two hops so [27:05] this is the graph that we'll be [27:07] demonstrating on and these are the [27:10] matrices the age filter matrix tells us [27:14] that person number 2 3 & 4 [27:16] and also person number 6 there they are [27:20] all over 30 and the friendship matrix [27:24] basically represents the graph that we [27:26] have just seen and we need to evaluate [27:29] this expression we need to perform those [27:31] multiplications but we must recall that [27:35] matrix multiplication is an associative [27:37] operation meaning that we can decide [27:41] which of the terms we would like to [27:44] multiply first we can start by [27:46] multiplying a times B or we can start by [27:50] multiplying B times C and we would like [27:54] basically to reduce the number of [27:57] nonzero values with each intermediate [28:01] multiplication as each nonzero values [28:04] not only takes memory but it also takes [28:07] CPU time when performing multiplication [28:11] as we need to consider each of these [28:13] nonzero values so if we start by [28:15] multiplying the friendship matrix by [28:18] itself we're ending up with 18 nonzero [28:21] values but if we start by multiplying [28:24] the age filter matrix with the [28:26] friendship matrix then we're left off [28:29] with only 7 nonzero values and this [28:32] makes sense because we're basically [28:34] reducing the number of persons we would [28:37] like to consider and so we're performing [28:40] the multiplication we're adding with a [28:43] result matrix let's call it f Oh a [28:45] friend of a friend and let's validate [28:48] that indeed the result is what we're [28:51] expecting [28:51] and so let's look at the bottom line of [28:55] the bottom row of the matrix which [28:57] represent node number six and we can see [29:01] that node number six the matrix tells us [29:03] that it is connected with node number [29:06] three and it also connects with node [29:08] number five and we can see that indeed [29:10] from node number six we can do to help [29:13] traversal in order to reach both node [29:16] number 3 and node number five the first [29:21] row and the fifth row of the matrix is [29:24] all zeroed out and this is because both [29:28] person number one and person number five [29:30] are younger than 30 so we don't want to [29:33] consider them another query which I [29:37] would like to review is a query which [29:41] does a variety we're interested in [29:45] finding friends of friends but this time [29:47] the number of hops is within some range [29:52] so for example I'm interested in friends [29:54] of friends who are two hop three hops [29:57] and four hops away from me this query is [30:00] not supported on the old version of [30:03] Freddie's graph as it was not simple to [30:05] introduce it with the current execution [30:10] model but in the language of linear [30:13] algebra this becomes really simple the [30:16] idea is for each variable length we're [30:19] taking the friendship matrix and raising [30:22] that matrix to the number of hops so in [30:26] this example we're raising the [30:28] friendship matrix to the power of two [30:30] three and four and we're adding it up [30:33] all together and what we're doing by [30:35] adding matrices were basically taking [30:38] graphs different graphs and we're [30:40] merging them together lastly we're [30:43] multiplying that result with the age [30:46] filter in order to consider only those [30:49] persons who are over 30 so let's see an [30:53] example the example only considered two [30:55] and three hops away because if we're [30:57] introduced four hops away then we can [30:59] reach every node within the graph so [31:02] performing their multiplication and [31:03] let's do a quick [31:05] datian for node number six we can see [31:09] that we can reach node number one and [31:11] indeed from six we can go to two from [31:14] two we can go to three and from three we [31:17] can reach number one this is three hops [31:19] away we can also reach node number three [31:23] with two hops going from 6 to 2 for 2 to [31:26] 3 5 is also reachable and 6 itself is [31:31] also reachable by traversing from 6 to 2 [31:36] 2 to 3 and the final hop back from 3 to [31:40] 6 [31:41] so far we've dealt with traversal but we [31:46] can also use matrices in linear algebra [31:48] to perform connected components we can [31:52] do shortest paths and we can also find [31:55] minimum spanning trees a little bit [31:58] about graph distribution is this is a [32:00] major issue within the graph database [32:03] world so we have a number of models of [32:06] how we can distribute a graph but if we [32:09] wanted to distribute the actual [32:12] traversal the actual multiplication what [32:15] we can do is think about matrix [32:17] multiplication not as one row times a [32:21] column but we can think about matrix [32:23] multiplication as blocks multiplication [32:27] what we're doing basically is taking a [32:29] matrix and divided it into several [32:32] blocks and then what we can do in order [32:35] to compute for example block c1 within [32:40] the resulting C matrix this is the [32:44] computation that we need to do and the [32:47] idea is that each block can be computed [32:50] on a different thread or on a different [32:53] server and then we simply gather all the [32:56] results back polarization so because [33:03] matrix multiplication is associative [33:05] suppose that we have a long expression [33:08] where we have a number of multiplication [33:11] needed to be computed then we can take [33:14] each individual computation it's [33:16] individual multiplication [33:18] and compute that in parallel maybe on [33:22] the same machine or on different servers [33:24] in addition the actual multiplication [33:28] operation can be parallelized [33:31] because of how matrix multiplication is [33:33] defined lastly let's have a quick look [33:36] at some benchmarks that we've ran all of [33:40] the benchmarks were ran on a graph with [33:42] over 1 million nodes and about 3 million [33:46] edges the first one deals with massive [33:49] insertion so importing a graph into the [33:53] new version of Redis graph takes about [33:55] half a second read operations so finding [34:04] all of the neighbors for every node [34:07] within the graph we're able to reach the [34:13] performance of 50 millisecond [34:17] similarly finding each source and [34:21] destination node for every given edge we [34:25] were able to do that also within 50 [34:28] milliseconds if you think about it this [34:30] is simply just returning the matrix all [34:33] the information required by this [34:35] benchmark is found within a single [34:37] matrix so it becomes really easy and [34:39] fast to perform and lastly finding the [34:43] shortest path from a given node to 100 [34:47] runs really big note so basically we're [34:49] performing performing BFS and we were [34:52] able to do that [34:53] within one millisecond thank you [35:02] I'm questions to me or 14 yes thank you [35:14] okay so graph plus is very cool actually [35:18] so again I like it I am a network [35:22] scientist myself so if I knew of this [35:26] library before I would have use it but [35:29] what type of higher level algorithms do [35:33] you have implemented like for example we [35:35] do a lot of community detection cake [35:38] leaks and stuff like that that I mean I [35:40] guess that if everybody has to figure [35:42] out how to do it with basic algebra to [35:45] be complicated right right it would be [35:47] so we're working on that I've got I've [35:50] got Luby's method for finding maximal [35:52] independent sets [35:53] I've got triangle counting so you want [35:56] you've got a graph you want to find how [35:57] many triangles are in the ground I've [35:58] got a kay truss algorithm that says I've [36:01] got a graph and I want to remove any [36:04] edge that's not in a triangle so you get [36:07] a commute you clusters of communities [36:09] you know the fortress is delete any edge [36:12] that's not in two triangles so you end [36:14] up with highly only just the highly [36:16] connected components of parts of the [36:18] graph I've got those let's see have a [36:21] breadth-first search there's a [36:24] betweenness centrality code that i [36:27] that's been written i have it looks [36:30] correct I haven't tested it on my graph [36:32] blas cuz and I know other people are [36:34] writing graph blahs algorithms in fact [36:36] they've written these before there was [36:37] an implementation so there's a [36:39] betweenness centrality metric written [36:41] it's about a I think maybe 50 lines of [36:44] graph plaus maybe a hundred at most so [36:48] yeah well that's a that's our next step [36:51] is to ask the question can i what [36:55] algorithms kind of right and then how [36:57] fast are they if you compare the the [36:59] algorithm you can write in graph plaus [37:00] with what you can do with an expert [37:06] writing it from scratch what's the [37:08] difference and I've done that for a [37:09] couple ones like the triangle counting [37:11] one it's I can I could be if I was [37:14] clever without graph Blasi two to three [37:17] times faster because I know I I can [37:19] discard computations as I'm building and [37:21] just count otherwise I have to compute [37:23] the matrix and then reduce it to a [37:24] scalar but for the triangle counting one [37:27] if I pull out all the stops I've got so [37:29] I've got graph plus I've got like four [37:30] or five lines of graphed laws and then [37:32] I've got fifth I've got maybe a hundred [37:34] or so plus lines of just pure C code and [37:37] if it pull out all the stops and exploit [37:39] everything I can do everything I know to [37:41] make it go as fast as this expert can [37:44] make go fast I can beat myself by 20% so [37:49] that's I bet I'm happy about because of [37:52] course I can be faster than than a API [37:54] but I can't write it faster okay and [37:58] another question do you plan to have all [38:02] the contributions from the community [38:04] like you know centralized place so that [38:07] it's sort of easy because otherwise it [38:09] gets really hard - yeah I know the [38:11] pieces and put together and have like a [38:13] general API like I don't know I care for [38:15] Network X in Python they have look like [38:16] those libraries that are pretty [38:18] beautiful so yeah so that's a good [38:20] question I I write most of so this whole [38:23] package I wrote myself a lot of my codes [38:25] I just write myself pick his own I don't [38:28] know trust of the people to not [38:31] introduce bugs in my code I don't know I [38:33] however so including features into graph [38:38] falls under the hood that that I'm not [38:41] sure about if I can do that with with [38:43] the public but having a a suite of [38:48] algorithms written on top of graph laws [38:51] that use graph laws that say hey this is [38:53] yours betweenness centrality hey here's [38:54] a Google Pagerank hey you know those [38:57] that would be really cool to to have a a [39:00] site where those kinds of solutions can [39:03] be posted yeah I I would really be keen [39:05] on that because then I'm not I'm not [39:06] vouching for them correctness it just [39:08] there's an example it'd be like a stack [39:10] overflow all right if it works for you [39:13] great you know it's just not been [39:14] validated and verified and hammered and [39:16] pounded on like like I would do it [39:19] inside you know my robust package so yes [39:23] I would I'm very keen I very interested [39:25] in doing that I don't have that yet [39:27] you know maybe a github something or [39:30] other it might be a good way of doing it [39:31] I have to think about how how I can do [39:32] that but that's yeah that's a great [39:34] thing to think about I've not done it [39:36] yet but all right suggestion [39:38] thank you next question just wanted to [39:47] ask you a question around I mean a [39:49] little bit about the history of this [39:51] library in the sense that I'm very [39:53] curious because when you show the first [39:54] example you know how to do breadth first [39:59] yeah yes I mean it's what they teach you [40:02] in computer science 101 right yes it [40:04] teaches you about matrix multiplication [40:06] Utley now right right [40:07] so you apply two different so why is had [40:10] no one thought about this before I know [40:12] it sounds like a oh that's a great [40:14] question that's a great question why is [40:16] no one thought it's before people have [40:18] been thinking about this for a while [40:19] it's going back at least more than 10 [40:22] years there's a book from Siam on graph [40:25] algorithms in the language of linear [40:27] algebra and they explain the linear [40:28] algebra how all this can be done but [40:30] there was no API there there's no [40:31] library there that said okay this is how [40:33] we would write these codes that book is [40:36] about 10 years old there's a community [40:38] there's been workshops there's been [40:39] conferences all without any code feel [40:43] five years ago they started to create [40:44] the API like ok this time to actually [40:47] make this happen because people are [40:48] doing pieces of it but not we need to [40:53] now generalize it make these approaches [40:55] available to the world in a cleanly [40:59] well-designed mathematically closed API [41:02] and that just finished a year ago that [41:04] they finish the API and so yes it's it's [41:09] it's been kind of rumbling for a long [41:11] time but but the actual get down to [41:13] brass tacks specified down to the last [41:16] jot and tiddle an API that's only been [41:18] recently done but but yeah the [41:23] observation mathematically has been [41:25] observed for a long time and I don't [41:27] know people have tried it they've tried [41:29] like a sparse blahs you know but then [41:31] they're people thinking in terms of of [41:32] finite element matrices linear systems [41:36] like I think they are not thinking of [41:37] just pure graphs with these semi rings [41:39] and so but these [41:40] people are and so that it's a it's a [41:42] combination of two communities basically [41:43] that have finally come together and to [41:46] do this so do we have time for another [41:48] question we've got negative 50 seconds [41:53] we started late so can we go over a few [41:57] minutes thank you [41:58] we have a non-circular relationship [42:03] between nodes so you know a graph that [42:06] doesn't point back to it to its own [42:08] nodes right so that's that's one set of [42:13] data and then we have another set of [42:14] data that we store our properties of the [42:18] nodes as sets so what I'm hoping for is [42:21] to be able to do a query of descendants [42:24] of node where you know they have this [42:28] property and do a set intersection right [42:32] now what I've done with the graph is [42:34] I've kind of expanded it into a ton of [42:37] sites essentially which is highly [42:39] redundant mm-hmm and it's it's fast it's [42:42] it's an you know standard Redis and it [42:45] works it's just you know eating up my [42:47] memory and I'm trying to figure out you [42:52] know trade-off between performance and [42:54] memory can I expect graphs to interact [42:59] with sets you know in unions and [43:02] intersections well you've done some [43:05] playing around with that I'm sure yeah [43:07] well I'm not sure about your [43:11] implementation but basically Redis graph [43:16] has a similar notion where the matrices [43:19] themself only refer to the node IDs and [43:23] so once you have some intermediate [43:29] matrix after done doing some [43:31] multiplication and traversal and you [43:34] need some access to the actual [43:36] properties you wouldn't have any [43:38] alternative but given some ID let me [43:42] look up the set where the actual [43:45] attributes of that node are stored and I [43:48] can retrieve those attributes and [43:53] continue computation on them for example [43:57] if we are if you are doing filtering [44:00] like please give me please consider all [44:04] the nodes with age over 30 then what I [44:07] would suggest is using an index and so [44:11] the idea behind the new version of Redis [44:14] graph is that indices will simply be [44:18] either vectors or matrices and then what [44:23] I can do is simply given some vector [44:28] which has 1 in it for every node which [44:33] specified some criteria all I need to do [44:36] is multiply that vector or matrix by [44:39] some relation matrix and then I'm only [44:41] focusing on the nodes which applies to [44:45] that criteria I hope I meant to answer [44:49] your question and you can also to add to [44:52] that you can also define usually any [44:54] user-defined type you like in graph plus [44:56] so I could have a sparse anything vector [44:58] where your anything is your node [45:00] attributes I could do that the only [45:02] constraint for for my for graph Plaza's [45:05] that the user defined type is a fixed [45:06] size for all types so it can't be like a [45:10] variable length string it can't be some [45:12] malloc bunch of pointer kind of data [45:15] structure but that's the next thing [45:17] that's actually in the next step in [45:18] graft law is to have the type be any any [45:21] object that can be current with a [45:23] constructor destructor kind of kind of [45:25] thing we've we've not gone there yet the [45:27] API and and we I mean we because I only [45:30] wrote the code I didn't design the API [45:32] and there's a lot more people involved [45:35] in the API dozens of people and a [45:38] five-person committee to create the API [45:41] so a lot of thought has gone into that [45:43] to make it make it make that pure and [45:46] simple but that's one thought we're [45:49] thinking of to be able to allow for that [45:50] kind of variable data type so I would [45:53] like to thank dr. Tim and Roy for the [45:57] session thank you so much thank you very [45:59] much [46:00] you