Search NASA⌕ Search

SEARCH · Search NASA

Results for “large 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 55 records · Page 3
All sourcesNASA NTRSDOE OSTI
NASA NTRS1981

Graph theory approach to the eigenvalue problem of large space structures

Graph theory is used to obtain numerical solutions to eigenvalue problems of large space structures (LSS) characterized by a state vector of large dimensions. The LSS are considered as large, flexible systems requiring both orientation and surface shape control. Graphic interpretation of the determinant of a matrix is employed to reduce a higher dimensional matrix into combinations of smaller dimensional sub-matrices. The reduction is implemented by means of a Boolean equivalent of the original matrices formulated to obtain smaller dimensional equivalents of the original numerical matrix. Computation time becomes less and more accurate solutions are possible. An example is provided in the form of a free-free square plate. Linearized system equations and numerical values of a stiffness matrix are presented, featuring a state vector with 16 components.

Reddy, A. S. S. R.↗
DOE OSTI2020

C-SAW: a framework for graph sampling and random walk on GPUs

Many applications require to learn, mine, analyze and visualize large-scale graphs. These graphs are often too large to be addressed efficiently using conventional graph processing technologies. Fortunately, recent research efforts find out graph sampling and random walk, which significantly reduce the size of original graphs, can benefit the tasks of learning, mining, analyzing and visualizing large graphs by capturing the desirable graph properties. This paper introduces C-SAW, the first framework that accelerates Sampling and Random Walk framework on GPUs. Particularly, C-SAW makes three contributions: First, our framework provides a generic API which allows users to implement a wide range of sampling and random walk algorithms with ease. Second, offloading this framework on GPU, we introduce warp-centric parallel selection, and two novel optimizations for collision migration. Third, towards supporting graphs that exceed the GPU memory capacity, we introduce efficient data transfer optimizations for out-of-memory and multi-GPU sampling, such as workload-aware scheduling and batched multi-instance sampling. Taken together, our framework constantly outperforms the state of the art projects in addition to the capability of supporting a wide range of sampling and random walk algorithms.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2022

Scalable training of graph convolutional neural networks for fast and accurate predictions of HOMO-LUMO gap in molecules

Abstract Graph Convolutional Neural Network (GCNN) is a popular class of deep learning (DL) models in material science to predict material properties from the graph representation of molecular structures. Training an accurate and comprehensive GCNN surrogate for molecular design requires large-scale graph datasets and is usually a time-consuming process. Recent advances in GPUs and distributed computing open a path to reduce the computational cost for GCNN training effectively. However, efficient utilization of high performance computing (HPC) resources for training requires simultaneously optimizing large-scale data management and scalable stochastic batched optimization techniques. In this work, we focus on building GCNN models on HPC systems to predict material properties of millions of molecules. We use HydraGNN, our in-house library for large-scale GCNN training, leveraging distributed data parallelism in PyTorch. We use ADIOS, a high-performance data management framework for efficient storage and reading of large molecular graph data. We perform parallel training on two open-source large-scale graph datasets to build a GCNN predictor for an important quantum property known as the HOMO-LUMO gap. We measure the scalability, accuracy, and convergence of our approach on two DOE supercomputers: the Summit supercomputer at the Oak Ridge Leadership Computing Facility (OLCF) and the Perlmutter system at the National Energy Research Scientific Computing Center (NERSC). We present our experimental results with HydraGNN showing (i) reduction of data loading time up to 4.2 times compared with a conventional method and (ii) linear scaling performance for training up to 1024 GPUs on both Summit and Perlmutter.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗
DOE OSTI2023

Scalable Graph Analytics and HPC Operational Enhancement: Parallel Computing and ML/DL Innovations

Parallel computing plays a pivotal role in the efficient processing of large-scale graphs. Complex network analysis stands as a capti- vating research frontier, holding promise across diverse scientific domains such as sociology, biology, online media, and recommenda- tion systems. In this era, Machine Learning (ML) and Deep Learning (DL) have emerged as indispensable tools, underpinning remarkable technological achievements. Within this dynamic landscape, my research revolves around advancing parallel algorithms tailored for large-scale graph operations. To achieve this, I harness the power of cutting-edge technologies including OpenMP, MPI, HIP, and CUDA, on the High-Performance Computing (HPC) platforms to unlock optimal performance. I also apply ML/DL techniques to HPC operational data, to streamline the monitoring and maintenance of supercomputers, alleviating the complexities associated with their upkeep and enhancing user support. My research echoes the syn- ergy between parallel computing, large-scale graph analysis, and ML/DL, improving computational efficiency and user experience.

