Influence of Random Walk Parametrization on Graph Embeddings
Ontology highlight
ABSTRACT:
SUBMITTER: Jose J
PROVIDER: S-EPMC7148094 | biostudies-literature | 2020 Mar
REPOSITORIES: biostudies-literature
Similar Datasets
Project description:Graph representation learning methods opened new avenues for addressing complex, real-world problems represented by graphs. However, many graphs used in these applications comprise millions of nodes and billions of edges and are beyond the capabilities of current methods and software implementations. We present GRAPE (Graph Representation Learning, Prediction and Evaluation), a software resource for graph processing and embedding that is able to scale with big graphs by using specialized and smart data structures, algorithms, and a fast parallel implementation of random-walk-based methods. Compared with state-of-the-art software resources, GRAPE shows an improvement of orders of magnitude in empirical space and time complexity, as well as competitive edge- and node-label prediction performance. GRAPE comprises approximately 1.7 million well-documented lines of Python and Rust code and provides 69 node-embedding methods, 25 inference models, a collection of efficient graph-processing utilities, and over 80,000 graphs from the literature and other sources. Standardized interfaces allow a seamless integration of third-party libraries, while ready-to-use and modular pipelines permit an easy-to-use evaluation of graph-representation-learning methods, therefore also positioning GRAPE as a software resource that performs a fair comparison between methods and libraries for graph processing and embedding.
| S-EPMC10768636 | biostudies-literature
Project description:MotivationDespite recent advancements in sequencing technologies and assembly methods, obtaining high-quality microbial genomes from metagenomic samples is still not a trivial task. Current metagenomic binners do not take full advantage of assembly graphs and are not optimized for long-read assemblies. Deep graph learning algorithms have been proposed in other fields to deal with complex graph data structures. The graph structure generated during the assembly process could be integrated with contig features to obtain better bins with deep learning.ResultsWe propose GraphMB, which uses graph neural networks to incorporate the assembly graph into the binning process. We test GraphMB on long-read datasets of different complexities, and compare the performance with other binners in terms of the number of High Quality (HQ) genome bins obtained. With our approach, we were able to obtain unique bins on all real datasets, and obtain more bins on most datasets. In particular, we obtained on average 17.5% more HQ bins when compared with state-of-the-art binners and 13.7% when aggregating the results of our binner with the others. These results indicate that a deep learning model can integrate contig-specific and graph-structure information to improve metagenomic binning.Availability and implementationGraphMB is available from https://github.com/MicrobialDarkMatter/GraphMB.Supplementary informationSupplementary data are available at Bioinformatics online.
| S-EPMC9525014 | biostudies-literature
Project description:MotivationGraph representation learning is a family of related approaches that learn low-dimensional vector representations of nodes and other graph elements called embeddings. Embeddings approximate characteristics of the graph and can be used for a variety of machine-learning tasks such as novel edge prediction. For many biomedical applications, partial knowledge exists about positive edges that represent relationships between pairs of entities, but little to no knowledge is available about negative edges that represent the explicit lack of a relationship between two nodes. For this reason, classification procedures are forced to assume that the vast majority of unlabeled edges are negative. Existing approaches to sampling negative edges for training and evaluating classifiers do so by uniformly sampling pairs of nodes.ResultsWe show here that this sampling strategy typically leads to sets of positive and negative examples with imbalanced node degree distributions. Using representative heterogeneous biomedical knowledge graph and random walk-based graph machine learning, we show that this strategy substantially impacts classification performance. If users of graph machine-learning models apply the models to prioritize examples that are drawn from approximately the same distribution as the positive examples are, then performance of models as estimated in the validation phase may be artificially inflated. We present a degree-aware node sampling approach that mitigates this effect and is simple to implement.Availability and implementationOur code and data are publicly available at https://github.com/monarch-initiative/negativeExampleSelection.
| S-EPMC10994718 | biostudies-literature
Project description:Restrictions to molecular motion by barriers (membranes) are ubiquitous in porous media, composite materials and biological tissues. A major challenge is to characterize the microstructure of a material or an organism nondestructively using a bulk transport measurement. Here we demonstrate how the long-range structural correlations introduced by permeable membranes give rise to distinct features of transport. We consider Brownian motion restricted by randomly placed and oriented membranes (d - 1 dimensional planes in d dimensions) and focus on the disorder-averaged diffusion propagator using a scattering approach. The renormalization group solution reveals a scaling behavior of the diffusion coefficient for large times, with a characteristically slow inverse square root time dependence for any d. Its origin lies in the strong structural fluctuations introduced by the spatially extended random restrictions, representing a novel universality class of the structural disorder. Our results agree well with Monte Carlo simulations in two dimensions. They can be used to identify permeable barriers as restrictions to transport, and to quantify their permeability and surface area.
| S-EPMC3114643 | biostudies-other
Project description:Learning embeddings of entities and relations existing in knowledge bases allows the discovery of hidden patterns in them. In this work, we examine the contribution of geometrical space to the task of knowledge base completion. We focus on the family of translational models, whose performance has been lagging. We extend these models to the hyperbolic space so as to better reflect the topological properties of knowledge bases. We investigate the type of regularities that our model, dubbed HyperKG, can capture and show that it is a prominent candidate for effectively representing a subset of Datalog rules. We empirically show, using a variety of link prediction datasets, that hyperbolic space allows to narrow down significantly the performance gap between translational and bilinear models and effectively represent certain types of rules. Electronic supplementary material The online version of this chapter (10.1007/978-3-030-49461-2_12) contains supplementary material, which is available to authorized users.
| S-EPMC7250606 | biostudies-literature
Project description:Random walkers on a two-dimensional square lattice are used to explore the spatio-temporal growth of an epidemic. We have found that a simple random-walk system generates non-trivial dynamics compared with traditional well-mixed models. Phase diagrams characterizing the long-term behaviors of the epidemics are calculated numerically. The functional dependence of the basic reproductive number [Formula: see text] on the model's defining parameters reveals the role of spatial fluctuations and leads to a novel expression for [Formula: see text]. Special attention is given to simulations of inter-regional transmission of the contagion. The scaling of the epidemic with respect to space and time scales is studied in detail in the critical region, which is shown to be compatible with the directed-percolation universality class.
| S-EPMC8481482 | biostudies-literature
Project description:BackgroundCancer as a worldwide problem is driven by genomic alterations. With the advent of high-throughput sequencing technology, a huge amount of genomic data generates at every second which offer many valuable cancer information and meanwhile throw a big challenge to those investigators. As the major characteristic of cancer is heterogeneity and most of alterations are supposed to be useless passenger mutations that make no contribution to the cancer progress. Hence, how to dig out driver genes that have effect on a selective growth advantage in tumor cells from those tremendously and noisily data is still an urgent task.ResultsConsidering previous network-based method ignoring some important biological properties of driver genes and the low reliability of gene interactive network, we proposed a random walk method named as Subdyquency that integrates the information of subcellular localization, variation frequency and its interaction with other dysregulated genes to improve the prediction accuracy of driver genes. We applied our model to three different cancers: lung, prostate and breast cancer. The results show our model can not only identify the well-known important driver genes but also prioritize the rare unknown driver genes. Besides, compared with other existing methods, our method can improve the precision, recall and fscore to a higher level for most of cancer types.ConclusionsThe final results imply that driver genes are those prone to have higher variation frequency and impact more dysregulated genes in the common significant compartment.AvailabilityThe source code can be obtained at https://github.com/weiba/Subdyquency .
| S-EPMC6518800 | biostudies-literature
Project description:In this paper we present a method to examine the synchrony between brains without the need to carry out simultaneous recordings of EEG signals from two people which is the essence of hyper-scanning studies. We used anonymous random walks to spatially encode the entire graph structure without relying on data at the level of individual nodes. Anonymous random walks enabled us to encapsulate the structure of a graph regardless of the specific node labels. That is, random walks that visited different nodes in the same sequence resulted in the same anonymous walk encoding. We have analyzed the EEG data offline and matched each possible pair of players from the entire pool of players that performed a series of tacit coordination games. Specifically, we compared between two network patterns associated with each possible pair of players. By using classification performed on the spatial distance between each pair of individual brain patterns, analyzed by the random walk algorithm, we tried to predict whether each possible pair of players has managed to converge on the same solution in each tacit coordination game. Specifically, the distance between a pair of vector embeddings, each associated with one of the players, was used as input for a classification model for the purpose of predicting whether the two corresponding players have managed to achieve successful coordination. Our model reached a classification accuracy of ~85%.
| S-EPMC10358924 | biostudies-literature
Project description:We introduce methods for estimating the spectral density of a random field on a [Formula: see text]-dimensional lattice from incomplete gridded data. Data are iteratively imputed onto an expanded lattice according to a model with a periodic covariance function. The imputations are convenient computationally, in that circulant embedding and preconditioned conjugate gradient methods can produce imputations in [Formula: see text] time and [Formula: see text] memory. However, these so-called periodic imputations are motivated mainly by their ability to produce accurate spectral density estimates. In addition, we introduce a parametric filtering method that is designed to reduce periodogram smoothing bias. The paper contains theoretical results on properties of the imputed-data periodogram and numerical and simulation studies comparing the performance of the proposed methods to existing approaches in a number of scenarios. We present an application to a gridded satellite surface temperature dataset with missing values.
| S-EPMC6508039 | biostudies-literature
Project description:Chromosome conformation capture experiments result in pairwise proximity measurements between chromosome locations in a genome, and they have been used to construct three-dimensional models of genomic regions, chromosomes, and entire genomes. These models can be used to understand long-range gene regulation, chromosome rearrangements, and the relationships between sequence and spatial location. However, it is unclear whether these pairwise distance constraints provide sufficient information to embed chromatin in three dimensions. A priori, it is possible that an infinite number of embeddings are consistent with the measurements due to a lack of constraints between some regions. It is therefore necessary to separate regions of the chromatin structure that are sufficiently constrained from regions with measurements that do not provide enough information to reconstruct the embedding.We present a new method based on graph rigidity to assess the suitability of experiments for constructing plausible three-dimensional models of chromatin structure. Underlying this analysis is a new, efficient, and accurate algorithm for finding sufficiently constrained (rigid) collections of constraints in three dimensions, a problem for which there is no known efficient algorithm. Applying the method to four recent chromosome conformation experiments, we find that, for even stringently filtered constraints, a large rigid component spans most of the measured region. Filtering highlights higher-confidence regions, and we find that the organization of these regions depends crucially on short-range interactions.Without performing an embedding or creating a frequency-to-distance mapping, our proposed approach establishes which substructures are supported by a sufficient framework of interactions. It also establishes that interactions from recent highly filtered genome-wide chromosome conformation experiments provide an adequate set of constraints for embedding. Pre-processing experimentally observed interactions with this method before relating chromatin structure to biological phenomena will ensure that hypothesized correlations are not driven by the arbitrary choice of a particular unconstrained embedding. The software for identifying rigid components is GPL-Licensed and available for download at http://cbcb.umd.edu/kingsford-group/starfish.
| S-EPMC3577487 | biostudies-literature