Engineering Papers⌕ Search

SEARCH · Engineering Papers

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.

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

At least 361 records · Page 20

Poisson Brackets Symmetry from the Pentagon-Wheel Cocycle in the Graph Complex

Kontsevich designed a scheme to generate infinitesimal symmetries P-dot =Q(P) of Poisson brackets P on all affine manifolds M{sup r}; every such deformation is encoded by oriented graphs on n+2 vertices and 2n edges. In particular, these symmetries can be obtained by orienting sums of non-oriented graphs γ on n vertices and 2n−2 edges. The bi-vector flow P-dot =O r-vector (γ)(P) preserves the space of Poisson structures if γ is a cocycle with respect to the vertex-expanding differential d in the graph complex. A class of such cocycles γ{sub 2ℓ+1} is known to exist: marked by ℓ∈N, each of them contains a (2ℓ+1) -gon wheel with a nonzero coefficient. At ℓ=1 the tetrahedron γ{sub 3} itself is a cocycle; at ℓ=2 the Kontsevich–Willwacher pentagon-wheel cocycle γ{sub 5} consists of two graphs. We reconstruct the symmetry Q{sub 5}(P)=O r-vector (γ{sub 5})(P) and verify that Q{sub 5} is a Poisson cocycle indeed: [ [P,Q{sub 5}(P)] ]≐0 via [ [P,P] ]=0.

72 PHYSICS OF ELEMENTARY PARTICLES AND FIELDS↗

Spectral Upscaling for Graph Laplacian Problems with Application to Reservoir Simulation

Here, we consider coarsening procedures for graph Laplacian problems written in a mixed saddle-point form. In that form, in addition to the original (vertex) degrees of freedom (dofs), we also have edge degrees of freedom. We extend previously developed aggregation-based coarsening procedures applied to both sets of dofs to now allow more than one coarse vertex dof per aggregate. Those dofs are selected as certain eigenvectors of local graph Laplacians associated with each aggregate. Additionally, we coarsen the edge dofs by using traces of the discrete gradients of the already constructed coarse vertex dofs. These traces are defined on the interface edges that connect any two adjacent aggregates. The overall procedure is a modification of the spectral upscaling procedure developed in for the mixed finite element discretization of diffusion type PDEs which has the important property of maintaining inf-sup stability on coarse levels and having provable approximation properties. We consider applications to partitioning a general graph and to a finite volume discretization interpreted as a graph Laplacian, developing consistent and accurate coarse-scale models of a fine-scale problem.

58 GEOSCIENCES↗

Graph Generator Survey

The benchmarking effort within the Extreme Scale Systems Center at Oak Ridge National Laboratory seeks to provide High Performance Computing benchmarks and test suites of interest to the DoD sponsor. The work described in this report is a part of the effort focusing on graph generation. A previously developed benchmark, SystemBurn, allowed the emulation of different application behavior profiles within a single framework. To complement this effort, similar capabilities are desired for graph-centric problems. This report examines existing synthetic graph generator implementations in preparation for further study on the properties of their generated synthetic graphs.

analytics↗

A Guide to Conquer the Biological Network Era Using Graph Theory

Networks are one of the most common ways to represent biological systems as complex sets of binary interactions or relations between different bioentities. In this article, we discuss the basic graph theory concepts and the various graph types, as well as the available data structures for storing and reading graphs. In addition, we describe several network properties and we highlight some of the widely used network topological features. We briefly mention the network patterns, motifs and models, and we further comment on the types of biological and biomedical networks along with their corresponding computer- and human-readable file formats. Finally, we discuss a variety of algorithms and metrics for network analyses regarding graph drawing, clustering, visualization, link prediction, perturbation, and network alignment as well as the current state-of-the-art tools. We expect this review to reach a very broad spectrum of readers varying from experts to beginners while encouraging them to enhance the field further.

59 BASIC BIOLOGICAL SCIENCES↗

NWGraph: A Library of Generic Graph Algorithms and Data Structures in C++20

