Search

Several real-world phenomena, including social, communication, transportation, and biological networks, can be efficiently expressed as graphs. This enables the deployment of graph algorithms to infer information from such complex network interactions to enhance graph applications' accuracy, including link prediction, node classification, and clustering. However, the large size and complexity of the network data limit the efficiency of the learning algorithms in making decisions from such graph datasets. To overcome these limitations, graph embedding techniques are usually adopted. However, many studies not only assume static networks but also pay less attention to preserving the network topological and centrality information, which information is key in analyzing networks. In order to fill these gaps, we propose a novel end-to-end unified Topological Similarity and Centrality driven Hybrid Deep Learning model for Temporal Link Prediction (TSC-TLP). First, we extract topological similarity and centrality-based features from the raw networks. Next, we systematically aggregate these topological and centrality features to act as inputs for the encoder. In addition, we leverage the long short-term memory (LSTM) layer to learn the underlying temporal information in the graph snapshots. Lastly, we impose topological similarity and centrality constraints on the model learning to enforce preserving of topological structure and node centrality role of the input graphs in the learned embeddings. The proposed TSC-TLP is tested on 3 real-world temporal social networks. On average, it exhibits a 4% improvement in link prediction accuracy and a 37% reduction in MSE on centrality prediction over the best benchmark. [ABSTRACT FROM AUTHOR]

Quantum computing is a game-changing technology for global academia, research centers and industries including computational science, mathematics, finance, pharmaceutical, materials science, chemistry and cryptography. Although it has seen a major boost in the last decade, we are still a long way from reaching the maturity of a full-fledged quantum computer. That said, we will be in the noisy-intermediate scale quantum (NISQ) era for a long time, working on dozens or even thousands of qubits quantum computing systems. An outstanding challenge, then, is to come up with an application that can reliably carry out a nontrivial task of interest on the near-term quantum devices with non-negligible quantum noise. To address this challenge, several near-term quantum computing techniques, including variational quantum algorithms, error mitigation, quantum circuit compilation and benchmarking protocols, have been proposed to characterize and mitigate errors, and to implement algorithms with a certain resistance to noise, so as to enhance the capabilities of near-term quantum devices and explore the boundaries of their ability to realize useful applications. Besides, the development of near-term quantum devices is inseparable from the efficient classical simulation, which plays a vital role in quantum algorithm design and verification, error-tolerant verification and other applications. This review will provide a thorough introduction of these near-term quantum computing techniques, report on their progress, and finally discuss the future prospect of these techniques, which we hope will motivate researchers to undertake additional studies in this field. [ABSTRACT FROM AUTHOR]

Virtualized datacenters offer great flexibilities in terms of resource allocation. In particular, by decoupling applications from the constraints of the underlying infrastructure, virtualization supports an optimized mapping of virtual machines as well as their interconnecting network (the so-called virtual cluster ) to their physical counterparts: a graph embedding problem. However, existing virtual cluster embedding algorithms often ignore a crucial dimension of the problem, namely data locality : the input to a cloud application such as MapReduce is typically stored in a distributed, and sometimes redundant, file system. Since moving data is costly, an embedding algorithm should be data locality aware, and allocate computational resources close to the data; in case of redundant storage, the algorithm should also optimize the replica selection . This paper initiates the algorithmic study of data locality aware virtual cluster embeddings on datacenter topologies. We show that despite the multiple degrees of freedom in terms of embedding, replica selection and assignment, many problems can be solved efficiently. We also highlight the limitations of such optimizations, by presenting several NP-hardness proofs; interestingly, our hardness results also hold in uncapacitated networks of small diameter. [ABSTRACT FROM AUTHOR]

