Search NASA⌕ Search

SEARCH · Search NASA

Results for “high performance graph algorithms”

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
DOE OSTI2022

Augmenting Graph Convolution with Distance Preserving Embedding for Improved Learning

Graph convolution incorporates topological information of a graph into learning. Message passing corresponds to traversal of a local neighborhood in classical graph algorithms. We show that incorporating additional global structures, such as shortest paths, through distance preserving embedding can improve performance. Our approach, Gavotte, significantly improves the performance of a range of popular graph neu-ral networks such as GCN, GA T,Graph SAGE, and GCNII for transductive learning. Gavotte also improves the performance of graph neural networks for full-supervised tasks, albeit to a smaller degree. As high-quality embeddings are generated by Gavotte as a by-product, we leverage clustering algorithms on these embed dings to augment the training set and introduce Gavotte+. Our results of Gavotte+ on datasets with very few labels demonstrate the advantage of augmenting graph convolution with distance preserving embedding.

Cong, Guojing↗
DOE OSTI2021

MLPF: efficient machine-learned particle-flow reconstruction using graph neural networks

In general-purpose particle detectors, the particle-flow algorithm may be used to reconstruct a comprehensive particle-level view of the event by combining information from the calorimeters and the trackers, significantly improving the detector resolution for jets and the missing transverse momentum. In view of the planned high-luminosity upgrade of the CERN Large Hadron Collider (LHC), it is necessary to revisit existing reconstruction algorithms and ensure that both the physics and computational performance are sufficient in an environment with many simultaneous proton–proton interactions (pileup). Machine learning may offer a prospect for computationally efficient event reconstruction that is well-suited to heterogeneous computing platforms, while significantly improving the reconstruction quality over rule-based algorithms for granular detectors. We introduce MLPF, a novel, end-to-end trainable, machine-learned particle-flow algorithm based on parallelizable, computationally efficient, and scalable graph neural network optimized using a multi-task objective on simulated events. We report the physics and computational performance of the MLPF algorithm on a Monte Carlo dataset of top quark–antiquark pairs produced in proton–proton collisions in conditions similar to those expected for the high-luminosity LHC. The MLPF algorithm improves the physics response with respect to a rule-based benchmark algorithm and demonstrates computationally scalable particle-flow reconstruction in a high-pileup environment.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2018

Xi-cam : a versatile interface for data visualization and analysis

Xi-cam is an extensible platform for data management, analysis and visualization. Xi-cam aims to provide a flexible and extensible approach to synchrotron data treatment as a solution to rising demands for high-volume/high-throughput processing pipelines. The core of Xi-cam is an extensible plugin-based graphical user interface platform which provides users with an interactive interface to processing algorithms. Plugins are available for SAXS/WAXS/GISAXS/GIWAXS, tomography and NEXAFS data. With Xi-cam 's `advanced' mode, data processing steps are designed as a graph-based workflow, which can be executed live, locally or remotely. Remote execution utilizes high-performance computing or de-localized resources, allowing for the effective reduction of high-throughput data. Xi-cam 's plugin-based architecture targets cross-facility and cross-technique collaborative development, in support of multi-modal analysis. Xi-cam is open-source and cross-platform, and available for download on GitHub.

Pandolfi, Ronald J. (ORCID:0000000308248548)↗
DOE OSTI2023

Semi-supervised graph neural networks for pileup noise removal

Abstract The high instantaneous luminosity of the CERN Large Hadron Collider leads to multiple proton–proton interactions in the same or nearby bunch crossings (pileup). Advanced pileup mitigation algorithms are designed to remove this noise from pileup particles and improve the performance of crucial physics observables. This study implements a semi-supervised graph neural network for particle-level pileup noise removal, by identifying individual particles produced from pileup. The graph neural network is firstly trained on charged particles with known labels, which can be obtained from detector measurements on data or simulation, and then inferred on neutral particles for which such labels are missing. This semi-supervised approach does not depend on the neutral particle pileup label information from simulation, and thus allows us to perform training directly on experimental data. The performance of this approach is found to be consistently better than widely-used domain algorithms and comparable to the fully-supervised training using simulation truth information. The study serves as the first attempt at applying semi-supervised learning techniques to pileup mitigation, and opens up a new direction of fully data-driven machine learning pileup mitigation studies.

43 PARTICLE ACCELERATORS↗
DOE OSTI2021

Versatile feature learning with graph convolutions and graph structures

