Patent Description:
<CIT> describes 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 <NUM>-diversity variants, while taking into account and preserving the rich semantics of the graph.

<CIT> describes system, method, and computer program product embodiments for data anonymization in an in-memory database. An embodiment operates by receiving an indication to perform data anonymization based on quasi attributes of a data set. Partitioning is recursively performed on the data set based on one or more of the quasi attributes until both a first anonymization threshold corresponding to the quasi attributes is satisfied and a second anonymization threshold corresponding to the one or more sensitive attributes is satisfied for each of a plurality of sub-partitions produced as a result of the partitioning. A resultant data set including a plurality of records of the data set corresponding to the plurality of sub-partitions that satisfy both the first anonymization threshold and the second anonymization threshold is provided.

<CIT> describes receiving a view command for creating a view to display anonymized data in response to one or more queries, the view command including a view name, a table, a set of columns of the table, an anonymization type, a set of static parameters, and, for a sub-set of columns of the table, one or more sets of column-specific parameters, each set of column-specific parameters being specific to anonymization of data of a respective column of the table included in the sub-set of columns, storing the view command within the database system, and receiving a query referencing the view, and in response, providing a data set including data from each column in the sub-set of columns, receiving an anonymized data set including anonymized data that is generated from the data set using the anonymization type, the static parameters, and the sets of column-specific parameters.

The underlying technical problem is solved by the subject-matter having the features of the independent claims. Additional embodiments are defined in the dependent claims. In some implementations, a method may include receiving a knowledge graph and a predefined parameter and processing the knowledge graph, with a set of quasi-identifier relations, to select a set of triples in the knowledge graph, each triple in the set of triples including a quasi-identifier relation. The method may include generating an equivalence first class based on the set of triples in the knowledge graph and determining a quantity of quasi-identifier attributes in the first class. The method may include comparing the quantity of quasi-identifier attributes to the predefined parameter to generate a first comparison and embedding the knowledge graph to generate an embedding space representation. The method may include identifying a similar neighbor second class and determining a first quantity of nodes in the first class and the second class. The method may include comparing the first quantity of nodes in the first class and the second class to the predefined parameter to generate a second comparison and identifying a similar neighbor third class. The method may include determining a second quantity of nodes in the first class and the third class and comparing the second quantity of nodes in the first class and the third class to the predefined parameter to generate a third comparison. The method may include merging the second class or the third class with the first class, based on the first comparison, the second comparison, and the third comparison, to generate anonymized nodes for the knowledge graph.

In some implementations, a device includes one or more memories, and one or more processors to receive a knowledge graph and a predefined parameter and process the knowledge graph to select a set of triples, with a set of quasi-identifier relations, to select a set of triples in the knowledge graph, each triple in the set of triples including a quasi-identifier relation. The one or more processors may generate an equivalence first class based on the set of triples in the knowledge graph and may determine a quantity of quasi-identifier attributes in the first class. The one or more processors may compare the quantity of quasi-identifier attributes to the predefined parameter to generate a first comparison and may embed the knowledge graph to generate an embedding space representation. The one or more processors may identify a similar neighbor second class and may determine a first quantity of nodes in the first class and the second class. The one or more processors may compare the first quantity of nodes in the first class and the second class to the predefined parameter to generate a second comparison and may identify a similar neighbor third class. The one or more processors may determine a second quantity of nodes in the first class and the third class and may compare the second quantity of nodes in the first class and the third class to the predefined parameter to generate a third comparison. The one or more processors may merge the second class or the third class with the first class, based on the first comparison, the second comparison, and the third comparison, to generate anonymized nodes for the knowledge graph, and may utilize the knowledge graph, with the anonymized nodes, to perform a calculation that satisfies one or more privacy conditions.

In some implementations, a non-transitory computer-readable medium may store a set of instructions that includes one or more instructions that, when executed by one or more processors of a device, cause the device to receive a knowledge graph and a predefined parameter, and process the knowledge graph, with a set of quasi-identifier relations, to select a set of triples in the knowledge graph, each triple in the set of triples including a quasi-identifier relation. The one or more instructions may cause the device to generate an equivalence first class based on the set of triples in the knowledge graph and determine a quantity of quasi-identifier attributes in the first class. The one or more instructions may cause the device to compare the quantity of quasi-identifier attributes to the predefined parameter to generate a first comparison and embed the knowledge graph to generate an embedding space representation. The one or more instructions may cause the device to identify a similar neighbor second class and determine a first quantity of nodes in the first class and the second class. The one or more instructions may cause the device to compare the first quantity of nodes in the first class and the second class to the predefined parameter to generate a second comparison and identify a similar neighbor third class. The one or more instructions may cause the device to determine a second quantity of nodes in the first class and the third class and compare the second quantity of nodes in the first class and the third class to the predefined parameter to generate a third comparison. The one or more instructions may cause the device to merge the second class or the third class with the first class, based on the first comparison, the second comparison, and the third comparison, to generate anonymized nodes for the knowledge graph, and utilize the knowledge graph, with the anonymized nodes, to determine new knowledge associated with a subject matter of the knowledge graph. The one or more instructions may cause the device to provide data identifying the new knowledge for display.

