# US 2022/0035832 A1 · Knowledge graph analytics kernels in high performance computing

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2022/0035832 A1
- Document ID: US20220035832A1
- Status: Published application
- Kind: A1
- Application number: 17/389,862
- Filed: 2021-07-30
- Published: 2022-02-03
- Earliest claimed: 2020-07-31
- Assignees: UT-Battelle, LLC
- Applicants: UT-Battelle, LLC
- Inventors: Ramakrishnan Kannan; Piyush K. Sao; Hao Lu; Drahomira Herrmannova; Vijay Thakkar; Robert M. Patton; Richard W. Vuduc; Thomas E. Potok
- Web page: https://patentgrep.com/patent/US20220035832A1

## CPC

- G06F 16/9024: {Graphs; Linked lists (G06F16/9027 takes precedence)}
- G06F 16/26: Visual data mining; Browsing structured data
- G06F 16/904: Browsing; Visualisation therefor (for navigating the web G06F16/954; browsing optimisation for the web G06F16/957)
- G06N 7/01: Probabilistic graphical models, e.g. probabilistic networks
- G16H 50/70: for mining of medical data, e.g. analysing previous cases of other patients
- G16H 70/60: relating to pathologies
- G06F 16/24578: {using ranking}
- Y02A 90/10: Information and communication technologies [ICT] supporting adaptation to climate change, e.g. for weather forecasting or climate simulation
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
- G16H: HEALTHCARE INFORMATICS, i.e. INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR THE HANDLING OR PROCESSING OF MEDICAL OR HEALTHCARE DATA
- Y02A: TECHNOLOGIES FOR ADAPTATION TO CLIMATE CHANGE

## Abstract

Data mining large-scale corpora of scholarly publications, such as the full biomedical literature, which may consist of tens of millions of papers spanning decades of research. The present disclosure provides a Distributed Accelerated Semiring All-Pairs Shortest Path (DSNAPSHOT) algorithm for computing shortest paths of a knowledge graph using distributed-memory parallel computers accelerated by GPUs. DSNAPSHOT implementations can analyze connected input graphs with millions of vertices using a large number graphics processing units (e.g., the 24,576 GPUs of the Oak Ridge National Laboratory's Summit supercomputer system). DSNAPSHOT provides sustained performance of about 136*1015 floating-point operations per second (136 petaflop/s) at a parallel efficiency of about 90% under weak scaling and, in absolute speed, 70% of the performance given our computation (in the single-precision tropical semiring or “min-plus” algebra). DSNAPSHOT may enable mining of scholarly knowledge corpora when embedded and integrated into artificial intelligence-driven natural language processing workflows at scale.

## Claims

### Claim 1

A method, performed by a high-performance computing system, to enable mining of existing information and deriving new knowledge, the method comprising:
receiving from multiple textual databases information about a set of articles and annotations relating to concepts that appear in the articles;
forming a first knowledge graph using the entire received information and annotations, the knowledge graph having nodes connected by edges, where some of the nodes represent respective articles and the remaining nodes represent respective concepts, and edges between concept nodes represent relations between concepts, edges between concept nodes and article nodes represent relations between concepts and articles, and edges between article nodes represent relations between articles;
determining shortest paths between all pairs of nodes of the first knowledge graph;
forming a second knowledge graph that includes the nodes of the first knowledge graph and the edges of the first knowledge graph that correspond only to the shortest paths; and
predicting yet-undiscovered direct connections between the concepts based on the second knowledge graph.

### Claim 2 (depends on 1)

The method of claim 1, wherein forming the first knowledge graph is performed based on existing information about either occurrence of concepts in articles, or relation of concepts in articles, or citation relations between articles.

### Claim 3 (depends on 1)

The method of claim 1, wherein the concepts include bio-medical terms and the articles include articles of bio-medical interest.

### Claim 4 (depends on 1)

The method of claim 1, further comprises applying, while determining the shortest paths, a constraint to at least one of downweight, remove at least some edges along particular paths, and ignore a shortest path completely.

### Claim 5 (depends on 4)

The method of claim 4, wherein the constraint represents a measure of relevance between concepts, between articles, or between concepts and articles.

### Claim 6 (depends on 1)

The method of claim 1, wherein determining the shortest paths is performed, only by CPUs, only by GPUs, or concurrently on CPUs and GPUs of the high-performance computing system, using a distributed Floyd-Warshall (FW) algorithm.

### Claim 7 (depends on 6)

The method of claim 6, wherein the distributed FW algorithm is performed in a semi-ring manner.

### Claim 8 (depends on 7)

The method of claim 7, wherein the distributed FW algorithm includes MPI assignment, diagonal update, panel update, and MinPlus Outer Product sections.

### Claim 9 (depends on 8)

The method of claim 8, wherein communications for determining the shortest paths is performed using only CPU communicators, only GPU communicators, or concurrently both CPU-GPU communicators of the high performance computing system.

### Claim 10 (depends on 8)

The method of claim 8, wherein the high-performance computing system uses GPU communicators when the distributed FW algorithm is performed only by GPUs.

### Claim 11 (depends on 10)

The method of claim 10, further comprising reducing communication burden by instructing communicating subprocesses to run on resources of the high-performance computing system that are closer together.

### Claim 12 (depends on 10)

The method of claim 10, wherein reducing the communication burden further comprises performing techniques that include one or more of lookahead, ring broadcast over tree-based broadcast, optical rank placement, or intra-node communication optimization.

### Claim 13

A method, performed by a computing system, of mining knowledge graphs at scale comprising:
obtaining a knowledge graph including a plurality of vertices and a plurality of edges, each of the plurality of edges having an associated weight;
wherein each of the plurality of vertices represent:
i) one of a plurality of unique concepts; or
ii) one of a plurality of documents from which one of the plurality of unique concepts was extracted;
wherein each of the plurality of edges between the plurality of vertices represent:
1) a relationship between two or more of the plurality of unique concepts
2) a relationship between one or more of the plurality of unique concepts and one or more of the plurality of documents; or
3) a citation relationship between two documents
determining shortest paths between all pairs of nodes of the knowledge graph using a scalable, distributed, accelerated, semiring all-pairs shortest path (APSP) algorithm (DSNAPSHOT).

