Tracking individuals or groups based on their hidden and/or emergent behaviors is an indispensable task in homeland security, mental health evaluation, and consumer analytics. On-line and off-line communication patterns, behavior profiles and social relationships form complex dynamic evolving knowledge graphs. Investigative search involves capturing and mining such large-scale knowledge graphs for emergent profiles of interest. While graph databases facilitate efficient and scalable operations on complex heterogeneous graphs, dealing with incomplete, missing and/or inconsistent information and need for adaptive querying pose major challenges. We address these by proposing an inexact graph pattern matching method, which is implemented in a graph database with a scoring mechanism that helps identify hidden behavioral patterns. PINGS (Procedures forINvestigativeGraphSearch), a graph database library of procedures for investigative graph search is presented. Results presented demonstrate the capability of detecting individuals/groups meeting query criteria as well as the iterative query performance in graph databases. We evaluate our approach on three datasets: a synthetically generated radicalization dataset, a publicly available patient’s ICU hospitalization stays dataset, and a crime dataset. These varied datasets demonstrate the wide-range applicability and the enhanced effectiveness of observing suspicious or latent trends in investigative domains.

The search in graph databases for individuals or entities undertaking latent or emergent behaviors has applicability in the areas of homeland security, consumer analytics, behavioral health, and cybersecurity. In this setting, even partial matches to hypothesized indicators are worthy of further investigation, and analysts in these domains aim to identify and maintain awareness of entities that either fully or partially match the queried attributes over time. We provide a comprehensive version of a graph pattern matching technique called Investigative Search for Graph Trajectories (INSiGHT) to find emergent patterns of behaviors in networks and tailor the application to detecting radicalization in the homeland security domain. To enable analysts' accounting of recurring behavioral indicators and the recency of behaviors as the imminence of a threat, we provide parameterized methods to score multiple occurrences of indicators and to dampen the significance of indicators over time, respectively. Additionally, we provide an indicator categorization scheme and a match filtering technique to ensure that partial matches to the most salient indicators are identified while reducing the number of false positives. Furthermore, since individuals may be radicalized in small groups or be involved in collective terrorist plots, we introduce a non-combinatorial neighborhood matching technique that enables analysts to use INSiGHT to identify potential query matches from clusters of individuals who may be operating in conspiracies. We demonstrate the performance of our approach using a synthetic radicalization data set and a large, real-world data set of the BlogCatalog social network.

This paper proposes the use of graph pattern matching for investigative graph search, which is the process of searching for and prioritizing persons of interest who may exhibit part or all of a pattern of suspicious behaviors or connections. While there are a variety of applications, our principal motivation is to aid law enforcement in the detection of homegrown violent extremists. We introduce investigative simulation, which consists of several necessary extensions to the existing dual simulation graph pattern matching scheme in order to make it appropriate for intelligence analysts and law enforcement officials. Specifically, we impose a categorical label structure on nodes consistent with the nature of indicators in investigations, as well as prune or complete search results to ensure sensibility and usefulness of partial matches to analysts. Lastly, we introduce a natural top-k ranking scheme that can help analysts prioritize investigative efforts. We demonstrate performance of investigative simulation on a real-world large dataset.

Investigative graph search is the process of searching for and prioritizing entities of interest that may exhibit part or all of a pattern of attributes or connections for a latent behavior. In this work we formulate a related sub-problem of determining the pattern matching trajectories of such entities. The goal is to not only provide analysts with the ability to find full or partial matches against a query pattern, but also a means to quantify the pace of the appearance of the indicators. This technology has a variety of potential applications such as aiding in the detection of homegrown violent extremists before they carry out acts of domestic terrorism, detecting signs for post-traumatic stress in veterans, or tracking potential customer activities and experiences along a consumer journey. We propose a vectorized graph pattern matching approach that calculates the multi-hop class similarities between nodes in query and data graphs over time. By tracking partial match trajectories, we provide another dimension of analysis in investigative graph searches to highlight entities on a pathway towards a pattern of a latent behavior. We demonstrate the performance of our approach on a real-world BlogCatalog dataset of over 470K nodes and 4 million edges, where 98.56% of nodes and 99.65% of edges were filtered out with preprocessing steps, and successfully detected the trajectory of the top 1,327 nodes towards a query pattern.

This paper outlines our on-going efforts to address the radicalization detection problem, the automated or semi-automated task of dynamically detecting and tracking behavioral changes in individuals who undergo the process of increasingly espousing jihadist beliefs and transition to the use of violent action in support of those beliefs. Leveraging the notion that personal trajectories towards violent radicalization exist, we take a graph pattern matching approach to track individual-level indicators using data fused from available public and government/law enforcement databases. We show that our approach provides analysts with the ability to find full or partial matches against a query pattern of radicalization, and a means to quantify the pace of the appearance of the indicators that may help prioritize investigative efforts and resources to prevent planned attacks.

This article considers the nonlethal targeting assignment problem in the counterinsurgency in Afghanistan, the problem of deciding on the people whom U.S. forces should engage through outreach, negotiations, meetings, and other interactions in order to ultimately win the support of the population in their area of operations. We propose two models: (1) the Afghan counterinsurgency (COIN) social influence model, to represent how attitudes of local leaders are affected by repeated interactions with other local leaders, insurgents, and counterinsurgents, and (2) the nonlethal targeting model, a NonLinear Programming (NLP) optimization formulation that identifies a strategy for assigning k U.S. agents to produce the greatest arithmetic mean of the expected long-term attitude of the population. We demonstrate in an experiment the merits of the optimization model in nonlethal targeting, which performs significantly better than both doctrine-based and random methods of assignment in a large network.