Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “GRAPH”

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 559 records · Page 31
All sourcesNASA NTRSDOE OSTI
DOE OSTI2017

Task-based Parallel Computation of the Density Matrix in Quantum-based Molecular Dynamics using Graph Partitioning

Quantum-based molecular dynamics (QMD) is a highly accurate and transferable method for material science simulations. However, the time scales and system sizes accessible to QMD are typically limited to picoseconds and a few hundred atoms. These constraints arise due to expensive self-consistent ground-state electronic structure calculations that can often scale cubically with the number of atoms. Linearly scaling methods depend on computing the density matrix P from the Hamiltonian matrix H by exploiting the sparsity in both matrices. The second-order spectral projection (SP2) algorithm is an O(N) algorithm that computes P with a sequence of 40 - 50 matrix-matrix multiplications. In this paper, we present task-based implementations of a recently developed data-parallel graph-based approach to the SP2 algorithm, G-SP2. We represent the density matrix P as an undirected graph and use graph partitioning techniques to divide the computation into smaller independent tasks. The partitions thus obtained are generally not of equal size and give rise to undesirable load imbalances in standard MPI-based implementations. This load-balancing challenge can be mitigated by dynamically scheduling parallel computations at runtime using task-based programming models. We develop task-based implementations of the data-parallel G-SP2 algorithm using both Intel's Concurrent Collections (CnC) as well as the Charm++ programming model and evaluate these implementations for future use. Scaling and performance results of our implementations are investigated for representative segments of QMD simulations for solvated protein systems containing more than 10,000 atoms.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2013

Fast Search for Dynamic Multi-Relational Graphs

Acting on time-critical events by processing ever growing social media or news streams is a major technical challenge. Many of these data sources can be modeled as multi-relational graphs. Continuous queries or techniques to search for rare events that typically arise in monitoring applications have been studied extensively for relational databases. This work is dedicated to answer the question that emerges naturally: how can we efficiently execute a continuous query on a dynamic graph? This paper presents an exact subgraph search algorithm that exploits the temporal characteristics of representative queries for online news or social media monitoring. The algorithm is based on a novel data structure called the that leverages the structural and semantic characteristics of the underlying multi-relational graph. The paper concludes with extensive experimentation on several real-world datasets that demonstrates the validity of this approach.

Choudhury, Sutanay↗
DOE OSTI2016

User-Assisted Store Recycling for Dynamic Task Graph Schedulers

The emergence of the multi-core era has led to increased interest in designing effective yet practical parallel programming models. Models based on task graphs that operate on single-assignment data are attractive in several ways: they can support dynamic applications and precisely represent the available concurrency. However, they also require nuanced algorithms for scheduling and memory management for efficient execution. In this paper, we consider memory-efficient dynamic scheduling of task graphs. Specifically, we present a novel approach for dynamically recycling the memory locations assigned to data items as they are produced by tasks. We develop algorithms to identify memory-efficient store recycling functions by systematically evaluating the validity of a set of (user-provided or automatically generated) alternatives. Because recycling function can be input data-dependent, we have also developed support for continued correct execution of a task graph in the presence of a potentially incorrect store recycling function. Experimental evaluation demonstrates that our approach to automatic store recycling incurs little to no overheads, achieves memory usage comparable to the best manually derived solutions, often produces recycling functions valid across problem sizes and input parameters, and efficiently recovers from an incorrect choice of store recycling functions.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2019

Scalable Causal Graph Learning through a Deep Neural Network

Learning the causal graph in a complex system is crucial for knowledge discovery and decision making, yet it remains a challenging problem because of the unknown nonlinear interaction among system components. Most of the existing methods either rely on predefined kernel or data distribution, or they focus simply on the causality between a single target and the remaining system. This work presents a deep neural network for scalable causal graph learning (SCGL) through low-rank approximation. The SCGL model can explore nonlinearity on both temporal and intervariable relationships without any predefined kernel or distribution assumptions. Through low-rank approximation, the noise influence is reduced, and better accuracy and high scalability are achieved. Experiments using synthetic and real-world datasets show that our SCGL algorithm outperforms existing state-of-the-art methods for causal graph learning.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2021

