Research On Multi-entity Association Search And Pattern Mining

Nowadays,graph has been wildly adopted as information representation in rising application,like Google's Knowledge Graph and Semantic Web application based on Resource Description Framework(RDF).Graph-structured data describes attributes of and relations between entities in the domain of interest.In particular,entities and their binary relations form an entity-relation graph.Entities in this graph are not only directly connected by arcs representing explicit relations,but also indirectly connected by paths and subgraphs representing implicit relations.Searching for associations(or relationships)between entities is a common type of information needs in many domains.Yet,with the scale of graph data increasing,searching association among entities becomes extremely challenging.On the one hand,the searching space would be tremendous which makes the searching,per se,difficult.On the other hand,the number of association found by searching is also huge,which suffers users in their understanding and exploring the results.This thesis studys these problems over large-scale graph-structured semantic data representing relations between entities,like Knowledge Graphs,in which a semantic association is defined as a minimal connected subgraph covering all the query entities.Different from traditional methods which retrieve top-ranked results,this thesis aims to realize exploratory search by finding all the semantic associations and mine their common conceptual patterns,to group and summarize the results and facilitate understanding and exploration.In particular,there are three folds contributions:1.Proposed a distance-base pruning algorithm to search associations.This algorithm can not only process the traditional association searching between two entities,it is also capable to seach associations among multiple entities.Simultaneously,a canonical code and a novel total order,which is wildly used,are defined and exploited to dedulplicate the searched associations.2.Proposed a skeleton-based partition strategy to mine frequent association patterns.This strategy exploits the graph structure of an association and the label set of it's vertices,i.e.skeleton,at the same time,which contributes to a finer granularity of the association blocks.Accordingly,it can efficiently exclude semantic association patterns that are unlikely frequent.3.Performed extensive experiment to evaluate the proposed algorithms.Realworld large scale graphs that vary in different dimensions are exploited to evaluate the proposed association searching algorithms and pattern mining algorithms.Specifically,we observe algorithms'performance under different parameter settings.