Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “Bipartite 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.

27 records · Page 2

Quantum-assisted associative adversarial network: applying quantum annealing in deep learning

Abstract Generative models have the capacity to model and generate new examples from a dataset and have an increasingly diverse set of applications driven by commercial and academic interest. In this work, we present an algorithm for learning a latent variable generative model via generative adversarial learning where the canonical uniform noise input is replaced by samples from a graphical model. This graphical model is learned by a Boltzmann machine which learns low-dimensional feature representation of data extracted by the discriminator. A quantum processor can be used to sample from the model to train the Boltzmann machine. This novel hybrid quantum-classical algorithm joins a growing family of algorithms that use a quantum processor sampling subroutine in deep learning, and provides a scalable framework to test the advantages of quantum-assisted learning. For the latent space model, fully connected, symmetric bipartite and Chimera graph topologies are compared on a reduced stochastically binarized MNIST dataset, for both classical and quantum sampling methods. The quantum-assisted associative adversarial network successfully learns a generative model of the MNIST dataset for all topologies. Evaluated using the Fréchet inception distance and inception score, the quantum and classical versions of the algorithm are found to have equivalent performance for learning an implicit generative model of the MNIST dataset. Classical sampling is used to demonstrate the algorithm on the LSUN bedrooms dataset, indicating scalability to larger and color datasets. Though the quantum processor used here is a quantum annealer, the algorithm is general enough such that any quantum processor, such as gate model quantum computers, may be substituted as a sampler.

Wilson, Max (ORCID:0000000207983391)↗

GMFOLD: Subgraph matching for high-throughput DNA-aptamer secondary structure classification and machine learning interpretability

Aptamers are oligonucleotide receptors that bind to their targets with high affinity. Here, we consider aptamers comprised of single-stranded DNA that undergo target-binding-induced conformational changes, giving rise to unique secondary and tertiary structures. Given a specific aptamer primary sequence, there are well-established computational tools (notably mfold) to predict the secondary structure via free energy minimization algorithms. While mfold generates secondary structures for individual sequences, there is a need for a high-throughput process whereby thousands of DNA structures can be predicted in real-time for use in an interactive setting, when combined with aptamer selections that generate candidate pools that are too large to be experimentally interrogated. We developed a new Python code for high-throughput aptamer secondary structure determination (GMfold). GMfold uses subgraph matching methods to group aptamer candidates by secondary structure similarities. We also improve an open-source code, SeqFold, to incorporate subgraph matching concepts. We represent each secondary structure as a lowest-energy bipartite subgraph matching of the DNA graph to itself. These new tools enable thousands of DNA sequences to be compared based on their secondary structures, using machine-learning algorithms. This process is advantageous when analyzing sequences that arise from aptamer selections via systematic evolution of ligands by exponential enrichment (SELEX). This work is a building block for future machine-learning-informed DNA-aptamer selection processes to identify aptamers with improved target affinity and selectivity and advance aptamer biosensors and therapeutics.

Aptamer↗

Line-Graph Approach to Spiral Spin Liquids

Competition among exchange interactions is able to induce novel spin correlations on a bipartite lattice without geometrical frustration. A prototype example is the spiral spin liquid, which is a correlated paramagnetic state characterized by subdimensional degenerate propagation vectors. Here, using spectral graph theory, we show that spiral spin liquids on a bipartite lattice can be approximated by a further-neighbor model on the corresponding line-graph lattice that is nonbipartite, thus broadening the space of candidate materials that may support the spiral spin liquid phases. As examples, we examine neutron scattering experiments performed on two spinel compounds, ZnCr 2 Se 4 and CuInCr 4 Se 8 , to demonstrate the feasibility of this new approach and expose its possible limitations in experimental realizations.

72 PHYSICS OF ELEMENTARY PARTICLES AND FIELDS↗

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↗

Understanding the Scalability of Bayesian Network Inference Using Clique Tree Growth Curves

