SEARCH · Search NASA

Results for “graph alignment”

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.

SourceResearch connectionFrom yearThrough year

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

At least 19 records

All sources NASA NTRS DOE OSTI

DOE OSTI2020

Programming Strategies for Irregular Algorithms on the Emu Chick

The Emu Chick prototype implements migratory memory-side processing in a novel hardware system. Rather than transferring large amounts of data across the system interconnect, the Emu Chick moves lightweight thread contexts to near-memory cores before the beginning of each remote memory read. Previous work has characterized the performance of the Chick prototype in terms of memory bandwidth and programming differences from more typical, non-migratory platforms, but there has not yet been an analysis of algorithms on this system. This work evaluates irregular algorithms that could benefit from the lightweight, memory-side processing of the Chick and demonstrates techniques and optimization strategies for achieving performance in sparse matrix-vector multiply operation (SpMV), breadth-first search (BFS), and graph alignment across up to eight distributed nodes encompassing 64 nodelets in the Chick system. We also define and justify relative metrics to compare prototype FPGA-based hardware with established ASIC architectures. The Chick currently supports up to 68x scaling for graph alignment, 80 MTEPS for BFS on balanced graphs, and 50% of measured STREAM bandwidth for SpMV.

Hein, Eric↗

DOE OSTI2024

Gene-Metabolite Association Prediction with Interactive Knowledge Transfer Enhanced Graph for Metabolite Production

Identifying gene targets for enhancing metabolite production in metabolic engineering is challenging due to the vast research literature and the approximation in genome-scale metabolic model (GEM) simulations. Here, to address this, we propose the Gene-Metabolite Association Prediction task, which automates gene discovery for given metabolite-gene pairs, accompanied by a benchmark dataset of 2474 metabolites and 1947 genes for Saccharomyces cerevisiae (SC) and Issatchenkia orientalis (IO). This task is complicated by incomplete metabolic graphs and metabolic heterogeneity. We introduce an Interactive Knowledge Transfer mechanism based on Metabolism Graphs (IKT4Meta) to enhance prediction accuracy by integrating cross-metabolism knowledge. Using Pretrained Language Models (PLMs) to generate inter-graph links mitigates heterogeneity issues, while intra-graph links are propagated via these anchors. Gene-metabolite predictions are then performed on the enriched graphs integrating multiple microorganisms’ knowledge. Experiments show that IKT4Meta outperforms baselines by up to 12.3% in link prediction.

59 BASIC BIOLOGICAL SCIENCES↗

DOE OSTI2022

Semantic Property Graph for Scalable Knowledge Graph Analytics

Graphs are a natural and fundamental representation to describe entities, relationships, activities, and evolution of complex systems. Many domains such as communication, citation, procurement, biology, social media, and transportation can be modeled as a set of entities and their relationships. Resource Description Framework (RDF) and Labeled Property Graph (LPG) are two of the most used data models to encode information in a graph. Both models are similar in terms of using basic graph elements such as nodes and edges but differ in terms of the modeling approach, expressibility, serialization, and target applications. RDF is a flexible data exchange model for expressing information about entities but it tends to a have high memory footprint and inefficient storage, which does not make it a natural choice to perform scalable graph analytics. In contrast, LPG has gained traction as a reliable model to perform scalable graph analytic tasks such as sub-graph matching, network alignment, and real-time knowledge graph query. It provides efficient storage, fast traversal, and flexibility to model various real-world domains. At the same time, the LPG lacks the support of a formal knowledge representation such as an ontology to provide automated knowledge inference. We propose Semantic Property Graph (SPG) as a logical projection of reified RDF into the LPG model. SPG continues to use RDF ontology to define the type hierarchy of the projected graph and validate it against a given ontology. We present a framework to convert reified RDF graphs into SPG using two different computing environments. We also present cloud-based graph migration capabilities using Amazon Web Services.

Purohit, Sumit↗

DOE OSTI2023

cuAlign: Scalable Network Alignment on GPU Accelerators

