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 469 records · Page 26
All sourcesNASA NTRSDOE OSTI
DOE OSTI2012

A weak zero-one law for sequences of random distance graphs

We study zero-one laws for properties of random distance graphs. Properties written in a first-order language are considered. For p(N) such that pN{sup {alpha}}{yields}{infinity} as N{yields}{infinity}, and (1-p)N{sup {alpha}} {yields} {infinity} as N {yields} {infinity} for any {alpha}>0, we succeed in refuting the law. In this connection, we consider a weak zero-one j-law. For this law, we obtain results for random distance graphs which are similar to the assertions concerning the classical zero-one law for random graphs. Bibliography: 18 titles.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2013

Subdominant pseudoultrametric on graphs

Let (G,w) be a weighted graph. We find necessary and sufficient conditions under which the weight w:E(G)→R{sup +} can be extended to a pseudoultrametric on V(G), and establish a criterion for the uniqueness of such an extension. We demonstrate that (G,w) is a complete k-partite graph, for k≥2, if and only if for any weight that can be extended to a pseudoultrametric, among all such extensions one can find the least pseudoultrametric consistent with w. We give a structural characterization of graphs for which the subdominant pseudoultrametric is an ultrametric for any strictly positive weight that can be extended to a pseudoultrametric. Bibliography: 14 titles.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2016

A mass graph-based approach for the identification of modified proteoforms using top-down tandem mass spectra

Motivation: Although proteomics has rapidly developed in the past decade, researchers are still in the early stage of exploring the world of complex proteoforms, which are protein products with various primary structure alterations resulting from gene mutations, alternative splicing, post-translational modifications, and other biological processes. Proteoform identification is essential to mapping proteoforms to their biological functions as well as discovering novel proteoforms and new protein functions. Top-down mass spectrometry is the method of choice for identifying complex proteoforms because it provides a “bird’s eye view” of intact proteoforms. The combinatorial explosion of various alterations on a protein may result in billions of possible proteoforms, making proteoform identification a challenging computational problem. Results: We propose a new data structure, called the mass graph, for efficient representation of proteoforms and design mass graph alignment algorithms. We developed TopMG, a mass graph-based software tool for proteoform identification by top-down mass spectrometry. Experiments on top-down mass spectrometry data sets showed that TopMG outperformed existing methods in identifying complex proteoforms.

Dynamic Programming↗
DOE OSTI2023

An finite element analysis surrogate model with boundary oriented graph embedding approach for rapid design

Abstract In this work, we present a boundary oriented graph embedding (BOGE) approach for the graph neural network to assist in rapid design and digital prototyping. The cantilever beam problem has been solved as an example to validate its potential of providing physical field results and optimized designs using only 10 ms. Providing shortcuts for both boundary elements and local neighbor elements, the BOGE approach can embed unstructured mesh elements into the graph and performs an efficient regression on large-scale triangular-mesh-based finite element analysis (FEA) results, which cannot be realized by other machine-learning-based surrogate methods. It has the potential to serve as a surrogate model for other boundary value problems. Focusing on the cantilever beam problem, the BOGE approach with 3-layer DeepGCN model achieves the regression with mean square error (MSE) of 0.011 706 (2.41% mean absolute percentage error) for stress field prediction and 0.002 735 MSE (with 1.58% elements having error larger than 0.01) for topological optimization. The overall concept of the BOGE approach paves the way for a general and efficient deep-learning-based FEA simulator that will benefit both industry and Computer Aided Design (CAD) design-related areas.

42 ENGINEERING↗
DOE OSTI2011

Multiparticle entanglement in graph-diagonal states: Necessary and sufficient conditions for four qubits

The characterization of genuine multiparticle entanglement is important for entanglement theory as well as experimental studies related to quantum-information theory. Here, we completely characterize genuine multiparticle entanglement for four-qubit states diagonal in the cluster-state basis. In addition, we give a complete characterization of multiparticle entanglement for all five-qubit graph states mixed with white noise, for states diagonal in the basis corresponding to the five-qubit Y-shaped graph, and for a family of graph states with an arbitrary number of qubits.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2025

Quantum graph models for transport in filamentary switching

The formation of metallic nanofilaments bridging two electrodes across an insulator is a mechanism for resistive switching. Examples of such phenomena include atomic synapses, which constitute a distinct class of memristive devices the behavior of which is closely tied to the properties of the filament. Until recently, experimental investigation of the low-temperature regime and quantum transport effects has been limited. However, with growing interest in understanding the true impacts of the filament on device conductance, comprehending quantum effects has become crucial for quantum neuromorphic hardware. Here, we discuss quantum transport resulting from filamentary switching in a narrow region where the continuous approximation of the contact is not valid, and only a few atoms are involved. In this scenario, the filament can be represented by a graph depicting the adjacency of atoms and the overlap between atomic orbitals. Using the theory of quantum graphs with locally diffusive node scattering, we calculate the scattering amplitude of charge carriers on this graph and explore the interplay between filamentary formation and quantum transport effects.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2017

