Modern visual analytic tools promote human-in-the-loop analysis but are limited in their ability to direct the user toward interesting and promising directions of study. This problem is especially acute when the analysis task is exploratory in nature, e.g., the discovery of potentially coordinated relationships in massive text datasets. Such tasks are very common in domains like intelligence analysis and security forensics where the goal is to uncover surprising coalitions bridging multiple types of relations. We introduce new maximum entropy models to discover surprising chains of relationships leveraging count data about entity occurrences in documents. These models are embedded in a visual analytic system called MERCER (Maximum Entropy Relational Chain ExploRer) that treats relationship bundles as first class objects and directs the user toward promising lines of inquiry. We demonstrate how user input can judiciously direct analysis toward valid conclusions, whereas a purely algorithmic approach could be led astray. Experimental results on both synthetic and real datasets from the intelligence community are presented. H. Wu et al. Unstructured exploration of relationships from large text datasets is a crucial problem in many application domains, for example, intelligence analysis, biomedical discovery, analysis of legal briefs and opinions. The state-of-the-art today involves two broad classes of techniques. Visual analytic tools, for example Jigsaw [47], support the exploration of relationships extracted from large text datasets. While they promote human-in-the-loop analysis, identifying promising leads to explore is left to the creativity of the user. At the other end of the spectrum, text relationship exploration techniques such as storytelling [21] provide interesting artifacts (e.g., stories and summaries) for analysis but are limited in their ability to incorporate user input to steer the discovery process. Our goal here is to realize an amalgamation of algorithmic and human-driven techniques to support the discovery of coordinated relationship chains from document collections. A coordinated relationship (also called a bicluster) is one in which a group of entities are related to another group of entities via a common relation. It is thus a generalization of a relationship instance. A chain of such coordinated relationships enables us to bundle groups of entities across various domains and relate them through a succession of individual relationships. The primary artifact of interest are thus chains summarizing how entities in a document collection are related. We introduce new maximum entropy (MaxEnt) models to identify surprising chains of interest and rank them for inspection by the user. In intelligence analysis, such chains can reveal how hitherto unconnected people or places are related through a sequence of intermediaries. In biomedical discovery, such chains can reveal how proteins involved in distinct pathways are related through cross-talk via other proteins or signaling molecules. In legal briefs, one can use chains to determine how rationale for court opinions vary over the years and are buttressed by the precedence structure implicit in legal history. As shown in Figure 1 (left) , we propose an interactive approach wherein user feedback is woven at each stage and used to rank the most interesting chains for further exploration. Such user feedbacks are also taken into account by the algorithm for further investigations of the data. We will demonstrate through case studies how such an approach gets users to their intended objectives compared to a purely algorithmic approach (Figure 1 (right) ). The work presented here is implemented in a system-Maximum Entropy Relational Chain ExploRer (MERCER) that uses a variety of visual exploration strategies and algorithmic means to foster user exploration. Our key contributions are as follows: (1) MERCER is a marriage of two of our prior works [51, 61] but supercedes the state-of-theart in those papers in significant, orthogonal, ways. MERCER is a significant improvement over the work presented by Sun et al. [51] because the authors provide support for only manual exploration of coordinated relationships. MERCER is also a significant improvement over the work presented by Wu et al. [61] because this work only presents approaches to rank chains involving a binary MaxEnt model whereas MERCER introduces more general MaxEnt approaches for real-valued data. (2) We present two path strategies (full path and stepwise) to help analyze datasets. Using our proposed MaxEnt models, the full path strategy discovers the most surprising bicluster chains from all possible chains involving an analyst-selected bicluster. The stepwise strategy evaluates biclusters neighboring a user-specified one, and prioritizes possible connected information with the current pieces under investigation. Both strategies directs analysts to reveal hidden plots involving surprising relational patterns. (3) We describe new visual encodings and summary as well as detailed views to support user-guided exploration of coordinated relationships in massive datasets. Besides basic color codings (e.g., connection-oriented highlighting [51]), MERCER offers highlighting
REF proposed a visual analytic system called MERCER (Maximum Entropy Relational Chain ExploRer), designed to help a user discover interesting relationships, e.g. in large text datasets.
Interactive Discovery of Coordinated Relationship Chains with Maximum Entropy Models
TKDD
Computer Science