Single-node Partitioned-Memory for Huge Graph Analytics: Cost and Performance Trade-offs

Nonvolatile memory NVDIMMs, available as Intel Optane, are less expensive than DRAM and bring large byte-addressable storage within reach to many applications. Evaluations on graph analytics have shown promising performance only when DRAM is used as a hardware cache (Memory mode). An open question is whether graph applications can exploit Optane and DRAM directly (AppDirect mode) and achieving better-than-DRAM average bandwidth and run times. We evaluate Optane as a volatile pool on two large-scale graph applications with very different computational patterns, Grappolo and Ripples. We show that AppDirect mode can deliver better-than-DRAM performance, by allocating data structures to Optane and DRAM according to their access characteristics, resulting in higher average memory bandwidth and lower average latency. Memory mode provides DRAM-competitive performance with capacity equal to persistent memory. We demonstrate occasional 4x improvement using the latest AppDirect option and frequently observe competitive performance between Optane AppDirect Memory modes and DRAM.

Ghosh, Sayan↗
DOE OSTI2021

I-GCN: A Graph Convolutional Network Accelerator with Runtime Locality Enhancement through Islandization

In this paper, we propose a novel hardware accelerator for GCN inference called I-GCN that significantly improves data locality and reduces unnecessary computation through a new online graph restructuring algorithm we refer to as islandization. The proposed algorithm finds clusters of nodes with strong internal but weak external connections. The islandization process yields two major benefits. First, by processing islands rather than individual nodes, there is better on-chip data reuse and fewer off-chip memory accesses. Second, there is less redundant computation as aggregation for common/shared neighbors in an island can be reused. The parallel search, identification, and leverage of graph islands are all handled purely in hardware at runtime working in an incremental pipelined manner. This is done without any preprocessing of the graph data or adjustment of the GCN model structure.

Geng, Tong↗
DOE OSTI2021

Neuromorphic Graph Algorithms: Cycle Detection, Odd Cycle Detection, and Max Flow

Neuromorphic computing is poised to become a promising computing paradigm in the post Moore’s law era due to its extremely low power usage and inherent parallelism. Spiking neural networks are the traditional use case for neuromorphic systems, and have proven to be highly effective at machine learning tasks such as control problems. More recently, neuromorphic systems have been applied outside of the arena of machine learning, primarily in the field of graph algorithms. Neuromorphic systems have been shown to perform graph algorithms faster and with lower power consumption than their traditional (GPU/CPU) counterparts, and are hence an attractive option for a co-processing unit in future high performance computing systems, where graph algorithms play a critical role. In this paper, we present a neuromorphic implementation of cycle detection, odd cycle detection, and the Ford-Fulkerson max-flow algorithm. We further evaluate the performance of these implementations using the NEST neuromorphic simulator by using spike counts and simulation time as proxies for energy consumption and run time. In addition to gains inherent in neuromorphic systems, we show that within the neuromorphic implementations early stopping criteria can be implemented to further improve performance.

Kay, Bill↗
DOE OSTI2021

Conflation of Geospatial POI Data and Ground-level Imagery via Link Prediction on Joint Semantic Graph

With the proliferation of smartphone cameras and social networks, we have rich, multi-modal data about points of interest (POIs) - like cultural landmarks, institutions, businesses, etc. - within a given areas of interest (AOI) (e.g., a county, city or a neighborhood) available to us. Data conflation across multiple modalities of data sources is one of the key challenges in maintaining a geographical information system (GIS) which accumulate data about POIs. Given POI data from nine different sources, and ground-level geo-tagged and scene-captioned images from two different image hosting platforms, in this work we explore the application of graph neural networks (GNNs) to perform data conflation, while leveraging a natural graph structure evident in geospatial data. The preliminary results demonstrate the capacity of a GNN operation to learn distributions of entity (POIs and images) features, coupled with topological structure of entity's local neighborhood in a semantic nearest neighbor graph, in order to predict links between a pair of entities.

