Thank you so very much for joining the session today. So this talk is a tiger's guide to Dungeons and Dragons. I have no idea what expectation you have. And I'm really surprised that so many of you showed up.

And I'm really glad, actually. Let's get started with a brief introduction of myself. And this slide is normally what I call a short summary of myself in logos. I'm a researcher, a data scientist. I've been working in academia for many years. Now I am DevRel in Anaconda. And I'm also a fellow of the Sophosis and Ability Institute.

That's the serious part of myself, the nerdy, geeky part of myself. I am into Python quite a lot. I actually help organizing many conferences, Europe SciPy, which, by the way, is in Basel in a couple of weeks. Python Italy, PyData events, also PyMagic gathering, Dungeons and Dragons.

So this is where I am. I couldn't wear my Darth Vader mask to come, but I have my... to compensate. And that's it. So this is where I am. Sorry. So let's get started. And let's start by saying that we have a D&D problem.

And in particular, let's say we have... We're about to embark in this mission. We are a mage. We have to fight this green dragon, hidden in this ancient castle. And in particular, the mission we are about to embark is that we have to find this dragon and slay the dragon, poor dragon.

And... but we've been empowered by an extra set of skills. We know that we have to cross this path. We have to go through this maze. We have the map. We have to essentially find a way to reach the dragon, which is hiding in the forest, and cast a fireball.

Sorry, this is very nerdy language, I know. But... and in case you haven't noticed, this map is essentially Prague Castle. So we did have, indeed, a D&D problem in Prague. So going back, seriously, what we have to do is essentially finding a way very efficiently.

This is the extra skills we've been gathered by this ancient potion, Pythonic. To go through this maze in a very efficient way, and so find a way into the forest. And also, so maybe the shortest way to get to the dragon, and essentially cast a spell.

And the spell has been... so this area here is actually the forest. So the royal garden, I gather, from the map. So we want to increase the power of our magic, and by...

So we want to find exactly the spot in which we want to cast our magic, increasing the effect. So in other terms, talking algorithms now, what we probably want to do is something like shortest path to reach the dragon.

This is technically referred to as SSP, single source shortest path. We probably want to do some travers of the maids. This is a very confusing name. Technically, it's historically called breadth-first search, even though sometimes it's just moving through the graph,

there's no search necessarily, to maximize viable effect. And we can think of many, many other algorithms. This is just an excuse to talk about graphs. And the following slides are essentially taken from this wonderful talk.

I absolutely recommend it from Guy Rose. And in case, when I mentioned... please take a picture, this is really fantastic. The talk is called D&D and graph databases. He's talking about graph databases.

I am not, but I've been borrowed some of his slides. And in case when I said graph, this is what you had in mind, you're still in time to probably go to another talk, because this is not what we're going to talk about. So talking about graphs, graphs are identified by vertices,

and these vertices, or sometimes edges, can be, sorry, nodes, can be connected by edges or arcs. The technology changes in literature depending on whether these connections are directed or not. I'll get to that.

But you can have isolated nodes or connected nodes. If every single node is reachable, the graph is said to be connected. If essentially you have this subgraph here is also referred to as fully connected graph,

because there's always a path from each node. As I was saying, graph can be undirected or can be directed, meaning that you have a direction to follow when you're moving from one node to another one. And the last thing to say, a couple of more things to say.

Sometimes we can talk about degrees of nodes. This is a property of nodes. You can have, if the graph is directed, like in this case, you have inbound degree, so the number of edges getting into the node, in this case is one, and you have degree of three, meaning, in this case, meaning you have two outbound degree in this node and one inbound.

The out degree, of course, is how many edges are actually starting from the node. And just to be clear, when you're dealing with graph, anything can be connected to anything. So you can always have situations like this. And situations can even be more complicated.

Anyway, enough with theory, I promise. And also because we still have our D&D problem. And we were saying that what we want to do is to look for shortest path or breadth-first search. This is just an excuse to talk about these two algorithms specifically.

Now let's talk briefly about graph abstractions in Python. And to be clear, this is a very interesting problem, at least to what I define interesting. There's a lot of theory behind it, and it's certainly not a three-way problem for many reasons.

