How data is encoded in a knowledge graph directly influences what can be done with that data. A common problem with many encodings is that they have difficulty representing ambiguity and evolution inherent in many real-world data sets. The data encoding represented in this paper (called CARAT) is a graph-level description of our attempt to capture data that is contradictory, ambiguous and evolves over time (including deleting information). The data encoding relies on tracking assertions about subjects rather than directly tracking states. This encoding decision resolves many issues our team had experienced using other data encodings but produces a a larger graph. This is a preliminary presentation of our CARAT data encoding and our experience using it.

Curating knowledge from multiple siloed sources that contain both structured and unstructured data is a major challenge in many real-world applications. Pattern matching and querying represent fundamental tasks in modern data analytics that leverage this curated knowledge. The development of such applications necessitates overcoming several research challenges, including data extraction, named entity recognition, data modeling, and designing query interfaces. Moreover, the explainability of these functionalities is critical for their broader adoption.The emergence of Large Language Models (LLMs) has accelerated the development lifecycle of new capabilities. Nonetheless, there is an ongoing need for domain-specific tools tailored to user activities. The creation of such digital assistants has gained considerable traction in recent years, with LLMs offering a promising avenue to develop such assistants utilizing domain-specific knowledge and assumptions.In this context, we introduce an advanced query and reasoning system, GraphAide, which constructs a knowledge graph (KG) from diverse sources and allows to query and reason over the resulting KG. GraphAide harnesses both the KG and LLMs to rapidly develop domain-specific digital assistants. It integrates design patterns from retrieval augmented generation (RAG) and the semantic web to create an agentic LLM application. GraphAide underscores the potential for streamlined and efficient development of specialized digital assistants, thereby enhancing their applicability across various domains.

A Knowledge Graph (KG) is a formal and structured representation of entities, relationships, and their semantic descriptions. Traditionally, KGs are used to describe metadata about entities and provide additional context to a target application. Many real-world domains also involve temporal interactions between entities, in addition to the metadata. Modeling these attributed transactions is a critical requirement when using KGs in complex real-world applications, such as modeling adversarial activities. Adversarial activity modeling requires methodology and tools to produce realistic large-scale background graphs that include embedded Weapons of Mass Destruction (WMD) activity patterns [1]. We present a novel framework for constructing transactional knowledge graphs from a diverse set of sources. We present cloud-scale architecture of the framework, core components, and a real-world use case to demonstrate the generation of a background knowledge graph and WMD activity templates to evaluate network alignment and subgraph matching algorithms.

Graphs are a natural and fundamental representation to describe entities, relationships, activities, and evolution of complex systems. Resource Description Framework (RDF) and Labeled Property Graph (LPG) are two of the most used graph-based data models to encode information. Both the models are similar in terms of using basic graph elements such as nodes and edges but differ in terms of the modeling approach, expressibility, serialization, and target applications. RDF is a flexible data exchange model for expressing information about entities but it tends to a have high memory footprint and inefficient storage, which does not make it a natural choice to perform scalable graph analytics. In contrast, LPG has gained traction as a reliable model to perform scalable graph analytic tasks such as sub-graph matching, network alignment, and real-time knowledge graph query. It provides efficient storage, fast traversal, and flexibility to model various real-world domains. At the same time, the LPG lacks the support of a formal knowledge representation such as an ontology to provide automated knowledge inference. We introduce Semantic Property Graph (SPG) as a logical projection of reified RDF into the LPG model. SPG continues to use RDF ontology to define the type hierarchy of the projected graph and validate it against a given ontology. We present the projection rules and a cloud-scale framework to convert reified RDF into SPG. We also present examples to demonstrate lossless SPG conversion for the subgraph matching application.

In the real world, data does not come neatly packaged. Instead, it typically comes as small updates from many sources with different conventions. Building a single, cohesive knowledge-base to work from requires merging small updates from many different sources. This paper outlines methods we have investigated for scoring merging routines. Given a challenge problem consisting of a large knowledge-base and a set of smaller documents, algorithms are asked to identify alignment points between the smaller document and the knowledge base. This paper surveys options for evaluating such algorithms, providing notes on strengths, weaknesses and considerations for interpretation.

