Initialization

Recall in our model that an Account is a digital identity, and a User is a real person. The original database contains only Accounts. The initialization step creates a unique temporary User linked to each Account. And, for every edge from an Account to one of the attribute vertices (Email, Phone, etc.), we create a corresponding edge from the User to the same set of attribute vertices. Figure 2-7 shows an example. The three vertices on the left and the two edges connecting them are part of the original data. The initialization step creates the User vertex and the three dotted-line edges. As a result, each User starts out with the same attribute neighborhood as its Account.

Figure 2-7. User vertex and edges created in the initialization step

Run the GSQL query initialize_users by selecting the query name from the list (step 1 in Figure 2-8) and then clicking the Run icon above the code panel (step 2). This query has no input parameters, so it will run immediately without any additional steps from the user.

Figure 2-8. Running the initialize_users query

Let’s take a look at the GSQL code. The block of code below shows the first 20 lines of initialize_users. If you are familiar with SQL, then GSQL may look familiar. The comment at the beginning (lines 2 and 3) lists the 6 types of attribute vertices to be included. Lines 6 to 10 create a User vertex (line 9) and an edge connecting the User to the Accounts (line 10) for each Account (line 6) which doesn’t already have a neighboring User (line 7).

1   CREATE QUERY initialize_users() SYNTAX v2 {
2   // Create a User vertex for each Account, plus edges to connect attributes
3   // (IP, Email, Device, Phone, Last_Name, Address) of the Account to the User
4
5   // Initialize each account with a user
6   Accounts = SELECT s FROM Account:s
7   WHERE s.outdegree("Has_Account")==0
8   ACCUM
9     INSERT INTO User VALUES(s.id),
10    INSERT INTO Has_Account VALUES(s.id, s);
11
12  // Connect the User to all the attributes of their account
13  IPs = SELECT attr FROM Accounts:s -(Has_IP:e)- IP:attr
14  ACCUM
15    INSERT INTO User_IP VALUES(s.id, attr);
16
17  Emails = SELECT attr FROM Accounts:s -(Has_Email:e)- Email:attr
18  ACCUM
19    INSERT INTO User_Email VALUES(s.id, attr);
20  // Remaining code omitted for brevity
21  }

Lines 13 to 15 take care of IP attribute vertices: If there is a Has_IP edge from an Account to an IP vertex, then insert an edge from the corresponding User vertex to the same IP vertex. While the alias s defined in line 13 refers to an Account, s.id in line 15 can refer to a User because the source vertex of a User_IP edge may only be a User, and we recently used s.id to create a User (line 9). Lines 17 to 19 take care of Email attribute vertices in an analogous way. The code blocks for the remaining four attribute types (Device, Phone, Last_Name, and Address) have been omitted for brevity.

Similarity Detection

Jaccard similarity counts how many attributes two entities have in common, divided by the total number of attributes between them. Each comparison of attributes results in a yes/no answer; a miss is as good as a mile. Figure 2-9 shows an example where User A and User B each have three attributes; two of those match (Email 65 and Device 87). Therefore, A and B have two attributes in common.

Figure 2-9. Jaccard similarity example

They have a total of four distinct attributes (Email 65, Device 87, Phone 23, and Phone 99); therefore, the Jaccard similarity is 2/4 = 0.5.

Do: Run connect_jaccard_sim.

The query connect_jaccard_sim computes this similarity score for each pair of vertices. If the score is at or above the given threshold, then create a Same_As edge to connect the two Users. The default threshold is 0.5, but you can make it higher or lower. Jaccard scores range from 0 to 1. Figure 2-10 shows the connections for User vertices 1, 2, 3, 4, and 5, using Jaccard similarity and a threshold of 0.5. For these five vertices, we need communities that range in size from one vertex alone (User 3) to two clusters of three (Users 1 and 2).

Figure 2-10. Connections for User vertices 1, 2, 3, 4, and 5, using Jaccard similarity and a threshold of 0.5

