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 109 records · Page 6
All sourcesNASA NTRSDOE OSTI
DOE OSTI2024

Graph-Based Representations and Applications to Process Simulation

Rapid and robust convergence of a process flowsheet is critical to enable large-scale simulations that address core scientific questions related to process design, optimization, and sustainability. However, due to the highly coupled and nonlinear nature of chemical processes, efficiently solving a flowsheet remains a challenge. In this work, we show that graph representations of the underlying physical phenomena in unit operations may help identify potential avenues to systematically reformulate the network of equations and enable more robust topology-based convergence of flowsheets. To this end, we developed graph abstractions of the governing equations of vapor-liquid and liquid-liquid equilibrium separation equipment. These graph abstractions consist of a mesh of interconnected variable nodes and equation nodes that are systematically generated through PhenomeNode, a new open-source library in Python developed in this study. We show that partitioning the graph into separate mass, energy, and equilibrium subgraphs can help decouple nonlinearities and guide decomposition algorithms. By employing the graph abstraction on an industrial separation process for separating glacial acetic acid from water, we implemented a new block decomposition scheme in BioSTEAM and demonstrated that this can accelerate convergence over a traditional sequential modular approach.

Distillation↗
DOE OSTI2025

Capturing Historic Reliability Performance Through Graph Databases: A Model Based System Engineering Approach

With the goal of improving the performance and reliability of high dependable technological systems such as nuclear power plants, advanced monitoring and health management systems are employed to inform system engineers on observed degradation processes and anomalous behaviors of assets and components. This information is captured in the form of large amount of data which can be heterogenous in nature (e.g., numeric, textual). Such large data availability poses challenges when system engineers are required to parse and analyze them in order to track historic reliability performance of assets and components. This paper tackles directly this challenge by providing means to organize data in the form of a graph: a knowledge graph. The presented approach distinguish itself from current knowledge graph-based methods by the fact that model-based system engineering (MBSE) models are used to “put data into context”. In particular, MBSE models are used as skeleton of a knowledge graph; numeric and textual data elements, once processed, are associated to MBSE model elements. Thus, a knowledge graph captures both system architecture (though MBSE models) and health/performance data. Such feature opens the door to new data analytics methods designed to identify causal relations between observed phenomena.

97 - MATHEMATICS AND COMPUTING↗
DOE OSTI2024

DyG-DPCD: A Distributed Parallel Community Detection Algorithm for Large-Scale Dynamic Graphs

Dynamic (Temporal) graphs capture the valuable evolution of real-world systems, from the continuously evolving patterns of social interactions and genetic pathways to the dynamic fluctuations of economic forces. Detecting communities for such evolving networks poses unique challenges. Detecting and analyzing the evolution of communities within dynamic graphs unlocks valuable insights into the underlying structural and temporal patterns of real-world systems. However, the sheer volume of modern graph data and the inherent complexity of the temporal dimension pose significant challenges to scalable community detection algorithms. Addressing this gap, our work explores the limited landscape of scalable distributed-memory parallel methods specifically designed for dynamic network community detection. We propose a novel parallel algorithm, DyG-DPCD (Dynamic Graph Distributed Parallel Community Detection), to detect communities in dynamic networks using the Message Passing Interface (MPI) framework. We present a vertex-centric approach, allowing us to detect communities through local optimization. Furthermore, we enhance our baseline algorithm by incorporating three heuristics, which improve the algorithm’s performance significantly while maintaining the quality of the solutions. We demonstrate the efficiency of our algorithm by experimenting on several real-world large-scale networks with hundreds of millions of edges spanning diverse domains. Notably, DyG-DPCD achieves speedups between 25× and 30× for large networks that we experimented on using NERSC compute nodes. In conclusion, our algorithm outperforms the STINGER parallel re-agglomeration algorithm by 30×.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2022

A Julia Framework for Graph-Structured Nonlinear Optimization

Graph theory provides a convenient framework for modeling and solving structured optimization problems. Under this framework, the modeler can arrange/assemble the components of an optimization model (variables, constraints, objective functions, and data) within nodes and edges of a graph, and this representation can be used to visualize, manipulate, and solve the problem. In this work, we present a Julia framework for modeling and solving graph-structured nonlinear optimization problems. Our framework integrates the modeling package Plasmo.jl (which facilitates the construction and manipulation of graph models) and the nonlinear optimization solver MadNLP.jl (which provides capabilities for exploiting graph structures to accelerate solution). We illustrate with a simple example how model construction and manipulation can be performed in an intuitive manner using Plasmo.jl and how the model structure can be exploited by MadNLP.jl. We also demonstrate the scalability of the framework by targeting a large-scale, stochastic gas network problem that contains over 1.7 million variables.

