Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “Graphs”

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 127 records · Page 7
All sourcesNASA NTRSDOE OSTI
DOE OSTI2021

A variant selection framework for genome graphs

Abstract Motivation Variation graph representations are projected to either replace or supplement conventional single genome references due to their ability to capture population genetic diversity and reduce reference bias. Vast catalogues of genetic variants for many species now exist, and it is natural to ask which among these are crucial to circumvent reference bias during read mapping. Results In this work, we propose a novel mathematical framework for variant selection, by casting it in terms of minimizing variation graph size subject to preserving paths of length α with at most δ differences. This framework leads to a rich set of problems based on the types of variants [e.g. single nucleotide polymorphisms (SNPs), indels or structural variants (SVs)], and whether the goal is to minimize the number of positions at which variants are listed or to minimize the total number of variants listed. We classify the computational complexity of these problems and provide efficient algorithms along with their software implementation when feasible. We empirically evaluate the magnitude of graph reduction achieved in human chromosome variation graphs using multiple α and δ parameter values corresponding to short and long-read resequencing characteristics. When our algorithm is run with parameter settings amenable to long-read mapping (α = 10 kbp, δ = 1000), 99.99% SNPs and 73% SVs can be safely excluded from human chromosome 1 variation graph. The graph size reduction can benefit downstream pan-genome analysis. Availability and implementation https://github.com/AT-CG/VF. Supplementary information Supplementary data are available at Bioinformatics online.

59 BASIC BIOLOGICAL SCIENCES↗
DOE OSTI2020

Spin-Orbit-Induced Topological Flat Bands in Line and Split Graphs of Bipartite Lattices

Topological flat bands, such as the band in twisted bilayer graphene, are becoming a promising platform to study topics such as correlation physics, superconductivity, and transport. In this Letter, we introduce a generic approach to construct two-dimensional (2D) topological quasiflat bands from line graphs and split graphs of bipartite lattices. A line graph or split graph of a bipartite lattice exhibits a set of flat bands and a set of dispersive bands. The flat band connects to the dispersive bands through a degenerate state at some momentum. We find that, with spin-orbit coupling (SOC), the flat band becomes quasiflat and gapped from the dispersive bands. By studying a series of specific line graphs and split graphs of bipartite lattices, we find that (i) if the flat band (without SOC) has inversion or C 2 symmetry and is nondegenerate, then the resulting quasiflat band must be topologically nontrivial, and (ii) if the flat band (without SOC) is degenerate, then there exists a SOC potential such that the resulting quasiflat band is topologically nontrivial. This generic mechanism serves as a paradigm for finding topological quasiflat bands in 2D crystalline materials and metamaterials.

36 MATERIALS SCIENCE↗
DOE OSTI2023

Hyperparameter Optimization and Feature Inclusion in Graph Neural Networks for Spiking Implementation

Graph convolutional networks leverage both graph structures and features on nodes and edges for improved learning performance in comparison with classical machine learning approaches. Spiking neuromorphic computers natively implement network-like computation and have been shown to be successful at implementing graph learning without features. Incorporating graph features brings the challenge of efficient feature representation and balancing the contribution of topology and features in learning. In this work, we present our design of a simulated network of spiking neurons to perform semi-supervised learning on graph data using both the graph structure and the node features. We explore various design choices, present preliminary results, and discuss the opportunities for using neuromorphic computers for this task in the future.

Cong, Guojing↗
DOE OSTI2020

AWB-GCN: A Graph Convolutional Network Accelerator with Runtime Workload Rebalancing

The recent development of deep learning has been mostly focusing on Euclidean data, such as images, videos, audios, etc. However, most real-world information and relation are often expressed as graphs. To efficiently learn from graph data, graph convolutional networks (GCNs) emerge as a promising approach, showing advantages in several practical applications such as social network analysis, knowledge discovery, 3D modeling, motion capturing, etc. Real-world graphs are usually extremely large and imbalanced, posting significant performance demand and design challenges on the hardware dedicated for GCN inference. In this paper, we propose an architecture design called UW-GCN to accelerate graph convolutional network inference. To tackle the major performance bottleneck from workload imbalance, we propose dynamic neighborhood stealing and remote chunk shuffling techniques, relying on hardware flexibility to achieve hardware auto-tuning under negligible area or delay overhead. Specifically, UW-GCN is able to smartly profile the sparse graph pattern while continuously adjusting the workload distribution via routing reconfiguration among parallel processing elements (PEs). The ideal configuration is then reused in the remaining iterations. To the best of our knowledge, this is the first accelerator design particularly for GCN and the first work relying on hardware auto-tuning, which is normally based on software, to achieve near-optimal workload balance in processing sparse structures.

