INDIGO: GNN-Based Inductive Knowledge Graph Completion Using Pair-Wise Encoding
Authors: Shuwen Liu
Bernardo Cuenca Grau
Ian Horrocks
Egor V. Kostylev
Venue: NeurIPS 2021 Poster (2021)
Keywords: Knowledge Graph Completion
Graph Neural Networks

Abstract: The aim of knowledge graph (KG) completion is to extend an incomplete KG with missing triples. Popular approaches based on graph embeddings typically work by first representing the KG in a vector space, and then applying a predefined scoring function to the resulting vectors to complete the KG. These approaches work well in transductive settings, where predicted triples involve only constants seen during training; however, they are not applicable in inductive settings, where the KG on which the model was trained is extended with new constants or merged with other KGs. The use of Graph Neural Networks (GNNs) has recently been proposed as a way to overcome these limitations; however, existing approaches do not fully exploit the capabilities of GNNs and still rely on heuristics and ad-hoc scoring functions. In this paper, we propose a novel approach, where the KG is fully encoded into a GNN in a transparent way, and where the predicted triples can be read out directly from the last layer of the GNN without the need for additional components or scoring functions. Our experiments show that our model outperforms state-of-the-art approaches on inductive KG completion benchmarks.

INDIGO: GNN-Based Inductive Knowledge Graph Completion Using Pair-Wise Encoding
Shuwen Liu', Bernardo Cuenca Grau', Jan Horrocks', and Egor V. Kostylev²
'Department of Computer Science, University of Oxford, UK (shuwen.1ik) bernardo. cuenca. grau, ian. horrocks) @cs ox. ac. uk DDepartment Informatics, University of Oslo egork@ifi.ube .uio.no
Abstract
The aim of knowledge graph (KG) completion is to extend an incomplete KG with missing triples. Popular approaches based on graph embeddings typically work by first representing the KG a vector space, and then applying a predefined scoring function to the resulting vectors to complete the KG. These approaches work well in transductive settings, where predicted triples involve only constants seen during training; however, they are not applicable in inductive settings, where the KG on which the model was trained extended with new constants or merged with other KGs. The use of Graph Neural Networks (GNNs) has recently been proposed as a way to overcome these limitations; however, existing approaches do not fully exploit the capabilities of GNNs and still rely heuristics and ad- hoc scoring functions. In this paper, we propose novel approach, where the KG is fully encoded into GNN in transparent way, and where the predicted triples can be read out directly from the last layer of the GNN without the need for additional components scoring functions. Our experiments show that our model outperforms saate-oftthe-an approaches on inductive KG completion benchmarks.
Introduction
Knowledge graphs (KGs) are graph-structured knowledge bases where nodes and edges represent entities of interest and their relations [7]. KGs are commonly represented sets of triples in standard format such as the Resource Description Framework (RDF) [.. Many prominent KGs are highly incomplete, which limits their usefulness in practice; hence KG completion (or link prediction) the problem of extending a KG with missing triples has received significant attention 14].
Most approaches to KG completion, such as TransE 3. DistMult [28], and RotatE 220 are based on graph embedding techniques, which first embed the KG into a vector space (e.g.. by learning a feature vector for each entity) and then generate the predicted triples by applying predefined scoring function to the learnt vectors 14). These models demonstrate good performance transductive settings, where missing triples assumed to mention only constants already occurring in the incomplete KG. A key
limitation of these models, however, is that they are not applicable in inductive settings 5 24 (1],
where missing triples may involve constants unseen during training: this setting is especially relevant in practice since KGs are evolving: they may be extended with triples describing new objects or integrated with external KGs. Consider, for instance, the KG inside the frame in Fig. T where embedding based model has been used to extend the KG with the triple (Plato, lives, Greece); thus, the model seems to have successfully learnt the pattern that students and their teachers tend live in the same country. Assume the graph is now extended with the triples
(Aristotle, student, Plato); (R. Feynman, Re.FFeyynnnttudeent..I J.
(J. U.hheeler, lives, USA),
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Greece
lives
Aristotle
USA
lives
lives
student
lives
Xenophon
lives
Plato
R. Feynman
lives
student
student
student
Socrates
J. W.eheerrr
Figure I: An example for link prediction, where solid and dotted arrows represent known and missing triples, respectively. If we use the graph enclosed within the frame for training, transductive methods will only be able to predict the missing triple (Plato, lives, Greece) inside the frame: in contrast, inductive methods can take the new information (e.g., triple (Aristotle, student, Plato)) into account and predict all three missing triples without re- re-training.
introducing constants for Aristotle, Feynman, Wheeler, and the USA. Since the parameters learnt by embedding- based models are tied to the constants the original KG, such a model cannot generalise the learnt pattern to the constants unseen during training, and fails to complete the KG with triples (Aristorle, lives, Greece) and Feymmann lives, USA). Indeed, for the model become applicable, it would require re-training using also the newly introduced triples.
There are various approaches for inductive KG completion. Rule-based methods 29 good results, but only when the shape of the rules is known in advance. Other methods utilise side information about unseen constants, such attributes [6] and textual descriptions 25 [8]
10
15 show
which is not always available in practice. Recent approaches [5] 17 30 [4, 21] aim to overcome these limitations by exploiting Graph Neural Networks (GNNs), which directly applicable to graphs annotated with feature vectors [16]. GNNs are biased towards graph symmetries (nodes with same neighbourhoods receive the same value) and have built-in inductive capabilities: they are invariant under isomorphisms (i.e., insensitive to the identity of nodes) and can capture general patterns represented logic formulas
27
Conceptually, we see GNN-based KG completion approaches as working in three stages. First, they encode the input KG graph with nodes annotated by feature vectors; second, this graph is fed to GNN; third, the predicted triples are decoded from the output vectors of the GNN. Approaches differ in their encoding of the KG, the kind of GNN they use, and the chosen function for decoding. In the R- R-GCN approach [17], the encoder generates a node with a randomly initialised vector for each entity in the KG and triples are encoded as directed coloured edges (colours correspond to binary relations); their GNN model aggregates separately for each colour, and a colour-specific scoring function is applied to the outermost GNN layer for decoding the prediction. Hamaguchi et al. (5) and Wang et al. (24] developed similar approaches with decoding also based on a scoring function. A drawback of these approaches is that their prediction for triple depends on the standalone neighbourhoods of its constants in the input KG, but does not take into account what is the common part of these neighbourhoods. This drawback has been recently addressed in the GraIL system by Teru et al. [2T]. To predict whether a given triple should be added to the KG, GralL identifies sub-graph of the KG for that triple and encodes in a way similar to R-GCN. Then, Grall. applies a GNN and makes a prediction for this triple using scoring function applied globally to the output vectors of all nodes in its dedicated subgraph. To make predictions for many triples, the approach requires generating a subgraph to each of them, which is a significant bottleneck in practice.
In this paper, we propose novel approach where the KG is encoded into the input graph to graph convolutional network 8) in transparent and direct way, so that the inductive capabilities of the GNN are fully exploited. In contrast to existing approaches, our encoding establishes a one-to-one correspondence between elements of the feature vectors in the innermost and outermost layers of the GNN and triples over the KG's signature, and hence the predicted triples can read out directly from the outermost layer without the need for an external scoring function. As result, our approach has neither the aforementioned drawbacks of scoring- based approaches, nor the bottleneck of Grall., being able to process the entire graph at once; moreover, our approach allows to make predictions for