Gurav, Rutuja↗
DOE OSTI2025

AI-Powered Knowledge Graphs for Neuromorphic and Energy-Efficient Computing

The surge in scientific literature obscures breakthroughs and hinders the discovery of new research paths. We propose an artificial intelligence (AI) powered framework using large language models (LLMs) and knowledge graphs (KGs) to automate parts of scientific discovery, focusing on energy-efficient AI circuits. Our hybrid approach combines LLMs, structured data, and ontology-based reasoning to construct a comprehensive knowledge graph that integrates insights across computational neuroscience, spiking neuron models, learning rules, architectural motifs, and neuromorphic device technologies. This multi-domain representation enables the generation of hypotheses that connect biological function with implementable, energy-efficient hardware architectures. Using KG embeddings and graph neural networks, the framework generates hypotheses for novel circuits, validates them through optimization on exascale HPC systems, and with tools like SuperNeuro and Fugu, the most promising designs will be prototyped in hardware. This open-source system aims to accelerate discoveries and bridging neuroscience with hardware innovation, drive collaboration, and unlock new opportunities in low-power AI computing.

Gautam, Ashish [ORNL]↗
DOE OSTI2022

MSASGCN : Multi-Head Self-Attention Spatiotemporal Graph Convolutional Network for Traffic Flow Forecasting

Traffic flow forecasting is an essential task of an intelligent transportation system (ITS), closely related to intelligent transportation management and resource scheduling. Dynamic spatial-temporal dependencies in traffic data make traffic flow forecasting to be a challenging task. Most existing research cannot model dynamic spatial and temporal correlations to achieve well-forecasting performance. The multi-head self-attention mechanism is a valuable method to capture dynamic spatial-temporal correlations, and combining it with graph convolutional networks is a promising solution. Therefore, we propose a multi-head self-attention spatiotemporal graph convolutional network (MSASGCN) model. It can effectively capture local correlations and potential global correlations of spatial structures, can handle dynamic evolution of the road network, and, in the time dimension, can effectively capture dynamic temporal correlations. Experiments on two real datasets verify the stability of our proposed model, obtaining a better prediction performance than the baseline algorithms. The correlation metrics get significantly reduced compared with traditional time series prediction methods and deep learning methods without using graph neural networks, according to MAE and RMSE results. Compared with advanced traffic flow forecasting methods, our model also has a performance improvement and a more stable prediction performance. We also discuss some problems and challenges in traffic forecasting.

Cao, Yang↗
DOE OSTI2017

NOUS: A Knowledge Graph Management System

Knowledge graphs represent information as entities and relationships between them. For tasks such as natural language question answering or automated analysis of text, a knowledge graph provides valuable context to establish the specific type of entities being discussed. It allow us to derive better context about newly arriving information and leads to intelligent reasoning capabilities. We address two primary needs: A) Automated construction of knowledge graphs is a technically challenging, expensive process; and B) The ability to synthesize new information by monitoring newly emerging knowledge is a transformational capability that does not exist in state of the art systems.

Source record↗
DOE OSTI2023

GRAPH CONVOLUTIONAL NEURAL NETWORK (GCNN)FOR POLYMER PROPERTY PREDICTION

SF-22-121 Graph convolutional neural networks (GCNN) are powerful machine learning models that apply a message-passing algorithm on adjacent nodes in a graph. Due to the natural representation of molecules via discrete graphs (where nodes encode atoms and edges encode bonds), GCNNs are an intuitive machine learning model chemical space informatics, including the prediction of polymer properties. Here, molecules are represented in feature and adjacency matrices where they are directly used as inputs to a GCNN.

FEINSTEIN, JEREMY↗
DOE OSTI2019

temporal-graphs/STM