Geng, Tong↗
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

Multi-Edge Graph Convolutional Networks for Power Systems

The exponential electrification of transportation has contributed to highly intermittent load variations in the distribution grid. This uncertainty has raised challenges for distribution system operation and control. Accurate nodal voltage estimation is highly essential for the safe and reliable operation of the grid. Graph convolutional networks have been used in machine-learning-based models for power grid applications like voltage estimation for their ability to capture the network topology of the grid. This paper presents a novel multi-edge graph convolutional layer that considers resistance and reactance as edge attributes. This layer is created by modifying the message-passing function within the graph convolutional network. The novel layer is then used to create a multi-edge graph convolutional network-based surrogate model for estimating voltage in the distribution network with highly uncertain electric vehicle loads. Results indicate improved performance of the multi-edge graph convolutional network model when compared to a standard graph convolutional network model.

Ravi, Abhijith↗
DOE OSTI2023

Session Introduction: Graph Representations and Algorithms in Biomedicine

Connectivity is a fundamental property of biological systems: on the cellular level, proteins interact with each other to form protein-protein interaction networks (PPIs); on the organism level, neurons are arranged in a network; and on a community-level, species can have complex relationships with one another that drive the development and balance of an ecosystem. Graphs, representations of systems consisting of entities as vertices and their connections as edges, are a useful structure to characterize many such systems. Such models can be used to understand biological systems that naturally have a network structure, including PPIs, biological neurons, and ecosystems. In today’s information age, graph representations and algorithms (often in combination with machine learning techniques) are used to organize massive amounts of related data, much of which may be heterogeneous or unstructured, and identify patterns that represent novel biological insights. PSB’s 2023 session “Graph Representations and algorithms in Biomedicine,” encompasses modern developments in graph theory and its applications to various fields of biomedicine. This session includes a wide range of research - knowledge graphs built from text-mined health data, heterogeneous networks using multi-omic databases, and graphs refined to represent uncertainty or improve memory usage.

Chrisman, Brianna S.↗
DOE OSTI2020

Quantifying Graph Uncertainty from Communication Data

Graphs are a widely used abstraction for representing a variety of important real-world problems including emulating cyber networks for situational awareness, or studying social networks to understand human interactions or pandemic spread. Communication data is often converted into graphs to help understand social and technical patterns in the underlying communication data. However, prior to this project, little work had been performed analyzing how best to develop graphs from such data. Thus, many critical, national security problems were being performed against graph representations of questionable quality. Herein, we describe our analyses that were precursors to our final statistically grounded technique for creating static graph snapshots from a stream of communication events. The first analyzes the statistical distribution properties of a variety of real-world communication datasets generally fit best by Pareto, log normal, and extreme value distributions. The second derives graph properties that can be estimated given the expected statistical distribution for communication events and the communication interval to be viewed node observability, edge observability, and expected accuracy of node degree. Unfortunately, as that final process is under review for publication, we can't publish it here at this time.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2024

Portable Parallel Algorithms and Frameworks for Exascale Graph Analytics

Graphs (or networks) are a tool used to model the interactions among various entities. Efficiently processing large graphs has recently attracted significant attention due to the applications of graphs in various domains, such as biology, chemistry, and cyber-security. Analyzing the structure and properties of these graphs is an important component of many scientific computing pipelines. With the explosion in the volume of data, graphs have become very large and can contain hundreds of billions of vertices and trillions of edges. Therefore, it is crucial to develop high-performance methods to enable graph analysis to be done quickly and energy-efficiently. Furthermore, these solutions should be highly parallel in order to take advantage of modern parallel machines. However, designing efficient solutions is not enough. With the wide variety of computing environments available, each with different programmability and performance characteristics, it is necessary to develop solutions that are portable in terms of both performance (i.e., provide theoretical guarantees) and programmability (i.e., provide high level abstractions).

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2023