Sattar, Naw Safrin↗
DOE OSTI2021

Explore Spatio‐Temporal Learning of Large Sample Hydrology Using Graph Neural Networks

Abstract Streamflow forecasting over gauged and ungauged basins play a vital role in water resources planning, especially under the changing climate. Increased availability of large sample hydrology data sets, together with recent advances in deep learning techniques, has presented new opportunities to explore temporal and spatial patterns in hydrological signatures for improving streamflow forecasting. The purpose of this study is to adapt and benchmark several state‐of‐the‐art graph neural network (GNN) architectures, including ChebNet, Graph Convolutional Network (GCN), and GraphWaveNet, for end‐to‐end graph learning. We explicitly represent river basins as nodes in a graph, learn the spatiotemporal nodal dependencies, and then use the learned relations to predict streamflow simultaneously across all nodes in the graph. The efficacy of the developed GNN models is investigated using the Catchment Attributes and MEteorology for Large‐sample Studies (CAMELS) data set under two settings, fixed graph topology (transductive learning), and variable graph topology (inductive learning), with the latter applicable to prediction in ungauged basins (PUB). Results indicate that GNNs are generally robust and computationally efficient, achieving similar or better performance than a baseline model trained using the long short‐term memory (LSTM) network. Further analyses are conducted to interpret the graph learning process at the edge and node levels and to investigate the effect of different model configurations. We conclude that graph learning constitutes a viable machine learning‐based method for aggregating spatiotemporal information from a multitude of sources for streamflow forecasting

Sun, Alexander Y.↗
DOE OSTI2022

A differentiable approach to the maximum independent set problem using dataless neural networks

The success of machine learning solutions for reasoning about discrete structures has brought attention to its adoption within combinatorial optimization algorithms. Such approaches generally rely on supervised learning by leveraging datasets of the combinatorial structures of interest drawn from some distribution of problem instances. Reinforcement learning has also been employed to find such structures. Here, in this paper, we propose a different approach in that no data is required for training the neural networks that produce the solution. In this sense, what we present is not a machine learning solution, but rather one that is dependent on neural networks and where backpropagation is applied to a loss function defined by the structure of the neural network architecture as opposed to a training dataset. In particular, we reduce the popular combinatorial optimization problem of finding a maximum independent set to a neural network and employ a dataless training scheme to refine the parameters of the network such that those parameters yield the structure of interest. Additionally, we propose a universal graph reduction procedure to handle large-scale graphs. The reduction exploits community detection for graph partitioning and is applicable to any graph type and/or density. Experimental results on both real and synthetic graphs demonstrate that our proposed method performs on par or outperforms state-of-the-art learning-based methods in terms of the size of the found set without requiring any training data.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2020

Using Graph Edit Distance for Noisy Subgraph Matching of Semantic Property Graphs

The subgraph matching problem is a fundamental problem in graph theory that is known to be NP-complete. In this study, performers were asked to develop algorithms to search for semantic property graphs that were subgraphs of a large knowledge graph. The templates provided contained structural information about the subgraphs and some attributes for each node and edge. There also exists a similarity measure between a set of attribute values that occurs on every node and edge. Algorithms performed well in the case where an exact match existed, but performers were also provided templates that had noise added such that there existed no match in the knowledge graph. Performers were asked to find the closest matches to those noisy subgraphs. To evaluate performance on this task, we developed a version of the graph edit distance algorithm to measure the cost of editing the template graph so that it is isomorphic in structure and attributes to the performer submission.

Ebsch, Christopher L.↗
DOE OSTI2021

Preventing Failures By Dataset Shift Detection in Safety-Critical Graph Applications

