SEARCH · Search NASA

Results for “Graph”

Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.

SourceResearch connectionFrom yearThrough year

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 451 records · Page 25

All sources NASA NTRS DOE OSTI

DOE OSTI2011

Graph anomalies in cyber communications

Enterprises monitor cyber traffic for viruses, intruders and stolen information. Detection methods look for known signatures of malicious traffic or search for anomalies with respect to a nominal reference model. Traditional anomaly detection focuses on aggregate traffic at central nodes or on user-level monitoring. More recently, however, traffic is being viewed more holistically as a dynamic communication graph. Attention to the graph nature of the traffic has expanded the types of anomalies that are being sought. We give an overview of several cyber data streams collected at Los Alamos National Laboratory and discuss current work in modeling the graph dynamics of traffic over the network. We consider global properties and local properties within the communication graph. A method for monitoring relative entropy on multiple correlated properties is discussed in detail.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2013

Parallel Algorithms for Graph Optimization using Tree Decompositions

Although many NP-hard graph optimization problems can be solved in polynomial time on graphs of bounded tree-width, the adoption of these techniques into mainstream scientific computation has been limited due to the high memory requirements of required dynamic programming tables and excessive running times of sequential implementations. This work addresses both challenges by proposing a set of new parallel algorithms for all steps of a tree-decomposition based approach to solve maximum weighted independent set. A hybrid OpenMP/MPI implementation includes a highly scalable parallel dynamic programming algorithm leveraging the MADNESS task-based runtime, and computational results demonstrate scaling. This work enables a significant expansion of the scale of graphs on which exact solutions to maximum weighted independent set can be obtained, and forms a framework for solving additional graph optimization problems with similar techniques.

Weerapurage, Dinesh P↗

DOE OSTI2013

graphMC: A package for testing the independence of graphs

graphMC consists of an implementation of a set of statistical tests that ensure that a Markov chain in the space of graphs has converged to its stationary distribution. The tests are applicable when the graphs have labelled nodes. The tests are applied to the binary time-series traced out by an edge between two selected nodes. The software fits models of a first-order Markov process and an independent draws from a binary distribution to the time-series and selects one based on the BIC scores of the two models. The package consists of (1) an implementation of a Markov chain driving a graph rewiring process that preserves the joint degree distribution of the graph, (2) implementation of the statistical test mentioned above and (3) two examples that show how the Markov chain infrastructure and the statistical tests can be used.

Source record↗

DOE OSTI2018

Searches over graphs representing geospatial-temporal remote sensing data

Various technologies pertaining to identifying objects of interest in remote sensing images by searching over geospatial-temporal graph representations are described herein. Graphs are constructed by representing objects in remote sensing images as nodes, and connecting nodes with undirected edges representing either distance or adjacency relationships between objects and directed edges representing changes in time. Geospatial-temporal graph searches are made computationally efficient by taking advantage of characteristics of geospatial-temporal data in remote sensing images through the application of various graph search techniques.

47 OTHER INSTRUMENTATION↗

DOE OSTI2018

Representation of activity in images using geospatial temporal graphs

Various technologies pertaining to modeling patterns of activity observed in remote sensing images using geospatial-temporal graphs are described herein. Graphs are constructed by representing objects in remote sensing images as nodes, and connecting nodes with undirected edges representing either distance or adjacency relationships between objects and directed edges representing changes in time. Activity patterns may be discerned from the graphs by coding nodes representing persistent objects like buildings differently from nodes representing ephemeral objects like vehicles, and examining the geospatial-temporal relationships of ephemeral nodes within the graph.

47 OTHER INSTRUMENTATION↗

DOE OSTI2019

Radioactive Decay Computation with a Graph Approach for Solving a Linear Dynamic System

ABSTRACT: This article gives two graph-based algorithms for radioactive decay computation. The first algorithm identifies the connected components of the graph induced from the given radioactive decay dynamics to reduce the size of the problem. The solutions are derived over the precalculated connected components, respectively and independently. The second algorithm utilizes acyclic structure of radioactive decay dynamics. The algorithm evaluates the reachable vertices of the induced system graph from the initially activated vertices and finds the minimal set of starting vertices populating the entire reachable vertices. Then, the decay calculations are performed over the reachable vertices from the identified minimal starting vertices, respectively, with the partitioned initial value over the reachable vertices. A formal argument is given to show that the proposed graph inspired divide and conquer calculation methods perform the intended radioactive decay calculation. Empirical efforts comparing the proposed radioactive decay calculation algorithms are presented.

