Multi-dimensional knowledge index and application thereof

Patent metadata

Field	Value
Publication number	US-10776337-B2
Application number	US-201816028604-A
Country	US
Kind code	B2
Filing date	Jul 6, 2018
Priority date	Jul 6, 2018
Publication date	Sep 15, 2020
Grant date	Sep 15, 2020

Abstract

A method of augmenting a knowledge graph includes obtaining the knowledge graph, which includes entities and relationships between the entities defining respective edges, clustering the entities into knowledge domains using semantic distances determined between the entities and a threshold on the semantic distances, identifying strengths of the relationships between adjacent entities in the knowledge graph, creating knowledge chains from node pairs in the knowledge graph, including generating a minimum spanning tree using the strengths of the relationships, pruning edges from the knowledge chain using a threshold on weights corresponding to the edges, defining a first knowledge index for each of the knowledge chains, defining a second knowledge index for each of the knowledge domains, and defining a third knowledge index for the knowledge graph as a harmonic mean of a sum of the first knowledge indexes and a sum of the second knowledge indexes.

First claim

What is claimed is:

1. A method of augmenting a knowledge graph comprising:
obtaining the knowledge graph, wherein the knowledge graph includes a plurality of entities and relationships between the entities defining respective edges;
clustering the entities into a plurality of knowledge domains using semantic distances determined between the entities and a threshold on the semantic distances;
identifying a strength of each of the relationships between adjacent ones of the entities in the knowledge graph;
creating a plurality of knowledge chains from a plurality of node pairs in the knowledge graph, including generating a minimum spanning tree using the strength of each of the relationships between the adjacent entities in the knowledge graph;
pruning a plurality of the edges from the knowledge chain using a threshold on weights corresponding to the edges;
defining a first knowledge index for each of the knowledge chains;
defining a second knowledge index for each of the knowledge domains; and
defining a third knowledge index for the knowledge graph as a harmonic mean of a sum of the first knowledge indexes and a sum of the second knowledge indexes.

2. The method of claim 1 , further comprising, prior to the clustering, cleaning and normalizing the entities and relationships of the knowledge graph.

3. The method of claim 1 , wherein defining the first knowledge index for each of the knowledge chains comprises determining a first knowledge index for each of the knowledge chains as a sum of the strengths of each of the relationships of the plurality of node pairs therein.

4. The method of claim 1 , wherein defining the second knowledge index for each of the knowledge domains comprises determining a second knowledge index for each of the knowledge domains as an overlap between the entities in the knowledge domain and a given reference ontology.

5. The method of claim 1 , further comprising:
comparing the third knowledge index of a knowledge index corresponding to an alternative knowledge graph; and
selecting, using the third knowledge index, the knowledge index for a subsequent pipeline.

6. In a general purpose computer, a method for loading at least a portion of a knowledge graph into a memory of the general purpose computer, the method comprising:
obtaining a plurality of knowledge graphs, wherein each of the knowledge graphs includes a plurality of entities and relationships between the entities defining respective edges;
for each of the plurality of knowledge graphs:
clustering the entities into a plurality of knowledge domains using semantic distances determined between the entities and a threshold on the semantic distances;
identifying a strength of each of the relationships between adjacent ones of the entities in the knowledge graph;
creating a plurality of knowledge chains from a plurality of node pairs in the knowledge graph, including generating a minimum spanning tree using the strength of each of the relationships between the adjacent entities in the knowledge graph;
pruning a plurality of the edges from the knowledge chain using a threshold on weights corresponding to the edges;
defining a first knowledge index for each of the knowledge chains;
defining a second knowledge index for each of the knowledge domains; and
defining a third knowledge index for the knowledge graph as a harmonic mean of a sum of the first knowledge indexes and a sum of the second knowledge indexes; and

selecting the knowledge graph from among the plurality of knowledge graphs using the third knowledge index, wherein at least the portion of the knowledge graph selected is loaded into the memory.

7. The method of claim 6 , further comprising, prior to the clustering, cleaning and normalizing the entities and relationships of the knowledge graph.

8. The method of claim 6 , wherein defining the first knowledge index for each of the knowledge chains comprises determining a first knowledge index for each of the knowledge chains as a sum of the strengths of each of the relationships of the plurality of node pairs therein.

9. The method of claim 6 , wherein defining the second knowledge index for each of the knowledge domains comprises determining a second knowledge index for each of the knowledge domains as an overlap between the entities in the knowledge domain and a given reference ontology.

10. A non-transitory computer readable medium comprising computer executable instructions which when executed by a computer cause the computer to perform a method of augmenting a knowledge graph, the method comprising:
obtaining the knowledge graph, wherein the knowledge graph includes a plurality of entities and relationships between the entities defining respective edges;
clustering the entities into a plurality of knowledge domains using semantic distances determined between the entities and a threshold on the semantic distances;
identifying a strength of each of the relationships between adjacent ones of the entities in the knowledge graph;
creating a plurality of knowledge chains from a plurality of node pairs in the knowledge graph, including generating a minimum spanning tree using the strength of each of the relationships between the adjacent entities in the knowledge graph;
pruning a plurality of the edges from the knowledge chain using a threshold on weights corresponding to the edges;
defining a first knowledge index for each of the knowledge chains;
defining a second knowledge index for each of the knowledge domains; and
defining a third knowledge index for the knowledge graph as a harmonic mean of a sum of the first knowledge indexes and a sum of the second knowledge indexes.

11. The computer readable medium of claim 10 , further comprising, prior to the clustering, cleaning and normalizing the entities and relationships of the knowledge graph.

12. The computer readable medium of claim 10 , wherein defining the first knowledge index for each of the knowledge chains comprises determining a first knowledge index for each of the knowledge chains as a sum of the strengths of each of the relationships of the plurality of node pairs therein.

13. The computer readable medium of claim 10 , wherein defining the second knowledge index for each of the knowledge domains comprises determining a second knowledge index for each of the knowledge domains as an overlap between the entities in the knowledge domain and a given reference ontology.

14. The computer readable medium of claim 10 , further comprising:
comparing the third knowledge index of a knowledge index corresponding to an alternative knowledge graph; and
selecting, using the third knowledge index, the knowledge index for a subsequent pipeline.

Assignees

• IBM

Inventors

• Ding Chengmin
• Filoti Octavian F
• Vernier Stanley J
• Decker Renee F
• Shek Elinna

Classifications

• G06F16/2272 Primary

  Management thereof · CPC title

• G06F16/2264 Primary

  Multidimensional index structures · CPC title

• G06F16/9024

  Graphs; Linked lists (G06F16/9027 takes precedence) · CPC title