Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “graph processing”

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 73 records · Page 4
All sourcesNASA NTRSDOE OSTI
DOE OSTI2025

Intern Poster: STIG Shouldn't Drop ACID

STIG (Structured Threat Intelligence Graph) is an open-source graph database tool from INL. It’s used to create and process cyber intelligence graphs, which are shared in the cyber threat intelligence community and used to train INL machine learning products like @DisCo. For quality machine learning and critical infrastructure defense, STIG’s database must be ACID: Atomic, Consistent, Isolated, Durable. Various ACID tests were designed and applied to STIG to ensure its behavior follows these properties.

99 - GENERAL AND MISCELLANEOUS↗
NASA NTRS1991

Application of machine learning and expert systems to Statistical Process Control (SPC) chart interpretation

Statistical Process Control (SPC) charts are one of several tools used in quality control. Other tools include flow charts, histograms, cause and effect diagrams, check sheets, Pareto diagrams, graphs, and scatter diagrams. A control chart is simply a graph which indicates process variation over time. The purpose of drawing a control chart is to detect any changes in the process signalled by abnormal points or patterns on the graph. The Artificial Intelligence Support Center (AISC) of the Acquisition Logistics Division has developed a hybrid machine learning expert system prototype which automates the process of constructing and interpreting control charts.

Shewhart, Mark↗
DOE OSTI2024

Uncertainty quantification of graph convolution neural network models of evolving processes

The application of neural network models to scientific machine learning tasks has proliferated in recent years. In particular, neural networks have proved to be adept at modeling processes with spatial–temporal complexity. Nevertheless, these highly parameterized models have garnered skepticism in their ability to produce outputs with quantified error bounds over the regimes of interest. Hence there is a need to find uncertainty quantification methods that are suitable for neural networks. In this work we present comparisons of the parametric uncertainty quantification of neural networks modeling complex spatial–temporal processes with Hamiltonian Monte Carlo and Stein variational gradient descent and its projected variant. Specifically we apply these methods to graph convolutional neural network models of evolving systems modeled with recurrent neural network and neural ordinary differential equations architectures. We show that Stein variational inference is a viable alternative to Monte Carlo methods with some clear advantages for complex neural network models. For our exemplars, Stein variational interference gave similar pushed forward uncertainty profiles through time compared to Hamiltonian Monte Carlo, albeit with generally more generous variance. As a result, projected Stein variational gradient descent also produced similar uncertainty profiles to the non-projected counterpart, but large reductions in the active weight space were confounded by the stability of the neural network predictions and the convoluted likelihood landscape.

36 MATERIALS SCIENCE↗
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 OSTI2025

Scalable edge clustering of dynamic graphs via weighted line graphs

Timestamped relational datasets consisting of records (or connections) between pairs of entities are ubiquitous in network science. For applications like peer-to-peer communication, email, various social network interactions, and computer network security, it is useful to organize these records into groups based on how and when they are occurring. Weighted line graphs offer a natural way to model how records are related in such datasets but for large real-world graph topologies, building and utilizing the line graph is prohibitively expensive. Here, we present the framework to cluster the edges of a dynamic graph via the associated line graph that contains two major contributions. The first is a method to work with the line graph implicitly and the second is a distributed scale implementation of an agglomerative hierarchical graph clustering algorithm. We outline a novel hierarchical dynamic graph edge clustering approach that efficiently breaks massive relational datasets into small sets of edges containing events at various timescales. This is in stark contrast to traditional graph clustering algorithms that prioritize highly connected (clique-like) community structures. Our approach relies on constructing a sufficient subgraph of a weighted line graph and applying a hierarchical agglomerative clustering. This approach is related to scalable techniques from spatial clustering, nonlinear-dimension reduction, topological data analysis, and draws particular inspiration from HDBSCAN. As an edge clustering, this method yields an overlapping node clustering. Our algorithm is parallelizable and we demonstrate efficient clustering of a billion-scale, real-world dynamic graph into small edge sets that correlate in topology and time. The entire clustering process for a graph with tens of billions of edges takes just a few minutes of run time on 256 nodes of a distributed compute environment. We argue how the output of the edge clustering is useful for a multitude of data visualization and powerful machine learning tasks, both involving the original massive dynamic graph data and metadata associated with the nodes and edges. Finally, we describe how this approach can be extended to dynamic hypergraphs and dynamic graphs/hypergraphs with unstructured data living on vertices and edges.

Data Analysis↗
NASA NTRS1993

Process and representation in graphical displays

Our initial model of graphic comprehension has focused on statistical graphs. Like other models of human-computer interaction, models of graphical comprehension can be used by human-computer interface designers and developers to create interfaces that present information in an efficient and usable manner. Our investigation of graph comprehension addresses two primary questions: how do people represent the information contained in a data graph?; and how do they process information from the graph? The topics of focus for graphic representation concern the features into which people decompose a graph and the representations of the graph in memory. The issue of processing can be further analyzed as two questions: what overall processing strategies do people use?; and what are the specific processing skills required?

