Search NASA⌕ Search

SEARCH · Search NASA

Results for “graph learning algorithm”

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 OSTI2024

Optimization on Manifolds via Graph Gaussian Processes

This paper integrates manifold learning techniques within a Gaussian process upper confidence bound algorithm to optimize an objective function on a manifold. Our approach is motivated by applications where a full representation of the manifold is not available and querying the objective is expensive. We rely on a point cloud of manifold samples to define a graph Gaussian process surrogate model for the objective. Query points are sequentially chosen using the posterior distribution of the surrogate model given all previous queries. We establish regret bounds in terms of the number of queries and the size of the point cloud. Several numerical examples complement the theory and illustrate the performance of our method.

Bayesian optimization↗
DOE OSTI2023

Spatio-Temporal Deep Graph Network for Event Detection, Localization, and Classification in Cyber-Physical Electric Distribution System

This work proposes a deep graph learning framework to identify, locate, and classify power, cyber, and cyber power events at the distribution system level. The proposed algorithm jointly exploits spatial, temporal, and node-level cyber and physical data features. The developed graph neural network, together with a deep autoencoder, utilizes physical measurements from distribution level phasor measurement units and cyber data from communication network logs. The spatial structure of the synchrophasor measurements and network is incorporated through a weighted adjacency matrix. The temporal structure is incorporated by defining a spatial operation in the gated recurrent unit. This spatio-temporal learning element resides inside a power event detection, localization, and classification module that provides the degree of confidence for an event label. To accurately pinpoint the location of an event to the nearest bus equipped with a measurement unit, a combination of squared error and proximity score is utilized. Also included is a cyber event detection module that employs heteroskedasticity to analyze the significance of various cyber features during different types of attacks. Finally, a dual-bit cyber-power decision table determines the nature of the event. The proposed method is validated on two distribution systems modeled in OPAL-RT/Hypersim with limited phasor measurement units for different possible physical and cyber events. Further analyses include comparison with other state-of-the-art methods and validation in the presence of measurement noise. As a result, our method outperforms existing approaches and achieves an average detection accuracy of 97.97%, F1-score of 96.88%, precision of 96.53%, and recall of 98.57%.

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 OSTI2021

Co-design of Advanced Architectures for Graph Analytics using Machine Learning

A graph is an excellent way of representing relationships among entities. We can use graph analytics to synthesize and analyze such relational data, and extract relevant features that are useful for various tasks such as machine learning. Considering the crucial role of graph analytics in various domains, it is important and timely to investigate the right hardware configurations that can achieve optimal performance for graph workloads on future high-performance computing systems. Design space exploration studies facilitate the selection of appropriate configurations (e.g. memory) to achieve a desired system performance. Recently, the approach of accelerating graph analytics using persistent non-volatile memory has gained a lot of attention. Traditional system simulators such as Gem5 and NVMain can be used to explore the design space of these advanced memory architectures for graph workloads. However, these simulators are slow in execution thus limiting the efficiency of design space exploration studies. To overcome this challenge, we proposed a machine learning based approach to co-design advanced memory architectures for graph workloads. We tested our approach with DRAM, non-volatile memory, and hybrid memory (DRAM+NVM) using a breadth first search benchmark algorithm. Our results showed the applicability of the proposed machine learning based approach to the co-design of the advanced memory architectures. In this paper, we provide recommendations on selecting advanced memory architectures to achieve desired performance for graph workloads. We also discuss the performances of different machine learning models that were considered in this study.

Kurte, Kuldeep↗
DOE OSTI2023

Graph-based machine learning improves just-in-time defect prediction