The subgraph matching problem is a fundamental problem in graph theory that is known to be NP-complete. In this study, performers were asked to develop algorithms to search for semantic property graphs that were subgraphs of a large knowledge graph. The templates provided contained structural information about the subgraphs and some attributes for each node and edge. There also exists a similarity measure between a set of attribute values that occurs on every node and edge. Algorithms performed well in the case where an exact match existed, but performers were also provided templates that had noise added such that there existed no match in the knowledge graph. Performers were asked to find the closest matches to those noisy subgraphs. To evaluate performance on this task, we developed a version of the graph edit distance algorithm to measure the cost of editing the template graph so that it is isomorphic in structure and attributes to the performer submission.

Modeling adversarial activities is a critical component of developing high-confidence indicators of efforts to acquire, fabricate, proliferate, and/or deploy weapons of mass terror (WMTs). Current approaches to generating representative patterns of interest (a.k.a templates) from the real-world domains involve a Subject Matter Expert (SME)-guided manual process. The goal of Data-Driven Template Discovery (DDTD) is to use a (potentially small) set of SME generated templates to discover other previously unknown and interesting templates in an attributed graph. A template is an activity pattern describing a set of interactions among a group of nodes in the graph. The motivation behind DDTD is to expand the original set of templates, without having SMEs craft all the templates by hand. DDTD also provides seed templates to SMEs, to help them construct larger, high-fidelity, and scenario-oriented templates. In these cases, obtaining a larger set of templates that are related (contain similar signals) to the original set is of great value. In this work, we propose to use Graph Convolutional Neural Networks (GCNs) to discover new templates that are heavily related to the original set. GCNs are a family of Neural Network (NN) architectures especially designed to work directly on graphs. In contrast to the traditional NNs, that require considerable amounts of labeled data, GCNs do not require a big labeled training set because they can directly leverage the graph structure instead. This property makes GCNs the perfect tool for creating activity templates.

When searching for adversarial activity within multiple networks, one of the greatest challenges is how to accurately align entities across different channels of information. This task becomes increasingly difficult when minimal additional information is known about each individual besides a name. Within this study, we analyze name rarity and how it can be used to align people on three distinct data channels: Venmo financial transactions, Reddit online discussions, and a bibliographic data source of academic writings. We explore how the uniqueness of a name can be used to decide if a person is likely the same as another across networks, in the absence of any additional ground truth. While 100 percent confidence cannot be gained, we can use this information to clarify when a possible alignment is more or less likely to be the same individual, increasing our confidence of accurately detecting adversarial behavioral patterns. From the data collected, we found that 0.1% of people had the same name across data sets, and 22.5% of those names are considered rare by our threshold. In our study, we also examine the accuracy of our method and show how real names can be extracted from account usernames, and compared in a similar manner.

Network simulation is essential to test adversarial search problems for privacy preservation and benchmarking purposes. Different generative models have been developed for single-channel, homogeneous networks that model social networks, communication, and co-authorship. Modeling multichannel networks simultaneously with correlated channel attributes at scale compounds complexity, and including adversarial signals across channels creates a second set of burdens. We present a methodology to employ a suite of generation tools to produce realistic large-scale synthetic activity graphs with embed an adversarial activity. We describe our technical process and how we employ subject matter experts (SMEs) to improve the adversarial signal. We discuss challenges in multi-channel modeling and scalability. We also discuss challenges for high fidelity multi-channel network generation at billion-edges scale.

A useful technique for adversary activity graph analytics is to perform subgraph isomorphism; searching for a specific graph pattern within a larger graph. Many of the networks that may be useful for adversary activity analysis are temporal networks, in which the chronological ordering of the edges has importance to the meaning of the data. Performing temporal subgraph matching requires the edges in the subgraphs to match the order of the temporal graph motif we are searching for. Previous methods for solving this rely on the use of static subgraph matching to find potential matches first, before filtering them based on edge order to find the true temporal matches. We present a new algorithm for temporal subgraph isomorphism that performs the subgraph matching directly on the chronologically sorted edges. By restricting our search to only the subgraphs with chronologically correct edges, we can improve the performance of the algorithm significantly in many cases. We present experimental timing results to show significant performance improvements on publicly available datasets for a number of different temporal query graph motifs with four or more nodes. We also demonstrate a practical example of how temporal subgraph isomorphism can produce more meaningful results than traditional static subgraph searches.

Acting on time-critical events by processing ever growing social media, news or cyber data streams is a major technical challenge. Many of these data sources can be modeled as multi-relational graphs. Mining and searching for subgraph patterns in a continuous setting requires an efficient approach to incremental graph search. The goal of our work is to enable real-time search capabilities for graph databases. This demonstration will present a dynamic graph query system that leverages the structural and semantic characteristics of the underlying multi-relational graph.