18 results on '"graph embedding problem"'
Search Results
2. Improved NMR‐data‐compliant protein structure modeling captures context‐dependent variations and expands the scope of functional inference.
- Author
-
Das, Niladri R., Chaudhury, Kunal N., and Pal, Debnath
- Abstract
Nuclear magnetic resonance (NMR) spectroscopy can reveal conformational states of a protein in physiological conditions. However, sparsely available NMR data for a protein with large degrees of freedom can introduce structural artifacts in the built models. Currently used state‐of‐the‐art methods deriving protein structure and conformation from NMR deploy molecular dynamics (MD) coupled with simulated annealing for building models. We provide an alternate graph‐based modeling approach, where we first build substructures from NMR‐derived distance‐geometry constraints combined in one shot to form the core structure. The remaining molecule with inadequate data is modeled using a hybrid approach respecting the observed distance‐geometry constraints. One‐shot structure building is rarely undertaken for large and sparse data systems, but our data‐driven bottom‐up approach makes this uniquely feasible by suitable partitioning of the problem. A detailed comparison of select models with state‐of‐art methods reveals differences in the secondary structure regions wherein the correctness of our models is confirmed by NMR data. Benchmarking of 106 protein‐folds covering 38–282 length structures shows minimal experimental‐constraint violations while conforming to other structure quality parameters such as the proper folding, steric clash, and torsion angle violation based on Ramachandran plot criteria. Comparative MD studies using select protein models from a state‐of‐art method and ours under identical experimental parameters reveal distinct conformational dynamics that could be attributed to protein structure–function. Our work is thus useful in building enhanced NMR‐evidence‐based models that encapsulate the contextual secondary and tertiary structure variations present during the experimentation and expand the scope of functional inference. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
3. Multivariate temporal process monitoring with graph‐based predictable feature analysis.
- Author
-
Fan, Wei, Zhu, Qinqin, Ren, Shaojun, Xu, Bo, and Si, Fengqi
- Subjects
TIME series analysis ,LATENT variables ,INFORMATION theory ,DATA mining ,DIMENSION reduction (Statistics) ,HEATING ,QUALITY control charts - Abstract
Dynamic latent variable (DLV) methods have been widely studied for high dimensional time series monitoring by exploiting dynamic relations among process variables. However, explicit extraction of predictable information is rarely emphasized in these DLV methods. In this paper, the graph‐based predictable feature analysis (GPFA) algorithm is introduced for statistical process monitoring due to its explicit predictability, and a novel index, prediction information, is designed to determine the number of its principal components for dimensionality reduction and parameter optimization. A GPFA‐based dynamic process monitoring framework is proposed to differentiate among dynamic faults, normal operating condition changes, and break in relation in the normal data. Case studies on the Tennessee Eastman process and a high‐pressure feedwater heater are conducted to demonstrate the superiority of GPFA over other approaches in terms of fault detection performance. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
4. The Minimum Bisection Widths of the Cube-Connected Cycles Graph and Cube Graph.
- Author
-
Manabe, Yoshifumi, Hagihara, Ken'ichi, and Tokura, Nobuki
- Subjects
GRAPH theory ,ALGORITHMS ,MATHEMATICAL analysis ,VERY large scale circuit integration ,CUBES ,SOLID geometry - Abstract
The minimum bisection width is an important quantity both as a measure of area for the graph embedding problem, which is an abstraction of the wiring problem of VLSI, and as a measure of computation time of a parallel algorithm in an abstraction of data communication relationships by a graph. In general, it is NP-complete to obtain the minimum bisection width for a given graph. Therefore it is useful to obtain the minimum bisection widths for graphs (e.g., a cube-connected cycles graph and a cube graph) which often are employed to represent interconnection relationships useful in parallel algorithms. It has been known that the minimum bisection width of a cube-connected cycles graph with n = s · 2
s vertices is 0(n/log n). It is shown that the minium bisection width of a cube-connected cycles graph with n = h · 2s (h >le; s) vertices is exactly 2s-1 , and that the minimum bisection width of a cube graph with 2s vertices is 2s-1 . The results presented in this paper will be the foundation for detailed analyses which will become important in the future. In addition, the order of the wiring area for VLSI and of calculation time of a parallel algorithm is discussed. [ABSTRACT FROM AUTHOR]- Published
- 1984
5. Partitioning and mapping of parallel programs by self-organization.
- Author
-
Heiss, Hans-Ulrich and Dormanns, Marcus
- Subjects
PARALLEL computers ,PARALLEL programming ,COMMUNICATION ,SELF-organizing maps ,SELF-organizing systems ,ARTIFICIAL neural networks - Abstract
To execute a parallel program on a multicomputer system, the tasks of the program have to be mapped to the particular processors of the parallel machine. The aim of the mapping is twofold: (i) to achieve a balanced load on the processors (partitioning problem) and (ii) to keep communication delays low by placing communicating tasks closely together (mapping). Since both the communication structure of the program and the interconnection structure of the parallel machine can he represented as graphs, the mapping problem can he regarded as a graph embedding problem to minimize communication costs. As a new heuristic approach to this NP-hard problem we apply Kohonen's self-organizing maps to establish a topology-preserving embedding. Experimental results are presented and compared to other approaches to this problem. The most attractive feature of our new method is that it can he extremely well parallelized. [ABSTRACT FROM AUTHOR]
- Published
- 1996
- Full Text
- View/download PDF
6. Vertex decomposition method for wirelength problem and its applications to enhanced hypercube networks.
- Author
-
Arockiaraj, Micheal, Liu, Jia‐Bao, and Shalini, Arul Jeya
- Abstract
In this study, the authors discuss the vertex congestion of any embedding from the guest graph into the host graph and outline a rigorous mathematical method to compute the wirelength of that embedding. Further, they show that the computation of the optimal wirelength depends on finding optimal solutions for another graph partition problem such as edge isoperimetric problem in that guest graph. On the other side, they consider an important variant of the popular hypercube network, the enhanced hypercube, and obtain the nested optimal solutions for the edge isoperimetric problem. As a combined output, they illustrate the authors' technique by embedding enhanced hypercube into a caterpillar and from that reducing the linear layout of the enhanced hypercube. As another application of their technique, they embed the hypercube as well as the enhanced hypercube on the two rows extended grid structure with optimal wirelength for the first time and showing that the existing edge congestion technique cannot be used to solve this problem. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
7. Learning Fuzzy Set Representations of Partial Shapes on Dual Embedding Spaces.
- Author
-
Sung, Minhyuk, Dubrovina, Anastasia, Guibas, Leonidas, and Kim, Vladimir G.
- Subjects
SHAPE analysis (Computational geometry) ,FUZZY sets ,REPRESENTATION theory ,MACHINE learning ,THREE-dimensional modeling - Abstract
Abstract: Modeling relations between components of 3D objects is essential for many geometry editing tasks. Existing techniques commonly rely on labeled components, which requires substantial annotation effort and limits components to a dictionary of predefined semantic parts. We propose a novel framework based on neural networks that analyzes an uncurated collection of 3D models from the same category and learns two important types of semantic relations among full and partial shapes: complementarity and interchangeability. The former helps to identify which two partial shapes make a complete plausible object, and the latter indicates that interchanging two partial shapes from different objects preserves the object plausibility. Our key idea is to jointly encode both relations by embedding partial shapes as fuzzy sets in dual embedding spaces. We model these two relations as fuzzy set operations performed across the dual embedding spaces, and within each space, respectively. We demonstrate the utility of our method for various retrieval tasks that are commonly needed in geometric modeling interfaces. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
8. ShapeFit: Exact Location Recovery from Corrupted Pairwise Directions.
- Author
-
Hand, Paul, Lee, Choongbum, and Voroninski, Vladislav
- Subjects
PAIRED comparisons (Mathematics) ,VECTORS (Calculus) ,MATHEMATICAL decomposition ,PHOTOMETRY ,MATHEMATICAL equivalence - Abstract
Let t
1 ,..., tn ∊ ℝd for d ≥ 2 and consider the location recovery problem: given a subset of pairwise direction observations [ABSTRACT FROM AUTHOR]- Published
- 2018
- Full Text
- View/download PDF
9. In-memory staging and data-centric task placement for coupled scientific simulation workflows.
- Author
-
Zhang, Fan, Jin, Tong, Sun, Qian, Romanus, Melissa, Bui, Hoang, Klasky, Scott, and Parashar, Manish
- Subjects
DATA libraries ,COMPUTER simulation ,COMPUTER input-output equipment ,SCALABILITY ,WIRELESS sensor nodes - Abstract
Coupled scientific simulation workflows are composed of heterogeneous component applications that simulate different aspects of the physical phenomena being modeled and that interact and exchange significant volumes of data at runtime. As the data volumes and generation rates keep growing, the traditional disk I/O-based data movement approach becomes cost prohibitive, and workflow requires more scalable and efficient approach to support the data movement. Moreover, the cost of moving large volume of data over system interconnection network becomes dominating and significantly impacts the workflow execution time. Minimize the amount of network data movement and localize data transfers are critical for reducing such cost. To achieve this, workflow task placement should exploit data locality to the extent possible and move computation closer to data. In this paper, we investigate applying in-memory data staging and data-centric task placement to reduce the data movement cost in large-scale coupled simulation workflows. Specifically, we present a distributed data sharing and task execution framework that (1) co-locates in-memory data staging on application compute nodes to store data that needs to be shared or exchanged and (2) uses data-centric task placement to map computations onto processor cores that a large portion of the data exchanges can be performed using the intra-node shared memory. We also present the implementation of the framework and its experimental evaluation on Titan Cray XK7 petascale supercomputer. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
10. A tree-based algorithm for virtual infrastructure allocation with joint virtual machine and network requirements.
- Author
-
Oliveira, Ramon and Koslovski, Guilherme Piegas
- Subjects
VIRTUAL networks ,VIRTUAL machine systems ,COMPUTER network resources ,WORKLOAD of computer networks ,CLOUD computing - Abstract
Cloud providers have introduced the on-demand provisioning of virtual infrastructures (VIs) to deliver virtual networks of computing resources as a service. By combining network and computing virtualization, providers allow traffic isolation between hosted VIs. Taking advantage of this opportunity, tenants have deployed private VIs with application-optimized network topologies to increase quality of experience of final users. One of the main open challenges in this scenario is the allocation of physical resources to host VIs in accordance with quality of service computing (eg, virtual CPUs and memory) and network requirements (guaranteed bandwidth and specific network topology). Moreover, a VI can be allocated anywhere atop a network datacenter, and because of its NP-hard complexity, the search for optimal solutions has a limited applicability in cloud providers as requesting users seek an immediate response. The present work proposes an algorithm to accomplish the VI allocation by applying tree-based heuristics to reduce the search space, performing a joint allocation of computing and network resources. So as to accomplish this goal, the mechanism includes a strategy to convert physical and virtual graphs to trees, which later are pruned by a grouped accounting algorithm. These innovations reduce the number of comparisons required to allocate a VI. Experimental results indicate that the proposed algorithm finds an allocation on feasible time for different cloud scenarios and VI topologies, while maintaining a high acceptance rate and a moderate physical infrastructure fragmentation. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
11. Tailoring the network to the problem: topology configuration in hybrid electronic packet switched/optical circuit switched interconnects.
- Author
-
Christodoulopoulos, Kostas, Katrinis, Kostas, Ruffini, Marco, and O'Mahony, Donal
- Subjects
COMPUTER networks ,HIGH performance computing ,ELECTRONIC circuits ,DATA libraries ,LINEAR programming ,COMPUTER algorithms ,OPTICAL switching - Abstract
SUMMARY We consider a hybrid electronic packet switched and optical circuit switched interconnection network for future high performance computing and datacenter systems. Given the logical task-to-task communication graph of an application, our objective is to cluster the logical parallel tasks to compute resources and configure the (reconfigurable) optical part of the hybrid interconnect to efficiently serve application communication requirements. We formulate the clustering and topology configuration problem in such a network, prove that it is NP-complete, and provide an optimal algorithm to solve it based on an integer linear programming formulation. The integer linear programming algorithm is used to optimally solve small-scale instances of the problem for the purpose of obtaining performance bounds. Aiming at large-scale, we also present a heuristic based on simulated annealing that trades-off performance for responsiveness. We measure the performance of a hybrid interconnect employing the proposed algorithm using real workloads, as well as extrapolated traffic, and compare it against application mapping on conventional fixed, electronic-only interconnects based on toroidal topologies. Copyright © 2013 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]
- Published
- 2013
- Full Text
- View/download PDF
12. The scalable process topology interface of MPI 2.2.
- Author
-
Hoefler, Torsten, Rabenseifner, Rolf, Ritzdorf, Hubert, de Supinski, Bronis R., Thakur, Rajeev, and Träff, Jesper Larsson
- Subjects
COMPUTER interfaces ,COMPUTER software ,COMPUTER programmers ,PROBLEM solving ,COMPUTER networks ,COMPUTER programming ,COMPUTER science - Abstract
The Message-passing Interface (MPI) standard provides basic means for adaptations of the mapping of MPI process ranks to processing elements to better match the communication characteristics of applications to the capabilities of the underlying systems. The MPI process topology mechanism enables the MPI implementation to rerank processes by creating a new communicator that reflects user-supplied information about the application communication pattern. With the newly released MPI 2.2 version of the MPI standard, the process topology mechanism has been enhanced with new interfaces for scalable and informative user-specification of communication patterns. Applications with relatively static communication patterns are encouraged to take advantage of the mechanism whenever convenient by specifying their communication pattern to the MPI library. Reference implementations of the new mechanism can be expected to be readily available (and come at essentially no cost), but non-trivial implementations pose challenging problems for the MPI implementer. This paper is first and foremost addressed to application programmers wanting to use the new process topology interfaces. It explains the use and the motivation for the enhanced interfaces and the advantages gained even with a straightforward implementation. For the MPI implementer, the paper summarizes the main issues in the efficient implementation of the interface and explains the optimization problems that need to be (approximately) solved by a good MPI library. Copyright © 2010 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]
- Published
- 2011
- Full Text
- View/download PDF
13. Multiple vertex coverings by specified induced subgraphs.
- Author
-
Füredi, Zoltán, Mubayi, Dhruv, and West, Douglas B.
- Published
- 2000
- Full Text
- View/download PDF
14. Congestion-free, dilation-2 embedding of complete binary trees into star graphs.
- Author
-
Tseng, Yu-Chee, Chen, Yuh-Shyan, Juang, Tong-Ying, and Chang, Chiou-Jyu
- Published
- 1999
- Full Text
- View/download PDF
15. Orientation embedding of signed graphs.
- Author
-
Zaslavsky, Thomas
- Published
- 1992
- Full Text
- View/download PDF
16. Compressing cube-connected cycles and butterfly networks.
- Author
-
Klasing, Ralf, Lüling, Reinhard, and Monien, Burkhard
- Published
- 1998
- Full Text
- View/download PDF
17. Cost minimization in placing service chains for virtualized network functions.
- Author
-
Wang, Chien Ting, Lin, Ying‐Dar, Wang, Chih‐Chiang, and Lai, Yuan‐Cheng
- Subjects
END-to-end delay ,NONLINEAR programming ,HEURISTIC algorithms ,VIRTUAL machine systems ,QUALITY of service ,SERVER farms (Computer network management) - Abstract
Summary: Network function virtualization (NFV) places network functions onto the virtual machines (VMs) of physical machines (PMs) located in data centers. In practice, a data flow may pass through multiple network functions, which collectively form a service chain across multiple VMs residing on the same or different PMs. Given a set of service chains, network operators have two options for placing them: (a) minimizing the number of VMs and PMs so as to reduce the server rental cost or (b) placing VMs running network functions belonging to the same service chain on the same or nearby PMs so as to reduce the network delay. In determining the optimal service chain placement, operators face the problem of minimizing the server cost while still satisfying the end‐to‐end delay constraint. The present study proposes an optimization model to solve this problem using a nonlinear programming (NLP) approach. The proposed model is used to explore various operational problems in the service chain placement field. The results suggest that the optimal cost ratio for PMs with high, hybrid, and low capacity, respectively, is equal to 4:2:1. Meanwhile, the maximum operating utilization rate should be limited to 55% in order to minimize the rental cost. Regarding quality of service (QoS) relaxation, the server cost reduces by 20%, 30%, and 32% as the end‐to‐end delay constraint is relaxed from 40 to 60, 80, and 100 ms, respectively. For the server location, the cost decreases by 25% when the high‐capacity PMs are decentralized rather than centralized. Finally, the cost reduces by 40% as the repetition rate in the service chain increases from 0 to 2. A heuristic algorithm, designated as common sub chain placement first (CPF), is proposed to solve the service chain placement problem for large‐scale problems (eg, 256 PMs). It is shown that the proposed algorithm reduces the solution time by up to 86% compared with the NLP optimization model, with an accuracy reduction of just 8%. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
18. A new approach for traffic matrix estimation in high load computer networks based on graph embedding and convolutional neural network.
- Author
-
Emami, Mohsen, Akbari, Reza, Javidan, Reza, and Zamani, Ali
- Subjects
PARAMETER estimation ,COMPUTER networks ,GRAPH theory ,SIGNAL convolution ,ARTIFICIAL neural networks ,COMPUTATIONAL complexity ,PROBLEM solving - Abstract
In computer networks, transmitted traffic between origin‐destination nodes has been considered a crucial factor in traffic engineering applications. To date, measuring the traffic directly in high load networks is difficult due to high computational costs. On the other hand, accurate estimation of network traffic by means of link load measurements and routing information is currently a challenging problem. In this paper, we propose a new approach to estimate end‐to‐end traffic, inspired by graph embedding. In the proposed approach, we consider a computer network as a time‐varying graph. Our model provides explicit routing information to a convolutional neural network estimator via link load measurements and network topological structure. When explicit routing information is provided, the learning model is only expected to embed the relations between link loads into a traffic estimation vector, instead of figuring out the routing paths. The experimental results showed that the proposed approach outperforms similar estimators in terms of lower estimation error and better tracking the fluctuations. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.