Engineering Papers⌕ Search

Engineering topics

Chin, George

Publications and source records attributed to Chin, George.

At least 19 records

ITeM: Independent temporal motifs to summarize and compare temporal networks

We report networks are a fundamental and flexible way of representing various complex systems. Many domains such as communication, citation, procurement, biology, social media, and transportation can be modeled as a set of entities and their relationships. Temporal networks are a specialization of general networks where every relationship occurs at a discrete time. The temporal evolution of such networks is as important to understand as the structure of the entities and relationships. We present the Independent Temporal Motif (ITeM) to characterize temporal graphs from different domains. ITeMs can be used to model the structure and the evolution of the graph. In contrast to existing work, ITeMs are edge-disjoint directed motifs that measure the temporal evolution of ordered edges within the motif. For a given temporal graph, we produce a feature vector of ITeM frequencies and the time it takes to form the ITeM instances. We apply this distribution to measure the similarity of temporal graphs. We show that ITeM has higher accuracy than other motif frequency-based approaches. We define various ITeM-based metrics that reveal salient properties of a temporal network. We also present importance sampling as a method to efficiently estimate the ITeM counts. We present a distributed implementation of the ITeM discovery algorithm using Apache Spark and GraphFrame. We evaluate our approach on both synthetic and real temporal networks.

97 MATHEMATICS AND COMPUTING↗

Synthetic Data and Graph Generation for Modeling Adversarial Activity (Final Project Report)

The Data and Graph Generation for Modeling Adversary Activity (MAA) project developed a methodology along with scalable graph modeling and generation tools to produce realistic large-scale background activity graphs with embedded adversarial activity pathways. The technical report presents PNNL methodology, released datasets, lessons learned, and recommendations to develop graph analytic algorithms for structure-only and attributed knowledge graphs.

97 MATHEMATICS AND COMPUTING↗

Semantic Property Graph for Scalable Knowledge Graph Analytics

Graphs are a natural and fundamental representation to describe entities, relationships, activities, and evolution of complex systems. Many domains such as communication, citation, procurement, biology, social media, and transportation can be modeled as a set of entities and their relationships. Resource Description Framework (RDF) and Labeled Property Graph (LPG) are two of the most used data models to encode information in a graph. Both 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 propose 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 a framework to convert reified RDF graphs into SPG using two different computing environments. We also present cloud-based graph migration capabilities using Amazon Web Services.

Purohit, Sumit↗

Transactional Knowledge Graph Generation To Model Adversarial Activities

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

Purohit, Sumit↗

QLiG: Query Like a Graph For Subgraph Matching

A graph is a natural and flexible modeling approach to represent entities and relationships between them in real-world. A Knowledge Graphs (KG) is a specialized graph with formal and structured representation of facts, relationships, annotated with semantic descriptions. Subgraph matching is one of the fundamental graph problems to identify relationships, interactions and activities of interest within a large graph. A query specification is a collection of abstract components, operations, and constraints to express a pattern. The specification can be implemented in different ways based on underlying data model. Various graph query specifications have been developed over the years and have led to the development of different open-sourced and vendor-specific query languages. Such specification are modeled as an extension of relational algebra used to develop relational query languages such as SQL. Such relational concepts do not inherently support graph queries. There is a need to represent graph queries in terms on graph-based components to expedite query construction by non-database experts. We present a graph-based query approach QLiG (pronounced cleeg), to perform subgraph matching in Labeled Property Graph. We present the query specifications, salient features, and a use case to show functional examples.

Purohit, Sumit↗

The Utility in Conjoint Analysis as a Fast Expert Elicitation Technique

This paper presents an interface and analysis technique for quickly conducting expert elicitation with the goal of determining entity importance. Our interface deploys a two-alternative choice experiment that is capable of representing knowledge graphs in an easy to interpret fashion for users with limited experience with knowledge graphs. Our analysis methodology takes advantage of conjoint analysis techniques and provides entity weights for many SMEs simultaneously. The results largely align with individual participant fits.

Conjoint Analysis, interface, Expert Elicitation, ↗

Data-Driven Template Discovery Using Graph Convolutional Neural Networks

Modeling adversarial activities is a critical component of developing high-con?dence 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-?delity, 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.

Joaristi, Mikel↗

Using Graph Edit Distance for Noisy Subgraph Matching of Semantic Property Graphs

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.

Ebsch, Christopher L.↗

Evaluation of Alignment: Precision, Recall, Weighting and Limitations

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.

Cottam, Joseph A.↗

A Dynamic Contingency Analysis Visualization Tool

We are developing a web-based visualization that shows the results of running a contingency analysis on a power grid system. Power grid analysists will be able to use this tool to visualize power event simulations and be better prepared for contingencies that may arise. The tool consists of a map, showing the power grid and its current state, and tables and charts showing the current status of various elements on the grid. The user can iterate over a number of cascading contingencies to visualize how the power grid will change under various scenarios.

Contingency analysis, power grid, smart grid, visu↗

Multi-Channel Entity Alignment via Name Uniqueness Estimation

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.

Orren, Miquette J.↗

Performance and usability enhancements for continuous subgraph matching queries on graph-structured data

