Querying Associative Entities In Knowledge Graph Based On Probabilistic Inferences

The task of querying associative entities(AEs)is to provide user with top-ranked entities in knowledge graph(KG).Recently,as KG has shown rich application value in assisting question answering(Q?A)systems,search engines,and recommender systems,query AEs has become the subject with great attention and key technology in KG research.Meanwhile,lots of user-entity interaction(abbreviated as user-entity data)are quickly generated based on KG-related downstream applications,called user-entity data.In fact,many entities are not linked explicitly in KG but actually associated when incorporating outside user-generated data.Therefore,it is of great significance to use the entity information contained in the user-entity data as a supplement to the task of querying AEs.In this thesis,we adopt the Bayesian network,an important probabilistic graph model,as the framework for representing and inferring the uncertain dependencies of KG entities in the user-entity data to improve the accuracy of query processing.Specifically,upon the association rules obtained from user-entity data,we construct the association entity Bayesian network(AEBN),which represents dependence relations and facilitates inferences of implicit associations between entities.Consequently,we formulate the problem of querying AEs as the problem of probabilistic inferences,and propose the method to rank associative entities by evaluating the association degree between entities via probabilistic inferences over AEBN.Our work can be summarized as follows:(1)We propose a weighting function to calculate the score of entities with respect to the query entity,by which the set of candidate entities that may be associated with the query entity in the data could be obtained.Furthermore,based on association rules mined from user-entity data,we introduce the query entity rule(QER)to describe the dependency between the query entity and candidate entities.Based on the branch and bound algorithm,the optimal QERs could be obtained.(2)To construct the structure of an AEBN,the optimal QERs are represented as Horn clauses,which are then transformed equivalently to the directed acyclic graph(DAG)of the AEBN.Following,based on the logical constraints specified by the Horn clause of each node in AEBN,we normalize the frequencies of frequent entities from user-entity data and give the method to calculate the conditional probability parameters to constitute the conditional probability table(CPTs).(3)To rank AEs efficiently,and to facilitate the expansion of querying AEs processing with respect to large-scale KGs,we propose the approximate algorithm for probabilistic inferences of AEBN based on rejection sampling.The result of probabilistic inferences is adopted as the degree of associations,by which we rank the AEs in descending order.(4)Upon the two real-world datasets,we test the effectiveness of querying AEs and efficiency of AEBN construction.Furthermore,we design and implement the AEBN prototype system to illustrate the practicality of our method.