Dataset shift refers to the problem where the input data distribution may change over time (e.g., between training and test stages). Since this can be a critical bottleneck in several safety-critical applications such as healthcare, drug-discovery, etc., dataset shift detection has become an important research issue in machine learning. Though several existing efforts have focused on image/video data, applications with graph-structured data have not received sufficient attention. Therefore, in this paper, we investigate the problem of detecting shifts in graph structured data through the lens of statistical hypothesis testing. Specifically, we propose a practical two-sample test based approach for shift detection in large-scale graph structured data. Our approach is very flexible in that it is suitable for both undirected and directed graphs, and eliminates the need for equal sample sizes. Using empirical studies, we demonstrate the effectiveness of the proposed test in detecting dataset shifts. We also corroborate these findings using real-world datasets, characterized by directed graphs and a large number of nodes.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2022

Graph-component approach to defect identification in large atomistic simulations

In this work, the graph-theoretical concept of connected components is employed to extract the evolution of defect configurations in a polycrystalline aluminum structure containing ~8.3 million atoms. This graph-component approach is applied to reveal details of defect formation, transport, and transformation in the polycrystalline Al under large shear deformation. Building upon standard nearest neighbor analysis, graph theory and associated tools are used to reduce the multi-million-atom system into discrete component subgraphs that represent distinct structural defects. This method allows the automated identification, characterization, and tracking of defective regions within large volumes of data representing atomic-scale processes. Such analysis elucidates relationships between external stimuli, such as strain, and defect distributions, which have a large influence on material properties. The Graph Analytics for Large Atomistic Simulations (GALAS) codebase that implements this analysis, together with user guidance, is openly available at https://github.com/pnnl/galas.

36 MATERIALS SCIENCE↗
DOE OSTI2024

Graph Neural Network-based Tracking as a Service

Recent studies have shown promising results for track finding in dense environments using Graph Neural Network (GNN)-based algorithms. However, GNN-based track finding is computationally slow on CPUs, necessitating the use of coprocessors to accelerate the inference time. Additionally, the large input graph size demands a large device memory for efficient computation, a requirement not met by all computing facilities used for particle physics experiments, particularly those lacking advanced GPUs. Furthermore, deploying the GNN-based track-finding algorithm in a production environment requires the installation of all dependent software packages, exclusively utilized by this algorithm. These computing challenges must be addressed for the successful implementation of GNN-based track-finding algorithm into production settings. In response, we introduce a ``GNN-based tracking as a service'' approach, incorporating a custom backend within the NVIDIA Triton inference server to facilitate GNN-based tracking. This paper presents the performance of this approach using the Perlmutter supercomputer at NERSC.

72 PHYSICS OF ELEMENTARY PARTICLES AND FIELDS↗
DOE OSTI2025

GRAPH — an readout ASIC for large MCP based detectors

We present a programmable 16 channel, mixed signal, low power readout ASIC, having the project historically named Gigasample Recorder of Analog waveforms from a PHotodetector (GRAPH). It is designed to read large aperture single photon imaging detectors using micro channel plates for charge multiplication, and measuring the detector's response on crossed strips anodes to extrapolate the incoming photon position. Each channel consists of a fast, low power and low noise charge sensitive amplifier, which provides a myriad of coarse and fine programmable options for gain and shaping settings. Further, the amplified signal is recorded using, to our knowledge novel, the Hybrid Universal sampLing Architecture (HULA) ADC. A kind of mixed signal double buffer memory, that enables concurrent waveform recording, and selected event digitized data extraction. The sampling frequency is freely adjustable between few kHz up to 125 MHz, while the chip's internal digital memory holds a history 2048 samples for each channel, with a digital headroom of 12 bits. An optimized region of interest sample-read algorithm allows to extract the information just around the event pulse peak, while selecting the next event, thus substantially reducing the operational dead time. The chip is designed in 130 nm TSMC CMOS technology, and its power consumption is around 47 mW per channel.

47 OTHER INSTRUMENTATION↗
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

Acceleration of Graph Neural Network-Based Prediction Models in Chemistry via Co-Design Optimization on Intelligence Processing Units

