KS-GNN: Keywords Search over Incomplete Graphs via Graph Neural Network
Year: 2021

Abstract:
Keyword search is a fundamental task to retrieve information that is the most relevant to the query keywords. Keyword search over graphs aims to find subtrees or subgraphs containing all query keywords ranked according to some criteria. Existing studies all assume that the graphs have complete information. However, real-world graphs may contain some missing information (such as edges or keywords), thus making the problem much more challenging. To solve the problem of keyword search over incomplete graphs, we propose a novel model named KS-GNN based on the graph neural network and the auto-encoder. By considering the latent relationships and the frequency of different keywords, the proposed KS-GNN aims to alleviate the effect of missing information and is able to learn low-dimensional representative node embeddings that preserve both graph structure and keyword features. Our model can effectively answer keyword search queries with linear time complexity over incomplete graphs. The experiments on four real-world datasets show that our model consistently achieves better performance than state-of-the-art baseline methods in graphs having missing information.

heading: 1 Introduction
text: Keyword search is an important research topic which allows users to provide query keywords and returns the most relevant results. The keyword search over graph data [1] usually retrieves top-k subtrees or subgraphs which contain all the query keywords ranked according to some criteria. For example, He et al. [2] propose a general scoring function considering both graph structure and content, and they aim to find top-k nodes where each node can reach all query keywords, and the sum of its shortest path distances to these keywords is as small as possible. This ranking method is commonly used in later graph keyword search works [3, 4].
∗Corresponding author.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
All existing studies assume that the graph data is complete and has no missing information. However, real-world graphs usually have some missing edges [5] and missing attributes on some nodes [6]. This renders previous graph keyword search methods unable to find exact answers when dealing with such incomplete graphs. Figure 1 shows an example keyword search query over graphs. Given q={c, e, f}, on the left graph G with no missing information, the best node is v4, since it contains keywords c and f , it can reach v5 containing e, and its sum of the shortest path distances to all query keywords is the smallest which is 1 (the shortest distances of v4
to c, e, and f are 0, 1, and 0). However, on the right graph G′ which has a missing edge and a node with missing attributes, the result becomes v1, v2 or v6, and the subtree consists of {v1, v2, v6}, with a total distance of 2.
To handle the missing information, one simple idea is to first utilize some state-of-the-art graph completion models (such as SAT [6]) to predict the missing information and then apply the existing algorithms (such as BLINKS [2]) to find the answers from the graph with predicted keywords and edges. However, such a completed graph contains many noises and errors comparing with the original graph, and thus this method has poor performance as shown in our experimental study. To capture the latent information of the incomplete graphs, we propose to utilize the graph neural network (GNN) for graph keyword search. GNN has been widely applied in tasks such as link prediction [7, 8, 9], node classification [10, 11], and node clustering [6, 12], but existing models cannot be directly applied to keyword search since they usually embed all the features (keywords) of a node into a single vector and they cannot obtain the representation for the individual query keywords.
We firstly design two naïve approaches based on GNN and dimension reduction. To achieve better performance, we propose a novel auto-encoder and GNN-based model using the message passing mechanism, called KS-GNN. The model mainly consists of three components: an encoder that transforms the original keyword information to low-dimensional embedding vectors; a decoder that aims to reconstruct the high-dimensional representation of keywords from the embedding; a message passing-based aggregation mechanism that preserves the shortest path information between keywords and the target node. Different from the existing graph keyword search works, we propose to leverage GNN to obtain representative node embedding that contains the keyword information, taking the latent graph structure, keyword distribution, and keyword frequency information into account. Meantime, the proposed KS-GNN is able to encode the input query as a low-dimensional vector by its learned powerful encoder, and the results are obtained by computing the similarity between the query embedding and node embeddings. This also speeds up query processing time to linear complexity.
The main contributions of our approach are as follows:
• To our best knowledge, this is the first work on keyword search in graphs with missing information.
• We propose an auto-encoder and GNN-based model KS-GNN to solve the problem effectively without having to know the complete information of the input graph.
• The experimental results on four real-world datasets show that our proposed model consistently outperforms several baseline methods.