42 ENGINEERING↗

DOE OSTI2020

Vertex Reordering for Real-world Graphs and Applications: An Empirical Evaluation

Vertex reordering is a way to improve locality in graph computations. Given an input (or ``natural'') order, reordering aims to compute an alternate permutation of the vertices that is aimed at maximizing a locality-based objective. Given decades of research on this topic, there are tens of graph reordering schemes, and there are also several linear arrangement ``gap'' measures for treatment as objectives. However, a comprehensive empirical analysis of the efficacy of the ordering schemes against the different gap measures, and against real-world applications is currently lacking. In this study, we present an extensive empirical evaluation of up to 11 ordering schemes, taken from different classes of approaches, on a set of 34 real-world graphs emerging from different application domains. Our study is presented in two parts: a) a thorough comparative evaluation of the different ordering schemes on their effectiveness to optimize different linear arrangement gap measures, relevant to preserving locality; and b) extensive evaluation of the impact of the ordering schemes on two real-world, parallel graph applications, namely, community detection and influence maximization. Our studies show a significant divergence among the ordering schemes (up to $40\times$ between the best and the poor) in their effectiveness to reduce the gap measures; and a wide ranging impact of the ordering schemes on various aspects including application runtime (up to $4\times$), memory and cache use, load balancing, and parallel work and efficiency. The comparative study also help reveal the nuances of a parallel environment (compared to serial) on the ordering schemes and their role in optimizing applications.

Barik, Reet↗

DOE OSTI2024

Predicting Drug Effects from High-dimensional Asymmetric Drug Data Sets using Graph Neural Networks: A Comprehensive Analysis of Multi-target Drug Effect Prediction

Graph neural networks (GNNs) have emerged as one of the most effective Machine learning (ML) techniques for drug effect prediction from drug molecular graphs. Despite having immense potential, GNN models lack performance when using data sets that contain high dimensional asymmetrically co-occurrent drug effects as targets with complex correlations between them. Training individual learning models for each drug effect and incorporating every prediction result for a wide spectrum of drug effects is beyond practicality. Such an implication provides a testbed to address this challenge as multi-target prediction problems, aiming to predict all drug effects at a time. We develop standard and hybrid graph neural networks (GNNs)to perform two separate tasks that are multi-regression for continuous values and multi-label classification for categorical values contained in our data sets. Since this step makes the target data even more sparse and introduces asymmetric label co-occurrence, the learning of multi-label classification models becomes difficult and heavily impacts the GNN's performance. To address these challenges, we propose a new data oversampling technique to improve multi-label classification performances on all the given imbalanced molecular graph data sets. Using the technique, we improve the data imbalance ratio of the drug effects better than before while protecting the data set's integrity. Finally, we evaluate multi-label classification performance using the best-performant hybrid GNN model on all the oversampled data sets obtained from the proposed oversampling technique. These results outperform those of other ML models including GNN models when they are trained on the original data sets or oversampled data sets using MLSMOTE (a well-known oversampling technique) in all evaluation metrics precision, recall, and F1 score by a significant margin.

Bose, Avishek [ORNL]↗

DOE OSTI2017

Graph-based optimization of epitope coverage for vaccine antigen design

Epigraph is a recently developed algorithm that enables the computationally efficient design of single or multi-antigen vaccines to maximize the potential epitope coverage for a diverse pathogen population. Potential epitopes are defined as short contiguous stretches of proteins, comparable in length to T-cell epitopes. This optimal coverage problem can be formulated in terms of a directed graph, with candidate antigens represented as paths that traverse this graph. Epigraph protein sequences can also be used as the basis for designing peptides for experimental evaluation of immune responses in natural infections to highly variable proteins. The epigraph tool suite also enables rapid characterization of populations of diverse sequences from an immunological perspective. Fundamental distance measures are based on immunologically relevant shared potential epitope frequencies, rather than simple Hamming or phylogenetic distances. Here, we provide a mathematical description of the epigraph algorithm, include a comparison of different heuristics that can be used when graphs are not acyclic, and we describe an additional tool we have added to the web-based epigraph tool suite that provides frequency summaries of all distinct potential epitopes in a population. Lastly, we also show examples of the graphical output and summary tables that can be generated using the epigraph tool suite and explain their content and applications.