In this paper, a novel supervised local high-order differential channel feature is proposed for fast pedestrian detection. This method is motivated by the recent successful use of filtering on the multiple channel maps, which can improve the performance. This method firstly compute the multiple channel maps for the input RGB image, and average pooling is acted on the channel maps in order to reduce the effect of noise and sample misalignment. Then, each of the pooled channel maps is convolved with our proposed local high-order filter bank, which can enhance the discriminative information in the feature space. Finally, due to the increasing memory consumption incurred by the higher dimension of resulting feature, we have proposed a local structure preserved supervised dimension reduction method which aims to keep the manifold structure of samples in the feature space. This method is formulated as a classical spectral graph embedding problem which can be solved by the LPP algorithms. Thorough experiments and comparative studies show that our method can achieve very competitive result compared with many state-of-art methods on the INRIA and Caltech datasets. Besides, our detector can run about 20 fps in 480 $$\times $$ 640 resolution images. [ABSTRACT FROM AUTHOR]

Graphs are data structures that effectively represent relational data in the real world. Graph representation learning is a significant task since it could facilitate various downstream tasks, such as node classification, link prediction, etc. Graph representation learning aims to map graph entities to low-dimensional vectors while preserving graph structure and entity relationships. Over the decades, many models have been proposed for graph representation learning. This paper aims to show a comprehensive picture of graph representation learning models, including traditional and state-of-the-art models on various graphs in different geometric spaces. First, we begin with five types of graph embedding models: graph kernels, matrix factorization models, shallow models, deep-learning models, and non-Euclidean models. In addition, we also discuss graph transformer models and Gaussian embedding models. Second, we present practical applications of graph embedding models, from constructing graphs for specific domains to applying models to solve tasks. Finally, we discuss challenges for existing models and future research directions in detail. As a result, this paper provides a structured overview of the diversity of graph embedding models. [ABSTRACT FROM AUTHOR]

Software question answering community (SQAC) as an effective platform of knowledge sharing has achieved rapid development. In SQAC, one critical and challenging problem is question routing (or expert recommendation). To solve this problem, previous approaches focus on learning the relevance between the question and answerers. However, such approaches usually suffer from the data sparsity and noise issues which may reduce the accuracy of the question routing. Moreover, previous approaches also ignored the response quality and timeliness of the question routing. To tackle those issues, we study the question routing problem from two aspects: 1) the answerer's relevance to the given question, and 2) the answerer's capability. We first propose a deep knowledge-awared question routing framework (termed ExpRec) which leverages the attentive embedding propagates and their high-order connectivities to learn the answerer's relevance to the given question. Then we explicitly model the answerer's capability and incorporate it with the answerer's relevance to the given question. Finally, to evaluate the performance of ExpRec, we conduct extensive experiments on two real-world datasets. The experimental results show that ExpRec outperforms other five state-of-the-art approaches significantly. [ABSTRACT FROM AUTHOR]

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]

The reconstruction of realistic large-scale 3D scene models using aerial images or videos has significant applications in smart cities, surveying and mapping, the military and other fields. In the current state-of-the-art 3D-reconstruction pipeline, the massive scale of the scene and the enormous amount of input data are still considerable obstacles to the rapid reconstruction of large-scale 3D scene models. In this paper, we develop a professional system for large-scale 3D reconstruction. First, in the sparse point-cloud reconstruction stage, the computed matching relationships are used as the initial camera graph and divided into multiple subgraphs by a clustering algorithm. Multiple computational nodes execute the local structure-from-motion (SFM) technique, and local cameras are registered. Global camera alignment is achieved by integrating and optimizing all local camera poses. Second, in the dense point-cloud reconstruction stage, the adjacency information is decoupled from the pixel level by red-and-black checkerboard grid sampling. The optimal depth value is obtained using normalized cross-correlation (NCC). Additionally, during the mesh-reconstruction stage, feature-preserving mesh simplification, Laplace mesh-smoothing and mesh-detail-recovery methods are used to improve the quality of the mesh model. Finally, the above algorithms are integrated into our large-scale 3D-reconstruction system. Experiments show that the system can effectively improve the reconstruction speed of large-scale 3D scenes. [ABSTRACT FROM AUTHOR]