heading: 2 Related Work
text: Keyword Search in Graphs. Keyword search over graph data aims to find the top-k subtrees or subgraphs according to some ranking criteria. The conventional methods design algorithms assuming that the graphs have complete information. For example, DBXplorer [13] proposes to utilize the number of the answer’s edges as the scoring function. BANKS [14] model tuples as nodes in a graph and then performs keyword search using proximity-based ranking. He et al. [2] propose a general ranking function considering both graph structure and content. BLINKS also builds an efficient bi-level index structure to improve efficiency. Kargar and An, motivated by the Steiner tree problem,
use the total edge weight in ranking answers [15]. There also exists studies on keyword search in temporal graphs [16], uncertain graphs [17], knowledge graphs [18], RDF graphs [19], etc. However, real-world graphs may usually be incomplete. As all the state-of-art keyword search methods retrieve the exact answer, the missing information (keywords or edges) imposes a significant effect on the query results. To address this issue, we propose a graph representation learning-based solution to solve the top-k keyword search problem on incomplete graphs.
Graph Neural Networks. As a powerful branch of graph representation learning methods, the graph neural network has been widely used in recent years due to its excellent performance. The models in the early years are usually based on the so-called graph convolutional network (GCN) [20, 21, 22], which is based on the Fourier transform theory of graphs developed by Shuman et al. [23]. However, research in recent years has shown that the GCN-based methods can be represented by the message passing mechanism, which is more consistent with the experimental results [24]. The Graph Attention Network (GAT) [11] is one of the representatives of graph neural networks based on the message passing mechanism. GAT introduces the attention mechanism to calculate the attention coefficient between nodes and then uses it to assign different weights to neighbors’ information. Based on the auto-encoder and GCN, Graph auto-encoder (GAE) [25] is proposed to reconstruct the adjacency matrix. Moreover, there are some GNN-based works that aim to predict and impute missing data to a data matrix [6, 26, 27]. However, all the methods mentioned above cannot directly handle the graph keyword search problem. To our best knowledge, this is the first work that leverages GNN to process keyword search on incomplete graphs.

heading: 3 Problem Statement
text: A graph keyword search query q = (wq1 , wq2 , ..., wqm) contains a set of query keywords, and it searches relevant results from a graph2 G = (V, E ,W), where each node v ∈ V , each edge e ∈ E , and each keyword w ∈ W . For each node v, it is associated with a set of keywords {wv1 , wv2 , ..., wvn}. In this work, we study the keyword search problem over an incomplete graph. To alleviate the effect of the missing information to keyword search over incomplete graphs, we assume that in the original graph the query results are obtained by applying the BLINKS scheme [2] (a commonly used graph keyword search method). Given a query q, let s(v, q) denote the score of the node v. According to [2, 3, 28, 29, 30], s(v, q) = ∑m i=1 distmin(v, wqi), where distmin(v, wqi) computes the shortest path distance from node v to a node containing wqi . BLINKS aims to find top-k nodes where each node can reach all query keywords in the graph, and the scores of the k nodes measured by s(v, q) are the smallest. E.g., in Figure 1(a), s(v4, q) = distmin(v4, c) + distmin(v4, e) + distmin(v4, f) = 1.
Problem Definition. Given an incomplete graph G′ = (V, E ′,W ′, rw, re), where E ′ ⊆ E ,W ′ ⊆ W , and the proportions of nodes with missing keywords and of missing edges in G are denoted by rw and re, respectively. Given a query q, the incomplete graph top-k keyword search problem aims to find a set S = (v1, v2, ..., vk) of k nodes from G′ such that for any vertex v′ /∈ S, s(v′, q) ≥ max({s(vi, q)|vi ∈ S}).