60 APPLIED LIFE SCIENCES↗

DOE OSTI2025

The connection between the chromatic numbers of a hypergraph and its 1-intersection graph

A well known problem from an excellent book of Lovász states that any hypergraph with the property that no pair of hyperedges intersect in exactly one vertex can be properly 2-colored. Motivated by this as well as recent works of Keszegh and of Gyárfás et al. we study the 1-intersection graph of a hypergraph. The 1-intersection graph encodes those pairs of hyperedges in a hypergraph that intersect in exactly one vertex. We prove for k ϵ {2, 4} that all hypergraphs whose 1-intersection graph is k-partite can be properly k-colored.

1-intersection graph of hypergraphs↗

DOE OSTI2020

Online Event Detection in Synchrophasor Data with Graph Signal Processing

Online detection of anomalies is crucial to enhancing the reliability and resiliency of power systems. We propose a novel data-driven online event detection algorithm with synchrophasor data using graph signal processing. In addition to being extremely scalable, our proposed algorithm can accurately capture and leverage the spatio-temporal correlations of the streaming PMU data. This paper also develops a general technique to decouple spatial and temporal correlations in multiple time series. Finally, we develop a unique framework to construct a weighted adjacency matrix and graph Laplacian for product graph. Case studies with real-world, large-scale synchrophasor data demonstrate the scalability and accuracy of our proposed event detection algorithm. Compared to the state-of-the-art benchmark, the proposed method not only achieves higher detection accuracy but also yields higher computational efficiency.

Event detection↗

DOE OSTI2021

Learning Sequential Distribution System Restoration via Graph-Reinforcement Learning

We report a distribution service restoration algorithm as a fundamental resilient paradigm for system operators provides an optimally coordinated, resilient solution to enhance the restoration performance. The restoration problem is formulated to coordinate distribution generators and controllable switches optimally. A model-based control scheme is usually designed to solve this problem, relying on a precise model and resulting in low scalability. To tackle these limitations, this work proposes a graph-reinforcement learning framework for the restoration problem. We link the power system topology with a graph convolutional network, which captures the complex mechanism of network restoration in power networks and understands the mutual interactions among controllable devices. Latent features over graphical power networks produced by graph convolutional layers are exploited to learn the control policy for network restoration using deep reinforcement learning. The solution scalability is guaranteed by modeling distributed generators as agents in a multi-agent environment and a proper pre-training paradigm. Comparative studies on IEEE 123-node and 8500-node test systems demonstrate the performance of the proposed solution.

24 POWER TRANSMISSION AND DISTRIBUTION↗

DOE OSTI2022

Learning Latent Interactions for Event Identification via Graph Neural Networks and PMU Data

Phasor measurement units (PMUs) are being widely installed on power systems, providing a unique opportunity to enhance wide-area situational awareness. One essential application is the use of PMU data for real-time event identification. However, how to take full advantage of all PMU data in event identification is still an open problem. Thus, we propose a novel method that performs event identification by mining interaction graphs among different PMUs. The proposed interaction graph inference method follows an entirely data-driven manner without knowing the physical topology. Moreover, unlike previous works that treat interactive learning and event identification as two different stages, our method learns interactions jointly with the identification task, thereby improving the accuracy of graph learning and ensuring seamless integration between the two stages. Moreover, to capture multi-scale event patterns, a dilated inception-based method is investigated to perform feature extraction of PMU data. To test the proposed data-driven approach, a large real-world dataset from tens of PMU sources and the corresponding event logs have been utilized in this work. We report numerical results validate that our method has higher classification accuracy compared to previous methods.

24 POWER TRANSMISSION AND DISTRIBUTION↗

DOE OSTI2024

Improving Property Graph Layouts by Leveraging Attribute Similarity for Structurally Equivalent Nodes