The problem of determining the genus for a graph can be dated to the Map Color Conjecture proposed by Heawood in 1890. This was implied to be a Thread Problem by Hilbert and Cohn-Vossen. The conjecture was finally established by Ringel, Youngs, and many other mathematicians. Subsequently, the genera of some special graphs with symmetry were determined. The study of genus embeddings of graphs is closely related to other invariants of a graph. Specifically, the computational complexity is dependent on the genus of the underlying graph for certain well-known NP-hard problems. In this survey, main construction techniques and certain criteria are stated in the topic of the genus of a graph. Most graphs with a known genus are listed. A new theorem is shown that the method of joint trees of a graph is reasonable. Moreover, a formal set is introduced, and related results are obtained. Although a cubic graph of Hamilton cycle is asymmetric, it is interesting that a set of associate surfaces of all its joint trees is a formal set with symmetry. [ABSTRACT FROM AUTHOR]

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]

This paper discusses about the new approach of multiple object tracking relative to background information. The concept of multiple object tracking through background learning is based upon the theory of relativity, that involves a frame of reference in spatial domain to localize and/or track any object. The field of multiple object tracking has seen a lot of research, but researchers have considered the background as redundant. However, in object tracking, the background plays a vital role and leads to definite improvement in the overall process of tracking. In the present work an algorithm is proposed for the multiple object tracking through background learning. The learning framework is based on graph embedding approach for localizing multiple objects. The graph utilizes the inherent capabilities of depth modelling that assist in prior to track occlusion avoidance among multiple objects. The proposed algorithm has been compared with the recent work available in literature on numerous performance evaluation measures. It is observed that our proposed algorithm gives better performance. [ABSTRACT FROM AUTHOR]

Embedding static graphs in low-dimensional vector spaces plays a key role in network analytics and inference, supporting applications like node classification, link prediction, and graph visualization. However, many real-world networks present dynamic behavior, including topological evolution, feature evolution, and diffusion. Therefore, several methods for embedding dynamic graphs have been proposed to learn network representations over time, facing novel challenges, such as time-domain modeling, temporal features to be captured, and the temporal granularity to be embedded. In this survey, we overview dynamic graph embedding, discussing its fundamentals and the recent advances developed so far. We introduce the formal definition of dynamic graph embedding, focusing on the problem setting and introducing a novel taxonomy for dynamic graph embedding input and output. We further explore different dynamic behaviors that may be encompassed by embeddings, classifying by topological evolution, feature evolution, and processes on networks. Afterward, we describe existing techniques and propose a taxonomy for dynamic graph embedding techniques based on algorithmic approaches, from matrix and tensor factorization to deep learning, random walks, and temporal point processes. We also elucidate main applications, including dynamic link prediction, anomaly detection, and diffusion prediction, and we further state some promising research directions in the area. [ABSTRACT FROM AUTHOR]

Knowledge graph embedding has been proposed to embed entities and relations into continuous vector spaces, which can benefit various downstream tasks, such as question answering and recommender systems, etc. A common assumption of existing knowledge graph embedding models is that the relation is a translation vector connecting the embedded head entity and tail entity. However, based on this assumption, the same relation connecting multiple entities may form a circle and lead to mistakes during computing process. To solve this so-called circular relation problem that has been ignored previously, we propose a novel method called ContE (Contextualized Embedding) for knowledge graphs by exploring collaborative relations. Specifically, each collaborative relation combines an explicit relation and a latent relation, where the explicit one is the original relation between two entities, and the latent one is introduced to capture the implicit interactions obtained via the context information of the two entities. With the collaborative relations, the same relations will be embedded varying across different contexts, and the sharing of similar semantics will be guaranteed as well. We conduct extensive experiments in link prediction and triple classification tasks on five benchmark datasets. The experimental results demonstrate that the proposed ContE achieves improvements over several baselines. [ABSTRACT FROM AUTHOR]

The rotational dimension is a minor-monotone graph invariant related to the dimension of a Euclidean space containing a spectral embedding corresponding to the first nonzero eigenvalue of the graph Laplacian, which is introduced by Göring, Helmberg and Wappler. In this paper, we study rotational dimensions of graphs which contain large complete graphs. The complete graph is characterized by its rotational dimension. It will be obtained that a chordal graph may be made large while keeping the rotational dimension constant. [ABSTRACT FROM AUTHOR]