---

several triples in one run, which may provide significant speed up in practice. We have implemented our approach in a system called INDIGO and compared it with R- R-GCN, GralL, and the system in [S] on the inductive benchmarks developed in [21] and [ as well as on a new benchmark we have developed based on Freebase. Our results show that INDIGO not only outperforms the baselines on these benchmarks, but can also be trained and applied more efficiently. We have finally studied the ability of our system to learn in practice common inference patterns represented using logical rules; our experiments show that our system is able to learn more comprehensive rule sets than the evaluated baselines.
2 Inductive KG Completion
In the context of this paper, a knowledge graph is a set of triples represented a standard format for graph-structured data such as RDF [9]. More formally, signature consists of pairwise disjoint sets of types (i.e., unary predicates), relations (i.e., binary predicates), and constants. knowledge graph (KG) is finite set of triples of the form (c, type, t), where e is a constant and t is type, and triples of the form (c, r, d), where c, d are constants and r is relation The signature Sig (K) of a KG IC is the set of types, relations, and constants used in KC; then, Pred is the subset of Sig (PC consisting of all its types and relations.
The problem of KG completion can be loosely understood as that of extending an incomplete KG IC to its complete version KC* by adding triples over Sig(KC), where triple added if there is sufficient evidence that it holds given the triples in K. We formalise inductive KG completion as the following ML problem. Given arbitrary (but fixed) finite sets Types and Rels of types and relations, respectively, the aim in inductive KG completion is to learn a Boolean completion function s(..-) applicable to each pair of a KG K. with (r)) S. Types L Rels and a triple À with Sig(A) C Sig(K)) such that fIC, A) is true if À is in K Note that, in this formalisation, transductive KG completion is the particular case of inductive completion where the function to be learnt is applicable only to a fixed KG KC-that is, can be seen as f-(()) such that fx( is true for triple À if À belongs to K**
A key limitation of transductive approaches based on graph embeddings is that the completion function learnt for a given KG is not applicable to any other KG (for this one needs to independently learn a new function). In other words, trained instance of such an approach cannot make predictions for triples involving constants unseen during training: for example, a model trained by such a system on a graph in the frame Fig. T cannoot make predictions for any triple with constant outside this frame. In contrast, once trained on a KG K, inductive GNN-based systems, such as Grall. and our system, can make predictions without re-training on every KG and triple over the same types and relations as K, regardless of the constants they use.
3
A GNN-Based Architecture for Inductive KG Completion
3.1 Overview
Our inductive approach relies on the completion function f realised by the following three steps.
1. Encoding, which takes (incomplete) KG K. and set A of candidate triples (of the same signature) as input and returns a node-annotated graph G of the form specified in Definition I
the encoding is pair-wise: nodes in GZ correspond to pairs of constants occurring in IC and A.
2. GNN application, which updates the annotations of the graph nodes; in approach, we use graph convolutional network ( (GCN), which is a GNN variant popular in applications (8].
3. Decoding, which extracts the predictions (KC X) for each À E A from the updated graph output by the GNN; this step is essentially mirroring the encoding.
The details of these steps are given in Sections difference distinguishing our approach from existing inductive systems, such as R-GCN and GralL, lies in the encoding and decoding steps. On the one hand, existing approaches typically encode each constant in K. by a unique node in the graph, where the node's 's feature vector is randomly initialised; in contrast, in our approach each node in the graph encodes a pair of constants, and each element in
and 3.4 respectively. The key conceptual
In the KG literature, constants and types are sometimes collectively referred to as entities and the type relation is treated ordinary relation.
3

---

the initial feature vector of this node directly captures fact in the KG involving these constants. On the other hand, existing approaches typically rely on ad-hoe scoring functions to decode the output of the GNN, whereas in our approach the predicted triples can be read out directly from the feature vectors the final layer of the GNN. Furthermore, our approach, we are able to make predictions for set A of candidate triples at once (for the same KG) rather than for single triple: this facilitates training and testing in many practical scenarios, including those reflected in existing benchmarks.
Next, we define the node-annotated graphs which are used on all three steps of our approach. There are significant differences between KGs, which represent graph- data, and annotated graphs. which are the graphs manipulated by GNNs. Nodes in KG represent constants and types, and edges are labelled with relations between such entities; in contrast, nodes in annotated graphs are annotated with feature vectors, and (undirected and unlabelled) edges between nodes indicate that the values of their vectors influence each other during the execution of the GNN.
Definition 1. For annotation dimension N, a 8-annotated graph is an undirected graph where each node u is associated with feature vector u E F. The i-th element of u is denoted by (u),
In our approach, the amnotation dimension is determined by the relevant sets Rels of relations and Types of types (which are assumed known and fixed before training in the inductive setting); in particular, we take å = [Types] + 2- Rels]. This allows us to associate positions in feature vectors to types, relations, and inverses of relations, which will be instrumental for encoding and decoding. In particular, we fix an (arbitrary) enumeration id assigning a unique natural number from to to each E Types, each E Rels, and the inverse r- of each Rels, and assume that, for every type, relation, or inverse p. element ip) of a node feature vector corresponds to p. Observe that the dimension does not depend on the constants of the input KG; so our approach is indeed inductive: once trained, our model is applicable to any KG over the fixed sets of types and relations, but using arbitrary constants. For the rest of this section, we assume that Rels, Types, id, and are fixed.
3.2 Encoding KGs
Our encoder maps a KG XC and a set A of candidate triples to a 6 d-annotated graph G where each node Wa.d corresponds to a pair of (not necessarily distinct) constants c, connected by triple in I or A. To avoid duplication of information, graph G contains only one of the nodes ued and ua,e when e + dd The choice between Wedd and Udee is immaterial to our approach; for definiteness, we employ the lexicographic order = on the set of constants and add node teedd to G only if c 3 d. As formalised in the following definition, the annotation of ue.d a Boolean feature vector where an element is set to 1 if and only if the corresponding type, relation, or inverse relation holds in I. for and d (e.g., (uc.a): = if and only if = d and (c, type, 1) E I. for type 1 with id = i): if e and d appear in the same triple only in A, then the elements of Ur,d are all 0. As result, our encoding establishes a one-to-one correspondence between elements of the feature vectors and relevant triples over the KG's signature. Finally, two nodes in G are connected by edge if they share constant, which, as we will see, allows GNNs to learn structural patterns in the data (e.g., such as the pattern in Fig. D capturing that teachers live in the same country as their students).
Definition 2. The encoding of KG IC over Types and Rels, and a set A of candidate triples of the same signature as K. is the 8-annotated graph G where
- Ge has a node Weed for every two constants e, d in K. such that either d, c x and KU A contains a triple of the form (c,r, d) or (d, (d,r,,) c) for some relation r; the feature vectors of nodes in G are defined as (ue,e)aa()) = for all (c, type, t) E K. (ue,a)aa(r) = 1 for all (c, r, d) E K. with e 3 d and (ue,)iittr = 1 for all (d, c.) E K with 1 d, all other elements are 0; -G has an edge between different nodes ux and uy pairs X and Y have a constant common.
The graph in Fig. 2(a) depicts the structure of GR for our running example KG inside the frame in Fig. and A ((Plato, lives, Greece)} (where we assume that enumeration id of relations is lexicographic). Nodes represent pairs of constants, and two nodes are connected only if their pairs share constant. Since our example I. has no types and two relations, each feature vector (not

---

(G,G)
(G,X)
(X,X)
Col
(G.P)
(G,S)
(5,5)
X
Coh
Col2
Col2
(P.P)
(P.5)
(S.X)
S
(a)
(b)
Figure 2: Encodings of the KG in the frame in Fig. I with candidate triple (Plato, lives, Greece). (a) Encoding of INDIGO, where the feature vectors of the nodes are omitted and the node names are abbreviated; for example (G, X) denotes MGreece Xenophow (b) Encodings of R-G R-GCN, where the names of constants are abbreviated their first letter, and Col and Col2 are colours.
shown in the figure for clarity) has dimension 4. For instance, the vector of (G, X) 0,, 0]: the first two components are set to O because I. does not contain the triple (Greece, lives, Xenophon) or (Greece, student, Xenophon), the third is since K. contains (Xenophon, lives, Greece). and the last is O because there is no triple (Xenophon, student, Greece) in K. As we will see in Section 3.4 our model predicts the triple (Plato, lives, Greece) to be in the completion KC by examining the feature vector of (G, P) after processing G using a GNN as in Section 3.3 in the encoding, the node (G, P) is justified in G by A and initialised with vector [0, 0, 0, 0J. since Plato and Greece are not connected in I.
is interesting to compare our encoding to that of existing approaches. In particular, Fig. b)) depicts the encoding of R-GCN [17] for the same example. The annotated graph now contains one node per constant, and its directed edges are labelled with colours Col, and Col2, representing relations lives and student; thus, the structure of the annotated graph closely mimics that of the KG. In contrast to our approach, however, the feature vectors associated to each node do not bear any connection with the contents of the KG and are typically initialised randomly. After processing this graph by an appropriate GNN, the R-GCN model applies scoring function to the feature vectors of Plato and Greece the output layer of the GNN to predict the presence of the triple the completion K**
Observe that, differently to R-GCN, the size of the encoding graph in our approach can be larger than that of the original KG. Although the size growth can be quadratic in theory, almost always linear in practice. To this end, let I. be KG and let A be set of candidate triples of the same signature. By construction, encoding CA has - |C] + |A] nodes annotated by d-vectors and up to (m + KC| + [A]) * edges, where m is the number of constants in IC and n is the maximal degree of constant in K. U A (here, the degree of constant is the number of constants d such that e and d appear in the same triple in IC A). In theory, is bounded by m, which is, however, approached only if every two constants are connected by triple in KC A. This hardly happens in practice, since real-world KGs are typically sparse. Hence, we can assume that n is small and the encoding size is linear (assuming that 8, which the number of types and relations, is also small).
next argue that it is
3.3
The GNN Model
Broadly speaking, a GNN is characterised by aggregation and combination functions for each layer, where the functions usually depend on learnable parameters. Every layer of the GNN updates the feature vector of each node in the graph by first aggregating the previous vectors of the neighbouring nodes using the aggregation function, and then combining the result with the node's previous vector using the combination function. The vectors in the final layer form the GNN's output.
In our approach, we use a graph convolutional network (GCN) variant [ with ReLU activation on the hidden layers, which offers a good balance between expressivity and performance (note, however, that the choice of GCNs is not crucial for our approach, and GCNs can be easily replaced with any other suitable GNN variant). The following definition of GCNs relies on representation of each d-annotated graph G with N nodes two matrices Ag E {0, 1) NxN and UG E RR x6 with
5

---

AG = A/ for A/g the adjacency matrix of G and I the identity matrix, and UG the feature matrix of G where each row is the feature vector of a node in G. This representation relies on an ordering of nodes in G, which we assume arbitrarily fixed for each graph. The diagonal identity matrix plays technical role: in essence, it adds an artificial loop to each node in the graph and thus allows for uniform treatment of combination and aggregation in GCNs. In fact, instead of A % AADD where D is the node degree matrix of GCNs use its normalised version A G = D G
Ag that is, the diagonal matrix where the i-th diagonal element is defined as (DG)a = ΣS (A(A))s
(where My is the element of a matrix M in row and column j).
Definition A graph convolutional network (GCN) S1 with L N layers and dimension 6 E N is characterised by (learnable) weight matrices We R and bias vectors by E 12 for all layers& & E {L....,L) ,,,, where each de N is the dimension of layer i such that do Pg (the number I. of layers and the dimensions dg of the hidden layers are eyper-parameters of the model). For an input 8 5-annotated graph with N nodes given as matrices Ag and Uc. R updates, on each layer 8 E (1....,L) L}, its hidden state matrix U2 E RR
Nxé using the rule
U. oz A U--1 We+ be),
where = UGa and the non-linear activation function ae is ReLU for each E < L and the logistic sigmoid function for = L, which (in both cases) is applied to matrices element-wise. Then, R(G) is the 8-annotated graph with the same nodes and edges G, where the feature vector of each node is the row in UL corresponding to u.
Observe that the all the elements of GCN, including all trainable and non-trainable parameters. do not depend on the number of nodes in the graph, and so each (trained) GCN is applicable to graphs of arbitrary size. Also, the activations are justified by practice: ReLU on hidden layers is computationally efficient and prevents the vanishing gradient problem, while sigmoid on the final layer guarantees values be (0, 1), which is convenient for computing the loss.
3.4 Decoding the GNN Output
The result R(G of a GCN M applied the encoding GA of KC and a candidate set A can be decoded into a set of triples over the same signature by essentially inverting the encoder. Note, however, that features in ())))
not Boolean; so, to decide if the decoded graph contains triple, check if the corresponding feature in ((G)) is above threshold 9, which take 0.5 in our experiments.
Definition 4. Given threshold value 0 R. the decoding of 8-annotated graph G is the set Kdec (G) of the following triples, for c, d constants, t a type, and r a relation:
(c, type, t) such that (dt)) 2 0,
(c,r, d) such that (ue,ahi(r)) 2 0 and = d, rd),,) such that (De,))d((->> 2 0 and c 3 d.
Overall, a triple in a candidate set A for KG K. is predicted by a GCN M. to be in the completion K if X E (9t )) Note, however, that in training and evaluation we sometimes need not just a Boolean prediction for a candidate triple, but a confidence in this prediction that is, a numeric value from (0, 1); for this, we directly take the corresponding component of ue,d in the final layer.
3.5 Capturing Logical Rules
In addition to using standard benchmarks, we will also compare the inductive capabilities of com- pletion approaches in terms of their ability to capture common inference patterns represented in Datalog M well-known logic-based rule language in knowledge representation and databases.
(Datalog) rule is function-frer first-order logic sentence of the form
Vx. Bi...., B, - H,
where all B, and H are atoms over predicates in Types U Rels using variables in x as terms, such that each variable in H is mentioned in one of B;; in our context, it is convenient to see atoms as triples as in a KG where variables are used instead of constants. Each assignment a of constants to variables of rule of form I maps the atoms Bi...., .., B, into a KG KV;; in the same way, maps H to

---

Proposition 1. Let r be a rule of form (.. lei C' be set of |x| constants, and let E be the set of all f captures funnciono if and Table Benchmarks statistics, where (7). [V] [Krestl, and | are the sizes of the corresponding training set, validation set, incomplete test KG, and positive test triple set, respectively.
GralL-BMa FB15K-233 237 v2
GralL-BAe BMM
NELL-995
GralL-BM WNISRR
v3
v1
v2
v3
v1
v2
v3
v4
IT
4,245
9,739
17,986
27,203
4,687
8,219
16,393
7,546
5,410
15,262
25,901
7,940
y
1,166
2,194
3.352
414
922
1,851
876
630
1,838
3,097
934
Rust
1,993
4.145
7,406
11,714
833
4,586
8,048
7,073
1,618
4,011
6,327
12,334
A
205
478
865
1,424
100
476
809
731
188
441
605
1,429
Hamaguchi -MM
INDIGO-
h-1k
h-3K
h-5k
t-IK
t-3K
t-5K
b-1k
b-3K
b-5K
BM
T
108,197
99,963
92,309
96,968
78,763
67,774
93,364
71,097
57,601
121,601
M
4,613
4,184
3,845
3,999
3,122
2,601
3,799
2,759
2,166
14,121
Crast
4,352
12,376
19,625
15,277
31,770
40,584
18,638
38,285
48,425
250,195
Aesz
994
2,969
4,919
986
2,880
4,603
960
2,708
4,196
14,904
triple t.. A completion function (or a GNN-based model realising this function) captures r if, for every assignment of constants x, the model predicts triple 1 when applied the KG KCç.
In general, verifying whether a completion function captures a rule requires checking an infinite number of assignments. We can, however, restrict ourselves to small finite number and rely the following proposition (proven in the appendix) when comparing, in Section 4.5 the ability of different approaches capture rules in practice, provided the completion function f realised by system under consideration is constant-agnostic that is, such that f fXC, A) = f f(e(CC, e(A)) for every KG K, candidate triple X, and renaming @ of constants. As far as could check, all the systems considered this paper realise constant- annssttt completion functions.
assignments of constants from to x. constant-age -agiosti- completion function only if fIC; t{) is true for each E E.
Evaluation
We have implemented our approach using Python and PyTorch v1.4.0 in system called INDIGO. We used R-GCN (17) GralL (21), and the system by Hamaguchi et al. (5) baselines. We also tried to include the system of Wang et al. [24], but we found that the system crashes during testing. All experiments were performed
Intel(R) Xeon(R) machine with 8 cores and 2.6 GHz CPU equipped with 540 GB of RAM running Fedora 33 (x86_64).
4.1 Benchmarks
We exploit number of benchmarks proposed by Teru al. (11 and Hamaguchi et al. (5) for inductive KG completion. The benchmarks by Teru et al., 12 in total, are based on transductive benchmarks FB15K-237 (22) NELL-995 (26). and WNISRR 44, and have four versions for each of these transductive benchmarks; we will call them using the pattern GralL-BM XXX.vi where XXX is the base and the number of the version (e.g., GralL-BM/ NELL-995.v.
the third version of the benchmark based on NELL-995). Similarly, the benchmarks by Hamaguchi et al., 9 in total, are all based on transductive benchmark IordNetl I [19], and we call them Hamaguchi-Bin -inguuchiBMMM BM / X-iK, where X is one of h, b and i = 1,3, 5 (these parameters specify how the benchmark was constructed, but the exact details are not essential for this paper).
Each of these benchmarks provides the following:
disjoint sets T and V triples with Sig(V) C Sig(T) for training and validation;
incomplete KG Krest and set t of test triples with Sig(Att)) S Sig(Krest) that are to hold in the completion of Krest for testing.
7

---

These benchmarks implicitly assume that all provided triples represent true facts. In contrast, all other triples over the relevant signature represent facts that are unknown, but assumed to be psendo- negative- that is, are false with equal probability. This relatively weak assumption is due to the fundamental incompleteness and open-world nature of existing KGs, which make difficult to discern the truth status of triple not mentioned in the KG when designing a benchmark. The equal probability ensures that no system has an advantage when evaluated on these benchmarks under the assumption that all -seudo-negative triples are truly negative. Furthermore, to capture the inductive setting, triples in all sets use the same types and relations, but the test sets contain constants that are not mentioned in the training and validation sets.
These existing benchmarks are, however, limited in that they capture the KG evolution scenario in Fig. only partially. On the one hand, in benchmarks GraIL-BM the training and test sets mention completely disjoint sets of constants, thus not capturing the situation where triples mentioning both existing and new constants are added to the KG; on the other hand, in benchmarks Hamaguchi-Bi each triple in the testing set always uses both a constant mentioned in the training set and an unseen constant, thus not capturing the situation where KG is also extended with triples mentioning only unseen constants. To address this limitation, we have designed a new benchmark, called INDIGO- BM, which is based on FB15K- 15K-237 and has the same structure and assumptions benchmarks, but where the use of unseen constants in the test sets is not restricted in any specific way. Additionally, in contrast to existing benchmarks, which contain no type information, our benchmark comes equipped with type triples. Further details of the construction are given in the appendix.
the existing
The statistics of all our 22 benchmarks are summarised in Table
4.2 Performance Metrics
We evaluate the systems' performance using standard classification metries (e.g., accuracy and Fl F1-score) and ranking metrics (e.g.. Hits@k), which are computed based on the systems' outcomes on sets P and N of positive and negative examples. For benchmark with incomplete KG Krest and a set A of test triples, we take P as the set of all pairs (Krest, A) with À E A for all metries; in turn, we obtain N by sampling from the set N of all pairs (Krest, A) with the pseudo-negative triples & Krest U A and Sig(A) S Sigg(Kest) using different sampling methods for classification and ranking-based metrics as described below. Note that sampling is necessary because N is usually very large, and so using all its triples is infeasible. To mitigate the effects of possible fluctuations caused by sampling, we evaluate each system on given benchmark over 10 runs with independently sampled sets of negative examples, and report the average and variance for each metric.
For classification-based metrics, we construct N by randomly sampling, with equal probability, one element of N* for each positive example in P. This method ensures that systems cannot gain advantage by adopting a particular sampling strategy for negative examples during training [12]. Classification-aast based metries for KG completion system evaluated on P and N are then computed in the standard way based on the numbers ip. In, f'p f of true positives, true negatives, false positives, and false negatives. In our experiments, we use precision lp/ (Ip + fy), recall lp/(Ip + f'), and accuracy (lp + Ln)/(Ip + In + fp + fn). Besides this, we use Fl-score and the area under the precision-recall curve (AUC), which are defined as usual from precision and recall for different thresholds (computed using ceiidnnee-bsed predictions).
For monking-basede metrics, construct N No U N, U Na by randomly "corrupting" positive examples. In particular, for each positive example (Krest: (c. r, d)) in P. set N: contains 50 randomly sampled negative examples in N of the form (Krest, (d', r. d)); sets N, and Na are constructed analogously by corrupting r and and taking all and 50 samples, respectively (note that the number of candidates for N, is bounded by the number of relations in Sig(Kreat) Our ranking-based metrics for KG completion system evaluated on P and N are then computed as follows. For each À E A and x E {c. r, d), let Ronk, (A) be the position of (Krest, X) in the decreasing-orderes system's confidence predictions for all the examples in P U N₂. Then, we use entity and relation hit metrics e-Hits@k = (Hits, @k + Hitsa@k)// /2 and H- = Hits, @kk for l = 1,3, 10, where, for each x. Hits, @k = m/lAtes for m the number of À E A such that Rank, (A) S k. We also use the entity and relation mean reciprocal ranks eMRR (MRR. + MRRa)/2 and r-MRR MRR, where, for each MRR, h/ ht//Atssl for h the sum of 1/ Rankk (A) for all X At
list of the
8

---

Table 2: Main metric results the benchmarks in %, where R, G. H, and stand for R-GCN, Grall., the system of Hamaguchi et al., and INDIGO, respectively.
Bench-
Accuracy
AUC
c-Hits@33
r-Hits@3
mark
R
G
H
R
G
H
1
G
H
FB15K-237
v1
51.0
69.0
84.3
51.0
78.6
93.4
16.1
45.1
53.1
V2
51.3
80.0
89.3
50.5
90.0
96.3
18.3
68.5
36.2
3.4
0.4
67.6
v3
54.9
81.0
89.0
50.5
93.1
96.6
14.1
71.2
33.9
3,5
6.6
66.5
v4
52.1
79.3
87.8
52.6
89.5
95.8
16.1
61.8
37.1
3.3
3.0
66.3
Grall BBM
v1
63.7
97.3
85.6
74.5
98.8
94.5
7.5
51.0
39.5
26.0
0.0
80.0
NELL-995
v2
52.0
68.5
84.1
50.4
89.7
92.5
12.2
76.5
44.2
0.8
7.4
56.9
v3
52.3
74.3
89.7
95.1
15.5
2.5
64.4
v4
53.6
49.7
85.2
51.0
65.8
92.9
9.3
56.0
52.3
3.0
0.5
45.7
v1
50.2
88.7
85.7
49.0
91.2
20.1
82.7
12.5
2.1
98.4
WNIBRR
52.7
81.2
85.8
49.8
92.7
92.5
18.1
81.5
18.8
11.0
10.7
97.3
33
52.2
75.7
84.3
53.1
82.8
92.4
16.9
55.5
33.1
24.5
17.5
91.9
v4
86.4 48.4
85.4
50.2
94.4
94.7
8.8
76.3
13.5
8.1
22.6
96.1
h-1k
43.0
49.3
83.6
75.3
43.0
51.5
77.7
87.4
31.6
13.8
55.6
32.9
31.4
29.6
47.1
80.0
h-3K
44.1
50.2
79.0
80.8
43.0
55.6
72.4
91.2
29.7
17.7
48.1
35.3
27.8
29.1
41.6
83.8
Hamaguchi BM
b-5k
46.5
50.0
79.7
83.3
56.8
73.1
93.4
23.9
21.0
49.7
33.4
31.3
26.1
38.5
86.2
t-lK
49.8
53.5
77.1
81.8
48.7
58.8
71.4
90.3
17.1
23.9
42.9
31.0
27.6
31.7
43.3
85.4
t-3K
42.5
53.1
75.3
85.8
41.4
61.7
69.2
94.3
24.9
19.5
31.6
33.9
30.3
27.9
35.3
88.0
L-5K
53.4 40.8
74.0
87.0
39.2
62.0
67.7
95.3
21.3
26.7
31.6
36.1
25.4
25.5
37.4
88.3
b-1k
22.4
54.0
85.0
87.0
33.4
59.2
79.2
95.4
62.5
26.5
46.7
43.2
19.8
32.1
38.5
93.8
b-3K
27.3
53.8
79.3
86.8
35.4
61.1
72.1
95.7
36.0
22.3
37.1
37.5
20.2
28.6
41.5
90.1
b-5K
28.3
52.6
75.8
88.8
35.1
58.8
68.4
96.8
24.3
26.3
30.6
39.1
22.1
27.2
34.0
92.0
INDIGO-BM
73.9
86.2
94.4
89.5
94.2
99.0
36.1
73.6
53.5
32.4
4.9
77.0
4.3 Training
Our INDIGO system is trained as a demoising autoencoder 23 The training set T of benchmark first randomly split, with ratio 9:1, into an incomplete KG Krrain and set A of triples assumed to hold in the completion of Krrain- Then, the model is trained on positive examples (Kirain: A) for each À E A and negative examples (Kerain: A) for X sampled from the set of triples not in T using the strategy described next. For each triple (c, r. d) A with * type we sampled (with equal probability) the following triples from N three triples of the form (c, f", d) where r' is disjoint from r role in Thath is, such that T has no triples (c', d') and (c',r',
(c, rr d'),, r is functional in T-that is, T has no triples (c',,,d] r', d')); three triples of the form (c,r,dz) with dj & dz; and three triples of the form (c', d), if is inverse-functional in T-that is, has triples (c1, ru,r,,"), d'), (cz, r, d') with * c2. For each triple (c, type, 1) E At we similarly sampled from N three triples of the form (c, type, (') where disjoint from type T, which defined analogously to disjoint roles.
As result, we generate up negative training examples for each positive example.
We employed the standard cross-entrows loss function and trained for 3,000 epochs using Adam optimisation with L2 penalty 5e-8. We set as parammeareesers the number of layers in the GCN (2, 3, or 4), the dimension of vectors in the hidden layers (32, 64, or 128) and the learning rate (0.01 or 0.001) and cross-validated them each of the benchmarks using the validation sets to obtain most favourable (for all benchmarks) setting of layers, vector dimension of 64, and learning rate 0.001.
Our baseline systems are trained similarly as autoencoders. We trained them using their (publicly available) code and the settings reported the papers without modifications, including their negative sampling strategies for training, the values of hyper-parameters, and the number of training epochs.

---

Table 3: Results capturing high-confidence rules, where each entry indicates both the number of the high-confidence rules of the benchmark represented by the pattern that are captured by the model and the percentage of the total number of the represented rules.
GralL-BMM NELL-995.v3
INDIGO-BM
Rule pattern
R-GCN
Grall. INDIGO
R-GCN
GraiL
INDIGO
(,,_r,)) [,,_8, y)
(9%)
3 (13%)
3 (13%)
(2, [p) + [r_,ype___) u)
89 (20%)
207 (46%)
(a, _x))
+ (V,_r,
0
(80%)
(33%)
14 (58%)
(x, _r 8) [8))
+ [t, 2)
0 (12%) %)
2 (12%)
95 (14%)
130 (19%)
150 (22%)
(z, w): (2,, 5.8)
> (.)
0
0
42 (49%)
19 (7%)
19 (7%)
116 (41 %
(a.type: (ar.ype, u) (2.,ype, v)
5281 (20%)
timeout
12288 (47%)
4.4 Evaluation Results
The results for several indicative metrics (accuracy, AUC, e-Hits @,, and r-Hits@3)) of the metric-base evaluation of the systems the benchmarks summarised in Table (the system by Hamaguchi et al. is not applicable to GralL-BM and INDIGO-BAN due to its limited inductive capabilities); results for other metrics given in the appendix. As we can see, INDIGO consistently outperforms, often by a significant margin, the baselines on almost all metrics. A notable exception is Lanking-based entity metrics e- e-Hits@k and e-MRR, where INDIGO is often worse than the baselines. This can be explained by the fact that the baselines use entity corruption in negative sampling for training, which can be seen a bias towards these metrics, while our sampling strategy in training is not prejudiced to any metric. In addition to achieving better results, our system is also significantly faster to train. For instance, training on Hamaguchi-BMin BM/b-5kk dataset took more than 0.5 hours for R-GCN, more than 4.5 hours for Grall., 0.9 hours for the system of Hamaguchi et al., and 0.37 hours for INDIGO in the reported configurations. Detailed time statistics for training and testing is given in the appendix.
4.5 Capturing Logical Rules
We also studied the systems' ability learn rules by means of capturing, discussed in Section 3.5 In particular, we considered several commonly used rule patterns, which are specified in the first column of Table 3 Each pattern represents all rules obtained by appropriately substituting its templates aa by types and relations. We took experiments, and considered INDIGO, GraIL and R-GCN trained for these benchmarks. For each benchmark with an incomplete KG Krest and a set Arstt of test triples, and for each rule pattern we proceeded as follows. We first generated all rules represented by the pattern over the types and relations in Sig(Krest) We then identified the rules with confidence at least 0.7, where the confidence of rule in Krest and A is n/m m for m the number of assignments a such that Ki C Keest and n the number of such a that also satisfy to E Krest U A Finally, for each model we computed, using Proposition T the proportion of captured high-confidence rules.
v3 and INDIGO-BM benchmarks for
Our results are summarised in Table 3 As we can see, INDIGO was consistently able to capture the highest number of high-confidence rules for each of the patterns. This suggests that our system is able to inductively generalise its predictions more effectively than the baselines.
5 Conclusion and Future Work
In this paper we have proposed a novel GNN-based approach to inductive KG completion which significantly outperforms state-of-the-ar approaches. The key novelty of our approach that encodes KGs using a one-to-one correspondence between triples in the KG and elements of nodes" feature vectors in the graphs processed by the GNN. A current limitation of our approach is that all predicted triples involve only the relations and types mentioned in the original KG; there has been recent work on methods that are able to complete the KG with triples over unseen relations and types [13], and it would be interesting to see if our techniques can be extended to this setting. For future work, we are also planning to explore the potential applications of our approach in real-world settings (such as KG-enhanced recommendation systems) in collaboration with our industrial partner.
10

---

Acknowledgments and Disclosure of Funding
This work was supported by the EPSRC projects OASIS (EP/S032347/I), UK FIRES (EP/S019111/1), the SIRIUS Centre for Scalable Data Access, and Samsung Research UK.
References
[1] Serge Abiteboul, Richard Hull, and Victor Vianu, Foundations of Databases. Addison- Wesley, 1995.
[2] Pablo Barceló, Egor V. Kostylev, Mikaël Monet, Jorge Pérez, Juan L. Reutter, and Juan Pablo Silva. The logical expressiveness graph neural networks. ICLR, 2020.
[3] Antoine Bordes, Nicolas Usunier, Alberto Garcia-Duran Jason Weston, and Oksana Yakhnenko. Translating embeddings for modeling multi-relational data. In NIPS, pages 2787-2795, 2013.
[4] Tim Dettmers, Pasquale Minervini, Pontus Stenetorp, and Sebastian Riedel. Convolutional 21) knowledge graph embeddings. In AAAI, 2018
[5] Takuo Hamaguchi, Hidekazu Oiwa, Masashi Shimbo, and Yuji Matsumoto. Knowledge transfer for outtof--nooledge-bbl entities: A graph neural network approach. In IJCAI, pages 1802- 1808, 2017.
[6] Yu Hao, Xin Cao, Yixiang Fang, Xike Xie, and Sibo Wang. Inductive link prediction for nodes having only attribute information. In IJCAI, pages 1209-1215, 2020.
[7] Aidan Hogan, Eva Blomqvist, Michael Cochez, Claudia d' A'mato, Gerard de Melo, Claudio Gutiérrez, José Emilio Labra Gayo, Sabrina Kirrane, Sehastian Neumaier, Axel Polleres, Roberto Navigli, Axel-Cyrille Ngonga Ngomo, Sabbir M. Rashid, Anisa Rula, Lukas Schmelzeisen, Juan Sequeda, Steffen Staab, and Antoine Zimmermann. Knowledge graphs CoRR, abs/2003.02320,, 2020.
[8] Thomas N. Kipf and Max Welling, Semi-supervised classification with graph convolutional networks. In ICLR, 2017.
[9] Frank Manola and Eric Miller. RDF Primer. W3C Recommendation, 10 February 2004.
[10] Christian Meilicke, Manuel Fink, Yanjic Wang. Daniel Ruffinelli, Rainer Gemulla, and Heiner Stuckenschmidt.
evaluation of rule-and embedding- based systems for knowledge graph completion. In ISWC, pages 3-20, 2018
[11] C. Morris, M. Ritzert, M. Fey, W/ I.. Hamilton, J. E. Lenssen, G. Rattan, and M. Grohe. Weisfeiler and Leman go neural: Higher-order graph neural networks. AAAI, pages 4602- 4609, 2019.
[12] Pouya Pezeshkpour, Yifan Tian, and Sameer Singh. Revisiting evaluation knowledge base completion models. In AKBC, 2020.
[13] Pengda Qin, Xin Wang, Wenhu Chen, Chunyun Zhang, Weiran Xu, and William Yang Wang. Generative adversarial zero-shot relational learning for knowledge graphs. In AAAI, pages 8673-8680, 2020.
[14] Andrea Rossi, Donatella Firmani, Antonio Matinata, Paolo Merialdo, and Denilson Bar- bosa. Knowledge graph embedding for link prediction: A comparative analysis. CoRR, abs/2002.00819 2020.
[15] Ali Sadeghian, Mohammadreza Armandpour, Patrick Ding, and Daisy Zhe Wang. Drum: End-to-end differentiable rule mining on knowledge graphs. In NIPS, pages 15347-15357, 2019.
[16] Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Trans. Neural Networks, 20(1):61-80 2009.

