Secure zones in knowledge graph

Patent metadata

Field	Value
Publication number	US-10754963-B2
Application number	US-201815904531-A
Country	US
Kind code	B2
Filing date	Feb 26, 2018
Priority date	Feb 26, 2018
Publication date	Aug 25, 2020
Grant date	Aug 25, 2020

Abstract

Access in a knowledge graph, comprising nodes and edges connecting two or more nodes, is controlled by assigning each node to a non-intersecting zone. A first and second zone identifier, each indicative of a zone occupied by a node where an edge ends, are each stored. Determining an access graph comprising an access node for each zone, access edges representing edges between the zones, and a first list of the zones. Each entry in the first list relates to a zone and a second list of node identifiers, each indicative of a node occupying the zone. A first and second access control list, each related to a zone where an access edge ends and to which a access node in the access graph relates, are stored in each access edge.

First claim

What is claimed is:

1. A method for controlling access in a knowledge graph, the method comprising:
assigning each node in a knowledge graph to a zone of one or more non-intersecting zones, the knowledge graph comprising two or more nodes and one or more edges, each of the one or more edges connecting two of the two or more nodes;
determining an access graph comprising an access node for each zone and access edges representing one or more edges between the one or more non-intersecting zones, the access graph further comprising a first list of the one or more non-intersecting zones, the first list comprising one or more entries, each entry related to a zone and to a second list of node identifiers, each node identifier indicative of a node assigned to the zone;
storing a first zone identifier indicative of a first zone that is occupied by a first node where an edge ends and a second zone identifier indicative of a second zone that is occupied by a second node where the edge ends;
storing a first access control list and a second access control list in each access edge, the first access control list relating to a first zone where an access edge ends and to which a first access node in the access graph relates, and the second access control list relating to a second zone where the access edge ends to which a second access node in said access graph relates;
identifying a starting node on the knowledge graph;
identifying a target node on the knowledge graph; and
determining a path of the lowest cost between the starting node and the target node, wherein the determining is based on a set of weights of a set of edges between the starting node and the target node.

2. The method of claim 1 , further comprising:
determining an access right to the target node, when a knowledge graph edge in a path to the target node crosses a zone border, by referring to an access edge in the access graph relating to the knowledge graph edge; and
determining the access right to the target node of the knowledge graph by referring to a corresponding access control list stored in the access edge of the access graph relating to a zone containing the target node of the knowledge graph.

3. The method of claim 1 , further comprising adding a new node to the access graph by:
identifying, in the knowledge graph, one or more edges relating to the new node;
identifying, in the knowledge graph, each node related to the one or more edges;
determining that all nodes relating to the one or more edges belong to one zone; and
adding a node identifier indicative of the new node to the second list of nodes related to the one zone.

4. The method of claim 3 , further comprising:
determining that a new edge of the new node crosses a zone border to a second zone;
determining no access edge exists between the one zone of the new node and the second zone; and
adding an access edge to the access graph between a first access node relating to the one zone and a second access node related to the second zone.

5. The method of claim 3 , further comprising:
determining there is only one edge between a first zone and a second zone of the knowledge graph;
determining the one edge is to be removed from the knowledge graph; and
removing a corresponding access edge from the access graph between a first access node representing the first zone and a second access node representing the second zone.

6. The method of claim 3 , wherein one access edge of the access graph is related to a plurality of edges between nodes of two zones of the knowledge graph.

7. The method of claim 1 , wherein a first zone lies within a second zone.

8. The method of claim 1 , wherein a change in a structure of the knowledge graph is treated as a removal of an edge and an adding of an edge.

9. The method of claim 1 , further comprising:
determining no access rights exist to the target node when starting from a starting node connected via an edge to the target node;
and
accessing another node via another edge with a next lowest cost points when compared to the cost points associated with the edge to the target node for which no access rights exist.

10. A system for controlling access in a knowledge graph, the system comprising:
an assignment unit adapted for assigning each node in a knowledge graph to a zone of one or more non-intersecting zones, the knowledge graph comprising two or more nodes and one or more edges, each of the one or more edges connecting two of the two or more nodes;
a determination unit adapted for determining an access graph comprising an access node for each zone and access edges representing one or more edges between the one or more non-intersecting zones, the access graph further comprising a first list of the one or more non-intersecting zones, the first list comprising one or more entries, each entry related to a zone and to a second list of node identifiers, each node identifier indicative of a node assigned to the zone; and
a storage module adapted for storing a first access control list and a second access control list in each access edge, the first access control list relating to a first zone where an access edge ends and to which a first access node in the access graph relates, and the second access control list relating to a second zone where the access edge ends to which a second access node in said access graph relates;
wherein the determining unit is further adapted for:
identifying a starting node on the knowledge graph;
identifying a target node on the knowledge graph; and
determining a path of the lowest cost between the starting node and the target node, wherein the determining is based on a set of weights of a set of edges between the starting node and the target node.

11. The system of claim 10 , further comprising an access right determination unit adapted for:
determining an access right to the target node, when a knowledge graph edge in a path to the target node crosses a zone border, by referring to an access edge in the access graph relating to the knowledge graph edge; and
determining the access right to the target node of the knowledge graph by referring to a corresponding access control list stored in the access edge of the access graph relating to a zone containing the target node of the knowledge graph.

12. The system of claim 10 , further comprising an adding unit adapted for adding a new node to the knowledge graph, wherein said adding unit is adapted for:
identifying, in the knowledge graph, one or more edges relating to the new node;
identifying, in the knowledge graph, each node related to the one or more edges;
determining that all nodes relating to the one or more edges belong to one zone; and
adding a node identifier indicative of the new node to the second list of nodes related to the one zone.

13. The system of claim 12 , further comprising an access edge adding unit adapted for:
determining that a new edge of the new node crosses a zone border to a second zone;
determining no access edge exists between the one zone of the new node and the second zone; and
adding an access edge to the access graph between a first access node relating to the one zone and a second access node related to the second zone.

14. The system of claim 12 , further comprising an edge removal unit adapted for:
determining there is only one edge between a first zone and a second zone of the knowledge graph;
determining the one edge is to be removed from the knowledge graph; and
removing a corresponding access edge from the access graph between a first access node representing the first zone and a second access node representing the second

Assignees

• IBM

Inventors

• Scheideler Tim U
• Graf Florian
• Rueger Erik
• Albrecht Marc

Classifications

• G06F21/6218 Primary

  to a system of files or objects, e.g. local or distributed file system or database · CPC title

• G06N5/02

  Knowledge representation; Symbolic representation · CPC title

• G06F21/604 Primary

  Tools and structures for managing or administering access control systems · CPC title

• G06F2221/2141

  Access rights, e.g. capability lists, access control lists, access tables, access matrices · CPC title

• G06N5/022

  Knowledge engineering; Knowledge acquisition · CPC title