Cole, David↗
DOE OSTI2024

A graph embedding‐based approach for automatic cyber‐physical power system risk assessment to prevent and mitigate threats at scale

Abstract Power systems are facing an increasing number of cyber incidents, potentially leading to damaging consequences to both physical and cyber aspects. However, the development of analytical methods for the study of large‐scale power infrastructures as cyber‐physical systems is still in its early stages. Drawing inspiration from machine‐learning techniques, the authors introduce a method inspired by the principles of graph embedding that is tailored for quantitative risk assessment and the exploration of possible mitigation strategies of large‐scale cyber‐physical power systems. The primary advantage of the graph embedding approach lies in its ability to generate numerous random walks on a graph, simulating potential access paths. Meanwhile, it enables capturing high‐dimensional structures in low‐dimensional spaces, facilitating advanced machine‐learning applications, and ensuring scalability and adaptability for comprehensive network analysis. By employing this graph embedding‐based approach, the authors present a structured and methodical framework for risk assessment in cyber‐physical systems. The proposed graph embedding‐based risk analysis framework aims to provide a more insightful perspective on cyber‐physical risk assessment and situation awareness for power systems. To validate and demonstrate its applicability, the method has been tested on two cyber‐physical power system models: the Western System Coordinating Council (WSCC) 9‐Bus System and the Illinois 200‐Bus System , thereby showing its advantages in enhancing the accuracy of risk analysis and comprehensiveness of situational awareness.

Sun, Shining↗
DOE OSTI2023

Gaps labeling theorem for the bubble-diamond self-similar graphs

Abstract Motivated by the appearance of fractals in several areas of physics, especially in solid state physics and the physics of aperiodic order, and in other sciences, including the quantum information theory, we present a detailed spectral analysis for a new class of fractal-type diamond graphs, referred to as bubble-diamond graphs, and provide a gap-labeling theorem in the sense of Bellissard for the corresponding probabilistic graph Laplacians using the technique of spectral decimation. Labeling the gaps in the Cantor set by the normalized eigenvalue counting function, also known as the integrated density of states, we describe the gap labels as orbits of a second dynamical system that reflects the branching parameter of the bubble construction and the decimation structure. The spectrum of the natural Laplacian on limit graphs is shown generically to be pure point supported on a Cantor set, though one particular graph has a mixture of pure point and singularly continuous components.

Physics↗
DOE OSTI2021

Fixed-angle conjectures for the quantum approximate optimization algorithm on regular MaxCut graphs

The quantum approximate optimization algorithm (QAOA) is a near-term combinatorial optimization algorithm suitable for noisy quantum devices. However, little is known about performance guarantees for p > 2. A recent work computing MaxCut performance guarantees for 3-regular graphs conjectures that any d-regular graph evaluated at particular fixed angles has an approximation ratio greater than some worst-case guarantee. In this work, we provide numerical evidence for this fixed angle conjecture for p < 12. We compute and provide these angles via numerical optimization and tensor networks. These fixed angles serve for an optimization-free version of QAOA and have universally good performance on any 3-regular graph. Heuristic evidence is presented for the fixed angle conjecture on graph ensembles, which suggests that these fixed angles are "close" to global optimum. Under the fixed angle conjecture, QAOA has a larger performance guarantee than the Goemans Williamson algorithm on 3-regular graphs for p >= 11.

Wurtz, Jonathan↗
DOE OSTI2025

Graph reinforcement learning for exploring model spaces beyond the standard model