Many real-world networks contain structurally-equivalent nodes. These are defined as vertices that share the same set of neighboring nodes, making them interchangeable with a traditional graph layout approach. However, many real-world graphs also have properties associated with nodes, adding additional meaning to them. We present an approach for swapping locations of structurally-equivalent nodes in graph layout so that those with more similar properties have closer proximity to each other. This improves the usefulness of the visualization from an attribute perspective without negatively impacting the visualization from a structural perspective. We include an algorithm for finding these sets of nodes in linear time, as well as methodologies for ordering nodes based on their attribute similarity, which works for scalar, ordinal, multidimensional, and categorical data.

graph drawing, network visualization, property gra↗

DOE OSTI2026

When does global attention help: a unified empirical study on atomistic graph learning

Graph neural networks (GNNs) are widely used as surrogates for costly experiments and first-principles simulations to study the behavior of compounds at atomistic scale, and their architectural complexity is constantly increasing to enable the modeling of complex physics. While most recent GNNs combine more traditional message passing neural networks (MPNNs) layers to model short-range interactions with more advanced graph transformers (GTs) with global attention mechanisms to model long-range interactions, it is still unclear when global attention mechanisms provide real benefits over well-tuned MPNN layers due to inconsistent implementations, features, or hyperparameter tuning. We introduce the first unified, reproducible benchmarking framework–built on HydraGNN–that enables seamless switching among four controlled model classes: MPNN, MPNN with chemistry/topology encoders, GPS-style hybrids of MPNN with global attention, and fully fused localglobal models with encoders. Using seven diverse open-source datasets for benchmarking across regression and classification tasks, we systematically isolate the contributions of message passing, global attention, and encoder-based feature augmentation. Our study shows that encoder-augmented MPNNs form a robust baseline, while fused localglobal models yield the clearest benefits for properties governed by long-range interaction effects. We further quantify the accuracycompute trade-offs of attention, reporting its overhead in memory. Together, these results establish the first controlled evaluation of global attention in atomistic graph learning and provide a reproducible testbed for future model development.

Equivariant graph neural networks↗

DOE OSTI2020

Online Event Detection in Synchrophasor Data with Graph Signal Processing

24 POWER TRANSMISSION AND DISTRIBUTION↗

DOE OSTI2017

APT malware static trace analysis through bigrams and graph edit distance

Research and business organizations are vulnerable to attack by malware, particularly advanced persistent threat malware tailored for a specific target. Malware identification is made more difficult because samples can be subtly altered to avoid detection by methods that check for an identical match to known code. Different versions of an original piece of malware form a malware family. And when new malicious software is identified, reverse engineers seek to identify its origin and purpose. Knowing whether new malware is from a known family or a previously unobserved family aids the efficiency of reverse engineers. Furthermore, this article presents a three-stage method to classify new malware into a family by comparing its similarity to existing static traces, and assigning it to the most similar family. First, a fast filtering method creates a shortlist of samples with some similarity to the new malware, using a simple bigram comparison of the instructions. The second stage takes the call graph view of the shortlisted static traces and uses simulated annealing to estimate the graph edit distance, a measure of dissimilarity between graphs. Finally, a random forest classifier combines the previous two results to predict the family to which a new sample belongs. Our paper also considers how to detect when malware is from a new family.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2018

The Local Limit of the Uniform Spanning Tree on Dense Graphs

Let G be a connected graph in which almost all vertices have linear degrees and let T be a uniform spanning tree of G. For any fixed rooted tree F of height r we compute the asymptotic density of vertices v for which the r-ball around v in T is isomorphic to F. We deduce from this that if {G_n} is a sequence of such graphs converging to a graphon W, then the uniform spanning tree of G{sub n} locally converges to a multi-type branching process defined in terms of W. As an application, we prove that in a graph with linear minimum degree, with high probability, the density of leaves in a uniform spanning tree is at least e{sup −1}−o(1), the density of vertices of degree 2 is at most e{sup −1}+o(1) and the density of vertices of degree k⩾3 is at most (((k−2){sup k−2})/((k−1)!e{sup k−2}))+o(1). These bounds are sharp.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