Semantic Guided and Response Times Bounded Top-k Similarity Search over Knowledge Graphs
share
Recently, graph query is widely adopted for querying knowledge graphs. Given a query graph G_Q, graph query finds subgraphs in a knowledge graph G that exactly or approximately match G_Q. We face two challenges on graph query over a knowledge graph: (1) the structural gap between G_Q and the predefined schema in G causes mismatch with query graph, (2) users cannot view the answers until the graph query terminates, leading to a longer system response time (SRT). In this paper, we propose a semantic guided and response-time-bounded graph query to return top-k answers effectively and efficiently. We first leverage a knowledge graph embedding model to build the semantic graph SG_Q for each G_Q. Then we define the path semantic similarity (pss) over SG_Q to evaluate the match's quality. We propose an A* semantic search on SG_Q to find top-k answers with the greatest pss via a heuristic pss estimation. Furthermore, we make an approximate optimization on A* semantic search to allow users to trade off the effectiveness for SRT within a user-specific time bound. Extensive experiments over real datasets confirm the effectiveness and efficiency.
READ FULL TEXT