A major goal of this project is the development of new mathematical algorithms and models involving knowledge graphs. A knowledge graph represents what is known about a subject in the form of labeled nodes and edges. More than simply labeled data, knowledge graphs organize data according to high-level meanings and assign globally unique identification to each node in the graph to match real-world entities. Much work on knowledge graphs treats databases and queries. In contrast, in the context of threat detection, this project focuses on algorithms that identify latent information in the graph and predictive models associated with data on the graph. The project involves a combination of mathematical methods for subgraph isomorphism detection, time series analysis, agent-based and multiscale modeling, and pattern recognition.  To build our methodology we develop new models for graph-structured data that could become part of a knowledge graph.

One important outcome of this project is the development of methods that leverage the role of symmetry in subgraph matching, both in the description of the graphs in question and in how it confounds the search process. More specifically, this work shows how to quantify these effects and how to use symmetries to increase the efficiency of subgraph isomorphism algorithms. The work introduces rigorous definitions of structural equivalence and establish conditions for when it can be used to generate more solutions. This work illustrates how to adapt standard search routines to utilize these symmetries to accelerate search and compactly describe the solution space.  As am example, we adapt a state-of-the-art solver and perform a comprehensive series of tests to demonstrate these methods' efficacy on a standard benchmark set. We extend these methods to multiplex graphs and present results on large multiplex networks drawn from transportation systems, social media, adversarial attacks, and knowledge graphs.

The ability to leverage symmetries and structural equivalences results in the ability to identify extremely large solution spaces for the subgraph matching problem on the order of 10¹⁰⁰ or more solutions.  In a real use-case scenario, analysts may need to query additional information about template nodes or world nodes to reduce the problem size and the solution space. Currently, this query process is done by hand, based on the personal experience of analysts. By analogy to the well-known active learning problem in machine learning classification problems, we present a machine-based active learning problem for the subgraph match problem in which the machine suggests optimal template target nodes that would be most likely to reduce the solution space when it is otherwise overly large and complex. The humans in the loop can then include additional information about those target nodes. We present some case studies for both synthetic and real-world datasets for multichannel subgraph matching.

In addition to algorithm development, this project showed examples of large knowledge graphs created from modern databases of information, thereby allowing the user to quickly understand comprehensive information embedded in the data.  Examples include a knowledge graph from twitter content during and about the COVID19 pandemic, a knowledge graph about the QAnon conspiracy network, a knowledge graph about hate speech and online content, and one about a crime narrative.  These graphs point to a multitude of ways in which information can be understood once it is put into such a format. 

At the end of this project, we studied the use of large language models in the context of knowledge graphs and knowledge graph queries. 

Last Modified: 12/03/2024
Modified by: Andrea L Bertozzi