Guaranteeing anonymity of linked data graphs

• US 9,514,161 B2
• Filed: 04/25/2013
• Issued: 12/06/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/870,346
• Publication Number:
  US 20140324915A1
• Time in Patent Office: 1,321 Days
• Field of Search: 707/803, 707/800
• 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 method, 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 method to guarantee anonymity under r-dereferenceability in a Linked Data graph comprising:

transforming 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 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;

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

making a URI determined as breaching said anonymity non-dereferenceable,

wherein a computing system including at least one processor unit performs one or more of;

the transforming, iteratively expanding, determining and said dereferencing.

2. The method as claimed in claim 1, wherein prior to said transforming, said method comprises:

identifying, by said computer system, 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 method 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 method as claimed in claim 1, further comprising:

identifying, by said computer system, 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 method 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 method 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 a 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 the 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 method 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 l-diversity.

8. The method 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.