KS-GNN: Keywords Search over Incomplete Graphs via Graphs Neural Network
Authors: YU HAO
Xin Cao
Yufan SHENG
Yixiang Fang
Wei Wang
Venue: NeurIPS 2021 Poster (2021)
Keywords: GNN
Keyword search
Graph Representation Learning
Node Embedding

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.

KS-GNN: Keywords Search over Incomplete Graphs via Graph Neural Network
Yu Hao University of New South Wales
Xin Cao" University of New South Wales
NSW, Australia yu yu..haounsw.. edu. au
NSW, Australia xin. www.unsw..eee.cccooo edu
Yufan Sheng
Yixiang Fang
University New South Wales NSW, Australia
Chinese University of Hong
Kong, Shenzhen, China
yufan. www..nuhsgouuss....o. edu.
fangyixiang@cuhk, edu. cn
Wei Wang
The Hong Kong University of Science
and Technology, Guangzhou, China weiwcsBust.hr
Abstract
Keyword search is a fundamental task to retrieve information that is the most relevant the query keywords. Keyword search over graphs aims 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 key- words), thus making the problem much more challenging. To solve the problem of keyword search over incomplete graphs, we propose novel model named KS-GNN based the graph neural network and the auto-encoder. By considering the latent relationships and the frequency of different keywords, the proposed KS-GNN aims alleviate the effect of missing information and 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.
Introduction
Keyword search an important research topic which allows users to provide query keywords and returns the most relevant results. The keyword search graph data [I] usually retrieves top- subtrees or subgraphs which contain all the query keywords ranked according to some criteria. For example, He et al. [2] propose 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 these keywords is small possible. This ranking method is commonly used in later graph keyword search works
Corresponding author.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