---

[17] Michael Schlichtkrull, Thomas N. Kipf. Peter Bloem, Rianne Van Den Berg, Ivan Titov, and Max Welling. Modeling relational data with graph convolutional networks. ESWC. 2018.
[18] Baoxu Shi and Tim Weninger. Open-world knowledge graph completion. AAAI, pages 1957-1964, 2018.
[19] Richard Socher, Danqi Chen, Christopher D. Manning, and Andrew Y. Ng. Reasoning with neural tensor networks for knowledge base completion. In NeurlPS, pages 2244934, 2013.
[20] Zhiqing Sun, Zong Deng, Jian- Nie, and Jian Tang. Rotate: Knowledge graph embed- ding by relational rotation in complex space. In ICLR, 2019.
[21] Komal Teru, Etienne Denis, and Will Hamilton. Inductive relation prediction by subgraph reasoning. In ICML, pages 9448-9457, 2020.
[22] Kristina Toutanova and Danqi Chen. Observed versus latent features for knowledge base and text inference. In CVSC, pages 57-66, 2015.
[23] Pascal Vincent, Hugo Larochelle, Isabelle Lajoie, Yoshua Bengio, Pierre-Antoine Manzagol, and Léon Bottou. Stacked denoising autoencoders: Learning useful representations in deep network with a local denoising criterion. J. of Machine Learning Res., 11 (112), 2010.
[24] Peifeng Wang, Jialong Han, Chenliang Li, and Rong Pan. Logic attention based neighborhood aggregation for inductive knowledge graph embedding. In AAAI, pages 7152-7159, 2019.
[25] Ruobing Xie, Zhiyuan Liu, Jia Jia, Huanbo Luan, and Maosong Sun. Representation learning of knowledge graphs with entity descriptions. In AAAI, pages 2659-2665, 2016.
[26] Wenhan Xiong, Thien Hoang, and William Yang Wang- DeepPath: A reinforcement learning method for knowledge graph reasoning. In EMNLP, pages 564-573, 2017.
[27] K. Xu, W. Hu, Leskovec, and Jegelka. How powerful are graph neural networks? In ICLR, 2019.
[28] Bishan Yang, Wen-tau Yih, Xiaodong He, Jianfeng Gao, and Li Deng. Embedding entities and relations for learning and inference in knowledge bases. arXiv preprint arXiv:1412.6575, 2014.
[29] Fan Yang, Zhilin Yang, and William W Cohen. Differentiable learning of logical rules for knowledge base reasoning. NIPS, pages 2319-2328, 2017.
[30] Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. NeurlPS, pages 5171-5181, 2018.
12