Graphs represent real world relationships, and graph embedding projects nodes in a graph to a latent space that can help simplify downstream tasks. Recent development of graph convolutions in deep learning significantly improves the performance of many learning tasks on graphs. Unfortunately, prior embedding methods either do not embed graphs with node features, or fail to produce high-quality embeddings for downstream learning tasks that result in large performance gap in comparison to direct learning on graphs.We present a versatile and effective embedding method, Conv2Vec, for embedding graphs with or without node features. It is based on graph convolutions with objective functions motivated by concepts and structures from classical graph algorithms. Conv2Vec produce high-quality embedding for both plain graphs and graphs with node features for downstream tasks.We evaluate the embeddings generated by Conv2Vec with a transductive node classification task. With the generated embeddings and very simple machine learning approaches, we are able to achieve accuracies similar to those achieved by direct learning with graph convolutions. Interestingly, if we strip the node features from the graph and thus learning an embedding has to rely entirely on the graph topology, node classification with our embedding significantly outperforms direct learning with various graph convolutions. This suggests that structures from classical graph algorithms may play an important role in learning on graphs.

Cong, Guojing↗
DOE OSTI2024

AGS-GNN: Attribute-guided Sampling for Graph Neural Networks

We propose AGS-GNN, a novel attribute-guided sampling algorithm for Graph Neural Networks (GNNs) that exploits node features and connectivity structure of a graph while simultaneously adapting for both homophily and heterophily in graphs. (In homophilic graphs vertices of the same class are more likely to be connected, and vertices of different classes tend to be linked in heterophilic graphs.) While GNNs have been successfully applied to homophilic graphs, their application to heterophilic graphs remains challenging. The best-performing GNNs for heterophilic graphs do not fit the sampling paradigm, suffer high computational costs, and are not inductive. We employ samplers based on feature-similarity and feature-diversity to select subsets of neighbors for a node, and adaptively capture information from homophilic and heterophilic neighborhoods using dual channels. Currently, AGS-GNN is the only algorithm that we know of that explicitly controls homophily in the sampled subgraph through similar and diverse neighborhood samples. For diverse neighborhood sampling, we employ submodularity, which was not used in this context prior to our work. The sampling distribution is pre-computed and highly parallel, achieving the desired scalability. Using an extensive dataset consisting of 35 small (<=100K nodes) and large (>100K nodes) homophilic and heterophilic graphs, we demonstrate the superiority of AGS-GNN compare to the current approaches in the literature. AGS-GNN achieves comparable test accuracy to the best-performing heterophilic GNNs, even outperforming methods using the entire graph for node classification. AGS-GNN also converges faster compared to methods that sample neighborhoods randomly, and can be incorporated into existing GNN models that employ node or graph sampling.

artificial intelligence↗
DOE OSTI2018

Robust system size reduction of discrete fracture networks: a multi-fidelity method that preserves transport characteristics

In this paper, we propose a multi-fidelity system reduction technique that uses weighted graphs paired with three-dimensional discrete fracture network (DFN) modelling for efficient simulation of subsurface flow and transport in fractured media. DFN models are used to simulate flow and transport in subsurface fractured rock with low-permeability. One method to alleviate the heavy computational overhead associated with these simulations is to reduce the size of the DFN using a graph representation of it to identify the primary flow sub-network and only simulate flow and transport thereon. The first of these methods used unweighted graphs constructed solely on DFN topology and could be used for accurate predictions of first-passage times. However, these techniques perform poorly when predicting later stages of the mass breakthrough. We utilize a weighted-graph representation of the DFN where edge weights are based on hydrological parameters in the DFN that allows us to exploit the kinematic quantities derivable a posteriori from the flow solution obtained on the graph representation of the DFN to perform system reduction and predict the later stages of the breakthrough curve with high fidelity. We also propose and demonstrate the use of an adaptive pruning algorithm with error control that produces a pruned DFN sub-network whose predicted mass breakthrough agrees with the original DFN within a user-specified tolerance. Lastly, the method allows for the level of accuracy to be a user-controlled parameter.

58 GEOSCIENCES↗
DOE OSTI2024

Efficient Hybrid Attack Graph Generation for Cyber-Physical System Resilience Experimentation (Final Project Report)

HAGEN project has developed theory, algorithms, and capabilities to assist cyber physical system modelers and operators to perform system and device-level vulnerability assessment, risk assessment, impact assessment, and mitigation planning. The project generates hybrid attack graphs for Cyber-Physical System (CPS) resilience experimentation at desired scale and speed. The project will produce composite attack datasets, algorithms, and demonstrable prototypical tools, and a library of high-impact attack sequences for a given CPS of interest. This report provided overall summary of research and development performed between FY22-24.

45 MILITARY TECHNOLOGY, WEAPONRY, AND NATIONAL DEF↗
DOE OSTI2022

ExaTN: Scalable GPU-Accelerated High-Performance Processing of General Tensor Networks at Exascale

