Query-driven Exploration of Big Graphs
MetadataShow full item record
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.
Showing items related by title, author, creator and subject.
Yao, Yibo (2016)With the emergence of networked data, graph classification has received considerable interest during the past years. Most approaches to graph classification focus on designing effective kernels to compute similarities for ...
Choudhury, Sutanay (2014)Subgraph search is the problem of searching a data graph for the occurrences of another graph, typically referred to as the query or pattern graph. This thesis is dedicated to studying a specific class of subgraph search, ...
Wu, Changjun (2011)Developing high performance computing solutions for modern day biological problems present a unique set of challenges. The field is experiencing a data revolution due to a rapid introduction of several disruptive experimental ...