Information can be structured in the form of a knowledge graph that include nodes representing entities and edges representing relationships between entities. A knowledge graph acquires and integrates information into an ontology and applies a reasoner to derive new knowledge. In other words, a knowledge graph is a programmatic way to model a knowledge domain with the help of subject-matter experts, data interlinking, and machine learning models. However, maximizing utilization of a knowledge graph data is restricted by data privacy legal compliance requirements. Data privacy technology and models have been applied to standard relational databases and social graph data structures. Currently, there are no frameworks for applying data privacy in the context of knowledge graphs or knowledge graph embeddings. Thus, current methods for utilizing knowledge graphs waste human resources, computing resources (e.g., processing resources, memory resources, communication resources, and/or the like), networking resources, and/or the like associated with violating data privacy legal compliance requirements during utilization of knowledge graphs, unsuccessfully attempting to identify privacy data associated with knowledge graphs, and/or the like.

Some implementations described herein relate to an anonymization system that applies 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. For example, the anonymization system may receive a knowledge graph and a predefined parameter and may process the knowledge graph to select a set of triples in the knowledge graph, each triple in the set of triples including a quasi-identifier relation. The anonymization system may generate an equivalence first class based on the set of triples in the knowledge graph and may determine a quantity of quasi-identifier attributes in the first class. The anonymization system may compare the quantity of quasi-identifier attributes to the predefined parameter to generate a first comparison and may embed the knowledge graph to generate an embedding space representation. The anonymization system may identify a similar neighbor second class and may determine a first quantity of nodes in the first class and the second class. The anonymization system may compare the first quantity of nodes in the first class and the second class to the predefined parameter to generate a second comparison and may identify a similar neighbor third class. The anonymization system may determine a second quantity of nodes in the first class and the third class and may compare the second quantity of nodes in the first class and the third class to the predefined parameter to generate a third comparison. The anonymization system may merge the second class or the third class with the first class, based on the first comparison, the second comparison, and the third comparison, to generate anonymized nodes for the knowledge graph.

In this way, the anonymization system may apply 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. For example, the anonymization system may utilize a k-anonymization model that leverages a knowledge graph embedding as an approximate means to maximize data utility during a data privatization phase. The anonymization system may incorporate a differential privacy mechanism to provide privacy for sensitive attributes contained in the knowledge graph and may aid an end user in understanding trade-offs in privacy and utility. Thus, the anonymization system conserves human resources, computing resources, networking resources, and/or the like that would otherwise have been wasted by violating data privacy legal compliance requirements during utilization of knowledge graphs, unsuccessfully attempting to identify privacy data associated with knowledge graphs, and/or the like.

<FIG> are diagrams of an example implementation <NUM> described herein. Example implementation <NUM> may be associated with utilizing models for replacing existing enterprise software with new enterprise software. As shown in <FIG>, example implementation <NUM> includes a client device associated with an anonymization system. The client device may include a laptop computer, a mobile telephone, a desktop computer, and/or the like utilized by the user. The anonymization system may include a system that applies 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.

As shown in <FIG>, and by reference number <NUM>, the anonymization system may receive a knowledge graph, a predefined parameter, a sensitivity parameter, a noise multiplier parameter, and an acceptance value. The knowledge graph may include a graph that acquires and integrates information into an ontology and applies a reasoner to derive new knowledge. In some implementations, the knowledge graph is a programmatic way to model a knowledge domain with the help of subject-matter experts, data interlinking, and machine learning models. Data of the knowledge graph may need to be restricted due data privacy legal compliance requirements. For example, the knowledge graph may include private graph data, such as personal identifiers (e.g., "patient <NUM>," "person <NUM>," and/or the like), quasi-identifier relations (e.g., "has age," "has nationality," and/or the like), quasi-identifier attributes (e.g., "<NUM>," "<NUM>," "Irish," "Scottish," and/or the like) associated with the quasi-identifier relations, insensitive attributes, and/or the like.

The predefined parameter may include a k-anonymity value associated with a k-anonymity model to be applied to the knowledge graph. Given privacy-specific (e.g., person-specific) field-structured data, the k-anonymity model may produce data that guarantees that the privacy-specific data (e.g., data identifying individuals) of the produced data cannot be re-identified while the produced data remains useful. The produced data may include a k-anonymity property if the privacy-specific data provided in the produced data cannot be distinguished from at least k-<NUM> individuals whose information also appear in the produced data.

The sensitivity parameter may include a sensitivity value associated with a differential privacy model to be applied to the knowledge graph. The differential privacy model may publicly share information about a dataset by describing patterns of groups within the dataset (e.g., a distribution of data) while withholding information about individuals in the dataset. A model may be referred to as a differential privacy model if an observer seeing output of the model cannot tell if a particular individual's information was used to compute the output. In one example, the sensitivity parameter may include a value of one when changing any entry in a dataset causes an output of the differential privacy model to change by either zero or one.

The noise multiplier parameter may include a noise multiplier distribution associated with the differential privacy model. Adding controlled noise from predetermined distributions is a way of designing differentially private datasets and is useful for designing private mechanisms for real-valued functions on sensitive data. The noise multiplier parameter may include a Laplace mechanism, a Gaussian mechanism, and/or the like. The Laplace mechanism may add noise drawn from a Laplace distribution, while the Gaussian mechanism may add noise drawn from a Gaussian distribution.