The C++ Standard Library is a valuable collection of generic algorithms and data structures that improves the usability and reliability of C++ software. Graph algorithms and data structures are notably absent from the standard library, and previous attempts to fill this gap have not gained widespread adoption. In this paper we show that the richness of graph algorithms and data structures can in fact be captured by straightforward composition of existing C++ mechanisms. Generic programming is algorithm-oriented. Accordingly, we apply a systematic approach to analyzing a broad set of graph algorithms, “lift” unnecessary constraints from them, and organize the resulting set of minimal common type requirements, i.e., concepts, for defining their interfaces. By using the newly available ranges and concepts in C++20, the type requirements for generic graph algorithms can be succinctly expressed. The generic algorithms and data structures resulting from our analysis are realized in NWGraph, in a modern, composable, and extensible C++ library.

graphs and networks, programming language, C++20↗

A graph signal processing‐based multiple model Kalman filter ( GSP‐MMKF ) tool for predictive analytics: An air separation unit process application

Abstract The industrial Air Separations Unit (ASU) is a complicated and tightly operated process. The use of dynamic process analytics is also a key element of safe and economic operation of these processes, with increasing focus on predictive analytics to take preemptive actions. With the availability of real‐time data from hundreds of sensors, the data analysis process should also consider the topology of the data, as seen in sensor networks. In this paper, a novel tool is presented that considers the complex connectivity patterns in the sensor network and uses local adaptive disturbance estimations to predict global network‐scale trends. The paper introduces the emerging field of Graph Signal Processing (GSP) and presents a rigorous derivation of the tool starting from the extraction of the sensor‐network (in a graph theoretical sense) from the data. This network, which is in the form of a matrix, is then used to derive a Kalman‐filter type of state‐space model driven by input disturbances. Multiple disturbance models (e.g., step, ramp, periodic) are included to allow the model to have different kinds of disturbance propagation. Each graph node (representing the sensors used) dynamically adapts to the most recent detected disturbance individually. These estimated disturbances are propagated to the global network using the graph. Modifications to ensure stability are also discussed. The fidelity of the tool is tested on certain downtime events and the paper concludes by discussing the advantages of the method and planned future improvements.

Ghosh, Sambit↗

Multilevel graph embedding

The goal of the present paper is the design of embeddings of a general sparse graph into a set of points in $\mathbb{R}^d$ for appropriate d ≥ 2. The embeddings that we are looking at here aim to keep vertices that are grouped in communities together and keep the rest apart. To achieve this property, we utilize coarsening that respects possible community structures of the given graph. We employ a hierarchical multilevel coarsening approach that identifies communities (strongly connected groups of vertices) at every level. The multilevel strategy allows any given (presumably expensive) graph embedding algorithm to be made into a more scalable (and faster) algorithm. We demonstrate the presented approach on a number of given embedding algorithms and large-scale graphs and achieve speed-up over the methods in a recent paper.

97 MATHEMATICS AND COMPUTING↗

Graph 500 in OpenSHMEM, In: OpenSHMEM 2014: OpenSHMEM and Related Technologies. Experiences, Implementations, and Technologies

This document describes the effort to implement the Graph 500 benchmark using OpenSHMEM based on the MPI-2 one-side version. The Graph 500 benchmark performs a breadth-first search in parallel on a large randomly generated undirected graph and can be implemented using basic MPI-1 and MPI-2 one-sided communication. Graph 500 requires atomic bit-wise operations on unsigned long integers but neither atomic bit-wise operations nor OpenSHMEM for unsigned long are available in OpenSHEM. Such needed bit-wise atomic operations and support for unsigned long are implemented using atomic condition swap (CSWAP) on signed long integers. Preliminary results on comparing the OpenSHMEM and MPI-2 one-sided implementations on a Silicon Graphics Incorporated (SGI) cluster and the Cray XK7 are presented.

Computer Science↗

SO(3)-invariance of informed-graph-based deep neural network for anisotropic elastoplastic materials

This work examines the frame-invariance (and the lack thereof) exhibited in simulated anisotropic elasto-plastic responses generated from supervised machine learning of classical multi-layer and informed-graph-based neural networks, and proposes different remedies to fix this drawback. The inherent hierarchical relations among physical quantities and state variables in an elasto-plasticity model are first represented as informed, directed graphs, where three variations of the graph are tested. While feed-forward neural networks are used to train path-independent constitutive relations (e.g., elasticity), recurrent neural networks are used to replicate responses that depends on the deformation history, i.e. or path dependent. In dealing with the objectivity deficiency, we use the spectral form to represent tensors and, subsequently, three metrics, the Euclidean distance between the Euler Angles, the distance from the identity matrix, and geodesic on the unit sphere in Lie algebra, can be employed to constitute objective functions for the supervised machine learning. In this, the aim is to minimize the measured distance between the true and the predicted 3D rotation entities. Following this, we conduct numerical experiments on how these metrics, which are theoretically equivalent, may lead to differences in the efficiency of the supervised machine learning as well as the accuracy and robustness of the resultant models. Neural network models trained with tensors represented in component form for a given Cartesian coordinate system are used as a benchmark. Our numerical tests show that, even given the same amount of information and data, the quality of the anisotropic elasto-plasticity model is highly sensitive to the way tensors are represented and measured. The results reveal that using a loss function based on geodesic on the unit sphere in Lie algebra together with an informed, directed graph yield significantly more accurate rotation prediction than the other tested approaches.

