More Like this

1. Source Relationships and Model Structures Determine Information Flow Paths in Ecohydrologic Models

   https://doi.org/10.1029/2021WR031164  

   Goodwell, Allison E.; Bassiouni, Maoya (September 2022, Water Resources Research)

   Abstract In a complex ecohydrologic system, vegetation and soil variables combine to dictate heat fluxes, and these fluxes may vary depending on the extent to which drivers are linearly or nonlinearly interrelated. From a modeling and causality perspective, uncertainty, sensitivity, and performance measures all relate to how information from different sources “flows” through a model to produce a target, or output. We address how model structure, broadly defined as a mapping from inputs to an output, combines with source dependencies to produce a range of information flow pathways from sources to a target. We apply information decomposition, which partitions reductions in uncertainty into synergistic, redundant, and unique information types, to a range of model cases. Toy models show that model structure and source dependencies both restrict the types of interactions that can arise between sources and targets. Regressions based on weather data illustrate how different model structures vary in their sensitivity to source dependencies, thus affecting predictive and functional performance. Finally, we compare the Surface Flux Equilibrium theory, a land‐surface model, and neural networks in estimating the Bowen ratio and find that models trade off information types particularly when sources have the highest and lowest dependencies. Overall, this study extends an information theory‐based model evaluation framework to incorporate the influence of source dependency on information pathways. This could be applied to explore behavioral ranges for both machine learning and process‐based models, and guide model development by highlighting model deficiencies based on information flow pathways that would not be apparent based on existing measures. 

   more » « less
2. Knowledgebra: An Algebraic Learning Framework for Knowledge Graph

   https://doi.org/10.3390/make4020019  

   Yang, Tong; Wang, Yifei; Sha, Long; Engelbrecht, Jan; Hong, Pengyu (June 2022, Machine Learning and Knowledge Extraction)

   Knowledge graph (KG) representation learning aims to encode entities and relations into dense continuous vector spaces such that knowledge contained in a dataset could be consistently represented. Dense embeddings trained from KG datasets benefit a variety of downstream tasks such as KG completion and link prediction. However, existing KG embedding methods fell short to provide a systematic solution for the global consistency of knowledge representation. We developed a mathematical language for KG based on an observation of their inherent algebraic structure, which we termed as Knowledgebra. By analyzing five distinct algebraic properties, we proved that the semigroup is the most reasonable algebraic structure for the relation embedding of a general knowledge graph. We implemented an instantiation model, SemE, using simple matrix semigroups, which exhibits state-of-the-art performance on standard datasets. Moreover, we proposed a regularization-based method to integrate chain-like logic rules derived from human knowledge into embedding training, which further demonstrates the power of the developed language. As far as we know, by applying abstract algebra in statistical learning, this work develops the first formal language for general knowledge graphs, and also sheds light on the problem of neural-symbolic integration from an algebraic perspective. 

   more » « less
3. Unbiased pangenome graphs

   https://doi.org/10.1093/bioinformatics/btac743  

   Garrison, Erik; Guarracino, Andrea (November 2022, Bioinformatics)

   Alkan, Can (Ed.)

   Abstract Motivation Pangenome variation graphs model the mutual alignment of collections of DNA sequences. A set of pairwise alignments implies a variation graph, but there are no scalable methods to generate such a graph from these alignments. Existing related approaches depend on a single reference, a specific ordering of genomes or a de Bruijn model based on a fixed k-mer length. A scalable, self-contained method to build pangenome graphs without such limitations would be a key step in pangenome construction and manipulation pipelines. Results We design the seqwish algorithm, which builds a variation graph from a set of sequences and alignments between them. We first transform the alignment set into an implicit interval tree. To build up the variation graph, we query this tree-based representation of the alignments to reduce transitive matches into single DNA segments in a sequence graph. By recording the mapping from input sequence to output graph, we can trace the original paths through this graph, yielding a pangenome variation graph. We present an implementation that operates in external memory, using disk-backed data structures and lock-free parallel methods to drive the core graph induction step. We demonstrate that our method scales to very large graph induction problems by applying it to build pangenome graphs for several species. Availability and implementation seqwish is published as free software under the MIT open source license. Source code and documentation are available at https://github.com/ekg/seqwish. seqwish can be installed via Bioconda https://bioconda.github.io/recipes/seqwish/README.html or GNU Guix https://github.com/ekg/guix-genomics/blob/master/seqwish.scm. 

   more » « less
4. Validating Paired-end Read Alignments in Sequence Graphs

   https://doi.org/10.1101/682799  

   Jain, Chirag; Zhang, Haowen; Dilthey, Alexander; Aluru, Srinivas (September 2019, Leibniz international proceedings in informatics)

   Graph based non-linear reference structures such as variation graphs and colored de Bruijn graphs enable incorporation of full genomic diversity within a population. However, transitioning from a simple string-based reference to graphs requires addressing many computational challenges, one of which concerns accurately mapping sequencing read sets to graphs. Paired-end Illumina sequencing is a commonly used sequencing platform in genomics, where the paired-end distance constraints allow disambiguation of repeats. Many recent works have explored provably good index-based and alignment-based strategies for mapping individual reads to graphs. However, validating distance constraints efficiently over graphs is not trivial, and existing sequence to graph mappers rely on heuristics. We introduce a mathematical formulation of the problem, and provide a new algorithm to solve it exactly. We take advantage of the high sparsity of reference graphs, and use sparse matrix-matrix multiplications (SpGEMM) to build an index which can be queried efficiently by a mapping algorithm for validating the distance constraints. Effectiveness of the algorithm is demonstrated using real reference graphs, including a human MHC variation graph, and a pan-genome de-Bruijn graph built using genomes of 20 B. anthracis strains. While the one-time indexing time can vary from a few minutes to a few hours using our algorithm, answering a million distance queries takes less than a second. 

   more » « less
5. Mycelium: Large-Scale Distributed Graph Queries with Differential Privacy

   https://doi.org/10.1145/3477132.3483585  

   Roth, Edo; Newatia, Karan; Ma, Yiping; Zhong, Ke; Angel, Sebastian; Haeberlen, Andreas (October 2021, ACM SIGOPS Symposium on Operating Systems Principles (SOSP))

   This paper introduces Mycelium, the first system to process differentially private queries over large graphs that are distributed across millions of user devices. Such graphs occur, for instance, when tracking the spread of diseases or malware. Today, the only practical way to query such graphs is to upload them to a central aggregator, which requires a great deal of trust from users and rules out certain types of studies entirely. With Mycelium, users' private data never leaves their personal devices unencrypted, and each user receives strong privacy guarantees. Mycelium does require the help of a central aggregator with access to a data center, but the aggregator merely facilitates the computation by providing bandwidth and computation power; it never learns the topology of the graph or the underlying data. Mycelium accomplishes this with a combination of homomorphic encryption, a verifiable secret redistribution scheme, and a mix network based on telescoping circuits. Our evaluation shows that Mycelium can answer a range of different questions from the medical literature with millions of devices. 

   more » « less