Given two graphs, the objective of network alignment is to find the best one-to-one mapping of vertices in one graph (??) to vertices in the other (??), such that the number of overlaps is maximized. We say that edges(??, ??) ???and(??', ??') ??? are overlapped if ?? is mapped to ??' and ?? is mapped to??'. Network alignment is an important optimization problem with several applications in bioinformatics, computer vision and ontology matching. Since it is an NP-hard problem, efficient heuristics and scalable implementations are necessary. In this work, we introduce a new framework that combines the concepts of intra-network proximity using vertex embedding,Belief Propagation (BP) and approximate weighted matching, and provides qualitative improvements up to22%over state-of-the-art approaches. We also provide scalable implementations on GPU accelerators, demonstrating up to19×speedup for Belief Propagation and 3× speedup for approximate weighted matching relative to previous multithreaded implementation. A combination of combinatorial and algebraic kernels within the network alignment algorithm poses significant hurdles for parallelization. Load imbalance and irregular DRAM traffic limit achievable performance on GPUs. Our novel approach identifies and exploits unique structural proper-ties of the BP-based algorithm and employs code fusion to reduce data movement between different steps of the algorithm. Using a diverse set of inputs, we demonstrate qualitative improvements of our algorithms, and performance gains of our GPU-accelerated implementation. We believe that our work will enable algorithmic improvements and practical applications of network alignment.

Xiang, Lizhi↗

DOE OSTI2023

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↗

DOE OSTI2020

Machine Learning Approaches for Nuclear Material Accounting Data from Irradiation and Reprocessing

We are currently exploring data analysis methods for their ability to strengthen the synthesis and evaluation of information generated within domestic and international safeguard regimes. Safeguard data typically includes rich heterogenous datasets amenable to advanced data analytics methods, such as machine learning. We have converted transactional data containing both numerical and categorical attributes from a domestic nuclear material control and accountability (NMC&A) system into a low-dimensional numerical structure via linear principal component analysis. This data representation allows for global structure discovery via cluster analysis, which can characterize the typical behavior of each of the primary types of transaction events. Furthermore, the structure of the top principal components captures the “typical behavior” of the data and is thus amenable to anomaly detection through statistical hypothesis testing. We explored this capability by generating erroneous permutations of the data and computing the Q-residual quantity increase associated with the information loss when these data are projected into the low-dimensional principal component analysis space representative of typical transactions.Future work will focus on identifying data transformations (e.g., graph networks) that more closely align with the inherent structure of these transactions to explain more salient information and disambiguate the underlying nuclear process—in this case, irradiation and reprocessing—from artifacts of NMC&A system transactional record keeping data.

Drescher, Adam↗

DOE OSTI2025

GASP: Gradient-Aware Shortest Path Algorithm for Boundary-Confined 2-Manifold Reeb Graph Visualization

Reeb graphs are an important tool for abstracting and representing the topological structure of a function defined on a manifold. We have identified three properties for faithfully representing Reeb graphs in a visualization: they should be constrained to the boundary, compact, and aligned with the function gradient. Existing algorithms for drawing Reeb graphs are agnostic to or violate these properties. In this paper, we introduce an algorithm to generate Reeb graph visualizations, called GASP, that is cognizant of these properties, thereby producing visualizations that are more representative of the underlying data. To demonstrate the improvements, the resulting Reeb graphs are evaluated both qualitatively and quantitatively against the geometric barycenter algorithm, using its implementation available in the Topology ToolKit (TTK), a widely adopted tool for calculating and visualizing Reeb graphs.

Rahman, Sefat [University of Utah]↗

DOE OSTI2024

MiNAA: Microbiome Network Alignment Algorithm

A microbial network is a mathematical representation of a microbial community where nodes represent microbes and edges represent interactions. It is well-recognized that microbes are among the main drivers of biological phenotypes in soil, plants, and animals alike, and thus, their study has vast implications for soil, plant and human health. In particular, recognizing the microbial, environmental, and agricultural factors that drive plant and soil phenotypes is crucial to comprehend processes connected to plant and soil health, to identify global practices of sustainable agriculture, as well as to predict plant and soil responses to environmental perturbations such as climate change. The adaptability of microbes to thrive in every environment poses challenges for scientists who try to understand their communities. Indeed, two microbial communities with the exact same players can interact differently depending on the environmental conditions. It is thus desirable to identify commonalities and differences on two microbial networks, hence the need for computational tools that can match (or align) them.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2025