42 ENGINEERING↗

Multiview Incomplete Knowledge Graph Integration with application to cross-institutional EHR data harmonization

Objective: The growing availability of electronic health records (EHR) data opens opportunities for integrative analysis of multi-institutional EHR to produce generalizable knowledge. A key barrier to such integrative analyses is the lack of semantic interoperability across different institutions due to coding differences. We propose a Multiview Incomplete Knowledge Graph Integration (MIKGI) algorithm to integrate information from multiple sources with partially overlapping EHR concept codes to enable translations between healthcare systems. Methods: The MIKGI algorithm combines knowledge graph information from (i) embeddings trained from the co-occurrence patterns of medical codes within each EHR system and (ii) semantic embeddings of the textual strings of all medical codes obtained from the Self-Aligning Pretrained BERT (SAPBERT) algorithm. Due to the heterogeneity in the coding across healthcare systems, each EHR source provides partial coverage of the available codes. MIKGI synthesizes the incomplete knowledge graphs derived from these multi-source embeddings by minimizing a spherical loss function that combines the pairwise directional similarities of embeddings computed from all available sources. MIKGI outputs harmonized semantic embedding vectors for all EHR codes, which improves the quality of the embeddings and enables direct assessment of both similarity and relatedness between any pair of codes from multiple healthcare systems. Results: With EHR co-occurrence data from Veteran Affairs (VA) healthcare and Mass General Brigham (MGB), MIKGI algorithm produces high quality embeddings for a variety of downstream tasks including detecting known similar or related entity pairs and mapping VA local codes to the relevant EHR codes used at MGB. Based on the cosine similarity of the MIKGI trained embeddings, the AUC was 0.918 for detecting similar entity pairs and 0.809 for detecting related pairs. For cross-institutional medical code mapping, the top 1 and top 5 accuracy were 91.0% and 97.5% when mapping medication codes at VA to RxNorm medication codes at MGB; 59.1% and 75.8% when mapping VA local laboratory codes to LOINC hierarchy. When trained with 500 labels, the lab code mapping attained top 1 and 5 accuracy at 77.7% and 87.9%. MIKGI also attained best performance in selecting VA local lab codes for desired laboratory tests and COVID-19 related features for COVID EHR studies. Compared to existing methods, MIKGI attained the most robust performance with accuracy the highest or near the highest across all tasks. Conclusions: The proposed MIKGI algorithm can effectively integrate incomplete summary data from biomedical text and EHR data to generate harmonized embeddings for EHR codes for knowledge graph modeling and cross-institutional translation of EHR codes.

Zhou, Doudou↗

Graph-Based Approach to Systematic Molecular Coarse-Graining

A novel methodology is introduced here to generate coarse-grained (CG) representations of molecular models for simulations. The proposed strategy relies on basic graph-theoretic principles and is referred to as graph-based coarse-graining (GBCG). It treats a given system as a molecular graph and derives a corresponding CG representation by using edge contractions to combine nodes in the graph, which correspond to atoms in the molecule, into CG sites. A key element of this methodology is that the nodes are combined according to well-defined protocols that rank-order nodes based on the underlying chemical connectivity. By iteratively performing these operations, successively coarser representations of the original atomic system can be produced to yield a systematic set of CG mappings with hierarchical resolution in an automated fashion. These capabilities are demonstrated in the context of several test systems, including toluene, pentadecane, a polysaccharide dimer, and a rhodopsin protein. In these examples, GBCG yields multiple, intuitive structures that naturally preserve the chemical topology of the system. Importantly, these representations are rendered from algorithmic implementation rather than an arbitrary ansatz, which, until now, has been the conventional approach for defining CG mapping schemes. Overall, the results presented here indicate that GBCG is efficient, robust, and unambiguous in its application, making it a valuable tool for future CG modeling.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

