Abstract: The task of associative entities discovery is to provide user with top-ranked entities in Knowledge Graph (KG). Many entities are not linked explicitly in KG but actually associated in user-generated data, which could enrich entity association in KG’s query processing. In this paper, we leverage user-entity interactions (called user-entity data) to improve the accuracy of KG query processing. Upon the frequent patterns obtained from user-entity data, we construct the Entity Association Rule (EAR) to model the association between entities, and employ confidence to evaluate the strength of association between entities. Furthermore, we obtain the optimal set of EARs based on the branch and bound algorithm, and then obtain the set of association entities most relevant to the query. The experiments show that the precision of discovering the top 1 associative entity could be improved via EAR by 10.7% and 4.1% on two real-world datasets respectively, compared with the traditional KG structure-based methods.