Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “Graphs”

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 1,081 records · Page 60
All sourcesNASA NTRSDOE OSTI
DOE OSTI2023

Exploring temporal community evolution: algorithmic approaches and parallel optimization for dynamic community detection

Abstract Dynamic (temporal) graphs are a convenient mathematical abstraction for many practical complex systems including social contacts, business transactions, and computer communications. Community discovery is an extensively used graph analysis kernel with rich literature for static graphs. However, community discovery in a dynamic setting is challenging for two specific reasons. Firstly, the notion of temporal community lacks a widely accepted formalization, and only limited work exists on understanding how communities emerge over time. Secondly, the added temporal dimension along with the sheer size of modern graph data necessitates new scalable algorithms. In this paper, we investigate how communities evolve over time based on several graph metrics under a temporal formalization. We compare six different algorithmic approaches for dynamic community detection for their quality and runtime. We identify that a vertex-centric (local) optimization method works as efficiently as the classical modularity-based methods. To its advantage, such local computation allows for the efficient design of parallel algorithms without incurring a significant parallel overhead. Based on this insight, we design a shared-memory parallel algorithm DyComPar , which demonstrates between 4 and 18 fold speed-up on a multi-core machine with 20 threads, for several real-world and synthetic graphs from different domains.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2021

Retaining Systems Engineering Model Meaning Through Transformation: Demo 2

Digital engineering strategies typically assume that digital engineering models interoperate seamlessly across the multiple different engineering modeling software applications involved, such as model- based systems engineering (MBSE), mechanical computer-aided design (MCAD), electrical computer-aided design (ECAD), and other engineering modeling applications. The presumption is that the data schema in these modeling software applications are structured in the familiar flat- tabular schema like any other software application. Engineering domain-specific applications (e.g., systems, mechanical, electrical, simulation) are typically designed to solve domain-specific problems, necessarily excluding explicit representations of non-domain information to help the engineer focus on the domain problems (system definition, design, simulation). Such exclusions become problematic in inter-domain information exchange. The obvious assumptions of one domain might not be so obvious to experts in another domain. Ambiguity in domain-specific language can erode the ability to enable different domain modeling applications to interoperate, unless the underlying language is understood and used as the basis for translation from one application to another. The engineering modeling software application industry has struggled for decades to enable these applications to interoperate. Industry standards have been developed, but they have not unified the industry. Why is this? The authors assert that the industry has relied on traditional database integration methods. The basic issue prohibiting successful application integration then is that traditional database-driven integration does not consider the distinct languages of each domain. An engineering models meaning is expressed through the underlying language of that engineering domain. In essence, traditional integration methods do not retain the semantic context (meaning) of the model. The basis of this research stems from the widely held assumption that systems engineering models are (or can be) structured according to the underlying semantic ontology of the model. This assumption can be imagined from two thoughts. 1) Digital systems engineering models are often represented using graph theory (the graph of a complex systems model can contain millions of nodes and edges). When examining the nodes one at a time and following the outbound edges of each node one by one, one can end up with rudimentary statements about the model (i.e., node A relates to node B), as in a semantic graph. 2) Likewise, from the study of natural languages, a sentence can be structured into unambiguous triples of subject-predicate-object within formal and highly expressive semantic ontologies. The rudimentary statements about a systems model discerned with graph theory closely mimic the triples used in the ontologies that try to structure natural languages. In other words, a systems models semantic graph can be (or is) structured into an ontology. Additionally, it is well established in industry that through natural language processing (NLP), which provides the means to create language structures, that computers can interpret ontological graphs. Therefore, the authors hypothesized that if the integrity of the underlying semantic structure of a systems model is retained, the contextual meaning of the model is retained. By structuring system models into the triples of the underlying ontology during the transformation from one MBSE application to another, the authors have provided a proof of the concept that the meaning of a system model can be retained during transformation. The authors assert that this is the missing ingredient in effective systems model-to-model interoperability. ACKNOWLEDGEMENTS The authors would like to thank the FY19 Model Interoperability team members who provided a solid foundation for the FY20 team to leverage: John McCloud, for the work he did to guide us toward the right use of technology that will appropriately discover and manipulate ontologies. Carlos Tafoya, for the work he did to develop an application programming interface (API)/Adapter that would export ontology-based data from GENESYS. Peter Chandler, for the work he did to architect our overall integration solution, with an eye toward the future that would influence a large-scale federated production-level systems engineering digital model ecosystem.