LatticeAnalytics: Strut-Level Visualization and Inspection of Additively Manufactured Lattice Structures

Additive manufacturing (AM) is revolutionizing the production of custom components with complex internal geometries, essential for high-performance applications in diverse fields such as medicine and defense. These AM parts optimize strength while minimizing weight by utilizing internal lattice structures consisting of large quantities of small interconnected struts. However, the complexity of these structures, combined with the challenges of using X-ray Computed Tomography (XCT) data, makes validation of part reliability difficult. This ultimately inhibits the development of novel parts for our collaborating material scientists. Here, we introduce LatticeAnalytics, a novel framework specifically designed for visual inspection of defects in these lattice structures. Our framework offers an end-to-end solution that includes the data management of XCT scans, enables remote access for geographically dispersed teams through a web-based dashboard, and incorporates novel visualizations. Our analysis is facilitated by a coarse alignment between the lattice’s nominal model, a spatial graph, and the XCT data. We employ a simple VR-based approach for fast and rough alignment, followed by an offline registration and identification of the struts. With the nodes and struts aligned and identified in the volume, our framework allows querying of subvolumes containing a single strut at multiple resolutions. This avoids computation over the entire lattice and also allow for easy parallelization of down-stream computations, such as strut-specific metrics. To depict a fast overview of the strut quality, we introduce two innovative visual encodings, crucial for our collaborators’ research in creating novel AM parts: the Contour View and the Roughness Map, which depict critical geometrical and surface features of individual struts in standardized two 2D views. We evaluated the integrated system through expert interviews. The feedback confirms the framework’s practicality and its effectiveness in enhancing current inspection workflows. It solves major bottlenecks for our collaborators, ultimately helping them create novel parts with advanced properties.