We present a methodology for performing scans of beyond the standard model (BSM) parameter spaces with reinforcement learning. We identify a novel procedure using graph neural networks that is capable of exploring spaces of models without the user specifying a fixed particle content, allowing broad classes of BSM models to be explored—in theory, the technique is applicable to nearly any model space with a prespecified gauge group. We provide a generic procedure by which a suitable graph grammar can be developed for any BSM model that features user-specified symmetry groups and a finite number of different possible particle species, the use of which is applicable to a variety of machine learning tasks over the actions of BSM theories beyond our particular reinforcement learning use case. As a proof of concept, we construct the graph grammar for theories with vectorlike leptons that may or may not be charged under a dark U ( 1 ) group, inspired by portal matter extensions of the sub-GeV vector portal/kinetic mixing simplified dark matter models. We then use this graph grammar to create a reinforcement learning environment tasked with creating models with these vectorlike leptons that are consistent with a list of a variety of precision observables. The reinforcement learning agent succeeds in developing models that can address the observed muon anomalous magnetic moment discrepancy while remaining consistent with flavor violation and electroweak precision observables, including both constructions that have previously been studied as well as new models that have not, to our knowledge, previously been identified. By inspecting the resulting ensembles of models that the agent produces and experimenting with different configurations for our reinforcement learning environment and graph grammar, we also infer various lessons about the development of these environments that can be transferable to reinforcement learning scans of more complicated model spaces and comment on future directions for the development of this technique into a more mature tool. Published by the American Physical Society 2025

Wojcik, George N.↗
DOE OSTI2021

Visual Understanding of COVID-19 Knowledge Graph for Predictive Analysis

This study aims to effectively analyze and visualize the concept to concept network derived from the COVID-19 Open Research Dataset (CORD-19) dataset, where we have more than 48,000 concepts with more than 300,000 relationships between concepts. In analyzing networks, we focus on finding relationship patterns between the coronavirus disease 2019 (COVID-19) concepts and other concepts. Given the node and edge datasets, we construct directional graphs and calculate all pair shortest paths based on multiple edge weight schemes. However, statistical metrics are not sufficient to identify specific relationships represented in the network. Therefore, we also propose a visual analytics approach to effectively understand the knowledge graph. Our highly interactive visual analytics allows users to effectively analyze the evolving graphs and (COVID-19) concept nodes and other nodes related to the COVID-19 nodes. We envision that this study will pave the path to develop strategies to provide more accurate and scalable predictive analysis on knowledge graphs related to CORD19 and other biomedical knowledge graphs.

Lim, Seung-Hwan↗
DOE OSTI2022

H-GCN: A Graph Convolutional Network Accelerator on Versal ACAP Architecture

Recently Graph Neural Networks (GNNs) have drawn tremendous attentions due to their unique capability to extend the Machine Learning (ML) approaches to broadly defined applications with unstructured data, especially graphs. Comparing with other ML modalities, the acceleration of GNNs is as critical but even more challenging due to the irregularity and heterogeneity from graph typologies that together limit the performance. Existing efforts mainly focus on handling graphs’ irregularity, however, have not studied the heterogeneity. To this end, in this work, we propose H-GCN, a PL-AIE-based hybrid accelerator that leverages the emerging heterogeneity of Xilinx Versal ACAPs to achieve high-performance GNN inference. In particular, H-GCN partitions each graph into three subgraphs based on its inherent heterogeneity and processes them using PL and the newly emerged AIE respectively. To further improve the performance, we explore the sparsity support of AIE and develop an efficient density-aware method to map tiles of SpMM onto the systolic tensor array automatically. Compared with the current state-of-the-art GCN accelerator, HGCN achieves on average 1.5× speedups.

Zhang, Chengming↗
DOE OSTI2023

Attention-Augmented Parametric Kernel Graph Neural Network (APKGNN) for Node Classification

We present a new graph neural network, the Attention-based Parametric-Kernel augmented Graph Neural Network (APKGNN), developed for node classification tasks. Despite extensive work on modeling multi-faceted relationships between connected nodes of a graph, the effect of attention on edge features mapped to relationships has not yet been analyzed through learning representation. This study derives such an attention vector by first calculating node features corresponding to endpoints of an edge and then aggregating these with extracted local intrinsic patches of a given graph to generate augmented local patch vectors. This process uses a parametric kernel based on Gaussian mixture models (GMMs) to embed local neighborhoods of the graph in local patches. The patch vectors then convolve with the above node features to produce an updated node representation. We show that this new learning representation (APKGNN) achieves higher node classification accuracy on tasks - both standard benchmarks (Cora, PubMed, Citeseer) and new experimental short text corpora where nodes correspond to text documents and words. This implementation of the GNN convolution layer outperforms state-of-the-art (SOTA) algorithms, achieving higher training, validation, and test accuracy by a significant margin on three standard benchmark data sets under both SOTA experimental settings and those for new testbeds.

Bose, Avishek↗
DOE OSTI2025

Detecting Masquerade Attacks in Controller Area Networks Using Graph Machine Learning