heading: 4 Proposed Methods
text: We propose to solve the keyword search problem with an unsupervised graph representation learning method, since the representative low-dimensional node embeddings can capture the latent information of the input incomplete graph and thus can help recovering the missing information. In addition, low dimensional node embeddings can speed up the query processing by comparing the node embedding with the generated query embedding at the cost of linear complexity. In this section, we first propose two naïve methods that are based on GNN and dimensionality reduction methods, and then we introduce our proposed KS-GNN in details.

heading: 4.1 Naïve Methods
text: Conv-OH. Graph convolutional layer has been widely used in GNNs, which enables GNN models to gather information from neighbor nodes. Our first naïve method Conv-OH utilizes the graph
2For ease of presentation, we focus on the undirected graphs, and it is easy to extend the proposed method in directed graphs by passing messages along the edges.
convolutional layer and takes the one-hot encoding of keywords as the input feature for nodes due to the scoring function mentioned in Section 3. Conv-OH is able to return the same answer as does BLINKS [2], if the graph has no missing information and l is large enough.
Frg. 2 shows the message passing and aggregation of Conv-OH. Specifically, with |V| = N and |W| = M , the one-hot encoding of node v is denoted by x = {0, 1}M with hv,j = 1 if wj is a keyword associated with v and 0 otherwise. Therefore, the input feature matrix is denoted by X ∈ {0, 1}N×M . Let Hl denote the output node embedding of the l-th layer and hlv denote the v-th row of Hl, we have:
hl+1v = Aggregate ( {f(hlu),∀u ∈ N (v)} ∪ {hlv} ) , (1)
where H0 = X, f(·) denotes a transform function and N (v) denotes the neighbors of node v. Using the combined distance as the scoring function (described in Section 3), Eq. (1) can be written as:
hl+1v = Ω ( {1(hlu) ◦ (hlu + 1),∀u ∈ N (v)} ∪ {hlv} ) , (2)
where Ω(·) denotes the element-wise minimum function which ignores zeros, ◦ denotes the elementwise product, and 1(·) denotes the indicator function that the element of 1(h) is 1 if the input element is positive and 0 otherwise. For instance, Ω({[0, 0, 1, 1], [2, 0, 0, 2]}) = [2, 0, 1, 1], and 1([0, 2, 0, 3]) = [0, 1, 0, 1]. With Eq. (2), the output of Conv-OH is an N ×M matrix, denoted by Z. Note that there is no dimensionality reduction in Conv-OH and thus this method consumes huge space. The node embedding hlv of v also represents the shortest path distances between the keywords and v. Specifically, if hlv,i > 0, it means that the shortest path distance between v and wi is h l v,i − 1, and v cannot reach wi within l hops if hlv,i = 0.
For the query processing, given q, we can obtain the one-hot encoding of q, denoted by xq . Therefore, given the output node embedding Z, the sum of graph shortest-path distances between nodes and the query keywords can be computed with xqZ>, and the space complexity is O(NM). It is obvious that Conv-OH cannot deal with the missing information, but it provides some hints to propose more advanced methods.
Conv-PCA. Principal component analysis (PCA) is a classic dimensionality reduction technique in multivariate statistical analysis [31]. In order to facilitate data storage and query processing, we propose another naïve PCA-based method to solve the keyword search problem.
Given the one-hot encoding matrix X as the input feature matrix, PCA is able to keep d principal components of X with Xp = XU>, where the rows of U ∈ Rd×M form an orthogonal basis for the d features that are decorrelated [32]. It is worth noting that we can obtain the reconstructed feature matrix X′ with X′ = XpU. The learning object is to minimize Lpca = ||X′ −X||22, where || · ||2 denotes the L2 norm.
Inspired by the graph convolutional layers of Conv-OH, we propose Conv-PCA with the convolutional layers as below:
hl+1v = max ( {αhlu,∀u ∈ N (v)} ∪ {hlv} ) , (3)
where α ∈ (0, 1) is a decay parameter used to estimate the shortest path distances in Eq. (3), since the dimension is reduced from M to d and thus it is difficult to discriminate M keywords within the d dimensions (d M ). Specifically, a larger cumulative decay corresponds to a larger shortest path distance. Conv-PCA takes Xp as the initial node embedding (H0 = Xp). This mechanism performs better than directly using PCA in experiments as shown in Section 5.3. For the query processing, given q, we can obtain the query embedding hq = xqU>. Therefore, given the output node embedding Z, the similarity scores between nodes and the query keywords can be computed by hqZ> with linear space complexity O(dN), where the dimension d is a small constant.
Compared with Conv-PCA, Conv-OH utilizes each element of hv to record the shortest path distance between keywords and v and cannot reduce the dimension of node embedding. Conv-PCA can more efficiently process the keyword search query and requires less space than Conv-OH, but neither of them can well handle the missing information in incomplete graphs.