Graph embedding is of great significance for the research and analysis of graphs. Graph embedding aims to map nodes in the network to low-dimensional vectors while preserving information in the original graph of nodes. In recent years, the appearance of graph neural networks has significantly improved the accuracy of graph embedding. However, the influence of clusters was not considered in existing graph neural network (GNN)-based methods, so this paper proposes a new method to incorporate the influence of clusters into the generation of graph embedding. We use the attention mechanism to pass the message of the cluster pooled result and integrate the whole process into the graph autoencoder as the third layer of the encoder. The experimental results show that our model has made great improvement over the baseline methods in the node clustering and link prediction tasks, demonstrating that the embeddings generated by our model have excellent expressiveness. [ABSTRACT FROM AUTHOR]

Identifying urban functional regions is a trending topic in urban computing. It helps understand the economic and cultural development of cities and assists decision-makers in land-use planning. However, the studies to date have not fully mined the spatio-temporal characteristics of location data, and most have used the direct clustering method to judge differences among urban land use types, resulting in low identification accuracies. Here, we propose a novel framework for urban functional region discovery based on residents' travel patterns. The framework uses GPS trajectory data and check-in data to construct a travel pattern graph with temporal and spatial attributes and learns the vector representations of urban regions using the Node2vec method to identify urban functional regions. In addition, a novel detection method that combines semantic information of check-in data and well-known points of interest (POIs) was constructed to annotate the semantics of the functional regions. Real location data sets were used for verification. The experimental results showed that the proposed graph embedding learning method could effectively discover urban functional regions. Moreover, this method solved the problem of accurately identifying the semantics of functional regions to a certain extent. [ABSTRACT FROM AUTHOR]

The extraction of valuable insights from unstructured content has attracted much attention in the last decades. Main results lie in the area of text mining, while the understanding of multimedia contents, thanks to the improvements in computer vision, mainly relies on adopting emerging deep learning models. About image understanding, people's name association in images is still an open issue. The approaches at the state of the art mainly use facial features and find the corresponding names by extracting the most recurring entities in the attached captions. These methods are experimented for celebrities and often fail when few labeled samples are available or there are particular poses. The proposed solution tries to improve the name–face association in such cases by defining a cognitive layer for a deep learning architecture embedding the surrounding context of the entities in the caption or the image. The method mainly focuses on name–face association as enabling technology for people recognition in open-source intelligence frameworks that mostly investigate not popular (or unknown) people. Given a face, the proposed system predicts the most likely corresponding name leveraging image features, caption, and context. The learning model embeds the knowledge graph of the context elicited in the open sources through a graph neural network. The experimentation highlights that the context improves the results of the name–face association, especially when other methods fail. [ABSTRACT FROM AUTHOR]

A s i g n e d g r a p h is a graph whose edges carry the weight '+' or '−'. A signed graph S is called sign-regular if d − (v) is same for all v ∈ V and d + (v) is same for all v ∈ V. The problems of embedding (i , j) -sign-regular signed graphs in (i + k , j + l) -sign-regular signed graphs is one of the fascinating problem from application point of view which is dealt in this paper with insertion of least number of vertices in S and the problem of finding least number of non-isomorphic co-regular signed graphs is explored. We also define the relationship between characteristic polynomial of graph G and the graph in which it embeds. [ABSTRACT FROM AUTHOR]

The efficiency of a graph embedding problem when simulating one interconnection network in another interconnection network is characterized by the influential parameter of wirelength. Obtaining the minimum wirelength in an embedding problem determines the quality of that embedding. In this paper, we obtained the convex edge partition of 3-Ary n-Cubes and the minimized wirelength of the embeddings of both 3-Ary n-Cubes and circulant networks.