Modern vehicles rely on a myriad of electronic control units (ECUs) interconnected via controller area networks (CANs) for critical operations. Despite their ubiquitous use and reliability, CANs are susceptible to sophisticated cyberattacks, particularly masquerade attacks, which inject false data that mimic legitimate messages at the expected frequency. These attacks pose severe risks such as unintended acceleration, brake deactivation, and rogue steering. Traditional intrusion detection systems (IDS) often struggle to detect these subtle intrusions due to their seamless integration into normal traffic. This paper introduces a novel framework for detecting masquerade attacks in the CAN bus using graph machine learning (ML). We hypothesize that the integration of shallow graph embeddings with time series features derived from CAN frames enhances the detection of masquerade attacks. We show that by representing CAN bus frames as message sequence graphs (MSGs) and enriching each node with contextual statistical attributes from time series, we can enhance detection capabilities across various attack patterns compared to using graph-based features only. Our method ensures a comprehensive and dynamic analysis of CAN frame interactions, improving robustness and efficiency. Extensive experiments on the ROAD dataset validate the effectiveness of our approach, demonstrating statistically significant improvements in the detection rates of masquerade attacks compared to a baseline that uses graph-based features only as confirmed by Mann-Whitney U and Kolmogorov-Smirnov tests (p < 0.05) .