The increasing complexity of today’s software requires the contribution of thousands of developers. This complex collaboration structure makes developers more likely to introduce defect-prone changes that lead to software faults. Determining when these defect-prone changes are introduced has proven challenging, and using traditional machine learning (ML) methods to make these determinations seems to have reached a plateau. In this work, we build contribution graphs consisting of developers and source files to capture the nuanced complexity of changes required to build software. By leveraging these contribution graphs, our research shows the potential of using graph-based ML to improve Just-In-Time (JIT) defect prediction. We hypothesize that features extracted from the contribution graphs may be better predictors of defect-prone changes than intrinsic features derived from software characteristics. We corroborate our hypothesis using graph-based ML for classifying edges that represent defect-prone changes. This new framing of the JIT defect prediction problem leads to remarkably better results. We test our approach on 14 open-source projects and show that our best model can predict whether or not a code change will lead to a defect with an F1 score as high as 77.55% and a Matthews correlation coefficient (MCC) as high as 53.16%. This represents a 152% higher F1 score and a 3% higher MCC over the state-of-the-art JIT defect prediction. We describe limitations, open challenges, and how this method can be used for operational JIT defect prediction.

59 BASIC BIOLOGICAL SCIENCES↗
DOE OSTI2020

Neuromorphic Graph Algorithms: Extracting Longest Shortest Paths and Minimum Spanning Trees

Neuromorphic computing is poised to become a promising computing paradigm in the post Moore's law era due to its extremely low power usage and inherent parallelism. Traditionally speaking, a majority of the use cases for neuromorphic systems have been in the field of machine learning. In order to expand their usability, it is imperative that neuromorphic systems be used for non-machine learning tasks as well. The structural aspects of neuromorphic systems (i.e., neurons and synapses) are similar to those of graphs (i.e., nodes and edges), However, it is not obvious how graph algorithms would translate to their neuromorphic counterparts. In this work, we propose a preprocessing technique that introduces fractional offsets on the synaptic delays of neuromorphic graphs in order to break ties. This technique, in turn, enables two graph algorithms: longest shortest path extraction and minimum spanning trees.

Kay, Bill↗
DOE OSTI2024

Optimizing High-Throughput Inference on Graph Neural Networks at Shared Computing Facilities with the NVIDIA Triton Inference Server

Abstract With machine learning applications now spanning a variety of computational tasks, multi-user shared computing facilities are devoting a rapidly increasing proportion of their resources to such algorithms. Graph neural networks (GNNs), for example, have provided astounding improvements in extracting complex signatures from data and are now widely used in a variety of applications, such as particle jet classification in high energy physics (HEP). However, GNNs also come with an enormous computational penalty that requires the use of GPUs to maintain reasonable throughput. At shared computing facilities, such as those used by physicists at Fermi National Accelerator Laboratory (Fermilab), methodical resource allocation and high throughput at the many-user scale are key to ensuring that resources are being used as efficiently as possible. These facilities, however, primarily provide CPU-only nodes, which proves detrimental to time-to-insight and computational throughput for workflows that include machine learning inference. In this work, we describe how a shared computing facility can use the NVIDIA Triton Inference Server to optimize its resource allocation and computing structure, recovering high throughput while scaling out to multiple users by massively parallelizing their machine learning inference. To demonstrate the effectiveness of this system in a realistic multi-user environment, we use the Fermilab Elastic Analysis Facility augmented with the Triton Inference Server to provide scalable and high-throughput access to a HEP-specific GNN and report on the outcome.

72 PHYSICS OF ELEMENTARY PARTICLES AND FIELDS↗
DOE OSTI2018

Error-Bounded Graph Construction for Semi-supervised Manifold Learning

Graphs are commonly used in semi-supervised learning to represent a manifold on which the data reside in a high-dimensional ambient space. The graph can then be utilized in different ways, typically via the Laplacian of the graph, in order to leverage associations among the unlabeled data to improve learning. One common way to leverage the graph Laplacian is as a regularization term, where models that would disagree with the graph are penalized. More often the spectrum of the graph Laplacian is used to find a lower dimensional embedding in which neighboring relations encoded via the graph are preserved. Most manifold-based methods of semi-supervised learning depend upon geometric structure in the ambient feature space in order to construct a graph whose edges encode similarity that should be useful in selecting a model. A critical assumption is that some standard measure of similarity applied to the ambient space can be used to construct a graph that is error-free or of low error, meaning that examples (i.e., vertices) from distinct classes are not connected. However, this assumption often precludes the use of such methods in noisy or complex feature spaces, even though such spaces often arise in problems that can most benefit from structure that might be uncovered within the unlabeled data. This paper presents a method of graph construction for manifold-based semi-supervised learning that respects the manifold assumptions underlying these methods and bounds the error on the graph itself, which then permits bounds on the overall generalization error of the learning algorithms without relying on assumptions that do not hold in many modern problem domains.