We present ExaTN (Exascale Tensor Networks), a scalable GPU-accelerated C++ library which can express and process tensor networks on shared- as well as distributed-memory high-performance computing platforms, including those equipped with GPU accelerators. Specifically, ExaTN provides the ability to build, transform, and numerically evaluate tensor networks with arbitrary graph structures and complexity. It also provides algorithmic primitives for the optimization of tensor factors inside a given tensor network in order to find an extremum of a chosen tensor network functional, which is one of the key numerical procedures in quantum many-body theory and quantum-inspired machine learning. Numerical primitives exposed by ExaTN provide the foundation for composing rather complex tensor network algorithms. We enumerate multiple application domains which can benefit from the capabilities of our library, including condensed matter physics, quantum chemistry, quantum circuit simulations, as well as quantum and classical machine learning, for some of which we provide preliminary demonstrations and performance benchmarks just to emphasize a broad utility of our library.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2025

ARCH: Large-scale knowledge graph via aggregated narrative codified health records analysis

Objective: Electronic health record (EHR) systems contain a wealth of clinical data stored as both codified data and free-text narrative notes (NLP). The complexity of EHR presents challenges in feature representation, information extraction, and uncertainty quantification. Here, to address these challenges, we proposed an efficient Aggregated naRrative Codified Health (ARCH) records analysis to generate a large-scale knowledge graph (KG) for a comprehensive set of EHR codified and narrative features. Methods: Using data from 12.5 million Veterans Affairs patients, ARCH first derives embedding vectors and generates similarities along with associated p-values to measure the strength of relatedness between clinical features with statistical certainty quantification. Next, ARCH performs a sparse embedding regression to remove indirect linkage between features to build a sparse KG. Finally, ARCH was validated on various clinical tasks, including detecting known relationships between entity pairs, predicting drug side effects, disease phenotyping, as well as sub-typing Alzheimer’s disease patients. Results: ARCH produces high-quality clinical embeddings and KG for over 60,000 codified and narrative EHR concepts. The KG and embeddings are visualized in the R-shiny powered web-API.3 ARCH achieved high accuracy in detecting EHR concept relationships, with AUCs of 0.926 (codified) and 0.861 (NLP) for similar EHR concepts, and 0.810 (codified) and 0.843 (NLP) for related pairs. It detected drug side effects with a 0.723 AUC, which improved to 0.826 after fine-tuning. Using both codified and NLP features, the detection power increased significantly. Compared to other methods, ARCH has superior accuracy and enhances weakly supervised phenotyping algorithms’ performance. Notably, it successfully categorized Alzheimer’s patients into two subgroups with varying mortality rates. Conclusion: The proposed ARCH algorithm generates large-scale high-quality semantic representations and knowledge graph for both codified and NLP EHR features, useful for a wide range of predictive modeling tasks.

Electronic health records↗
DOE OSTI2020

Parallel algorithms for finding connected components using linear algebra

Finding connected components is one of the most widely used operations on a graph. Optimal serial algorithms for the problem have been known for half a century, and many competing parallel algorithms have been proposed over the last several decades under various different models of parallel computation. This paper presents a class of parallel connected-component algorithms designed using linear-algebraic primitives. These algorithms are based on a PRAM algorithm by Shiloach and Vishkin and can be designed using standard GraphBLAS operations. Here, we demonstrate two algorithms of this class, one named LACC for Linear Algebraic Connected Components, and the other named FastSV which can be regarded as LACC’s simplification. With the support of the highly-scalable Combinatorial BLAS library, LACC and FastSV outperform the previous state-of-the-art algorithm by a factor of up to 12x for small to medium scale graphs. For large graphs with more than 50B edges, LACC and FastSV scale to 4K nodes (262K cores) of a Cray XC40 supercomputer and outperform previous algorithms by a significant margin. This remarkable performance is accomplished by (1) exploiting sparsity that was not present in the original PRAM algorithm formulation, (2) using high-performance primitives of Combinatorial BLAS, and (3) identifying hot spots and optimizing them away by exploiting algorithmic insights.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2016

GraphMeta: Managing HPC Rich Metadata in Graphs

High-performance computing (HPC) systems face increasingly critical metadata management challenges, especially in the approaching exascale era. These challenges arise not only from exploding metadata volumes, but also from increasingly diverse metadata, which contains data provenance and arbitrary user-defined attributes in addition to traditional POSIX metadata. This ‘rich’ metadata is becoming critical to supporting advanced data management functionality such as data auditing and validation. In our prior work, we identified a graph-based model as a promising solution to uniformly manage HPC rich metadata due to its flexibility and generality. However, at the same time, graph-based HPC rich metadata anagement also introduces significant challenges to the underlying infrastructure. In this study, we first identify the challenges on the underlying infrastructure to support scalable, high-performance rich metadata management. Based on that, we introduce GraphMeta, a graphbased engine designed for this use case. It achieves performance scalability by introducing a new graph partitioning algorithm and a write-optimal storage engine. We evaluate GraphMeta under both synthetic and real HPC metadata workloads, compare it with other approaches, and demonstrate its advantages in terms of efficiency and usability for rich metadata management in HPC systems.