A query graph, which includes vertices and edges, represents a query on graph-structured data. The query graph is decomposed into query subgraphs. A network analysis tool performs continuous subgraph matching queries to facilitate analysis of computer network traffic, social media events, or other streams of data represented as a dynamic data graph (graph-structured data). This can help identify emerging trends in the data. Some features of the network analysis tool enhance performance by effectively utilizing distributed computing resources (including processing cores and memory at different nodes of a cluster) to speed up the process of updating the dynamic data graph and detecting matches of query subgraphs. Features of a query graph building tool enhance usability by providing intuitive ways to specify query graphs and their subgraphs. Features of a results visualization tool enhance usability by providing an intuitive way to present the results of continuous subgraph matching queries.

Choudhury, Sutanay↗

temporal-graphs/STM

Structural Temporal Modeling Generating a synthetic graph that is similar to a given real- world graph is a critical requirement for privacy preservation and benchmarking purposes. This software presents a temporal-motif based approach to generate synthetic temporal graph datasets.

Purohit, Sumit↗

Multi-Channel Large Network Simulation Including Adversarial Activity

Using network simulation to generate high fidelity networks is essential to test adversarial search problems, in addition to their benefits of privacy preservation and benchmarking purposes. Different generative models have been developed to generate single-channel, homogeneous networks that can model domains such as social networks, communication, and co-authorship. Modeling adversarial activity compounds the complexity of network simulation as it requires generating multi-channel networks simultaneously with correlated channel attributes at scale. We present a methodology along with scalable graph modeling and generation tools to produce realistic large-scale synthetic background activity graphs with embedded an adversarial activity. We present a concrete use case based on an attack scenario developed with the help of subject matter experts (SMEs). We discuss challenges in modeling integration across channels, scalability of the generative models, and integration across such models. We also discuss required aspects to simulate high fidelity multi-channel networks up-to an order of billion edges.

Network simulation, Multi-channel simulation, Adve↗

Temporal Graph Generation Based on a Distribution of Temporal Motifs

Generating a synthetic graph that is similar to a given real-world graph is a critical requirement for privacy preservation and benchmarking purposes. Various generative models attempt to generate static graphs similar to real-world graphs. However, generation of temporal graphs is still an open research area. We present a temporal-motif based approach to generate synthetic temporal graph datasets and results from three real-world use cases.

Purohit, Sumit↗

Visual Steering and Modeling Environment for Smart Grid Models and Simulations

We are developing the Visual Steering and Modeling Environment (VSME) to enable the visual control and steering of smart grid simulations as well as the visualization of simulation behaviors, conditions, and results. Visual steering will allow planners and operators to visually adjust the parameters to a suite of coordinated and dynamic smart grid simulations and immediately see the effects in multi-perspective visualizations. A configurable dashboard connects and integrates parameters, simulations, data, and visualizations into a combined and coherent display.

Power grid, smart grid, visualization, data visual↗

A Selectivity based approach to Continuous Pattern Detection in Streaming Graphs

Cyber security is one of the most significant technical challenges in current times. Detecting adversarial activities, prevention of theft of intellectual properties and customer data is a high priority for corporations and government agencies around the world. Cyber defenders need to analyze massive-scale, high-resolution network flows to identify, categorize, and mitigate attacks involving networks spanning institutional and national boundaries. Many of the cyber attacks can be described as subgraph patterns, with prominent examples being insider infiltrations (path queries), denial of service (parallel paths) and malicious spreads (tree queries). This motivates us to explore subgraph matching on streaming graphs in a continuous setting. The novelty of our work lies in using the subgraph distributional statistics collected from the streaming graph to determine the query processing strategy. We introduce a ``Lazy Search" algorithm where the search strategy is decided on a vertex-to-vertex basis depending on the likelihood of a match in the vertex neighborhood. We also propose a metric named ``Relative Selectivity" that is used to select between different query processing strategies. Our experiments performed on real online news, network traffic stream and a synthetic social network benchmark demonstrate 10-100x speedups over non-incremental, selectivity agnostic approaches.

dynamic graphs↗

A Selectivity based approach to Continuous Pattern Detection in Streaming Graphs

Cyber security is one of the most significant technical challenges in current times. Detecting adversarial activities, prevention of theft of intellectual properties and customer data is a high priority for corporations and government agencies around the world. Cyber defenders need to analyze massive-scale, high-resolution network flows to identify, categorize, and mitigate attacks involving net- works spanning institutional and national boundaries. Many of the cyber attacks can be described as subgraph patterns, with promi- nent examples being insider infiltrations (path queries), denial of service (parallel paths) and malicious spreads (tree queries). This motivates us to explore subgraph matching on streaming graphs in a continuous setting. The novelty of our work lies in using the subgraph distributional statistics collected from the streaming graph to determine the query processing strategy. We introduce a “Lazy Search" algorithm where the search strategy is decided on a vertex-to-vertex basis depending on the likelihood of a match in the vertex neighborhood. We also propose a metric named “Relative Selectivity" that is used to se- lect between different query processing strategies. Our experiments performed on real online news, network traffic stream and a syn- thetic social network benchmark demonstrate 10-100x speedups over selectivity agnostic approaches.

graphs, cybersecurity↗