Atomic structure prediction and associated property calculations are the bedrock of chemical physics. Since high-fidelity ab initio modeling techniques for computing the structure and properties can be prohibitively expensive, this motivates the development of machine-learning (ML) models that make these predictions more efficiently. Training graph neural networks over large atomistic databases introduces unique computational challenges such as the need to process millions of small graphs with variable size and support communication patterns that are distinct from learning over large graphs such as social networks. We demonstrate a novel hardware-software co-design approach to scale up the training of atomistic graph neural networks (GNN) for structure and property prediction. First, to eliminate redundant computation and memory associated with alternative padding techniques and to improve throughput via minimizing communication, we formulate the effective coalescing of the batches of variable-size atomistic graphs as the bin packing problem and introduce a hardware-agnostic algorithm to pack these batches. In addition, we propose hardware-specific optimizations including a planner and vectorization for the gather-scatter operations targeted for Graphcore’s Intelligence Processing Unit (IPU), as well as model-specific optimizations such as merged communication collectives and optimized softplus. Putting these all together, we demonstrate the effectiveness of the proposed co-design approach by providing an implementation of a well-established atomistic GNN on the Graphcore IPUs. We evaluate the training performance on multiple atomistic graph databases with varying degrees of graph counts, sizes and sparsity. Here, we demonstrate that such a co-design approach can reduce the training time of atomistic GNNs and can improve the performance by up to 1.5× compared to the baseline implementation of the model on the IPUs. Additionally, we compare our IPU implementation with a Nvidia GPU-based implementation and show that our atomistic GNN implementation on the IPUs can run 1.8× faster on average compared to the execution time on the GPUs.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗
NASA NTRSDate not supplied

Trust-Informed Large Language Models via Word Embedding-Knowledge Graph Alignment

A major weakness of a Large Language Model (LLM) is its tendency to accept information at face value, often leading to injection of erroneous information and inducing a greater probability of hallucinating non-existent information. While Retrieval Augmented Generation (RAG) uses external knowledge sources to bolster LLMs through grounded truth, this work seeks to explore methods to engender a LLM with an intrinsic capability to evaluate an input’s believability without relying on external knowledge sources. We investigate unifying a LLM with a Knowledge Graph (KG) and using the KG to reinforce the LLM’s internal word embedding while also maintaining belief metrics along the edge’s in the KG.

Large Language Model↗
DOE OSTI2020

Multilevel graph embedding

The goal of the present paper is the design of embeddings of a general sparse graph into a set of points in $\mathbb{R}^d$ for appropriate d ≥ 2. The embeddings that we are looking at here aim to keep vertices that are grouped in communities together and keep the rest apart. To achieve this property, we utilize coarsening that respects possible community structures of the given graph. We employ a hierarchical multilevel coarsening approach that identifies communities (strongly connected groups of vertices) at every level. The multilevel strategy allows any given (presumably expensive) graph embedding algorithm to be made into a more scalable (and faster) algorithm. We demonstrate the presented approach on a number of given embedding algorithms and large-scale graphs and achieve speed-up over the methods in a recent paper.

97 MATHEMATICS AND COMPUTING↗
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 OSTI2023

Benchmarking the PCMCI Causal Discovery Algorithm for Spatiotemporal Systems

Causal discovery algorithms construct hypothesized causal graphs that depict causal dependencies among variables in observational data. While powerful, the accuracy of these algorithms is highly sensitive to the underlying dynamics of the system in ways that have not been fully characterized in the literature. In this report, we benchmark the PCMCI causal discovery algorithm in its application to gridded spatiotemporal systems. Effectively computing grid-level causal graphs on large grids will enable analysis of the causal impacts of transient and mobile spatial phenomena in large systems, such as the Earth’s climate. We evaluate the performance of PCMCI with a set of structural causal models, using simulated spatial vector autoregressive processes in one- and two-dimensions. We develop computational and analytical tools for characterizing these processes and their associated causal graphs. Our findings suggest that direct application of PCMCI is not suitable for the analysis of dynamical spatiotemporal gridded systems, such as climatological data, without significant preprocessing and downscaling of the data. PCMCI requires unrealistic sample sizes to achieve acceptable performance on even modestly sized problems and suffers from a notable curse of dimensionality. This work suggests that, even under generous structural assumptions, significant additional algorithmic improvements are needed before causal discovery algorithms can be reliably applied to grid-level outputs of earth system models.

54 ENVIRONMENTAL SCIENCES↗