Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: Summary: In this study the authors propose INDIGO, a GCN based method for inductive knowledge base completion, i.e. predicting relations between known or unknown constants of a KG. The paper provides a great survey over current related approaches and also proposes a new dataset for this setting. The proposed method basically does label (feature) propagation with a GCN, in which the labels (features) are indicators of the relations and the types of the nodes. To induce the presence of a new triple, the hidden state after label (feature) propagation is used for binary predictions, i.e. a pair of constants (c, d) will predicted to be connected by relation r if their labels (features) contain r and and many other pairs of constants that also are in relation r are highly similar regarding the other labels (features). The experiments on two previously proposed datasets and its own dataset show that the proposed method improves in most classification and ranking metrics over previous approaches, except for the entity ranking metric.
main_review: Originality: None of its elements is new or modified in a novel way, but as far as I am aware it was not applied in this way on knowledge graphs. The work positions itself well in the context of related work. 

Quality: The work seems sound. The claims are supported by experimental results, but no theoretical guarantees on the limits of this approach are given and the weaknesses of the approach are not treated completely transparently. The discussion why this is bad for ranking but works apparently better for classification where the negatives to which the true triple is compared against are semantically less close to the true triple is lacking. The approach looks to me like a high recall low precision method. This aspect is somewhat interesting, if it would have been investigated more closely (theoretically or empirically), i.e. what is the limiting factor, how could it be improved? Was it a training parameter like the number of pseudo-negatives or is this as good as it gets? As the paper is about the inductive scenario it would have been necessary to be explicit in the evaluation about which parts of the model need to be updated when new constants are added and what complexity this incurs. Also, isn’t another limiting factor the number of the constants, i.e. the Adjacency matrix? This should be discussed as well also in contrast to the other approaches. As the evaluation is based on metrics computed against random samples it is unclear how stable these results are.  

Clarity: The authors use a different language than typical Neurips papers and hence it takes more effort than necessary to follow the paper. The core idea of the paper can be summed up pretty briefly and the paper takes a lot of time to explain the idea. However, I did like the introduction and how the paper contrasts itself with related work and the paper is also quite self-sustained due to its verboseness which is also a good attribute.   

Significance: There are some interesting aspects of this work that could inspire follow-ups and it does establish some good results on benchmark datasets and provides another one which is well motivated. 

limitations_and_societal_impact: Some limitations and impact have been discussed.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: Knowlegde graph completion (KGC) has traditionally been attempted in transductive mode: a fixed (incomplete) graph is provided, the algorithm analyzes it, and proposes edges between existing nodes.  The inductive version, where new nodes never seen during training are then presented, and (subject, relation, object) queries have to be scored with unseen subject and/or object, is less studied, and is the subject of this paper.  The paper proposes a new encoding/transformation of the training+test graph, new in the KGC task but not particularly striking as far as graph representation goes; it is a variation of a product graph.  Then it proposes to run a fairly standard GCN on top of the transformed graph.  The output from the GCN is used to predict new edges in the original KG.  Experiments show frequent, sometimes dramatic gains over some recent systems.

The core idea (Defn 2) is to build a new graph from the KG, where each node is a pair of (perhaps identical) entities.  Roughly speaking, each node $(e,e)$ in the new graph, where $e$ is an entity in the original KG is associated with a bit vector over the entity types of the KG.  If $e$ is an instance of type $t$, then the $t$th bit is set.  Also, each node pair $(s,o)$ in the new graph, where $(s,r,o)$ is in the original KG, is associated with a bit vector over the relation types of the KG, with the $r$th bit set.   Two nodes in the new graph are connected by an edge if any of their component entities in the original KG is common.  On this new graph they run a GCN.  The GCN representation of a node is used to infer a softmax over types or relations as appropriate.  This makes the KGC scheme inductive.
main_review: Novelty and importance of problem spec: Yes, this is an important problem where insufficient work exists.

Originality of technique: This general form of graph construction using a Cartesian space of nodes is not new; it has been applied in link prediction, but I have not seen it applied to KGC.

Effectiveness and impact: The numbers presented seem impressive, but I am not familiar with the latest numbers on most of these specific data sets.  Provided one question I raise about the size of the derived graph is satisfactorily answered, the technique seems effective.


Detailed comments:

L11 "external heuristics and ad-hoc scoring functions" --- unclear.

L24 entity + "and relation"

L26 Throughout, "constants" is used in a sense not that common in KG literature. If you wish to use "constants" throughout, define it precisely at this point.

In Figure 1 caption, explain that G, X, P, S are shorthand. Explain what $Col_{1,2}$ mean.  Explanatory text is too far; do this in the caption itself.

One feature of your approach that you can highlight better is the collective nature of inference.  In standard KGC, inference (scoring) for (s,r,o) triples is done one by one.  Your approach allows collective inference of a whole test batch.

L41 is -> are

L52 "randomly initialized" --- why?  Only if there is no usable local info at nodes, which is never the case with KGs.  Nodes have rich aliases, descriptions, attribute names and values.  These have been used to get very good baseline accuracies in BERT-INT, for example.

[BERT-INT] https://www.ijcai.org/Proceedings/2020/0439.pdf

L57 "does not take into account what is the common part of these neighbourhoods"

remove "what is"

Apart from the fixes you cite, also see
https://proceedings.neurips.cc/paper/7763-link-prediction-based-on-graph-neural-networks.pdf and https://arxiv.org/abs/2005.00687 for more pointers.

L67 "one to one correspondence" --- completely unclear until one reads and understands your technique.