heading: 4.2 KS-GNN
text: Based on the prior discussions on Conv-OH and Conv-PCA, we present the desiderata that guide the development of our method for tackling keyword search as follows:
Dimensionality Reduction. Taking the one-hot encoding matrix X as input, it is difficult to afford the cost of generating an output with size N ×M . Therefore, the model should be able to reduce the dimensions of the output node embedding M to a lower level.
Key Information Preservation. Some keywords and edges information may be lost in the process of dimensionality reduction, which affects the performance of keyword search. The model should retain as much key information as possible to guarantee results quality.
Adaptive Encoding. When generating node embedding, the model should consider the structure information of the target node centered subgraph and the distribution of keywords on the subgraph, rather than only considering the keywords of the target node. Specifically, to recover the missing keywords information in the incomplete graph, the model should be able to capture latent relationships among different keywords. For instance, a pair of keywords "AI" and "ML" often co-occur on nodes near to each other (e.g., one-hop neighbors). Given a node containing either "AI" or "ML", it is natural to assume that the neighbor of this node is more likely to contain the other keyword than the nodes whose one-hop neighbors do not contain either of the two keywords.
Keyword Frequency Awareness. Based on the scoring function in Section 3, the returned top-k nodes tend to be decided by the query keywords with low frequency compared to the high-frequency ones. Thus, for a given keyword, the number of nodes containing it (we denote this by the keywords’ node frequency) can reflect its importance to the query processing, similar to the inverse document frequency (IDF) used in information retrieval. The keyword set of the whole graph can be regarded as a corpus and the keyword set of each node can be regarded as a document. Therefore, the model
should encode keywords taking in consideration of their frequencies, which are measured based on the keyword node frequency in the whole graph3.
Based on these desiderata, we propose an auto-encoder based Keyword Search Graph Neural Network (KS-GNN) for tackling the problem in incomplete graphs. An illustration of the message passing and aggregation mechanism for generating the node embedding h3 with KS-GNN is provided in Fig. 3.
Encoder and Decoder. KS-GNN employs an encoder f to generate low-dimensional node embedding for dimensionality reduction. Recall that in Conv-PCA, the dimension reduction caused information loss and it is hard to discriminate keywords in the low-dimensional space. To address this issue, for the sake of key information preservation, KS-GNN employs another decoder g which aims to reconstruct the input from embedding space. By training f simultaneously with g, the output embedding of f is able to preserve key information of the input graph. Given the one-hot encoding matrix X as the input, we define H = f(X) where H ∈ RN×d. For the decoder, it is defined as X′ = g(H) where X′ ∈ RN×M . In this work, we utilise the multi-layer perceptron (MLP) with a nonlinear activation layer [33] as both non-linear encoder and decoder. It is worth noting that MLP can be replaced by a more complex neural network. Our goal here is to use simple encoder and decoder to show the advantages of the proposed mechanism. In addition, as a conventional learning objective of the auto-encoder, f and g are trained to minimize:
L1 = 1
N ||X′ −X||22. (4)
It is worth noting that the representation PCA learns is essentially the same as that learned by a basic linear auto-encoder. However, the encoder f and the decoder g here are not necessarily linear functions and thus are able to learn more representative node embeddings than the linear ones.
Message Passing and Aggregation. The message passing and aggregation mechanisms for both Conv-OH and Conv-PCA are based on the orthogonal basis and decorrelated features. However, in KS-GNN, its encoder f transforms the input without any basis, and thus we cannot simply apply the max(·) function to capture the information of the nearest keywords on a node. Thanks to the reconstruction ability of the decoder g, we can utilise g to reconstruct the M -dimension encoding during the message passing and then using max(·) at this step. Moreover, if the learned node embedding contains the latent information of the missing keyword of the incomplete graph, g can also help recover the missing keywords during the reconstruction. Formally, given the output node embedding Hl of l-th layer, we have:
hl+1v = f
( max ( {αg(hlu),∀u ∈ N (v)} ∪ {g(hlv)} )) , (5)
where α ∈ (0, 1) is a decay parameter that is the same as the one in Eq. (3). As Eq. (5) shows, the M -dimension embedding will only be generated by the decoder g during the message passing and aggregation, while the hidden node embedding and the final output node embedding are both d dimensions. Therefore, it meets the requirement of dimensionality reduction. The message passing and aggregation can be processed in parallel, and the time-complexity is acceptable. It is worth noting that in incomplete graphs, due to the mechanism of message passing and aggregation, nodes without any keyword information can still be embedded accordingly.
Subgraph keywords-based Node Similarity. To realize adaptive encoding, we propose to train KS-GNN by a triplet siamese network [34] with a triplet loss [35] according to the subgraph keywords-based node similarity, which enables KS-GNN to capture the latent missing keyword and edge information on incomplete graphs. For a node v, we consider the subgraph SGv containing all the neighbors of v within k hops for measuring node similarity. The one-hot encoding of this subgraph SGv is denoted by xSGv . For instance in G
′ shown in Fig. 1, given k = 1, the 1-hop subgraph of v5 contains keywords {a, c, d, e, f} with the corresponding one-hot encoding xSG′5 = (1, 0, 1, 1, 1, 1). Similarly, the one-hot encoding of the subgraphs around v4 and v6 are xSG′4 = (1, 1, 1, 0, 0, 1) and xSG′6 = (1, 1, 1, 1, 1, 1), respectively. Therefore, by counting the number of common keywords as the similarity scoring function, we can compare the similarity between (v5, v4) and (v5, v6) by
3The multi-occurrence of a keyword on one node only contribute 1 to this keyword’s node frequency.
comparing xSG′5x > SG′4 = 3 and xSG′5x > SG′6 = 5. Specifically, xSG′5x > SG′4 < xSG′5x > SG′6 indicates (v5, v6) are more similar than (v5, v4) in G′.
Given G′, the KS-GNN model denoted by φ, and a sampled batch of triplets T = {t1, t2, ...tn} = {(vo1, vp1, vq1), (vo2, vp2, vq2), ..., (von, vpn, vqn)}, KS-GNN is trained to minimise:
L2 = 1 |T | ∑ ti∈T max ( m− sgn(ti) ( φ(X)oiφ(X) > pi − φ(X)oiφ(X) > qi ) , 0 ) , (6)
where m is a margin hyper-parameter of the hinge loss, sgn(·) denotes a sign function that sgn(ti) returns 1 if (voi, vpi) are more similar than (voi, vqi) and −1 otherwise. Thus, KS-GNN can learn the structure and keyword information from the subgraphs involved.
For large-scale datasets, it might be time-consuming to compute sgn(ti). In this case, it is acceptable to intuitively sample T based on the links. For example, for a sampled node voi , vpi can be sampled from the 1-hop neighbors of voi , and vqi can be negatively sampled from unconnected nodes of voi , thereby setting sgn(ti) to 1. Eq. (6) still takes both the graph structural information and the keyword distribution into account by feeding the one-hot encoding of subgraph keywords to KS-GNN. In addition, minimizing Eq. (6) helps generate similar adaptive embedding for the keywords which co-occur commonly.
Keyword Frequency-based Regularization. Intuitively, if a keyword appears on many nodes, it is regarded as less important than the keyword which appears on fewer nodes for query processing. Therefore, in this work, we consider the keyword node frequency, denoted by ci, that indicates the number of nodes containing keyword wi. For instance, in G′ shown in Fig. 1, c1 = 2 and c2 = 2 for keywords a and b, respectively. We propose to enhance the model’s keyword frequency awareness with a regularization that minimizes:
L3 = 1
M ∑ wi∈W ci||f(Ii)||2, (7)
where I denotes an M ×M identity matrix, and Ii denotes the i-th row of I. Feeding Ii in f can return the representation of keyword wi, and minimizing Eq. (7) aims to differentiate the lengths of keyword embeddings according to their keyword frequencies, thereby being aware of keyword frequency.
To train KS-GNN, the final learning objective is to minimize:
L = λ1L1 + λ2L2 + λ3L3, (8)
where λ1, λ2 and λ3 are hyper-parameters. By minimizing Eq. (8), we can optimize KS-GNN to generate informative node embedding which can capture the latent representation of missing keywords and edges. The superiority of the proposed KS-GNN is validated in Section 5.3.
Query Processing. To process query q, given the one-hot encoding of q as xq , the trained encoder f and the learned node embedding Z, we can compute the similarity between the nodes and query with sq = f(xq)Z>, and the top-k answers can be found with the largest scores in sq. In addition, the space complexity of computing query processing is O(dN).