Pythonically, this is an old page of documentation, and there's a Python pattern to implement graphs. So it's still in the legacy set of the documentation, but it's a very interesting read. So in the following slides, we try to think or reason together.

And please feel free to, I don't know, provide your own comment on what we're going to say about what we can do in Python to implement a graph. We can start by adjacency lists. So we have a set of nodes from 0 to 7 in this case, and then we present our graph N as a list of other lists.

And each list has essentially the nodes that each node is connected to. This is pretty easy. We can do slightly better in case every single connection has a weight or a value, whatever you want to call it,

we can have an adjacency dictionary. So it's a list of dictionaries, every single essentially. Reference for each node is a dictionary containing the node as a key and the value, and the weight as value.

We can even have a more flexible approach. This is still on the Python basic data structure. This is what I'm talking about. You can have a graph, and in the previous implementation, we're considering, was considering nodes as numbers. We can have labels on each node, so it's not necessarily numbers. So this is a more general approach. We have a dictionary in which each key is the label to the node, and the list of corresponding reachable nodes.

Even better, we can do same obstruction, but this time we use a set. The difference in what I'm trying to say here, the multiple implementation, and this is still a very basic idea we can come up with,

can vary depending on what you want to do with graphs. So this is the kind of message I'm trying to get across. Depending on what you have to do with the graph, implementation may vary. So when you have sets, for example, and you're looking for specific, you're adding a node,

you're absolutely sure that you won't have repetitions. So this is one feature you have immediately for the data structure you have. So this is the kind of thing we're trying to think about here. Another probably quite popular representation, obstruction for a graph, is adjacency matrix.

In this case, we don't bother in storing just the piece of information related to every single node. We store everything. And in case there's no connection, we can have a zero here, meaning there's no connection from this node to this other node.

And if we have weights, for example, or any information on the node, we can put directly numbers. So either than zero, one to indicate something like there is a connection, there is no connection. We can actually do numbers. And in case the graph is undirected, this matrix is essentially symmetric.

So we can store just the triangular matrix, so we don't need to store everything. In case you're not entirely familiar with this representation, this is a simple graph. We have the multiple nodes, we have weights, or the edges here, and the matrix will be symmetric.

The row in this matrix represents the outgoing edges, and the column for this node represents the inbound edges. It has to be said that apart from standard Python, we do have alternatives.

And probably you know already where I'm going. Graph can be represented as a sparse adjacency matrix, and indeed SciPy as a sparse package. And in this particular case, it's even more clear that depending on what you need to do with your representation,

you have to choose carefully what sparse implementation you want to use. So SciPy, this is all a sparse matrix class in SciPy, so you have multiple formats, multiple strategies to implement sparsity. And in fact, in the documentation, you can say that if you need to construct a matrix efficiently,

you will probably want to do list of lists, which is LIL, by the way. List of lists, in case you're missing this, this is exactly what we're talking here. This is the list of lists, nothing different. Or you can use coordinate format here.

But this is strongly discouraged to use NumPy directly on this format, you have to convert them first. In case you need to perform manipulations such as inversions, operations, algebraic operations, there's another format. This is a comma separated column sparse row or something like that, sorry, I don't remember exactly.

Just to be clear, this is what Scikit-learn supports internally. So whenever you have sparse data, you can pass on matrices in this format, because this is the format where you can use arithmetic operations, as you would do in machine learning.

And if you will have to convert this format into another format, like COO, for example, it's linear time. So it really depends on what you have to do. No format is always perfect, and you have to choose carefully. And when you have to do both the two things, you have to convert from one format to the other.

And of course, probably the best solution we have in Python is using data abstractions. And NetworkX is the package we want to use when we work with graphs. This is the implementation of graph in NetworkX.

And there's also digraph, which is directed graph, multigraph, multidi-graph, and so on and so forth. So NetworkX already provides abstractions in Python to work with graphs. Are you all familiar with NetworkX? Fantastic. So I guess from the audience, half of you. So when you're dealing with a graph, you have nodes and edges automatically,