Marfo, William [Univ. of Texas, El Paso, TX (Unite↗
DOE OSTI2024

Analysis and Mitigation of Cascading Failures Using a Stochastic Interaction Graph with Eigen-analysis

In studies on complex network systems using graph theory, eigen-analysis is typically performed on an undirected graph model of the network. However, when analyzing cascading failures in a power system, the interactions among failures suggest the need for a directed graph beyond the topology of the power system to model directions of failure propagation. To accurately quantify failure interactions for effective mitigation strategies, this paper proposes a stochastic interaction graph model and associated eigen-analysis. Different types of modes on failure propagations are defined and characterized by the eigenvalues of a stochastic interaction matrix, whose absolute values are unity, zero, or in between. Finding and interpreting these modes helps identify the probable patterns of failure propagation, either local or widespread, and the participating components based on eigenvectors. Then, by lowering the failure probabilities of critical components highly participating in a mode of widespread failures, cascading can be mitigated. Here, the validity of the proposed stochastic interaction graph model, eigen-analysis and the resulting mitigation strategies is demonstrated using simulated cascading failure data on an NPCC 140-bus system.

24 POWER TRANSMISSION AND DISTRIBUTION↗
DOE OSTI2022

Direction-optimizing Label Propagation Framework for Structure Detection in Graphs: Design, Implementation, and Experimental Analysis

Label Propagation is not only a well-known machine learning algorithm for classification but also an effective method for discovering communities and connected components in networks. We propose a new Direction-optimizing Label Propagation Algorithm (DOLPA) framework that enhances the performance of the standard Label Propagation Algorithm (LPA), increases its scalability, and extends its versatility and application scope. As a central feature, the DOLPA framework relies on the use of frontiers and alternates between label push and label pull operations to attain high performance. It is formulated in such a way that the same basic algorithm can be used for finding communities or connected components in graphs by only changing the objective function used. Additionally, DOLPA has parameters for tuning the processing order of vertices in a graph to reduce the number of edges visited and improve the quality of solution obtained. We present the design and implementation of the enhanced algorithm as well as our shared-memory parallelization of it using OpenMP. We also present an extensive experimental evaluation of our implementations using the LFR benchmark and real-world networks drawn from various domains. Compared with an implementation of LPA for community detection available in a widely used network analysis software, we achieve at most five times the F-Score while maintaining similar runtime for graphs with overlapping communities. We also compare DOLPA against an implementation of the Louvain method for community detection using the same LFR-graphs and show that DOLPA achieves about three times the F-Score at just 10% of the runtime. For connected component decomposition, our algorithm achieves orders of magnitude speedups over the basic LP-based algorithm on large-diameter graphs, up to 13.2× speedup over the Shiloach-Vishkin algorithm, and up to 1.6× speedup over Afforest on an Intel Xeon processor using 40 threads.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2022

Graph-Env

The Graph-Env library provides a framework for adapting graph search problems into OpenAI Gym environments for reinforcement learning. In other words, Graph-Env enables reinforcement learning algorithms to be applied to graph search problems. Graph search problems include molecule and crystal structure design problems; route planning problems, including traveling salesperson problem; puzzles and games, such as chess and go; shortest path problems; minimum spanning tree; vehicle path generation; and others.

Tripp, Charles↗
DOE OSTI2024

A Data Processing Pipeline To Extract A Knowledge Graph From Sec Documents For Socio-technical Analysis Of Critical Infrastructure Influence

The code is written in Python and consists of the following pipeline that is implemented in Apache Airflow. This pipeline intends to understand the companies that are directly or indirectly involved with a type of critical infrastructure system at some point in that system's lifecycle. The pipeline takes a configuration file that specifies a list of initial companies to consider, a geographic region of interest (disk) expressed as a latitude/longitude point and distance, and a set of SEC form types from which to extract entities and relations. There are three main components to this pipeline as currently implemented: Social Network Extraction, Critical Infrastructure Network Extraction, and Inference and Fusion. First, Social Network Extraction, implemented as the `organizations_sec` component of the workflow graph queries the SEC EDGAR webservice using the list of initial companies from the configuration file. Given this, it extracts metadata that documents the number of each type of form for the given set of companies and their location. This forms metadata represents a catalog of data sources for the extracted social network knowledge graph. The pipeline then downloads these forms from the website and saves them in a build directory for further processing. These documents are then parsed for entities and relations. Second, the Critical Network Extraction component extracts entities and relations for a critical infrastructure sector. Currently, we focus on Electric Vehicle charging stations and this information is available via the Department of Energy (DOE) database on fueling stations maintained by NREL. Third, the Inference and Fusion component relates the social network graph to the critical infrastructure graph in order to understand the impact of a company within a geographic region. Relations include ownership of the EV Charging Station asset as well as maintenance/ownership of the EV payment networks. The fused network can be represented in many ways and currently we emit a knowledge graph.

Weaver, GabrielA.↗
DOE OSTI2022

Synthetic Data and Graph Generation for Modeling Adversarial Activity (Final Project Report)

The Data and Graph Generation for Modeling Adversary Activity (MAA) project developed a methodology along with scalable graph modeling and generation tools to produce realistic large-scale background activity graphs with embedded adversarial activity pathways. The technical report presents PNNL methodology, released datasets, lessons learned, and recommendations to develop graph analytic algorithms for structure-only and attributed knowledge graphs.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2026

Promise of Graph Sparsification and Decomposition for Noise Reduction in QAOA: Analysis for Trapped-Ion Compilations

We develop new approximate compilation schemes that significantly reduce the expense of compiling the Quantum Approximate Optimization Algorithm (QAOA) for solving the Max-Cut problem. Our main focus is on compilation with trapped-ion simulators using Pauli-X operations and all-to-all Ising Hamiltonian HIsing evolution generated by Molmer-Sorensen or optical dipole force interactions, though some of our results also apply to standard gate-based compilations. Our results are based on principles of graph sparsification and decomposition; the former reduces the number of edges in a graph while maintaining its cut structure, while the latter breaks a weighted graph into a small number of unweighted graphs. Though these techniques have been used as heuristics in various hybrid quantum algorithms, there have been no guarantees on their performance, to the best of our knowledge. This work provides the first provable guarantees using sparsification and decomposition to improve quantum noise resilience and reduce quantum circuit complexity. For quantum hardware that uses edge-by-edge QAOA compilations, sparsification leads to a direct reduction in circuit complexity. For trapped-ion quantum simulators implementing all-to-all HIsing pulses, we show that for a (1−ϵ) factor loss in the Max-Cut approximation (ϵ>0), our compilations improve the (worst-case) number of HIsing pulses from O(n2) to O(nlog(n/ϵ)) and the (worst-case) number of Pauli-X bit flips from O(n2) to O(nlog(n/ϵ)ϵ2) for n-node graphs. This is an asymptotic improvement for any constant ϵ>0. We demonstrate that significant improvements to the approximation ratio are obtained using decomposition in simulated trapped-ion experiments with dephasing noise. We further present a generic argument showing that sparsification results in an exponentially improved circuit fidelity lower bound in digital computing schemes based on one- and two-qubit gates, which are relevant to a wide variety of hardwares such as superconducting qubits and certain neutral atom or trapped ion setups, and more sophisticated noise models. We anticipate these approximate compilation techniques will be useful tools in a variety of future quantum computing experiments.

Moondra, Jai [Georgia Institute of Technology]↗