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.

Critical infrastructure such as power grids are becoming increasingly complex, connected, and vulnerable. Effective risk mitigation for these cyber-physical energy systems (CPES), requires preemptive knowledge of likely adversarial attack scenarios. However, the scarcity of documented attack sequences hinders this process. We propose a data-driven Graph Convolutional Deep-Q Network (GCDQ) to address this lack of data through generating Hybrid Attack Graphs (HAGs), a graphical representation of CPES attack sequences. By leveraging limited real-world observations from the MITRE ATT&CK knowledge base, our GCDQ model synthesizes realistic graphs with the targeted attribute of minimum detectability via reinforcement learning. This generative model is the first step in creating a tool to substantially boost the attack sequence dataset and enhance the performance of CPES defense-related tasks by providing insights into likely attack sequences with given attributes.

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.

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.

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.

We demonstrate \perco, a distributed system for graph pattern discovery in dynamic graphs. In contrast to conventional mining systems, Percolator advocates efficient pattern mining schemes that (1) support pattern detection with keywords; (2) integrate incremental and parallel pattern mining; and (3) support analytical queries such as trend analysis. The core idea of \perco is to dynamically decide and verify a small fraction of patterns and their instances that must be inspected in response to buffered updates in dynamic graphs, with a total mining cost independent of graph size. We demonstrate a( the feasibility of incremental pattern mining by walking through each component of \perco, b) the efficiency and scalability of \perco over the sheer size of real-world dynamic graphs, and c) how the user-friendly \gui of \perco interacts with users to support keyword-based queries that detect, browse and inspect trending patterns. We demonstrate how \perco effectively supports event and trend analysis in social media streams and research publication, respectively.

Graph mining is an important data analysis methodology, but struggles as the input graph size increases. The scalability and usability challenges posed by such large graphs make it imperative to sample the input graph and reduce its size. The critical challenge in sampling is to identify the appropriate algorithm to insure the resulting analysis does not suffer heavily from the data reduction. Predicting the expected performance degradation for a given graph and sampling algorithm is also useful. In this paper, we present different sampling approaches for graph mining applications such as Frequent Subgrpah Mining (FSM), and Community Detection (CD). We explore graph metrics such as PageRank, Triangles, and Diversity to sample a graph and conclude that for heterogeneous graphs Triangles and Diversity perform better than degree based metrics. We also present two new sampling variations for targeted graph mining applications. We present empirical results to show that knowledge of the target application, along with input graph properties can be used to select the best sampling algorithm. We also conclude that performance degradation is an abrupt, rather than gradual phenomena, as the sample size decreases. We present the empirical results to show that the performance degradation follows a logistic function. Original Datasets, implementation of sampling algorithms, and results are available online.

Property graphs can be used to represent heterogeneous networks with labeled (attributed) vertices and edges. Given a property graph, simulating another graph with same or greater size with the same statistical properties with respect to the labels and connectivity is critical for privacy preservation and benchmarking purposes. In this work we tackle the problem of capturing the statistical dependence of the edge connectivity on the vertex labels and using the same distribution to regenerate property graphs of the same or expanded size in a scalable manner. However, accurate simulation becomes a challenge when the attributes do not completely explain the network structure. We propose the Property Graph Model (PGM) approach that uses a label augmentation strategy to mitigate the problem and preserve the vertex label and the edge connectivity distributions as well as their correlation, while also replicating the degree distribution. Our proposed algorithm is scalable with a linear complexity in the number of edges in the target graph. We illustrate the efficacy of the PGM approach in regenerating and expanding the datasets by leveraging two distinct illustrations. Our open-source implementation is available on GitHub.

The ability to construct domain specific knowledge graphs (KG) and perform question-answering or hypothesis generation is a transformative capability. Despite their value, automated construction of knowledge graphs remains an expensive technical challenge that is beyond the reach for most enterprises and academic institutions. We propose an end-toend framework for developing custom knowledge graph driven analytics for arbitrary application domains. The uniqueness of our system lies A) in its combination of curated KGs along with knowledge extracted from unstructured text, B) support for advanced trending and explanatory questions on a dynamic KG, and C) the ability to answer queries where the answer is embedded across multiple data sources.