and you have methods to add nodes and edges directly. So it's very easy to work with, and it's very Pythonic. So you have a very fantastic abstraction, so you don't have to worry about the internals. NetworkX is working everything for you. Fine. What are the pros of NetworkX?

Well, it's a reference implementation in Python. It's very well-known and popular if you work in graphs. Many algorithms already provide it, and it's well-documented, and it's a nice read. And it's great for small graphs. What's the cons, though? It's quite slow. It's very slow. And in particular, if you compare performance here, this graph and the other kind of graph,

sorry, probably is not entirely readable. The green line here is the sci-fi sparse. The blue one is NetworkX, and the red one is NumPy. So sci-fi sparse is certainly faster at increasing the size of the graph,

but NetworkX is certainly not the slowest. It is slower than NumPy up until some point, because NumPy diverges because NumPy doesn't have any notion of sparsity. So NumPy stores everything in memory.

So that's where the difference comes from. But nonetheless, NetworkX is certainly slow, and you can't actually use it. For small graphs. So what if we would still be using NetworkX and all the advantages of using NetworkX? Because NetworkX, again, provides abstractions, very easy to use from Python,

and algorithms already implemented. We don't have to implement any will. But we can still have NetworkX pros retaining all the pros, but having a faster sparse graph algorithms. In particular, what we're looking for is a foundational sparse graphs library

that is fast, flexible, scalable, and runs on any architecture. To be completely clear, sci-fi also provides a package within the sparse package, which is a CS graph. You have already, so the sparse matrices I told you earlier,

they do come with algorithms already, so they're not just like data structures. You can also do graph operations on them. So this notion of using sparse matrices for graph problems is still, is indeed a very practical case.

So you have connected component, shorter spout, the breadth, the sorta, essentially the same algorithms we're talking here. The problem is, and I'll tell you immediately, cypher-sparse is not that library. It's not the library we're looking for. Cyper-sparse is still too slow for what we're talking about. It's single-threaded, first off, and it's not expressive enough.

We don't have masking operations that work efficiently. We cannot change operator in matrix multiplication, and I come back to that in a second, what I mean here. And it's too low level. You have no integration with NetworkX. There's no way you can have the two talking to each other.

And also has some what is technically called format gymnastic. So you have to work out different formats to work with it. So depending on what you're doing, CSR rather than COO. And last but not least, is not yet hardware or implementation agnostic.

Okay, so let's think about this. Graph problems can indeed be expressed as sparse linear algebra problem. And I probably convinced you enough already that sparse matrices are the actually way to go

for representing a graph, especially when it's sparse. And so with these in mind, let me introduce you a very new project I came up with, I came across with recently. It's called GraphBlast. So GraphBlast is exactly what you can imagine it to be.

It's just BLAST, but for graphs. BLAST is basically an algebra program. So GraphBlast is indeed a BLAST version for sparse matrices. In this particular case, graphs are presented of course as sparse matrices, and the matrix multiplication is the foundational tool to graph operations.

And in particular, everything is expressed as matrix multiplication with the caveat that we can customize the operator. So I'm not going to go into any details, I would be happy to do it after the talk, but whenever you have to, for example, express a single source shortest path,

when you're doing matrix multiplication, you can replace, you can use min plus as the two operators to use during matrix multiplication. It's very convoluted, I'm not going to go much more into details than this, but happy to later on. So just to give you an example,

when you have to process incoming edges, you can use sparse matrix times sparse vector. When you have to process outgoing edges, it could be sparse vector times sparse matrix, and this is exactly what you get. To be entirely clear, GraphBlast is not a library. It is a standard. So it's a specification similar to Blas,

and so you have the other architecture here, Blas or GraphBlast, and then you have some lay graph or graph analytical apps building on top of it. So this is the full stack we're talking here, and so how do we transition from GraphBlast to NetworkX? It is very possible. GraphBlast is the map specification.

There exists the C API of GraphBlast. Then there is the suit-sparse GraphBlast C implementation, and to be clear, this specification was created, as far as I know, as a library to support sparse matrix operations in MATLAB.

This is where this comes from. While we're talking here, and that's why I'm presenting this to the Europe Python audience, is because you can use this library in Python as well, and there's Python GraphBlast and GraphBlast algorithms, which connect ultimately to NetworkX via dispatching,

