Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: 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.
main_review: Strengths: 
1. Well-motivated challenging task of keyword search over incomplete graphs.
2. KS-GNN is technically sound and capable of modeling incompleteness, compared to Conv-OH and Conv-PCA.
3. Extensive experiments on a large number of settings are provided. 

Weaknesses:
1.The problem formulation is somewhat unclear in the statement and introduction examples. 
2. More baselines or self variants should be compared to better prove the effectiveness.

Detailed comments:
1. 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? 
2. 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. 
3. 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. 
4. 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.
5. Figure 3: The notations of the figure (especially function f and g) are confusing.
limitations_and_societal_impact: Not applicable.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
main_review: Strengths:
* The paper is well written
* Experiments show that the method can effectively solve the problem of searching in graphs when the information is missing about the connection between nodes.

Weaknesses:
* 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?
* 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.
* The complexity of the query processing phase is very high (dN) and it might be impractical in a real-world scenario
* 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. 

Comments on the content
* 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

limitations_and_societal_impact: Authors should run an analysis to put confidence intervals around results in tables 1 and 2.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: 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.

main_review: 
Originality: 

This paper creates a novel task of answering queries in graph where informations are missing. The work is a novel combination of known techniques.

Quality: 

Scalability/Computational challenges are not discussed. What are we paying for to achieve this better result?

If 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?

What type of missing information KS-GNN can handle is unclear? Random query generation process don't provide enough knowledge.

Ablation 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?

Why 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?

A 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.

The 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. 

How can we use KS-GNN when new keyword information is available? Do we need to retrain the complete model?

Clarity: 

The 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.

Significance: 

The results are significant but the experimental setting and procedure has a lot of scope to improve on.



limitations_and_societal_impact: Can not find a section on this on the paper.
review_title: null

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)