An Anonymiser Tool for Sensitive Graph Data

Abstract

Analysis of graph data is extensively conducted in numerous domains to learn the relationships between and behaviour of connected entities. Many graphs contain sensitive data, for example social network users and their posts, or genealogical records such as birth and death certificates. This has limited the use and publication of such sensitive graph data sets. While there are various techniques available to anonymise tabular data, anonymising graph data while maintaining the node and edge structure of the original graph, such as node attributes and the similarities between nodes, is a challenging task. In this paper, we present a web tool which can anonymise sensitive graph data while maintaining the similarity structure of the original graph by employing a cluster-based mapping of sensitive to public attribute values, as well as randomly shifting date values. Our demonstration will illustrate the tool on two example data sets of historical birth records.

Keywords

• eol>Graph anonymisation
• sensitive data
• data privacy
• data generation
• cluster mapping
• string similarity

1. Introduction

Proceedings of the CIKM 2020 Workshops, October 19-20, 2020, Galway, Ireland email: [e-mail] (C. Nanayakkara); [e-mail] (P. Christen); [e-mail] (T. Ranbaduge) orcid: 0000-0002-7603-1845 (C. Nanayakkara); 0000-0003-3435-2015 (P. Christen); 0000-0001-5405-3704 (T. Ranbaduge)

© 2020 Copyright for this paper by its authors. Use permitted under Creative CPWrEooUrckReshdoinpgs IhStpN:/c1e6u1r3-w-0s.o7r3g CCoEmUmoRns WLiceonrsekAsthtriobuptioPnr4o.0cIneteerdnaitniognasl ((CCC EBYU4R.0)-.WS.org) Female FN Fernandes Fernanders Fernando Whitacre .W.. hittacre Input parameters

3. Cluster based Attribute Value

Mapping

We now describe our anonymisation approach for sensitive attribute values. Assume we have a sensitive input data set containing records

∈ that represent entities, and external lookup tables of attribute for = ∈ do: ( . ) 2: for ∈ do: 1: 3: 4: 5: 6: 7: 8: 9: return = { }, = ′ = . // Initialise empty attribute value mapping table

// Iterate over sensitive attributes ( . ) // Cluster input attribute values // Cluster lookup attribute values // Iterate over attribute value clusters ( . , . , | . |, )

// Find best match ( , . , ′. ) ( ′) // Remove selected cluster from lookup clusters // Map attribute values in clusters

- : Set of sensitive attributes = ( , ), where a node (vertex) in values. The data set can be represented as a graph

represents a record pairwise attribute similarity of the record pair ( , ).

Such similarities, as calculated by comparing attribute

∈ , and an edge in corresponds to the values, are often used to show the strength or importance of relationships in graph data [ 7 ]. We refer to the set of sensitive attributes in as and the values from each sensitive attribute = { 1, … , },

in the

Assuming that the sensitive attributes have been used to calculate the pairwise similarities between records in , we need to ensure that these similarities are maintained in the anonymised data set we generate. This means that we need to retain the similarity graph = ( ,

data set . To achieve this goal, we use a one-to-one cluster mapping approach where we map an attribute value cluster from the sensitive input data set to an attribute value cluster from the public lookup tables such that the intra cluster similarities are highly simi , ) in the generated anonymised ) which represents the anonymised

Algorithm 1 outlines this approach to anonymise the sensitive attribute values in a given graph data set.

The input to the algorithm are the set of attributes tain values that attributes ∈ could assume. graph data set , and the lookup tables which con

In lines 2 to 4, the algorithm iterates over the sensitive attributes

∈ , and clusters the corresponding attribute values in the input data set lookup table . . Next, in lines 5 and 6, we iterate

and the over the attribute value clusters ∈ put data set and find the best matching attribute value cluster from the lookup attribute value clusters from the in