Predictions of first passage times in sparse discrete fracture networks using graph-based reductions

Here, we present a graph-based methodology to reduce the computational cost of obtaining first passage times through sparse fracture networks. We also derive graph representations of generic three-dimensional discrete fracture networks (DFNs) using the DFN topology and flow boundary conditions. Subgraphs corresponding to the union of the k shortest paths between the inflow and outflow boundaries are identified and transport on their equivalent subnetworks is compared to transport through the full network. The number of paths included in the subgraphs is based on the scaling behavior of the number of edges in the graph with the number of shortest paths. First passage times through the subnetworks are in good agreement with those obtained in the full network, both for individual realizations and in distribution. We obtain accurate estimates of first passage times with an order of magnitude reduction of CPU time and mesh size using the proposed method.

54 ENVIRONMENTAL SCIENCES↗
DOE OSTI2019

Deformation pathway and defect generation in crystals: a combined group theory and graph theory description

The generation and motion of crystalline defects during plastic deformation are critical processes that determine the mechanical properties of a crystal. The types of defect generated are not only related to the symmetry of a crystal but also associated with the symmetry-breaking process during deformation. Proposed here is a new mathematical framework to capture the intrinsic coupling between crystal symmetry and deformation-induced symmetry breaking. Using a combination of group theory and graph theory, a general approach is demonstrated for the systematic determination of the types of crystalline defect induced by plastic deformation, through the construction of a crystal deformation group and a deformation pathway graph. The types of defect generated in the deformation of a face-centered cubic crystal are analyzed through the deformation pathway graph and compared with experimental observations.

36 MATERIALS SCIENCE↗
DOE OSTI2025

Graph-Based Prediction of Spatio-Temporal Vaccine Hesitancy From Insurance Claims Data

Growing vaccine hesitancy is contributing to the decline in immunization rates for highly contagious, vaccine-preventable childhood diseases. Therefore, there has been a significant interest in understanding how hesitancy is spreading at higher spatio-temporal resolutions, enabling more targeted interventions. Motivated by this, we study the problem of prediction of vaccine hesitancy at the ZIP Code level, referred to as the VaxHesitancy problem. A significant challenge for this problem is the lack of high-resolution data that indicates hesitancy. Here, we develop a hybrid VaxHesSTL framework that combines a Graph Neural Network (GNN) and a Recurrent Neural Network (RNN) to address the VaxHesitancy problem. The GNN uses a ZIP Code-level network to capture spatial signals from neighboring areas, while the RNN models the temporal dynamics present in the data. We train and evaluate VaxHesSTL using a large dataset, namely the All-Payer Claims Databases (APCD), for Virginia, consisting of insurance claims from over five million individuals for six years. We find that an aggregated contact network or graph, developed from a detailed activity-based population network, plays an important role in the performance of VaxHesSTL, compared to graph models based solely on spatial proximity. Experiments demonstrate that VaxHesSTL outperforms a range of state-of-the-art baselines, which rely solely on historical time series data without accounting for spatial relationships. Since hesitancy data at higher spatial resolution is often unavailable or hard to get, we incorporate an active learning approach with our VaxHesSTL framework to optimize the training set without compromising the prediction performance. We find that hesitancy data for only 18% of ZIP Codes selected by active learning allows us to forecast hesitancy for all the ZIP Codes in the Virginia.

60 APPLIED LIFE SCIENCES↗
DOE OSTI2024

Graph Analytics on Jellyfish topology

Because large unstructured datasets is important for many science domains, distributed graph analytics is critical to many scientists. Unfortunately, obtaining scaling and performance for irregular communication is challenging because contemporary network interconnects are primarily designed to maximize bandwidths of fixed-neighborhoods large-message exchanges (e.g., stencils). Although there is no consensus on the “best” network topologies for irregular communication, unstructured graph-based interconnects can be more suitable. We analyze three popular graph workloads – clustering, pattern enumeration, and traversal — on comparable networks (in terms of resources and costs) constructed from Jellyfish Random Regular, Dragonfly and Fat tree topologies, varying the routing algorithms. Using packet-level simulations, we demonstrate up to 60% improvement in communication time with Jellyfish due to diversity of the short paths between arbitrary endpoints, which can reduce overall network stalls and congestion.

Graph Analytics, network topology, interconnect, H↗
DOE OSTI2023

1-D Convolutional Graph Convolutional Networks for Fault Detection in Distributed Energy Systems

