Paul, we're going to talk about scalable graph algorithms in Rust.
Thank you.
Hello.
I am Martin.
I'm here with Paul.
And we talk about scalable graph algorithms in Rust and some Python.
Who are we?
We're both engineers at a company called Neo4j, and the J stands not for R, like Rust, unfortunately.
But we will talk about a little bit what we do in our day job, which is we work on a product
which is called Neo4j Graph Data Science, so Neo4j is a graph database.
Maybe you heard of it.
It's written in Java.
And the two of us, we work on a project called Graph Data Science, which is essentially a
plug-in for the Neo4j Graph Database.
And it provides a collection of graph and machine learning algorithms that we deploy
to our customers, and they use it for many different things, but like the top three
applications of these things are fraud detection, recommendation, and identity resolution.
And we have customers with up to 10 billion nodes and 65 billion relationship graphs that
they compute our algorithms on.
And you can find out more about the product and the source code is available online and
in the documentation, of course, if you follow those things.
Last week, we released version 2.3 of the Graph Data Science product, and what you can
see here is basically all the graph and machine learning algorithm that we provide to our
customers or users, ordered by some category, and some of them you probably know from university
like Dijkstra path searching algorithms or connect components algorithms.
Okay, but we are in the Rust step room, so why do we talk about Java?
So first of all, so Paul and I, we discovered Rust like two or three years ago, and we started
building like smaller tools, libraries, fell in love with the language, and we were curious
about how we can actually do what we do at work, like implementing those parallel algorithms
in Java, how good would they perform if we would do the same thing in Rust, and also
make a bit more use of what Rust has to offer.
And we had a quick look around.
There is only one graph library that is, I think, very popular, which is called PetGraph,
which is focusing on a network X replacement, and it focused on like single-threaded execution
of graph algorithms, basically textbook implementations.
So we thought we want to go like the step further and do like the parallel implementations
of the graph algorithms.
So that's how we started the project.
So we started in May 21.
First of all, it was an experiment, basically, or a hobby project by the two of us, where
we tried to figure out like what's the maximum performance we can get out of this implementation.
And then over time, yeah, we got more interest into the project, and we added some more implementations
of different algorithms, like it's not a lot, but you will see that later.
And we added some Python support that we will talk about in a demo.
We added an arrow server so that you can use this thing in a network, for example, and
everything is available on GitHub and MAT licensed.
The project itself contains or consists of five grades.
Today we will talk about three of those.
The one at the bottom is the graph builder, which is essentially the abstraction or data
structure that represents the in-memory graph that we use to compute on.
It's a CSR, compressed sparse row representation.
And it also has a builder API, hence the name, to allow users of this library to construct
graphs, either programmatically or from files.
On top of that, we have the actual graph grade.
And yes, the name was free on grades, I owe it wasn't actually free, but the owner wanted
to give it away anyway, so we took it, lucky us.
So yeah, this contains some algorithms, and then we have graph mate, which are our Python
bindings on top of the graph and the graph builder grades.
The servers, the arrow server, and the app is the CLI application that we won't talk
about today.
So let's start with the graph builder.
The graph builder is basically an API for building directed and undirected so-called
property graphs.
What you can see on the right-hand side is a undirected graph consisting of five nodes,
zero to four, which are connected by edges.
And they have no direction, hence the graph is undirected.
How do we construct such a graph?
So what we show here is the Rust API.
So the main entry point that you can see is the graph builder, which is this thing here.
And the graph builder is just authenticated, and you give it, you can call the edges function,
which takes, in this example, like we take an array of tuples where the first value is
the source node and the second value is the target node to describe essentially the graph
on the right-hand side.
We call build, and what we want to construct here is basically controlled by the type that
we assigned to the G variable, which is an undirected CSR graph.
So it's very similar to collect, where you can specify I want to collect into a vec or
a string or something like that.
Basically we use a type system here, which is very nice or expressive in comparison to
Java to basically define what the output of this function call is.
And we have this undirected CSR graph, which is a concrete implementation of a graph.
And the first, the type parameter we use here, U64, is basically the type for the node IDs.
And then once you have this constructed, you have several methods available, like the degree,
which is the number of edges that are connected to a node.
So the degree of node one is free because it's connected to zero, two, and three.
And you can get the neighbors of a specific node as an iterator.
And in this particular implementation, you can also turn this iterator into a slice,
which means you basically have zero copy if you want to access the neighborhood of a node,
which is very useful if you want to implement performant graph algorithms.
Now we want to turn this into a directed graph, which means now our edges have these
little arrows at the end, which means an edge has always a source node, or a source node
where it starts and an end node where it ends.
The only thing that we need to change here is basically the return type or the type of
our G variable, which is now a directed graph.
And we have additional methods.
We have the out degree, because now we have to differentiate between the outgoing edges
and the incoming edges, and the same for the out neighbors and the in neighbors.
What we can also do is, since we are talking about property graphs, which means we have
properties on nodes and also on edges, we can add node values as another builder method
or builder function.
Again an array, which is node count minus one length, where you basically provide the
node values that you want to add to your nodes.
It gives you an additional function called node value to access the value.
Similar for edge values, now you do basically a triple, where the third value is the relationship
value.
For example, here like the 0.1 for the edge between zero and zero and one, which is this
one.
All right.
And we get another method down here, it's the out neighbors with values, which in addition
to the target ID of this edge also gives you the relationship where the edge weight.
For convenience, we have this so-called GDL string that you can provide, GDL stands for
graph definition language, which is another crate that we wrote.
It's basically a subset of the Cypher query language, that is the main query language
of Neo4j, which allows you to declaratively describe the graph on the right-hand side
using sqr syntax.
So basically this in parenthesis n zero is node zero and this kind of JSON style map
here is the property map, like P1 for example, to describe node zero and an edge is expressed
by node zero where you can refer to a variable that you declared earlier and connect it to
another one called n1, which is this edge description and you can also provide properties
to this edge.
It's basically used for testing or for building like small POCs to play around, it's much
simpler than using the edges methods and so on.
But it's basically the same graph that we constructed before.
So as you can see, you can create those graphs programmatically if you use like the edges
method and so on.
The construction is also parallelized under the hood using rayon.
But the main use case is usually from reading graphs from files and we have a graph input
trade that you can implement.
We provide three implementations.
The most common one, especially if you want to start playing around, is using an edge
list, which is basically a text file where in each row you have a source and a target
and an optional value and graph 500 is a benchmark or a benchmark description specification
for HPC graph algorithm benchmarks and they also provide a data generator and we basically
can read the binary file format that this generator produces.
Like I said, everything as part of graph creation is parallelized using rayon and we will see
this in the demo in action.
The next grade I want to just mention briefly is the graph grade, which contains the parallel
graph algorithm implementations.
At the moment, it's these four, which we implemented in the first place to compare them to our
Java implementations.
So for example, PageRank, it's an algorithm to give like a population, popularity value
to a node.
It basically tells like if you traverse the graph randomly, like how likely is it that
you end up with that node, so it's kind of a popularity metric.
Connected components, Paul will talk a little bit about that in the demo.
Again, also the graph algorithms are parallelized using rayon and if you want to see more or
just open an issue or PR.
Just a quick Rust API where how we call this algorithm, so in the graph pre-loot, we also
provide like all the algorithm methods, for example, PageRank as you can see in the middle.
The first thing we do here, we have a GDL graph again.
It's the graph on the right-hand side without any properties.
We create a directed graph with a specific layout, which Paul will talk about and then
we call the PageRank method using that graph as a reference.
You can specify some parameters in the PageRank config, which are not that important right
now and the result are the scores, which are the values assigned to each node after the
computation is done.
And that's basically it.
Okay, over to Paul with GraphMate.
Yeah.
Hi, I'm Paul and I want to talk about GraphMate, which are our Python bindings over this set
of crates that Martin just talked about.
And we just had a wonderful talk about Python APIs on top of Rust and this is in the same
spirit.
So we want to expose a Python API for Rust implementations and we don't want to deal
with all the shortcomings in Python in terms of like proper parallelism and memory management.
We also integrate with NumPy and Pandas, which are de facto standard libraries in anything
Python.
It's very alpha, so it works and you can install it for a pip.
It's available on PyPy and I just want to run through a demo, which is a notebook.
And there we go.
So first we, I think I need to clip this on once again.
Okay, we configure some logging so we can see some outputs and we import typical Python
prelude.
We import our crates and as well as NumPy and Pandas.
And in this demo, we are loading a Graph 500 graph in particular scale 42 and Graph 500
describes it as you have your scale number, two to the power of the scale number of nodes
and 16 times as many relationships and this ends up in, so we load that file.
We also load a direct graph and it takes a few seconds and at the end we will get a
graph that says we have about 16 million, almost 17 million nodes and about 260 million
relationships.
And we are loading a direct graph, which means we have two sets of logging outputs that look
very similar because we do it once for the outgoing, once for the incoming direction.
And we also use the duplicated layout, which will merge parallel edges between the same
source and target node pair.
It will de-duplicate them and we only represent one of them in the graph.
And with that we can run PageRank.
So PageRank is a method on the graph object that we get and PageRank is an iterative algorithm.
It runs in a number of iterations and when it finds that the result is good enough, it
will stop and we can now access some metadata about the run.
So we see we ran eight iterations in about 1.3 seconds, but now we also want to access
the actual scores, the PageRank scores.
In the other slide that Martin showed, we store the scores in a WEC of F32 and we don't
want to copy that WEC into Python land, into the Python heap, convert the floating point
numbers into Python numbers.
So we are interfacing with the C API from NumPy and we return an array view that points
to that WEC.
So when you call scores, there's no copying involved.
We return you a NumPy array that directly accesses the data and there's nothing to be
copied in the Python heap or anywhere else.
And you can use that array, it's a proper NumPy array and you can use that for example
to put it into a partner's data frame and then do some calculations based on that.
The numbers here don't really mean anything in particular, it's just for demonstration.
And the next algorithm you want to run is WCC, which stands for weekly connected components.
So it basically identifies components within a graph.
Every node that is connected together is one component and we run that, it takes about
200 milliseconds, we're still running on the same graph.
And similar to PageRank, we can access the data here and the data is an array where for
every position in that array for that node ID, it's the component ID, so every node
that is together in the same component will have the same component ID in that array.
And we can use a pandas method here, drop duplicates, which will give us all the unique
components IDs so we can identify the number of components here.
And so we see, we are down from 16 million something something nodes down to almost eight
million unique components.
And yeah, that is WCC and for the last thing we want to count the total number of triangles
in the graph.
A triangle is defined as a connection between three nodes from A to B to Z back to A.
And for that, first we need to convert the graph into an undirected graph.
There's a method there.
And it'll take a little while, a few seconds, because it's creating a new graph.
We have to basically merge those two out and in lists together, we produce a new graph
and since it's a new API, a new type in Rust, we also return it as a new graph.
Which means if we, if we're low on memory, we can delete references to the old graph,
we don't need that anymore.
There's a particular optimization for triangle counting that makes it not be super slow,
which we call make degree audit.
I don't really want to go into details what it's actually doing, but it's, let me just
run triangle counting here.
It makes it so that triangle count finishes within a minute, not within five minutes.
And that optimization only takes like one and a half seconds.
At the bottom, you can see the H-top output, so you can see that it's actually using all
the cores and proper parallelism without any typical Python shenanigans that you need
to do to avoid the GIL and so on.
And we don't have to watch it finish.
We can go back to the presentation.
This is a summary of the demonstration that we just went through.
We don't need to look at it anymore.
Once in our repository, we have three variations of the demonstration.
We have the first one in Python that we just showed.
We have another one using the Rust API and the third one using the arrow server that
Martin mentioned, where there's a Python client, but it's not using the library directly.
It's using arrow and arrow flight to communicate with the server and doing it remotely.
I mean, if you're interested in those demos, you can follow those QR code links at the
end.
And I think by now, triangle counting should be done.
So we took about a minute and it found 10 billion triangles.
If I count it correctly, it seems, yeah, it seems it way.
So that is for the demonstration.
Now we can look back a little bit and talk about the lessons learned, particularly for
us coming from the JVM world.
And so using Rust as a Java developer, first of all, the way the Rust paradigms require
us to think differently about the code and allow us to think differently about the code.
Things like using the type system to define whether or not we have indirect or undirect
the graph.
And this is, of course, very nice and very refreshing coming from a Java world.
But also, we have a better mechanical sympathy for what happens.
We don't have to think about this JVM black box where things go through before they touch
the hardware.
Ecosystem cargo, Rust analyzer is very, very nice.
But also, of course, there are some downsides to it.
We don't have that experience of just clicking a fancy button in the IDE to run a debug or
a profiler.
We have to actually learn different tools and do things the proper way, I guess.
Yeah, but what about performance?
We talked about what we want to do in a performance way.
And for every algorithm that we have implemented, we are faster and less memory-intensive than
the Java implementations.
It's not just about that.
It's also predictable behavior.
No latency spikes, no allocation rates, no cheat compiler that does things in the back.
And just quickly showing what we want to do from the future, of course, expanding all
the things.
And if you want to play around with it, feel welcome and open issues.
There's also a longer version of this talk because I'm already out of time, so thank
you.
We don't have time for all of this.