FPGA Acceleration of GCN in Light of the Symmetry of Graph Adjacency Matrix

Graph Convolutional Neural Networks (GCNs) are widely used to process large-scale graph data. Different from deep neural networks (DNNs), GCNs are sparse, irregular, and unstructured, posing unique challenges to hardware acceleration with regular processing elements (PEs). In particular, the adjacency matrix of a GCN is extremely sparse, leading to frequent but irregular memory access, low spatial/temporal data locality and poor data reuse. Furthermore, a realistic graph usually consists of unstructured data (e.g., unbalanced distributions), creating significantly different processing times and imbalanced workload for each node in GCN acceleration. To overcome these challenges, we propose an end-to-end hardware-software co-design to accelerate GCNs on resource-constrained FPGAs with the features including: (1) A custom dataflow that leverages symmetry along the diagonal of the adjacency matrix to accelerate feature aggregation for undirected graphs. We utilize either the upper or the lower triangular matrix of the adjacency matrix to perform aggregation in GCN to improve data reuse. (2) Unified compute cores for both aggregation and transform phases, with full support to the symmetry-based dataflow. These cores can be dynamically reconfigured to the systolic mode for transformation or as individual accumulators for aggregation in GCN processing. (3) Preprocessing of the graph in software to rearrange the edges and features to match the custom dataflow. This step improves the regularity in memory access and data reuse in the aggregation phase. Moreover, we quantize the GCN precision from FP32 to INT8 to reduce the memory footprint without losing the inference accuracy. We implement our accelerator design in Intel Stratix10 MX FPGA board with HBM2, and demonstrate 1.3x-110.5x improvement in end-to-end GCN latency as compared to the state-of the-art FPGA implementations, on the graph datasets of Cora, Pubmed, Citeseer and Reddit.

Nair, Gopikrishnan R.↗
DOE OSTI2024

A Comparison between Invariant and Equivariant Classical and Quantum Graph Neural Networks

Machine learning algorithms are heavily relied on to understand the vast amounts of data from high-energy particle collisions at the CERN Large Hadron Collider (LHC). The data from such collision events can naturally be represented with graph structures. Therefore, deep geometric methods, such as graph neural networks (GNNs), have been leveraged for various data analysis tasks in high-energy physics. One typical task is jet tagging, where jets are viewed as point clouds with distinct features and edge connections between their constituent particles. The increasing size and complexity of the LHC particle datasets, as well as the computational models used for their analysis, have greatly motivated the development of alternative fast and efficient computational paradigms such as quantum computation. In addition, to enhance the validity and robustness of deep networks, we can leverage the fundamental symmetries present in the data through the use of invariant inputs and equivariant layers. In this paper, we provide a fair and comprehensive comparison of classical graph neural networks (GNNs) and equivariant graph neural networks (EGNNs) and their quantum counterparts: quantum graph neural networks (QGNNs) and equivariant quantum graph neural networks (EQGNN). The four architectures were benchmarked on a binary classification task to classify the parton-level particle initiating the jet. Based on their area under the curve (AUC) scores, the quantum networks were found to outperform the classical networks. However, seeing the computational advantage of quantum networks in practice may have to wait for the further development of quantum technology and its associated application programming interfaces (APIs).

Forestano, Roy T. (ORCID:0000000203552076)↗
NASA NTRS2003

Using Bond Graphs for Articulated, Flexible Multi-bodies, Sensors, Actuators, and Controllers with Application to the International Space Station

