Hierarchy Builder: Organizing Textual Spans into a Hierarchy to Facilitate Navigation (2023)

Abstract: Information extraction systems often producehundreds to thousands of strings on a specifictopic. We present a method that facilitatesbetter consumption of these strings, in an ex-ploratory setting in which a user wants to bothget a broad overview of what’s available, and achance to dive deeper on some aspects. The sys-tem works by grouping similar items together,and arranging the remaining items into a hierar-chical navigable DAG structure. We apply themethod to medical information extraction.

## introduction we are dealing with the question of organising and displaying a large collection of related textual strings. the need arises, for example, in information extraction or text mining applications, that extract strings from text. consider a system that scans the scientific literature and extracts possible causes for a given medical condition. such a system may extract thousands of different strings, some of them relate to each other in various ways, 1 and some are distinct. users consume the list in an exploratory mode @xcite , in which they do not have a clear picture of what they are looking for, and would like to get an overview of the different facets in the results, as well as to dig deeper into some of them. for example, distinct strings extracted as causes for sciatica include "herniated disc", "herniated disk", "lumbar disk herniation" , "posterior interverbal disc herniation" and "endometriosis", among hundreds of others. the user of this system likes to go over the returned list to learn about possible causes, but going over hundreds to thousands of results is mentally taxing, and we would like to reduce this effort. in the current case, we would certainly like to treat the first two items (herniated disc and herniated disk) as equivalent and show 1 figure 1 lists the kinds of relations between strings. an additional complication is that the hierarchy we are considering is often not a tree: a single item may have two different parents, resulting in a direct acyclic graph (dag). for example, arguably a condition like leg pain should be indexed both under leg (together with other leg related items) and under pain (together with pain related items). the hierarchy structure is contextual, and depends on the data: if there are not many other leg related items, it may not be beneficial to introduce this category into the hierarchy. additionally, note that some items in the hierarchy may not directly correspond to input strings: first, for the "leg pain" example above, if the input list does not include stand-alone leg or pain items, we may still introduce them in our hierarchy. we may also introduce additional abstraction, for example we may want to group "heart disease", "ischemia", "hypotension", and "bleeding" under "cardiovascular disease". in this work we introduce a system that takes such a flat list of related strings, and arranges them in a navigable dag structure, allowing users to get a high level overview as well as to navigate from general topics or concepts to more specific content by drilling down through the graph. ideally, the graph would allow the user to: at a high level, the system works by finding lexically equivalent terms, arranging them in a dag structure reflecting the specificity relation between terms, further merging equivalent nodes based on a neural similarity model, add additional potential intermediary hierarchy nodes based on taxonomic information and other heuristics, and then pruning it back into a smaller sub-dag that contains all the initial nodes (input strings) but only a subset of the additional hierarchy nodes. finally, we select the top-k "entry points" to this graph: high level nodes that span as many of the input nodes as possible. this process is described in section §3. while the dag extended with potential hierarchies is very permissive and contains a lot of potentially redundant information, the dag pruning stage aims to ensure the final graph is as compact and informative as possible. we focus on causes-for-medical-conditions queries, and provide a demo in which a user can select a medical condition, and browse its causes in a compact dag structure. to evaluate the resulting dags, we perform automatic and manual evaluation. the automatic evaluation is based on measuring various graph metrics. the human evaluation is performed by human domain experts. our results show that the dag structure is significantly more informative and effective than a frequency-ranked flat list of results. ## requirements as discussed in the introduction, our input is a list of strings that reflect answers to a particular question, as extracted for a large text collection (we focus in this paper on the biomedical domain, and more specifically in causes for medical conditions). this list can be the output of an open-ie system @xcite @xcite , the results of running extractive qa @xcite with the same question over many paragraphs, or extracted using an extractive query in a system like spike @xcite @xcite . the lists we consider typically contain from hundreds to thousands of unique items. we identified a set of relations that can hold between strings in our inputs, which are summarized in this suggests a hierarchy that respects the following conditions: paraphrased spans should be combined into a single group, and close-meaning spans should be combined into the same group; elaboration relations should be expressed hierarchically; co-mention spans should be both descendants of the shared concept; taxonomic relations should (in some cases) be descendants of the taxonomical parent. additionally, we would like each node in the hierarchy to have relatively few children (to reduce the need to scan irrelevant items), yet keep the hierarchy relatively shallow (to save expansion clicks if possible). the hierarchical structure should also be informative: we should be able to guess from a given node which kinds of items to expect to find under it, and which kinds of items not to expect to find under it. this means a single item should be lockable in different ways, in case it can be categorized under different keys (we would sometimes like "brain tumor" to be listed under brain and sometimes under tumors). foot_0 3 method expanding the initial list. we assume that the strings in the initial list are maximal, meaning that the string captures the extracted noun-phrase including all of its possible modifiers. we further expand the list by considering also potential substrings of each maximal string, reflecting different granularities. for example, from the string "severe pain in the lower right leg" we would extract "pain", "severe pain" , "severe pain in the leg", "severe pain in the lower right leg", among others. 3 we then consider the union of the initial set of input strings and the set of additional sub-strings. different users would be interested in different granularities depending on their information need. we rely on the dag-pruning stage to properly organize these strings and prune away non-informative ones in the context of the entire set. initial grouping into equivalence sets. the input of this stage is a set of strings (the union of the input set and the extended set), and the output is a list of sets, such that the sets are distinct, and their union covers the initial set. for example, after this stage, the items "herniated disk", "herniated disc", "disc herniation", "herniation of the disc" will be in the same equivalence set. the grouping in this stage is inspired by @xcite and is based on considering each string as a bag of lemmas, discarding stop words, modal words, and quantity words, and considering items as equivalent if their bags are equivalent. the lemma matching is relaxed, and allows, beyond exact string match, also matches with small edit distance and matches based on umls @xcite and wordnet @xcite spelling variants and synonyms. ## input-output example we demonstrate with a minified example. given the set of spans in figure (2a ), representing causes of chest pain, hierarchy builder expands the set by adding the spans "rib fracture" (this is a substring of two existing spans) and "respiratory diseases" (a new taxonomic node). based on the expanded set of spans in figure (2b ), hierarchy builder identifies synonymous spans and merges them into the concepts. in figure (2c ) we see these concepts, where each concept includes aliases in parenthesis where applicable. hierarchy builder then places the entries in a dag based on a hierarchy of specificity, as depicted in figure (2d) . ## experiments and evaluation scope we focus on the medical domain and evaluate our system on etiologies (causes) of two medical symptoms ("jaundice" and "chest pain"). these symptoms were chosen because their are common and each contain many different etiologies mentioned in the literature. the input lists for the system were the result of running a set of 33 syntactic patterns over pubmed abstracts, looking for patterns such as "cond due to ___" or "patients with cond after ___" where cond is either jaundice or chest pain. the results were extracted using the spike system @xcite and each matched head-word was expanded to the entire syntactic subgraph below it. this resulted in 3389 overall extracted strings and 2623 unique strings for jaundice and 2464 overall and 2037 unique for chest pain. after merging strings into synonym sets as described in §3, we remain with 2227 concepts for jaundice and 1783 for chest pain. for each of the symptoms there are established and widely accepted lists of common etiologies, which we rely on in our evaluation. 8 we take 38 established etiologies for jaundice and 33 for chest pain, and check their accessability in the flat list of extracted symptoms, as well as in the hierarchical dag we create. coverage and entry-point selection for jaundice, our input list contains 28 out of the 38 known etiologies, and for chest pain 26/33. with @xmath0, 25 of 28 concepts are reachable from an entry point for jaundice and 21/26 for chest pain. with @xmath1. ## conclusions we presented an automatic method to organize large lists of extracted terms (here, of medical etiologies) into a navigable, dag-based hierarchy, where the initial layer provides a good overview of the different facets in the data, and each internal node is has relatively few items. the code together with a video and an online demonstration are available at https://github.com/itayair/ hierarchybuilder .