42 ENGINEERING↗
DOE OSTI2024

LENS: Learning Enabled Network Synthesis

RTRC and UMD have developed novel machine learning based methods under the ARPA-E DIFFERENTIATE program for rapid acceleration of hypothesis generation in complex architecture design spaces involving both discrete choices of component inclusion and interconnection and continuous parametric decisions. The project named Learning Enabled Network Synthesis (LENS) further demonstrated the developed methods on challenging electrical power converter design problems by identifying the most suitable circuit topologies and simultaneously selecting the most appropriate components to achieve optimized design of power converter with improved performances. We demonstrated that LENS could enable exploration of very large design space of circuit topologies and components by addressing the limitations of conventional design process in non-linear, high switching speed, multi-dimensional power converter design and optimization. The key innovation developed in LENS is the seamless integration of statistical learning and logical reasoning techniques and building on the individual strengths of these techniques for rapid hypothesis discovery. The main component of LENS comprises of: 1) Graph Reasoning Engine (GRE) to enforce composition rules that rapidly reject all discrete architectures that are composed incorrectly and generates an adaptive database of feasible designs which can be used by ML modules, 2) Graph Generative Learning module which is a deep neural network based generative model for graph architectures which can enable design space exploration beyond the dataset generated by the GRE, 3) Graph Reduced Order Model (ROM) for graph domains for accelerating computation of output metrics, and 4) Active learning and Rule Discovery module for sample efficient learning and extracting logical rules from the learned ML models which will be integrated in the GRE to enhance the filtering effectiveness. LENS approach can be applied to any design domains where designs can be represented as multi-attribute graphs. The LENS team integrated the various technical innovations listed above into an optimization pipeline and exercised the optimization pipeline on the converter design problem. The LENS project demonstrated that the developed AI/ML technologies can be used to generate novel converter circuits >45x faster than experts on chosen use-cases. This can enable faster design space exploration and identification of new designs which are not considered by experts due to the increasing design space complexity. This has significant potential impact on the public and energy needs of the country. It is currently estimated that 30% of all electrical powers generated passes through power converters. The future estimate is that 80% of all power generated would be passing through converters. LENS fills a critical gap in this space since by accelerating the design process the designers would be able to generate more efficient converters which can lead to significant energy savings for the country.

42 ENGINEERING↗
NASA NTRS1989

Multiprocessor performance modeling with ADAS

A graph managing strategy referred to as the Algorithm to Architecture Mapping Model (ATAMM) appears useful for the time-optimized execution of application algorithm graphs in embedded multiprocessors and for the performance prediction of graph designs. This paper reports the modeling of ATAMM in the Architecture Design and Assessment System (ADAS) to make an independent verification of ATAMM's performance prediction capability and to provide a user framework for the evaluation of arbitrary algorithm graphs. Following an overview of ATAMM and its major functional rules are descriptions of the ADAS model of ATAMM, methods to enter an arbitrary graph into the model, and techniques to analyze the simulation results. The performance of a 7-node graph example is evaluated using the ADAS model and verifies the ATAMM concept by substantiating previously published performance results.

Hayes, Paul J.↗
NASA NTRS1993

Process and representation in graphical displays

Our initial model of graphic comprehension has focused on statistical graphs. Like other models of human-computer interaction, models of graphical comprehension can be used by human-computer interface designers and developers to create interfaces that present information in an efficient and usable manner. Our investigation of graph comprehension addresses two primary questions: how do people represent the information contained in a data graph?; and how do they process information from the graph? The topics of focus for graphic representation concern the features into which people decompose a graph and the representations of the graph in memory. The issue of processing can be further analyzed as two questions: what overall processing strategies do people use?; and what are the specific processing skills required?

Gillan, Douglas J.↗
NASA NTRSDate not supplied

Contact Multigraph Routing: Overview and Implementation