Conceptually, modeling of flexible, multi-body systems involves a formulation as a set of time-dependent partial differential equations. However, for practical, engineering purposes, this modeling is usually done using the method of Finite Elements, which approximates the set of partial differential equations, thus generalizing the approach to all continuous media. This research investigates the links between the Bond Graph method and the classical methods used to develop system models and advocates the Bond Graph Methodology and current bond graph tools as alternate approaches that will lead to a quick and precise understanding of a flexible multi-body system under automatic control. For long endurance, complex spacecraft, because of articulation and mission evolution the model of the physical system may change frequently. So a method of automatic generation and regeneration of system models that does not lead to implicit equations, as does the Lagrange equation approach, is desirable. The bond graph method has been shown to be amenable to automatic generation of equations with appropriate consideration of causality. Indeed human-interactive software now exists that automatically generates both symbolic and numeric system models and evaluates causality as the user develops the model, e.g. the CAMP-G software package. In this paper the CAMP-G package is used to generate a bond graph model of the International Space Station (ISS) at an early stage in its assembly, Zvezda. The ISS is an ideal example because it is a collection of bodies that are articulated, many of which are highly flexible. Also many reaction jets are used to control translation and attitude, and many electric motors are used to articulate appendages, which consist of photovoltaic arrays and composite assemblies. The Zvezda bond graph model is compared to an existing model, which was generated by the NASA Johnson Space Center during the Verification and Analysis Cycle of Zvezda.

Montgomery, Raymond C.↗
NASA NTRS2003

Automated Modeling and Simulation Using the Bond Graph Method for the Aerospace Industry

Bond graph modeling was originally developed in the late 1950s by the late Prof. Henry M. Paynter of M.I.T. Prof. Paynter acted well before his time as the main advantage of his creation, other than the modeling insight that it provides and the ability of effectively dealing with Mechatronics, came into fruition only with the recent advent of modern computer technology and the tools derived as a result of it, including symbolic manipulation, MATLAB, and SIMULINK and the Computer Aided Modeling Program (CAMPG). Thus, only recently have these tools been available allowing one to fully utilize the advantages that the bond graph method has to offer. The purpose of this paper is to help fill the knowledge void concerning its use of bond graphs in the aerospace industry. The paper first presents simple examples to serve as a tutorial on bond graphs for those not familiar with the technique. The reader is given the basic understanding needed to appreciate the applications that follow. After that, several aerospace applications are developed such as modeling of an arresting system for aircraft carrier landings, suspension models used for landing gears and multibody dynamics. The paper presents also an update on NASA's progress in modeling the International Space Station (ISS) using bond graph techniques, and an advanced actuation system utilizing shape memory alloys. The later covers the Mechatronics advantages of the bond graph method, applications that simultaneously involves mechanical, hydraulic, thermal, and electrical subsystem modeling.

Granda, Jose J.↗
NASA NTRSDate not supplied

Populating a Graph Database to Run a Usage-Based Discovery Tool

Most dataset discovery tools for Earth Observation data rely on descriptions and other metadata of the datasets, using keyword searches or attribute filtering to determine relevance. However, these descriptions often do not include the potential uses of the data. Thus, a user working on floods will rarely see few if any rainfall datasets show up in such a search. The Usage Based Discovery tool, on the other hand, offers usage instances to the user, either research articles or applications, along with the datasets that those usage instances used. This allows a user, particularly one new to the world of Earth Observation data, to investigate which datasets are used in similar cases. The information that powers Usage-Based Discovery is a graph database of relationships of usage to dataset and usage to topic, allowing the user to narrow their search for similar cases. In order to scale out to a graph database rich enough to provide a satisfactory user experience, we combine manual and automated processes to populate the graph. The initial content of the graph has been seeded primarily via human-aided data curation methods, using sites like Google Scholar. To scale up this effort, we’ve employed crowdsourcing. It is easy for anyone to contribute to our graph using their Open Researcher and Contributor Identifier for authorization. We’re now experimenting with Machine Learning and Natural Language Processing to help automate population of the graph, starting with the classification of research articles by topic. Finding adequate training data in the absence of a comprehensive and open research article API continues to be a significant challenge.

Vincent Inverso↗
NASA NTRSDate not supplied

Verb Sense Disambiguation for Densifying Knowledge Graphs in Earth Science

