Guaranteeing anonymity of linked data graphs

• US 9,477,694 B2
• Filed: 08/13/2013
• Issued: 10/25/2016
• Est. Priority Date: 04/25/2013
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Gkoulalas-Divanis, Aris, Kotoulas, Spyros, Lopez, Vanessa, Sbodio, Marco Luca
• Primary Examiner(s): Le, Miranda
• Application Number:
  US13/965,870
• Publication Number:
  US 20140325666A1
• Time in Patent Office: 1,169 Days
• Field of Search: 707/800, 707/803
• US Class Current: 1/1
• CPC Class Codes: G06F 16/21 Design, administration or maintenance of databases
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 21/60 Protecting data
• CPC Class Codes: G06F 21/6254 by anonymising data, e.g. decorrelating personal data from the owner's identification

Abstract

A system and computer program product for transforming a Linked Data graph into a corresponding anonymous Linked Data graph, in which semantics is preserved and links can be followed to expand the anonymous graph up to r times without breaching anonymity (i.e., anonymity under r-dereferenceability). Anonymizing a Linked Data graph under r-dereferenceability provides privacy guarantees of k-anonymity or l-diversity variants, while taking into account and preserving the rich semantics of the graph.

Claims

1. A computer program product to guarantee anonymity under r-dereferenceability in a Linked Data graph, the computer program product comprising:

a storage medium, wherein said storage medium is not a propagating signal, said storage medium readable by a processing circuit and storing instructions for execution by the processing circuit for performing a method comprising;

transforming an original Linked Data graph structure having labelled nodes interconnected by directed edges into a corresponding anonymous Linked Data graph, with one or more nodes embodying a searchable Uniform Resource Identifier (URI), and updating the corresponding ontology definitions of the Linked Data graph based on the applied transformations;

iteratively expanding said corresponding anonymous Linked Data graph up to r times, where r is an integer >

0, wherein said iteratively expanding comprises;

dereferencing a searchable URI of a node of said anonymized Linked Data graph structure by following a link to a resource from which a further Linked Data graph structure is obtained, said further Linked Data graph structure having additional labeled nodes embodying additional searchable URIs and property values, and replacing the node embodying the searchable URI of the anonymized Linked Data graph structure with the further Linked Data graph structure to obtain an expanded Linked Data graph, and updating the corresponding ontology definitions of the expanded Linked Data graph to include the ontology definitions of the further Linked Data graph structure; and

determining from each said additional URIs and property values in said expanded corresponding anonymous Linked Data graph whether anonymity is breached by searching for a URI whose iterative dereferencing originates a graph containing a Linked Data graph node URI that was present in the original Linked Data graph, and in that case

making the URI determined as breaching said anonymity non-dereferenceable.

2. The computer program product as claimed in claim 1, wherein prior to said transforming, the method further comprises:

identifying all inferences or indirect relations that can be extracted from the graph nodes, and the graph nodes included in the graph through dereferencing.

3. The computer program product as claimed in claim 2, wherein said transforming comprises:

computing instances I of nodes in said Linked Data graph structure, potentially having a direct identifier to be anonymized, and quasi-identifying properties Q of nodes whose values are to be anonymized;

anonymizing all direct identifiers of instances I,

changing the value of quasi-identifying properties in Q, and

changing corresponding ontology definitions of said properties and instance identifiers, wherein said changing values in Q comprises;

computing equivalence classes E for quasi-identifying properties in Q; and

changing values of such properties to be anonymized based on said computed equivalence classes.

4. The computer program product as claimed in claim 1, wherein said method further comprises:

identifying from said original Linked Data graph structure, one or more instances I to protect, said identified one or more instances I comprising;

a first set of said instances relating nodes of a given semantic class C that includes equivalent instances, instances of equivalent classes and instances whose inferred type is the given semantic class C, or any equivalent class; and

,

a second set of instances that are connected through an inverse functional property to any instance in said instances first set; and

extracting said instances I to be protected.

5. The computer program product as claimed in claim 1, further comprising:

identifying, by said computer system, from said original Linked Data graph structure, one or more properties Q to collectively protect, said identified one or more properties Q comprising;

properties that are inferred to be equivalent to any property given in an input set of properties P of said original Linked Data graph structure.

6. The computer program product as claimed in claim 5, wherein said protecting one or more properties Q comprises:

for each instance i of a given semantic class C;

compute a set Sim_i of a plurality of at least k−

1 other instances of said semantic class C which are similar to instance i according to a similarity measure S, said identifying of properties Q further considering a semantic class C and properties in said set P and semantically-equivalent instances and properties computed through inference, wherein said transforming comprises one of;

assigning the same generalized value to each property in set P for each instance in said set Sim_i (produced equivalence class), or suppressing a property for all instances in said set Sim_i,