Gillan, Douglas J.↗
DOE OSTI2022

Efficient Topology Assessment for Integrated Transmission and Distribution Network with 10,000+ Inverter-based Resources

The renewable energy proliferation calls upon the grid operators and planners to systematically evaluate the potential impacts of distributed energy resources (DERs). Considering the significant differences between various inverter-based resources (IBRs), especially the different capabilities between grid-forming inverters and grid-following inverters, it is crucial to develop an efficient and effective assessment procedure besides available co-simulation framework with high computation burdens. This paper presents a streamlined graph-based topology assessment for the integrated power system transmission and distribution networks. Graph analyses were performed based on the integrated graph of modified miniWECC grid model and IEEE 8500-node test feeder model, high performance computing platform with 40 nodes and total 2400 CPUs has been utilized to process this integrated graph, which has 100,000+ nodes and 10,000+ IBRs. The node ranking results not only verified the applicability of the proposed method, but also revealed the potential of distributed grid forming (GFM) and grid following (GFL) inverters interacting with the centralized power plants.

Graph Analysis, Topology evaluation, Infrastructur↗
NASA NTRS1994

A software tool for dataflow graph scheduling

A graph-theoretic design process and software tool is presented for selecting a multiprocessing scheduling solution for a class of computational problems. The problems of interest are those that can be described using a dataflow graph and are intended to be executed repetitively on multiple processors. The dataflow paradigm is very useful in exposing the parallelism inherent in algorithms. It provides a graphical and mathematical model which describes a partial ordering of algorithm tasks based on data precedence.

Jones, Robert L., III↗
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↗
DOE OSTI2021

Improved Bounds for Burning Fence Graphs

Graph burning studies how fast a contagion, modeled as a set of fires, spreads in a graph. The burning process takes place in synchronous, discrete rounds. In each round, a fire breaks out at a vertex, and the fire spreads to all vertices that are adjacent to a burning vertex. Additionally, the burning number of a graph G is the minimum number of rounds necessary for each vertex of G to burn. We consider the burning number of the \(m \times n\) Cartesian grid graphs, written \(G_{m,n}\) . For \(m = \omega (\sqrt{n})\) , the asymptotic value of the burning number of \(G_{m,n}\) was determined, but only the growth rate of the burning number was investigated in the case \(m = O(\sqrt{n})\) , which we refer to as fence graphs. We provide new explicit bounds on the burning number of fence graphs \(G_{c\sqrt{n},n}\) , where \(c > 0\) .

79 ASTRONOMY AND ASTROPHYSICS↗
DOE OSTI2025

ScaWL: Scaling k-WL (Weisfeiler-Lehman) Algorithms in Memory and Performance on Shared and Distributed-Memory Systems

The k-dimensional Weisfeiler-Lehman (k-WL) algorithm—developed as an efficient heuristic for testing if two graphs are isomorphic—is a fundamental kernel for node embedding in the emerging field of graph neural networks. Unfortunately, the k-WL algorithm has exponential storage requirements, limiting the size of graphs that can be handled. This work presents a novel k-WL scheme with a storage requirement orders of magnitude lower while maintaining the same accuracy as the original k-WL algorithm. Due to the reduced storage requirement, our scheme allows for processing much bigger graphs than previously possible on a single compute node. For even bigger graphs, we provide the first distributed-memory implementation. Our k-WL scheme also has significantly reduced communication volume and offers high scalability. Our experimental results demonstrate that our approach is significantly faster and has superior scalability compared to five other implementations employing state-of-the-art techniques.

algorithims↗
DOE OSTI2026

Discovery of Probabilistic Dirichlet-to-Neumann Maps on Graphs

Dirichlet-to-Neumann maps enable the coupling of multiphysics simulations across computational subdomains by ensuring continuity of state variables and fluxes at artificial interfaces. We present a novel method for learning Dirichlet-to-Neumann maps on graphs using Gaussian processes, specifically for problems where the data obey a conservation law arising from an underlying partial differential equation. Our approach combines discrete exterior calculus and nonlinear optimal recovery to infer relationships between vertex and edge values. This framework yields data-driven predictions with uncertainty quantification across the entire graph, even when observations are limited to a subset of vertices and edges. By minimizing the reproducing kernel Hilbert space norm while penalizing kernel complexity through maximum likelihood estimation, our method ensures that the resulting surrogate strictly enforces conservation laws without overfitting. We demonstrate our method on two representative applications: subsurface flow in fracture networks and arterial blood flow. Finally, the results demonstrate that the method maintains high accuracy and well-calibrated uncertainty estimates even under severe data scarcity, highlighting its potential for scientific applications where limited data and reliable uncertainty quantification are critical.

Dirichlet-to-Neumann map↗
DOE OSTI2022