The acceptance value may include a threshold epsilon (ε)-differential privacy score associated with the differential privacy model. The acceptance value may include a mathematical definition for privacy loss associated with a dataset. The acceptance value may ensure that an individual's privacy cannot be compromised by a dataset release if data associated with the individual is not in the dataset. The acceptance value may provide each individual approximately a same privacy that would result from having the data associated with the individual removed. This may ensure that statistical functions executed on the dataset do not overly depend on the data of any one individual.

As further shown in <FIG>, and by reference number <NUM>, the anonymization system may process the knowledge graph, with a quasi-identifier relation model, to select triples in the knowledge graph. Quasi-identifiers are pieces of information that are not of themselves unique identifiers but are sufficiently well-correlated with an entity that they can be combined with other quasi-identifiers to create a unique identifier. Quasi-identifiers can thus, when combined, become personally identifying information. In some implementations, the quasi-identifier relation model selects triples in the knowledge graph that include quasi-identifier relations. For example, the quasi-identifier relation model may select sets of triples in the knowledge graph, such as ["patient <NUM>," "has age," "<NUM>"], ["patient <NUM>," "has height," "<NUM>"], ["patient <NUM>," "has nationality," "Irish"], ["patient <NUM>," "has age," "<NUM>"], ["patient <NUM>," "has gender," "male"], ["patient <NUM>," "has age," "<NUM>"], ["patient <NUM>," "has gender," "male"], ["patient <NUM>," "has age," "<NUM>"], ["patient <NUM>," "has gender," "female"], and/or the like.

As shown in <FIG>, and by reference number <NUM>, the anonymization system may generate an equivalence first class based on the triples in the knowledge graph. For example, the anonymization system may map the quasi-identifier attributes connected to each personal entity by the quasi-identifier relations in the knowledge graph (e.g., the triples in the knowledge graph), and may determine equivalence classes based on the mapping (e.g., the equivalence first class). For example, if the knowledge graph includes ages and genders of individuals, the equivalence first class may include groups based on the ages and the genders (e.g., "<NUM> year old males," "<NUM> year old males," "<NUM> year old males," "<NUM> year old females," and/or the like).

As further shown in <FIG>, and by reference number <NUM>, the anonymization system may determine a quantity of quasi-identifier attributes in the first class. For example, the anonymization system may determine sizes of the equivalence classes. In other words, the anonymization system may determine quantities of individuals in the groups. For example, for the groups based on the ages and the genders, the anonymization system may determine that there are "<NUM>" "<NUM> year old males," that there are "<NUM>" "<NUM> year old males," that there are "<NUM>" "<NUM> year old males," that there are "<NUM>" "<NUM> year old females," and/or the like in the knowledge graph.

As further shown in <FIG>, and by reference number <NUM>, the anonymization system may compare the quantity of quasi-identifier attributes to the predefined parameter to generate a first comparison. For example, the anonymization system may compare the quantities of individuals in the groups (e.g., the quantity of quasi-identifier attributes) to the k-anonymity value (e.g., the predefined parameter) to generate the first comparison. If none of the quantities of individuals in the groups are greater than the k-anonymity value, the anonymization system may determine that k-anonymity is achieved for the k-anonymity value. If one or more of the quantities of individuals in corresponding one or more groups are greater than or equal to the k-anonymity value, the anonymization system may determine that k-anonymity is not achieved for the k-anonymity value (e.g., for the corresponding one or more groups).

As shown in <FIG>, and by reference number <NUM>, the anonymization system may embed the knowledge graph to generate an embedding space representation. For example, the anonymization system may process the triples of the knowledge graph, with a knowledge graph embedding model, to generate the embedding space representation (e.g., a latent space graph). The embedding space representation may represent entities and relations in the knowledge graph as elements in a continuous vector space, and the embedding space representation may provide a generalizable context about the knowledge graph that can be used to infer relations. In some implementations, the knowledge graph embedding model may include a translation based embedding model (e.g., TransE), a hyperplane translation based embedding model (e.g., TransH), a relationship space based embedding model (e.g., TransR), a Rescal model, a DistMult model, and/or the like.

As further shown in <FIG>, and by reference number <NUM>, the anonymization system may identify a similar neighbor second class. In some implementations, for each equivalence class, the anonymization system may determine a nearest equivalence class (e.g., the similar neighbor second class). For example, for the groups based on the ages and the genders, the anonymization system may determine that the "<NUM> year old males" group provided in the first class is nearest to a group of "<NUM> year old males" (e.g., the similar neighbor second class), may determine that "<NUM> year old females" group provided in the first class is nearest to a group of "<NUM> year old females" (e.g., the similar neighbor second class), and/or the like.

As further shown in <FIG>, and by reference number <NUM>, the anonymization system determines a first quantity of nodes in the first class and the second class. For example, the anonymization system may determine the quantity of nodes in the first class based on the sizes of the equivalence classes (e.g., the quantities of individuals in the groups). For example, for the groups based on the ages and the genders, the anonymization system may determine that there are "<NUM>" "<NUM> year old males," that there are "<NUM>" "<NUM> year old males," that there are "<NUM>" "<NUM> year old males," that there are "<NUM>" "<NUM> year old females," and/or the like. The anonymization system may determine the quantity of nodes in the second class based on sizes of the similar neighbor classes (e.g., the quantities of individuals). For example, for the groups based on the ages and the genders, the anonymization system may determine that there are "<NUM>" "<NUM> year old males," that there are "<NUM>" "<NUM> year old females," and/or the like.

