Concealing sensitive patterns from linked data graphs
A method, system and computer program product for preventing sensitive pattern disclosures from Linked Data graphs. The proposed method (i) receives as input a Linked Data graph and a set of query patterns that correspond to sensitive knowledge that needs to be concealed, and (b) minimally distorts the Linked Data graph to generate a sanitized counterpart (graph) in which only the non-sensitive patterns can be discovered. The method supports a variety of utility functions, which it optimizes during the graph sanitization process. The resulting, sanitized graph can be subsequently used for publishing and/or querying purposes.
1. A method to conceal sensitive patterns from Linked Data Graphs comprising:
receiving at a hardware processor, data representing a Linked Data graph form (data graph G) and a set of patterns S to be concealed in said data graph G;
using the hardware processor to de-reference from the received data Uniform Resource Indicators (URIs) in the data graph G;
using the hardware processor to compute inferences from the de-referenced data graph G structure;
using the hardware processor to extract said patterns from said data graph G based on said computed inferences;
using the hardware processor to compute for each pattern extracted its bindings
in data graph G which lead to the discovery of the patterns S; and
using said hardware processor to remove each of the one or more bindings in the data graph G by suppressing one or more of: nodes, links between nodes, or nodes and links between nodes to form a new data graph G′ such that the patterns discoverable in G, cannot be discovered in graph G′, and
using said hardware processor to render said new data graph G′ in a form suitable for publishing over a communications network and accessible via a browser-based user device.
2. The method of claim 1 , wherein said one or more bindings are removed in a manner to optimize a given utility function.
3. The method of claim 2 , wherein the and
suppressing one or more of: nodes/links between nodes from the graph G is based on said given utility function.
4. The method of claim 3 , further comprising:
iteratively repeating said de-referencing, inferences computing and said node/link suppressing until all the patterns in said set S are non-discoverable in said new Linked Data graph G′.
5. The method of claim 3 , wherein said de-referencing URIs in the Linked Data graph G and computing inferences are repeated for up to r times.
6. The method of claim 1 , wherein said patterns are based upon one of: a priori knowledge of a user and data mining for patterns in graph G as specified by a user.
7. The method of claim 2 , wherein said patterns are represented as queries whose answers yield the patterns, one or more said queries representing patterns not to be concealed in said graph being answerable in said new Linked Data graph G′ with a maximal utility based on the utility function.
8. A system for concealing sensitive patterns from Linked Data Graphs comprising:
a memory storage device;
a hardware processor programmed with instructions from said memory storage device to configure said hardware processor to:
receive data representing a Linked Data graph form (data graph G);
receive data representing a set of patterns to be concealed in said data graph G;
de-reference from the received data Uniform Resource Indicators (URIs) in the data graph G;
compute inferences from the de-referenced data graph G structure;
extract said patterns from said data graph G based on said computed inferences;
compute for each pattern extracted its bindings
in data graph G which lead to the discovery of the patterns; and
remove each of the one or more bindings in the data graph G by suppressing one or more of: nodes, links between nodes, or nodes and links between nodes to form a new data graph G′ such that said patterns discoverable in G, cannot be discovered in graph G′, and
render said new data graph G′ in a form suitable for publishing over a communications network and accessible via a browser-based user device.
9. The system of claim 8 , wherein said hardware processor is further configured to:
remove the bindings in a manner to optimize a given utility function.
10. The system of claim 9 , wherein said hardware processor is further configured to:
suppress one or more of: nodes/links from the graph based on said given utility function.
11. The system of claim 10 , wherein the URI de-referencing, inferences computing and said node/link suppressing are iteratively repeated until all the patterns in set S are non-discoverable in said new Linked Data graph G′.
12. The system of claim 11 , wherein said de-referencing URIs in the Linked Data graph G and computing inferences are repeated for up to r times.
13. The system of claim 8 , wherein said patterns are based upon one of: a priori knowledge of a user and data mining for patterns in graph G as specified by a user.
14. The system of claim 8 , wherein said patterns are represented as queries whose answers yield the patterns, one or more said queries representing patterns not to be concealed in said graph being answerable in said new Linked Data graph G′, with a maximal utility based on the given utility function.
15. A computer program product to conceal sensitive patterns from Linked Data Graphs 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:
receiving data representing a Linked Data graph form (data graph G);
receiving data representing a set of patterns to be concealed in said data graph G,
de-referencing from the received data Uniform Resource Indicators (URIs) in the data graph G;
computing inferences from the de-referenced data graph G structure;
extracting said patterns from said data graph G based on said computed inferences;
computing for each pattern extracted its bindings
in data graph G which lead to the discovery of the patterns;
removing each of the one or more bindings in the said data graph G by suppressing one or more of: nodes, links between nodes, or nodes and links between nodes to form a new data graph G′ such that said sensitive patterns discoverable in G, cannot be discovered in graph G′, and
rendering said new data graph G′ in a form suitable for publishing over a communications network and accessible via a browser-based user device.
16. The computer program product of claim 15 , wherein the one or more bindings are removed in a manner to optimize a given utility function.
17. The computer program product of claim 16 , wherein said
suppressing one or more of: nodes/links from the graph is based on said utility function.
18. The computer program product of claim 17 , further comprising:
iteratively repeating said de-referencing, inferences computing and said node/link suppressing until all the patterns in said set S are non-discoverable in said new Linked Data graph G′.
19. The computer program product of claim 17 , wherein said de-referencing URIs in the Linked Data graph G and computing inferences are repeated for up to r times.
20. The computer program product of claim 15 , wherein said patterns are represented as queries whose answers yield the patterns, one or more said queries representing patterns not to be concealed in said graph of queries being answerable in said new Linked Data graph G′ with a maximal utility based on the given utility function.