Understanding Metal–Organic Framework Nucleation from a Solution with Evolving Graphs

A mechanistic understanding of metal–organic framework (MOF) synthesis and scale-up remains underexplored due to the complex nature of the interactions of their building blocks. In this work, we investigate the collective assembly of building units at the early stages of MOF nucleation, using MIL-101(Cr) as a prototypical example. Using large-scale molecular dynamics simulations, we observe that the choice of solvent (water and N,N-dimethylformamide), the introduction of ions (Na+ and F–) and the relative populations of MIL-101(Cr) half-secondary building unit (half-SBU) isomers have a strong influence on the cluster formation process. Additionally, the shape, size, nucleation and growth rates, crystallinity, and short and long-range order largely vary depending on the synthesis conditions. We evaluate these properties as they naturally emerge when interpreting the self-assembly of MOF nuclei as the time evolution of an undirected graph. Solution-induced conformational complexity and ionic concentration have a dramatic effect on the morphology of clusters emerging during assembly. While pure solvents lead to the rapid formation of a small number of large clusters, the presence of ions in aqueous solutions results in smaller clusters and slower nucleation. This diversity is captured by the key features of the graph representation. Principle component analysis on graph properties reveals that only a small number of molecular descriptors is needed to deconvolute MOF self-assembly. Furthermore, descriptors such as the average coordination number between half-SBUs and fractal dimension are of particular interest as they can be can be followed experimentally by techniques like by time-resolved spectroscopy. Ultimately, graph theory emerges as an approach that can be used to understand complex processes revealing molecular descriptors accessible by both simulation and experiment.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

Efficient and interpretable graph network representation for angle-dependent properties applied to optical spectroscopy

Abstract Graph neural networks are attractive for learning properties of atomic structures thanks to their intuitive graph encoding of atoms and bonds. However, conventional encoding does not include angular information, which is critical for describing atomic arrangements in disordered systems. In this work, we extend the recently proposed ALIGNN (Atomistic Line Graph Neural Network) encoding, which incorporates bond angles, to also include dihedral angles (ALIGNN-d). This simple extension leads to a memory-efficient graph representation that captures the complete geometry of atomic structures. ALIGNN-d is applied to predict the infrared optical response of dynamically disordered Cu(II) aqua complexes, leveraging the intrinsic interpretability to elucidate the relative contributions of individual structural components. Bond and dihedral angles are found to be critical contributors to the fine structure of the absorption response, with distortions that represent transitions between more common geometries exhibiting the strongest absorption intensity. Future directions for further development of ALIGNN-d are discussed.

36 MATERIALS SCIENCE↗

Efficient generation of grids and traversal graphs in compositional spaces towards exploration and path planning

Abstract Diverse disciplines across science and engineering deal with problems related to compositions, which exist in non-Euclidean simplex spaces, rendering many standard tools inaccurate or inefficient. This work explores such spaces conceptually in the context of materials discovery, quantifies their computational feasibility, and implements several essential methods specific to simplex spaces through a new high-performance open-source library . Most significantly, we derive and implement an algorithm for constructing a novel n-dimensional simplex graph data structure, containing all discretized compositions and possible neighbor-to-neighbor transitions. Critically, no distance or neighborhood calculations are performed, instead leveraging pure combinatorics and order in procedurally generated simplex grids, keeping the algorithm $${\mathcal{O}}(N)$$ O ( N ) , with minimal memory, enabling rapid construction of graphs with billions of transitions in seconds. Additionally, we demonstrate how such graph representations can be combined to homogeneously express complex path-planning problems, while facilitating efficient deployment of existing high-performance gradient descent, graph traversal, and other optimization algorithms.

Krajewski, Adam M. (ORCID:0000000222660099)↗

The signed permutation group on Feynman graphs

The Feynman rules assign to every graph an integral which can be written as a function of a scaling parameter L. Assuming L for the process under consideration is very small, so that contributions to the renormalization group are small, we can expand the integral and only consider the lowest orders in the scaling. The aim of this article is to determine specific combinations of graphs in a scalar quantum field theory that lead to a remarkable simplification of the first non-trivial term in the perturbation series. It will be seen that the result is independent of the renormalization scheme and the scattering angles. To achieve that goal we will utilize the parametric representation of scalar Feynman integrals as well as the Hopf algebraic structure of the Feynman graphs under consideration. Moreover, we will present a formula which reduces the effort of determining the first-order term in the perturbation series for the specific combination of graphs to a minimum.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Graph-based quantum response theory and shadow Born–Oppenheimer molecular dynamics