As further shown in <FIG>, and by reference number <NUM>, the anonymization system may compare the first quantity to the predefined parameter to generate a second comparison. For example, the anonymization system may compare the quantities of individuals in the first class and the second class to the k-anonymity value (e.g., the predefined parameter) to generate the second comparison.

As shown in <FIG>, and by reference number <NUM>, the anonymization system may identify a similar neighbor third class. In some implementations, for each individual in each equivalence class, the anonymization system may determine a nearest non-group individual (e.g., the similar neighbor third class) in the embedding space representation. For example, for the groups based on the ages and the genders, the anonymization system may determine that ["person <NUM>," "<NUM>," "male"] provided in the first class is nearest to ["person <NUM>," "<NUM>," "male"] of the third class; that ["person <NUM>," "<NUM>," "male"] provided in the first class is nearest to ["person <NUM>," "<NUM>," "male"] of the third class; that ["person <NUM>," "<NUM>," "male"] provided in the first class is nearest to ["person <NUM>," "<NUM>," "male"] of the third class; and/or the like.

As further shown in <FIG>, and by reference number <NUM>, the anonymization system may determine a second quantity of nodes in the first class and the third class. For example, the anonymization system may determine the quantity of nodes in the first class based on the sizes of the equivalence classes (e.g., the quantities of individuals in the groups). For example, for the groups based on the ages and the genders, the anonymization system may determine that there are "<NUM>" "<NUM> year old males," that there are "<NUM>" "<NUM> year old males," that there are "<NUM>" "<NUM> year old males," that there are "<NUM>" "<NUM> year old females," and/or the like. The anonymization system may determine the quantity of nodes in the third class based on sizes of the similar neighbor classes (e.g., the quantities of individuals). For example, for the groups based on the ages and the genders, the anonymization system may determine that there are "<NUM>" "<NUM> year old males" (e.g., similar to person <NUM>), that there are "<NUM>" "<NUM> year old males" (e.g., similar to person <NUM>), that there are "<NUM>" "<NUM> year old males" (e.g., similar to person <NUM>), and/or the like.

As further shown in <FIG>, and by reference number <NUM>, the anonymization system may compare the second quantity to the predefined parameter to generate a third comparison. For example, the anonymization system may compare the quantities of individuals in the first class and the third class to the k-anonymity value (e.g., the predefined parameter) to generate the third comparison.

As shown in <FIG>, and by reference number <NUM>, the anonymization system may merge the second class or the third class with the first class, based on the first comparison, the second comparison, and the third comparison, to generate anonymized nodes for the knowledge graph. For example, the anonymization system may merge the second class with the first class, based on the first comparison, the second comparison, and the third comparison, to generate a first set of anonymized nodes for the knowledge graph. The anonymization system may merge the third class with the first class, based on the first comparison, the second comparison, and the third comparison, to generate a second set of anonymized nodes for the knowledge graph. The anonymization system may combine the first set of anonymized nodes and the second set of anonymized nodes to generate an anonymized knowledge graph.

In some implementations, the anonymization system may determine whether to merge the second class or the third class with the first class by determining a first size associated with combining the second class with the first class and determining a second size associated with combining the third class with the first class. If the first size is minimized above the predefined parameter (e.g., the k-anonymity value), then the anonymization system may merge the second class with the first class. If the second size is minimized above the predefined parameter (e.g., the k-anonymity value), then the anonymization system may merge the third class with the first class. If neither the first size nor the second size is minimized above the predefined parameter, but the first size is larger than the second size, then the anonymization system may merge the second class with the first class. If neither the first size nor the second size is minimized above the predefined parameter, but the second size is larger than the first size, then the anonymization system may merge the third class with the first class. If neither the first size nor the second size is minimized above the predefined parameter, and the first size is equivalent to the second size, then the anonymization system may randomly select the second class or the third class to merge with the first class.

As shown in <FIG>, and by reference number <NUM>, the anonymization system may partition the triples in the knowledge graph into a first set of sensitive triples and a second set of non-sensitive triples based on the sensitivity parameter. For example, the sensitivity parameter may include a parameter that ensures that sensitive data (e.g., personal identifiers, ages, genders, nationalities, and/or the like) of the knowledge graph is maintained in privacy. The anonymization system may analyze the triples in the knowledge graph and may identify triples that include sensitive data (e.g., satisfy the sensitivity parameter). The anonymization system may group the triples that include the sensitive data into the first set of sensitive triples. The anonymization system may identify triples that fail to include sensitive data (e.g., fail to satisfy the sensitivity parameter) and may group the triples that fail to include the sensitive data into the second set of non-sensitive triples.

As further shown in <FIG>, and by reference number <NUM>, the anonymization system may convert the first set into a first embedding space using a first stochastic descent model. For example, the anonymization system may process the first set of sensitive triples, with a stochastic gradient descent model, to convert the first set of sensitive triples into the first embedding space. The first embedding space may include a stochastic approximation of gradient descent optimization, since the first embedding space replaces an actual gradient (e.g., calculated from the entire first set of sensitive triples) with an estimated gradient (e.g., calculated from a randomly selected subset of the first set of sensitive triples).