All existing studies assumee that the graph data is complete and has no missing information. How- ever, real-world graphs usually have some míss- ing 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. Fig- ssows an example keyword search query over graphs. Given e, on the left graph G with no missing information, the best node is vg since it contains keywords and f, it can reach is containing e, and its sum of the short- est path distances to all query keywords is the smallest which 1 (the shortest distances of 14 to c, e, and are 0, I, and 0). However, on the right graph G' which has missing edge and node with missing attributes, the result becomes U1, U2 or Ug. and the subtree consists of {01, U2, vo with a total distance of 2.
Query q= (c, e, f}
(b, c)
(a, d, e)
(b, c)
(a, d,
(a,
{d. f
(a, bl
fd, f
{c,
{c,
f
(a, e)
(ay
Answer (v1,)
Answers (2), V2, Vol
(a) Graph
(b) Incomplete Graph G'
Figure 1: Example of keyword search on incom-
plete graphs
To handle the missing information, one simple idea is to first utilize some state-of-the th--re-artttttt graph completion models (such as SAT [6]) 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 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 utilize the graph neural network (GNN) for graph keyword search. GNN has been widely applied in tasks such as link prediction 77 1 99. node classification [TO M. and node clustering [6] [1]. but existing models cannot be directly applied to keyword search since they usually embed all the features keeywords) of a node into a single vector and they cannot obtain the representation for the individual query keywords.
We firstly design two naive approaches based on GNN and dimension reduction. To achieve better performance, propose 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 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 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 oiw-dimeniional 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 linear complexity.
low-dimensional embedding vectors; decoder
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 effec- tively without having to know the complete information of the input graph.
The experimental results on four real-world datasets show that proposed model consis- tently outperforms several baseline methods.
2
Related Work
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 [33 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-basee 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 [5]. 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 graph representation learning-basse 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. [3]
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) [1] 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 66 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.
Problem Statement
A graph keyword search query 9 (Wg. : 12 ,.., Wgm) contains a set of query keywords. and it searches relevant results from a graph G = (V,E, W). where each node E V. each edge e E E, and each keyword 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 8(u, g) denote the score of the node v. According to 3 28
W. For each node v, is associated with a set of keywords {wi, wy. ..., w
29 30), s(v, q) in distmin (v, Wa;)) ). where disl.an (v, Wg:) computes the shortest path distance from node to a node containing Wy,- BLINKS aims to find top-k nodes where each node reach all query keywords in the graph, and the scores of the k nodes measured by s(t, q) are the smallest. E.g., in Figure I(a), s(V1, q) = dist (V1, c) + distman (Ua, e) - dist (Ug, f) = 1.
Problem Definition. Given an incomplete graph G' = (V,,', W, Te, and the proportions of nodes with missing keywords and of missing edges in G are denoted by Tw and re. respectively. Given a query q, the incomplete graph top-k keyword search problem aims to find a set (U1, U2,...,yy Uk) of is nodes from G' such that for any vertex v' $ S, s(v', 2 mar( (s 4) |/ E 8)).
Te), where E' E W C W.
4 Proposed Methods
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 naive methods that are based on GNN and dimensionality reduction methods, and then we introduce our proposed KS-GNN in details.
4.1 Naïve Methods
Cony-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
FFrr 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.
3

---

f
Aggregation
122
f f(h2) h2
12
h
h4
f(h2)
Figure 2:
An illustration of the message passing and aggregation of Conv-OH, where vg is target node and it aggregates keyword information from its neighbors.
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 does BLINKS [2], if the graph has no missing information and is large enough.
Frg. shows the message passing and aggregation of Conv-OH. Specifically, with [ N and W M, the one-hot encoding of node v is denoted by x = {0, 1) with he. = wy is keyword associated with and 0 otherwise. Therefore, the input feature matrix is denoted by
X E {0, 11_ N.N Let H' denote the output node embedding of the /-th layer and h', denote the e-th
row of H we have:
h !+1 Aggregate (L(()) ( U (h!)).
where = J() denotes a transform function and (we) denotes the neighbors node v. Using the combined distance the scoring function (described in Section 3). Eq. ①1 can be written as:
h h++1 22 (1b)) (h', + 1u, Yu e N(()) (b!))
where (2-)) denotes the element-wise -wine minimum function which ignores zeros, a denotes the element-
wise product, and 1(-) denotes the indicator function that the element of (1)h is if the input element positive and otherwise. For instance, (2{ 0, 1, 1], [2, O, 0, 2|} = [2, 0, 1, 1]. and ( 2, 0, 3)) [0, 1, 0, 1). With Eq. (2). the output of Conv-OH is an N x 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 hy, of also represents the shortest path distances between the keywords and Specifically, if h4, > 0, it means that the shortest path distance between u and is N 1, and cannot reach w; within hops if A 0.
For the query processing, given g, we can obtain the one-hot encoding of 9, denoted by X.. Therefore, given the output node embedding Z. the sum of graph shortest-path distances between nodes and the query keywords can be computed with x,Z T and the space complexity is O(N M). 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 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 as the input feature matrix, PCA able to keep d principal components of X with X, XUT where the rows of U d form an orthogonal basis for the features that are decorrelated [32]. is worth noting that we can obtain the reconstructed feature matrix X' with X' = X, U. The learning object is to minimize Lpea denotes the 2 norm.
X -X where || lla

---

g
f
a
a
Aggregation
h22
ag(h))
hg
g (h
h23
h
h2
(g
Figure 3: An illustration of the message passing and aggregation of our KS-GNN model.
Inspired by the graph convolutional layers of Conv-OH, we propose Conv-PCA with the convolu- tional layers below:
h = max (aahl, Vu U(o))UU(h))
(3)
where a E (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 discriminate M keywords within the dimensions (d < M). Specifically, a larger cumulative decay corresponds to larger shortest path distance. Conv-PCA takes X, as the initial node embedding (H) Xp). This mechanism performs better than directly using PCA in experiments as shown Section 5.3 For the query processing, given
y. obtain the query embedding h2 x, U Therefore, given the output node embedding Z, the similarity scores between nodes and the query keywords can be computed by h, with linear space complexity O(dN), where the dimension is small constant.
Compared with Conv-PCA, Conv-OH utilizes each element of h,, 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.
KS-GNN
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 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 much key information possible 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 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, pair of keywords "AI" and "ML" " often co-occur on nodes to each other (e.g., one-hop neighbors). Given node containing either "AI" "ML", it is natural to assume that the neighbor 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 Bl the returned top-k nodes tend to be decided by the query keywords with low frequency compared to the high- frequeey ones. Thus, for given keyword, the number of nodes containing (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 the whole graph can be regarded corpus and the keyword set of each node can be regarded document. Therefore, the model
5

---

should encode keywords taking in consideration of their frequencies, which are measured based on the keyword node frequency in the whole grapt
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.
Encoder and Decoder. KS-GNN employs an encoder f to generate low-dimensional node em- bedding 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 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 R xd For the decoder, it is defined as X' g (H) where X' E N.N
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 conventional learning objective of the auto-encoder, f and are trained to minimize:
L1
X X
(4)
worth noting that the representation PCA learns essentially the same as that learned by a basic linear auto-encoder. However, the encoder J 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 í transforms the input without any basis, and thus 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 H' of (-th layer, we have:
h = / (man (man(fo((h)) (log(h)) Vu E N(t)) (o())))
(5)
where a E 10, is a decay parameter that is the same as the one in Eq. G3. 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 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 node v, we consider the subgraph SG, containing all the neighbors of e within hops for measuring node similarity. The one-hot encoding of this subgraph SG, is denoted by xsa. For instance in G' shown in Fig. given & = 1, the 1 h-hop subgraph of us contains keywords (a, c, d,e, f with the corresponding one-hot encoding XsG; = (1, 1,,,,, 1). Similarly, the one-hot encoding of the subgraphs around 1/4 and 0g are Xsc; = 1,,
and Xsc; = (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, u4) and (e5, c6) by
TTe multi-oceurrence of keyword one node only contribute I to this keyword's node frequency.

---

comparing xsa, ss, = 3 and xsa; ss 5. Specifically, Xsa, < XsG, sGg indicates (v5, v6) are more similar than (e5, v4) in G". Given G", the KS-GNN model denoted by o, and a sampled batch of triplets T (2,,tt {(V01, Up1, 112)), (Voz, Uy2, 1122); .... (Von, Upn: (gn)), KS-GNN is trained to minimise:
T
L2
1
Σ GET
max sgg((t))) (ogn(()((((()))))))))))))))))))
((X)),,(X))))..)
IT
where m is margin hyper-parameter of the hinge loss, sgn(.) denotes a sign function that stn(t:) returns 1 if (Voi, Upi) are more similar than (Voi, Cgi) 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 stn(t;). In this case, it is acceptable intuitively sample based the links. For example, for sampled node Vo Up, can be sampled from the 1-hop neighbors of Vo and Eg; can be negatively sampled from unconnected nodes of tor thereby setting stn( 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-base Regularization. Intuitively, a keyword appears on many nodes, 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 c, that indicates the number of nodes containing keyword w; For instance, in G' shown in Fig. [ = 2 and = 2 for keywords a and h, respectively. We propose to enhance the model's keyword feyword_rrquency awareness with regularization that minimizes:
L3
Σ alll(L)))l. WEW
where I denotes an M x M identity matrix, and I, denotes the i-th row of Feeding I, in f can return the representation of keyword ws, 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 minimize:
L = L= + Xgh2 + AsC3.
where Å1, A2 and \a are hyper-parameter By minimizing Eq. X 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 9. given the one-hot encoding of q as X.y, the trained encoder and the learned node embedding Z, we can compute the similarity between the nodes and query with Sq f'(x,) and the top-k answers can be found with the largest scores in Sq. In addition, the space complexity of computing query processing is (dN).
Experiments
In this section, 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.
5.1 Baseline Methods
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 the supplementary materials.
7