This paper presents a 1-D convolutional and graph convolutional networks for fault detection in microgrids. The combination of 1-D convolutional neural networks (1D-CNN) and graph convolutional networks (GCN) helps extract both spatial-temporal correlations from the voltage measurements in microgrids. The fault detection scheme includes fault event detection, fault type and phase classification, and fault location. There are five neural network model training to handle these tasks. Transfer learning and fine-tuning are applied to reduce training efforts. The combined 1-D convolutional and graph convolutional networks (1D-CGCN) is compared with the traditional ANN structure on the Potsdam 13-bus microgrid dataset. The accuracy of 99.5%, 98.4%, 99.2%, and 95.5% are achieved in fault event detection, fault type classification, fault phase identification, and fault location respectively. The detailed confusion matrices of fault type and fault phase classification are provided for validation.

deep neural network↗
DOE OSTI2023

A Transductive Graph Neural Network learning for Grid Resilience Analysis

Power grids are critical infrastructures that require robust resilience analysis to ensure reliable and uninterrupted electricity supply. Traditional simulation-based methods for grid resilience analysis suffer from computational complexity and limited ability to capture the full spectrum of potential disruptions. This paper presents a novel approach to enhance grid resilience by leveraging transductive graph neural network (GNN) learning to identify critical nodes and links. By leveraging the graph structure and system features, GNNs effectively learn resilience metrics and accurately identify critical nodes based on actual grid operational behavior. The efficacy of the proposed approach is demonstrated through case studies on node criticality scoring and critical node/line identification in cascading outage scenarios. The results highlight the advantages of learning-based methods over traditional simulation-based approaches and their potential to revolutionize grid resilience analysis. The contributions of this paper include a graph-based scalable approach for fast cascading analysis, an inductive formulation for training GNN models, and a transfer learning-based approach to scale the model to largescale power systems.

grid resilience, graph neural networks, transducti↗
DOE OSTI2016

Computing Maximum Cardinality Matchings in Parallel on Bipartite Graphs via Tree-Grafting

It is difficult to obtain high performance when computing matchings on parallel processors because matching algorithms explicitly or implicitly search for paths in the graph, and when these paths become long, there is little concurrency. In spite of this limitation, we present a new algorithm and its shared-memory parallelization that achieves good performance and scalability in computing maximum cardinality matchings in bipartite graphs. This algorithm searches for augmenting paths via specialized breadth-first searches (BFS) from multiple source vertices, hence creating more parallelism than single source algorithms. Algorithms that employ multiple-source searches cannot discard a search tree once no augmenting path is discovered from the tree, unlike algorithms that rely on single-source searches. We describe a novel tree-grafting method that eliminates most of the redundant edge traversals resulting from this property of multiple-source searches. We also employ the recent direction-optimizing BFS algorithm as a subroutine to discover augmenting paths faster. Our algorithm compares favorably with the current best algorithms in terms of the number of edges traversed, the average augmenting path length, and the number of iterations. Here, we provide a proof of correctness for our algorithm. Our NUMA-aware implementation is scalable to 80 threads of an Intel multiprocessor and to 240 threads on an Intel Knights Corner coprocessor. On average, our parallel algorithm runs an order of magnitude faster than the fastest algorithms available. The performance improvement is more significant on graphs with small matching number.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2017

Algorithms for Balanced Graph Colorings with Applications in Parallel Computing

Graph coloring is used to identify subsets of independent tasks in parallel scientific computing applications. Traditional coloring heuristics aim to reduce the number of colors used as that number also corresponds to the number of parallel steps in the application. However, if the color classes produced have a skew in their sizes, utilization of hardware resources becomes inefficient, especially for the smaller color classes. Equitable coloring is a theoretical formulation of coloring that guarantees a perfect balance among color classes, and its practical relaxation is referred to as balanced coloring. In this paper, we revisit the problem of balanced coloring in the context of parallel computing. The goal is to achieve a balanced coloring of an input graph without increasing the number of colors that an algorithm oblivious to balance would have used. We propose and study multiple heuristics that aim to achieve such a balanced coloring for two variants of coloring problem, distance-1 coloring and partial distance-2 coloring (defined on a bipartite graph). We present parallelization approaches for multi-core and manycore architectures, and cross-evaluate their effectiveness with respect to the quality of balance achieved and performance. Furthermore, we study the impact of the proposed balanced coloring heuristics on a concrete application - viz. parallel community detection, which is an example of an irregular application. In addition, we propose several extensions to our balancing schemes and evaluate their balancing efficacy and performance characteristics. The thorough treatment of balanced coloring presented in this paper from algorithms to application is expected to serve as a valuable resource to parallel application developers who seek to improve parallel performance of their applications using coloring.

graph coloring, multithreaded algorithms↗
DOE OSTI2018

Managing Rich Metadata in High-Performance Computing Systems Using a Graph Model