As further shown in <FIG>, and by reference number <NUM>, the anonymization system may convert the second set into a second embedding space using a second stochastic descent model. For example, the anonymization system may process the second set of non-sensitive triples, with a stochastic gradient descent model, to convert the second set of non-sensitive triples into the second embedding space. The second embedding space may include a stochastic approximation of gradient descent optimization, since the second embedding space replaces an actual gradient (e.g., calculated from the entire second set of non-sensitive triples) with an estimated gradient (e.g., calculated from a randomly selected subset of the second set of non-sensitive triples).

As shown in <FIG>, and by reference number <NUM>, the anonymization system may add noise to the first embedding space using the noise multiplier parameter. For example, the anonymization system may add parameterized Gaussian noise to the first embedding space. In some implementations, the anonymization system adds enough noise to the first embedding space to hide data in the first embedding space and to generate a noisy first embedding space.

In some implementations, the anonymization system may utilize a clip value parameter to bound the first embedding space, prior to adding the noise to the first embedding space. For example, the first embedding space (e.g., gradients) may be represented as: <MAT> where b corresponds to a batch size, σ·C corresponds to a standard deviation of the Gaussian noise mechanism, and C corresponds to a threshold that controls clipping of each gradient. The gradient of a sample (xi) may be defined as: <MAT> where L corresponds to a loss function, and ∇ and θ correspond to parameters in a model to be optimized. A clipped gradient of a sample (xi) may be defined as: <MAT> where ∥xi∥<NUM> corresponds to an L<NUM> norm of g(xi).

As further shown in <FIG>, and by reference number <NUM>, the anonymization system may determine a differential privacy epsilon score based on the noisy first embedding space. The differential privacy epsilon score enables the anonymization system to balance privacy and accuracy levels with a positive value named epsilon (ε). If epsilon is small, then more privacy is preserved, but data accuracy is worse. If epsilon is large, privacy is worse, but data accuracy is preserved. Epsilon may include a value from zero to infinity. In some implementations, the anonymization system processes the noisy first embedding space, with an epsilon differential privacy model, to determine the differential privacy epsilon score.

As further shown in <FIG>, and by reference number <NUM>, the anonymization system may compare the differential privacy epsilon score to the acceptance value to generate privatized edges for the knowledge graph. For example, if the anonymization system determines that the differential privacy epsilon score satisfies the acceptance value (e.g., satisfies a privacy requirement for the knowledge graph), the anonymization system may generate privatized edges for the knowledge graph based on the differential privacy epsilon score. If the anonymization system determines that the differential privacy epsilon score fails to satisfy the acceptance value (e.g., fails to satisfy the privacy requirement for the knowledge graph), the anonymization system may modify the epsilon value and recalculate the differential privacy epsilon score until the differential privacy epsilon score satisfies the acceptance value.

As further shown in <FIG>, and by reference number <NUM>, the anonymization system may combine the anonymized nodes and the privatized edges to create an anonymized knowledge graph. For example, the anonymization system may combine the anonymized nodes, described above in connection with <FIG>, with the privatized edges to create the anonymized knowledge graph. In some implementations, the anonymization system provides the knowledge graph, with the anonymized nodes, for display to the client device, or provides the anonymized knowledge graph for display to the client device. In this way, the client device may utilize the anonymized knowledge graph without disclosing private information.

In some implementations, the anonymization system utilizes the knowledge graph, with the anonymized nodes, to perform a calculation that satisfies one or more privacy conditions or utilizes the anonymized knowledge graph to perform the calculation that satisfies the one or more privacy conditions. In this way, the anonymization system may utilize the anonymized knowledge graph without disclosing private information.

In some implementations, the anonymization system utilizes the knowledge graph, with the anonymized nodes, or the anonymized knowledge graph to determine new knowledge associated with a subject matter of the knowledge graph, and provides data identifying the new knowledge for display to the client device. In this way, the anonymization system may utilize the anonymized knowledge to determine new knowledge and without disclosing private information.

In some implementations, the anonymization system provides the knowledge graph, with the anonymized nodes, or the anonymized knowledge graph for display to the client device, and receives, from the client device, feedback associated with the knowledge graph. The feedback may indicate that privacy is not preserved by the anonymized knowledge graph. The anonymization system may increase a value associated with the predefined parameter, based on the feedback, to increase an anonymization associated with the anonymized nodes for the knowledge graph.

In this way, the anonymization system may apply 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. For example, the anonymization system may utilize a k-anonymization model that leverages a knowledge graph embedding as an approximate means to maximize data utility during a data privatization phase. The anonymization system may incorporate a differential privacy mechanism to provide privacy for sensitive attributes contained in the knowledge graph, and the anonymization system may aid an end user in understanding trade-offs in privacy and utility. Thus, the anonymization system conserves human resources, computing resources, networking resources, and/or the like that would otherwise have been wasted by violating data privacy legal compliance requirements during utilization of knowledge graphs, unsuccessfully attempting to identify privacy data associated with knowledge graphs, and/or the like.