Structural Temporal Modeling Generating a synthetic graph that is similar to a given real- world graph is a critical requirement for privacy preservation and benchmarking purposes. This software presents a temporal-motif based approach to generate synthetic temporal graph datasets.

Purohit, Sumit↗
DOE OSTI2025

Graph-based Reversible Evaluation and Tangents Library

GRETL is a C++ library for evaluation, re-evaluation and algorithmic differentiation of functional operations on an arbitrary computational graph with limited memory usage. Similar to popular machine learning frameworks in Python, like PyTorch and JAX, it tracks and stores both operations and output data as functions are evaluated. Once this composition of functions is built up, the entire chain of operations can be back propagated to compute sensitivities of the final result with respect to any number of inputs. In contrast to most machine learning applications, memory usage becomes the bottleneck for back propagation in many physics applications, especially for time-dependent PDEs. Dynamic check pointing becomes essential. An important distinguishing feature of GRETL is its ability to limit the maximum memory usage by automatically dynamic checkpointing the data output for each graph operation (see Wang, Moin, Iaccarino, 2009). During backpropagation, parts of the graph that are no longer in memory are automatically re-evaluated from upstream checkpointed states as needed for derivative sensitivity calculations (or more precisely, for vector-Jacobian products). GRETL is particularly beneficial for applications, such as coupled multi-physics, where deriving adjoint-based sensitivities and managing checkpoint memory across modules becomes onerous. Cases which can be readily handled by the GRETL library include: different time-integration algorithms per physics (e.g., coupled predictor-corrector algorithms, IMEX, etc.), sub-cycling, asynchronous integrators, state dependent timestep sizes, iterative solvers and coupling algorithms, controller algorithms, and more.