heading: 5 Experiments
text: In this section, we evaluate the performance of our proposed approach, KS-GNN, on four real-world datasets, including citation networks (CiteSeer), co-purchase networks (Video & Toy) and co-author networks (DBLP). The details of datasets, additional experimental results and analysis can be found in the supplementary materials.

heading: 5.1 Baseline Methods
text: We compare our model against five baseline methods, including a state-of-the-art deep learning based missing-data completion GNN model. More details on the baseline models are provided in the supplementary materials.
• GraphSAGE [10] is a representative GNN-based graph embedding method. We add an MLP encoder for GraphSAGE to address the keyword search problem for GraphSAGE.
• BLINK+SAT firstly predicts and completes the missing keywords and edges with a stateof-the-art missing-data completion GNN model SAT [6] and then utilises BLINK [2] to process keyword search on the new graph.
• PCA is based on the classic dimensionality reduction technique [31]. • Conv-PCA is a naïve method proposed in Section 4.1. • KS-PCA is a simplified variant of our proposed KS-GNN that replaces the MLP encoder and
decoder with PCA transformations. Specifically, it leverages U to reconstruct M -dimension embedding from hv .

heading: 5.2 Experimental Setup
text: In our experiments, we compare the proposed method with baseline methods for keyword search tasks in two kinds of graphs: (1) the graphs with only missing keywords; (2) the graphs with both missing keywords and edges. For each dataset, to simulate a real-world scenario and quantitatively control the ratios of missing information, we process the original datasets with two steps: (1) hide the keywords of randomly sampled nodes with a predefined proportion (denoted by rw) in the graph; (2) randomly hide a proportion (denoted by re) of the edges in the graph. Let nq = |q| denote the number of words in the query q, we randomly sample 100 queries as the test set for each value of nq ranging from 3 to 9 with a step of 2.
In addition, in each incomplete graph, the validation set consists of 100 randomly generated queries with ground truth answers. We tune the hyper-parameters of compared methods with the grid search algorithm on the validation set, more details can be found in the supplementary materials. In terms of the evaluation metric, we use Hits@K, which is a common ranking metric that counts the ratio of positive edges that are ranked at the K-th place or above. The ground truth is the top-K answers retrieved by BLINK on the original graph for each dataset. Specifically, we report Hits@100, and more experimental results (Hits@10 and Hits@50) can be found in the appendix.