A Block-Based Triangle Counting Algorithm on Heterogeneous Environments

Triangle counting is a fundamental building block in graph algorithms. In this article, we propose a block-based triangle counting algorithm to reduce data movement during both sequential and parallel execution. Our block-based formulation makes the algorithm naturally suitable for heterogeneous architectures. The problem of partitioning the adjacency matrix of a graph is well-studied. Our task decomposition goes one step further: it partitions the set of triangles in the graph. By streaming these small tasks to compute resources, we can solve problems that do not fit on a device. We demonstrate the effectiveness of our approach by providing an implementation on a compute node with multiple sockets, cores and GPUs. The current state-of-the-art in triangle enumeration processes the Friendster graph in 2.1 seconds, not including data copy time between CPU and GPU. Using that metric, our approach is 20 percent faster. When copy times are included, our algorithm takes 3.2 seconds. This is 5.6 times faster than the fastest published CPU-only time.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2022

A spatial superstructure approach to the optimal design of modular processes and supply chains

Modularity is a design principle that aims to provide flexibility for spatio-temporal assembly/disassembly and reconfiguration of systems. This design principle can be applied to multiscale (hierarchical) manufacturing systems that connect units, processes, facilities, and entire supply chains. Designing modular systems is challenging because of the need to capture spatial interdependencies that arise between system components due to product exchange/transport between components and due to product transformation in such components. In this work, we propose an optimization framework to facilitate the design of modular manufacturing systems. Central to our approach is the concept of a spatial superstructure, which is a graph that captures all possible system configurations and interdependencies between components. The spatial superstructure is a generalization of the notion of a superstructure and of a p-graph used in process design, in that it encodes spatial (geographical) context of the system components. Here, we show that this generalization facilitates the simultaneous design and analysis of processes, facilities, and of supply chains. Our framework aims to select the system topology from the spatial superstructure that minimizes design cost and that maximizes design modularity. We show that this design problem can be cast as a mixed-integer, multi-objective optimization formulation. We demonstrate these capabilities using a case study arising in the design of a plastic waste upcycling supply chain.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗
NASA NTRS1988

An intelligent allocation algorithm for parallel processing

The problem of allocating nodes of a program graph to processors in a parallel processing architecture is considered. The algorithm is based on critical path analysis, some allocation heuristics, and the execution granularity of nodes in a program graph. These factors, and the structure of interprocessor communication network, influence the allocation. To achieve realistic estimations of the executive durations of allocations, the algorithm considers the fact that nodes in a program graph have to communicate through varying numbers of tokens. Coarse and fine granularities have been implemented, with interprocessor token-communication duration, varying from zero up to values comparable to the execution durations of individual nodes. The effect on allocation of communication network structures is demonstrated by performing allocations for crossbar (non-blocking) and star (blocking) networks. The algorithm assumes the availability of as many processors as it needs for the optimal allocation of any program graph. Hence, the focus of allocation has been on varying token-communication durations rather than varying the number of processors. The algorithm always utilizes as many processors as necessary for the optimal allocation of any program graph, depending upon granularity and characteristics of the interprocessor communication network.

Carroll, Chester C.↗
DOE OSTI2022

Online Power System Event Detection via Bidirectional Generative Adversarial Networks

Accurate and speedy detection of power system events is critical to enhancing the reliability and resiliency of power systems. Although supervised deep learning algorithms show great promise in identifying power system events, they require a large volume of high-quality event labels for training. This paper develops a bidirectional anomaly generative adversarial network (GAN)-based algorithm to detect power system events using streaming PMU data, which does not rely on a huge amount of event labels. By introducing conditional entropy constraint in the objective function of GAN and graph signal processing-based PMU sorting technique, our proposed algorithm significantly outperforms state-of-the-art event detection algorithms in terms of accuracy. To facilitate the adoption of the proposed algorithm, a prototype online platform is also developed using Apache Hadoop, Kafka, and Spark to enable real-time event detection. Here, the accuracy and computational efficiency of the proposed algorithm are validated using a large-scale real-world PMU dataset from the Eastern Interconnection of the United States.

24 POWER TRANSMISSION AND DISTRIBUTION↗
NASA NTRS1973

Generalize aerodynamic coefficient table storage, checkout and interpolation for aircraft simulation

The set of programs described has been used for rapidly introducing, checking out and very efficiently using aerodynamic tables in complex aircraft simulations on the IBM 360. The preprocessor program reads in tables with different names and dimensions and stores then on disc storage according to the specified dimensions. The tables are read in from IBM cards in a format which is convenient to reduce the data from the original graphs. During table processing, new auxiliary tables are generated which are required for table cataloging and for efficient interpolation. In addition, DIMENSION statements for the tables as well as READ statements are punched so that they may be used in other programs for readout of the data from disc without chance of programming errors. A quick data checking graphical output for all tables is provided in a separate program.

Neuman, F.↗