Search NASA⌕ Search

SEARCH · Search NASA

Results for “graph problems”

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 181 records · Page 10
All sourcesNASA NTRSDOE OSTI
DOE OSTI2024

Generating Euler Diagrams Through Combinatorial Optimization

Abstract Can a given set system be drawn as an Euler diagram? We present the first method that correctly decides this question for arbitrary set systems if the Euler diagram is required to represent each set with a single connected region. If the answer is yes, our method constructs an Euler diagram. If the answer is no, our method yields an Euler diagram for a simplified version of the set system, where a minimum number of set elements have been removed. Further, we integrate known wellformedness criteria for Euler diagrams as additional optimization objectives into our method. Our focus lies on the computation of a planar graph that is embedded in the plane to serve as the dual graph of the Euler diagram. Since even a basic version of this problem is known to be NP‐hard, we choose an approach based on integer linear programming (ILP), which allows us to compute optimal solutions with existing mathematical solvers. For this, we draw upon previous research on computing planar supports of hypergraphs and adapt existing ILP building blocks for contiguity‐constrained spatial unit allocation and the maximum planar subgraph problem. To generate Euler diagrams for large set systems, for which the proposed simplification through element removal becomes indispensable, we also present an efficient heuristic. We report on experiments with data from MovieDB and Twitter. Over all examples, including 850 non‐trivial instances, our exact optimization method failed only for one set system to find a solution without removing a set element. However, with the removal of only a few set elements, the Euler diagrams can be substantially improved with respect to our wellformedness criteria.

Computer Science↗
DOE OSTI2023

Code for Value Decomposition Graph Network and environment for AMR on linear advection

