6.2.1 Identity Theories

The concept of identity has long been studied in philosophy, psychology, and sociology. It has a complex and changing subjective notion [8]. We consider an individual’s identity to have two basic components, namely a personal identity and a social identity.

A personal identity is one’s self-perception as an individual [9]. It deals with those necessary and sufficient conditions under which self persists over time. For example, people often ask common questions about their personal identities such as “Who am I” and “Where did I come from.” A personal identity may include personal information given at birth (e.g. name, date and place of birth), personal identifiers (e.g. social security number, passport number), physical descriptions (e.g. height, weight), and biometric information (e.g. fingerprint, DNA). A study conducted by the United Kingdom Home Office [10] suggests that identity crimes usually involve the illegal use or alteration of those personal identity components.

A social identity is one’s biographical history that builds up over time. It reflects how a person interacts with the society that he or she belongs to. Social identity theories consist of psychological and sociological views. The psychological view defines a social identity as one’s self-perception as a member of certain social groups such as nation, culture, gender, and employment [11,12]. Based on the psychological view, people within a social group may share some common characteristics that can distinguish themselves from people in other groups. On the other hand, the sociological view focuses on “the relationships between social actors who perform mutually complementary roles (e.g. employer–employee, doctor–patient)” [13]. The emphasis is on the interpersonal relationships among people and the social structure formed based on the relationships [14]. In addition, one’s social context determines the specific roles that the individual takes. For example, a man can have different roles in his family: the father of his children, the son of his parents, and the husband of his wife. An individual’s social identity, in this sense, is defined as the role-based interactions between the individual and people in his or her surrounding social networks. Deaux and Martin [13] integrated the psychological view and sociological view into one framework by regarding them as different levels of social context. The psychological view deals with large-scale social groups, whereas the sociological view deals with the proximate social groups in which members interact with each other. In this framework, a social identity becomes a multi-level concept that involves understanding one’s social groups at various scales.

6.2.2 Identity Attributes Used in Identity Resolution

For identity resolution, we are interested in determining features that can reliably identify an individual. Personal identity attributes such as names are often subject to data quality problems such as deception and data entry errors [5]. The use of identification cards and biometrics has been touted to be reliable identifiers by their proponents [15,16]. However, not only are there public concerns over its privacy implications, but a study also suggests that the connection between the use of national identity cards and antiterrorism is largely intuitive [17]. They investigated 25 countries that had been most adversely affected by terrorism since 1986. Those countries that employed an identity card system and biometric techniques did not show lessened terrorist activities in terms of number of attacks and deaths. O’Neil [18] discussed the shortcomings in biometrics as a counter-terrorist tool. He found that biometrics were not as reliable and fraud-proof as people expected. The lack of a reliable personal identifier prompts us to look for a good set of attributes for more accurate identity resolution than any single identifier.

The identity theories reviewed in the previous section suggest that personal and social identity attributes may complement each other for the purpose of identity resolution. Social identity attributes are derived from people’s social activities and relationships with other individuals. Such attributes exist implicitly in identity management databases and can be extracted for identity resolution. For example, we may infer relationships among identities based on the facts that some identities share the same address or get involved in the same incident. These inferred social attributes might be more reliable that personal identity attributes in that they cannot be easily altered or falsified by an individual. Taking into account social identity features can provide additional evidence when distinguishing one individual from others.

6.2.3 Existing Resolution Techniques

Identity resolution techniques are one type of entity resolution technique specializing in identity management. Entity resolution is also known as record linkage and deduplication in the areas of statistics and database management respectively. Record linkage, originated in the statistics community, identifies records in the same or different databases that refer to the same real-world entity [19]. The very same task is studied as record deduplication in database and artificial intelligence communities [20–22]. These techniques consider records comprised of multiple fields. To determine whether or not two records match, they first compare corresponding individual fields between two records. A decision model determines whether or not the two records refer to the same real-world entity by combining all comparison results. Elmagarmid et al. [23] provide a survey on individual field-matching techniques and models that detect duplicate records.