High-performance computing (HPC) systems generate huge amounts of metadata about different entities such as jobs, users, and files. Existing systems can efficiently record and manage part of these metadata, mainly the POSIX metadata of data files (e.g., file size, name, and permissions mode). But another important set of metadata, referred to as "rich" metadata in this study, which record not only wider range of entities (e.g., running processes and jobs) but also more complex relationships between them, are mostly missing in current HPC systems. Yet such rich metadata are critical for supporting many advanced data management functions such as identifying data sources and parameters behind a given result; auditing data usage; or understanding details about how inputs are transformed into outputs. To uniformly and efficiently manage the rich metadata generated in HPC systems, We propose to utilize a graph model in this study. We identify the key challenges of implementing such a graph-based HPC rich metadata management system and present GraphMeta, a graph-based rich metadata management system designed and optimized for HPC platforms, to tackle these challenges. In conclusion, extensive evaluations on both synthetic and real HPC metadata workloads show its advantages in both performance and scalability compared with existing solutions.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2022

Exponential Decay of Sensitivity in Graph-Structured Nonlinear Programs

We study solution sensitivity for nonlinear programs (NLPs) whose structures are induced by graphs. These NLPs arise in many applications such as dynamic optimization, stochastic optimization, optimization with partial differential equations, and network optimization. We illustrate that for a given pair of nodes, the sensitivity of the primal-dual solution at one node against a data perturbation at the other node decays exponentially with respect to the distance between these two nodes on the graph. In other words, the solution sensitivity decays as one moves away from the perturbation point. This result, which we call exponential decay of sensitivity, holds under the strong second-order sufficiency condition and the linear independence constraint qualification. We also present conditions under which the decay rate remains uniformly bounded; this allows us to characterize the sensitivity behavior of NLPs defined over subgraphs of infinite graphs. The theoretical developments are illustrated with numerical examples.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2026

T-FSM: A Scalable Distributed Task-Based System for Frequent Subgraph Pattern Mining from a Big Graph

Finding frequent subgraph patterns in a big graph is an important problem with many applications such as classifying chemical compounds and building indexes to speed up graph queries. Since this problem is NP-hard, some recent parallel and distributed systems have been developed to accelerate the mining. However, they often have a huge memory cost, very long running time, suboptimal load balancing, poor scale-out capability, and possibly inaccurate results. In this article, we propose an efficient system called T-FSM for parallel mining of frequent subgraph patterns in a big graph. T-FSM supports a new anti-monotonic frequentness measure called Fraction-Score, which is more accurate than the widely used MNI measure. The execution engine of T-FSM supports both intra-machine parallelism and inter-machine parallelism. For intra-machine parallelism, T-FSM adopts a novel task-based execution model to ensure high multithreading concurrency, bounded memory consumption, and effective load balancing. For inter-machine parallelism, T-FSM ensures good scale-out performance with a lightweight pattern rebalancing approach that reduces workload skewness of pattern evaluations among machines. To avoid recomputing the contexts for migrated patterns, we design a novel context cache table to support concurrent and asynchronous requesting and caching of remote context data, which can timely evict and garbage collect used pattern contexts that are no longer needed to keep memory consumption bounded. Extensive experiments show that T-FSM is orders of magnitude faster than existing state-of-the-art parallel systems (more than 10×, 51×, 131×, 55× speedup over ScaleMine, DistGraph, Pangolin and Peregrine, respectively) and distributed systems (more than 42× and 88× over ScaleMine and DistGraph, respectively) for frequent subgraph pattern mining, and it scales out satisfactorily to 512 CPU cores on the Polaris supercomputer at Argonne National Laboratory.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2021

EXAGRAPH: Graph and combinatorial methods for enabling exascale applications

Combinatorial algorithms in general and graph algorithms in particular play a critical enabling role in numerous scientific applications. However, the irregular memory access nature of these algorithms makes them one of the hardest algorithmic kernels to implement on parallel systems. With tens of billions of hardware threads and deep memory hierarchies, the exascale computing systems in particular pose extreme challenges in scaling graph algorithms. The codesign center on combinatorial algorithms, ExaGraph, was established to design and develop methods and techniques for efficient implementation of key combinatorial (graph) algorithms chosen from a diverse set of exascale applications. Algebraic and combinatorial methods have a complementary role in the advancement of computational science and engineering, including playing an enabling role on each other. In this paper, we survey the algorithmic and software development activities performed under the auspices of ExaGraph from both a combinatorial and an algebraic perspective. In particular, we detail our recent efforts in porting the algorithms to manycore accelerator (GPU) architectures. We also provide a brief survey of the applications that have benefited from the scalable implementations of different combinatorial algorithms to enable scientific discovery at scale. We believe that several applications will benefit from the algorithmic and software tools developed by the ExaGraph team.

97 MATHEMATICS AND COMPUTING↗