Query-driven Exploration of Big Graphs

MohammadHossein   Namaki

Exploring graph-structured data either by mining or querying is a fundamental operation that enables important applications including knowledge graph search, social network analysis, and cyber-network security. Given the proliferation of complex data in the forms of large-scale heterogeneous and dynamic graphs, it is preferable while difficult to revisit traditional query-response paradigms. Graph query construction is a daunting task and typically requires multiple iterations either due to the complexity of the schema, unfamiliarity to the data, or not having pre-determined goals. To ease the access and consumption of such rich information, there is a need to complete the existing graph-based analytical systems for exploration. In response to this requirement, the dissertation focuses on the problem of query-driven graph exploration and develops a framework to aid users in exploration of both static and dynamic graphs. Query-driven exploration allows the users to explore a fraction of the data by providing a desired but potentially incomplete analytical query (e.g. keywords, graph pattern query). It then retrieves answers to the initial query in the hope of obtaining feedback such as an updated query, examples of desired answers, or questions on why the results are not satisfactory. By focusing on interesting fraction of the data, query-driven graph exploration meets the usability and response-time requirement of real-world applications. It reduces the excessive results that may be retrieved by conventional graph mining techniques, decreases the irrelevant answers to the users' needs, and improves efficiency by e.g. local search. Hence, to support effective graph exploration with keywords as a user-friendly tool, the thesis first introduces cost-aware keyword exploratory search. Second, by proposing a class of event patterns that pertains to a set of keywords, the thesis extends exploration to the dynamic graphs. It then develops incremental algorithms to detect such patterns and the association rules among them. Finally, to aid users debugging their pattern queries by asking why the results are not satisfactory, a set of algorithms are developed. The thesis experimentally verifies the efficiency and effectiveness of the proposed approaches using real-life graphs.

Query-driven Exploration of Big Graphs

Files and links (1)

Abstract

Metrics

Details