INDIGO: GNN-Based Inductive Knowledge Graph Completion Using Pair-Wise Encoding
Year: 2021

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

heading: 1 Introduction
text: Knowledge graphs (KGs) are graph-structured knowledge bases where nodes and edges represent entities of interest and their relations [7]. KGs are commonly represented as sets of triples in a standard format such as the Resource Description Framework (RDF) [9]. 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 [20], 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 a predefined scoring function to the learnt vectors [14]. These models demonstrate good performance in transductive settings, where missing triples are 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, 21], 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. 1, where an 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 to live in the same country. Assume the graph is now extended with the triples
(Aristotle, student,Plato), (R.Feynman, student, J.Wheeler), (J.Wheeler, lives,USA),
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
introducing constants for Aristotle, Feynman, Wheeler, and the USA. Since the parameters learnt by embedding-based models are tied to the constants in 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 (Aristotle, lives,Greece) and (R.Feynman, lives,USA). Indeed, for the model to 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, 10, 15] show good results, but only when the shape of the rules is known in advance. Other methods utilise side information about unseen constants, such as attributes [6] and textual descriptions [25, 18], which is not always available in practice. Recent approaches [5, 17, 30, 24, 21] aim to overcome these limitations by exploiting Graph Neural Networks (GNNs), which are 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 as logic formulas [2, 11, 27].
Conceptually, we see GNN-based KG completion approaches as working in three stages. First, they encode the input KG as a graph with nodes annotated by feature vectors; second, this graph is fed to a 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-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 a 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. [21]. To predict whether a given triple should be added to the KG, GraIL identifies a sub-graph of the KG for that triple and encodes it in a way similar to R-GCN. Then, GraIL applies a GNN and makes a prediction for this triple using a 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 a novel approach where the KG is encoded into the input graph to a graph convolutional network [8]) in a 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 be read out directly from the outermost layer without the need for an external scoring function. As a result, our approach has neither the aforementioned drawbacks of scoring-based approaches, nor the bottleneck of GraIL, 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-GCN, GraIL and the system in [5] on the inductive benchmarks developed in [21] and [5], 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.

heading: 2 Inductive KG Completion
text: In the context of this paper, a knowledge graph is a set of triples represented in a standard format for graph-structured data such as RDF [9]. More formally, a signature consists of pairwise disjoint sets of types (i.e., unary predicates), relations (i.e., binary predicates), and constants. A knowledge graph (KG) is a finite set of triples of the form (c, type, t), where c is a constant and t is a type, and triples of the form (c, r, d), where c, d are constants and r is a relation.1 The signature Sig(K) of a KG K is the set of types, relations, and constants used in K; then, Pred(K) is the subset of Sig(K) consisting of all its types and relations.
The problem of KG completion can be loosely understood as that of extending an incomplete KG K to its complete version K∗ by adding triples over Sig(K), where a triple is 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 f(·, ·) applicable to each pair of a KG K with Pred(K) ⊆ Types ∪ Rels and a triple λ with Sig(λ) ⊆ Sig(K) such that f(K,λ) 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 K—that is, can be seen as fK(·) such that fK(λ) is true for a 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, a 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 in Fig. 1 cannot make predictions for any triple with a constant outside this frame. In contrast, once trained on a KG K, inductive GNN-based systems, such as GraIL 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.

heading: 3 A GNN-Based Architecture for Inductive KG Completion

heading: 3.1 Overview
text: Our inductive approach relies on the completion function f realised by the following three steps.
1. Encoding, which takes an (incomplete) KG K and a set Λ of candidate triples (of the same signature) as input and returns a node-annotated graph GΛK of the form specified in Definition 1; the encoding is pair-wise: nodes in GΛK correspond to pairs of constants occurring in K and Λ. 2. GNN application, which updates the annotations of the graph nodes; in our approach, we use a graph convolutional network (GCN), which is a GNN variant popular in applications [8]. 3. Decoding, which extracts the predictions f(K,λ) for each λ ∈ Λ from the updated graph output by the GNN; this step is essentially mirroring the encoding.
The details of these steps are given in Sections 3.2, 3.3, and 3.4, respectively. The key conceptual difference distinguishing our approach from existing inductive systems, such as R-GCN and GraIL, 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 feature vector is randomly initialised; in contrast, in our approach each node in the graph encodes a pair of constants, and each element in
1In the KG literature, constants and types are sometimes collectively referred to as entities and the type relation is treated as an ordinary relation.
the initial feature vector of this node directly captures a fact in the KG involving these constants. On the other hand, existing approaches typically rely on ad-hoc 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 in the final layer of the GNN. Furthermore, in our approach, we are able to make predictions for a set Λ of candidate triples at once (for the same KG) rather than for a 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-structured data, and annotated graphs, which are the graphs manipulated by GNNs. Nodes in a 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 δ-annotated graph is an undirected graph where each node u is associated with a feature vector u ∈ Rδ . The i-th element of u is denoted by (u)i.
In our approach, the annotation 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 1 to δ to each t ∈ Types, each r ∈ Rels, and the inverse r− of each r ∈ Rels, and assume that, for every type, relation, or inverse p, element id(p) 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.