<FIG> is a diagram of an example environment <NUM> in which systems and/or methods described herein may be implemented. As shown in <FIG>, environment <NUM> may include an anonymization system <NUM>, which may include one or more elements of and/or may execute within a cloud computing system <NUM>. The cloud computing system <NUM> may include one or more elements <NUM>-<NUM>, as described in more detail below. As further shown in <FIG>, environment <NUM> may include a network <NUM> and/or a client device <NUM>. Devices and/or elements of environment <NUM> may interconnect via wired connections and/or wireless connections.

The cloud computing system <NUM> includes computing hardware <NUM>, a resource management component <NUM>, a host operating system (OS) <NUM>, and/or one or more virtual computing systems <NUM>. The resource management component <NUM> may perform virtualization (e.g., abstraction) of computing hardware <NUM> to create the one or more virtual computing systems <NUM>. Using virtualization, the resource management component <NUM> enables a single computing device (e.g., a computer, a server, and/or the like) to operate like multiple computing devices, such as by creating multiple isolated virtual computing systems <NUM> from computing hardware <NUM> of the single computing device. In this way, computing hardware <NUM> can operate more efficiently, with lower power consumption, higher reliability, higher availability, higher utilization, greater flexibility, and lower cost than using separate computing devices.

Computing hardware <NUM> includes hardware and corresponding resources from one or more computing devices. For example, computing hardware <NUM> may include hardware from a single computing device (e.g., a single server) or from multiple computing devices (e.g., multiple servers), such as multiple computing devices in one or more data centers. As shown, computing hardware <NUM> may include one or more processors <NUM>, one or more memories <NUM>, one or more storage components <NUM>, and/or one or more networking components <NUM>. Examples of a processor, a memory, a storage component, and a networking component (e.g., a communication component) are described elsewhere herein.

The resource management component <NUM> includes a virtualization application (e.g., executing on hardware, such as computing hardware <NUM>) capable of virtualizing computing hardware <NUM> to start, stop, and/or manage one or more virtual computing systems <NUM>. For example, the resource management component <NUM> may include a hypervisor (e.g., a bare-metal or Type <NUM> hypervisor, a hosted or Type <NUM> hypervisor, and/or the like) or a virtual machine monitor, such as when the virtual computing systems <NUM> are virtual machines <NUM>. Additionally, or alternatively, the resource management component <NUM> may include a container manager, such as when the virtual computing systems <NUM> are containers <NUM>. In some implementations, the resource management component <NUM> executes within and/or in coordination with a host operating system <NUM>.

A virtual computing system <NUM> includes a virtual environment that enables cloud-based execution of operations and/or processes described herein using computing hardware <NUM>. As shown, a virtual computing system <NUM> may include a virtual machine <NUM>, a container <NUM>, a hybrid environment <NUM> that includes a virtual machine and a container, and/or the like. A virtual computing system <NUM> may execute one or more applications using a file system that includes binary files, software libraries, and/or other resources required to execute applications on a guest operating system (e.g., within the virtual computing system <NUM>) or the host operating system <NUM>.

Although the anonymization system <NUM> may include one or more elements <NUM>-<NUM> of the cloud computing system <NUM>, may execute within the cloud computing system <NUM>, and/or may be hosted within the cloud computing system <NUM>, in some implementations, the anonymization system <NUM> may not be cloud-based (e.g., may be implemented outside of a cloud computing system) or may be partially cloud-based. For example, the anonymization system <NUM> may include one or more devices that are not part of the cloud computing system <NUM>, such as device <NUM> of <FIG>, which may include a standalone server or another type of computing device. The anonymization system <NUM> may perform one or more operations and/or processes described in more detail elsewhere herein.

Network <NUM> includes one or more wired and/or wireless networks. For example, network <NUM> may include a cellular network, a public land mobile network (PLMN), a local area network (LAN), a wide area network (WAN), a private network, the Internet, and/or the like, and/or a combination of these or other types of networks. The network <NUM> enables communication among the devices of environment <NUM>.

Client device <NUM> includes one or more devices capable of receiving, generating, storing, processing, and/or providing information associated with a knowledge graph, as described elsewhere herein. Client device <NUM> may include a communication device and/or a computing device. For example, client device <NUM> may include a wireless communication device, a mobile phone, a user equipment, a laptop computer, a tablet computer, a desktop computer, a gaming console, a set-top box, a wearable communication device (e.g., a smart wristwatch, a pair of smart eyeglasses, a head mounted display, or a virtual reality headset), or a similar type of device.

<FIG> is a diagram of example components of a device <NUM>, which may correspond to anonymization system <NUM> and/or client device <NUM>. In some implementations, anonymization system <NUM> and/or client device <NUM> may include one or more devices <NUM> and/or one or more components of device <NUM>. As shown in <FIG>, device <NUM> may include a bus <NUM>, a processor <NUM>, a memory <NUM>, a storage component <NUM>, an input component <NUM>, an output component <NUM>, and a communication component <NUM>.

Bus <NUM> includes a component that enables wired and/or wireless communication among the components of device <NUM>. Processor <NUM> includes a central processing unit, a graphics processing unit, a microprocessor, a controller, a microcontroller, a digital signal processor, a field-programmable gate array, an application-specific integrated circuit, and/or another type of processing component. Processor <NUM> is implemented in hardware, firmware, or a combination of hardware and software. In some implementations, processor <NUM> includes one or more processors capable of being programmed to perform a function. Memory <NUM> includes a random access memory, a read only memory, and/or another type of memory (e.g., a flash memory, a magnetic memory, and/or an optical memory).