and I'll talk about it in a second. So, more in details, having this NetworkX connection, essentially through GraphBlast algorithms and Python GraphBlast, we can target even multiple architectures. So you have abstractions working on top, and depending on what is your architecture here,

you can have CPU, you can have Dask arrays, you can have GPU, you can also plug in cool graph, which goes directly to GPU and Dask, so NetworkX has this advantage through the dispatching method. So, looking internally at the stack, so GraphBlast is a pseudocode.

It's just the map specification. This is what we're talking here. The C specification is this level of details, and there is an implementation to this specification called SootSparseGraphBlast, and as I was saying, Matlab uses it for sparse matrix multiplication, and it's based on OpenMP for parallel operation, and every single format we mentioned before

is supported in this implementation. Python GraphBlast is a project which is currently an open-source project. You can install it via PIP or Conda in CondaForge, jointly developed by some of my colleagues, Jim McKitchen at Anaconda and Eric Welch at NVIDIA,

and it essentially provides a Pythonic implementation to the C specification. GraphBlast algorithm is, so this is, in some sense, the low-level Python here. This is the general algorithms,

similar to the NetworkX algorithms, so these are the algorithms that essentially implemented the plug to NetworkX. Currently implemented more than 80 algorithms, but the project is open-source, and please provide a pull request if you have algorithms that you can't find there and you want them to implement. They will be more than happy to do it.

And NetworkX finally is on top, so you can call it, as you would normally do, on your graph, and thanks to the dispatching method, it goes down here using GraphBlast. I'll show you an example in a second. This is how the dispatching works.

So NetworkX provide some of the methods, for example, shortest path. They do have a decorator, which is nx.dispatch. If those methods have this decorator in place, it means that the dispatching method for that algorithm is available, and so NetworkX automatically figures out whatever is the library that should be called underneath.

So just to give you a concrete example here, we're using, sorry, this is a typo here, but we're generating a random graph with a very low probability of connectivity, so it's a very sparse, 10,000 nodes, and this is, oh, sorry, this has been updated, sorry.

I should have played this slide. It's 10,000 nodes and more edges, apparently. Sorry about that. If we try to list all the pairs shortest path in that graph, NetworkX way, it takes 32 seconds.

We have to slightly adjust our code to use GraphBlast algorithms. We just have to import GraphBlast here. We do convert the NetworkX graph to GraphBlast NetworkX graph through utility function included in GraphBlast algorithm, and we pass to NetworkX method directly the GBLS graph,

so nothing changes but the input of the graph. So the conversion takes more or less 8,400 milliseconds on my laptop, and the whole execution here takes 3.4 seconds, 10 times faster.

There's actually a benchmark of all the, changing the sizes, the change in different graph, and changing also the algorithms, comparing using NetworkX as a baseline, and so GraphBlast versus NetworkX, and also a speed-up against iGraph, and if you're working with graph,

iGraph is probably one of the most popular library available nowadays for network analysis. So to briefly recap what we're talking about, GraphBlast API specification at the bottom of this stack SootSparse GraphBlast is a C++ OpenMP implementation. Python SootSparse GraphBlast is what is in the middle.

CFFI plus CITEN. Python GraphBlast is pure Python. GraphBlast algorithm is pure Python and provides connection to NetworkX. Multiple formats are supported. Highly tuned matrix multiplication kernels,

and you have no import or copy lag, and GPU support is forthcoming. So key messages. DDD is very cool. NetworkX is amazing, even if it's slow. GraphBlast uses sparse linear algebra to solve graph problems, mathematically elegant and blazing fast.

If you're interested in all the very details of that, I would be happy to talk about it. NetworkX can become the graph API for Python similar to what NumPy does, because at the end of the day, we have a fantastic API which goes very slow, so essentially, NetworkX says, I can demand the workload to whoever goes faster than I do.

And that's all I had. Thank you very much. Thanks for the amazing talk, Valerio. If you want to ask any question, you can use the mic.