Compared to general entity resolution, identity resolution has its own challenges. Firstly, identity resolution needs to be efficient, especially for security-related tasks. Secondly, the evaluation of an identity resolution technique may be subject to different criteria under different circumstances. For example, the false-positive rate may be less tolerable than the false-negative rate for identity authentication that grants access to a critical infrastructure facility. However, a high false-positive rate may not be of much concern when a detective searches for a suspect with limited information. Lastly, identity matching in intelligence and law enforcement communities suffers greatly from the missing data problem [4]. Those record linkage and deduplication techniques tend to work poorly if many fields are missing from a record. In the following we briefly review existing techniques most appropriate for identity resolution. We categorize them into rule-based and machine learning approaches.

In the literature there have been several rule-based approaches for identity resolution by encoding matching rules specified by human experts. For instance, in a study on cross-jurisdictional data integration, Marshall et al. [24] encode experts’ heuristics into a simple rule: two identity records match only if their first name, last name, and date-of-birth (DOB) values are all identical. Obviously, in the case of data quality problems including missing values, such exact-match heuristics will cause many false-negative decisions and cannot effectively identify matching identity records. Some other approaches allow partial matching to reduce false negatives. The IBM DB2 Identity Resolution included in the Entity Analytic Solutions (EAS) is a leading commercial product designed to manage identity records [1]. It provides a rule-based identity-matching system that associates identity records representing the same person. For a pair of identity records, a matching score is calculated by following a set of rules predefined by human experts. For example, given two identity records with identical dates of birth and last names, the system will resolve them into one if the matching score of their first names is above 70%. The score can be calculated using any of the string comparison techniques reviewed in Ref. [23]. For these rule-based approaches, the rule creation process can be quite time-consuming, and the rules tend to be domain dependent and not portable across different contexts.

An alternative to manual rule coding is machine learning, which can automatically build identity resolution models by learning from a training dataset with annotated matching pairs. Identity resolution techniques based on machine learning can be further categorized into distance-based and probabilistic methods. Distance-based methods define distance/similarity measures for different types of descriptive attributes and combine them into a weighted average distance score. Two identity records whose overall distance is below a predefined threshold will be regarded as a match. Brown and Hagen [25] proposed a data association method for linking criminal records that possibly refer to the same suspect. This method compares two records and calculates a total similarity measure as a weighted sum of the similarity measures of all corresponding feature values. The features used by their method include suspect and modus operandi (MO) descriptions. The method lacks a matching decision model and only provides a list of matching candidates. Wang et al. [5] proposed a record comparison algorithm for detecting deceptive identities by comparing four personal features (name, DOB, social security number (SSN), and address) and combining them into an overall similarity score. A supervised learning process determines a threshold for match decisions using a set of identity pairs labeled by an expert. However, missing values could significantly affect the performance of the record comparison algorithm [4]. Probabilistic methods for identity matching are rooted in the seminal work of Ref. [19]. By posing record linkage as a probabilistic classification problem, they propose a formal framework to label pairs of identities from two different datasets as “match” or “non-match” based on the agreement among different features. Assuming conditional independence among features given the match class, the framework estimates the probabilistic parameters of the record linkage model in an unsupervised fashion. Many later studies were built based upon this work to enrich the probabilistic model [26–29]. These studies have shown that the probabilistic models achieve good performance for identity matching. However, the parameters of the probabilistic models may not be accurately estimated in the absence of sufficient training data [30].

Most identity resolution techniques reviewed above rely on personal identity attributes. Although these attributes provide a good basis for match decisions, they are prone to various issues, including entry errors, identity fraud and deception, and missing values. Identity resolution, especially in the crime/terrorist fighting context, is not simply a data quality problem as existing resolution techniques suggest. Solving such a complex problem requires a combination of multiple techniques and needs to be viewed from a network perspective [2]. Individuals are not isolated but interrelated to each other in a society. The social contexts associated with an individual can provide evidence that reveals his/her undeniable identity. Therefore, there is a need to develop identity resolution techniques that also incorporate the social perspective of identities.

