Mechanisms for Privately Sharing Semi-Structured Data

• US 20110078143A1
• Filed: 09/29/2009
• Published: 03/31/2011
• Est. Priority Date: 09/29/2009
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Aggarwal, Charu C.
• Granted Patent: US 9,471,645 B2
• Time in Patent Office: Days
• US Class Current: 707/737
• CPC Class Codes: G06F 16/2465 Query processing support for facilitating data mining operations in structured databases
• CPC Class Codes: G06F 16/285 Clustering or classification

Abstract

Mechanisms are provided for anonymizing data comprising a plurality of graph data sets. The mechanisms receive input data comprising a plurality of graph data sets. Each graph data set comprises data for generating a separate graph from graphs associated with other graph data sets. The mechanisms perform clustering on the graph data sets to generate a plurality of clusters. At least one cluster of the plurality of clusters comprises a plurality of graph data sets. Other clusters in the plurality of clusters comprise one or more graph data sets. The mechanisms also determine, for each cluster in the plurality of clusters, aggregate properties of the cluster. Moreover, the mechanisms generate, for each cluster in the plurality of clusters, pseudo-synthetic data representing the cluster, from the determined aggregate properties of the clusters.

Claims

1. A method, in a data processing system having a processor, for anonymizing data comprising a plurality of graph data sets, comprising:

receiving, by the processor of the data processing system, input data comprising a plurality of graph data sets, wherein each graph data set comprises data for generating a separate graph from graphs associated with other graph data sets;

performing, by the processor, clustering on the graph data sets to generate a plurality of clusters, wherein at least one cluster of the plurality of clusters comprises a plurality of graph data sets and wherein other clusters in the plurality of clusters comprise one or more graph data sets;

determining, by the processor, for each cluster in the plurality of clusters, an aggregate property of the cluster; and

generating, by the processor, for each cluster in the plurality of clusters, synthetic data representing the cluster, from the determined aggregate properties of the clusters.

2. The method of claim 1, further comprising receiving, by the processor, an anonymity level value k, wherein each cluster in the plurality of clusters comprises at least k number of graphs.

3. The method of claim 1, wherein the aggregate property of the cluster comprises a set of frequent sub-graphs of the cluster.

4. The method of claim 1, wherein performing clustering on the graph data sets to generate a plurality of clusters comprises:

creating an initial set of seed graphs; and

assigning, for each graph in the input data, the graph to a closest seed graph to generate an initial plurality of clusters.

5. The method of claim 4, wherein performing clustering on the graph data sets to generate a plurality of clusters further comprises:

iteratively performing a process comprising;

using a frequent pattern mining operation on the initial plurality of clusters to recreate a new improved set of seed graphs;

determining if the process has reached a convergence state; and

in response to the process not having reached a convergence state, assigning graphs in the input data to a closest seed graph in the improved set of seed graphs.

6. The method of claim 1, wherein determining, for each cluster in the plurality of clusters, an aggregate property of the cluster comprises determining a relative frequency of each edge in the cluster, wherein the relative frequency is a measure of a number of times that an edge appears in each of the graphs of the cluster.

7. The method of claim 6, wherein determining, for each cluster in the plurality of clusters, an aggregate property of the cluster further comprises:

determining a correlation between every pair of edges in the cluster as defined by a coefficient of correlation of the presence of the edges between a pair of graphs in the cluster; and

storing results of determining the correlation between every pair of edges in a correlation matrix data structure.

8. The method of claim 7, wherein generating, for each cluster in the plurality of clusters, synthetic data representing the cluster comprises:

generating eigenvectors of a corresponding covariance matrix based on the correlation matrix data structure; and

generating synthetic data for each cluster in the plurality of clusters based on the generated eigenvectors.

9. The method of claim 8, wherein generating synthetic data for each cluster in the plurality of clusters based on the generated eigenvectors comprises:

generating data points for each cluster based on the eigenvectors;

applying a rounding operation to the data points generated based on the eigenvectors to thereby generate binary values based on the data points generated based on the eigenvectors; and