heading: 3.2 Encoding KGs
text: Our encoder maps a KG K and a set Λ of candidate triples to a δ-annotated graph GΛK where each node uc,d corresponds to a pair of (not necessarily distinct) constants c, d connected by a triple in K or Λ. To avoid duplication of information, graph GΛK contains only one of the nodes uc,d and ud,c when c ̸= d. The choice between uc,d and ud,c is immaterial to our approach; for definiteness, we employ the lexicographic order ⪯ on the set of constants and add node uc,d to GΛK only if c ⪯ d. As formalised in the following definition, the annotation of uc,d is a Boolean feature vector where an element is set to 1 if and only if the corresponding type, relation, or inverse relation holds in K for c and d (e.g., (uc,d)i = 1 if and only if c = d and (c, type, t) ∈ K for type t with id(t) = i); if c and d appear in the same triple only in Λ, then the elements of uc,d are all 0. As a 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ΛK are connected by an edge if they share a constant, which, as we will see, allows GNNs to learn structural patterns in the data (e.g., such as the pattern in Fig. 1 capturing that teachers live in the same country as their students).
Definition 2. The encoding of a KG K over Types and Rels, and a set Λ of candidate triples of the same signature as K is the δ-annotated graph GΛK where
– GΛK has a node uc,d for every two constants c, d in K such that - either c = d, - or c ≺ d and K ∪ Λ contains a triple of the form (c, r, d) or (d, r, c) for some relation r; – the feature vectors of nodes in GΛK are defined as - (uc,c)id(t) = 1 for all (c, type, t) ∈ K, - (uc,d)id(r) = 1 for all (c, r, d) ∈ K with c ⪯ d and - (uc,d)id(r−) = 1 for all (d, r, c) ∈ K with c ⪯ d, - all other elements are 0; – GΛK has an edge between different nodes uX and uY if pairs X and Y have a constant in common.
The graph in Fig. 2(a) depicts the structure of GΛK for our running example KG K inside the frame in Fig. 1 and Λ = {(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 a constant. Since our example K has no types and two relations, each feature vector (not
(G,S)
(G,X)
(S,X)(P,S)
(G,G)
(S,S)
(P,P)
(X,X)
(G,P)
(a)
X
G
P
S
Col1
Col1
Col2Col2
?
(b)

heading: 3.3 The GNN Model
text: 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 [8] 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 a representation of each δ-annotated graph G with N nodes as two matrices AG ∈ {0, 1}N×N and UG ∈ RN×δ, with
AG = A ′ G + I 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 I plays a technical role: in essence, it adds an artificial loop to each node in the graph and thus allows for a uniform treatment of combination and aggregation in GCNs. In fact, instead of AG, GCNs use its normalised version AnormG = D −½ G AGD −½ G , where DG is the node degree matrix of
AG—that is, the diagonal matrix where the i-th diagonal element is defined as (DG)ii = ∑
j(AG)ij (where Mij is the element of a matrix M in row i and column j).
Definition 3. A graph convolutional network (GCN) N with L ∈ N layers and dimension δ ∈ N is characterised by (learnable) weight matrices Wℓ ∈ Rδℓ−1×δℓ and bias vectors bℓ ∈ Rδℓ for all layers ℓ ∈ {1, . . . ,L}, where each δℓ ∈ N is the dimension of layer ℓ such that δ0 = δL = δ (the number L of layers and the dimensions δℓ of the hidden layers are hyper-parameters of the model). For an input δ-annotated graph G with N nodes given as matrices AG and UG, N updates, on each layer ℓ ∈ {1, . . . ,L}, its hidden state matrix Uℓ ∈ RN×δℓ using the rule
Uℓ = σℓ(A norm G Uℓ−1 Wℓ + bℓ),
where U0 = UG and the non-linear activation function σℓ is ReLU for each ℓ < L and the logistic sigmoid function for ℓ = L, which (in both cases) is applied to matrices element-wise. Then, N(G) is the δ-annotated graph with the same nodes and edges as G, where the feature vector of each node u is the row in UL corresponding to u.
Observe that the all the elements of a 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 to be in (0, 1), which is convenient for computing the loss.

heading: 3.4 Decoding the GNN Output
text: The result N(GΛK) of a GCN N applied to the encoding G Λ K of K and a candidate set Λ can be decoded into a set of triples over the same signature by essentially inverting the encoder. Note, however, that features in N(GΛK) are not Boolean; so, to decide if the decoded graph contains a triple, we check if the corresponding feature in N(GΛK) is above a threshold θ, which we take as 0.5 in our experiments.
Definition 4. Given a threshold value θ ∈ R, the decoding of δ-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 (uc,c)id(t) ≥ θ, – (c, r, d) such that (uc,d)id(r) ≥ θ and c ⪯ d, – (d, r, c) such that (uc,d)id(r−) ≥ θ and c ⪯ d.
Overall, a triple λ in a candidate set Λ for a KG K is predicted by a GCN N to be in the completion K∗ if λ ∈ Kdec(N(GΛK)). 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 uc,d in the final layer.

heading: 3.5 Capturing Logical Rules
text: In addition to using standard benchmarks, we will also compare the inductive capabilities of completion approaches in terms of their ability to capture common inference patterns represented in Datalog [1]—a well-known logic-based rule language in knowledge representation and databases.
A (Datalog) rule is a function-free first-order logic sentence of the form
∀x.B1, . . . ,Bn → H, (1)
where all Bi and H are atoms over predicates in Types∪Rels using variables in x as terms, such that each variable in H is mentioned in one of Bi; in our context, it is convenient to see atoms as triples as in a KG where variables are used instead of constants. Each assignment σ of constants to variables x of a rule r of form (1) maps the atoms B1, . . . ,Bn into a KG Kσr ; in the same way, σ maps H to a
triple tσr . A completion function (or a GNN-based model realising this function) captures r if, for every assignment σ of constants to x, the model predicts triple tσr when applied to the KG Kσr . In general, verifying whether a completion function captures a rule requires checking an infinite number of assignments. We can, however, restrict ourselves to a small finite number and rely on the following proposition (proven in the appendix) when comparing, in Section 4.5, the ability of different approaches to capture rules in practice, provided the completion function f realised by a system under consideration is constant-agnostic—that is, such that f(K,λ) = f(ϱ(K), ϱ(λ)) for every KG K, candidate triple λ, and renaming ϱ of constants. As far as we could check, all the systems considered in this paper realise constant-agnostic completion functions.
Proposition 1. Let r be a rule of form (1), let C be a set of |x| constants, and let Σ be the set of all assignments of constants from C to x. A constant-agnostic completion function f captures r if and only if f(Kσr , tσr ) is true for each σ ∈ Σ.

heading: 4 Evaluation
text: We have implemented our approach using Python and PyTorch v1.4.0 in a system called INDIGO. We used R-GCN [17], GraIL [21], and the system by Hamaguchi et al. [5] as 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 on an Intel(R) Xeon(R) machine with 8 cores and a 2.6 GHz CPU equipped with 540 GB of RAM running Fedora 33 (x86_64).

heading: 4.1 Benchmarks
text: We exploit a number of benchmarks proposed by Teru et al. [21] 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 WN18RR [4], and have four versions for each of these transductive benchmarks; we will call them using the pattern GraIL-BM / XXX.vi where XXX is the base and i the number of the version (e.g., GraIL-BM / NELL-995.v3 is the third version of the benchmark based on NELL-995). Similarly, the benchmarks by Hamaguchi et al., 9 in total, are all based on a transductive benchmark WordNet11 [19], and we call them Hamaguchi-BM / X-iK, where X is one of h, t, 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 of triples with Sig(V) ⊆ Sig(T ) for training and validation;
– an incomplete KG Ktest and a set Λ+test of test triples with Sig(Λ+test) ⊆ Sig(Ktest) that are to hold in the completion of Ktest for testing.
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 pseudonegative—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 it difficult to discern the truth status of a 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 pseudo-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. 1 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-BM 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 a KG is also extended with triples mentioning only unseen constants. To address this limitation, we have designed a new benchmark, called INDIGOBM, which is based on FB15K-237 and has the same structure and assumptions as the existing 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 statistics of all our 22 benchmarks are summarised in Table 1.

heading: 4.2 Performance Metrics
text: We evaluate the systems’ performance using standard classification metrics (e.g., accuracy and 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 a benchmark with incomplete KG Ktest and a set Λ+test of test triples, we take P as the set of all pairs (Ktest,λ) with λ ∈ Λ+test for all metrics; in turn, we obtain N by sampling from the set N∗ of all pairs (Ktest,λ) with the pseudo-negative triples λ ̸∈ Ktest ∪ Λ+test and Sig(λ) ⊆ Sig(Ktest) 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 a 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-based metrics for a KG completion system evaluated on P and N are then computed in the standard way based on the numbers tp, tn, fp, fn of true positives, true negatives, false positives, and false negatives. In our experiments, we use precision tp/(tp+ fp), recall tp/(tp+ fn), and accuracy (tp + tn)/(tp + tn + fp + fn). Besides this, we use F1-score and the area under the precision-recall curve (AUC), which are defined as usual from precision and recall for different thresholds (computed using confidence-based predictions).
For ranking-based metrics, we construct N = Nc ∪ Nr ∪ Nd by randomly “corrupting” positive examples. In particular, for each positive example (Ktest, (c, r, d)) in P , set Nc contains 50 randomly sampled negative examples in N∗ of the form (Ktest, (c′, r, d)); sets Nr and Nd are constructed analogously by corrupting r and d and taking all and 50 samples, respectively (note that the number of candidates for Nr is bounded by the number of relations in Sig(Ktest)). Our ranking-based metrics for a KG completion system evaluated on P and N are then computed as follows. For each λ ∈ Λ+test and x ∈ {c, r, d}, let Rankx(λ) be the position of (Ktest,λ) in the decreasing-ordered list of the system’s confidence predictions for all the examples in P ∪Nx. Then, we use entity and relation hit metrics e-Hits@k = (Hitsc@k + Hitsd@k)/2 and r-Hits@k = Hitsr@k, for k = 1, 3, 10, where, for each x, Hitsx@k = m/|Λ+test| for m the number of λ ∈ Λ+test such that Rankx(λ) ≤ k. We also use the entity and relation mean reciprocal ranks e-MRR = (MRRc + MRRd)/2 and r-MRR = MRRr, where, for each x, MRRx = h/|Λ+test|, for h the sum of 1/Rankx(λ) for all λ ∈ Λ+test.

heading: 4.3 Training
text: (c2, r, d
′) with c1 ̸= c2. For each triple (c, type, t) ∈ Λ+train we similarly sampled from N three triples of the form (c, type, t′) where t′ is disjoint from t type in T , which is defined analogously to disjoint roles.
As a result, we generate up to 9 negative training examples for each positive example.
We employed the standard cross-entropy loss function and trained for 3,000 epochs using Adam optimisation with L2 penalty 5e-8. We set as hyper-parameters 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 on each of the benchmarks using the validation sets to obtain a most favourable (for all benchmarks) setting of 2 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 in the papers without modifications, including their negative sampling strategies for training, the values of hyper-parameters, and the number of training epochs.

heading: 4.4 Evaluation Results
text: The results for several indicative metrics (accuracy, AUC, e-Hits@3, and r-Hits@3) of the metric-base evaluation of the systems on the benchmarks are summarised in Table 2 (the system by Hamaguchi et al. is not applicable to GraIL-BM and INDIGO-BM due to its limited inductive capabilities); results for other metrics are 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 ranking-based entity metrics 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 as 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-BM/b-5k dataset took more than 0.5 hours for R-GCN, more than 4.5 hours for GraIL, 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.

heading: 4.5 Capturing Logical Rules
text: We also studied the systems’ ability to learn rules by means of capturing, as 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 _a by types and relations. We took GRAIL-BM/NELL-995.v3 and INDIGO-BM benchmarks for experiments, and considered INDIGO, GraIL and R-GCN trained for these benchmarks. For each benchmark with an incomplete KG Ktest and a set Λ+test 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(Ktest). We then identified the rules with confidence at least 0.7, where the confidence of a rule r in Ktest and Λ+test is n/m for m the number of assignments σ such that Kσr ⊆ Ktest and n the number of such σ that also satisfy tσr ∈ Ktest ∪Λ+test. Finally, for each model we computed, using Proposition 1, the proportion of captured high-confidence rules.
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.

heading: 5 Conclusion and Future Work
text: In this paper we have proposed a novel GNN-based approach to inductive KG completion which significantly outperforms state-of-the-art approaches. The key novelty of our approach is that it 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.
Acknowledgments and Disclosure of Funding
This work was supported by the EPSRC projects OASIS (EP/S032347/1), UK FIRES (EP/S019111/1), the SIRIUS Centre for Scalable Data Access, and Samsung Research UK.

Review summaries:
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.

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.

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.