(Covid-19) Contact tracing - an amazing graph problem & rabbit hole

In the past couple of days, I have been working with several of my colleagues on a number of projects, all around the world, that are preparing our societies for a post-lockdown strategy that will allow us to keep the Covid-19 pandemic under control, and still regain some of our freedoms. This will be tricky, for sure, but as in so many problems, technology can probably assist.

That's why I started experimenting with how a graph database like Neo4j could help with this. Some of the tracing problems that we will face, are uniquely well suited for a graph database approach: it allows for us to see and understand the indirect contacts that healthy and sick people may have had with one another, and the effects that this could cause in our environments. It also allows for some unique predictive analytics: the structure of our contacts, the network/graph that it constructs, actually says a lot about the importance that parts of the network may play in the evolution of the pandemic. Graph Data Science can give us pointers as to where this should direct our policies.

This has ended up being quite an extensive piece of work. In order to keep it readable, I have cut it up into 4 blogposts, which I will put up all at the same time:

• Part 1: how I go about creating a synthetic dataset, and import that into Neo4j
• Part 2: how I can start running some interesting queries on the dataset, making me understand some of the interesting data points in there and questions that one might ask
• Part 3: how I can use graph data science on this dataset, and understand some of the predictive metrics like pagerank, betweenness and use community detection to direct policies
• Part 4: a number of loose ends that I touched on during my exploration - but surely did not exhaust. 

There's so much potential in this dataset, and in this problem domain in general. I feel like I have gone into the rabbit hole and have just resurfaced for some air. But who knows, maybe I will dive back in and do some more digging - after all, this is interesting stuff, and I love working on interesting topics.

Hope this is as interesting for you as it was for me.

All the best

Rik

Note that these demos will require the following environment: 

• Neo4j Desktop 1.2.7, Neo4j Enteprise 3.5.17, apoc 3.5.0.9, gds 1.1.0, or
• Neo4j Desktop 1.2.7, Neo4j Enterprise 4.0.3, apoc 4.0.0.6 (NOT later! a bug in apoc.coll.max/apoc.coll.min needs to be resolved)

(Covid-19) Contact Tracing Blogpost - part 4/4

Part 4/4: Some loose ends for the Contact Tracing graph

In this last part of this blogpost series, I wanted to quickly articulate some interesting points that I found useful during these experiments.

Using the geospatial data for some additional insights

You may remember that back in part 1, I imported some geospatial properties into our graph - assigning coordinates to all of the Places nodes that we have in the graph. Clearly this also opens up further possibilities for additional analysis, which I have not explored yet in the previous posts. Suffice to say that this data is super easy to work with in Neo4j. Just run a query like this:

match (pl:Place) return pl.id, pl.name, pl.type, pl.location limit 10;

And you can see that the pl.location property has a real geospatial data type that I can use:

(Covid-19) Contact Tracing Blogpost - part 3/4

Part 3/4: Graph Analytics on the contact tracing graph

Note that these queries require environment: Neo4j Desktop 1.2.7, Neo4j Enteprise 3.5.17, apoc 3.5.0.9 and GDS 1.1. At the time of writing, Neo4j 4.0.3 is not yet supported by GDS 1.1.

One of the fantastic qualities of the graph data model, I have always found, is that it can give you interesting insights - without even looking at the data. The structure of the network can give you some really interesting new revelations, that you would not even have considered before. That is why Neo4j has invested a ton of effort in providing our industry with a completely new set of capabilities that allow us to discover these structural insights more easily - in the form of a new Graph Data Science Library. We have recently released the product, and you should read up on it in detail, and I think it would be a great and interesting idea to explore it on this Contact Tracing dataset that we have built in part 1 and queried in part 2.

Some data prep for analytics: inferring a new relationship

In order to do that, there's actually something that's missing: a new relationship between two Persons, which infers the fact that two people have MET. We can do that based on the overlap time of their visits to the same place - therefore leveraging a query from part 2. This is what are going to do: create a MEETS relationship between 2 Person nodes, based on the overlap - and we do that like this:

match (p1:Person)-[v1:VISITS]->(pl:Place)<-[v2:VISITS]-(p2:Person)
where id(p1)<id(p2)
with p1, p2, apoc.coll.max([v1.starttime.epochMillis, v2.starttime.epochMillis]) as maxStart,
apoc.coll.min([v1.endtime.epochMillis, v2.endtime.epochMillis]) as minEnd
where maxStart <= minEnd
with p1, p2, sum(minEnd-maxStart) as meetTime
create (p1)-[:MEETS {meettime: duration({seconds: meetTime/1000})}]->(p2);

As you can see, we are storing the length of the inferred meeting as a duration property on the relationship. The result appears very quickly:

(Covid-19) Contact Tracing Blogpost - part 2/4

Part 2/4: Querying the contact tracing graph

Note that these queries require environment: Neo4j Desktop 1.2.7, Neo4j Enteprise 3.5.17, apoc 3.5.0.9 or Neo4j Enterprise 4.0.3, apoc 4.0.0.6 (NOT later! a bug in apoc.coll.max/apoc.coll.min needs to be resolved)

In Part 1 we created and imported a contact tracing graph. Now, we are ready to experiment with some interesting graphy queries.

The most interesting part about many if these queries, I find, is that they all relay on the fundamental principle of "hypothesis-free querying". What I mean by this is, is that graph querying, in my experience and opinion, have this wonderful quality about them that you can actually interact with the data in a way that does not require you to hypothesize too much about the structure of the dataset. This is important, because very often I just won't know what I don't know, and making meaningful hypotheses is actually really hard and complicated. The fact that we don't have to do that, is a great win.

As always, you will find all queries are on github, so that you can have a play with it yourself as well. So let's dive right into it.

Who has a sick person potentially infected

To answer that, I will "grab" a sick person from the dataset, and then just walk the dataset from the person to the other persons that are currently healthy. The query goes like this:

match (p:Person {healthstatus:"Sick"})
with p
limit 1
match (p)--(v1:Visit)--(pl:Place)--(v2:Visit)--(p2:Person {healthstatus:"Healthy"})
return p.name as Spreader, v1.starttime as SpreaderStarttime, v2.endtime as SpreaderEndtime, pl.name as PlaceVisited, p2.name as Target, v2.starttime as TargetStarttime, v2.endtime as TargetEndttime;

(Covid-19) Contact Tracing Blogpost - part 1/4

Part 1/4: creating and importing a synthetic contact tracing graph

As we are living in these very interesting times, and many countries are still going through a massive operation to slow down the devastating effects of the SARS-CoV-2 virus and its CoViD-19 effects, there is of course also a lot of discussion already going on what we will do after the initial surge of the virus has passed, and when the various countries and regions will start opening up their economies.

A tactic many countries seem to be taking is the implementation of some kind of Contact Tracing. Using the technology on our phones and our pervasive internet connectivity, we could imagine a way to implement "distancing" and isolation of people that are either already victim of, or vulnerable to, CoViD-19. This seems like a logical, and useful tactic, that could help us to open up our economies for business, while still maintaining the basic attitude of wanting to "flatten the curve". Of course there are still many, many issues with this approach, not in the least with regards to patient privacy and political freedoms, but it seems like an interesting track to explore, at least. Many government organisations have therefore started to explore this, and are working with some of the industry giants like Google and Apple to make this a reality.

This evolution started a whole range of discussions inside Neo4j, especially with regards to the usefulness of a graph database to make sense of some of these contact traceability databases. I remember reading Christakis and Fowler's Connected book, and understanding that virus outbreaks are one of those cases where our direct contacts don't necessarily matter - or at least not matter alone. Indirect contacts, between our friends' friends' friends, can be just as important. So lots of interesting, graph-oriented questions arise: How could we maximise the effect of our distancing measures, and of any contact tracing applications that we put in place? How could we use the excellent and predictive power of the graph to find out which of a person's connections could be most risky? How can we use graph analytics to better understand the structural power and weakness of our social networks? And many more.

So, being locked down myself (although Belgium clearly has a much software stance than for example France or Italy), I thought I would spend some time exploring this. That's what this blogpost series is going to be about - so let's get right to it.

Experimenting with Conflicting access privileges in Neo4j 4.0