Symons, Christopher T↗
DOE OSTI2022

GCoD: Graph Convolutional Network Acceleration via Dedicated Algorithm and Accelerator Co-Design

Graph Convolutional Networks (GCNs) have emerged as the state-of-the-art graph learning model. However, it remains notoriously challenging to inference GCNs over large graph datasets, limiting their application to large real-world graphs and hindering the exploration of deeper and more sophisticated GCN graphs. This is because real-world graphs can be extremely large and sparse. Furthermore, the node degree of GCNs tends to follow the power-law distribution and therefore have highly irregular adjacency matrices, resulting in prohibitive inefficiencies in both data processing and movement and thus substantially limiting the achievable GCN acceleration efficiency. To this end, this paper proposes the first GCN algorithm and accelerator Co-Design framework dubbed GCoD which can largely alleviate the aforementioned GCN irregularity and boost GCNs' inference efficiency. Specifically, on the algorithm level, GCoD integrates a divide and conquer GCN training strategy that polarizes the graphs to be either denser or sparser in local neighborhoods without compromising the model accuracy, resulting in graph adjacency matrices that (mostly) have merely two levels of workload and enjoys largely enhanced regularity and thus ease of acceleration. On the hardware level, we further develop a dedicated two-pronged accelerator with a separated engine to process each of the aforementioned workloads, further boosting the overall utilization and acceleration efficiency. Extensive experiments and ablation studies validate that our GCoD consistently outperforms state-of-the-art designs in terms of accelerator efficiency while maintaining or even improving the task accuracy. Additionally, we visualize GCoD trained graph adjacency matrices to better understand its advantages. All codes and pre-trained models will be released upon acceptance.

You, Haoran↗
DOE OSTI2025

Spectral Clustering-Based Partitioning of Large-Scale Power Electronics-Based Power Systems for Small-Signal Stability Analysis

The nodal admittance matrix (NAM)-based approach is well-suited for small-signal stability analysis of large-scale power electronics-based power systems (PEPSs), as it preserves the system structure through its admittance matrix. Previous studies have explored partitioning such systems into subareas and interconnections to reduce computational burden; however, they lacked a formal algorithmic procedure for determining feasible partitions. While several grid partitioning methods, such as those based on graph theory or machine learning, exist in the literature, they cannot be directly applied to NAM-based analysis due to differing objectives and constraints. Here, this paper addresses this gap by presenting a systematic, step-by-step procedure for applying a spectral partitioning algorithm that yields a division of the system into subareas suitable for NAM-based analysis. The computational complexity of the proposed method is also derived to demonstrate its efficiency and justify the practicality of the resulting subarea decomposition. The performance of the partitioning method is evaluated by applying the spectral clustering-derived subareas and interconnections to the NAM-based partitioning approach on a 140-bus system. Computational times for the full-system and partitioned NAM analyses are compared using MATLAB. Additionally, PSCAD simulations of the complete system and partitioned subareas are carried out to verify the effectiveness of the proposed method.