---

GraphSAGE [10] is a representative GNN-based graph embedding method. We add an MLP encoder for GraphSAGE address the keyword search problem for GraphSAGE.
BLINK+SAT firstly predicts and completes the missing keywords and edges with state- of-the-art missing-date 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
Cony-PCA is a naive method proposed in Section 4.1
KS-PCA is a simplified variant of our proposed ES-GNN that replaces the MLP encoder and decoder with PCA transformations. Specifically, it leverages U to reconstruct M-dimension
embedding from ha.
5.2 Experimental Setup
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 the graph. Let ng lgl denote the number of words in the query q, we randomly sample 100 queries as the test set for each value of ny ranging from 3 to with step 2.
In addition, in each incomplete graph, the validation set consists of 100 randomly generated queries with ground truth answers. We tune the hyper- parametrrseeterss... 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.
5.3 Performance of Keyword Search
Table 1 shows the comparison results in graphs with Tw adjusted from 0.3 0.7 and n, adjusted from to 9. As shown in the table, KS-GNN and KS-PCA significantly outperforms the baselines, and changing Fw will not affect its performance. Moreover, the performance of KS-GNN better when more query keywords are given. As for the baselines, BLINK +AT 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 pesssag-ppassing 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-basse 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 n, 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.
model are
Table Table2] 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 [ Table 2 shows that the effect of missing edges cannot be reflected for the powerless methods, such as GraphSAGE and BLINK+SAL
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.
8

---

Table I: Method performance by Hits @ 100 (%) in graphs with only missing keywords.
Datasets
0.3
0.5
0.7
B4
3
7
9
3
5
7
9
5
7
GriphSAGE
6.87
5.64
2.95
3.71
5.15
4.74
3.52
2.07
9.42
8.27
6.05
7.54
BLINK+SAT
8.81
7.23
5.65
4.42
9.14
5.97
5.47
4.88
9.82
8.34
8.75
5.49
PCA
10.26
7.73
6.51
5.19
9.31
6.70
6.28
4.82
7.73
6.40
6.47
4.98
CiteSeer
Conv-PCA
8.49
8.43
8.76
7.41
8.92
7.78
11.28
13.58
11.38
9.20
11.44
9.90
KS-PCA
24.91
27.92
33.15
38.35
23.61
25.87
32.84
30.74
20.94
26.18
35.59
33.99
KS-GNN
30.84
37.86
38.07
42.61
31.43
38.79
38.86
42.62
28.69
35,25
35.61
38.64
GraphSAGE
0.49
0.30
0.06
0.03
0.44
0.14
0.00
0.05
0.34
0.35
0.21
0.16
BLINK+SAT
10.21
9.86
10.99
14.87
8.55
6.92
8.63
5.82
1.18
1.15
4.38
3.35
PCA
1.54
0.91
0.55
0.61
1.71
0.72
0.71
0.57
1.66
0.95
0.66
0.55
Video
Conv-PCA
1.81
2.46
1.58
2.38
2.43
1.49
1.66
2.54
2.42
2.37
2.80
3.37
KS-PCA
10.19
12.23
16.15
21.37
11.26
15.62
19.51
23.87
10.66
15.57
19.17
25.36
KS-GNN
21.43
23.36
22.92
26.79
22.54
22.57
30.41
33.41
21.01
16.48
22.01
28.47
GraphSAGE
0.74
0.88
5.11
4.21
4.24
12.49
6.50
6.10
1.45
4.39
6.71
0.09
BLINK+SAT
6.47
8.17
8.12
10.54
6.79
9.59
10.99
11.93
6.44
8.56
11.55
8.15
PCA
1.15
0.68
0.63
0.51
1.01
0.69
0.51
0.44
0.67
0.47
0.44
0.30
Toy
Conv Conv-PCA
21.34
21.99
23.76
25.40
19.17
19.72
20.21
25.22
16.99
21.61
23.95
24.90
KS-PCA
27.23
27.73
31.58
33.79
25.78
28. 94
31.04
32.82
18.35
22.03
25.50
26.25
KS-GNN
28.56
24.85
29.55
34.28
24.65
29.16
31.27
33.25
21.78
27.41
25.55
30.17
GraphSAGE
0.42
0.49
0.36
0.82
0.29
0.43
0.53
0.05
0.07
0.01
0.01
0.00
BLINK+SAT
3.26
6.09
4.01
6.65
3.49
1.66
5.42
3.95
4.25
2.42
3.12
4.24
PCA
3.78
2.57
2.25
2.38
3.06
2.55
2.21
2.15
2.97
2.51
2.02
1.88
DBLP
Conv-PCA PCA
9.00
13.29
16.87
5.93
6.56
7.64
10.62
7.00
10.52
10.03
15.68
KS-PCA
15.28
21.41
25.61
31.64
14.98
20.73
23.21
31.72
12.49
19.49
21.23
28.63
KS-GNN
16.21
24.94
29.55
33.51
16.52
22.73
26.85
30.69
15.57
24.15
27.12
29.06
Table 2: Method performance by Hits @ 100 (%) in graphs with both missing keywords and edges (ra
0.3).
0.3
0.5
0.7
Datasets
5
7
9
3
5
7
3
5
7
GraphSAGE
2.04
3,22
2.99
1.72
3.89
2.95
1.03
1.11
9.62
8.26
7.35
7.23
SLINK+SAT
9.19
8.14
5.68
3.71
8.26
6.79
6.04
8.57
7.88
8.33
7.69
8.30
PCA
10.26
7.73
6.51
5.19
9.31
6.70
6.28
4.82
7.73
6.40
6.47
4.98
CiteSeer
Conv-PCA
9.61
9.37
8.17
7.68
10.82
9.22
11.83
14.33
11.40
10.17
11.91
9.94
KS-PCA
25.27
27.89
31.47
35.71
22.51
24.92
31.65
30.49
20.72
25.60
35.30
32.81
KS-GNN
30.57
37.88
38.15
41.80
26.80
34.70
34.37
36.75
24.47
31.19
35.82
34.96
GraphSAGE
0.09
0.11
0.02
0.00
0.26
0.05
0.00
0.04
1.65
1.65
2.22
1.29
BLINK+SAT
1.67
1.85
2.48
1.44
0.08
0.99
4.96
2.97
2.19
1.77
0.78
1.21
PCA
1.54
0.91
0.55
0.61
1.71
0.72
0.71
0.57
1.66
0.95
0.66
0.55
Video
Conv-PCA
1.05
1.59
0.83
2.01
1.43
0.81
0.87
1.23
1.25
1.25
1.31
1.38
KS-PCA
3.82
4.13
4.88
7.13
3.96
4.52
5.33
6.11
3.64
4.58
5.17
6.55
KS-GNN
8.08
8.34
12.88
11.82
6.84
7.68
4.18
11.12
6.37
10.31
13.92
10.07
GraphSAGE
0.04
0.02
0.01
0.00
0.28
0.00
0.01
0.02
0.02
0.18
0.29
0.23
BLANK+SAT
3.69
3.03
4.85
5.66
2.56
1.34
1.86
5.46
1.76
1.39
4.73
4.45
PCA
1.15
0.68
0.63
0.51
0.69
0.51
0.44
0.67
0.47
0.44
0.30
Toy
Conv-PCA
11.64
10.46
11.23
12.29
9.31
9.00
9.08
11.61
6.74
8.87
8.99
9.56
KS-PCA
13.80
13.03
13.55
15.67
11.35
11.03
11.09
13.02
6.84
8.37
9.50
10.43
KS-GNN
13.82
13.28
14.38
15.22
12.51
12.54
12.68
12.59
9.41
8.99
12.83
11.15
GraphSAGE
0.51
0.20
0.34
0.67
0.25
0.40
0.90
0.40
0.05
0.04
0.02
+SANK
4.78
3.45
6.74
4.58
3.94
3.66
5.05
3.97
2.96
2.75
2.83
7.29
PCA
3.78
2.57
2.25
2.38
3.06
2.55
2.21
2.15
2.97
2.51
2.02
1.88
DBLP
Conv-PC
8.35
11.8
12.51
14.51
5.25
6.77
7.03
9.91
6.46
9.59
9.47
14.33
KS-PCA
15.05
19.99
22.61
28.57
13.68
19.19
21.59
28.96
11.67
17.71
18.38
24.51
KS-GNN
15.91
20.49
25.09
29.04
15.79
19.86
22.15
29.71
12.07
17.18
19.23
24.19

---

5.4 Ablation Study
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 = 0 and Iw = 0.3 on four datasets. For the queries, the number of keywords is set to my 3. Based on Eq. (8. we have three variants which are trained with different learning objectives, denoted by without L1. without L2 and without Las respectively. For instance, the learning objective A2L2 + AgL3 for the variant without L1. The hyper-parameeers 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. C2 and C3 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.
Table 3: Hits @ 100 (%) the ablation study of KS-GNN.
CiteSeer
Video
Toy
DBLP
without L1
28.17
17.82
24.67
14.62
without L2
29.51
18.86
26.39
15.63
without L3
26.28
17.13
27.01
16.05
KS-GNN 30.84
21.43
28.56
16.21
6 Conclusion
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 storage limitation or privacy issues. In this paper, we study the keyword search problem in incomplete graphs and propose 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 real-world datasets reveal that KS-GNN significantly outperforms the state-of-the-an 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.
References
[1] Haixun Wang and Charu C. Aggarwal. A survey of algorithms for keyword search on graph data. In Managing and Mining Graph Data, volume 40 of Advances in Database Systems, pages 249-273. Springer, 2010.
[2] Hao He, Haixun Wang. Jun Yang, and Philip S Yu. Blinks: ranked keyword searches on graphs. In SIGMOD, pages 305-316, 2007.
[3] Wangchao Le, Feifei Li, Anastasios Kementsietsidis, and Songyun Duan. Scalable keyword search on large rdf data. IEEE Transactions on knowledge and data engineering, 26(11):2774- 2788, 2014.
[4] Jieming Shi, Dingming Wu, and Nikos Mamoulis. Top-k relevant semantic place retrieval on spatial rdf data. In SIGMOD, pages 1977-1990, 2016.
[5] Dejian Yang. Senzhang Wang, Chaozhuo Li, Xiaoming Zhang. and Zhoujun Li. From properties to links: Deep network embedding on incomplete graphs. In CIKM, pages 367-376, 2017.
[6] Xu Chen, Siheng Chen, Jiangehao Yao, Huangjie Zheng, Ya Zhang, and Ivor W Tsang. Learning on misiint graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2020.
10

---

[7] Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. In Proc. of NeurIPS, pages 5165-5175, 2018.
[8] Yu Hao, Xin Cao, Yixiang Fang. Xike Xie, and Sibo Wang. Inductive link prediction for nodes having only attribute information. In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI-20, pages 1209-1215, 7 2020.
[9] Han Zhang, Yu Hao, Xin Cao, Yixiang Fang. Won-Yon Yong Shin, and Wei Wang. Relation prediction via graph neural network in heterogeneous information networks with missing type information. In CIKM, 2021.
[10] William L. Hamilton, Rex Ying, and Jure Leskovee. Inductive representation learning on large graphs. In Proc. of NeurIPS, 2017.
[11] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv: 1tt.//000.00.... 10903, 2017.
[12] Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsieh. Cluster-gen: An efficient algorithm for training deep and large graph convolutional networks. In SIGKDD, pages 257-266, 2019.
[13] S. Agrawal, S. Chaudhuri, and G. Das. Dbxplorer: a system for keyword-based search over relational databases. In ICDE, pages 5-16, 2002.
[14] Gaurav Bhalotia, Arvind Hulgeri, Charuta Nakhe, Soumen Chakrabarti, and Shashank Sudar- shan. Keyword searching and browsing in databases using banks. In ICDE, pages 431-440. IEEE, 2002.
[15] Mehdi Kargar and Aijun An. Keyword search in graphs: Finding r-cliques. Proceedings of the VLDB Endowment, 4(10):681 (000)))681622,,. 2011.
[16] Ziyang Liu, Chong Wang, and Yi Chen. Keyword search on temporal graphs. IEEE Trans. Knowl. Data Eng. 29(8):1667-168) 2017.
[17] Ye Yuan, Guoren Wang. Lei Chen, and Haixun Wang. Efficient keyword search on uncertain graph data. IEEE Trans. Knowl. Data Eng., 25(12):27772277, 2013.
[18] Yueji Yang, Divyakant Agrawal, H. V. Jagadish, Anthony K. H. Tung, and Shuang Wu. An efficient parallel keyword search engine on knowledge graphs. In ICDE, pages 338-349. IEEE, 2019.
[19] Shady Elbassuoni and Roi Blanco. Keyword search over RDF graphs. In CIKM, pages 237-242. ACM, 2011.
[20] Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks graphs arXiv preprini 1rXi::1312.6203. 2013.
[21] Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. Advances in neural information processing systems, 29:3844-3852, 2016.
[22] Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In Proc. of ICLR, 2017.
[23] David Shuman, Sunil K Narang. Pascal Frossard, Antonio Ortega, and Pierre Vandergheynst. The emerging field of signal processing on graphs: Extending nigh-dimensional data analysis to networks and other irregular domains. IEEE signal processing magazine, 30(3):83-98, 2013.
[24] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In ICLR, 2018
[25] Thomas N Kipf and Max Welling. Variational graph auto-encoders. NeurIPS Workshop, 2016.
[26] Jiaxuan You, Xiaobai Ma, Daisy Yi Ding, Mykel Kochenderfer, and Jure Leskovec. Handling missing data with graph representation learning. arXiv preprint arXiv:2010.164111 2020.

