Many mechanisms within biological systems can be modeled as pathways, chains of interactions between proteins, genes, chemicals, and other biological entities. These interactions can be represented using a graph structure, more specifically a knowledge graph representing known or inferred information about the entities in question. In this context, we propose a constraint propagation approach for identifying paths in a graph structure which represent potential biological pathways. We apply this approach to a knowledge graph dataset which was semantically extracted from literature on COVID-19.

We present an approach for inexact subgraph matching on attributed graphs optimizing the graph edit distance. By combining lower bounds on the cost of individual assignments, we obtain a heuristic for a backtracking tree search to identify optimal solutions. We evaluate our algorithm on a knowledge graph dataset derived from real-world data, and analyze the space of optimal solutions.

In the context of networks curated from real world data, an important problem is that of aligning entities across multiple data sources. Methods for performing alignment are often error-prone due to lack of information and noise within the data itself. When performing subgraph matching on the resulting aligned networks, these alignment errors often lead to catastrophic results. In this paper, we propose a fault-tolerant algorithm for subgraph matching on aligned networks which takes into account potential alignment errors.

We present filtering methods for finding all sub-graphs of a large multiplex network that are isomorphic to a smaller template network. These methods are shown to be effective on a set of synthetic transaction networks from the DARPA Modeling Adversarial Activity (MAA) program. In some cases, filtering allows us to identify and enumerate all possible isomorphisms. We observe that in some of the MAA networks, the number of subgraphs isomorphic to the template is orders of magnitude larger than the size of the network.