One of the main approaches to performing computation in Bayesian networks (BNs) is clique tree clustering and propagation. The clique tree approach consists of propagation in a clique tree compiled from a Bayesian network, and while it was introduced in the 1980s, there is still a lack of understanding of how clique tree computation time depends on variations in BN size and structure. In this article, we improve this understanding by developing an approach to characterizing clique tree growth as a function of parameters that can be computed in polynomial time from BNs, specifically: (i) the ratio of the number of a BN s non-root nodes to the number of root nodes, and (ii) the expected number of moral edges in their moral graphs. Analytically, we partition the set of cliques in a clique tree into different sets, and introduce a growth curve for the total size of each set. For the special case of bipartite BNs, there are two sets and two growth curves, a mixed clique growth curve and a root clique growth curve. In experiments, where random bipartite BNs generated using the BPART algorithm are studied, we systematically increase the out-degree of the root nodes in bipartite Bayesian networks, by increasing the number of leaf nodes. Surprisingly, root clique growth is well-approximated by Gompertz growth curves, an S-shaped family of curves that has previously been used to describe growth processes in biology, medicine, and neuroscience. We believe that this research improves the understanding of the scaling behavior of clique tree clustering for a certain class of Bayesian networks; presents an aid for trade-off studies of clique tree clustering using growth curves; and ultimately provides a foundation for benchmarking and developing improved BN inference and machine learning algorithms.

Mengshoel, Ole J.↗

Quantum Routing and Entanglement Dynamics Through Bottlenecks

To implement arbitrary quantum circuits in architectures with restricted interactions, one may effectively simulate all-to-all connectivity by routing quantum information. We consider the entanglement dynamics and routing between two regions only connected through an intermediate “bottleneck” region with few qubits. In such systems, where the entanglement rate is restricted by a vertex boundary rather than an edge boundary of the underlying interaction graph, existing results such as the small incremental entangling theorem give only a trivial constant lower bound on the routing time (the minimum time to perform an arbitrary permutation). We significantly improve the lower bound on the routing time in systems with a vertex bottleneck. Specifically, for any system with two regions 𝐿,𝑅 with 𝑁 𝐿 ,𝑁 𝑅 qubits, respectively, coupled only through an intermediate region 𝐶 with 𝑁 𝐶 qubits, for any 𝛿 > 0 we show a lower bound of Ω⁢(𝑁$^{1−𝛿}_{𝑅}$/√𝑁 𝐿⁢ 𝑁 𝐶 ) on the Hamiltonian quantum routing time when using piecewise time-independent Hamiltonians, or time-dependent Hamiltonians subject to a smoothness condition. We also prove an upper bound on the average amount of bipartite entanglement between 𝐿 and 𝐶,𝑅 that can be generated in time 𝑡 by such architecture-respecting Hamiltonians in systems constrained by vertex bottlenecks, improving the scaling in the system size from 𝑂⁡(𝑁 𝐿⁢ 𝑡) to 𝑂⁡(√𝑁 𝐿⁢ 𝑡). As a special case, when applied to the star graph (i.e., one vertex connected to 𝑁 leaves), we obtain an Ω⁡(√𝑁 1−𝛿 ) lower bound on the routing time and on the time to prepare 𝑁/2 Bell pairs between the vertices. We also show that, in systems of free particles, we can route optimally on the star graph in time Θ⁡(√𝑁) using Hamiltonian quantum routing, obtaining a speedup over gate-based routing, which takes time Θ⁡(𝑁).

97 MATHEMATICS AND COMPUTING↗

Understanding the Scalability of Bayesian Network Inference using Clique Tree Growth Curves