---

[27] Indro Spinelli, Simone Scardapane, and Aurelio Uncini. Missing data imputation with adversarially-trann graph convolutional networks. Neural Networks, 2292249-260, 2020.
[28] Bhavana Bharat Dalvi, Meghana Kshirsagar, and S Sudarshan. Keyword search on external memory data graphs. Proceedings of the VLDB Endowment, 1(1):1189-122) 2008.
[29] Gang Gou and Rada Chirkova. Efficient algorithms for exact ranked wig--pateern matching over graphs. In Proceedings of the 2008 ACM SIGMOD international conference on Management of datu, pages 581-594, 2008.
[30] Thanh Tran, Haofen Wang, Sebastian Rudolph, and Philipp Cimiano. Top-k exploration of query candidates for efficient keyword search graph-shaped (rdf) data. In 2009 IEEE 25th International Conference on Data Engineering, pages 405-416. IEEE, 2009.
[31] Jan J Gerbrands. On the relationships between svd, klt and pea. Pattern recognition, 14(1- 6):375-381, 1981.
[32] Yoshua Bengio, Aaron Courville, and Pascal Vincent. Representation learning: A review and new perspectives. IEEE transactions on pattern analysis and machine intelligence, 35(8):1798- 1828, 2013.
[33] lan Goodfellow, Yoshua Bengio, and Aaron Courville. Deep Learning. MIT Press, 2016.
[34] Elad Hoffer and Nir Ailon. Deep metric learning using triplet network. In International workshop on similarity-based pattern recognition, pages 84-9.. Springer, 2015.
[35] Florian Schroff, Dmitry Kalenichenko, and James Philbin. Facenet: A unified embedding for face recognition and clustering. Proc. of CVPR, pages 815-823, 2015.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] This work focuses on handling keyword search problem with missing information.
(b) Did you describe the limitations of your work? [Yes] See section 6 This research needs to be extended for larger-scale datasets.
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [N/A]
(b) Did you include complete proofs of all theoretical results? [N/A]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (c.g., data splits, hyperparameters, how they were chosen)? [Yes] See sections starting from section [5.2]
(c) Did you report error bars (e.g.. with respect to the random seed after running experi- ments multiple times)? [Yes] See Appendix E.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Appendix C.I.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] See Appendix B.
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material URL? [No]
12