This is the code for the paper [Multi-Agent Reinforcement Learning for Adaptive Mesh Refinement](https://arxiv.org/abs/2211.00801), published at AAMAS 2023. It contains the implementation of a new algorithm, called Value Decomposition Graph Network (VDGN), for applying multi-agent reinforcement learning to the problem of adaptive mesh refinement (AMR). It also contains the implementation of a multi-agent environment for AMR on a linear advection problem. VDGN is the first learning algorithm to display anticipatory refinement behavior in AMR, and it outperforms local error threshold-based heuristic strategies.

Yang, Jiachen↗
DOE OSTI2021

Simplifying and Visualizing the Ontology of Systems Engineering Models

The credibility of an engineering model is of critical importance in large-scale projects. How concerned should an engineer be when reusing someone else's model when they may not know the author or be familiar with the tools that were used to create it? In this report, the authors advance engineers' capabilities for assessing models through examination of the underlying semantic structure of a model--the ontology. This ontology defines the objects in a model, types of objects, and relationships between them. In this study, two advances in ontology simplification and visualization are discussed and are demonstrated on two systems engineering models. These advances are critical steps toward enabling engineering models to interoperate, as well as assessing models for credibility. For example, results of this research show an 80% reduction in file size and representation size, dramatically improving the throughput of graph algorithms applied to the analysis of these models. Finally, four future problems are outlined in ontology research toward establishing credible models--ontology discovery, ontology matching, ontology alignment, and model assessment.

42 ENGINEERING↗
DOE OSTI2024

Addressing GPU memory limitations for Graph Neural Networks in High-Energy Physics applications

Introduction Reconstructing low-level particle tracks in neutrino physics can address some of the most fundamental questions about the universe. However, processing petabytes of raw data using deep learning techniques poses a challenging problem in the field of High Energy Physics (HEP). In the Exa.TrkX Project, an illustrative HEP application, preprocessed simulation data is fed into a state-of-art Graph Neural Network (GNN) model, accelerated by GPUs. However, limited GPU memory often leads to Out-of-Memory (OOM) exceptions during training, due to the large size of models and datasets. This problem is exacerbated when deploying models on High-Performance Computing (HPC) systems designed for large-scale applications. Methods We observe a high workload imbalance issue during GNN model training caused by the irregular sizes of input graph samples in HEP datasets, contributing to OOM exceptions. We aim to scale GNNs on HPC systems, by prioritizing workload balance in graph inputs while maintaining model accuracy. Our paper introduces diverse balancing strategies aimed at decreasing the maximum GPU memory footprint and avoiding the OOM exception, across various datasets. Results Our experiments showcase memory reduction of up to 32.14% compared to the baseline. We also demonstrate the proposed strategies can avoid OOM in application. Additionally, we create a distributed multi-GPU implementation using these samplers to demonstrate the scalability of these techniques on the HEP dataset. Discussion By assessing the performance of these strategies as data loading samplers across multiple datasets, we can gauge their effectiveness in both single-GPU and distributed environments. Our experiments, conducted on datasets of varying sizes and across multiple GPUs, broaden the applicability of our work to various GNN applications that handle input datasets with irregular graph sizes.

Lee, Claire Songhyun↗
DOE OSTI2025

Increasing the hardness of posiform planting using random QUBOs for programmable quantum annealer benchmarking

Posiform planting is a method for constructing QUBO instances with a unique planted solution that can be tailored to arbitrary connectivity graphs. In this study we investigate making posiform planted QUBOs computationally harder by fusing many smaller random Ising models, whose global minimum is computed classically, with posiform planted QUBOs. The unique ground state of the resulting QUBO is the concatenation of (exactly one of) the ground states of each smaller problem. Our method generates QUBO instances that have a unique solution, are native to the hardware graph, and have tunable computational hardness. We use our QUBOs to benchmark three D-Wave quantum annealing processors (with 563–5627 qubits), and compare them against simulated annealing and Gurobi. Surprisingly, we find that the D-Wave ground state sampling success rate is not dependent on the glued random QUBO size, and that some QUBO classes are solved at high success rates at short annealing times on the Zephyr processors.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
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 OSTI2021

GEDet: Detecting Erroneous Nodes with A Few Examples

Detecting nodes with erroneous values in real-world graphs re- mains challenging due to the lack of examples and various error scenarios. We demonstrate GEDet, an error detection engine that can detect erroneous nodes in graphs with a few examples. The GEDet framework tackles error detection as a few-shot node classification problem. We invite the attendees to experience the following unique features. (1) Few-shot detection. Users only need to provide a few examples of erroneous nodes to perform error detection with GEDet. GEDet achieves desirable accuracy with (a) a graph augmentation module, which automatically generates synthetic examples to learn the classifier, and (b) an adversarial detection module, which improves classifiers to better distinguish erroneous nodes from both cleaned nodes and synthetic examples. We show that GEDet significantly improves the state-of-the-art error detection methods. (2) Diverse error scenarios. GEDet profiles data errors with a built-in library of transformation functions from correct values to errors. Users can also easily “plug in” new error types or examples. (3) User-centric detection. GEDet supports (a) an active learning mode to engage users to verify detected results, and adapts the error detection process accordingly; and (b) visual interfaces to interpret and track detected errors.

Guan, Sheng↗
DOE OSTI2023

Protection Against Graph-Based False Data Injection Attacks on Power Systems

Graph signal processing (GSP) has emerged as a powerful tool for practical network applications, including power system monitoring. By representing power system voltages as smooth graph signals, recent research has focused on developing GSP-based methods for state estimation, attack detection, and topology identification. Included, efficient methods have been developed for detecting false data injection (FDI) attacks, which until now were perceived as non-smooth with respect to the graph Laplacian matrix. Consequently, these methods may not be effective against smooth FDI attacks. In this paper, we propose a graph FDI (GFDI) attack that minimizes the Laplacian-based graph total variation (TV) under practical constraints. In addition, we develop a low-complexity algorithm that solves the non-convex GDFI attack optimization problem using ell_1-norm relaxation, the projected gradient descent (PGD) algorithm, and the alternating direction method of multipliers (ADMM). We then propose a protection scheme that identifies the minimal set of measurements necessary to constrain the GFDI output to high graph TV, thereby enabling its detection by existing GSP-based detectors. Our numerical simulations on the IEEE-57 bus test case reveal the potential threat posed by well-designed GSP-based FDI attacks. Moreover, we demonstrate that integrating the proposed protection design with GSP-based detection can lead to significant hardware cost savings compared to previous designs of protection methods against FDI attacks.

Morgenstern, Gal↗
DOE OSTI2023

Prepare Ground States of Highly Frustrated Magnetic Clusters on Quantum Computers

Solving challenging problems in physical, chemical, and materials sciences is one of the most promising applications of quantum utility that can be realized on current noisy hardware, considering (i) the direct map (encoding) from the quantum particles and their interactions to the qubits and their entangling gates and (ii) the rapidly improved quantum hardware and advanced error-mitigation techniques. Understanding quantum spin liquid in frustrated magnetic materials is a longstanding challenge in condensed matter physics and the nature of the ground-state phases is highly debated among researchers. Using IBM quantum computers with superconducting qubits, we implemented a variational quantum eigensolver (VQE) algorithm to prepare the ground states of two 12-site cluster approximations of these highly frustrated magnetic materials. The interaction graphs of the two corresponding Hamiltonians are (a) the six-pointed star graph (a unit cell of the kagome lattice) and (b) the cuboctahedral graph (the kagome on a sphere). These are also two instances of Quantum Max Cut problem. With the VQE based on the Hamiltonian variational ansatz acting on a valence bond solid initial trial state, we prepared the ground states and obtained the exact ground energy on simulator and high accuracy on noisy hardware. The deep ansatz necessary to reach the ground state of the cuboctahedral graph indicates that it is a hard instance of Quantum Max Cut.

Wang, Yan↗
DOE OSTI2021

From Anderson localization on random regular graphs to many-body localization

Highlights: • Anderson transition from ergodicity to localization on random regular graphs (RRG). • Analytical, pool method, and exact-diagonalization study of correlations on RRG. • Many-body localization (MBL) to ergodicity transition: quantum dots and spin chains. • Dynamical eigenstate correlation functions in RRG and MBL problems. • Anderson localization on RRG as a toy model for MBL. The article reviews the physics of Anderson localization on random regular graphs (RRG) and its connections to many-body localization (MBL) in disordered interacting systems. Properties of eigenstate and energy level correlations in delocalized and localized phases, as well at criticality, are discussed. In the many-body part, models with short-range and power-law interactions are considered, as well as the quantum-dot model representing the limit of the “most long-range” interaction. Central themes – which are common to the RRG and MBL problems – include ergodicity of the delocalized phase, localized character of the critical point, strong finite-size effects, and fractal scaling of eigenstate correlations in the localized phase.

36 MATERIALS SCIENCE↗
DOE OSTI2023

Defect graph neural networks for materials discovery in high-temperature clean-energy applications

We present a graph neural network approach that fully automates the prediction of defect formation enthalpies for any crystallographic site from the ideal crystal structure, without the need to create defected atomic structure models as input. Here we used density functional theory reference data for vacancy defects in oxides, to train a defect graph neural network (dGNN) model that replaces the density functional theory supercell relaxations otherwise required for each symmetrically unique crystal site. Interfaced with thermodynamic calculations of reduction entropies and associated free energies, the dGNN model is applied to the screening of oxides in the Materials Project database, connecting the zero-kelvin defect enthalpies to high-temperature process conditions relevant for solar thermochemical hydrogen production and other energy applications. The dGNN approach is applicable to arbitrary structures with an accuracy limited principally by the amount and diversity of the training data, and it is generalizable to other defect types and advanced graph convolution architectures. In conclusion, it will help to tackle future materials discovery problems in clean energy and beyond.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2021

Theoretically and practically efficient parallel nucleus decomposition

This paper studies the nucleus decomposition problem, which has been shown to be useful in finding dense substructures in graphs. We present a novel parallel algorithm that is efficient both in theory and in practice. Our algorithm achieves a work complexity matching the best sequential algorithm while also having low depth (parallel running time), which significantly improves upon the only existing parallel nucleus decomposition algorithm (Sariyüce et al. , PVLDB 2018). The key to the theoretical efficiency of our algorithm is a new lemma that bounds the amount of work done when peeling cliques from the graph, combined with the use of a theoretically-efficient parallel algorithms for clique listing and bucketing. We introduce several new practical optimizations, including a new multi-level hash table structure to store information on cliques space-efficiently and a technique for traversing this structure cache-efficiently. On a 30-core machine with two-way hyper-threading on real-world graphs, we achieve up to a 55x speedup over the state-of-the-art parallel nucleus decomposition algorithm by Sariyüce et al. , and up to a 40x self-relative parallel speedup. We are able to efficiently compute larger nucleus decompositions than prior work on several million-scale graphs for the first time.

Computer Science↗
DOE OSTI2024

Multilevel well modeling in aggregation-based nonlinear multigrid for multiphase flow in porous media

A full approximation scheme (FAS) nonlinear multigrid solver for two-phase flow and transport problems driven by wells with multiple perforations is developed here. It is an extension to our previous work on FAS solvers for diffusion and transport problems. The solver is applicable to discrete problems defined on unstructured grids as the coarsening algorithm is aggregation-based and algebraic. To construct coarse basis that can better capture the radial flow near wells, coarse grids in which perforated well cells are not near the coarse-element interface are desired. This is achieved by an aggregation algorithm proposed in this paper that makes use of the location of well cells in the cell-connectivity graph. Numerical examples in which the FAS solver is compared against Newton's method on benchmark problems are given. In particular, for a refined version of the SAIGUP model, the FAS solver is at least 35% faster than Newton's method for time steps with a CFL number greater than 10.

58 GEOSCIENCES↗
DOE OSTI2022

Tweezer-programmable 2D quantum walks in a Hubbard-regime lattice

Quantum walks provide a framework for designing quantum algorithms that is both intuitive and universal. To leverage the computational power of these walks, it is important to be able to programmably modify the graph a walker traverses while maintaining coherence. We do this by combining the fast, programmable control provided by optical tweezers with the scalable, homogeneous environment of an optical lattice. With these tools we study continuous-time quantum walks of single atoms on a square lattice and perform proof-of-principle demonstrations of spatial search with these walks. When scaled to more particles, the capabilities demonstrated can be extended to study a variety of problems in quantum information science, including performing more effective versions of spatial search using a larger graph with increased connectivity.

Science & Technology - Other Topics↗
DOE OSTI2021

Neuromorphic Graph Algorithms: Cycle Detection, Odd Cycle Detection, and Max Flow

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. Spiking neural networks are the traditional use case for neuromorphic systems, and have proven to be highly effective at machine learning tasks such as control problems. More recently, neuromorphic systems have been applied outside of the arena of machine learning, primarily in the field of graph algorithms. Neuromorphic systems have been shown to perform graph algorithms faster and with lower power consumption than their traditional (GPU/CPU) counterparts, and are hence an attractive option for a co-processing unit in future high performance computing systems, where graph algorithms play a critical role. In this paper, we present a neuromorphic implementation of cycle detection, odd cycle detection, and the Ford-Fulkerson max-flow algorithm. We further evaluate the performance of these implementations using the NEST neuromorphic simulator by using spike counts and simulation time as proxies for energy consumption and run time. In addition to gains inherent in neuromorphic systems, we show that within the neuromorphic implementations early stopping criteria can be implemented to further improve performance.

Kay, Bill↗
DOE OSTI2021

FL-DISCO: Federated Generative Adversarial Network for Graph-based Molecule Drug Discovery: Special Session Paper

The outbreak of the global COVID-19 pandemic emphasizes the importance of collaborative drug discovery for high effectiveness; however, due to the stringent data regulation, data privacy becomes an imminent issue needing to be addressed to enable collaborative drug discovery. In addition to the data privacy issue, the efficiency of drug discovery is another key objective since infectious diseases spread exponentially and effectively conducting drug discovery could save lives. Advanced Artificial Intelligence (AI) techniques are promising to solve these problems: (1) Federated Learning (FL) is born to keep data privacy while learning data from distributed clients; (2) graph neural network (GNN) can extract structural properties of molecules whose underlying architecture is the connected atoms; and (3) generative adversarial network (GAN) can generate novel molecules while retaining the properties learned from the training data. In this work, we make the first attempt to build a holistic collaborative and privacy-preserving FL framework, namely FL- DISCO, which integrates GAN and GNN to generate molecular graphs. Experimental results demonstrate the effectiveness of FL- DISCO on: (1) IID data for ESOL and QM9, where FL-DISCO can generate highly novel compounds with high drug-likeliness, uniqueness and LogP scores compared to the baseline; (2) non- IID data for ESOL and QM9, where FL-DISCO generates 100% novel compounds with high validity and LogP scores compared to the baseline. We also demonstrate how different fractions of clients, generator and discriminator architectures affect our evaluation scores.

Manu, Daniel↗
DOE OSTI2025

Boosting efficiency and reducing graph reliance: Basis adaptation integration in Bayesian multi-fidelity networks

The computational cost of high-fidelity numerical models makes outer-loop analysis, which requires repeated interrogation of the model such as uncertainty quantification, computationally demanding. Multi-fidelity methods, which construct a surrogate model using data from an ensemble of models of varying cost and accuracy, can substantially reduce the cost of outer-loop analysis. However, these methods can be difficult to apply when the model ensemble does not admit a clear hierarchy a priori and the correlations between models are low. Consequently, in this paper, we present a multi-fidelity method that leverages dimension reduction to enhance the correlation between models, thereby reducing the amount of data needed to train a surrogate from an unordered ensemble of models. Our method utilizes basis adaptation to build low-dimensional polynomial chaos expansions of each model and employs Multi-fidelity Networks to encode the relationships among models. We show that the resulting method exhibit two notable advantages over its counterpart: (1) enhanced accuracy (both reduced bias and variance); and (2) reduced dependency on the graph structure encoding relationships among models. We demonstrate the approach on an analytical test problem and a challenging finite element model for a spent nuclear fuel. Our method produces a surrogate model that is significantly more accurate than either a single-fidelity surrogate or a multi-fidelity surrogate constructed without basis adaptation.

42 ENGINEERING↗
DOE OSTI2020

Using modularity to segment binary code

We consider the problem of recovering program structure from compiled binary code. We first extract the call graph and layout of functions in memory from the compiled code and represent this information in a graphical format. We then employ Louvain's modularity algorithm to identify clusters of functions that are considered to be related. We find that the quality and properties of clusters extracted by our technique are greatly impacted by the relative importance we assign to the call graph and the ordering of functions in memory.

97 MATHEMATICS AND COMPUTING↗