Search NASA⌕ Search

SEARCH · Search NASA

Results for “Graph Challenge”

Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 343 records · Page 19

Optimizing Approximate Weighted Matching on Nvidia Kepler K40

Matching is a fundamental graph problem with numerous applications in science and engineering. While algorithms for computing optimal matchings are difficult to parallelize, approximation algorithms on the other hand generally compute high quality solutions and are amenable to parallelization. In this paper, we present efficient implementations of the current best algorithm for half-approximate weighted matching, the Suitor algorithm, on Nvidia Kepler K-40 platform. We develop four variants of the algorithm that exploit hardware features to address key challenges for a GPU implementation. We also experiment with different combinations of work assigned to a warp. Using an exhaustive set of $269$ inputs, we demonstrate that the new implementation outperforms the previous best GPU algorithm by $10$ to $100\times$ for over $100$ instances, and from $100$ to $1000\times$ for $15$ instances. We also demonstrate up to $20\times$ speedup relative to $2$ threads, and up to $5\times$ relative to $16$ threads on Intel Xeon platform with $16$ cores for the same algorithm. The new algorithms and implementations provided in this paper will have a direct impact on several applications that repeatedly use matching as a key compute kernel. Further, algorithm designs and insights provided in this paper will benefit other researchers implementing graph algorithms on modern GPU architectures.

GPU↗

Optimized Quantum Program Execution Ordering to Mitigate Errors in Simulations of Quantum Systems

Simulating the time evolution of a physical system at quantum mechanical levels of detail - known as Hamiltonian Simulation (HS) - is an important and interesting problem across physics and chemistry. For this task, algorithms that run on quantum computers are known to be exponentially faster than classical algorithms; in fact, this application motivated Feynman to propose the construction of quantum computers. Nonetheless, there are challenges in reaching this performance potential. Prior work has focused on compiling circuits (quantum programs) for HS with the goal of maximizing either accuracy or gate cancellation. Our work proposes a compilation strategy that simultaneously advances both goals. At a high level, we use classical optimizations such as graph coloring and travelling salesperson to order the execution of quantum programs. Specifically, we group together mutually commuting terms in the Hamiltonian (a matrix characterizing the quantum mechanical system) to improve the accuracy of the simulation. We then rearrange the terms within each group to maximize gate cancellation in the final quantum circuit. Furthermore, these optimizations work together to improve HS performance and result in an average 40% reduction in circuit depth. This work advances the frontier of HS which in turn can advance physical and chemical modeling in both basic and applied sciences.

97 MATHEMATICS AND COMPUTING↗

AI‐Driven Defect Engineering for Advanced Thermoelectric Materials

Thermoelectric materials offer a promising pathway to directly convert waste heat to electricity. However, achieving high performance remains challenging due to intrinsic trade-offs between electrical conductivity, the Seebeck coefficient, and thermal conductivity, which are further complicated by the presence of defects. This review explores how artificial intelligence (AI) and machine learning (ML) are transforming thermoelectric materials design. Advanced ML approaches including deep neural networks, graph-based models, and transformer architectures, integrated with high-throughput simulations and growing databases, effectively capture structure-property relationships in a complex multiscale defect space and overcome the “curse of dimensionality”. This review discusses AI-enhanced defect engineering strategies such as composition optimization, entropy and dislocation engineering, and grain boundary design, along with emerging inverse design techniques for generating materials with targeted properties. Finally, it outlines future opportunities in novel physics mechanisms and sustainability, highlighting the critical role of AI in accelerating the discovery of thermoelectric materials.

36 MATERIALS SCIENCE↗

Netostat: analyzing dynamic flow patterns in high-speed networks

Understanding flow traffic patterns in networks, such as the Internet or service provider networks, is crucial to improving their design and building them robustly. However, as networks grow and become more complex, it is increasingly cumbersome and challenging to study how the many flow patterns, sizes and the continually changing source-destination pairs in the network evolve with time. Here, we present Netostat, a visualization-based network analysis tool that uses visual representation and a mathematics framework to study and capture flow patterns, using graph theoretical methods such as clustering, similarity and difference measures. Netostat generates an interactive graph of all traffic patterns in the network, to isolate key elements that can provide insights for traffic engineering. We present results for U.S. and European research networks, ESnet and GEANT, demonstrating network state changes, to identify major flow trends, potential points of failure, and bottlenecks.