Definition 2 must be worked better into your intro --- it's a salient contribution.

L80 unclear what you mean by "pairwise disjoint" here.  Do you mean "mutually exclusive"?  That is never the case with real KGs.

L83 (c,r,d) is strange notation; (s,r,o) = (subject, relation, object) or (h,r,t) = (head, relation, tail) is commonly used.

L84 "the subset" -- which subset?

L106 "Definition 1" -- this is too much of a forward reference.  Besides, it does not define much!

L109 The limitation of GNCs are well documented. Why not use a more advanced member of the GNN family, evolved in recent years?

Definition 2 is the core of the proposal.  Here (or much earlier), you need to clarify one point that may occur to the reader.  What is the number of nodes and edges in the new graph you construct, as functions of the number of entities, types, and relations in the original KG?  E.g., in Figure 1 itself, we see that R-GCN uses a graph with 4 nodes and 5 edges, whereas your representation uses 9 nodes and at least 20 edges.

I scanned Table 1 to look for a direct comparison between the number of nodes in the original KG and the derived graph, as well as the number of edges.  But I could not get a direct idea of the typical blow-up you would suffer.  Particularly in view of your spectacular claims around L348 (and appendix tables 7, 8), you need to explain how you control the potentially explosive growth in the number of nodes and edges.

L186 Section 3.3 Before what the GNN model is, explain WHY you wish to run a GNN over the newly constructed graph, i.e., a brief verbal preview of section 3.4.

L213 "elements" -> "trainable weights"

Table 1/ L229 --- you should really use more descriptive and self-contained captions --- if they run into 5 lines, that's perfectly fine.  Remind what $\mathcal{T}, \mathcal{V}, \mathcal{K}_\text{test}, \Lambda_\text{test}$ mean.  Don't just present the numbers, interpret them and comment on them.  Coded names like v1 \dots v4 and h-1K t-5K etc. must be locally explained.

L307 What is the sensitivity of MRR to the number of negatives you sample per positive?

limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper proposes a novel approach called INDIGO for KG completion in the inductive setting. INDIGO is based on GNNs, and it adopts a distinct way to encode the KG into the input graph of a GNN. In the well-designed input graph, each node represents a pair of constants (i.e., entities), and two nodes are connected only if their pairs share a constant. Meanwhile, each node has an initial feature vector where each element captures a fact involving the pair constants in the KG. After the training of GNNs, the predicted triples can be read out directly based on the output representations from the last layer. The proposed method overcomes the drawbacks of the existing scoring-based approaches that ignore the common part of neighborhoods of entities, and can efficiently make predictions for many triples at one time. Experiments on several inductive KG completion benchmarks demonstrate the effectiveness of the proposed method. 
main_review: **Clarity**:

Generally, I think this paper is clearly written, especially in Section 3 to describe the proposed architecture. However, there is still room for improvement in the organization of the paper. For example, the analyses of the experimental results are somewhat limited, and I think the description of benchmarks and performance metrics seems a bit lengthy. 

**Originality**:

From my perspective, I think the proposed method on how to encode the KG into the input graph of a GNN sounds interesting and inspiring. However, it still lacks some novelty. In the architecture, it just uses a GCN to update the feature vectors and simply adopts a threshold to decode the output. I think more careful designs on these modules will make this work more solid. For example, [1] argues that a sigmoid layer to turn logits into probabilities will provide poor calibration, so the output of the proposed method may also need a well-designed calibration before adopting 0.5 as the threshold. 

**Quality**:

In general, I think this paper is technically sound. But, I still have a few questions and suggestions on experimental results. First, I notice that the authors argue existing benchmarks have some issues. They claim that some benchmarks cannot capture the situation where the triples mentioning both existing and new constants are added to the KG, and the others cannot capture the situation where a KG is also extended with the triples mentioning only unseen constants. By contrast, their proposed benchmark can capture both situations. However, the detailed statistics on the two situations are not listed, and it will be better to provide evaluation results on these two situations respectively. I think this will help the readers know the difficulty of the two situations, as well as the effectiveness of their proposed method and baselines on the two situations. Second, I notice that the proposed benchmark contains type information, and INDIGO can use such information while other baselines seem not to use such type information. So, is it a fair comparison?

**Other questions**:

The authors say that their proposed method can be trained and applied efficiently, and the results also show that INDIGO spends much less time on training. But I think the scale of the input graph in the proposed method is much larger than that in baselines, as each pair of constants may be a node. So the number of nodes in the input graph may reach O(N^2) (N is the number of entities). Due to this issue, I want to know why INDIGO is so efficient compared with other baselines.

[1] Pedro Tabacof, Luca Costabello: Probability Calibration for Knowledge Graph Embedding Models. ICLR 2020
limitations_and_societal_impact: It seems that INDIGO needs to know the candidate set in advance, as it needs to encode the KG and the candidate set together into the input graph of a GNN. Besides, if some changes happen in the candidate set, INDIGO may need retraining. I think these two issues are the limitations of INDIGO.
review_title: null

Meta-review: This paper describes a new knowledge graph completion alg. which can work on novel entities.  The evaluation is thorough and extensive.  There were several points brought up by the reviewers, and most handled well in the response.  

One reviewer thought there should be an additional analysis with a different negative sampling method. The authors respond "Our goal in this paper, however, was to develop a system that performs well when taking into account all relevant metrics rather than a particular one, and which does not exploit unnecessary biases. We believe that our results show that this objective has been achieved." I agree with the authors on this point -- an additional model is not needed

Decision: Accept (Poster)