Dai, Dong↗
DOE OSTI2018

A Graph Theory-Based Automated Twin Recognition Technique for Electron Backscatter Diffraction Analysis

Abstract The present article introduces a new software, Microstructure Evaluation Tool for Interface Statistics (METIS), that performs high-throughput microstructure statistical analysis from electron backscatter diffraction maps. Emphasis is placed on the detection of twin domains in hexagonal close-packed metals. The numerical framework on which METIS is built leverages graph theory, group structures, and associated numerical algorithms to automatically detect twins and unravel both their intrinsic characteristics features and those pertaining to their interactions. The proposed graphical interface allows for the detection and correction of unlikely twin/parent associations rendering the approach applicable to highly deformed microstructures. Twin statistics and microstructural data are classified and saved in a relational database that can be interrogated via either GUI or SQL requests to reveal a wide spectrum of features of the microstructure. Illustration of the approach is performed in the case of zirconium.

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

Accelerated Charged Particle Tracking with Graph Neural Networks on FPGAs

We develop and study FPGA implementations of algorithms for charged particle tracking based on graph neural networks. The two complementary FPGA designs are based on OpenCL, a framework for writing programs that execute across heterogeneous platforms, and hls4ml, a high-level-synthesis-based compiler for neural network to firmware conversion. We evaluate and compare the resource usage, latency, and tracking performance of our implementations based on a benchmark dataset. We find a considerable speedup over CPU-based execution is possible, potentially enabling such algorithms to be used effectively in future computing workflows and the FPGA-based Level-1 trigger at the CERN Large Hadron Collider.

46 INSTRUMENTATION RELATED TO NUCLEAR SCIENCE AND ↗
DOE OSTI2021

Communication-Avoiding and Memory-Constrained Sparse Matrix-Matrix Multiplication at Extreme Scale

Sparse matrix-matrix multiplication (SpGEMM) is a widely used kernel in various graph, scientific computing and machine learning algorithms. In this paper, we consider SpGEMMs performed on hundreds of thousands of processors generating trillions of nonzeros in the output matrix. Distributed SpGEMM at this extreme scale faces two key challenges: (1) high communication cost and (2) inadequate memory to generate the output. Furthermore, we address these challenges with an integrated communication-avoiding and memory-constrained SpGEMM algorithm that scales to 262,144 cores (more than 1 million hardware threads) and can multiply sparse matrices of any size as long as inputs and a fraction of output fit in the aggregated memory. As we go from 16,384 cores to 262,144 cores on a Cray XC40 supercomputer, the new SpGEMM algorithm runs 10x faster when multiplying large-scale protein-similarity matrices.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2016

Wasatch: An architecture-proof multiphysics development environment using a Domain Specific Language and graph theory

To address the coding and software challenges of modern hybrid architectures, we propose an approach to multiphysics code development for high-performance computing. This approach is based on using a Domain Specific Language (DSL) in tandem with a directed acyclic graph (DAG) representation of the problem to be solved that allows runtime algorithm generation. When coupled with a large-scale parallel framework, the result is a portable development framework capable of executing on hybrid platforms and handling the challenges of multiphysics applications. In addition, we share our experience developing a code in such an environment – an effort that spans an interdisciplinary team of engineers and computer scientists.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2019

Graph Algorithms in PGAS: Chapel and UPC++

The Partitioned Global Address Space (PGAS) programming model can be implemented «««< HEAD either with programming language features or with runtime library APIs, each implementation favoring different aspects (e.g., productivity, abstraction, flexibility, or performance). Certain language and runtime features, such as collectives, explicit and asynchronous communication primitives, and constructs facilitating overlap of communication and computation (such as futures and conjoined futures) can enable better performance and scaling for irregular applications, in particular for distributed graph analytics. We compare graph algorithms in one of each of these environments: the Chapel PGAS programming language and the UPC++ PGAS runtime library. We implement algorithms for breadth-first search and triangle counting graph kernels in both environments. We discuss the code in each of the environments, and compile performance data on a Cray Aries and an Infiniband platform. Our results show that the library-based approach of UPC++ currently provides strong performance while Chapel provides a high-level abstraction that, harder to optimize, still provides comparable performance. We argue that various language primitives and runtime library features should be considered in conjunction with each other to design future graph analytics libraries so as to incorporate the best of both worlds.

Distributed Algorithms, Graph algorithms, HPC↗