97 MATHEMATICS AND COMPUTING↗

ChemGraph as an agentic framework for computational chemistry workflows

Atomistic simulations are essential in chemistry and materials science but remain challenging to run due to the expert knowledge required for the setup, execution, and validation stages of these calculations. We present ChemGraph, an agentic framework powered by artificial intelligence and state-of-the-art simulation tools to streamline and automate computational chemistry and materials science workflows. ChemGraph leverages graph neural network-based foundation models for accurate yet computationally efficient calculations and large language models (LLMs) for natural language understanding, task planning, and scientific reasoning to provide an intuitive and interactive interface. We evaluate ChemGraph across 13 benchmark tasks and demonstrate that smaller LLMs (GPT-4o-mini, Claude-3.5-haiku, Qwen-2.5-14B) perform well on simple workflows, while more complex tasks benefit from using larger models. Importantly, we show that decomposing complex tasks into smaller subtasks through a multi-agent framework enables GPT-4o to reach perfect accuracy and smaller LLMs to match or exceed single-agent GPT-4o's performance in these benchmarks.

Computational chemistry↗

Distributed-Memory Sparse Deep Neural Network Inference Using Global Arrays

Partitioned Global Address Space (PGAS) models exhibit tremendous promise in developing efficient and productive distributed-memory parallel applications. They have been used extensively in scientific computations due to conveniently offering a ``shared-memory''-like model and convenient interfaces that separate communication with synchronization. Traditionally, PGAS communication models have been applied to dense/contiguously distributed data, but most modern applications depict varied levels of sparsity. Existing PGAS models require certain adaptations to support distributed sparse computations, since associated computations often require matrix arithmetic, in addition to data movement. The Global Arrays toolkit from Pacific Northwest National Laboratory (PNNL) is one of the earliest PGAS models to combine one-sided data communication and distributed matrix operations and is still used in the popular NWChem quantum chemistry suite. Recently, we have expanded the Global Arrays toolkit to support common sparse operations, like sparse matrix-dense matrix multiplies (SpMM), sparse matrix-sparse matrix multiplication (SpGEMM) and Sampled Dense-Dense Matrix Multiplication (SDDMM). As it turns out, these operations are the bedrock of sparse Deep Learning (DL); sparse deep neural networks and Graph Neural Networks (GNNs) have gained increasing attention recently in achieving speedups on training and inference with reduced memory footprints. Unlike scientific applications in High Performance Computing (HPC), modern (distributed-memory capable) DL toolkits often rely on non-standardized and closed-source vendor software optimizations, creating challenges in software-hardware co-design at scale. Our goal is to support a variety of distributed-memory sparse matrix operations and helper functions in the newly created Sparse Global Arrays (SGA), such that it is possible to build portable and productive Machine Learning scenarios for algorithm/software and hardware codesign purposes. Contemporary data-parallel schemes for training/inference are undergoing a major overhaul since model replication limits scalability and causes resource inefficiencies. As such, we have adopted tensor parallelism in decomposing the model and inputs, to mitigate memory issues. Current implementation is built on top of MPI and uses CPUs to maximize the portability across the platforms.

Distributed computing, machine learning↗

Assessing the Feasibility of Bordered Block Diagonal Reordering in Power System Matrices using Fully Convolutional Network

In electromagnetic transient (EMT) simulations for power systems and inverter-based resources (IBRs), the arrangement of states within the system's linear equations, represented by matrix A in Ax=b, is critical. The state ordering in matrix A can highlight distinct characteristics of the system's graph, and identifying an optimal state ordering is crucial for efficient computation. The choice of state ordering, however, is dependent on the solver used, as each solver may perform optimally with different matrix patterns. With a wide array of matrix reordering algorithms available, selecting the most suitable one becomes challenging without insights into the matrix's ideal configuration. To address this, the paper proposes a fully convolutional network (FCN) to evaluate the reordering potential of the A matrix into a bordered block diagonal (BBD) pattern, which is commonly observed in power system and IBR modeling. The FCN's assessment aims to streamline the solver's operation, which in turn could substantially reduce the computational time required to find a solution.