Graph-based semi-supervised learning has received considerable attention in machine learning community. The performance of existing methods highly depends on the input weight graph, which is related to the choice of hyper-parameters, such as the number of neighbors and the weight function. Multiple weights graphs can be easily built by selecting different hyper-parameters. In addition, there are multiple weights graphs representations for the same data set in many real-world applications. A key challenge is how to obtain better performance for graph-based semi-supervised learning by introducing multiple graphs. In this paper, we focus on multi-modal semi-supervised learning. A novel graph-based multi-modal semi-supervised learning framework, self-paced multi-modal label propagation learning (SPLP), is proposed. The main idea of SPLP is to take each type of weights graph as one modality and train "easy" modality first, then "complex" ones by self-paced learning. SPLP has the ability to select different weight coefficients in a purely self-paced way for multiple graphs and has good robustness against noisy or irrelevant graphs which cannot be rightly achieved by existing methods. We apply the proposed learning framework to solve the classification task on benchmark datasets including non-network datasets (MNIST, PIE, Sector and Reuters-21578) and network datasets (Cora and Citeseer). Experimental results show that our method achieves more than 2% improvement with regard to the several graph based state-of-the-art semi-supervised learning methods. [ABSTRACT FROM AUTHOR]

Graphs with complete node attributes have been widely explored recently. While in practice, there is a graph where attributes of only partial nodes could be available and those of the others might be entirely missing. This attribute-missing graph is related to numerous real-world applications and there are limited studies investigating the corresponding learning problems. Existing graph learning methods including the popular GNN cannot provide satisfied learning performance since they are not specified for attribute-missing graphs. Thereby, designing a new GNN for these graphs is a burning issue to the graph learning community. In this article, we make a shared-latent space assumption on graphs and develop a novel distribution matching-based GNN called structure-attribute transformer (SAT) for attribute-missing graphs. SAT leverages structures and attributes in a decoupled scheme and achieves the joint distribution modeling of structures and attributes by distribution matching techniques. It could not only perform the link prediction task but also the newly introduced node attribute completion task. Furthermore, practical measures are introduced to quantify the performance of node attribute completion. Extensive experiments on seven real-world datasets indicate SAT shows better performance than other methods on both link prediction and node attribute completion tasks. [ABSTRACT FROM AUTHOR]

Background: Protein structure comparison and classification is an effective method for exploring protein structurefunction relations. This problem is computationally challenging. Many different computational approaches for protein structure comparison apply the secondary structure elements (SSEs) representation of protein structures. Results: We study the complexity of the protein structure comparison problem based on a mixed-graph model with respect to different computational frameworks. We develop an effective approach for protein structure comparison based on a novel independent set enumeration algorithm. Our approach (named: ePC, efficient enumeration-based Protein structure Comparison) is tested for general purpose protein structure comparison as well as for specific protein examples. Compared with other graph-based approaches for protein structure comparison, the theoretical running-time O(1.47rnn²) of our approach ePC is significantly better, where n is the smaller number of SSEs of the two proteins, r is a parameter of small value. Conclusion: Through the enumeration algorithm, our approach can identify different substructures from a list of high-scoring solutions of biological interest. Our approach is flexible to conduct protein structure comparison with the SSEs in sequential and non-sequential order as well. [ABSTRACT FROM AUTHOR]

Embedding an interconnection network into another network is one of the important problems in parallel processing. In this paper, we study embedding of linear arrays (paths) of maximum length in O-shaped meshes (O-shaped grid graphs). This is equal to finding a longest path in an O-shaped mesh (grid graph). An O-shaped mesh is a 2D mesh that a smaller 2D mesh is removed from it. The removed nodes can be considered as faulty processor. We give a linear-time parallel algorithm for this problem. To show the algorithm finds an optimal path, first we prove some upper bounds on the length of the longest paths, then we show that how our algorithm meets these upper bounds. [ABSTRACT FROM AUTHOR]

