Interactive Search and Summarization on Hierarchical Directed Acyclic Graphs

Hierarchical Directed Acyclic Graph (HDAG) is an essential model widely adopted to represent hierarchical terminologies and their relation structure, such as for disease ontology, gene ontology, Wikipedia categories, ImageNet categories, medical entity directories, the ACM computing classifi- cation system, and so on. An interactive HDAG search leverages human intelligence to categorize target labels in an HDAG, which is useful for image classification, product categorization, and database search. However, many existing studies of interactive HDAG search aim at optimally identifying a single target, and are limited by asking too many questions and not being able to handle multiple targets. Our preliminary findings have shown the potentials to address these shortcomings and to suggest possible pathways towards stronger solutions (e.g., finding higher-quality answers of multiple targets using a few questions) and wider applications (e.g., controlling reward budgets for an economical benefit). Additionally, graph summarization uses small-sized representative vertices and subgraphs to summarize the whole HDAG. This has many useful practical applications, such as summarized recommendations, visual data exploration, and snippet generation in information search. However, due to the massive terminologies and complex structures of HDAGs, it is difficult to summarize the whole graph effectively. Despite fruitful progress on interactive search and graph summarization in HDAGs, there are several open issues and new applications requiring further investigation. In this proposal, we will systematically investigate a family of new problems regarding large-scale HDAG exploration and summarization. Specifically, we plan to design:
1. A budget constrained interactive HDAG search for identifying multiple targets.
2. Query-driven summarization over a weighted HDAG subgraph using k representative vertices.
3. Differential summarization to depict both similarities and dissimilarities between two HDAGs.
4. Novel techniques to support the efficient interactive search and summarization over large- scale HDAGs and develop a user-friendly prototype system.

With our extensive research experience in graph query processing and HDAG summarization, we expect the outcomes of this project to lead to a set of new tools for HDAG interactive search and summarization, thereby improving the recommendation services and graph analytics in the industry.