I know lunch is coming. Go ahead. Hello. Hi. So first question, what is your favorite D&D class and why is it a wizard? I know. Yeah. I've always been a wizard.

Yeah, that makes sense. Thanks for the question. Yeah, but I also have another question. So in the example you have showcased, you have created a dense graph for your NetworkX and then converted it to sparse. Is there any way for this GraphBlast on the Python layer to load a sparse graph directly from disk or whatever?

So you mean loading the graph in NetworkX from disk? Not in NetworkX, because NetworkX deals in the dense format by default, but in the GraphBlast Python library. Oh, yes, yes, yes.

So the example I had was like showcasing how you can use NetworkX algorithms directly. So this is why I went through NetworkX. But you can use GraphBlast entirely using their API. What is happening here? I was trying to think if I had examples.

I had a few backup slides, but not what you had in mind. Yeah, yeah. So in this case, essentially I'm just using this graph algorithm's utility conversion from NetworkX. And you can also convert it the other way, so from NetworkX to GraphBlast in case.

And this is graph algorithms. Python GraphBlast, which is what is underneath in the stack, has their own data types, metrics and vectors. So you can use them directly to represent the graph. You can do that. It's just a lower level. So probably you would go, it's preferably going from NetworkX

because you already have the algorithms, but it's not necessarily the only way, if that's what you meant. Yeah, OK. I meant is it possible to entirely deal in sparse graphs without having a dense graph as an intermediate step.

Yes, exactly. So Python GraphBlast only talks sparse graph. And that's a very good question. That's exactly a very good question. Because if you're not dealing with a sparse graph, GraphBlast at the end of the day is no different in performance than what NetworkX is. When you're using this sort of breach, it's the same performance.

You start appreciating the performance when you have sparsity in your graph. Yes, that's a very good question. One question that have some cases when still iGraph is better than this one?

We can look at the performance, actually. This is, so for example, page rank works better on this particular networks. I have no specific clues about this benchmarks, but these data sets and these results are public.

And core devs are very lovely people. So if you're very interested in that, you can, there's an old section. I can remember there's an old issue in the graph algorithms repository talking about this benchmark. So i can probably send you the link. I should have put the link there.

I can add the link maybe when i share the slides. Thank you. No worries. Thank you very much. Hello. Hi. One question on the need for dispatching to NetworkX. Sure. I mean, if the algorithms are getting reimplemented, at least 80 plus of them are reimplemented in the Python package,

then what advantage does it bring us to dispatch them to NetworkX again? You don't dispatch back to NetworkX. You dispatch from NetworkX. So what I mean is, this is what happens. So if you, so essentially graph algorithms

has a similar interface, the single source shortest path, then NetworkX does. And what you do, from the top level, you just use NetworkX. And this being dispatched internally to graph plus, because the G type here is a graph plus algorithm, sorry, yes, it's a graph plus graph data structure.

So NetworkX knows exactly how it works. I had a slide, i forgot to add it, in how the dispatching method works internally. So i can't, it's difficult to explain with that example,

but i promise you, this too are interconnected automatically. You don't have to do anything. What changes here in this internal implementation is that it uses python graph plus Rather than networkx implementation. And this is the kind of code we're talking about.

This is python graph plus. So, for example, the single Source shortest path, even if it's barely unreadable, sorry About that, this is the whole implementation of the operation. It's very compact, and it's very, it should be easier to Read, but it's very compact. So you really have to

Understand, that's why graph algorithms on top exist. This works because of how graph plus works. So transforming using the min plus, semi-ring, blah, blah, Blah. This is very, very detail. But this is python graph plus code.

Abstracted from graph plus algorithms. I have a quick follow-up question. So, say i'm using, i'm an end user, i need abc Algorithms on graph. I can just stop at the graph Plus python layer, right? You can. You can.

It means that you're essentially, yes, you can. You can totally can. The thing is, you can go back And forth, networkx. And if your program already Runs on networkx, you can plug in with just two lines of

Code, graph plus. This is probably a good way to Explain it. So it's totally true what you Said, as in, you can use graph plus algorithms on their Own without going through networkx at all. But if you were going through networkx, you can Speed up your code by just adding these two lines.

Thanks. Thank you.