Rather than showing the full code, we’ll just focus on a few excerpts. In the first code snippet, we’ll show how to count the attributes in common between every pair of Users, using a single SELECT statement. The statement uses pattern-matching to describe how two such Users would be connected, and then it uses an accumulator to count the occurrences.

1   Others = SELECT B FROM
2   Start:A -()- (IP|Email|Phone|Last_Name|Address|Device):n -()- User:B
3   WHERE B != A
4   ACCUM
5     A.@intersection += (B -> 1); // tally each path A->B,
6     @@path_count += 1            // count the total number of paths

The FROM clause in lines 1 to 2 presents a graph path pattern to search for. FROM User:A -()- (IP|Email|Phone|Last_Name|Address|Device):n -()- User:B defines a two-hop path pattern:

• User:A means start from a User vertex, aliased to A,

• -()- means pass through any edge type

• (IP|Email|Phone|Last_Name|Address|Device):n means arrive at one of these six vertex types, aliased to n

• -()- means pass through another edge of any type, and finally

• User:B means arrive at a User vertex, aliased to B

In line 3, (WHERE B != A) ensures that we skip the situation of a loop where A = B. Line 4 announces the start of an ACCUM clause. Line 5 (A.@intersection += (B -> 1); // tally each path A->B) is a good example of GSQL’s support for parallel processing and aggregation: for each path from A to B, append a key → value record attached to A. The record is (B, +=1). That is, if this is the first record associating B with A, then set the value to 1. For each additional record where B is A’s target, then increment the value by 1. Hence, we’re counting how many times there is a connection from A to B, via one of the six specified edge types. Line 6 (ACCUM @@path_count += 1) is just for bookkeeping purposes, to count now many of these paths we find.

Let’s look at one more code block, the final computation of Jaccard similarity and creation of connections between Users.

1   Result = SELECT A FROM User:A
2   ACCUM FOREACH (B, overlap) IN A.@intersection DO
3   FLOAT score = overlap*1.0/(@@deg.get(A) + @@deg.get(B) - overlap),
4   IF score > threshold THEN
5     INSERT INTO EDGE SameAs VALUES (A, B, score), // FOR Entity Res
6     @@insert_count += 1,
7     IF score != 1 THEN
8       @@jaccard_heap += SimilarityTuple(A,B,score)
9     END
10  END
11  END;

This SELECT block does the following:

1. For each User A, iterate over its record of similar Users B and the number of common neighbors, aliased to overlap.

2. For each such pair (A, B), compute the Jaccard score, using overlap as well as the number of qualified neighbors of A and B (@@deg.get(A) and @@deg.get(B)), computed earlier.

3. If the score is greater than the threshold, insert a SameAs edge between A and B.

4. @@insert_count and @@jaccard_heap are for reporting statistics and are not essential.

Merging

In our third and last stage, we merge together the connected communities of User vertices which we created in the previous step. For each community, we will select one vertex to be the survivor or lead. The remaining members will be deleted; all of the edges from an Account to a non-lead will be redirected to point to the lead User.

Do: run query merge_connected_users. Look at the JSON output. Note whether t says converged = TRUE or FALSE.

Figure 2-13 displays the User communities for Accounts 1, 2, 3, 4, and 5. The user communities have been reduced to a single User (real person). Each of those Users links to one or more Accounts (digital identities). We’ve achieved our entity resolution.

Figure 2-13. Entity resolution achieved, using Jaccard similarity

The merge_connected_users algorithm has four stages:

1. Find connected users using the connected component algorithm.

2. In each component, select a lead user.

3. In each component, redirect the attribute connections from other users to the lead user.

4. Delete the users that are not the lead user and all of the Same_As edges.

We’ll take a closer look at the GSQL code for the Connected Components algorithm.

1   Users = {User.*};
2   Updated_users = SELECT s FROM Users:s
3     POST-ACCUM
4       s.@min_user_id = s;
5
6   WHILE (Updated_users.size() > 0) DO
7     IF verbose THEN PRINT iteration, Updated_users.size(); END;
8     Updated_users = SELECT t
9      FROM Updated_users:s -(SameAs:e)- User:t
10      // Propagate the internal IDs from source to target vertex
11     ACCUM t.@min_user_id += s.@min_user_id   // t gets the lesser of t & s ids
12     HAVING t.@min_user_id != t.@min_user_id' // accum is accum's previous val
13      ;
14    iteration = iteration + 1;
15  END;

Line 1 initializes the vertex set called Users to be all User vertices. Lines 2 to 4 initializes an accumulator variable @min_user_id for each User. The initial value is the vertex’s internal ID (different from the externally visible ID). This variable will store the algorithm’s current best guess at the community ID for this vertex: all vertices having the same value of @min_user_id belong to the same community. It’s important to note that this accumulator is a MinAccum. Whenever you input a new value to a MinAccum, it retains the lesser of its current value and the new input value.

Lines 8 to 11 says that for each connected User pair from s to t, set t.@min_user_id to the lesser of s and t’s community IDs. Line 12 says that the output set (Updated_users in line 8) should contain only those User vertices who updated their community ID in this round. Note the tick mark ' at the end of the line; this is actually a modifier for the accumulator t.@min_user_id. It means “the previous value of the accumulator”; this lets us easily compare the previous to current values. When no vertices have changed their ID, then we can exit the WHILE loop (line 6).

Are We There Yet?

It might seem that one pass through the three steps – initialize, connect similar entities, and merge connected entities – should be enough. The merging, however, can create a situation in which new similarities arise. Take a look at Figure 2-14, which depicts the attribute connections of User 302 after Users 2 and 602 have been merged into it. Accounts 2, 302, and 602 remain separate, so you can see how each of them contributed some attributes. Because User 302 has more attributes than before, it is now possible that it is more similar than before to some other (possibly newly merged) User. Therefore, we should run another round of similarity connection and merge. Repeat these steps until no new similarities arise.

Figure 2-14. User with more attributes after entity resolution

Reset

After you’ve finished, or at any time, you might want to restore the database to its original state. You need to do this if you want to run the entity resolution process from the start again. The query util_delete_users will delete all User vertices and all edges connecting to them. Note that you need to change the input parameter are_you_sure from FALSE to TRUE. This manual effort is put in as a safety precaution.

Initialization

We are still using the same graph model with User vertices representing real persons and Account vertices representing digital accounts. So, we are still using the initialize_users query to set up an initial set of User vertices.

We are adding another initialization step. We are going to assign weights to each of the six attributes: IP, Email, Phone, Address, Last_Name, and Device. If this were a relational database, we would store those weights in a table. Since this is a graph, we are going to store them in a vertex. We only need one vertex, because one vertex can have multiple attributes. However, we are going to be even more fancy. We are going to use a map type attribute, which will have six key → value entries. This allows us to use the map like a lookup table: tell me the name of the key (attribute name), and I’ll tell you the value (weight).

Do:

1. Run initialize_users. Check the graph statistics on the Load Data page to make sure that all 900 Users and related edges have been created.
   

2. Run util_set_weights. The weights for the six attributes are input parameters for this query. Default weights are included, but you may change them if you wish. If you want to see the results, run util_print_vertices.

Scoring Weighted Exact Matches

We are going to do our similarity comparison and linking in two phases. In phase one, we are still checking for exact matches because exact matches are more valuable than approximate matches; however, those connections will be weighted. In phase two, we will then check for approximate matches for our two attributes which have alphabetic values: Last_Name and Address.

In weighted exact matching, we create weighted connections between Users, where higher weights indicate stronger similarity. The net weight of a connection is the sum of the contributions from each attribute that is shared by the two Users. Figure 2-15 illustrates the weighted match computation. Earlier, during the initialization phase, you established weights for each of the attributes of interest. In the figure, we use the names wt_email and wt_phone for the weights associated with matching Email and Phone attributes, respectively.

Figure 2-15. Two-phase calculation of weighted matches

The weighted match computation has two steps. In step 1, we look for connections from Users to Attributes and record a weight on each attribute for a connection to each User. Both User A and User B connect to Email 65, so Email 65 records A:wt_email and B:wt_email. Each User’s weight needs to be recorded separately. Phone 99 also connects to Users A and B so it records analogous information.

In step 2, we look for the same connections but in the other direction, with Users as the destinations. Both Email 65 and Phone 99 have connections to User A. User A aggregates their records from step 1. Note that some of those records refer to User A. User A ignores those, because it is not interested in connections to itself! In this example, it ends up recording B:(wt_email + wt_phone). We use this value to create a weighted Same_As edge between Users A and B. You can see that User B has equivalent information about User A.

Do: run connect_weighted_match.

Figure 2-16 shows one of the communities generated by connect_weighted_match. This particular community is the one containing User/Account 5. The figure also shows connections to two attributes, Address and Last_Name. The other attributes such as Email were used in the scoring but are not shown, to avoid clutter.

Figure 2-16. User community including Account 5 after exact weighted matching

The thickness of the SameAs edges indicates the strength of the connection. The strongest connection is between Users 505 and 805 at the bottom of the screen. In fact, we can see three subcommunities of Users among the largest community of seven members:

• Users 5, 105, and 205 at the top. The bond between Users 5 and 105 is a little stronger, for reasons not shown. All three share the same last name. They have similar addresses.

• Users 305 and 405 in the middle. Their last names and address are different, so some of the attributes not shown must be the cause of their similarity.

• Users 505 and 805 at the bottom. They share the same last name and address, as well as other attributes.

Scoring Approximate Matches

We can see (in Figure 2-16) that some Users have similar names (Ellsworth vs. Ellesworth) and similar addresses (Eagle Creek Center vs. Eagle Crest Ctr). A scoring system that looks only for exact matchings gives us no credit for these near misses. An entity resolution system would like to be able to assess the similarity of two text strings and to assign a score to the situation. Do they differ by a single letter, like Ellsworth and Ellsworth? Are letters transposed, like Center and Cneter? Computer scientists like to think of the edit distance between two text strings: how many single-letter changes of value or position are needed to transform string X into string Y?

We are going to use the Jaro-Winkler similarity to measure the similarity between two strings, an enhancement of Jaro similarity. Given two strings s1 and s2, who have m matching characters and t transformation steps between them, then their Jaro similarity is defined as shown in Equation 2-1.

If the strings are identical, then m = |s1| = |s2|, and t =0, so the equation simplifies to (1 + 1 + 1)/3 = 1. On the other hand, if there are no letters in common, then the score = 0. We then multiply this score by the weight for the attribute type. For example, if the attribute’s weight is 0.5, and if the JaroWinkler similarity score is 0.9, then the net score is 0.5 * 0.9 = 0.45.

Jaro-Winkler similarity takes Jaro as a starting point and adds an additional reward if the beginnings of each string, reading from the left end, match exactly.

Do: Run score_similar_attributes.

The score_similar_attributes query considers the User pairs which already are linked by a Same_As edge. It computes the weighted Jaro-Winkler similarity for the Last_Name and the Address attributes, and adds those scores to the existing similarity score. We chose Last_Name and Address because they are alphabetic instead of numeric. This is an application decision rather than a technical one. Figure 2-17 shows the results after adding in the scores for the approximate matches.

Figure 2-17. User community including Account 5 after exact and approximate weighted matching

Comparing Figures 11-16 and 11-17, we notice the following changes:

• The connections among Users 1, 105, and 205 have strengthened due to their having similar addresses.

• User 305 is more strongly connected to the trio above due to a similar last name.

• The connection between 305 and 405 has strengthened due to their having similar addresses.

• User 405 is more strongly connected to Users 505 and 805 due to the name Hunter having some letters in common with Brunke. This last effect might be considered an unintended consequence of the Jaro-Winkler similarity measure not being as judicious as a human evaluator would be.

Comparing two strings is a general purpose function which does not require graph traversal, so we have implemented it as a simple string function in GSQL. Because it is not yet a built-in feature of the GSQL language, we took advantage of GSQL’s ability to accept a user-supplied C++ function as a user-defined function (UDF). The UDFs for jaroDistance(s1, s2) and jaroWinklerDistance(s1, s2) are included in this starter kit. You can invoke them from within a GSQL query anywhere that you would be able to call a built-in string function.

The code snippet below shows how we performed the approximate matching and scoring for the Address feature:

1   Connected_users = SELECT A
2     // Find all linked users, plus each user's address
3     FROM Connected_users:A -(SameAs:e)- User:B,
4        User:A -()- Address:A_addr,
5        User:B -()- Address:B_addr
6     WHERE A.id < B.id    // filter so we don't count (A,B) & (B,A)
7     ACCUM @@addr_match += 1,
8     // If addresses aren't identical compute JaroWinkler * weight
9     IF do_address AND A_addr.val != B_addr.val THEN
10      FLOAT sim = jaroWinklerDistance(A_addr.id,B_addr.id) * addr_wt,
11      @@sim_score += (A -> (B -> sim)),
12      @@string_pairs += String_pair(A_addr.id, B_addr.id),
13      IF sim != 0 THEN @@addr_update += 1 END
14    END
15  ;

Lines 3 to 5 are an example of a conjunctive path pattern, that is, a compound pattern comprising several individual patterns, separated by commas. The commas act like boolean AND. This conjunctive pattern means “find a User A linked to a User B, and find the Address connected to A, and find the Address connected to B.” Line 6 filters out the case where A = B and prevents a pair (A, B) from being processed twice.

Line 9 filters out the case where A and B are different but have identical addresses. If their addresses are the same, then we already gave them full credit when we ran connect_weighted_match. Line 10 computes the weighted scoring, using the jaroWinklerDistance function and the weight for Address. Line 11 stores this value in a lookup table temporarily. Lines 12 and 13 are just to record our activity, for informative output at the end.

Merging Similar Entities

In Method 1, we had a simpler scheme for deciding whether to merge two entities: if their Jaccard score was greater than some threshold, then we created a SameAs edge. The decision was made. Merge everything that has a SameAs edge. We want a more nuanced approach now. Our scoring has adjustable weights, and the SameAs edges record our scores. We can use another threshold score to decide which Users to merge.

Take another look at Figure 2-17. We can see the effect of threshold score for mergIng. If we set the threshold at 3.0, there would be only two merges in this community: (5, 105) and (505, 805). If we set it at 2.0, we will get the three communities that we spoke about earlier: (5, 105, 205), (305, 405), and (505, 805). If we set the threshold at 1.0, all seven Users will be merged into 1.

We only need to make two small changes to merge_connected_users to let the user set a threshold.

• Add a threshold parameter to the query header:
  
  CREATE QUERY merge_connected_users(FLOAT threshold=1.0, BOOL verbose=FALSE)
  

• In the connected component algorithm, add a WHERE clause to check the SameAs edge’s similarity value:

1   WHILE (Updated_users.size() > 0) DO
2     IF verbose THEN PRINT iteration, Updated_users.size(); END;
3     Updated_users = SELECT t
4       FROM Updated_users:s -(SameAs:e)- User:t
5       WHERE e.1  similarity > threshold
6         // Propagate the internal IDs from source to target vertex
7           // t gets the lesser of t & s ids
8       ACCUM t.@min_user_id += s.@min_user_id
9           // accum' is accum's previous val
10      HAVING t.@min_user_id != t.@min_user_id'
11    ;
12    iteration = iteration + 1;
13  END;

Run merge_connected_users. Pick a threshold value and see if you get the result that you expect.

Figure 2-18 shows the three different merging results for threshold values of 1.0, 2.0, and 3.0, to the community we have been following.

Figure 2-18. Entity resolution with different threshold levels

That concludes our second and more nuanced method of entity resolution.