Applying a k-anonymity model to protect node level privacy in knowledge graphs and a differential privacy model to protect edge level privacy in knowledge graphs

Patent metadata

Field	Value
Publication number	US-12411984-B2
Application number	US-202017247381-A
Country	US
Kind code	B2
Filing date	Dec 9, 2020
Priority date	Dec 9, 2020
Publication date	Sep 9, 2025
Grant date	Sep 9, 2025

Abstract

A device processes a knowledge graph to select a set of triples and generates a first class based on the set of triples. The device determines a quantity of quasi-identifier attributes in the first class and compares the quantity to a predefined parameter. The device embeds the knowledge graph to generate an embedding space representation, identifies a second class, and determines a first quantity of nodes in the first class and the second class. The device compares the first quantity to the predefined parameter and identifies a third class. The device determines a second quantity of nodes in the first class and the third class and compares the second quantity to the predefined parameter. The device merges the second class or the third class with the first class, based on the comparisons, to generate anonymized nodes for the knowledge graph.

First claim

What is claimed is:

1. A method, comprising:
receiving, by a device, a knowledge graph, a predefined parameter, a sensitivity parameter, a noise multiplier parameter, and an acceptance value;
selecting, by the device, a set of triples in the knowledge graph, by processing the knowledge graph, each triple in the set of triples including a quasi-identifier relation;
generating, by the device, an equivalence first class based on the set of triples in the knowledge graph;
determining, by the device, a quantity of a plurality of quasi-identifier attributes in the first class;
generating, by the device, a first comparison, by comparing the quantity of the plurality of quasi-identifier attributes to the predefined parameter;
generating, by the device, an embedding space generation representation, by processing the set of triples of the knowledge graph with a knowledge graph embedding model;
identifying, by the device, a similar neighbor second class for the equivalence first class;
determining, by the device, a first quantity of nodes in the first class and the second class;
generating, by the device, a second comparison, by comparing the first quantity of nodes in the first class and the second class to the predefined parameter;
identifying, by the device, a similar neighbor third class by determining nearest nongroup in the embedding space generation representation;
determining, by the device, a second quantity of nodes in the first class and the third class;
generating, by the device, a third comparison, by comparing the second quantity of nodes in the first class and the third class to the predefined parameter; and
generating anonymized nodes for the knowledge graph, by the device, by merging the second class or the third class with the first class, based on the first comparison, the second comparison, and the third comparison,
wherein merging further comprises:
based on the second comparison, merge the second class with the first class, if the first quantity of nodes is minimized above the predefined parameter;
based on the third comparison, merge the third class with the first class, if the second quantity is minimized above the predefined parameter;
generating privatized edges for the knowledge graph based on a differential privacy model, wherein generating the privatized edges for the knowledge graph further comprises:
generating, by analyzing the set of triples in the knowledge graph and based on the sensitivity parameter, a first set of sensitive triples and a second set of non-sensitive triples, wherein the sensitivity parameter comprises a sensitivity value associated with the differential privacy model to be applied to the knowledge graph;
converting, by processing the first set of sensitive triples using a first stochastic descent model, the first set of sensitive triples into a first embedding space;
converting, by processing the second set of non-sensitive triples using a second stochastic descent model, the second set of non-sensitive triples into a second embedding space;
generating a noisy first embedding space by adding parameterized Gaussian noise using the noise multiplier parameter to the first embedding space;
determining, by processing the noisy first embedding space with the differential privacy model, a differential privacy epsilon score; and
determining, by comparing the differential privacy epsilon score to the acceptance value, the differential privacy epsilon score satisfies a privacy requirement for the knowledge graph to generate the privatized edges for the knowledge graph; and
generating, by combining the anonymized nodes and the privatized edges, an anonymized knowledge graph to provide data identifying new knowledge associated with a subject matter of the knowledge graph.

2. The method of claim 1 , further comprising one or more of:
providing the anonymized knowledge graph for display; or
utilizing the anonymized knowledge graph to perform a calculation that satisfies one or more privacy conditions.

3. The method of claim 1 , wherein the predefined parameter includes an anonymization value.

4. The method of claim 1 , wherein when the first quantity of nodes or the second quantity of nodes is greater than the predefined parameter, anonymity is achieved for the predefined parameter.

5. A device, comprising:
one or more memories; and
one or more processors, communicatively coupled to the one or more memories, configured to:
receive a knowledge graph, a predefined parameter, a sensitivity parameter, a noise multiplier parameter, and an acceptance value;
select a set of triples in the knowledge graph, by processing the knowledge graph, each triple in the set of triples including a quasi-identifier relation;
generate an equivalence first class based on the set of triples in the knowledge graph;
determine a quantity of quasi-identifier attributes in the first class;
generate a first comparison, by comparing the quantity of quasi-identifier attributes to the predefined parameter;
generate an embedding space representation, by processing the set of triples of the knowledge graph with a knowledge graph embedding model;
identify a similar neighbor second class for the equivalence class;
determine a first quantity of nodes in the first class and the second class;
generate a second comparison, by comparing the first quantity of nodes in the first class and the second class to the predefined parameter;
identify a similar neighbor third class;
determine a second quantity of nodes in the first class and the third class;
generate a third comparison, by comparing the second quantity of nodes in the first class and the third class to the predefined parameter to generate the third comparison;
generate anonymized nodes for the knowledge graph, by merging the second class or the third class with the first class, based on the first comparison, the second comparison, and the third comparison,
wherein merging further comprises:
based on the second comparison, merge the second class with the first class, if the first quantity of nodes is minimized above the predefined parameter;
based on the third comparison, merge the third class with the first class, if the second quantity is minimized above the predefined parameter;
generate privatized edges for the knowledge graph based on a differential privacy model, wherein generating the privatized edges for the knowledge graph further comprises:
generating, by analyzing the set of triples in the knowledge graph and based on the sensitivity parameter, a first set of sensitive triples and a second set of non-sensitive triples, wherein the sensitivity parameter comprises a sensitivity value associated with the differential privacy model to be applied to the knowledge graph;
converting, by processing the first set of sensitive triples using a first stochastic descent model, the first set of sensitive triples into a first embedding space;
converting, by processing the second set of non-sensitive triples using a second stochastic descent model, the second set of non-sensitive triples into a second embedding space;
generating a noisy first embedding space, by adding parameterized Gaussian noise using the noise multiplier parameter to the first embedding space;
determining, by processing the noisy first embedding space with the differential privacy model, a differential privacy epsilon score; and
determining, by comparing the differential privacy epsilon score to the acceptance value, satisfies a privacy requirement for the knowledge graph to generate the privatized edges for the knowledge graph; and
generate, by combining the anonymized nodes and the privatized edges, an anonymized knowledge graph to provide data identifying new knowledge associated with a subject matter of the knowledge graph.

Assignees

• Accenture Global Solutions Ltd

Inventors

• Mccarthy Nicholas
• Hayes Jeremiah
• Zheng Xu

Classifications

• G06N5/04

  Inference or reasoning models · CPC title

• G06N20/00

  Machine learning · CPC title

• G06F21/6254 Primary

  by anonymising data, e.g. decorrelating personal data from the owner's identification · CPC title

• G06F21/602 Primary

  Providing cryptographic facilities or services · CPC title