Bayesian networks (BNs) are used to represent and efficiently compute with multi-variate probability distributions in a wide range of disciplines. One of the main approaches to perform computation in BNs is clique tree clustering and propagation. In this approach, BN computation consists of propagation in a clique tree compiled from a Bayesian network. There is a lack of understanding of how clique tree computation time, and BN computation time in more general, depends on variations in BN size and structure. On the one hand, complexity results tell us that many interesting BN queries are NP-hard or worse to answer, and it is not hard to find application BNs where the clique tree approach in practice cannot be used. On the other hand, it is well-known that tree-structured BNs can be used to answer probabilistic queries in polynomial time. In this article, we develop an approach to characterizing clique tree growth as a function of parameters that can be computed in polynomial time from BNs, specifically: (i) the ratio of the number of a BN's non-root nodes to the number of root nodes, or (ii) the expected number of moral edges in their moral graphs. Our approach is based on combining analytical and experimental results. Analytically, we partition the set of cliques in a clique tree into different sets, and introduce a growth curve for each set. For the special case of bipartite BNs, we consequently have two growth curves, a mixed clique growth curve and a root clique growth curve. In experiments, we systematically increase the degree of the root nodes in bipartite Bayesian networks, and find that root clique growth is well-approximated by Gompertz growth curves. It is believed that this research improves the understanding of the scaling behavior of clique tree clustering, provides a foundation for benchmarking and developing improved BN inference and machine learning algorithms, and presents an aid for analytical trade-off studies of clique tree clustering using growth curves.

Mengshoel, Ole Jakob↗

Efficient mapping algorithms for scheduling robot inverse dynamics computation on a multiprocessor system

Two efficient mapping algorithms for scheduling the robot inverse dynamics computation consisting of m computational modules with precedence relationship to be executed on a multiprocessor system consisting of p identical homogeneous processors with processor and communication costs to achieve minimum computation time are presented. An objective function is defined in terms of the sum of the processor finishing time and the interprocessor communication time. The minimax optimization is performed on the objective function to obtain the best mapping. This mapping problem can be formulated as a combination of the graph partitioning and the scheduling problems; both have been known to be NP-complete. Thus, to speed up the searching for a solution, two heuristic algorithms were proposed to obtain fast but suboptimal mapping solutions. The first algorithm utilizes the level and the communication intensity of the task modules to construct an ordered priority list of ready modules and the module assignment is performed by a weighted bipartite matching algorithm. For a near-optimal mapping solution, the problem can be solved by the heuristic algorithm with simulated annealing. These proposed optimization algorithms can solve various large-scale problems within a reasonable time. Computer simulations were performed to evaluate and verify the performance and the validity of the proposed mapping algorithms. Finally, experiments for computing the inverse dynamics of a six-jointed PUMA-like manipulator based on the Newton-Euler dynamic equations were implemented on an NCUBE/ten hypercube computer to verify the proposed mapping algorithms. Computer simulation and experimental results are compared and discussed.

Lee, C. S. G.↗

Evaluation of global teleconnections in CMIP6 climate projections using complex networks

In climatological research, the evaluation of climate models is one of the central research subjects. As an expression of large-scale dynamical processes, global teleconnections play a major role in interannual to decadal climate variability. Their realistic representation is an indispensable requirement for the simulation of climate change, both natural and anthropogenic. Therefore, the evaluation of global teleconnections is of utmost importance when assessing the physical plausibility of climate projections. We present an application of the graph-theoretical analysis tool δ-MAPS, which constructs complex networks on the basis of spatio-temporal gridded data sets, here sea surface temperature and geopotential height at 500 hPa. Complex networks complement more traditional methods in the analysis of climate variability, like the classification of circulation regimes or empirical orthogonal functions, assuming a new non-linear perspective. While doing so, a number of technical tools and metrics, borrowed from different fields of data science, are implemented into the δ-MAPS framework in order to overcome specific challenges posed by our target problem. Those are trend empirical orthogonal functions (EOFs), distance correlation and distance multicorrelation, and the structural similarity index. δ-MAPS is a two-stage algorithm. In the first place, it assembles grid cells with highly coherent temporal evolution into so-called domains. In a second step, the teleconnections between the domains are inferred by means of the non-linear distance correlation. We construct 2 unipartite and 1 bipartite network for 22 historical CMIP6 climate projections and 2 century-long coupled reanalyses (CERA-20C and 20CRv3). Potential non-stationarity is taken into account by the use of moving time windows. The networks derived from projection data are compared to those from reanalyses. Our results indicate that no single climate projection outperforms all others in every aspect of the evaluation. But there are indeed models which tend to perform better/worse in many aspects. Differences in model performance are generally low within the geopotential height unipartite networks but higher in sea surface temperature and most pronounced in the bipartite network representing the interaction between ocean and atmosphere.

58 GEOSCIENCES↗