wherein said corresponding anonymous Linked Data graph exhibits k-anonymity.

7. The computer program product as claimed in claim 5, wherein said protecting one or more properties Q comprises:

for each instance i of a given semantic class C;

compute a set Sim_i of a plurality of at least k−

1 other instances of said semantic class C which are similar to instance i according to a specified similarity measure S, said identifying of properties Q further considering a semantic class C and properties in said set P and semantically-equivalent instances and properties computed through inference, wherein said transforming comprises one of;

selecting the instances in Sim_i that results in at least l well represented values of related instances based on said specified similarity measure S,

wherein said corresponding anonymous Linked Data graph exhibits k-diversity.

8. The computer program product as claimed in claim 1, wherein if said anonymity is breached, said dereferencing comprises:

computing a subset of URIs in said expanded corresponding anonymized Linked Data graph whose dereferencing breaches anonymity, and for each URI u in said subset,

removing from said expanded corresponding anonymized Linked Data graph the Linked Data obtained by dereferencing said URI u; and

determining if URI u belongs to the corresponding anonymous Linked Data graph, and substituting URI u with a non-dereferenceable URI if determined that the dereferencing u belongs to the transformed corresponding anonymous Linked Data graph.

9. A system to guarantee anonymity under r-dereferenceability in a Linked Data graph comprising:

a memory storage device;

a processor unit in communication with said memory storage device and configured to perform a method to;

transform an original Linked Data graph structure having labeled nodes interconnected by directed edges into a corresponding anonymous Linked Data graph, with one or more nodes embodying a searchable Uniform Resource Identifier (URI), and updating the corresponding ontology definitions of the Linked Data graph based on the applied transformations;

iteratively expand said corresponding anonymous Linked Data graph up to r times, where r is an integer >

0, wherein said to iteratively expand, the processor unit is further configured to;

dereference a searchable URI of a node of said anonymized Linked Data graph structure by following a link to a resource from which a further Linked Data graph structure is obtained, said further Linked Data graph structure having additional labeled nodes embodying additional searchable URIs and property values, and replace the node embodying the searchable URI of the anonymized Linked Data graph structure with the further Linked Data graph structure to obtain an expanded Linked Data graph, and update the corresponding ontology definitions of the expanded Linked Data graph to include the ontology definitions of the further Linked Data graph structure; and

determine from each said additional URIs and property values in said expanded corresponding anonymous Linked Data graph whether anonymity is breached searching for a URI whose iterative dereferencing originates a graph containing a Linked Data graph node URI that was present in the original Linked Data graph, and

dereference a URI determined as breaching said anonymity.

10. The system as claimed in claim 9, wherein said processor unit is further configured to:

identify from said original Linked Data graph structure, one or more properties Q to collectively protect, said identified one or more properties Q comprising;

properties that are inferred to be equivalent to any property given in an input set of properties P of said original Linked Data graph structure.

11. The system as claimed in claim 9, wherein to protect one or more properties Q, said processor unit is further configured to:

for each instance i of a given semantic class C;

compute a set Sim_i of a plurality of at least k−

1 other instances of said semantic class C which are similar to instance i according to a similarity measure S, said identifying of properties Q further considering a semantic class C and properties in said set P and semantically-equivalent instances and properties computed through inference, wherein to transform, said processor unit is configured to perform one of;

assigning the same generalized value to each property in set P for each instance in said set Sim_i (produced equivalence class), or suppressing a property for all instances in said set Sim_i,

wherein said corresponding anonymous Linked Data graph exhibits k-anonymity.

12. The system as claimed in claim 9, wherein to protect one or more properties Q, said processor unit is further configured to:

for each instance i of a given semantic class C;

compute a set Sim_i of a plurality of at least k−

1 other instances of said semantic class C which are similar to instance i according to a specified similarity measure S, said identifying of properties Q further considering a semantic class C and properties in said set P and semantically-equivalent instances and properties computed through inference, wherein to transform, said processor unit is configured to;

select the instances in Sim_i that results in at least l well represented values of related instances based on said specified similarity measure S,

wherein said corresponding anonymous Linked Data graph exhibits l-diversity.

13. The system as claimed in claim 9, wherein to transform, said processor unit is further configured to:

compute instances I of nodes in said Linked Data graph structure, potentially having a direct identifier to be anonymized, and quasi-identifying properties Q of nodes whose values are to be anonymized;

anonymize all direct identifiers of instances I,

change the value of quasi-identifying properties in Q, and

change corresponding ontology definitions of said properties and instance identifiers, wherein said changing values in Q comprises;

compute equivalence classes E for quasi-identifying properties in Q; and

change values of such properties to be anonymized based on said computed equivalence classes.