DKS: A GNN-based method for keyword search on dirty graphs

Most existing graph keyword search works assume that graph data are complete and clean, with no missing information (such as keywords or edges) and contaminated information (such as keywords) on the graph. However, real-world graphs often contain missing or contaminated data, making keyword searches on such graphs particularly challenging. To address the problem of keyword search on incomplete or contaminated graphs, we propose a transformation paradigm that converts such searches into estimated keyword queries within an embedding space. Furthermore, we designed a specific framework named dirty graph keyword search (DKS). DKS is able to simultaneously answer the keyword search on incomplete or contaminated graphs within linear time and space complexity (both are O(m · n), where m is the number of graph keyword types and n is the number of nodes in the graph). In the offline phase, DKS first employs a graph neural network-based model to clean the contaminated graph or complete the incomplete graph. Then, by capturing neighbourhood keyword distributions and graph structures for each node on the graph, DKS generates an embedding that represents each node within the embedding space. In the online phase, keyword search results are derived based on these node representations. We conducted experiments on five real datasets to evaluate the effectiveness and efficiency of DKS. The results revealed that DKS achieves up to 2-5x Hits@100 improvement on contaminated graphs and 1–2.8x Hits@100 improvement on incomplete graphs compared to the state-of-the-art methods.