Motivation We explore the use of literature-curated signed causal gene expression and gene–function relationships to construct unsupervised embeddings of genes, biological functions and diseases. Our goal is to prioritize and predict activating and inhibiting functional associations of genes and to discover hidden relationships between functions. As an application, we are particularly interested in the automatic construction of networks that capture relevant biology in a given disease context. Results We evaluated several unsupervised gene embedding models leveraging literature-curated signed causal gene expression findings. Using linear regression, we show that, based on these gene embeddings, gene–function relationships can be predicted with about 95% precision for the highest scoring genes. Function embedding vectors, derived from parameters of the linear regression model, allow inference of relationships between different functions or diseases. We show for several diseases that gene and function embeddings can be used to recover key drivers of pathogenesis, as well as underlying cellular and physiological processes. These results are presented as disease-centric networks of genes and functions. To illustrate the applicability of our approach to other machine learning tasks, we also computed embeddings for drug molecules, which were then tested using a simple neural network to predict drug–disease associations. Availability and implementation Python implementations of the gene and function embedding algorithms operating on a subset of our literature-curated content as well as other code used for this paper are made available as part of the Supplementary data. Supplementary information Supplementary data are available at Bioinformatics Advances online. [ABSTRACT FROM AUTHOR]

Embedding static graphs in low-dimensional vector spaces plays a key role in network analytics and inference, supporting applications like node classification, link prediction, and graph visualization. However, many real-world networks present dynamic behavior, including topological evolution, feature evolution, and diffusion. Therefore, several methods for embedding dynamic graphs have been proposed to learn network representations over time, facing novel challenges, such as time-domain modeling, temporal features to be captured, and the temporal granularity to be embedded. In this survey, we overview dynamic graph embedding, discussing its fundamentals and the recent advances developed so far. We introduce the formal definition of dynamic graph embedding, focusing on the problem setting and introducing a novel taxonomy for dynamic graph embedding input and output. We further explore different dynamic behaviors that may be encompassed by embeddings, classifying by topological evolution, feature evolution, and processes on networks. Afterward, we describe existing techniques and propose a taxonomy for dynamic graph embedding techniques based on algorithmic approaches, from matrix and tensor factorization to deep learning, random walks, and temporal point processes. We also elucidate main applications, including dynamic link prediction, anomaly detection, and diffusion prediction, and we further state some promising research directions in the area. [ABSTRACT FROM AUTHOR]

A graph embedding algorithm embeds a graph into a low-dimensional space such that the embedding preserves the inherent properties of the graph. While graph embedding is fundamentally related to graph visualization, prior work did not exploit this connection explicitly. We develop Force2Vec that uses force-directed graph layout models in a graph embedding setting with an aim to excel in both machine learning (ML) and visualization tasks. We make Force2Vec highly parallel by mapping its core computations to linear algebra and utilizing multiple levels of parallelism available in modern processors. The resultant algorithm is an order of magnitude faster than existing methods (43 × faster than DeepWalk, on average) and can generate embeddings from graphs with billions of edges in a few hours. In comparison to existing methods, Force2Vec is better in graph visualization and performs comparably or better in ML tasks such as link prediction, node classification, and clustering. Source code is available at https://github.com/HipGraph/Force2Vec.This paper is an extension of a conference paper by Rahman et al. (in: 20th IEEE international conference on data mining, IEEE ICDM, 2020b) published in IEEE ICDM 2020. [ABSTRACT FROM AUTHOR]

Graph is a natural data structure for describing complex systems, which contains a set of objects and relationships. Ubiquitous real-life biomedical problems can be modeled as graph analytics tasks. Machine learning, especially deep learning, succeeds in vast bioinformatics scenarios with data represented in Euclidean domain. However, rich relational information between biological elements is retained in the non-Euclidean biomedical graphs, which is not learning friendly to classic machine learning methods. Graph representation learning aims to embed graph into a low-dimensional space while preserving graph topology and node properties. It bridges biomedical graphs and modern machine learning methods and has recently raised widespread interest in both machine learning and bioinformatics communities. In this work, we summarize the advances of graph representation learning and its representative applications in bioinformatics. To provide a comprehensive and structured analysis and perspective, we first categorize and analyze both graph embedding methods (homogeneous graph embedding, heterogeneous graph embedding, attribute graph embedding) and graph neural networks. Furthermore, we summarize their representative applications from molecular level to genomics, pharmaceutical and healthcare systems level. Moreover, we provide open resource platforms and libraries for implementing these graph representation learning methods and discuss the challenges and opportunities of graph representation learning in bioinformatics. This work provides a comprehensive survey of emerging graph representation learning algorithms and their applications in bioinformatics. It is anticipated that it could bring valuable insights for researchers to contribute their knowledge to graph representation learning and future-oriented bioinformatics studies. [ABSTRACT FROM AUTHOR]