Reviews:
[{"review_id": "in0MFjoPg7Q", "reviewer": "Reviewer_WdL8", "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. ", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "**Clarity**:\n\nGenerally, 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. \n\n**Originality**:\n\nFrom 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. \n\n**Quality**:\n\nIn 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?\n\n**Other questions**:\n\nThe 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.\n\n[1] Pedro Tabacof, Luca Costabello: Probability Calibration for Knowledge Graph Embedding Models. ICLR 2020", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "dCdnRx0d4v", "reviewer": "Reviewer_CYvG", "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.\n\nThe 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.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "Novelty and importance of problem spec: Yes, this is an important problem where insufficient work exists.\n\nOriginality 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.\n\nEffectiveness 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.\n\n\nDetailed comments:\n\nL11 \"external heuristics and ad-hoc scoring functions\" --- unclear.\n\nL24 entity + \"and relation\"\n\nL26 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.\n\nIn 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.\n\nOne 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.\n\nL41 is -> are\n\nL52 \"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.\n\n[BERT-INT] https://www.ijcai.org/Proceedings/2020/0439.pdf\n\nL57 \"does not take into account what is the common part of these neighbourhoods\"\n\nremove \"what is\"\n\nApart from the fixes you cite, also see\nhttps://proceedings.neurips.cc/paper/7763-link-prediction-based-on-graph-neural-networks.pdf and https://arxiv.org/abs/2005.00687 for more pointers.\n\nL67 \"one to one correspondence\" --- completely unclear until one reads and understands your technique.\n\nDefinition 2 must be worked better into your intro --- it's a salient contribution.\n\nL80 unclear what you mean by \"pairwise disjoint\" here.  Do you mean \"mutually exclusive\"?  That is never the case with real KGs.\n\nL83 (c,r,d) is strange notation; (s,r,o) = (subject, relation, object) or (h,r,t) = (head, relation, tail) is commonly used.\n\nL84 \"the subset\" -- which subset?\n\nL106 \"Definition 1\" -- this is too much of a forward reference.  Besides, it does not define much!\n\nL109 The limitation of GNCs are well documented. Why not use a more advanced member of the GNN family, evolved in recent years?\n\nDefinition 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.\n\nI 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.\n\nL186 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.\n\nL213 \"elements\" -> \"trainable weights\"\n\nTable 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.\n\nL307 What is the sensitivity of MRR to the number of negatives you sample per positive?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4 hours"}, "extra_text": {}}, {"review_id": "MgqiKv-Mpxi", "reviewer": "Reviewer_e3QF", "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "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. \n\nQuality: 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.  \n\nClarity: 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.   \n\nSignificance: 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. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Some limitations and impact have been discussed.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

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)