In Delay Tolerant Networking (DTN), the standard routing algorithm used to navigate time-varying networks has been Contact Graph Routing (CGR). In CGR, a globally distributed list of contacts, periods during which two DTN nodes may communicate, is used to construct a contact graph, in which contacts are vertices. A version of Dijkstra’s algorithm can then be used to find paths through this model of the timevarying network. However, since contact graphs may be large compared to the network, potentially growing with the square of the number of network nodes and linearly with the time interval represented, the resulting algorithm does not scale well with the size of the network or time. Any improvement to the routing algorithm will bring significant returns to scale. In a previous paper, we briefly introduced an alternative to the contact graph model for routing. This alternative model is based on a multigraph (a graph in which there may be multiple edges between a pair of vertices) where vertices represent network nodes instead of contacts. A version of Dijkstra’s algorithm in these multigraph models reduces the time needed to perform the same routing computations done in the existing CGR algorithm. Moreover, a modified version of Yen’s algorithm for multigraphs is included. Our variation of CGR, which we call Contact Multigraph Routing (CMR), provides an in-line replacement for the previously used pathfinding algorithms. This paper describes an implementation created based on the CMR approach, and experimental comparisons to traditional CGR are given. In addition, we explore some additional modifications to the routing pipeline traditionally assumed in CGR. These modifications range from the theoretical to the practical in terms of size and scope. We step forward our understanding of sheaftheoretic networking and describe how to model the routing pipeline using sheaves. We detail some enhanced route selection criteria that addresses some of the added complexity of DTNbased systems. We also include a future works section on future improvements and implementations that would be of service to the broader DTN community.

contact graph routing↗
DOE OSTI2022

Towards scaling community detection on distributed-memory heterogeneous systems

Distributed multi-GPU systems pose significant challenges and opportunities for efficient execution of parallel applications. Graph algorithms are generally characterized by irregular memory accesses, low computation to communication ratios, and load balancing problems that are especially hard to address on multi-GPU systems. Graph community detection is an important problem in the emerging domain of graph analytics with numerous applications. In this paper, we present our ongoing work on distributed-memory multi-GPU implementation for graph community detection. Our work parallelizes the widely used (albeit serial) Louvain method on distributed multi-GPU platforms. Supported by an extensive set of experiments on a multi-GPU enabled supercomputer (OLCF Summit) and a single compute node (Nvidia DGX-2®), we demonstrate competitive performance to existing distributed-memory CPU-based implementation, and up to 6.5 better results than Nvidia RAPIDS® CUGRAPH. To the best of our knowledge, this work represents the first effort for community detection on distributed multi-GPU systems. Our approach and related findings can be extended to numerous other iterative graph algorithms on multi-GPU systems.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2021

Deep Learning Coordinate-Free Quantum Chemistry

Computing quantum chemical properties of small molecules and polymers can provide insights valuable to physicists, chemists and biologists when designing new materials, catalysts, biological probes and drugs. Deep learning can compute quantum chemical properties accurately in a fraction of the time required by commonly used methods such as density functional theory (DFT). However, many of these deep learning architectures require energy minimized molecular geometries as input, which is also computationally expensive, and decreasing the reproducibility and throughput of these methods. In this study, we demonstrate that accurate quantum chemical computations can be performed without optimized geometries by operating in the coordinate-free domain using deep learning on graph encodings. Furthermore, we also find that the choice of graph-encoding architecture substantially affects the performance of these methods. The Wave architecture outperforms graph convolution architectures, particularly on complex molecules. Furthermore, the structures of these graph encoding architectures provide an opportunity to probe an important, outstanding question in quantum mechanics: What types of quantum chemical properties can be represented by local-variable models? We find that Wave, a local-variable model, is more accurately calculates quantum chemical properties. Graph convolutional architectures require global variables, and are not as effective as as Wave. We anticipate that coordinate-free, deep-learning models of quantum chemistry will become valuable tools in chemistry and biology, enabling researchers to rapidly screen chemical databases or identify new molecules using automated, de-novo design algorithms.

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

Wave function analysis with a maximum flow algorithm

An efficient algorithm for computing the maximum-flow path in a network is applied to the identification of the dominant configuration state functions (CSFs) in a graphically contracted function (GCF), configuration interaction, wave function. The flow network is a space of spin-adapted CSFs represented by a Shavitt graph, wherein the nodes correspond to orbital occupations and spin quantum numbers. The graph nodes are connected by arcs, and an arc density is defined as sums of the associated squared CSF coefficients. A max-min approach determines an upper bound to the maximum possible incoming flow for each graph node. A backtracking step generates a candidate walk and is followed by a limited search of alternative branching paths for the dominant CSF. The arc density contributions are removed from the graph, and the algorithm is reapplied to the updated graph. This list of generated walks can be partitioned in order to guarantee that the dominant CSFs have been identified. All of the steps in this algorithm are computationally efficient and do not depend on the potentially large dimension of the underlying linear CSF expansion space. An analysis of low-lying valence states of C-2 illustrates the method.