heading: 5.3 Performance of Keyword Search
text: Table 1 shows the comparison results in graphs with rw adjusted from 0.3 to 0.7 and nq adjusted from 3 to 9. As shown in the table, KS-GNN and KS-PCA significantly outperforms the baselines, and changing rw will not affect its performance. Moreover, the performance of KS-GNN better when more query keywords are given. As for the baselines, BLINK+SAT cannot maintain good performance when many keywords are missing. Compared with Conv-PCA, KS-PCA can address the keyword search in incomplete graphs much more effectively due to the proposed novel message passing and aggregation mechanism. Although KS-PCA and KS-GNN have similar message-passing mechanisms, KS-GNN performs better in most cases due to its more representative output node embeddings. This reveals that the proposed learning objective and auto-encoder-based model are able to enhance the ability of representation learning. Since PCA focuses on each single node, it performs well when the query keywords are located on the same node. However, when nq increases, the query keywords tend to be located on different nodes, and the performance of PCA therefore decreases because it cannot gather neighbor information. By contrast, although GraphSAGE can aggregate information from neighbors, it sometimes performs worse than PCA, because only utilizing the max-pooling operator during the message aggregation cannot well distinguish the information from each unique keyword. This can be proved by that Conv-PCA performs better than both PCA and GraphSAGE, which also indicates the superiority of our proposed encoder and decoder-based message passing and aggregation mechanism.
Table 2 presents the results of the comparison in graphs with both missing keywords and edges, where re is set to 0.3 and rw is adjusted from 0.3 to 0.7. As the table shows, KS-GNN still outperforms other compared baseline methods in most cases since it can learn the adaptive embedding and structural information from the incomplete graph with missing keywords and edges. Compared with Table 1, Table 2 shows that the effect of missing edges cannot be reflected for the powerless methods, such as GraphSAGE and BLINK+SAT, because they might gather noisy information from neighbours. For KS-GNN, the effect of missing edges varies on different datasets. For instance, KS-GNN is more robust on CiteSeer and DBLP than on Video and Toy.

