25 papers · ranked by Valyu relevance
Yihong Zhang, Xinran Wei, Junshi Chen, Fusong Ju + 3 more
Evaluating high-dimensional integrals via deep hierarchical recurrences is a dominant cost in quantum chemistry. While CPUs manage these efficiently, GPUs suffer a critical mismatch: limited per-thread memory is quickly overwhelmed by an explosion of simultaneously live intermediate variables. As recurrence scales…
Yuting Zhang, Yi Han, Kai Wang, Wei Ni + 2 more
Large language models (LLMs) have been increasingly explored for graph computation, where tasks require reasoning over structured relationships and algorithmic operations. Yet, it remains unclear when LLMs can reliably support such computation and how they should be incorporated into graph-solving pipelines. Existing…
Authors not listed
Computational methods for predictive modeling have been increasingly utilized in the early stages of drug discovery to supplement high-throughput screening. The advent of highly efficient and complex machine learning architectures necessitates new methods of collating the plethora of topological, geometrical, and…
Schaad, Philipp, Ben-Nun, Tal + 2 more
Control flow graphs (CFGs) are essential tools for understanding program behavior, yet the size of real-world CFGs makes them difficult to interpret. With thousands of nodes and edges, sophisticated graph drawing algorithms are required to present them on screens in ways that make them readable and understandable.…
Authors not listed
Conventional molecular graphs often are unable to reliably encode stereochemistry, especially for symmetric molecules, non-tetrahedral centers, and transition states. To overcome this, we present StereoMolGraph, an open source Python library implementing a stereochemistry-aware graph representation for molecules and…
Zhenhan Huang, Tejaswini Pedapati, Pin‐Yu Chen, Chunheng Jiang + 1 more
Deep learning profoundly impacts various areas, such as face recognition and language translation. Owing to the increasingly high computational costs of training neural architectures, it is intractable to manually examine the performance of various neural architectures, promoting the area of Neural architecture search…
Alex Crane, Pål Grønås Drange, Eli Friedman, Paul D. Hovland + 5 more
The algorithmic differentiation (AD) of mathematical functions can be interpreted as a sequence of vertex eliminations in an underlying directed acyclic graph. The problem of determining a minimum-cost elimination ordering, which we call Optimal Vertex Elimination, is NP-complete. Consequently, much effort has been…
Xuran Cai, Amir Goharshady, S Hitarth, Chun Kit Lam
Control-flow graphs (CFGs) of structured programs are well known to exhibit strong sparsity properties. Traditionally, this sparsity has been modeled using graph parameters such as treewidth and pathwidth, enabling the development of faster parameterized algorithms for tasks in compiler optimization, model checking…
Haoran Sun, Likai Liang, Zhongrui Wang
Graph Neural Networks (GNNs) have become essential for analyzing graph-structured data, yet their deployment on resource-constrained edge devices is severely limited by high computational complexity and irregular memory access patterns. Here, we introduce DynamiGraph, a specialized FPGA-based overlay accelerator…
Authors not listed
The Polytope Formalism provides a rigorous and unifying mathematical framework for representing all possible molecular configurations and their interrelationships. Extending its application from stereoisomerism to molecular constitution reveals that both arise from a common structural foundation linking discrete and…
Toluwanimi O. Odemuyiwa, Serban D. Porumbescu, Muhammad Osama, Joel S. Emer + 1 more
We propose a principled approach to reasoning about various graph algorithm implementations. We leverage the extended general Einsum notation (EDGE) which allows us to factor complexity along four axes: algebraic manipulation, mapping, format, and low-level implementations. Using breadth-first search (BFS) as a driving…
Ian Seet, Keith Y. Patarroyo, Gage Siebert, Sara I. Walker + 1 more
of the Assembly Chemical Space of Molecular Graphs Authors: Ian Seet, Keith Y. Patarroyo, Gage Siebert, Sara I. Walker, Leroy Cronin Quantifying how hard it is to build a molecular graph matters for biosignature detection, chemical complexity, and cheminformatics. We present an exact, scalable algorithm to compute the…
Juha Harviainen, Francisco Sena, Corentin Moumard, Aleksandr Politov + 2 more
To define ultrabubble we need one more definition. The splitting operation receives a bidirected graph G and a vertex-side $uα$ and produces a new bidirected graph $G′=(V′,E′)$ with $V′:=V(G)\cup{u′}$ and $E′:=E(G)\setminus{{uα^,vβ}\inE(G)}\cup{{u′α^,vβ}∣{uα^,vβ}\inE(G)}$. Essentially, every edge of G incident to u…
Shreeharsha G Bhat, Daanish Mahajan, Chirag Jain
A key application of pangenome graphs is the characterization of small and large genomic variants represented as bubbles within the graph. Although bubbles have been extensively studied in directed graphs in the context of genome assembly, there remains a need for a rigorous definition and systematic analysis of…
Peilin Liu, Kaixin Hu, Lapo Mughini-Gras, Aldert L. Zomer + 3 more
Pangenome graphs are increasingly used to represent population-scale bacterial diversity, yet construction methods span fundamentally different representation paradigms whose outputs and sensitivities to assembly quality remain poorly quantified. We systematically reviewed microbial pangenome graph tools and…
Zhen Xie, Wenzhe Hou, Feiyang Wu, Hao Xu + 1 more
Graphs are a representative type of fundamental data structures. They are capable of representing complex association relationships in diverse domains. For large-scale graph processing, the stream graphs have become efficient tools to process dynamically evolving graph data. When processing stream graphs, the subgraph…
Ke Chen, Abhishek Talesara, Sanchal Thakkar, Mingfu Shao
The minimum flow decomposition problem abstracts a set of key tasks in bioinformatics, including metagenome and transcriptome assembly. These tasks, collectively known as multi-assembly, aim to reconstruct multiple genomic sequences from reads obtained from mixed samples. The reads are first organized into a directed…
Albert Jiménez-Blanco, Lorién López-Villellas, Juan Carlos Moure, Miquel Moreto + 1 more
Sequence-to-graph alignment is a central problem in bioinformatics, with applications in multiple sequence alignment (MSA) and pangenome analysis, among others. However, current algorithms for optimal affine-gap alignment impose high memory and computational requirements, limiting their scalability to aligning long…
Leonard Bohnenkämper, Jens Stoye
The study of evolution between species (phylogenetics) and the study of evolution within a species (population genetics) are highly related, as the same biological mechanisms are fundamental to both fields. Although both have been studied for a long time, their joint study in a unified setting has been prevented by the…
Anna Lisiecka, Agnieszka Kowalewska, Norbert Dojer
Pangenome graphs conveniently represent genetic variation within a population. Several types of such graphs have been proposed, with varying properties and potential applications. Among them, variation graphs (VGs) seem best suited to replace reference genomes in sequencing data processing, while whole genome…
ChangChao Liu, Jinzhe Han, Yue Zhang, Zhizheng Zhang + 2 more
In the field of intelligent fault diagnosis, graph neural networks (GNNs) can create a richer fault feature space by modeling dependencies between sensor signals and embedding them in a structural attribute graph. However, existing GNNs models typically use monitoring signals to directly construct graphical datasets…
Authors not listed
Machine learning is increasingly used to predict reaction properties such as barrier heights, reaction energies, rates, or yields, as well as the underlying molecular geometries, including transition state structures. While such predictions have the potential to provide mechanistic insight for high-impact applications…
Kengo Nakamura, Masaaki Nishino
Given a network and a set of vertices called seeds to initially inject information, influence spread is the expected number of vertices that eventually receive the information under a certain stochastic model of information propagation. Under the commonly used independent cascade model, influence spread is equivalent…
Brieuc Lehmann, Hanbin Lee, Luke Anderson-Trocmé, Jerome Kelleher + 3 more
Genetic relatedness is a central concept in genetics, underpinning studies of population and quantitative genetics in human, animal, and plant settings. It is typically stored as a genetic relatedness matrix, whose elements are pairwise relatedness values between individuals. This relatedness has been defined in…
Jing Xie, Qi Duan
Biological pathway analysis often requires identifying interventions that block reachability to an undesirable state, such as a disease-associated module, toxic byproduct, or adverse phenotype, while preserving reachability among essential biological functions. Motivated by this setting, we study the Reachability…