Storage component <NUM> stores information and/or software related to the operation of device <NUM>. For example, storage component <NUM> may include a hard disk drive, a magnetic disk drive, an optical disk drive, a solid-state disk drive, a compact disc, a digital versatile disc, and/or another type of non-transitory computer-readable medium. Input component <NUM> enables device <NUM> to receive input, such as user input and/or sensed inputs. For example, input component <NUM> may include a touch screen, a keyboard, a keypad, a mouse, a button, a microphone, a switch, a sensor, a global positioning system component, an accelerometer, a gyroscope, and/or an actuator. Output component <NUM> enables device <NUM> to provide output, such as via a display, a speaker, and/or one or more light-emitting diodes. Communication component <NUM> enables device <NUM> to communicate with other devices, such as via a wired connection and/or a wireless connection. For example, communication component <NUM> may include a receiver, a transmitter, a transceiver, a modem, a network interface card, and/or an antenna.

Device <NUM> may perform one or more processes described herein. For example, a non-transitory computer-readable medium (e.g., memory <NUM> and/or storage component <NUM>) may store a set of instructions (e.g., one or more instructions, code, software code, and/or program code) for execution by processor <NUM>. Processor <NUM> may execute the set of instructions to perform one or more processes described herein. In some implementations, execution of the set of instructions, by one or more processors <NUM>, causes the one or more processors <NUM> and/or the device <NUM> to perform one or more processes described herein. In some implementations, hardwired circuitry may be used instead of or in combination with the instructions to perform one or more processes described herein.

<FIG> is a flowchart of an example process <NUM> for 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. In some implementations, one or more process blocks of <FIG> may be performed by a device (e.g., anonymization system <NUM>). In some implementations, one or more process blocks of <FIG> may be performed by another device or a group of devices separate from or including the device, such as a client device (e.g., client device <NUM>). Additionally, or alternatively, one or more process blocks of <FIG> may be performed by one or more components of device <NUM>, such as processor <NUM>, memory <NUM>, storage component <NUM>, input component <NUM>, output component <NUM>, and/or communication component <NUM>.

As shown in <FIG>, process <NUM> may include receiving a knowledge graph and a predefined parameter (block <NUM>). For example, the device may receive a knowledge graph and a predefined parameter, as described above.

As further shown in <FIG>, process <NUM> may include processing the knowledge graph to select a set of triples in the knowledge graph, each triple in the set of triples including a quasi-identifier relation (block <NUM>). For example, the device may process the knowledge graph to select a set of triples in the knowledge graph, each triple in the set of triples including a quasi-identifier relation, as described above.

As further shown in <FIG>, process <NUM> may include generating an equivalence first class based on the set of triples in the knowledge graph (block <NUM>). For example, the device may generate an equivalence first class based on the set of triples in the knowledge graph, as described above.

As further shown in <FIG>, process <NUM> may include determining a quantity of quasi-identifier attributes in the first class (block <NUM>). For example, the device may determine a quantity of quasi-identifier attributes in the first class, as described above.

As further shown in <FIG>, process <NUM> may include comparing the quantity of quasi-identifier attributes to the predefined parameter to generate a first comparison (block <NUM>). For example, the device may compare the quantity of quasi-identifier attributes to the predefined parameter to generate a first comparison, as described above.

As further shown in <FIG>, process <NUM> may include embedding the knowledge graph to generate an embedding space representation (block <NUM>). For example, the device may embed the knowledge graph to generate an embedding space representation, as described above.

As further shown in <FIG>, process <NUM> may include identifying a similar neighbor second class (block <NUM>). For example, the device may identify a similar neighbor second class, as described above.

As further shown in <FIG>, process <NUM> may include determining a first quantity of nodes in the first class and the second class (block <NUM>). For example, the device may determine a first quantity of nodes in the first class and the second class, as described above.

As further shown in <FIG>, process <NUM> may include comparing the first quantity of nodes in the first class and the second class to the predefined parameter to generate a second comparison (block <NUM>). For example, the device may compare the first quantity of nodes in the first class and the second class to the predefined parameter to generate a second comparison, as described above.

As further shown in <FIG>, process <NUM> may include identifying a similar neighbor third class (block <NUM>). For example, the device may identify a similar neighbor third class, as described above.

As further shown in <FIG>, process <NUM> may include determining a second quantity of nodes in the first class and the third class (block <NUM>). For example, the device may determine a second quantity of nodes in the first class and the third class, as described above.

As further shown in <FIG>, process <NUM> may include comparing the second quantity of nodes in the first class and the third class to the predefined parameter to generate a third comparison (block <NUM>). For example, the device may compare the second quantity of nodes in the first class and the third class to the predefined parameter to generate a third comparison, as described above.

As further shown in <FIG>, process <NUM> may include merging the second class or the third class with the first class, based on the first comparison, the second comparison, and the third comparison, to generate anonymized nodes for the knowledge graph (block <NUM>). For example, the device may merge the second class or the third class with the first class, based on the first comparison, the second comparison, and the third comparison, to generate anonymized nodes for the knowledge graph, as described above.

