 My name is Nathan Smith. I'm a senior data scientist in the Neo4j Professional Services Division. I joined Neo4j in 2021, so I've been here for a little bit over three years. Before coming to Neo4j, I had done previous graph work as a data scientist at Love Every and PRA Health Sciences sciences and my home is in kansas city missouri i'd like to kind of motivate this session with a quotation from nick harkaway who said wrote garbage in garbage out or rather more felicitously the tree of nonsense is watered with error and from its branches swing the pumpkins of disaster On almost every data science project that I work with with Neo4j, one of the first steps is always doing some kind of entity resolution. And that's really important to make sure that whether the data is all coming from one system or whether it's coming from multiple systems, that we've resolved those entities to match items in the real world. And when I failed to do that upfront, then often the pumpkin of disaster has come back to smack me in the end. There are several sessions today about entity resolution. It's a great topic. In fact, there's one going on right now with Paco Nathan from Senzing. There's another I saw earlier today from Linkurious. And so I would encourage you to check those out on the videos. You know, sometimes you need a more of a rich application type of approach to any resolution. The approach that I'm going to take is more of a lightweight approach that you might take before you maybe advance and move on to something that's more application focused and more complex. In talking about this title of this session as an entity resolution playbook, I want to distinguish between a recipe versus a playbook. When I think of a recipe, I think of like the technical challenge on the British Baking Show where you've got an explicit list of step-by-step things to do. You've got the exact ingredients that you need and you want everything to come out very consistently exactly the same way every time. And contrast that with a playbook. You know, being from Kansas City, it's almost obligatory that I'm a fan of the Kansas City Chiefs and their head coach Andy Reid comes into the game not with a recipe of what he's going to do step by step all through the whole game, but he does have a playbook. He's got some things that he has worked out in advance that he knows have worked many times in other contexts that then he can apply as needed against the various opponent or based on injuries or the weather or whatever changes. He can adapt, but he's got a bag of tricks that he can pull from. And that's really what I want you to come away from. This session is not necessarily an explicit recipe, but a bag of tricks that you can pull from as you're working on your own projects. So at a high level, this graph entity resolution process that I'm gonna outline for you begins by designing a graph data model that shows shared identifiers. Once we have that data model, we're gonna populate it with standardized data, and then we're also gonna flag what I call placeholders, and we'll talk about what that means later. Then we want to identify candidate entity pairs that might be entities in the real world that are the same. Then we'll calculate a similarity score, and for items that are above a threshold on that similarity score, we're going to record the results of the entity resolution process in our graph. So to begin, we need to find a good graph data model. And sometimes when I come into a project, I see a data model that looks like the one on the left. And in some ways, this makes sense because I want to find out if these two people are the same. So I've got the two-person nodes. And then here, I've got a whole bunch of properties that tell me everything I know about that person. The challenge with this data model for entity resolution, though, is that from a graph perspective, there's really nothing that connects these two people. I have to look at the individual properties. Looking at the individual properties like that is almost like I might as well just do the entity resolution in Python with record linkage or some other technology that's not really a graph. However, if I come over here at this data model that's on the right, if I refactor the data so that the shared identifiers are actually shared nodes that both of these people nodes are connected to, they both have the same phone number, they both have the same social security number. Now, just as a visual, when I look at this from a graph standpoint, I can suddenly see where the connections are, and I don't have to compare property by property as I would with the model on the left. So identifying these shared identifiers and breaking them out as separate nodes is a good first step. Now, there's also a potential pitfall here, because I think it's important we identify or make a difference between what I call identifiers versus descriptors. Identifiers are things that are pretty unique that wouldn't be shared by more than a few people in the real world, like a phone number. Maybe two or three people share the same phone number, but not 100 people or a social security number or something like that. A descriptor, on the other hand, is something that might be shared by a whole lot of people. So if you look at this picture on the right, we've broken out gender as its own node. And then everybody who has the same value for gender is now suddenly pointing to the same node. It creates a super node which is not ideal for us. And the fact that two people are connected to the same gender node doesn't really tell me that much that they are actually the same person, they just happen to have the same gender. So this would be a poor example of splitting out every single property into its own node and linking them together if it's really a descriptor and not an identifier. Another piece of the data model that I often find useful is to treat the addresses in a special way. Often location data can be an important part of telling if two things are the same. And here I'm looking at an address node and what we can do is apply a geocoding service maybe from Esri or from Google Maps or all of the cloud providers have these geocoding services where you can put in an address and then it's gonna give you back a latitude and a longitude. And so I'll make a separate node for that location that has the latitude and longitude with the point type within Neo4j. And that way, if I have two different addresses where maybe there's just a slight variation, like this one was spelled ST or this one was spelled street all spelled out but otherwise it's basically the same address I can tell that they're at least pointing to the same location in the real world now once we have that data model in mind we want to start to fill it in with the actual data that we're trying to clean up. And as we do that, it's important that we standardize the data and identify placeholders. So as we're looking at our raw data, we want to apply whatever formatting is necessary to bring it into a standard format. So if there's maybe leading or trailing white spaces, we want to strip those off. For the phone numbers, if there's like parentheses or trailing white spaces, we want to strip those off. For the phone numbers, if there's like parentheses around the area code or the country codes or different things like that, we just want to make sure that every record is consistent. That way, if I see the same string value, I know that that actually is the same thing from the source data. Same thing for emails, make sure they're all lowercase. Social security numbers, do they have the dashes to separate the segments or do they not? All things like this that can standardize the property before we load it into the graph. whether or not it's a valid value or not. For example, if you're dealing with phone numbers, in the United States, there are no US area codes that begin with the range 100 to 199. So if you see that value come in, you know, oh, this one's actually invalid. There's a typo going on here, or maybe there's some kind of fraud. Same thing for social security numbers. There are certain ranges that are invalid ranges. I've recently been working on a project with npi numbers that identify pharmacies or medical professionals and the last number of the npi number is actually a check digit that has to have a certain value based on the other numbers that are part of that string and so i can tell maybe there was a typo along the way somewhere or maybe this npi number was just made up by somebody. So I usually go ahead and load this invalid data into the graph because it could be a signal for fraud detection or something. But I put a special label on it. And so I can exclude it from the candidate matching because just because two people have the same invalid identifier in common, that doesn't necessarily mean that they're probably the same person in the real world, it just means they both made a typo, is what I would normally assume from that. Now, they're also what I call placeholders, and these are things that happen when somebody has required field on a form, but they don't know what to put in there, and so they just put my phone number is 999-9999-9999 or something like that, or none at known.com is my email address. Again, this is not something that is gonna help me identify a person in the real world because there is no such phone number as that in the real world. And so we wanna try to identify these placeholder values and hold them out from our analysis. And one way that we can do that is using the graph data science degree algorithm to figure out that some of these identifiers have a very high degree. Because remember, an identifier is something that you wouldn't expect to be shared by more than a handful of people or objects in the real world. So I might make a graph projection that has the phone numbers and then the people associated with those phone numbers. And if there's a phone number that has a very high degree, then it's probably a placeholder. And I can run that degree algorithm in stats mode to just get a sense of the overall distribution, like where's the 99th percentile for the most common phone numbers. And then I can also run it in stream mode to get back the actual values. And then again, I can label these values that are above whatever threshold I want to say, hold these out and don't include them in the next steps of the process. So now that we have our data model loaded into the graph, the next step is to identify entity pairs that might be duplicates. Now, when you think about this process of comparing nodes with each other, if I compare every single node with every single other node in the graph, that's a quadratic operation there that's going to take a lot of resources, a lot of memory, and a lot of time to compare every single thing with every single other thing. And so if I can narrow down the universe of things that need to be compared, my entity resolution operation can happen much faster. So this is the workflow that I follow usually. I'll load the graph data model, and then the first thing I'll do is an algorithm called Weeklyly connected components to start to narrow down the list of candidate matches and if that gives me a small enough number of candidates that I can afford to evaluate them all then I'll go on to my next steps in the process of calculating string similarity calculating descriptor penalties and getting the final score but if we click in active components gives me still using with too many possible pairs it hasn't narrowed things down far your penalties and getting the final score. But if weekly connected components still leaves me with too many possible pairs, it hasn't narrowed things down far enough, then I might move on to another algorithm called node similarity, which is going to allow me to narrow the field even further. And if that is still too much data to process, or if the number of candidates is too high to run node similarity, because node similarity is also a rather expensive operation, another approach is to use fast RP with KNN. And we're going to talk about each of these three options on the next few slides. The weekly connected components algorithm is one that just asks the question, is there any possible path that can get me from one node to another node in the graph? It doesn't care about the direction of the relationships. It just says, can I get from here to there? So as I look at this picture, these three blue person nodes, they all do have some kind of a path that links them together. So I would want to evaluate and say, okay, how likely is it that any of them are actually duplicates? Whereas this person node over here on the right, there is no path that connects me from this person to this person. That means they're going to be in different weekly connected components, and there's really no reason that I need to spend time checking other downstream tasks to see if they're the same person because they have no identifiers in common and so that allows me to segment the graph and break up my work in an efficient way now the next possible way of filtering things down even further is to use an algorithm called node similarity node similarity is asking how similar are two nodes sets of neighbors? So if I look at this picture, I've got two blue people nodes, and they both share a phone and they share a location. And then this one has also a social security number node that's not shared. So two out of the three neighbors are shared. And so this would have a Jaccard score of 2 thirds. And the Jaccard is one of the metrics that you can use when you're running node similarity, and it's often a good baseline. You have an option of two other metrics. One of them is called overlap. And with the overlap score, instead of taking the size of the intersection of their neighborhood divided by the size of the union of the neighborhood, the numerator of the fraction for overlap is the same. It's the size of the union of the neighborhood, the numerator of the fraction for overlap is the same. It's the size of the intersection of the neighborhood, but then for the denominator, we take the size of the smaller neighborhood. In this case, there are two nodes in common, and then the node with the smaller neighborhood has two nodes in its neighborhood, and so we have 2 over 2. The overlap score would be 1.0 versus two-thirds for the jacquard score overlap can be useful when you have missing data but it's not um it's not necessarily different data so in this case you know this person probably has a social security number i just don't know what it is so i don't want to penalize their um their relationship as far as possible being the same thing just because i don't happen to penalize their relationship as far as possible being the same thing just because I don't happen to have a number associated with this account. The final metric that you can consider is the cosine similarity. Cosine similarity is good when you have weighted relationships between these nodes. And that brings up the point that all these relationships can potentially be weighted if some of the relationships are more significant than others. And I also want to mention that if you're wanting to use weighted relationships with node similarity, I would encourage you to make sure that your GDS version is upgraded to version 2.10.1. There was an important bug fix in that release that solves some issues with weighted Jacquard. And so 2.10.1 or later is recommended if you're using node similarity in a weighted context. Now, the node similarity is a great algorithm, but it's also a little bit expensive. And for a really big graph, it can be slow to run. And so another alternative is to use an algorithm called FastRP, which creates embeddings for our nodes in the graph. So basically, if you start with a graph that looks like this, you apply FASTRP, and you turn each of those nodes into a point in a vector space. And then I can look for each node vector, what are the other node vectors that are most nearby? That's what the k nearest neighbors stand for. And so if I was asking for the two nearest neighbors neighbors for this node it would point me to this one and this one as blue nodes that are neighbors of this one in space and those would then become the candidates that i would check to see if they might be duplicates the fast rp is very very fast to run that's that's how it got its name it just does some magical matrix multiplication to run. And so that's the advantage of this approach. The disadvantage is it's an approximate approach. It's not exact like you would get with the node similarity approach. So there's a little bit of a trade off with performance and approximation. If you go this route, a couple of pointers that I would offer you, one of the most important parameters that you can tune with FastRP is the iteration weights. That tells you as you're running FastRP, how far out across the graph do I need to listen for signals to create the embedding for each node. In our case, if it's like a bipartite graph like we've been looking at, I really don't need to go out more than two or three hops. I don't need to have an iteration weight that has five or six or seven positions in that iteration weight vector because that's listening way too far out when I'm really just looking for who are my nodes that are just a couple of hops out. And so set a low iteration weight of probably two or three at the most when you're using fast RP for this purpose. Then when you're running k-nearest neighbors, what it's doing is it's starting with a node and then it is getting a suggested set of other neighbors that might be the closest k-nodes. Then it just tries to swap out other nodes into that neighbor set to see if it can improve the distances associated from the node that you started from. Well, that initial potential neighbor set that it starts from can be generated in a couple of ways. One is with just a uniform random sample where it could pick any node from anywhere in the vector space, anywhere on the graph. The other alternative is to use a random walk. And this is usually the better approach if you're trying to just find the nearest neighbors because it's just going to search out starting from your source node and find neighbors within a random walk around it. And those are the ones that we're most interested in checking to see if they are duplicates anyway. So the random walk initializer is a good step if you're using fast RP with k-nearest neighbors. All right, so now that we've identified our candidates, we're going to move on to calculating the similarity score. And there are probably some properties like a product name or a person name that are just text properties that we would like to compare. And Neo4j within our APOC text library offers a whole bunch. You see a long list here on this slide of different ways of comparing texts. I'll just point out a couple that I think are the most useful for our purposes. The Levenstein distance is a very common text comparison algorithm. It just is really about edit distance. How many transpositions or substitutions or deletions are required to turn one string into another string? So that's a good baseline one to start from. Levenstein similarity is basically the same algorithm, but it's just been inverted so that a high score coming from Levenstein similarity means that the two strings are almost the same. Whereas a high score with Levenstein similarity means that the two strings are almost the same, whereas a high score with Levenstein distance means that they are very different because you had to do a lot of edits to turn one into the other. So just keep in mind that very similar strings will have a low Levenstein distance and a high Levenstein similarity. Another algorithm to be aware of is the Jera-Winkler distance. And this algorithm prioritizes matching the beginning of the strings. And it's usually a good one for personal names, because if I was typing in my name, surely I'm going to get my first initial right. And maybe down later on in the string, I might slip up and make a typo. But this can be a good one for names. This is also the point in our entity resolution process where we're going to look at conflicting descriptors and create some kind of a penalty associated with that. If I look at this picture, here's two person nodes. They both share the same phone. They both share the same address. Oh, so that looks promising. That might be the same. If I look at their names, the strings are only one character apart. So that seems also very promising. Robert Johnson, Roberta Johnson, you might be thinking they're the same, but then when you look at the gender, this one is male, this one is female, and you realize, oh, that actually makes it, now that I have that extra piece of information, it actually makes it a lot less likely to be the same person, that they're duplicates. And so that's an important piece of information we want to include in our final formula. So to find this final formula, basically we're just going to combine all the ingredients that we've been working with so far. I'm going to take the node similarity score that's maybe going to come from k nearest neighbors or coming from node similarity, and that's the way that I'm going to account for the common neighbors. I've also got maybe a string similarity score that's based on how similar the text properties are. And then I've also got a penalty for unmatched descriptors, and I will apply some kind of a weight, and sometimes I'll just kind of look at the data and kind of play with those different weights to see what seems to work best. Or if we have a deduplicated data set that you're already confident in, I could train a machine learning model to find the right way to combine these ingredients, maybe with a logistic regression, to get the right weights for our inputs. So here's an example of a Cypher query, how we could do this. I'm going to start by streaming out, I created in mutate mode when I ran node similarity, a new relationship in my projection called has similar identifiers, and it's going to have a similarity score that I'm going to get back from mutate mode. And then when it comes back from the graph projection, the source node ID is just a number. The target node ID is just a number. So I'm going to call gds.util.asNode to turn those into actual nodes. And now that I've got those nodes, I can retrieve their text properties, their name properties here, and then I can call the Levenstein similarity function to get the text similarity. I can also check to see if their gender properties are different, and if they are, I can then include a penalty for having different genders. And finally, I'm just going to combine it. So I'm going to wait the identifier similarity is 65 of the score the text similarity is 35 of the score and then out on the descriptor penalties and that's going to give me my final similarity score and then anything that's above a threshold i'm going to say these are duplicate nodes anything below the threshold i'm going to say is probably not duplicates so now that i've figured out what is probably a duplicate i'm going to say is probably not duplicates. So now that I've figured out what is probably a duplicate, I'm going to store the results in my graph. One way to do this is to actually create a new node, like in this case a person group node, and all of the nodes that have a similarity score above the threshold get related to that same person group node. And the nice thing about this is I can still see all of the inputs that went into that person group node. So if I come back later and wonder why these things are related, I can see, you know, this is what they had in common or this is what the similarity score was. This is often a good way to handle the results of your similarity calculations. Another option is we have this APOC.refactor.mergeNodes procedure that you can call. Now, this is going to actually take those separate nodes and collapse them down into one. And this can be nice because your end users sometimes don't want to have to go look out to that group node. They just want to see the results collapsed like that. The disadvantage to collapsing them is that you kind of destroy the input ingredients. So a little bit harder to retrace and see why you collapsed these nodes that were separate in the source system to be together. So that's the major downside. But if you choose to use this, you have some options. If the source nodes have slightly different properties, you can choose to take the property value from the first node or take the value from the last node in the list that you're collapsing. Or you can actually preserve all the unique values as a list-valued property when you combine them. So that's something that you can configure. You can also configure if these two nodes that you're combining are both related to the same neighbor node, then you can choose to collapse that relationship. That way, after you've done the merging, you don't end up with two parallel relationships pointing to the same neighbor, but you just have one relationship. So those are some things to configure with that. Another option is not to change your graph at all, but to send your results back to the source system. And then you can merge them there or deduplicate them perhaps with a human in the loop to help you figure out, you know, was this really a data entry error of some kind that you can clean up? And then when you re-ingest that data to Neo4j, the duplicates that you have identified will be cleaned up. So that gives us our whole graph entity resolution process from beginning to end. We designed the graph data model that showed the shared identifiers. Then we made sure that we standardized the data before we loaded into the graph. And then we could also use GDS to flag the placeholders where we had the same value showing up more often than we would expect it to with different profiles. Then we identified the candidate entity pairs that we wanted to compare and we had three different ways to do that depending really on the volume of the data. And then we calculated the similarity score, things that were above a certain threshold with that similarity score we assume are the, and then we can record those results of the entity resolution process in the graph. So thank you very much for your attention. Are there any questions? Let me jump over to the Q&A. How is fast RP different from vectorizing the property of each node? Oh, let's see, there's more to this. Like the new Neo4j vector index. So that's a good question, Nick. Fast RP is really about vectorizing the topology of the graph. You can potentially include node properties when you run Fast RP, but for the situation that we're doing here, I would recommend that you simply, you've already moved those properties for the shared identifiers off to be their own nodes. And then it's really the topology or the relationships within the graph that we're trying to encode with the fast RP. And so that's what you're going to get out versus the vector index is more if I have a new query vector that I want to check on, I can query that. And it's kind of like the k-nearest neighbors, but it's done in real time for one specific vector that you're trying to match. So hopefully that answers that question adequately. And Kenneth asks if I have a blog post for this methodology and i don't but it would be a good idea to write one um so thank you for that suggestion and this video will also be um available on our youtube channel so you can come back and refer to that as well and mark asks um the recommended strategies are to be done after we have data in the graph. What are some data collection, NLP, and resolution processes you can do beforehand? And that's very true that, you know, certainly you don't have to do everything after it's in the graph. And I think some of the standardization topics that we talked about, about just trimming the white spaces around or making sure that everything's in the same format, that's a really good way before you even load the data into the graph to begin to handle this entity resolution. But as much of the processes you've done in advance in other ways with other tools, and then you bring that into the graph, you can still reflect the results of that in the same way that we were showing with the graph-based approach, where maybe you make a group node that you relate everything to, or you possibly even merge the nodes after you bring them in. That can still be relevant relevant even if you've done some of the other work upstream so let's see i think we're just about out of time but do we have any more um questions here um i think we might have addressed them all great well enjoy the rest of nodes and if you have any questions beyond what I answered today, feel free to reach out and we'd be happy to continue the conversation.
NODES 2024 - A Graph Entity Resolution Playbook
Entity resolution, the process of determining which digital descriptions correspond to the same real-world entities, is an important graph use case. It is also a crucial precursor to many graph data science projects. In this session, you will learn steps that the Neo4j professional services team has used in many entity resolution projects. The steps include designing a graph data model that highlights shared identifiers, standardizing the format of node properties, identifying outlier nodes that should be excluded from the matching process, using graph data science algorithms to identify duplicate entities, using string similarity to identify misspellings, and capturing the results of entity resolution in your graph.

Get certified with GraphAcademy: https://dev.neo4j.com/learngraph
Neo4j AuraDB https://dev.neo4j.com/auradb
Knowledge Graph Builder https://dev.neo4j.com/KGBuilder
Neo4j GenAI https://dev.neo4j.com/graphrag