Graph-based linear scaling electronic structure theory for quantum-mechanical molecular dynamics simulations [A. M. N. Niklasson et al., J. Chem. Phys. 144, 234101 (2016)] is adapted to the most recent shadow potential formulations of extended Lagrangian Born–Oppenheimer molecular dynamics, including fractional molecular-orbital occupation numbers [A. M. N. Niklasson, J. Chem. Phys. 152, 104103 (2020) and A. M. N. Niklasson, Eur. Phys. J. B 94, 164 (2021)], which enables stable simulations of sensitive complex chemical systems with unsteady charge solutions. The proposed formulation includes a preconditioned Krylov subspace approximation for the integration of the extended electronic degrees of freedom, which requires quantum response calculations for electronic states with fractional occupation numbers. For the response calculations, we introduce a graph-based canonical quantum perturbation theory that can be performed with the same natural parallelism and linear scaling complexity as the graph-based electronic structure calculations for the unperturbed ground state. Further, the proposed techniques are particularly well-suited for semi-empirical electronic structure theory, and the methods are demonstrated using self-consistent charge density-functional tight-binding theory both for the acceleration of self-consistent field calculations and for quantum-mechanical molecular dynamics simulations. Graph-based techniques combined with the semi-empirical theory enable stable simulations of large, complex chemical systems, including tens-of-thousands of atoms.

74 ATOMIC AND MOLECULAR PHYSICS↗

Accelerating defect predictions in semiconductors using graph neural networks

First-principles computations reliably predict the energetics of point defects in semiconductors but are constrained by the expense of using large supercells and advanced levels of theory. Machine learning models trained on computational data, especially ones that sufficiently encode defect coordination environments, can be used to accelerate defect predictions. Here, we develop a framework for the prediction and screening of native defects and functional impurities in a chemical space of group IV, III–V, and II–VI zinc blende semiconductors, powered by crystal Graph-based Neural Networks (GNNs) trained on high-throughput density functional theory (DFT) data. Using an innovative approach of sampling partially optimized defect configurations from DFT calculations, we generate one of the largest computational defect datasets to date, containing many types of vacancies, self-interstitials, anti-site substitutions, impurity interstitials and substitutions, as well as some defect complexes. We applied three types of established GNN techniques, namely crystal graph convolutional neural network, materials graph network, and Atomistic Line Graph Neural Network (ALIGNN), to rigorously train models for predicting defect formation energy (DFE) in multiple charge states and chemical potential conditions. We find that ALIGNN yields the best DFE predictions with root mean square errors around 0.3 eV, which represents a prediction accuracy of 98% given the range of values within the dataset, improving significantly on the state-of-the-art. We further show that GNN-based defective structure optimization can take us close to DFT-optimized geometries at a fraction of the cost of full DFT. The current models are based on the semi-local generalized gradient approximation-Perdew–Burke–Ernzerhof (PBE) functional but are highly promising because of the correlation of computed energetics and defect levels with higher levels of theory and experimental data, the accuracy and necessity of discovering novel metastable and low energy defect structures at the PBE level of theory before advanced methods could be applied, and the ability to train multi-fidelity models in the future with new data from non-local functionals. The DFT-GNN models enable prediction and screening across thousands of hypothetical defects based on both unoptimized and partially optimized defective structures, helping identify electronically active defects in technologically important semiconductors.

Rahman, Md Habibur (ORCID:000000027705984X)↗

Spectra of perfect state transfer Hamiltonians on fractal-like graphs

Abstract In this paper we study the spectral features, on fractal-like graphs, of Hamiltonians which exhibit the special property of perfect quantum state transfer (PQST): the transmission of quantum states without dissipation. The essential goal is to develop the theoretical framework for understanding the interplay between PQST, spectral properties, and the geometry of the underlying graph, in order to design novel protocols for applications in quantum information science. We present a new lifting and gluing construction, and use this to prove results concerning an inductive spectral structure, applicable to a wide variety of fractal-like graphs. We illustrate this construction with explicit examples for several classes of diamond graphs.

Physics↗