heading: 5.4 Ablation Study
text: In this section, we further investigate how each component in Eq. (8) affects KS-GNN’s performance. The experiments are conducted in the incomplete graphs with re = 0 and rw = 0.3 on four datasets. For the queries, the number of keywords is set to nq = 3. Based on Eq. (8), we have three variants which are trained with different learning objectives, denoted by without L1, without L2 and without L3, respectively. For instance, the learning objective is λ2L2 + λ3L3 for the variant without L1. The hyper-parameters are still tuned with the grid search algorithm. The results of Hits@100 scores are shown in Table 3. As the table shows, among each component in Eq. (8), the average performance gains for L1, L2 and L3 on four datasets are 12.23%, 6.87% and 10.32%, respectively. The results also show that these three learning objectives play different roles on different datasets.

heading: 6 Conclusion
text: Keyword search in graphs is an important problem with many applications such as network analysis and recommendation. The keywords and edges in graphs might be lost or incomplete due to some reasons in real-world applications, such as storage limitation or privacy issues. In this paper, we study the keyword search problem in incomplete graphs and propose a novel auto-encoder and GNN-based method, KS-GNN. Compared to existing methods, KS-GNN is able to address the problem when some nodes have missing keywords or some edges are missing in the input graphs. The results of extensive experiments on real-world datasets reveal that KS-GNN significantly outperforms the state-of-the-art baseline methods on the incomplete graph keyword search task.
Acknowledgments and Disclosure of Funding
Xin Cao is supported by ARC DE190100663. Yixiang Fang is supported by CUHK-SZ grant UDF01002139.

Review summaries:
This paper introduces KS-GNN, Keywords Search GNN over Incomplete Graphs. More specifically, KS-GNN employs joint training on autoencoder (dimension deduction), keyword-based node similarity in subgraphs, and keyword frequency regularization to facilitate a complex keyword search task on incomplete graphs (missing keywords in node attributes and edges). Experimental results have proven the effectiveness of the proposed KS-GNN over multiple baseline approaches compared to various standard benchmarks.

This paper addressed an important problem that can answer queries in graph where some information is missing(edges and nodes). The proposed solution is based on auto-encoder and GNN. Here, the auto-encoder learns a low dimensional embedding for the node which was used to compute the score top-N ranked candidates based on similarity scores. Their method shows results better than other methods in the experiments.