. . For a given attribute value cluster , we obtain its sorted values . = [ 1, 2, … ], the vector of paircalculated with an approximate string similarity func- structure of = ( The sensitive graph data set and one or more lookup

For each node in the input graph data set an anony- lar across the two clusters. tains date values, as shown in our example in Fig. 1, (such as names and addresses of people), the sensitive (which create a corresponding date 1′ where ≤ 1′ ≤ . Then, the remaining date values in the record group are shifted by 1′ − 1 domly shifted by ±Δ erated date value, excluding the earliest date 1′, is ran

days such that any temporal constraints across the generated date values are main

days and each newly genwhich are tained. For example, if contains birth records of sibling groups, then the temporal constraints of the birth dates would reflect that it is not possible for two births by the same mother to be less than nine months apart unless they are twins [ 8 ]. The anonymised date values tion wise similarities of attribute values in cluster . = [ 1, 2 , … , 1, , 2, 3 , … , −1, ], and the attribute value length vector matching cluster for . = [| 1|, | 2|, … , | |]. The best

is identified with the function larities vector (), which takes as input the pairwise simi

. , the vector of attribute value lengths the set of lookup attribute value clusters . , the number of attribute values in cluster | . |, and

. The func() finds the most similar lookup cluster ′ to from the set of lookup clusters

are of the same size as ) using Euclidean distances calculated between their similarity vectors and their attribute value length vectors. The cluster with the minimal weighted distances is selected to be ′ ∈ mapped to cluster . If larger than | . | are considered. of size | . | then subsets of clusters from

In line 7, we remove the selected cluster to obtain unique cluster mappings. In line 8, we

′ from then map the sorted attribute values in . to the cor

does not contain clusters tribute value from data set to a value in the lookup table .

4. Generating an Anonymised

Data Set

ing manner.

Once the attribute value mapping has been completed, DOYEN generates the anonymised graph data set for the sensitive input graph data set in the follow

For each record from the input data set ∈ , we create a synthetic record sitive attribute value in

′ ∈ , and for each sen, we replace the original attribute value with the corresponding mapped attribute value from

.

Given many data sets have dates associated with their records (such as dates of birth or dates of hospital admission), DOYEN also provides an anonymisation approach for date values while maintaining the temporal distances across connected records. Prior to date anonymisation, the records in are grouped such that related records are contained in a single group.

These groupings reflect records that represent a related group of entities, such as the siblings of the same family. Subsequent to grouping records, DOYEN sorts the date values associated with the records in a group.

The tool allows the user to define a minimum ( ) ) date within which they want and a maximum ( the earliest date value from a specific group to appear.

Thus, for the earliest date 1 from a record group, we

has a unique mapping responding values in cluster ′. , such that each at- are then used in the synthetic records ′ ∈ .

5. Demonstration

The initial implementation of the DOYEN tool demonstrates sensitive graph data anonymisation using two input data sets which we generated based on two realworld historical birth data sets. These data sets contain name and address variations to help demonstrate the capability of DOYEN to anonymise a graph while maintaining its similarity structure. The example birth data sets contain several twin births as well as missing values for the last names of fathers and children, as seen in the original birth data sets. Lookup tables containing values for the sensitive attributes first name, surname, and address, were generated using a publicly available US voter database (see: https://dl.ncsbe.gov) as well as Australian addresses. Table 1 summarises the number of unique values in each sensitive attribute in the lookup tables and the two example data sets. If attribute values contained more than one token (such as having two names) they were separated into individual tokens as a preprocessing step.

As shown in Table 1, the number of values available for each attribute is significantly larger in the lookup tables compared to the input graph data set. Having more attribute values in the lookup tables will help anonymise the sensitive input data set in a manner that better preserves its graph similarity structure.

Fig. 2 shows the input screen of the DOYEN web tool. The two buttons Example 1 and Example 2 will load one of the input graph data sets and suitable parameter values. A sample of the input data set can be viewed by clicking on the View Input Data Sample button, whereas the full data set can be downloaded as well. The four parameters to be specified are: • Group size and their counts: This parameter allows control of the number of families of a given size that are to be generated. When a sensitive graph data set is loaded, this field is automatically populated with the family size distribution of the loaded input data set. The user can change the values as desired.

However, the current implementation restricts the user to specifying only up to a maximum number of families as appearing in the input data set, for a given family size. That is, if there are ten families (clusters) of size five in the input data set, then currently the user can only generate a maximum of ten families of size five.

Jaro-Winkler for names and the Jaccard q-gram based approach for addresses) [ 6 ]. Subsequently, the attribute value clusters are identified with the connected component clustering approach with a similarity threshold of 0.8 [ 9 ]. Next, all attribute value clusters from the input graph are mapped to clusters from the lookup table using the Euclidean distance vector similarity measure, as we described in Algorithm 1. Since the vector of similarities between attribute value pairs in clusters ( . ) is more important than the vector of attribute value lengths ( . ), we assign a relatively higher weight • Minimum/Maximum dates for the first birth : For ( > 0.5) to . and a weight of 1 − to . when each family in the anonymised data set, the first calculating the overall cluster similarity. birth record in the family is expected to have a birth After the attribute value mapping is completed, the date within (including) the given minimum and max- DOYEN tool generates the anonymised graph data set i mum. date range ( and ), where < ibvnyaplurueetp,dlaaantcdainsbgeyttswhheiitfahttittnhrgiebtcuhoteerrdveaastpleuosenosdfoibnfigretamhchaapsrpdeecedoscrardtitbirneibdtuhitnee • Random time ofset : This is the ±Δ time range Section 4. Once the anonymised data is generated, the which is used to further shift (randomly perturb) user can view a sample of the attribute value mappings the dates of birth in each anonymised synthetic fam- as shown in Fig. 3. Furthermore, the user can view a ily (except the first date) as we described in Sec- sample of the anonymised, synthetic data set created tion 4. by DOYEN, or download the full data set. Fig. 4 shows a sample of the sensitive input data set and the corresponding anonymised records. Notice how, for example, the address values ‘monkstadt’ and ‘monkstodt’ (in R8 and R9) with a high pairwise string similarity have been replaced with values ‘narembure’ and ‘naremburn’ which have a similar pairwise similarity.

To illustrate the quality of the anonymised graphs generated by DOYEN, Fig. 5 shows the distribution of the pairwise similarity for record pairs from each example data set. For each record pair, the similarity is

The user has the flexibility of editing the values with which the parameter fields are automatically populated after an example data set has been loaded. When the Generate Data button is clicked, the anonymisation and data generation process is executed in the back end.

The tool internally calculates the string similarity of attribute values by first applying a blocking technique [ 9 ] (with phonetic encoding for names and Locality Sensitive Hashing for addresses) and then applying a pairwise string similarity calculation method (we used ity of anonymising sensitive graph data sets while preserving their similarity structure. As future work we intend to further improve DOYEN such that it is capable of maintaining geographic structures in the graph data (such as maintaining similar distances between addresses in input records and the corresponding generated anonymised output records). Furthermore, we plan to support generating synthetic data sets of different cluster size distributions without restricting the user to a maximum distribution as limited by the input data set. Such flexibility will allow users to generate larger or smaller data sets as suited for their research requirements.

Acknowledgments

This research was partially funded by the Australian Research Council under grant DP160101934. calculated using the Jaro-Winkler similarity measure on names and the Jaccard q-gram similarity measure on addresses [ 6 ], followed by an averaging of these values. As can be seen from this figure, the similarity distribution of both the sensitive input data set and the generated anonymised data set are highly similar for each of the two example data sets. This shows the capability of DOYEN to anonymise sensitive graph data, while maintaining its structure, as reflected by these pairwise similarities.

6. Conclusion and Future Work

In this paper, we have presented the initial implementation of our web tool DOYEN which has the capabil

References

[1] T. Feder , S. U. Nabar , E. Terzi, Anonymizing graphs, arXiv Preprint ( 2008 ). URL: http://arxiv. org/abs/0810.5578.

[2] L.-E. Wang , X. Li , A graph-based multifold model for anonymizing data with attributes of multiple types , CaS 72 ( 2018 ) 122 - 135 .

[3] S. Das , O. Egecioglu , A. Abbadi , Anónimos: An LP-based approach for anonymizing weighted social network graphs , IEEE TKDE 24 ( 2012 ) 590 - 604 .

[4] B. Zhou , J. Pei , W. Luk , A brief survey on anonymization techniques for privacy preserving publishing of social network data, SIGKDD Explor . Newsl. 10 ( 2008 ) 12 - 22 .

[5] G. Bloothooft , P. Christen , K. Mandemakers , M. Schraagen , Population Reconstruction, Springer, Cham, 2015 .

[6] G. Navarro , A guided tour to approximate string matching , ACM Computing Surveys 33 ( 2001 ) 31 - 88 .

[7] R. Xiang , J. Neville , M. Rogati , Modeling relationship strength in online social networks , in: WWW , ACM , Raleigh, NC , 2010 , pp. 981 - 990 .

[8] C. Nanayakkara , P. Christen , T. Ranbaduge, Robust temporal graph clustering for group record linkage , in: PAKDD , Springer, Macau, 2019 .

[9] P. Christen , Data Matching - Concepts and techniques for record linkage, entity resolution , and duplicate detection, Springer, Heidelberg, 2012 .