In the past couple of weeks, I have been playing around with the shiny new security features of Neo4j 4.0. They are truly interesting - both for childproofing beergraphs and for ensuring that your sensitive fraud databases are properly secured. Take a look at the previous post, and I think you will understand why.

In this post, I wanted to talk about something that I have seen so many times in my previous lives in the security industry, and that also became evident in my 4.0 research. It's got to do with conflicting security privileges. In a nutshell, this is to do with the case where

• a specific user / role would receive a particular set of privileges from one policy
• the same user / role would receive a different, and contradictory privilege from another policy. 

In that case, we need clear rules to understand what would happen. In the case of Neo4j 4.0, this is reasonably well explained as part of the documentation - see the documentation site on this topic - but in this post I will try to give you a realistic, but simple example.

Creating Conflict

We'll start working on this with the same database as the previous post, the fraud dataset. If you don't have it yet, just download it from this link. Once we have the database up and running as a separate user database, we can switch to the system database and create a separate user for these tests.

//create a separate user for engineering the conflicting privileges
CREATE USER conflicted_user SET PASSWORD "changeme" CHANGE NOT REQUIRED;
CREATE ROLE conflicted_role AS COPY OF reader;

Securing a sample fraud graph with Neo4j 4.0

This week, we at Neo4j formally released our brightest and shiniest new version of the Neo4j Graphg Database to the world. It's been an amazing journey to this point, and others have reported on this magnificent piece of engineering in more depth. Take a look at Jim's blogpost, or if you are in a hurry, checkout the graphcast below:

Last week, I started playing around with it myself - by digging up my good old faithful beergraph, and illustrating some of the new features in childproofing exercise for beers. Take a look at that post as well for some giggles. Now in this post, I wanted to essentially do the same thing as I did on the beergraph, but using a Fraud dataset. 

Let's see how that would work.

Securing my Beergraph with Neo4j 4.0

Not sure if you have realised, but Neo4j has actually recently made the 4.0 version of the most fantastically awesome graph database on the planet available. You can get it ahead of the big launch event (on February 4th, 2020 - in case you were wondering!) from the Download Center and take it for a spin.

In this unbelievable release, there are so many new features, it's kind of hard to keep track of everything. But the ones that I can most easily get my head around are clearly

1. multi-database support - finally, Neo4j actually has this concept of running multiple databases on one database server. A multi-tenancy solution, that has been requested and anticipated by many of our users and customers. 
2. a VERY advanced schema-based security module, that allows people to extend the existing role-based security model of Neo4j even further - and make it crazy powerful. We'll spend a lot of time on that in this blogpost.

Readers of this blog probably know that I am a big fan of getting my feet down and dirty with our products, so this evening - with a couple of hours to spare, so to speak - I decided to try out the shiny new release. I spun up my Neo4j Desktop, and started reading some manual pages where stuff was explained. Specifically, I loved

• the manual pages on managing multiple databases
• the pages on authentication and authorisation
• a great video by Louise Söderström from Neo4j engineering:

Soon after flipping through this, I was on my way.

Podcast Interview With Andy Robbins, Rohan Vazarkar, SpecterOps

Here's another fantastic Neo4j Graphistania podcast episode for you. I had a brilliant chat with two guys in the US who have built a superb tool and written a bunch of articles about a topic that is very dear to my heart. I spent 10+ years working in the security industry, working on Identity and Access Management projects. And in that world, one of the most common problems is for people to misconfigure/mismanage their AD / LDAP server settings, and therefore get into a lot of security trouble because they just could not see through some of this stuff. Andy Robbins and Rohan Vazarkar (which I smilingly mispronounced as "the bezerker" :) ) did some amazing work on this, using Neo4j, and that's why we wanted to have a chat about this.

Here's the recording:


Here's the transcript of our conversation:

RVB: 00:00:03.538 Hello everyone. My name is Rik, Rik van Bruggen from Neo4J and here I am again recording another Graphistania podcast, and this time I have two lovely gentlemen on the other side of this Skype call. One is Andy Robbins and the other is Rohan Vazarkar, and these guys have been on my radar for a very long time because they have been developing some fascinating stuff around Neo4J. Welcome Andy. Welcome Rohan.