Nupur [Univ. of Tennessee, Knoxville, TN (United S↗
DOE OSTI2020

Graph interpolating activation improves both natural and robust accuracies in data-efficient deep learning

Improving the accuracy and robustness of deep neural nets (DNNs) and adapting them to small training data are primary tasks in deep learning (DL) research. In this paper, we replace the output activation function of DNNs, typically the data-agnostic softmax function, with a graph Laplacian-based high-dimensional interpolating function which, in the continuum limit, converges to the solution of a Laplace–Beltrami equation on a high-dimensional manifold. Furthermore, we propose end-to-end training and testing algorithms for this new architecture. The proposed DNN with graph interpolating activation integrates the advantages of both deep learning and manifold learning. Compared to the conventional DNNs with the softmax function as output activation, the new framework demonstrates the following major advantages: First, it is better applicable to data-efficient learning in which we train high capacity DNNs without using a large number of training data. Second, it remarkably improves both natural accuracy on the clean images and robust accuracy on the adversarial images crafted by both white-box and black-box adversarial attacks. Third, it is a natural choice for semi-supervised learning. This paper is a significant extension of our earlier work published in NeurIPS, 2018. For reproducibility, the code is available at https://github.com/BaoWangMath/DNN-DataDependentActivation .

Mathematics↗
DOE OSTI2020

Graph Neural Networks for Particle Reconstruction in High Energy Physics detectors

Pattern recognition problems in high energy physics are notably different from traditional machine learning applications in computer vision. Reconstruction algorithms identify and measure the kinematic properties of particles produced in high energy collisions and recorded with complex detector systems. Two critical applications are the reconstruction of charged particle trajectories in tracking detectors and the reconstruction of particle showers in calorimeters. These two problems have unique challenges and characteristics, but both have high dimensionality, high degree of sparsity, and complex geometric layouts. Graph Neural Networks (GNNs) are a relatively new class of deep learning architectures which can deal with such data effectively, allowing scientists to incorporate domain knowledge in a graph structure and learn powerful representations leveraging that structure to identify patterns of interest. In this work we demonstrate the applicability of GNNs to these two diverse particle reconstruction problems.

46 INSTRUMENTATION RELATED TO NUCLEAR SCIENCE AND ↗
DOE OSTI2023

Domain Adaptive Graph Neural Networks for Constraining Cosmological Parameters Across Multiple Data Sets

State of the art astronomical simulations have provided datasets which enabled the training of novel deep learning techniques for constraining cosmological parameters. However, differences in subgrid physics implementation and numerical approximations among simulation suites lead to differences in simulated datasets, which pose a hard challenge when trying to generalize across diverse data domains and ultimately when applying models to observational data. Recent work reveals deep learning algorithms are able to extract more information from complex cosmological simulations than summary statistics like power spectra. We introduce Domain Adaptive Graph Neural Networks (DA-GNNs), trained on CAMELS data, inspired by CosmoGraphNet (Villanueva-Domingo et al 2023). By utilizing GNNs, we can capitalize on their capacity to capture both astrophysical and topological features of galaxy distributions. Mixing these capabilities with domain adaptation techniques such as Maximum Mean Discrepancy (MMD), which enable extraction of domain-invariant features, our framework demonstrates enhanced accuracy and robustness. We present experimental results, including the alignment of distributions across domains through data visualization. These findings suggest that DA-GNNs are an efficient way of extracting domain independent cosmological information, a vital step toward robust deep learning for real cosmic survey data.

79 ASTRONOMY AND ASTROPHYSICS↗
DOE OSTI2025

Optimizing Traffic Signal Control to Enhance Transportation Efficiency and Maximize Pedestrian Benefits in the Road Network

Increasing urban mobility requirements demand efficient transportation system strategies for both vehicular and pedestrian movement. This study enhances the Decentralized Graph-based Multi-Agent Reinforcement Learning (DGMARL) approach, originally tailored for vehicular traffic signal timing, to incorporate pedestrian traffic dynamics. The improved algorithm considers crucial metrics such as Eco_PI, assesses vehicle fuel consumption by factoring in stops and delays, and addresses pedestrian waiting time, crucial for system efficiency while acknowledging driver waiting time impact. Utilizing Digital Twin simulation along the MLK Smart Corridor in Chattanooga, Tennessee, the algorithm's performance is compared for various pedestrian control scenarios. To evaluate the effectiveness of DGMARL, this study compared DGMARL-enabled signal management with automated pedestrian traffic detection and an actuated signal management system (real-word baseline) with pedestrian recall, which predetermingly enforces a pedestrian phase every cycle. Findings indicate substantial improvements with DGMARL, showing a 28.29% enhancement in vehicle Eco_PI, a 60.55 % reduction in pedestrian waiting time, and a 55.74% decrease in driver stop delay, on average, compared to the baseline actuated signal timing plan.

Kumarasamy, Vijayalakshmi K [The University of Ten↗
DOE OSTI2022

Learning Planar Ising Models Software

Learning Planar Ising Models is a software package written in Matlab for learning relationships among variable in a dataset using graphical models. The software package implements a generally-applicable algorithm for learning planar Ising models from any multivariate dataset. The code provides an algorithm for learning the best planar Ising model to approximate an arbitrary collection of binary random variables (possibly from sample data). Given the set of all pairwise correlations among variables, we select a planar graph and optimal planar Ising model defined on this graph to best approximate that set of correlations. The software includes demonstrations of the algorithm in simulations and for applications on publicly available datasets. Details of the algorithm, demonstration simulations, and applications are given in Johnson, et al; 2016. Reference: Johnson, J. K., Oyen, D., Chertkov, M., and Netrapalli, P. (2016). Learning planar Ising models. Journal of Machine Learning Research.

Oyen, Diane↗
DOE OSTI2024

Artificial Intelligence/Machine Learning Technology in Power System Applications

The primary purpose of this report is to provide an overview of the advancement in artificial intelligence and machine learning (AI/ML) technologies and their applications in power systems. It offers a foundation for understanding the transformative role of AI/ML in power systems and aims to stimulate further research and development in this area. This report begins with a historical perspective of AI/ML technologies, then explores their advancement to today’s prominence. The document highlights key contributors to the success of AI/ML technologies, including increased computational power, greater data availability, innovative algorithms, and advanced tools. It further introduces various AI/ML techniques, including supervised, unsupervised and reinforcement learning, graph neural networks, and generative AI. It also emphasizes the critical importance of ensuring the safety, security, and trustworthiness of these AI/ML techniques within this sector. The report reviews the recent representative advancements in various power system applications enhanced by AI/ML techniques, underscoring key developments and their transformative impact as evidenced by numerous studies. It also explores both the opportunities and challenges associated with the application of AI/ML technologies to improve power system applications. While the report extensively covers AI/ML applications in power systems, focusing primarily on the technical and operational aspects, it may not thoroughly explore the sociopolitical, economic, and broader regulatory implications of AI/ML integration in power systems. AI/ML techniques hold significant potential for enhancing power system applications; however, they are not omnipotent. It is crucial to acknowledge their limitations and understand that they may not be able to address all challenges in the power system domain. Various factors must be considered that influence the implementation, adoption, and effectiveness of AI/ML solutions, including but not limited to safety, security, transparency, and trustworthiness. Additionally, the incorporation of advanced human–machine interfaces is essential, as it enables humans to validate the effectiveness of AI/ML solutions while remaining actively engaged, fostering trust in AI/ML deployment. Finally, the report summarizes AI/ML research activities supported by the Department of Energy (DOE) Office of Electricity (OE) through the Advanced Grid Modeling (AGM) program. The work aligns with the interests and mission of DOE-OE AGM, with the report serving as a resource for identifying existing progress and for pinpointing future applications within AI/ML that need further exploration and support.

24 POWER TRANSMISSION AND DISTRIBUTION↗
DOE OSTI2022

MSASGCN : Multi-Head Self-Attention Spatiotemporal Graph Convolutional Network for Traffic Flow Forecasting

Traffic flow forecasting is an essential task of an intelligent transportation system (ITS), closely related to intelligent transportation management and resource scheduling. Dynamic spatial-temporal dependencies in traffic data make traffic flow forecasting to be a challenging task. Most existing research cannot model dynamic spatial and temporal correlations to achieve well-forecasting performance. The multi-head self-attention mechanism is a valuable method to capture dynamic spatial-temporal correlations, and combining it with graph convolutional networks is a promising solution. Therefore, we propose a multi-head self-attention spatiotemporal graph convolutional network (MSASGCN) model. It can effectively capture local correlations and potential global correlations of spatial structures, can handle dynamic evolution of the road network, and, in the time dimension, can effectively capture dynamic temporal correlations. Experiments on two real datasets verify the stability of our proposed model, obtaining a better prediction performance than the baseline algorithms. The correlation metrics get significantly reduced compared with traditional time series prediction methods and deep learning methods without using graph neural networks, according to MAE and RMSE results. Compared with advanced traffic flow forecasting methods, our model also has a performance improvement and a more stable prediction performance. We also discuss some problems and challenges in traffic forecasting.

Cao, Yang↗