6.2.4 Resolution Techniques Enabled by Social Contexts

Many recent studies have started to take into account linkage and contextual information for identity resolution. Köpcke and Rahm [31] categorized entity resolution approaches into attribute value matchers and context matchers. Unlike attribute value matchers, which solely consider descriptive attribute values, context matchers rely on information inferred through social interactions represented in a graph structure. Distance-based methods can combine the attribute similarity and relational similarity into one aggregated score for more reliable matching performance. Ananthakrishna et al. [32] introduced a deduplication method using a dimensional hierarchy (e.g. city–state–country) over the link relations in a customer data warehouse. This method enhances the personal feature comparison technique by only comparing feature values that have the same foreign key dependency. For example, the similarity of two people’s names will be assessed only when both live in the same city. However, that method requires a hierarchy among attribute relationships. In addition, it does not address the impact of the existence of missing values in a database. In a study on reference disambiguation, Kalashnikov et al. [33] incorporated inter-object relationships such as co-affiliation and co-authorship to disambiguate references using a nonlinear optimization model. However, their method cannot easily work as a plug-and-play solution in other entity resolution applications. In addition, probabilistic models that capture social contexts have been proposed for entity resolution. Culotta and McCallum [34] constructed a conditional random field model (CRF) for record deduplication that captures interdependencies between different types of entities. This method, however, fails to model the explicit links among the same type of entities. Pasula et al. [35] proposed a generic probabilistic relational model (PRM) for citation matching. It captures the dependences among entities over a relational database structure through foreign key relationships. This model is built upon the existing relational database structure and can be used as a plug-and-play solution because most current record management systems store records in relational databases. This approach, however, suffers from computational intractability. Bhattacharya and Getoor [36] proposed a graph-based method for entity resolution. It defines a similarity measure that combines corresponding attribute similarities with graph-based relational similarity between each entity reference pair. Their experiments show that the new similarity measure improves performance over the resolution methods that consider only attribute similarities. Furthermore, Bhattacharya and Getoor [6] extended their relational resolution approach to match entities in a collective fashion. Rather than making pairwise entity comparisons, their method collectively merges records into clusters. Through this process, new relational information can be derived and help to support further matching decisions.

The recent developments in entity resolution techniques shows that the relationships among entities can be used to improve resolution performance in addition to attribute distances/similarities. As we reviewed earlier, social relationships play an even more important role in personal identities than other types of entities because they affect one’s psychological and sociological perception of one’s own identity. It is our intention, based on the identity theories, to define social identity attributes that can be used to effectively enhance the performance of identity resolution.

6.3.1 Problem Formulation

We formulate the identity resolution problem as follows. Given a set of identity references, R = {r_i}, where each reference r is described by a set of personal identity attributes r•A₁, r•A₂, …, r•A_k. These references correspond to a set of unknown entities E = {e_i}. Due to duplicates and deception, multiple references { } may be co-referent to the same underlying entity e. We use r•E to refer to the entity to which reference r refers to. Also, each reference is involved with at least one incident and each incident may involve one or multiple references. We represent each incident as a hyper-edge in which multiple references may co-occur. We describe the co-occurrence with a set of hyper-edges H = {h_i}. Each hyper-edge h can also be described by a set of attributes h•B₁, h•B₂, …, h•B_l, and we use h•R to denote the set of references involved. A reference r can belong to zero or any number of hyper-edges and we use r•H to denote the set of hyper-edges in which r participates. The problem is to recover the hidden set of entities E = {e_i} and the entity labels r•E for individual references given the observed attributes of the references and their involved hyper-edges. Figure 6.1 illustrates the problem of identity resolution in a graph of five reference nodes connected by three hyper-edges.

6.3.2 Identity Resolution Approaches

Each identity resolution approach includes two major components: an attribute similarity measure and a matching strategy. A similarity function measures how similar two references are to each other based on certain attributes. A matching strategy specifies the algorithmic procedure of recovering the underlying entities from the given set of references. In this section we first define the identity attributes that can be used in identity resolution. We also discuss how we measure the similarity for each type of identity attribute. Lastly, we introduce matching strategies that make matching decisions based on the identity attribute similarities.

