Knowledge graph analytics kernels in high performance computing
Inventors
Kannan, Ramakrishnan • Sao, Piyush K. • LU, HAO • Herrmannova, Drahomira • Thakkar, Vijay • Patton, Robert M. • Vuduc, Richard W. • Potok, Thomas E.
Assignees
Interested in licensing this patent?
MTEC can help explore whether this patent might be available for licensing for your application.
Publication Number
US-12417246-B2
Publication Date
2025-09-16
Expiration Date
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.
Core Innovation
The invention provides a high-performance computing method to enable mining existing information and deriving new knowledge from biomedical literature. The method receives, from multiple textual databases, information about a set of articles and annotations relating to biomedical concepts appearing in the articles. A first knowledge graph is formed using the entire received information and annotations, with nodes and edges representing biomedical articles, biomedical concepts, and relations among them based on co-occurrence, annotations or mentions, and citation references between articles.
Shortest paths between all pairs of nodes in the first knowledge graph are determined using a distributed Floyd-Warshall algorithm across multiple processing units in a two-dimensional process grid. Parallel updates are coordinated using a message passing interface that performs diagonal updates, panel updates, and MinPlus Outer Product computations over a tropical semiring executed by graphics processing units. Computations are performed in CPU-only mode, GPU-only mode, or CPU-GPU overlapping mode to optimize resource utilization based on workload, with asynchronous lookahead scheduling to overlap computation and communication and broadcasting of matrix updates using a bandwidth-optimal ring communication protocol.
A second knowledge graph is formed that includes the nodes of the first knowledge graph and only the edges corresponding to the shortest paths. The method further optimizes communication load by placing communicating processes on processing units that are physically proximal within the high-performance computing system. Using the second knowledge graph, yet-undiscovered biomedical relationships between the biomedical concepts are predicted, where the predictions are computed using the shortest paths as input features, and a ranked list of biomedical relationships is output to a display.
Claims Coverage
The independent claim covers an end-to-end workflow comprising knowledge graph construction, distributed accelerated shortest-path computation, construction of a shortest-path-only graph, and prediction and ranking of biomedical relationships, with multiple explicitly specified HPC and communication features. Dependent claims refine how shortest paths are constrained and specify additional operational selections for communication and process placement.
Biomedical concept and article knowledge graph from received textual data
Receiving, from multiple textual databases, information about a set of articles and annotations relating to biomedical concepts; forming a first knowledge graph with article nodes and concept nodes, with concept-concept edges based on co-occurrence, concept-article edges based on annotations or mentions, and article-article edges based on citation references.
Distributed Floyd-warshall shortest paths on a two-dimensional process grid using MPI, tropical semiring, and GPU minplus outer product
Determining shortest paths between all pairs of nodes by implementing a distributed Floyd-Warshall algorithm across multiple processing units in a two-dimensional process grid; coordinating parallel updates using an MPI that performs diagonal updates, panel updates, and MinPlus Outer Product computations over a tropical semiring executed by GPUs.
CPU-only, GPU-only, or CPU-gpu overlapping execution with lookahead scheduling and bandwidth-optimal ring broadcasts
Performing computations in CPU-only mode, GPU-only mode, or CPU-GPU overlapping mode to optimize resource utilization based on workload; performing asynchronous lookahead scheduling to overlap computation and communication; broadcasting matrix updates using a bandwidth-optimal ring communication protocol.
Second knowledge graph containing only shortest-path edges for relationship prediction
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; predicting yet-undiscovered biomedical relationships between the biomedical concepts based on the second knowledge graph, where the predictions are computed using the shortest paths as input features; outputting a ranked list of biomedical relationships to a display.
Shortest-path constrained modifications during shortest-path determination
Applying a constraint during shortest-path determination that downweights, removes, and/or ignores at least one shortest path.
Constraint as a relevance measure
Specifying the constraint as a measure of relevance computed between concepts, between articles, or between a concept and an article.
Cpu communicators, gpu communicators, or concurrently both cpu-gpu communicators
Performing the shortest-path computations using only CPU communicators, only GPU communicators, or concurrently both CPU-GPU communicators.
Gpu-only execution using gpu communicators
When the distributed Floyd-Warshall algorithm is executed only on GPUs, using GPU communicators.
Physically proximal placement of communicating processes to reduce communication load
Further optimizing communication load by placing communicating processes on processing units that are physically proximal within the high-performance computing system.
Overall claim coverage centers on constructing a biomedical article/concept knowledge graph from received textual data, computing all-pairs shortest paths via distributed Floyd-Warshall coordinated with MPI updates over a tropical semiring on GPUs, managing execution and communication through CPU/GPU modes with lookahead and ring broadcast, and forming a shortest-path-only second graph for predicting and outputting ranked biomedical relationships using shortest paths as input features; dependent claims further constrain shortest paths and refine communication mode and process placement.
Stated Advantages
Enables mining of existing information and deriving new knowledge from biomedical concepts and articles.
Predicts yet-undiscovered biomedical relationships between biomedical concepts.
Outputs a ranked list of biomedical relationships based on shortest-path computations.
Optimizes resource utilization by enabling CPU-only mode, GPU-only mode, or CPU-GPU overlapping mode.
Overlaps computation and communication using asynchronous lookahead scheduling.
Reduces communication latency by performing intra-node communication optimization.
Reduces communication burden by placing communicating processes on processing units that are physically proximal within the high-performance computing system.
Documented Applications
Mining biomedical information from textual databases and deriving new knowledge by predicting yet-undiscovered biomedical relationships and outputting a ranked list of biomedical relationships for display.
Interested in licensing this patent?