UCLA

For applications involving graph-structured data, a natural problem is to identify subgraphs that match a given template. In this thesis, we present several approaches for solving this subgraph matching problem, including approaches for both exact and inexact subgraph matching. Additionally, we define several problems related to subgraph matching in order to obtain a better understanding of the entire solution space for the subgraph matching problem. We analyze a variety of synthetic and real-world multiplex datasets, including Sudoku, transportation networks, Twitter, the DBPedia knowledge graph, and several datasets from the DARPA-MAA program for modeling adversarial activity. We then show how our exact subgraph matching approach can be extended to handle errors in network alignment, the process of merging multiple networks together to form a single multiplex network. Finally, we address the closely related problem of matching variable length path-based graph templates, and apply our method to identify potential activation pathways within a biological knowledge graph extracted from scientific publications on COVID-19.