In a first implementation, process <NUM> includes providing the knowledge graph, with the anonymized nodes, for display, or utilizing the knowledge graph, with the anonymized nodes, to perform a calculation that satisfies one or more privacy conditions.

In a second implementation, alone or in combination with the first implementation, process <NUM> includes generating privatized edges for the knowledge graph based on a differential privacy model and combining the anonymized nodes and the privatized edges to create an anonymized knowledge graph.

In a third implementation, alone or in combination with one or more of the first and second implementations, process <NUM> includes providing the anonymized knowledge graph for display or utilizing the anonymized knowledge graph to perform a calculation that satisfies one or more privacy conditions.

In a fourth implementation, alone or in combination with one or more of the first through third implementations, the predefined parameter includes an anonymization value.

In a fifth implementation, alone or in combination with one or more of the first through fourth implementations, 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.

In a sixth implementation, alone or in combination with one or more of the first through fifth implementations, embedding the knowledge graph to generate the embedding space representation comprises processing the set of triples in the knowledge graph, with a knowledge graph embedding model, to generate the embedding space representation.

In a seventh implementation, alone or in combination with one or more of the first through sixth implementations, the embedding space representation is a latent space graph.

In an eighth implementation, alone or in combination with one or more of the first through seventh implementations, merging the second class or the third class with the first class, based on the first comparison, the second comparison, and the third comparison, to generate the anonymized nodes for the knowledge graph includes merging the second class with the first class, based on the first comparison, the second comparison, and the third comparison, to generate a first set of anonymized nodes for the knowledge graph; merging the third class with the first class, based on the first comparison, the second comparison, and the third comparison, to generate a second set of anonymized nodes for the knowledge graph; and combining the first set of anonymized nodes and the second set of anonymized nodes to generate an anonymized knowledge graph.

In a ninth implementation, alone or in combination with one or more of the first through eighth implementations, the anonymized nodes prevent identification of one or more of personal identifiers, the quasi-identifier attributes, insensitive attributes, or quasi-identifier predicates.

In a tenth implementation, alone or in combination with one or more of the first through ninth implementations, process <NUM> includes utilizing the knowledge graph, with the anonymized nodes, to determine new knowledge associated with a subject matter of the knowledge graph, and providing data identifying the new knowledge for display.

In an eleventh implementation, alone or in combination with one or more of the first through tenth implementations, process <NUM> includes increasing a value associated with the predefined parameter to increase an anonymization associated with the anonymized nodes for the knowledge graph.

In a twelfth implementation, alone or in combination with one or more of the first through eleventh implementations, process <NUM> includes providing the knowledge graph, with the anonymized nodes, for display to a client device; receiving, from the client device, feedback associated with the knowledge graph; and increasing a value associated with the predefined parameter, based on the feedback, to increase an anonymization associated with the anonymized nodes for the knowledge graph.

The present disclosure relates to 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. The foregoing disclosure provides illustration and description but is not intended to be exhaustive or to limit the implementations to the precise form disclosed. Modifications may be made in light of the above disclosure or may be acquired from practice of the implementations.

As used herein, satisfying a threshold may, depending on the context, refer to a value being greater than the threshold, greater than or equal to the threshold, less than the threshold, less than or equal to the threshold, equal to the threshold, and/or the like, depending on the context.

Although particular combinations of features are recited in the claims and/or disclosed in the specification, these combinations are not intended to limit the disclosure of various implementations.

Claim 1:
A method, comprising:
receiving (<NUM>), by a device, a knowledge graph and a predefined parameter, wherein the predefined parameter includes a k-anonymity value associated with a k-anonymity model to be applied to the knowledge graph;
processing (<NUM>), by the device, the knowledge graph to select a set of triples in the knowledge graph, each triple in the set of triples including a quasi-identifier relation;
generating (<NUM>), by the device, an equivalence first class based on the set of triples in the knowledge graph;
determining (<NUM>), by the device, a quantity of quasi-identifier attributes in the equivalence first class;
comparing (<NUM>), by the device, the quantity of quasi-identifier attributes to the predefined parameter to generate a first comparison;
embedding (<NUM>), by the device, the knowledge graph to generate an embedding space representation;
identifying (<NUM>), by the device, a similar neighbor second class, wherein the similar neighbor second class is determined as a nearest equivalence class for the equivalence first class;
determining (<NUM>), by the device, a first quantity of nodes in the first equivalence class and the similar neighbor second class;
comparing (<NUM>), by the device, the first quantity of nodes in the first equivalence class and the similar neighbor second class to the predefined parameter to generate a second comparison;
identifying (<NUM>), by the device, a similar neighbor third class, wherein the similar neighbor third class is determined as a nearest non-group individual in the embedding space representation for each individual in each equivalence class;
determining (<NUM>), by the device, a second quantity of nodes in the first equivalence class and the similar neighbor third class;
comparing (<NUM>), by the device, the second quantity of nodes in the first equivalence class and the similar neighbor third class to the predefined parameter to generate a third comparison; and
merging (<NUM>), by the device, the similar neighbor second class or the similar neighbor third class with the first equivalence class, based on the first comparison, the second comparison, and the third comparison, to generate anonymized nodes for the knowledge graph.