reporting the binary values as an anonymized data set for the input data.

10. The method of claim 9, further comprising:

executing one or more applications on the anonymized data set to perform an operation on the anonymized data set, wherein the operation is one of a data mining operation or a classification operation.

11. A computer program product comprising a computer readable storage medium having a computer readable program recorded thereon, wherein the computer readable program, when executed on a computing device, causes the computing device to:

receive input data comprising a plurality of graph data sets, wherein each graph data set comprises data for generating a separate graph from graphs associated with other graph data sets;

perform clustering on the graph data sets to generate a plurality of clusters, wherein at least one cluster of the plurality of clusters comprises a plurality of graph data sets and wherein other clusters in the plurality of clusters comprise one or more graph data sets;

determine for each cluster in the plurality of clusters, an aggregate property of the cluster; and

generate for each cluster in the plurality of clusters, synthetic data representing the cluster, from the determined aggregate properties of the clusters.

12. The computer program product of claim 11, wherein the computer readable program further causes the computing device to receive an anonymity level value k, wherein each cluster in the plurality of clusters comprises at least k number of graphs.

13. The computer program product of claim 11, wherein the aggregate property of the cluster comprises a set of frequent sub-graphs of the cluster.

14. The computer program product of claim 11, wherein the computer readable program causes the computing device to perform clustering on the graph data sets to generate a plurality of clusters by:

creating an initial set of seed graphs; and

assigning, for each graph in the input data, the graph to a closest seed graph to generate an initial plurality of clusters.

15. The computer program product of claim 14, wherein the computer readable program causes the computing device to perform clustering on the graph data sets to generate a plurality of clusters further by:

iteratively performing a process comprising;

using a frequent pattern mining operation on the initial plurality of clusters to recreate a new improved set of seed graphs;

determining if the process has reached a convergence state; and

in response to the process not having reached a convergence state, assigning graphs in the input data to a closest seed graph in the improved set of seed graphs.

16. The computer program product of claim 11, wherein the computer readable program causes the computing device to determine, for each cluster in the plurality of clusters, an aggregate property of the cluster by determining a relative frequency of each edge in the cluster, wherein the relative frequency is a measure of a number of times that an edge appears in each of the graphs of the cluster.

17. The computer program product of claim 16, wherein the computer readable program further causes the computing device to determine, for each cluster in the plurality of clusters, an aggregate property of the cluster by:

determining a correlation between every pair of edges in the cluster as defined by a coefficient of correlation of the presence of the edges between a pair of graphs in the cluster; and

storing results of determining the correlation between every pair of edges in a correlation matrix data structure.

18. The computer program product of claim 17, wherein the computer readable program further causes the computing device to generate, for each cluster in the plurality of clusters, synthetic data representing the cluster by:

generating eigenvectors of a corresponding covariance matrix based on the correlation matrix data structure; and

generating synthetic data for each cluster in the plurality of clusters based on the generated eigenvectors.

19. The computer program product of claim 18, wherein the computer readable program further causes the computing device to generate synthetic data for each cluster in the plurality of clusters based on the generated eigenvectors by:

generating data points for each cluster based on the eigenvectors;

applying a rounding operation to the data points generated based on the eigenvectors to thereby generate binary values based on the data points generated based on the eigenvectors; and

reporting the binary values as an anonymized data set for the input data.

20. An apparatus, comprising:

a processor; and

a memory coupled to the processor, wherein the memory comprises instructions which, when executed by the processor, cause the processor to;

receive input data comprising a plurality of graph data sets, wherein each graph data set comprises data for generating a separate graph from graphs associated with other graph data sets;

perform clustering on the graph data sets to generate a plurality of clusters, wherein at least one cluster of the plurality of clusters comprises a plurality of graph data sets and wherein other clusters in the plurality of clusters comprise one or more graph data sets;

determine for each cluster in the plurality of clusters, an aggregate property of the cluster; and

generate for each cluster in the plurality of clusters, synthetic data representing the cluster, from the determined aggregate properties of the clusters.