74 ATOMIC AND MOLECULAR PHYSICS↗
DOE OSTI2020

Fibers add flavor. Part II. 5d SCFTs, gauge theories, and dualities

In [1, 2] we proposed an approach based on graphs to characterize 5d superconformal field theories (SCFTs), which arise as compactifications of 6d $$ \mathcal{N} $$ N = (1 , 0) SCFTs. The graphs, so-called combined fiber diagrams (CFDs), are derived using the realization of 5d SCFTs via M-theory on a non-compact Calabi-Yau threefold with a canonical singularity. In this paper we complement this geometric approach by connecting the CFD of an SCFT to its weakly coupled gauge theory or quiver descriptions and demonstrate that the CFD as recovered from the gauge theory approach is consistent with that as determined by geometry. To each quiver description we also associate a graph, and the embedding of this graph into the CFD that is associated to an SCFT provides a systematic way to enumerate all possible consistent weakly coupled gauge theory descriptions of this SCFT. Furthermore, different embeddings of gauge theory graphs into a fixed CFD can give rise to new UV-dualities for which we provide evidence through an analysis of the prepotential, and which, for some examples, we substantiate by constructing the M-theory geometry in which the dual quiver descriptions are manifest.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2025

Hidden zeros of the cosmological wavefunction

Motivated by the recent discovery of hidden zeros in particle and string amplitudes, we characterize zeros of individual graph contributions to the cosmological wavefunction of a scalar field theory. We demonstrate that these contributions factorize near these zeros for all tree graphs and provide evidence that this extends to loop graphs as well. We explicitly construct polytopal realizations of the relevant graph associahedra and show that the cosmological zeros have natural geometric and physical interpretations. As a byproduct, we establish an equivalence between the wavefunction coefficients of chain graphs and flat-space Tr(ϕ 3 ) amplitudes, enabling us to leverage the cosmological zeros to uncover the recently discovered hidden zeros of colored amplitudes.

Cosmological models↗
DOE OSTI2022

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

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

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2023

Stream Temperature Prediction in a Shifting Environment: Explaining the Influence of Deep Learning Architecture

Stream temperature is a fundamental control on ecosystem health. Recent efforts incorporating process guidance into deep learning models for predicting stream temperature have been shown to outperform existing statistical and physical models. This performance is in part because deep learning architectures can actively learn spatiotemporal relationships that govern how water and energy propagate through a river network. However, exploration of how spatiotemporal awareness and process guidance influence a model's generalizability under shifting environmental conditions such as climate change is limited. Here, we use Explainable Artificial Intelligence (XAI) to interrogate how differing deep learning architectures affect a model's learned spatial and temporal dependencies, and how those learned dependencies affect a model's ability to maintain high accuracy when applied to unseen environmental conditions. Using the Delaware River Basin in the northeastern United States as a test case, we compare two spatiotemporally aware process–guided deep learning models for predicting stream temperature (a recurrent graph convolution network—RGCN, and a temporal convolution graph model—Graph WaveNet). Both models achieve equally high predictive performance when testing data are well represented in the training data (test root mean squared errors of 1.64°C and 1.65°C); however, Graph WaveNet significantly outperforms RGCN in 4 out of 5 experiments where test partitions represent different types of unseen environmental conditions. XAI results show that the architecture of Graph WaveNet leads to learned spatial relationships with greater fidelity to physical processes, and that this fidelity improves the generalizability of the model when applied to shifting and/or unseen environmental conditions.

54 ENVIRONMENTAL SCIENCES↗
DOE OSTI2023

Sampling frequency thresholds for the quantum advantage of the quantum approximate optimization algorithm

We compare the performance of the Quantum Approximate Optimization Algorithm (QAOA) with state-of-the-art classical solvers Gurobi and MQLib to solve the MaxCut problem on 3-regular graphs. We identify the minimum noiseless sampling frequency and depth p required for a quantum device to outperform classical algorithms. There is potential for quantum advantage on hundreds of qubits and moderate depth with a sampling frequency of 10 kHz. We observe, however, that classical heuristic solvers are capable of producing high-quality approximate solutions in linear time complexity. In order to match this quality for large graph sizes N, a quantum device must support depth p > 11. Additionally, multi-shot QAOA is not efficient on large graphs, indicating that QAOA p ≤ 11 does not scale with N. These results limit achieving quantum advantage for QAOA MaxCut on 3-regular graphs. Other problems, such as different graphs, weighted MaxCut, and 3-SAT, may be better suited for achieving quantum advantage on near-term quantum devices.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2021