### Claim 14 (depends on 13)

The method of claim 13 wherein DSNAPSHOT includes performing semi-ring on a GPU.

### Claim 15 (depends on 13)

The method of claim 13 wherein DSNAPSHOT is configured as a CPU-GPU overlapping all pairs shortest path algorithm.

### Claim 16 (depends on 13)

The method of claim 13 wherein DSNAPSHOT is configured as a flexible all pairs shortest path algorithm performed in a CPU only mode, GPU only mode, or CPU-GPU overlapping mode.

### Claim 17 (depends on 13)

The method of claim 13 wherein DSNAPSHOT is configured to reduce communication burden by placing communicating subprocesses on physically proximal machines.

### Claim 18

A method, performed by a computing system, of mining knowledge graphs at scale comprising:
obtaining a matrix representing a knowledge graph having a plurality of nodes and edges there between;
determining shortest paths between all pairs of nodes of the knowledge graph by processing the matrix with the computing system, wherein the processing is distributed across multiple processors coordinated by a message processing interface that coordinates parallel diagonal updates, panel updates, and min-plus outer products;
determining a ranking based on the determined shortest paths between all pairs of nodes; and
outputting the ranking to a display.

### Claim 19 (depends on 18)

The method of claim 18 wherein the method of mining knowledge graphs at scale includes performing computation and communication concurrently utilizing lookahead.

### Claim 20 (depends on 18)

The method of claim 18 wherein the method of mining knowledge graphs at scale includes configuring the computing system with bandwidth optimal asynchronous ring communication for broadcast.

### Claim 21 (depends on 18)

The method of claim 18 wherein the method of mining knowledge graphs at scale includes assigning a subset of communicating processes to hardware processors at least in part based on physical distance between the hardware processors.