---

(d) Did you discuss whether and how consent was obtained from people whose data you' re using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "hqUpSJ7czD", "reviewer": "Reviewer_ZPE7", "summary": "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths: \n1. Well-motivated challenging task of keyword search over incomplete graphs.\n2. KS-GNN is technically sound and capable of modeling incompleteness, compared to Conv-OH and Conv-PCA.\n3. Extensive experiments on a large number of settings are provided. \n\nWeaknesses:\n1.The problem formulation is somewhat unclear in the statement and introduction examples. \n2. More baselines or self variants should be compared to better prove the effectiveness.\n\nDetailed comments:\n1. The problem definition of keyword search on incomplete graphs is ambiguous and confusing. The KS-GNN mostly optimizes on node similarity and the inference stage tends to select the top-k most similar results towards the query keyword set. However, the problem itself seems more like a combinatorial one, or say, set optimization, node-set selection with minimal distance measurement. Are the targets here equivalent? \n2. The baseline approach seems much inferior to KS-GNN. It would be great to include some variants of the KS-GNN that delete some of the module or training objectives to confirm the contribution of each component. \n3. Table 2 with missing edges is supposed to be more challenging than the task in Table 1. However, a lot of models perform even better (or comparable) which seems strange. Also,  the claim of “KS-GNN has no significant effect” does not apply to the Toy and Video datasets for correctness. \n4. It is hard to conclude from Figure 4 on the benefit of keyword frequency regularization. That is, it’s better to show the performance scores along with the visualization.\n5. Figure 3: The notations of the figure (especially function f and g) are confusing.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Not applicable.", "review_text": "", "extra_scores": {"ethical_concerns": "Not applicable.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1.5"}, "extra_text": {}}, {"review_id": "fEtPMShwMH1", "reviewer": "Reviewer_dWyG", "summary": "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.\n", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\nOriginality: \n\nThis paper creates a novel task of answering queries in graph where informations are missing. The work is a novel combination of known techniques.\n\nQuality: \n\nScalability/Computational challenges are not discussed. What are we paying for to achieve this better result?\n\nIf we query for a complete graph what will be the performance for KS-GNN? In other words, is KS-GNN equally applicable when the graph is complete?\n\nWhat type of missing information KS-GNN can handle is unclear? Random query generation process don't provide enough knowledge.\n\nAblation studies should be presented in the main paper. What is the effect of r_e and r_w to the performance? Are the numbers will be consistant if the r_e or r_w samples change?\n\nWhy hits@100 is presented at the main paper? Whereas it is more interesting to see the results for hits@10 or hits@50. If the query result is presented in top-100 is it a good result?\n\nA small suggestion 4.1 Naive method is less important whereas more important parts i.e. ablation study (appendix E), algorithm (appendix D) will provide better insights to the end readers.\n\nThe learning objective from equation 8, it was not clear the impact of the three objectives on the learning process. The reader had to dig through appendix and found that, \\mathcal{L}_3 is the key driving factor here. However, which parameter settings were presented at Table:4 at appendix? I was expecting the numbers should match for KS-GNN with the tables from the original paper Table 1 or Table 2. \n\nHow can we use KS-GNN when new keyword information is available? Do we need to retrain the complete model?\n\nClarity: \n\nThe paper was hard to follow. Even when the authors uses the figures, it is not referenced properly. For example - where the figure 4 was referenced in the paper? Also, the message from the figure was not understandable.\n\nSignificance: \n\nThe results are significant but the experimental setting and procedure has a lot of scope to improve on.\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Can not find a section on this on the paper.", "review_text": "", "extra_scores": {"ethical_concerns": "Don't think there are ethical concerns over this work.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}, {"review_id": "X1suAoTYADA", "reviewer": "Reviewer_kP3a", "summary": "The paper proposes a method to run keyword searches over graphs that are incomplete. The proposal is that of encoding the graph into a latent space that allows the reconstruction of the graph and then the subsequent application of graph search mechanisms.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n* The paper is well written\n* Experiments show that the method can effectively solve the problem of searching in graphs when the information is missing about the connection between nodes.\n\nWeaknesses:\n* The motivations are not clearly stated. Keyword search on graphs is usually required for solving XML queries data. Can you better motivate the problem by listing some important applications of keyword search on incomplete graphs?\n* The description of the problem is not clear. In the beginning, you propose to first encode the graph and then use the latent representation to overcome the problem of missing information (Figure 2). Then, in Figure 3, you add some other layers, and the way these components are integrated is written in Eq. (8) which is at the very end of the description and it is confusing.\n* The complexity of the query processing phase is very high (dN) and it might be impractical in a real-world scenario\n* Given the stochastic nature of the missing info problem, I would have appreciated an analysis of the variance of the results varying the seed of edge and keyword sampling. \n\nComments on the content\n* It is not clear in the problem definition (Line 110) why you introduce r_w and r_e given that they are not part of the definition\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Authors should run an analysis to put confidence intervals around results in tables 1 and 2.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper addresses the novel and technically interesting problem of answering queries on graphs with missing information such as edges and nodes. 
The proposed problem is well-motivated and the proposed method based on autoencoders and GNNs, although being a combination of known techniques, sounds reasonable, and is considered as a solid technical contribution, and also  the experimental evaluations are fairly thorough in a variety of settings.
Overall, this paper is expected to be of interest to the NeurIPS community, and worth being accepted.
Decision: Accept (Poster)