Efficient Sampling of Complex Interdependent and Multiplex Networks

Efficient sampling of interdependent and multiplex infrastructure networks is critical for effectively applying failure and recovery algorithms in real-world settings, as well as to generate property-preserving reduced-order graph-based ensembles that address topological uncertainties. In this paper, we first explore the performance, i.e. the success in preserving graph properties, of graph sampling algorithms for interdependent and multiplex networks with synthetic and real-world graphs. We simulate sampling algorithms under different parameter settings. These settings include probabilistic graph generators, coupling patterns, and various performance metrics. Our results show that while Random Node and Random Walk sampling algorithms perform best for interdependent networks, Random Edge and Forest Fire sampling algorithms perform best for multiplex networks. Second, we propose and implement a novel similarity-based sampling algorithm for multiplex networks that samples only log(N) number of layers of an N-layer multiplex network while yielding computational savings with performance guarantees. Experimental results show that similarity sampling outperforms complete sampling of all layers while decreasing performance costs from a linear scale to a logarithmic one. Our results also indicate that similarity-based sampling outperforms complete sampling and random selection in nearly all scenarios when tested with real-world data.

Subasi, Omer↗
DOE OSTI2023

Evaluating Robust Entanglement on a Trapped Ion Platform

We present proof of principle results for evaluating an entanglement volumetric benchmark [1] on trapped ion platforms. The benchmark quantifies the robustness of multipartite and bipartite entanglement using stabilizer measurements and witness functions. Each n-qubit graph state is prepared and used to evaluate n state-specific stabilizer strings. These stabilizer measurements are used to evaluate entanglement witness functions. The entanglement benchmark defines families of graph states associated with an initial sub-graph of the hardware qubit connectivity - with all-to-all connectivity, trapped ion systems provide a flexibility in the choice of this initial graph, and this will affect the associated family. In this work, we present results targeting several classes of entangled states: 1) 1-D cluster states, 2) n-qubit GHZ states, and 3) cycle graph states. These states have been found in the literature as standard hardware benchmarks, and have connections to many near-term applications.

Hamilton, Kathleen↗
DOE OSTI2024

Red-QAOA: Efficient Variational Optimization through Circuit Reduction

The Quantum Approximate Optimization Algorithm (QAOA) provides a quantum solution for combinatorial optimization problems. However, the optimal parameter searching process of QAOA is greatly affected by noise, leading to non-optimal solutions. This paper introduces a novel approach to optimize QAOA by exploiting the energy landscape concentration of similar instances via graph reduction, thus addressing the effect of noise. We formalize the notion of similar instances in QAOA and develop a Simulated Annealing-based graph reduction algorithm, called Red-QAOA, to identify the most similar subgraph for efficient parameter optimization. Red-QAOA outperforms state-of-the-art Graph Neural Network (GNN) based graph pooling techniques in performance and demonstrates effectiveness on a diverse set of real-world optimization problems encompassing 3200 graphs. Red-QAOA reduced the node counts and edge counts by 28% and 37%, respectively, while maintaining a low mean square error of 2%. These enable the identification of an optimal parameter set that is closer to the ideal true optimal solution in the presence of noise. By substantially streamlining the search for QAOA parameters, our approach sets the stage for the practical application of quantum algorithms in solving complex optimization problems.

Wang, Meng↗
DOE OSTI2025

ScaWL: Scaling k-WL (Weisfeiler-Lehman) Algorithms in Memory and Performance on Shared and Distributed-Memory Systems

The k-dimensional Weisfeiler-Lehman (k-WL) algorithm—developed as an efficient heuristic for testing if two graphs are isomorphic—is a fundamental kernel for node embedding in the emerging field of graph neural networks. Unfortunately, the k-WL algorithm has exponential storage requirements, limiting the size of graphs that can be handled. This work presents a novel k-WL scheme with a storage requirement orders of magnitude lower while maintaining the same accuracy as the original k-WL algorithm. Due to the reduced storage requirement, our scheme allows for processing much bigger graphs than previously possible on a single compute node. For even bigger graphs, we provide the first distributed-memory implementation. Our k-WL scheme also has significantly reduced communication volume and offers high scalability. Our experimental results demonstrate that our approach is significantly faster and has superior scalability compared to five other implementations employing state-of-the-art techniques.

algorithims↗