Xia, Qianxue↗

Predicting Large‐Scale Systematic Missing Pipe Attributes in Water Distribution Networks

Water distribution network (WDN) models are an essential tool used by water utilities for hydraulic analysis. Unfortunately, missing data and insufficient resources often make creating and maintaining these models unfeasible. Existing methods to address missing pipe properties, like sequential imputation for missing values and reconstruction using graph metrics, are designed to accommodate random patterns of missing information and require a significant percentage of the system's attributes to be known. However, these data completeness assumptions do not always align with real‐world scenarios where large sections of the WDN model have missing data. To address this challenge, this study proposes a data‐driven approach for estimating pipe diameter when considering different spatial patterns and degrees of data completeness (i.e., 0%–90%). Using data from 16 WDNs in Kentucky, this study compares the use of machine learning (ML) using topological and geospatial features against an existing deterministic approach. Results demonstrate that WDN models with pipe diameters predicted by the proposed ML method had comparable hydraulic performance to the ground truth models. Moreover, results showed that ML method performance varies between WDNs of differing topological classification. Insights from this study help advance the ability to leverage partial data to create and maintain WDN models amid uncertainty and inadequate resources.

Poff, Jason W. [Oregon State Univ., Corvallis, OR ↗

Current and future directions in network biology

Network biology is an interdisciplinary field bridging computational and biological sciences that has proved pivotal in advancing the understanding of cellular functions and diseases across biological systems and scales. Although the field has been around for two decades, it remains nascent. It has witnessed rapid evolution, accompanied by emerging challenges. These stem from various factors, notably the growing complexity and volume of data together with the increased diversity of data types describing different tiers of biological organization. We discuss prevailing research directions in network biology, focusing on molecular/cellular networks but also on other biological network types such as biomedical knowledge graphs, patient similarity networks, brain networks, and social/contact networks relevant to disease spread. In more detail, we highlight areas of inference and comparison of biological networks, multimodal data integration and heterogeneous networks, higher-order network analysis, machine learning on networks, and network-based personalized medicine. Following the overview of recent breakthroughs across these five areas, we offer a perspective on future directions of network biology. Additionally, we discuss scientific communities, educational initiatives, and the importance of fostering diversity within the field. This article establishes a roadmap for an immediate and long-term vision for network biology.

59 BASIC BIOLOGICAL SCIENCES↗

Learning to Predict and Improve Build Successes in Package Ecosystems

Software has become increasingly complex, with a typical application depending on tens or hundreds of packages. Finding compatible versions and build configurations of these packages is challenging. This paper presents a method to learn the likelihood of software build success, and techniques for leveraging this information to guide dependency solvers to better software configurations. We leverage the heavily parameterized package recipes from the Spack package manager to produce a training data set of builds, and we use Graph Neural Networks to learn whether a given package configuration will build successfully or not. We apply our tool to the U.S. Exascale Computing Project’s software stack. We demonstrate its effectiveness in predicting whether a given package will build successfully. We show that our technique can be used to improve the solutions generated by dependency solvers, reducing the need for developers to find working builds by trial and error.

97 MATHEMATICS AND COMPUTING↗

Threat Reduction Research Networks: Fostering Sustainable Collaborations Through Trainings for Genomics for Biosurveillance

Scientific research communities can be represented as heterogeneous or multidimensional networks encompassing multiple types of entities and relationships. These networks might include researchers, institutions, meetings, and publications, connected by relationships like authorship, employment, and attendance. We describe a method for efficiently and flexibly capturing, storing, and extracting information from multidimensional scientific networks using a graph database. The database structure is based on an ontology that captures allowable types of entities and relationships. This allows us to construct a variety of projections of the underlying multidimensional graph through database queries to answer specific research questions. We demonstrate this process through a study of the U.S. Biological Threat Reduction Program (BTRP), which seeks to develop Threat Reduction Networks to build and strengthen a sustainable international community of biosecurity, biosafety, and biosurveillance experts to address shared biological threat reduction challenges. Networks like these create connectional intelligence among researchers and institutions around the world, and are central to the concept of cooperative threat reduction. Our analysis focuses on a series of seven BTRP genome sequencing training workshops, showing how they created a growing network of participants and countries over time, which is also reflected in coauthorship relationships among attendees. By capturing concept and relationship hierarchies, our ontology-based approach allows us to pose general or specific questions about networks within the same framework. This approach can be applied to other research communities or multidimensional social networks to capture, analyze, and visualize different types of interactions and how they change over time.

59 BASIC BIOLOGICAL SCIENCES↗

Labels as a feature: Network homophily for systematically annotating human GPCR drug-target interactions

Machine learning has revolutionized drug discovery by enabling the exploration of vast, uncharted chemical spaces essential for discovering novel patentable drugs. Despite the critical role of human G protein-coupled receptors in FDA-approved drugs, exhaustive in-distribution drug-target interaction testing across all pairs of human G protein-coupled receptors and known drugs is rare due to significant economic and technical challenges. This often leaves off-target effects unexplored, which poses a considerable risk to drug safety. In contrast to the traditional focus on out-of-distribution exploration (drug discovery), we introduce a neighborhood-to-prediction model termed Chemical Space Neural Networks that leverages network homophily and training-free graph neural networks with labels as features. We show that Chemical Space Neural Networks’ ability to make accurate predictions strongly correlates with network homophily. Thus, labels as features strongly increase a machine learning model’s capacity to enhance in-distribution prediction accuracy, which we show by integrating labeled data during inference. We validate these advancements in a high-throughput yeast biosensing system (3773 drug-target interactions, 539 compounds, 7 human G protein-coupled receptors) to discover novel drug-target interactions for FDA-approved drugs and to expand the general understanding of how to build reliable predictors to guide experimental verification.

Hansson, Frederik G↗

IRIS-MEMFLOW: Data Flow-Enabled Portable Memory Orchestration in IRIS Runtime for Diverse Heterogeneity

Task-based programming models and execution paradigms provide a means to decompose a computation by expressing it as a graph in which each node represents a specific computation operating on memory objects and the edges define the dependencies in the execution flow. In this execution model, independent nodes in the graph can be executed concurrently in different computing devices, making it suitable for heterogeneous systems in which computing devices with different architectures coexist. However, careful memory orchestration across heterogeneous devices is needed because copies of the same memory object may reside in multiple devices during execution. Manually ensuring such an orchestration is quite challenging. Not only must an application developer guard against race conditions, but they must also optimize data movement between the host and devices because unnecessary data movement significantly impacts performance. To mitigate these challenges, we enhance the IRIS heterogeneous runtime and introduce IRIS-MEMFLOW–a data flow–enabled portable memory abstraction for seamlessly orchestrating memory in diverse heterogeneous computing environments. By using data-flow analysis, IRIS-MEMFLOW guards against race conditions while multiple heterogeneous devices access memory objects. IRIS-MEMFLOW also optimizes data movement between the host and devices without manual intervention. As a result, IRIS provides improved programming productivity, performance, and portability for multidevice heterogeneous executions in high-performance computing and cloud systems that run diverse architectures from different vendors. The efficacy of IRIS-MEMFLOW is evaluated through experiments that show its capability in terms of programming productivity, multidevice heterogeneity, portability, and low overhead versus the state of the art.

Monil, M. A. H. [ORNL] (ORCID:0000000334194037)↗

Smart Data Mapping for Connecting Power System Model and Geospatial Data

Knowing the geospatial locations of power system model elements is the foundation for analyzing system vulnerability to natural hazards and connecting loads with end users and their communities. However, power system models and geospatial data for power grid assets may have been developed asynchronously without close coordination. Creating a direct mapping between the two may be a challenging task, considering heterogeneous data structures, target uses, historical legacies, and human errors. This work aims to build an automatic data mapping workflow to connect power system model elements and geospatial data for transmission network, and to support energy grid resilience studies for Puerto Rico. The primary steps in this workflow include constructing graphs using geospatial data, and aligning them to the transmission networks defined in the power system data. The results have been evaluated against existing manual mapping practices for part of the Puerto Rico Power Grid model to illustrate the performance of such auto-mapping solutions.

Resilience, geospatial data, grid transmission net↗

Prepare Ground States of Highly Frustrated Magnetic Clusters on Quantum Computers

Solving challenging problems in physical, chemical, and materials sciences is one of the most promising applications of quantum utility that can be realized on current noisy hardware, considering (i) the direct map (encoding) from the quantum particles and their interactions to the qubits and their entangling gates and (ii) the rapidly improved quantum hardware and advanced error-mitigation techniques. Understanding quantum spin liquid in frustrated magnetic materials is a longstanding challenge in condensed matter physics and the nature of the ground-state phases is highly debated among researchers. Using IBM quantum computers with superconducting qubits, we implemented a variational quantum eigensolver (VQE) algorithm to prepare the ground states of two 12-site cluster approximations of these highly frustrated magnetic materials. The interaction graphs of the two corresponding Hamiltonians are (a) the six-pointed star graph (a unit cell of the kagome lattice) and (b) the cuboctahedral graph (the kagome on a sphere). These are also two instances of Quantum Max Cut problem. With the VQE based on the Hamiltonian variational ansatz acting on a valence bond solid initial trial state, we prepared the ground states and obtained the exact ground energy on simulator and high accuracy on noisy hardware. The deep ansatz necessary to reach the ground state of the cuboctahedral graph indicates that it is a hard instance of Quantum Max Cut.

Wang, Yan↗

Machine learning applied to wind turbine blades impact detection

The significant development of wind power generation worldwide brings, together with environmental benefits, wildlife concerns, especially for volant species vulnerability to interactions with wind energy facilities. For surveying such events, an automatic system for continuous monitoring of blade collisions is critical. An onboard multi-senor system capable of providing real-time collision detection using integrated vibration sensors is developed and successfully tested. However, to detect low signal-to-noise ratio impact can be challenging; hence, an advanced impact detection method has been developed and presented in this article. A robust automated detection algorithm based on support vector machine is proposed. After a preliminary signal pre-processing, geometric features specifically selected for their sensitivity to impact signals are extracted from raw vibration signal and energy distribution graph. The predictive model is formulated by training conventional support vector machine using extracted features for impact identification. Finally, the performance of the predictive model is evaluated by accuracy, precision, and recall. Results indicate a linear regression relationship between signal-to-noise ratio and model overall performance. Here, the proposed method is much reliable on higher signal-to-noise ratio (SNR≥6), but it shows to be ineffective at lower signal-to-noise ratio (SNR<2).

17 WIND ENERGY↗

A Model Integration Pipeline for the Improvement of Human Genome-Scale Metabolic Reconstructions

Abstract Metabolism has been a major field of study in the last years, mainly due to its importance in understanding cell physiology and certain disease phenotypes due to its deregulation. Genome-scale metabolic models (GSMMs) have been established as important tools to help achieve a better understanding of human metabolism. Towards this aim, advances in systems biology and bioinformatics have allowed the reconstruction of several human GSMMs, although some limitations and challenges remain, such as the lack of external identifiers for both metabolites and reactions. A pipeline was developed to integrate multiple GSMMs, starting by retrieving information from the main human GSMMs and evaluating the presence of external database identifiers and annotations for both metabolites and reactions. Information from metabolites was included into a graph database with omics data repositories, allowing clustering of metabolites through their similarity regarding database cross-referencing. Metabolite annotation of several older GSMMs was enriched, allowing the identification and integration of common entities. Using this information, as well as other metrics, we successfully integrated reactions from these models. These methods can be leveraged towards the creation of a unified consensus model of human metabolism.

Vieira, Vítor↗

High Performance Descriptive Semantic Analysis of Semantic Graph Databases

As semantic graph database technology grows to address components ranging from extant large triple stores to SPARQL endpoints over SQL-structured relational databases, it will become increasingly important to be able to understand their inherent semantic structure, whether codified in explicit ontologies or not. Our group is researching novel methods for what we call descriptive semantic analysis of RDF triplestores, to serve purposes of analysis, interpretation, visualization, and optimization. But data size and computational complexity makes it increasingly necessary to bring high performance computational resources to bear on this task. Our research group built a novel high performance hybrid system comprising computational capability for semantic graph database processing utilizing the large multi-threaded architecture of the Cray XMT platform, conventional servers, and large data stores. In this paper we describe that architecture and our methods, and present the results of our analyses of basic properties, connected components, namespace interaction, and typed paths such for the Billion Triple Challenge 2010 dataset.

99 GENERAL AND MISCELLANEOUS↗