Miao, Haichao [Lawrence Livermore National Laborat↗

DOE OSTI2022

Transactional Knowledge Graph Generation To Model Adversarial Activities

A Knowledge Graph (KG) is a formal and structured representation of facts, relationships, and semantic descriptions of a set of entities. Traditionally, KGs are used to describe metadata about entities and to provide additional context to target application results. Many real-world domains also involve temporal interactions between entities in addition to the metadata data. Modeling these attributed transactions is a critical requirement when using KGs in complex real-world applications. Modeling adversarial activities is one such application that develops methodology and tools to produce realistic large-scale background activity graphs that include embedded Weapons of Mass Destruction (WMD) activity patterns. We present a novel platform for constructing a transactional knowledge graph from a diverse set of sources. We present the core components and architecture of the framework, and a use case for generating a background knowledge graph and WMD activity template to evaluate network alignment and subgraph matching algorithms.

Purohit, Sumit↗

DOE OSTI2020

A Guide to Conquer the Biological Network Era Using Graph Theory

Networks are one of the most common ways to represent biological systems as complex sets of binary interactions or relations between different bioentities. In this article, we discuss the basic graph theory concepts and the various graph types, as well as the available data structures for storing and reading graphs. In addition, we describe several network properties and we highlight some of the widely used network topological features. We briefly mention the network patterns, motifs and models, and we further comment on the types of biological and biomedical networks along with their corresponding computer- and human-readable file formats. Finally, we discuss a variety of algorithms and metrics for network analyses regarding graph drawing, clustering, visualization, link prediction, perturbation, and network alignment as well as the current state-of-the-art tools. We expect this review to reach a very broad spectrum of readers varying from experts to beginners while encouraging them to enhance the field further.

59 BASIC BIOLOGICAL SCIENCES↗

DOE OSTI2024

A Causal Approach to Model Validation and Calibration

This poster presents a novel method for validation and verification that focuses on identifying causal relationships between data elements, moving beyond traditional statistical and machine learning approaches. These methods employ causal discovery techniques to reveal the underlying mechanisms of data generation. The research utilizes structural causal models and directed acyclic graphs to depict causal relationships. This approach assists in achieving alignment between simulation models and reality.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2026

AGFormer: Adaptive Spatiotemporal graph informed transformer for multi-reservoir inflow forecasting

Accurate reservoir inflow forecasting is crucial for effective water resource management, yet most machine learning models focus on single-reservoir prediction and overlook spatial dependencies among hydrologically connected reservoirs. Here, we propose AGFormer (Adaptive Graph-Informed Transformer), an end-to-end framework that integrates adaptive graph learning with temporal sequence modeling for multi-reservoir inflow forecasting. A shared encoder and graph attention mechanism generate reservoir-specific embeddings, which are then processed by the Transformer-based encoder–decoder for multi-step inflow forecasting. We also introduce a pretraining paradigm to learn robust temporal embeddings from misaligned historical records. Evaluated on 30 reservoirs in the Upper Colorado River Basin, AGFormer achieves superior seven-day-ahead forecasts, with NSE > 0.75 for 20 reservoirs—outperforming Encoder–Decoder LSTM, GCN+LSTM, and Transformer baselines. Adaptive graph learning captures dynamic inter-reservoir dependencies, and feature attribution aligns with snowmelt-driven hydrology. Incorporating forecasted meteorological inputs further enhances accuracy, demonstrating AGFormer’s potential to support reservoir management under dynamic hydrological conditions.

Adaptive graph learning↗

DOE OSTI2026

FAIR Data Meets FAIR Software

Modern scientific research is increasingly defined by the interplay between data, software, and the workflows that connect them. Yet while the FAIR (Findable, Accessible, Interoperable, Reusable) principles have become foundational for scientific data stewardship, the same level of structure and expectation has only recently begun to extend to research software. This talk covers why and how FAIR principles are being applied to data and software to support data reuse. It outlines the gaps in current sharing norms, the growing federal emphasis on persistent identifiers and public access, and the opportunities created when datasets, computational workflows, code, and models are linked through rich, standardized metadata. Practical implementation pathways for the EIC and JLab communities are described, including datacards for structured dataset documentation and provenance-aware workflows. By aligning data lifecycle management with FAIR-aligned software practices, the scientific community can advance toward autonomous knowledge graphs, generative workflows, and high-quality, AI-ready scientific datasets.

McSpadden, Diana [Thomas Jefferson National Accele↗

DOE OSTI2023

An Efficient High-Order Solver for Diffusion Equations with Strong Anisotropy on Non-Anisotropy-Aligned Meshes

This paper concerns numerical solution of the diffusion equation with strong anisotropy on meshes not aligned with the anisotropic vector field. In order to resolve the numerical pollution for simulations on a non-anisotropy-aligned mesh and reduce the associated high computational cost we propose an effective preconditioner, extending our previous work. Similar to the anisotropy-aligned mesh case, we apply the auxiliary space preconditioning framework to design a preconditioner where a continuous finite element space is used as the auxiliary space for the discontinuous finite element space. The key component is an effective line smoother that can mitigate the high-frequency errors perpendicular to the magnetic field. We design a graph-based approach to find such a line smoother that is approximately perpendicular to the vector fields when the mesh does not align with the anisotropy. Finally, numerical experiments for several benchmark problems are presented, demonstrating the effectiveness and robustness of the proposed preconditioner when applied to Krylov iterative methods.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2021

Learning an Algebriac Multrigrid Interpolation Operator Using a Modified GraphNet Architecture

This work, building on previous efforts, develops a suite of new graph neural network machine learning architectures that generate data-driven prolongators for use in Algebraic Multigrid (AMG). Algebraic Multigrid is a powerful and common technique for solving large, sparse linear systems. Its effectiveness is problem dependent and heavily depends on the choice of the prolongation operator, which interpolates the coarse mesh results onto a finer mesh. Previous work has used recent developments in graph neural networks to learn a prolongation operator from a given coefficient matrix. In this paper, we expand on previous work by exploring architectural enhancements of graph neural networks. A new method for generating a training set is developed which more closely aligns to the test set. Asymptotic error reduction factors are compared on a test suite of 3-dimensional Poisson problems with varying degrees of element stretching. Results show modest improvements in asymptotic error factor over both commonly chosen baselines and learning methods from previous work.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2022

Multiview Incomplete Knowledge Graph Integration with application to cross-institutional EHR data harmonization

Objective: The growing availability of electronic health records (EHR) data opens opportunities for integrative analysis of multi-institutional EHR to produce generalizable knowledge. A key barrier to such integrative analyses is the lack of semantic interoperability across different institutions due to coding differences. We propose a Multiview Incomplete Knowledge Graph Integration (MIKGI) algorithm to integrate information from multiple sources with partially overlapping EHR concept codes to enable translations between healthcare systems. Methods: The MIKGI algorithm combines knowledge graph information from (i) embeddings trained from the co-occurrence patterns of medical codes within each EHR system and (ii) semantic embeddings of the textual strings of all medical codes obtained from the Self-Aligning Pretrained BERT (SAPBERT) algorithm. Due to the heterogeneity in the coding across healthcare systems, each EHR source provides partial coverage of the available codes. MIKGI synthesizes the incomplete knowledge graphs derived from these multi-source embeddings by minimizing a spherical loss function that combines the pairwise directional similarities of embeddings computed from all available sources. MIKGI outputs harmonized semantic embedding vectors for all EHR codes, which improves the quality of the embeddings and enables direct assessment of both similarity and relatedness between any pair of codes from multiple healthcare systems. Results: With EHR co-occurrence data from Veteran Affairs (VA) healthcare and Mass General Brigham (MGB), MIKGI algorithm produces high quality embeddings for a variety of downstream tasks including detecting known similar or related entity pairs and mapping VA local codes to the relevant EHR codes used at MGB. Based on the cosine similarity of the MIKGI trained embeddings, the AUC was 0.918 for detecting similar entity pairs and 0.809 for detecting related pairs. For cross-institutional medical code mapping, the top 1 and top 5 accuracy were 91.0% and 97.5% when mapping medication codes at VA to RxNorm medication codes at MGB; 59.1% and 75.8% when mapping VA local laboratory codes to LOINC hierarchy. When trained with 500 labels, the lab code mapping attained top 1 and 5 accuracy at 77.7% and 87.9%. MIKGI also attained best performance in selecting VA local lab codes for desired laboratory tests and COVID-19 related features for COVID EHR studies. Compared to existing methods, MIKGI attained the most robust performance with accuracy the highest or near the highest across all tasks. Conclusions: The proposed MIKGI algorithm can effectively integrate incomplete summary data from biomedical text and EHR data to generate harmonized embeddings for EHR codes for knowledge graph modeling and cross-institutional translation of EHR codes.

Zhou, Doudou↗

DOE OSTI2023

A Data Processing Pipeline for Adversarial Socio-Technical Network Analysis

With the rapid adoption of emerging technologies, there is a need to catalog and model sociotechnical interdependencies that have been historically used to influence the operation of Critical Infrastructure networks including the impacts of mergers and acquisitions, hostile takeovers, and foreign investment. Our research intends to address this need with two primary contributions. First, we have developed a data curation and processing pipeline to generate sociotechnical networks extracted from a variety of data sources including SEC filings and infrastructure asset databases. The pipeline, implemented in Apache Airflow, extracts and normalizes the representation of entities and relations, specified within ontologies. Our intent is to provide an extensible, machine-actionable approach to quickly communicate such models, reproduce previous results, and adapt them to new, unanticipated situations. Second, networks produced by our pipeline enable the development of graph-theoretic metrics that consider the properties of network components in addition to its topology. Metadata associated with network components---whether semantic, temporal, or geospatial---affects the alignment of generated networks with assumptions underlying complexity metrics. Validation of generated networks relative to component types defined by an ontology, may allow the research community to adapt metrics to the semantics of the domains being studied. Generated networks may be processed as knowledge, dynamic, or spatial graphs and enables a variety of analyses including automated reasoning and measures of network complexity. Automated reasoning views extracted entities and relations as a knowledge graph; this enables application of inference rules that represent historically-attested adversarial business methods and applies that behavior to a specific geographic context. Measures of network complexity, including degree distribution, reachability analyses, temporal analysis, and community detection can be adapted to indicate adversarial organizational influence.

97 MATHEMATICS AND COMPUTING↗