6.4.1 Synthetic Data Generation

We adopted a two-stage data-generation method described in Ref. [6] with some modifications, as described in Figure 6.3.

In the creation stage the algorithm first creates N entities with a personal identity attribute x and a behavior attribute y. We differentiate these two attributes because personal identity attributes can be easily modified or falsified while social behavioral attributes tend to be more consistent and less likely to change significantly over time. Next, we create M linkages among these N entities to represent their underlying social relationships. When we create these links, two entities with a similar social behavioral attribute y are more likely to be related to each other with a probability of , i.e. two individuals with similar interests are more likely to be related. In the generation stage, we created R hyper-edges that included a set of related entities’ references. An entity may join a hyper-edge of its neighbor with a probability of P_c. Whenever an entity is to join a hyper-edge, we either choose an existing reference of this entity with a probability P_a or create a new reference with its attribute x value following a Gaussian distribution of N(e•x, 1). Each reference r joins at least one hyper-edge. Each hyper-edge is also assigned an attribute y, which is equal to the average of all participating entities’ behavior attribute y.

It is worth noting that this synthetic data generator has two major differences compared to the one described in Ref. [6]. Firstly, for each entity, we define an additional attribute y to represent one’s behavioral characteristics that can be reflected and observed in its involved hyper-edges. Secondly, our synthetic data allow a reference to join more than one hyper-edge, while in Ref. [6] each reference only joins a single hyper-edge. This is more realistic in real identity management scenarios and requires more cost in computing similarities between references.

6.4.2 Experiment Design

In our experiments, we compared nine entity resolution approaches for identity resolution based on the categorization we described in the previous section (see Table 6.1). For similarity computation, we defined three different similarity functions that use personal identity attributes alone, personal identity attributes and social behavior attributes, and all three types of identity attributes respectively. For each similarity function, we employed it using one of the three different matching strategies: pairwise comparison, transitive closure, and collective clustering.

In our experiments we chose the following parameter values for generating the synthetic data: N = 100, M = 200, R = 500, P_a = 0.8, P_b = 0.9, P_c = 0.5, and the value ranges of x and y were set from 0 to 500. With such parameter settings, we generated 50 sets of synthetic data and compared the nine different resolution approaches.

The personal identity similarity between two references is defined as:

(6.9)

The similarity between two hyper-edges is defined as:

(6.10)

The two parameters that control the weights of the three types of similarity functions are set as α = 0.5 and β = 0.25. The threshold of overall similarity score is set as 0.99.

6.4.3 Evaluation Metrics

We evaluated the performance of each resolution approach by checking the correctness of the matching decisions for each reference pair. We followed most identity resolution studies and chose precision, recall and F-measure as our evaluation metrics [6]. As illustrated in Table 6.2, each matching decision on a pair of references is either a “match” (positive) or a “non-match” (negative). A decision can be either true or false.

Based on the decision outcomes, precision, recall, and F-measure are defined as follows:

(6.11)

(6.12)

(6.13)

6.4.4 Results and Discussion

Figure 6.4 summarizes the performance of the nine resolution approaches. Among the nine approaches, CB achieved the highest precision (92.92%) with the lowest recall (78.66%), A∗ achieved highest recall (99.49%) but the lowest precision (18.81%) and lowest F-measure (31.57%). The collective relational clustering approach (CR) achieved the highest F-measure of 89.39% because it considered all three types of identity attributes and matched references in a collective and iterative manner.

With the same matching strategy, the results show that approaches using personal identity attributes alone always achieved higher recall but at the cost of very low precision and F-measure. As social behavioral similarity is taken into account, we observed a significant boost in both precision and F-measure. This shows that social behavior attributes do contribute to the performance improvement of identity resolution by reducing false positives. Furthermore, when social relational attributes were also considered, there were some minor drops in precision but with generally higher F-measure. In particular, the approaches using all three types of identity attributes (R, R∗, and CR) outperformed its baselines in terms of F-measure.