We begin with an ambitious goal: to create a knowledge graph that spans the entire discipline of Earth science. In order to achieve this, we need to apply Natural Language Processing (NLP) techniques on Earth science journal articles to extract their semantic components for the graph. When sentences from Earth science journal articles are broken down into their semantic components and loaded onto a graph, the relationships among these semantic components are represented by the verbs in the sentences. However, since there are multiple verbs in English that can be used to denote the same meaning, the knowledge graph can become sparse and so can the results when we query the graph. In order to ensure quality results, it would be desirable to consolidate similar verbs into a single "class". So, this is the problem at hand: how do we make sure that multiple verbs that mean the same thing are represented as a single class of verb in the knowledge graph? Or in other words, how do we distinguish which meaning a particular verb takes given a particular sentence? In this poster, we demonstrate a potential technique to solve this problem.

Ashish Acharya↗
DOE OSTI2025

Nature-GL: A Revolutionary Learning Paradigm Unleashing Nature’s Power in Real-World Spatial-Temporal Graph Learning

Spatial-Temporal Graph Learning (ST-GL) is a prominent research area due to its unique capability to effectively learn real-world graphs. Applications of ST-GL pose stringent and various demands on not only real-time inference with low energy cost and high ac- curacy but also fast training. Unfortunately, as Moore’s Law approaches its limits and ST-GL model complexity drastically grows, the gap between digital hardware’s computational power and ST- GL application demands is widening. In response, this paper introduces Nature-GL, a nature-powered graph learning paradigm that exploits the principle of entropy increase to advance graph learning. In particular, Nature-GL transforms both the training and inference of real-valued ST-GL into electron-speed natural anneal- ing processes of a parameterized dynamical system that represents the target graphs. Experimental results across four real-world ap- plications with six datasets demonstrate that Nature-GL achieves orders-of-magnitude speedups in both training and inference, delivering higher accuracy compared to Graph Neural Networks.

Liu, Chuan [University of Rochester]↗
DOE OSTI2025

Scalable training of trustworthy and energy-efficient predictive graph foundation models for atomistic materials modeling: a case study with HydraGNN

We present our work on developing and training scalable, trustworthy, and energy-efficient predictive graph foundation models (GFMs) using HydraGNN, a multi-headed graph convolutional neural network architecture. HydraGNN expands the boundaries of graph neural network (GNN) computations in both training scale and data diversity. It abstracts over message passing algorithms, allowing both reproduction of and comparison across algorithmic innovations that define nearest-neighbor convolution in GNNs. This work discusses a series of optimizations that have allowed scaling up the GFMs training to tens of thousands of GPUs on datasets consisting of hundreds of millions of graphs. Our GFMs use multitask learning (MTL) to simultaneously learn graph-level and node-level properties of atomistic structures, such as energy and atomic forces. Using over 154 million atomistic structures for training, we illustrate the performance of our approach along with the lessons learned on two state-of-the-art US Department of Energy (US-DOE) supercomputers, namely the Perlmutter petascale system at the National Energy Research Scientific Computing Center and the Frontier exascale system at Oak Ridge Leadership Computing Facility. The HydraGNN architecture enables the GFM to achieve near-linear strong scaling performance using more than 2000 GPUs on Perlmutter and 16,000 GPUs on Frontier.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2026

Powers of magnetic graph matrix: Fourier spectrum, walk compression, and applications

Magnetic graphs, originally developed to model quantum systems under magnetic fields, have recently emerged as a powerful framework for analyzing complex directed networks. Existing research has primarily used the spectral properties of the magnetic graph matrix to study global and stationary network features. However, their capacity to model local, nonequilibrium behaviors, often described by matrix powers, remains largely unexplored. We present a combinatorial interpretation of the magnetic graph matrix powers through directed walk profiles—counts of graph walks indexed by the number of edge reversals. Crucially, we establish that walk profiles correspond to a Fourier transform of magnetic matrix powers. The connection allows exact reconstruction of walk profiles from magnetic matrix powers at multiple discrete potentials, and more importantly, an even smaller number of potentials often suffices for accurate approximate reconstruction in real networks. This shows the empirical compressibility of the information captured by the magnetic matrix. This fresh perspective suggests further applications; for example, we illustrate how powers of the magnetic matrix can identify frustrated directed cycles (e.g., feedforward loops) and can be effectively employed for link prediction by encoding local structural details in directed graphs.

complex networks↗