Graph machine learning (GML) is receiving growing interest within the pharmaceutical and biotechnology industries for its ability to model biomolecular structures, the functional relationships between them, and integrate multi-omic datasets — amongst other data types. Herein, we present a multidisciplinary academic-industrial review of the topic within the context of drug discovery and development. After introducing key terms and modelling approaches, we move chronologically through the drug development pipeline to identify and summarize work incorporating: target identification, design of small molecules and biologics, and drug repurposing. Whilst the field is still emerging, key milestones including repurposed drugs entering in vivo studies, suggest GML will become a modelling framework of choice within biomedical machine learning. [ABSTRACT FROM AUTHOR]

A string p=p0p1⋯pn−1 of non-negative integers is a Euclidean string if the string (p0+1)p1⋯(pn−1−1) is rotationally equivalent (i.e., conjugate) to p. We show that Euclidean strings exist if and only if n and p0+p1+⋯+pn−1 are relatively prime and that, if they exist, they are unique. We show how to construct them using an algorithm with the same structure as the Euclidean algorithm, hence the name. We show that Euclidean strings are Lyndon words and we describe relationships between Euclidean strings and the Stern–Brocot tree, Fibonacci strings, Beatty sequences, and Sturmian sequences. We also describe an application to a graph embedding problem. [Copyright &y& Elsevier]

In this paper, we compute the wirelength of embedding Recursive Circulants RC(2n, 4) into Circular Necklace. Further, we identify a set of edges S in RC(2n, 4) such that the wirelength of embedding RC(2n, 4)\S into circular necklace is minimum. [ABSTRACT FROM AUTHOR]

In the first days of social networking, the typical view of a community was a set of user profiles of the same interests and likes, and this community kept enlarging by searching, proposing, and adding new members with the same characteristics that were likely to interfere with the existing members. Today, things have changed dramatically. Social networking platforms are not restricted to forming similar user profiles: The vast amounts of data produced every day have given opportunities to predict and suggest relationships, behaviors, and everyday activities like shopping, food, traveling destinations, etc. Every day, vast data amounts are generated by the famous social networks such as Facebook, Twitter, Instagram, and so on. For example, Facebook alone generates 4 petabytes of data per day. The analysis of such data is of high importance to many aspects like recommendation systems, businesses, health organizations, etc. The community detection problem received considerable attention a long time ago. Communities are represented as clusters of an entire network. Most of the community detection techniques are based on graph structures. In this paper, we present the recent advances of deep learning techniques for community detection. We describe the most recent strategies presented in this field, and we provide some general discussion and some future trends. [ABSTRACT FROM AUTHOR]

The Internet of Vehicles (IoV) has a typical Internet of things architecture, which is the specific application of Internet of things (IoT) technology in the field of intelligent transportation. Virtual network embedding (VNE) is the effective allocation of physical network resources to the virtual network, and is a virtualization technology widely used in the data center of the IoV. The existing VNE algorithm ignores the attributes of the network itself. It only allocates resources according to the order in which the requests arrive, resulting in the problem of low utilization of physical resources. In this paper, we propose an efficient topology control scheme for mobile nodes in IoVs. We firstly present a novel hierarchy-based dynamic VNE model for IoV. Then a VNE algorithm based on hierarchical priority is established by considering the attributes of virtual network requests. Finally, a global resource capacity based dynamic VNE algorithm is designed. Compared with precious VNE algorithms, the proposed algorithm has a 19 percent to 23 percent increase in the resource utilization rate of nodes, and elevates the overall request acceptance rate and revenue overhead, and can reduce the average waiting time of virtual network requests. [ABSTRACT FROM AUTHOR]

