Dynamic graphs, community detection, and Riemannian geometry.
Ontology highlight
ABSTRACT:
SUBMITTER: Bakker C
PROVIDER: S-EPMC6214282 | biostudies-literature | 2018
REPOSITORIES: biostudies-literature
Publications
Dynamic graphs, community detection, and Riemannian geometry.
Bakker Craig C Halappanavar Mahantesh M Visweswara Sathanur Arun A
Applied network science 20180329 1
A community is a subset of a wider network where the members of that subset are more strongly connected to each other than they are to the rest of the network. In this paper, we consider the problem of identifying and tracking communities in graphs that change over time - dynamic community detection - and present a framework based on Riemannian geometry to aid in this task. Our framework currently supports several important operations such as interpolating between and averaging over graph snapsh ...[more]
Similar Datasets
Project description:Inter-temporal decisions involves assigning values to various payoffs occurring at different temporal distances. Past research has used different approaches to study these decisions made by humans and animals. For instance, considering that people discount future payoffs at a constant rate (e.g., exponential discounting) or at variable rate (e.g., hyperbolic discounting). In this research, we question the widely assumed, but seldom questioned, notion across many of the existing approaches that the decision space, where the decision-maker perceives time and monetary payoffs, is a Euclidean space. By relaxing the rigid assumption of Euclidean space, we propose that the decision space is a more flexible Riemannian space of Constant Negative Curvature. We test our proposal by deriving a discount function, which uses the distance in the Negative Curvature space instead of Euclidean temporal distance. The distance function includes both perceived values of time as well as money, unlike past work which has considered just time. By doing so we are able to explain many of the empirical findings in inter-temporal decision-making literature. We provide converging evidence for our proposal by estimating the curvature of the decision space utilizing manifold learning algorithm and showing that the characteristics (i.e., metric properties) of the decision space resembles those of the Negative Curvature space rather than the Euclidean space. We conclude by presenting new theoretical predictions derived from our proposal and implications for how non-normative behavior is defined.
| S-EPMC4809573 | biostudies-literature
Project description:When non-linear models are fitted to experimental data, parameter estimates can be poorly constrained albeit being identifiable in principle. This means that along certain paths in parameter space, the log-likelihood does not exceed a given statistical threshold but remains bounded. This situation, denoted as practical non-identifiability, can be detected by Monte Carlo sampling or by systematic scanning using the profile likelihood method. In contrast, any method based on a Taylor expansion of the log-likelihood around the optimum, e.g., parameter uncertainty estimation by the Fisher Information Matrix, reveals no information about the boundedness at all. In this work, we present a geometric approach, approximating the original log-likelihood by geodesic coordinates of the model manifold. The Christoffel Symbols in the geodesic equation are fixed to those obtained from second order model sensitivities at the optimum. Based on three exemplary non-linear models we show that the information about the log-likelihood bounds and flat parameter directions can already be contained in this local information. Whereas the unbounded case represented by the Fisher Information Matrix is embedded in the geometric framework as vanishing Christoffel Symbols, non-vanishing constant Christoffel Symbols prove to define prototype non-linear models featuring boundedness and flat parameter directions of the log-likelihood. Finally, we investigate if those models could allow to approximate and replace computationally expensive objective functions originating from non-linear models by a surrogate objective function in parameter estimation problems.
| S-EPMC6546239 | biostudies-literature
Project description:MotivationThe field of geometric deep learning has recently had a profound impact on several scientific domains such as protein structure prediction and design, leading to methodological advancements within and outside of the realm of traditional machine learning. Within this spirit, in this work, we introduce GCPNet, a new chirality-aware SE(3)-equivariant graph neural network designed for representation learning of 3D biomolecular graphs. We show that GCPNet, unlike previous representation learning methods for 3D biomolecules, is widely applicable to a variety of invariant or equivariant node-level, edge-level, and graph-level tasks on biomolecular structures while being able to (1) learn important chiral properties of 3D molecules and (2) detect external force fields.ResultsAcross four distinct molecular-geometric tasks, we demonstrate that GCPNet's predictions (1) for protein-ligand binding affinity achieve a statistically significant correlation of 0.608, more than 5%, greater than current state-of-the-art methods; (2) for protein structure ranking achieve statistically significant target-local and dataset-global correlations of 0.616 and 0.871, respectively; (3) for Newtownian many-body systems modeling achieve a task-averaged mean squared error less than 0.01, more than 15% better than current methods; and (4) for molecular chirality recognition achieve a state-of-the-art prediction accuracy of 98.7%, better than any other machine learning method to date.Availability and implementationThe source code, data, and instructions to train new models or reproduce our results are freely available at https://github.com/BioinfoMachineLearning/GCPNet.
| S-EPMC10904142 | biostudies-literature
Project description:BackgroundIdentification of transcription factor binding sites (also called 'motif discovery') in DNA sequences is a basic step in understanding genetic regulation. Although many successful programs have been developed, the problem is far from being solved on account of diversity in gene expression/regulation and the low specificity of binding sites. State-of-the-art algorithms have their own constraints (e.g., high time or space complexity for finding long motifs, low precision in identification of weak motifs, or the OOPS constraint: one occurrence of the motif instance per sequence) which limit their scope of application.ResultsIn this paper, we present a novel and fast algorithm we call TFBSGroup. It is based on community detection from a graph and is used to discover long and weak (l,d) motifs under the ZOMOPS constraint (zero, one or multiple occurrence(s) of the motif instance(s) per sequence), where l is the length of a motif and d is the maximum number of mutations between a motif instance and the motif itself. Firstly, TFBSGroup transforms the (l, d) motif search in sequences to focus on the discovery of dense subgraphs within a graph. It identifies these subgraphs using a fast community detection method for obtaining coarse-grained candidate motifs. Next, it greedily refines these candidate motifs towards the true motif within their own communities. Empirical studies on synthetic (l, d) samples have shown that TFBSGroup is very efficient (e.g., it can find true (18, 6), (24, 8) motifs within 30 seconds). More importantly, the algorithm has succeeded in rapidly identifying motifs in a large data set of prokaryotic promoters generated from the Escherichia coli database RegulonDB. The algorithm has also accurately identified motifs in ChIP-seq data sets for 12 mouse transcription factors involved in ES cell pluripotency and self-renewal.ConclusionsOur novel heuristic algorithm, TFBSGroup, is able to quickly identify nearly exact matches for long and weak (l, d) motifs in DNA sequences under the ZOMOPS constraint. It is also capable of finding motifs in real applications. The source code for TFBSGroup can be obtained from http://bioinformatics.bioengr.uic.edu/TFBSGroup/.
| S-EPMC3726413 | biostudies-literature
Project description:We describe techniques for the robust detection of community structure in some classes of time-dependent networks. Specifically, we consider the use of statistical null models for facilitating the principled identification of structural modules in semi-decomposable systems. Null models play an important role both in the optimization of quality functions such as modularity and in the subsequent assessment of the statistical validity of identified community structure. We examine the sensitivity of such methods to model parameters and show how comparisons to null models can help identify system scales. By considering a large number of optimizations, we quantify the variance of network diagnostics over optimizations ("optimization variance") and over randomizations of network structure ("randomization variance"). Because the modularity quality function typically has a large number of nearly degenerate local optima for networks constructed using real data, we develop a method to construct representative partitions that uses a null model to correct for statistical noise in sets of partitions. To illustrate our results, we employ ensembles of time-dependent networks extracted from both nonlinear oscillators and empirical neuroscience data.
| S-EPMC3618100 | biostudies-other
Project description:Riemannian geometry-based classification (RGBC) gained popularity in the field of brain-computer interfaces (BCIs) lately, due to its ability to deal with non-stationarities arising in electroencephalography (EEG) data. Domain adaptation, however, is most often performed on sample covariance matrices (SCMs) obtained from EEG data, and thus might not fully account for components affecting covariance estimation itself, such as regional trends. Detrended cross-correlation analysis (DCCA) can be utilized to estimate the covariance structure of such signals, yet it is computationally expensive in its original form. A recently proposed online implementation of DCCA, however, allows for its fast computation and thus makes it possible to employ DCCA in real-time applications. In this study we propose to replace the SCM with the DCCA matrix as input to RGBC and assess its effect on offline and online BCI performance. First we evaluated the proposed decoding pipeline offline on previously recorded EEG data from 18 individuals performing left and right hand motor imagery (MI), and benchmarked it against vanilla RGBC and popular MI-detection approaches. Subsequently, we recruited eight participants (with previous BCI experience) who operated an MI-based BCI (MI-BCI) online using the DCCA-enhanced Riemannian decoder. Finally, we tested the proposed method on a public, multi-class MI-BCI dataset. During offline evaluations the DCCA-based decoder consistently and significantly outperformed the other approaches. Online evaluation confirmed that the DCCA matrix could be computed in real-time even for 22-channel EEG, as well as subjects could control the MI-BCI with high command delivery (normalized Cohen's κ: 0.7409 ± 0.1515) and sample-wise MI detection (normalized Cohen's κ: 0.5200 ± 0.1610). Post-hoc analysis indicated characteristic connectivity patterns under both MI conditions, with stronger connectivity in the hemisphere contralateral to the MI task. Additionally, fractal scaling exponent of neural activity was found increased in the contralateral compared to the ipsilateral motor cortices (C4 and C3 for left and right MI, respectively) in both classes. Combining DCCA with Riemannian geometry-based decoding yields a robust and effective decoder, that not only improves upon the SCM-based approach but can also provide relevant information on the neurophysiological processes behind MI.
| S-EPMC10973000 | biostudies-literature
Project description:Many systems exhibit complex temporal dynamics due to the presence of different processes taking place simultaneously. An important task in these systems is to extract a simplified view of their time-dependent network of interactions. Community detection in temporal networks usually relies on aggregation over time windows or consider sequences of different stationary epochs. For dynamics-based methods, attempts to generalize static-network methodologies also face the fundamental difficulty that a stationary state of the dynamics does not always exist. Here, we derive a method based on a dynamical process evolving on the temporal network. Our method allows dynamics that do not reach a steady state and uncovers two sets of communities for a given time interval that accounts for the ordering of edges in forward and backward time. We show that our method provides a natural way to disentangle the different dynamical scales present in a system with synthetic and real-world examples.
| S-EPMC9094665 | biostudies-literature
Project description:MotivationThe de Bruijn graph is one of the fundamental data structures for analysis of high throughput sequencing data. In order to be applicable to population-scale studies, it is essential to build and store the graph in a space- and time-efficient manner. In addition, due to the ever-changing nature of population studies, it has become essential to update the graph after construction, e.g. add and remove nodes and edges. Although there has been substantial effort on making the construction and storage of the graph efficient, there is a limited amount of work in building the graph in an efficient and mutable manner. Hence, most space efficient data structures require complete reconstruction of the graph in order to add or remove edges or nodes.ResultsIn this article, we present DynamicBOSS, a succinct representation of the de Bruijn graph that allows for an unlimited number of additions and deletions of nodes and edges. We compare our method with other competing methods and demonstrate that DynamicBOSS is the only method that supports both addition and deletion and is applicable to very large samples (e.g. greater than 15 billion k-mers). Competing dynamic methods, e.g. FDBG cannot be constructed on large scale datasets, or cannot support both addition and deletion, e.g. BiFrost.Availability and implementationDynamicBOSS is publicly available at https://github.com/baharpan/dynboss.Supplementary informationSupplementary data are available at Bioinformatics online.
| S-EPMC8337006 | biostudies-literature
Project description:The use of Riemannian geometry decoding algorithms in classifying electroencephalography-based motor-imagery brain-computer interfaces (BCIs) trials is relatively new and promises to outperform the current state-of-the-art methods by overcoming the noise and nonstationarity of electroencephalography signals. However, the related literature shows high classification accuracy on only relatively small BCI datasets. The aim of this paper is to provide a study of the performance of a novel implementation of the Riemannian geometry decoding algorithm using large BCI datasets. In this study, we apply several Riemannian geometry decoding algorithms on a large offline dataset using four adaptation strategies: baseline, rebias, supervised, and unsupervised. Each of these adaptation strategies is applied in motor execution and motor imagery for both scenarios 64 electrodes and 29 electrodes. The dataset is composed of four-class bilateral and unilateral motor imagery and motor execution of 109 subjects. We run several classification experiments and the results show that the best classification accuracy is obtained for the scenario where the baseline minimum distance to Riemannian mean has been used. The mean accuracy values up to 81.5% for motor execution, and up to 76.4% for motor imagery. The accurate classification of EEG trials helps to realize successful BCI applications that allow effective control of devices.
| S-EPMC10255410 | biostudies-literature
Project description:Most high-dimensional datasets are thought to be inherently low-dimensional-that is, data points are constrained to lie on a low-dimensional manifold embedded in a high-dimensional ambient space. Here, we study the viability of two approaches from differential geometry to estimate the Riemannian curvature of these low-dimensional manifolds. The intrinsic approach relates curvature to the Laplace-Beltrami operator using the heat-trace expansion and is agnostic to how a manifold is embedded in a high-dimensional space. The extrinsic approach relates the ambient coordinates of a manifold's embedding to its curvature using the Second Fundamental Form and the Gauss-Codazzi equation. We found that the intrinsic approach fails to accurately estimate the curvature of even a two-dimensional constant-curvature manifold, whereas the extrinsic approach was able to handle more complex toy models, even when confounded by practical constraints like small sample sizes and measurement noise. To test the applicability of the extrinsic approach to real-world data, we computed the curvature of a well-studied manifold of image patches and recapitulated its topological classification as a Klein bottle. Lastly, we applied the extrinsic approach to study single-cell transcriptomic sequencing (scRNAseq) datasets of blood, gastrulation, and brain cells to quantify the Riemannian curvature of scRNAseq manifolds.
| S-EPMC8307776 | biostudies-literature