Tupek, MichaelR [Lawrence Livermore National Labor↗
DOE OSTI2022

Graph link prediction in computer networks using Poisson matrix factorisation

Graph link prediction is an important task in cybersecurity: relationships between entities within a computer network, such as users interacting with computers or system libraries and the corresponding processes that use them, can provide key insights into adversary behaviour. Poisson matrix factorisation (PMF) is a popular model for link prediction in large networks, particularly useful for its scalability. In this article PMF is extended to include scenarios that are commonly encountered in cybersecurity applications. Specifically, an extension is proposed to explicitly handle binary adjacency matrices and include known categorical covariates associated with the graph nodes. A seasonal PMF model is also presented to handle seasonal networks. To allow the methods to scale to large graphs, variational methods are discussed for performing fast inference. The results show an improved performance over the standard PMF model and other statistical network models.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2024

HydraGNN_Predictive_GFM_2024 - Ensemble of predictive graph foundation models for ground state atomistic materials modeling

We provide the ensemble of fifteen pre-trained graph foundation models (GFMs) for atomistic materials modeling applications. Each one of the fifteen GFMs has been trained on five open-source datasets that (once aggregated) amount to over 154 million atomistic structures, which cover over two-thirds of the natural elements of the periodic table and that comprises a broad set of organic and inorganic compounds. This vast set of atomistic structures comprises ground state configurations that are dynamically stable (i.e., equilibrated structures with atomic forces approximately close to zero values) as well as dynamically unstable structures (i.e., non-equilibrium structures with non-negligible non-zero values of atomic forces). The ensemble of datasets aggregated does NOT include excited states. The datasets have been curated to remove atomistic structures with spectral norm of the force tensor above 100 eV/angstrom. Moreover, a linear term of the energy was computed for each dataset using a linear regression model that uses the chemical concentration of each natural element as regressor. The linear term predicted by the linear regression model has been subtracted from each original energy value to perform a re-alignment of the energy values across different electronic structures approximation theories performed to generate the diverse multi-source, multi-fidelity datasets. The folder "ADIOS_files" contains the set of pre-processed datasets in Adaptable I/O System (ADIOS) format (https://www.exascaleproject.org/research-project/adios/) that have been used for the development and training of GFMs in this work. The "ADIOS_files" directory contains 6 sub-directories named as follows: - ANI1x-v3.bp - MPTrj-v3.bp - OC2020-20M-v3.bp - OC2020-v3.bp - OC2022-v3.bp - qm7x-v3.bp Each sub-directory contains the pre-processed datasets converted in Adaptable I/O System (ADIOS) format (https://www.exascaleproject.org/research-project/adios/) that have been used to the development, training, and performance testing of the ensemble go predictive graph foundation models. Each GFM was developed using HydraGNN (https://github.com/ORNL/HydraGNN) as underlying graph neural network (GNN) architecture. The multi-task learning (MTL) capability of HydraGNN was used to simultaneously train the GFMs on labeled values for direct predictions of energy (a total system property of an atomistic structure that measures the chemical stability) and atomic forces (an atomic level property of an atomistic structure that measures the dynamical stability). The hyper parameters of the GFM have been tuned using scalable hyperparameter optimization (HPO) algorithms implemented in the software DeepHyper (https://github.com/deephyper/deephyper). The pre-training of each HPO trial was performed using distributed data parallelism (DDP) to scale the training across 128 compute nodes of the exascale OLCF supercomputer Frontier. Each HPO trial was trained only for 10 epochs and an early stopping was performed to avoid wasting significant computational resources on GNN architectures that were clearly underperforming. For each HPO trial, the 'omnistat' tool developed by (AMD Research - Advanced Micro Device) was used to measure the total energy consumption in kWh. The ensemble of GFMs was obtained by selecting the fifteen best performing HPO trials. Four models have been selected for their clear advantage in accuracy, and these are the GFMs with IDs 229, 156, 147, 260. Additional eleven models have been selected based on judicious balance between accuracy and energy consumption needed for training, and these are the GFMs with IDs 165, 78, 137, 1, 175, 171, 181, 67, 179, 167, 351. Each selected GFM of the ensemble was continued to cumulate a total of at most 30 epochs. In some cases, the total number of epochs actually performed was les than 30 due to two combined factors: (1) the size of the GFM (i.e., the number of model parameters to train) and (2) the total wall-clock time for which the computational resources could be allocated on OLCF-Frontier. The "Ensemble_of_models" directory contains 15 sub-directories named as follows: - gfm_0.229 - gfm_0.156 - gfm_0.147 - gfm_0.260 - gfm_0.165 - gfm_0.78 - gfm_0.137 - gfm_0.1 - gfm_0.175 - gfm_0.171 - gfm_0.181 - gfm_0.67 - gfm_0.179 - gfm_0.167 - gfm_0.351 Each one of these sub-directories refers to one of the fifteen HPO trials that have been selected to continue the pre-training with at most 30 epochs. With each sub-directory associated with a specific HPO trial, the following files can be found: - config.json: file for argument parsing to develop and train an HydraGNN architecture - gfm_0.ID_epoch_N.pk: file with model parameters for HPO ID trial after N epochs of training The ensemble of fifteen GFM architectures was used for (1) ensemble averaging to stabilize the predictions of energy and atomic forces after pre-training for post-processing analysis and (2) ensemble uncertainty quantification (UQ). The code used to develop, pre-train, and load the pre-trained models for post-processing analysis is available on the ORNL-GitHub at the following link: https://github.com/ORNL/HydraGNN/tree/Predictive_GFM_2024

36 MATERIALS SCIENCE↗
DOE OSTI2012

The Graph Laplacian and the Dynamics of Complex Networks [Slides]

In this talk, we explore the structure of networks from a spectral graph-theoretic perspective by analyzing the properties of the Laplacian matrix associated with the graph induced by a network. We will see how the eigenvalues of the graph Laplacian relate to the underlying network structure and dynamics and provides insight into a phenomenon frequently observed in real world networks - the emergence of collective behavior from purely local interactions seen in the coordinated motion of animals and phase transitions in biological networks, to name a few.

97 MATHEMATICS AND COMPUTING↗