Graph embedding is a powerful method in parallel computing that maps a guest network G into a host network H. The performance of an embedding can be evaluated by certain parameters, such as the dilation, the edge congestion and the wirelength. In this manuscript, we obtain the wirelength (exact and minimum) of embedding complete multi-partite graphs into Cartesian product of paths and/or cycles, which include n-cube, n-dimensional mesh (grid), n-dimensional cylinder and ndimensional torus, etc., as the subfamilies. [ABSTRACT FROM AUTHOR]

Deployment of 100 Gigabit Ethernet (GbE) links challenges the packet processing limits of commodity hardware used for Network Functions Virtualization (NFV). Moreover, realizing chained network functions (i.e., service chains) necessitates the use of multiple CPU cores, or even multiple servers, to process packets from such high speed links. Our system Metron jointly exploits the underlying network and commodity servers' resources: (i) to offload part of the packet processing logic to the network, (ii) by using smart tagging to setup and exploit the affinity of traffic classes, and (iii) by using tag-based hardware dispatching to carry out the remaining packet processing at the speed of the servers' cores, with zero inter-core communication. Moreover, Metron transparently integrates, manages, and load balances proprietary "blackboxes" together with Metron service chains. Metron realizes stateful network functions at the speed of 100 GbE network cards on a single server, while elastically and rapidly adapting to changing workload volumes. Our experiments demonstrate that Metron service chains can coexist with heterogeneous blackboxes, while still leveraging Metron's accurate dispatching and load balancing. In summary, Metron has (i) 2.75-8× better efficiency, up to (ii) 4.7× lower latency, and (iii) 7.8× higher throughput than OpenBox, a state-of-the-art NFV system. [ABSTRACT FROM AUTHOR]

Curves play a fundamental role across computer graphics, physical simulation, and mathematical visualization, yet most tools for curve design do nothing to prevent crossings or self-intersections. This article develops efficient algorithms for (self-)repulsion of plane and space curves that are well-suited to problems in computational design. Our starting point is the so-called tangent-point energy, which provides an infinite barrier to self-intersection. In contrast to local collision detection strategies used in, e.g., physical simulation, this energy considers interactions between all pairs of points, and is hence useful for global shape optimization: local minima tend to be aesthetically pleasing, physically valid, and nicely distributed in space. A reformulation of gradient descent based on a Sobolev-Slobodeckij inner product enables us to make rapid progress toward local minima—independent of curve resolution. We also develop a hierarchical multigrid scheme that significantly reduces the per-step cost of optimization. The energy is easily integrated with a variety of constraints and penalties (e.g., inextensibility, or obstacle avoidance), which we use for applications including curve packing, knot untangling, graph embedding, non-crossing spline interpolation, flow visualization, and robotic path planning. [ABSTRACT FROM AUTHOR]

The available spatial data are rapidly growing and also diversifying. One may obtain in large quantities information such as annotated point/place of interest (POIs), check-in comments on those POIs, geo-tagged microblog comments, and demarked regions of interest (ROI). All sources interplay with each other, and together build a more complete picture of the spatial and social dynamics at play in a region. However, building a single fused representation of these data entries has been mainly rudimentary, such as allowing spatial joins. In this paper, we extend the concept of semantic embedding for POIs (points of interests) and devise the first semantic embedding of ROIs, and in particular ones that captures both its spatial and its semantic components. To accomplish this, we develop a multipart network model capturing the relationships between the diverse components, and through random-walk-based approaches, use this to embed the ROIs. We demonstrate the effectiveness of this embedding at simultaneously capturing both the spatial and semantic relationships between ROIs through extensive experiments. Applications like popularity region prediction demonstrate the benefit of using ROI embedding as features in comparison with baselines. [ABSTRACT FROM AUTHOR]

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 · 2s 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]