ReFactor GNNs: Revisiting Factorisation-based Models from a Message-Passing Perspective
Authors: Yihong Chen
Pushkar Mishra
Luca Franceschi
Pasquale Minervini
Pontus Stenetorp
Sebastian Riedel
Venue: NeurIPS 2022 Accept (2022)
Keywords: knowledge graph completion
link prediction
multi-relational graphs
graph neural networks
inductive reasoning

Abstract: Factorisation-based Models (FMs), such as DistMult, have enjoyed enduring success for Knowledge Graph Completion (KGC) tasks, often outperforming Graph Neural Networks (GNNs). However, unlike GNNs, FMs struggle to incorporate node features and generalise to unseen nodes in inductive settings. Our work bridges the gap between FMs and GNNs by proposing ReFactor GNNs. This new architecture draws upon $\textit{both}$ modelling paradigms, which previously were largely thought of as disjoint. Concretely, using a message-passing formalism, we show how FMs can be cast as GNNs by reformulating the gradient descent procedure as message-passing operations, which forms the basis of our ReFactor GNNs. Across a multitude of well-established KGC benchmarks, our ReFactor GNNs achieve comparable transductive performance to FMs, and state-of-the-art inductive performance while using an order of magnitude fewer parameters.

REFACTOR GNNS: Revisiting Factorisation-based Models from a Message-Passing Perspective
Yihong Chen Te
Pushkar Mishra
Luca Franceschi
Pasquale Minervini TD*
Pontus Stenetorp" Sebastian Riede!
TUL Centre for Artificial Intelligence, London, United Kingdom
Meta AI, London, United Kingdom
Amazon Web Services, Berlin, Germany
Schooo of Informatics, University of Edinburgh, Edinburgh, United Kingdom
[yihong. chen, p p.stemetorp, riedel (@es /ueeeucll....eeeeee.eeee.ee.eele ac. uk
pushikarmissha@@metaa.c com
franulucGamazon. de p.minervinised. ac uk
Abstract
Factorisation-buse Models (FMs), such as DistMult, have enjoyed enduring suc- cess for Knowledge Graph Completion (KGC) tasks, often outperforming Graph Neural Networks (GNNs). However, unlike GNNs, FMs struggle to incorporate node features and generalise to unseen nodes in inductive settings. Our work bridges the gap between FMs and GNNs by proposing REFACTOR GNNs. This new architecture draws upon both modelling paradigms, which previously were largely thought of as disjoint. Concretely, using a message-passing formalism, show how FMs can be cast GNNs by reformulating the gradient descent procedure as message- pressage-aassing operations, which forms the basis of our REFACTOR GNNs. Across multitude of well eslbblsstll KGC benchmarks, our REFACTOR GNNS achieve comparable transductive performance to FMs, and state-of-the-art inductive performance while using order of magnitude fewer parameters.
Introduction
In recent years, machine learning on graphs has attracted significant attention due to the abun- dance of graph-structured data and developments graph learning algorithms. Graph Neural Networks (GNNs) have shown state-of-the-art performance for many graph-related problems, such as node classification [16] and graph classification [7]. Their main advantage is that they can easily be applied in an inductive setting: generalising to new nodes and graphs without re-training, However, despite many attempts applying GNNs for multi-relational link prediction tasks such as Knowledge Graph Completion [26], there are still few positive results compared to factorisation-be based mod- els (FMs) [45, 39]. As it stands, GNNs either after resolving reproducibility concerns deliver significantly lower performance [23, 36] or yield negligible performance gains at the cost of highly sophisticated architecture designs [43]. notable exception is NBFNet [49], but even here improve- ments come at the price of high computational inference costs compared to FMs. Furthermore, it is unclear how NBFNet could incorporate node features, which - as we will see in this work leads to remarkably lower performance in an inductive setting. On the other hand FMs, despite being simpler architecture, have been found to be very accurate for knowledge graph completion when coupled with appropriate training strategies [30] and training objectives [17, 2]. However, they also come with shortcomings in that they, unlike GNNs, can not be applied in an inductive setting.
Work done while UCL.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Given the respective strengths and weaknesses of FMs and GNNs, can we bridge these two seemingly different model categories? While exploring this question, we make the following contributions:
By reformulating gradient descent on node embeddings using paasage-passing primitives, we show a practical connection between FMs and GNNs, in that: FMs can be treated as special instance of GNNs, but with infinite neighbourhood, layer-wise training and global normaliser.
Based on this connection, we propose a new family of architectures, referred to as REFACTOR GNNs, which interpolates between FMs and GNNs. In essence, REFACTOR GNNs inductivise FMs by using finite number of paassage-passing layers, and incorporating node features.
Through an empirical investigation across well-established inductive and transductive bench- marks, we find REFACTOR GNNs achieve state-of-the afr inductive performance and comparable transductive performance to FMs- despite using an order of magnitude fewer parameters.
Background
Knowledge Graph Completion (KGC) [25] is canonical task of multi-relational link prediction. The goal is to predict missing edges given the existing edges in the knowledge graph. Formally, a knowledge graph contains set of entities (nodes) & = {I....,,ET) [E1).
a set of relations (edge types)
R = =I,..... (l...., [R]] and a set of typed edges between the entities T = {(v). rı, w;) w)) where each triplet (v,, Tt, wy) indicates relationship of type r, E R between the subject 2 E E and the object W/ E E. Given a node v, we denote its outgoing 1-hop neighbourhood as the set of relation-object pairs M1 [v] = ((r, o) (v,r,o) E (T), its incoming 1-hop neighbourhood as the set of subject-relation pairs [v = ((r,
(s,r,v) ( E T), and [c] [N] UN! [u] the union of the two. We denote the neighbourhood of under specific relation r as W v]. Entities may come with features X E [ for describing them, such as textual encodings of their names and/or descriptions. Given (training) knowledge graph, KGC is evaluated by answering (v,r, ?tyyyyl queries i.e. predicting the object given the subject and relation the triplet.
Multi-relational link prediction models can be trained via maximum likelihood, by fitting a parame- terized conditional categorical distribution (w v, r) over the candidate objects of a relation, given the subject v and the relation type r:
Po v) = exp & (v, w.
Enes exp I's (V.
R is a scoring function, which, given a triplet (v, w). returns the likelihood that the corresponding edge appears in the knowledge graph. We illustrate our derivations using DistMult [45] as the score function and defer extensions to general score functions, e.g. ComplEx [39], to the appendix. For DistMult, the score function ro is defined as the tri-linear dot product of the vector representations corresponding to the subject, relation, and object of the triplet:
Here To X
To(u, r. w) = (v) (w))). Σ fa(v)ifsww)))r())
where fe E K and go R - R are learnable maps parameterised by & and vp that encode entities and relation types into K -dimensioonll vector representations, and 0 = (Ø, v). We will refer to f and as the entity and relation encoders, respectively. If we define the data distribution as Pz(z) | Σ (v.rwweeT (v.r,w)) (x)) where (e)rrw)) (I)) is Dirac delta function at (v, r, w). then the objective is to learn the model parameters by minimising the expected negative log-likelihood [()) of the ground-truti entities for the queries (v, r, ?) obtained from T:
arg min [()) where
((0) -Eg-ry [log( Po r)]
Σ
log Po(wy,,))) (3)
ITi
(0,7,w)ET
During inference, we use Pg for determining the plausibility of links not present in the training graph.
'The traditional view is that the transductive nature of FMs stem from their need to retrain on new nodes, a view which we further underpin by also observing that FMs are not inductive due to the need for infinite layers of on the message paassig...

---

2.1 Factorisation-batn bbasd Models for KGC
In factorisation- based models, which we assume to DistMult, fa and ge are simply parameterised as look-up up tables, associating each entity and relation with a continuous distributed representation:
(v) 6(v), & E RlEiX and go(r) +[rr,, &b E RR
(4)
2.2 GNN-based Models for KGC
GNNs were originally proposed for node or graph classification tasks [8, 32]. To adapt them to KGC, previous work has explored two different paradigms: node-wise entity representations [33] and pair-wise entity representations [37, 49]. Though the latter paradigm has shown promising results, requires computing representations for all pairs of nodes, which can be computationally expensive for large-scale graphs with millions of entities. Additionally, node- wise representations allow for using a single evaluation of fz(v) for multiple queries involving v.
Models based on the first paradigm differ from pure FMs only in the entity encoder and lend themselves well for a fairer comparison with pure FMs. We will therefore focus on this class and leave the investigation of pair-wise representations future work. Let qs 9 x X + USENI R be GNN encoder, where G {G G & x R x E) is the set of all possible multi-relational graphs defined over & and R. and X is the input feature space, respectively. Then we can set fv( = 4o (T, (e) Following the standard message-pasiin passing framework [7, 9] used by the GNNs, view 9s = 9º ... o q' the recursive composition of L N+ layers that compute intermediate representations ht' for I E {1..... L} (and ho X) for all entities in the KG. Each layer is made up of the following three functions:
x RKK R that computes the message along each 1. A message function dha RRK x R
edge. Given edge (u, w) T, the not only makes use of the node states h [u] and ht [w]] (as in standard GNNs) but also uses the relation denote the message as
m' w) div (h'- [[], h h
2. An aggregation function d USEN R - RRKK that aggregates all messages from the 1 h-hop neighbourhood of a node; denote the aggregated message as
z z'[0| = d' (4m'lu, r, w| (r, w) E [w]):
3. An update function du : R R.K R that produces the new node states h! by combining previous node states 1 and the aggregated messages zt:
h [v] du [w], z'(u)).
Different parameterisations of g/a- 93 and dt lead different GNNs. For example, R-GCNs [33] define the g/1 function using per-relation the linear transformations m' [V. w] x Whh [w];
d' is implemented by summation and et is a non-lineat transformation h' [0] = (22([]] + -o)) where a is the sigmoid function. For each layer, the learnable parameters are [W] and W all of which are matrices in K
3 Implicit Ressage-Passing in FMs
The sharp difference in analytical forms might give rise to the misconception that GNNs incorporate message-passingg over the neighbourhood of each node (up to L-hops), while FMs do not. In this work, we show that by explicitly considering the training dynamics of FMs, can uncover and analyse the hidden pesssage-passing mechanism within FMs. In turn, this will lead us to the formulation of a novel class of GNNs well suited for multi-relational link prediction tasks (Section 4). Specifically, we propose to interpret the FMs' optimisation process of their objective (3) as the entity encoder. If we consider, for simplicity, a gradient descent training dynamic, then
for (v) = d'[uj GD 1 [)) GD o... GD (00, TT)o),
(5)
3

---

where øf is the embedding vector at the t-th step, t E N+ is the total number of iterations and Φ is random initialisation. GD is the gradient descent operator:
i Blog P(wle,r)
GD T) = -V
(6)
OΦ
where [T|-1, with 7) learning rate. We now dissect Equation (6) in two different (but equivalent) ways. In the first, which we dub the edge view, we separately consider each addend of the gradient V.L. In the second, aggregate the contributions from all the triplets to the update of a particular node. With this latter decomposition, which we call the node view, we can explicate the message-passingg mechanism the core of the FMs. While the edge view suits vectorised implementation better, the node view further exposes the information flow among nodes, allowing us to draw analogy to passing GNNs.
3.1 The Edge View
Each addend of Equation (6) corresponds single edge (u, r, w) E T and contributes to the update of the representation of all nodes. The update on the representation of the subject Φfu] is:
GD( w)) Φlv] +a g(r) O
Σ WEE
Po(ulu,))g()) o ølu]
The - term indicates information flow from w (a neighbour of v) to v, increasing the score of the gold triplet (u,r; w)). The -> v term indicates information flow from global nodes, decreasing the scores of triplets (e, r, ?) with as the subject and as the predicate. Similarly, for the object w,
GD {(e, r, w))) [w] = Φfw] + ax - Po(wlu, r)) g(r) @ o(v).
0- where, again, the e -> w term indicates information flow from the neighhouring node v. Finally, for the nodes other than u and w, we have
GD ((o,,, = ølu + a
-Po(ulo, o s(r)
3.2
The Node View
To fully uncover the message-passing mechanism of FMs, we now focus on the gradient descent operation over single node E, referred to the central node in the GNN literature. Recalling Equation (6), we have:
Olg P(w v,F)
GD T) [[v] +
Σ
00lu)
(UNTWEET
which aggregates the information stemming from the updates presented in the edge view. The next theorem describes how this total information flow to particular node can be recast an instance of message passing (cf. Section 2.2). We defer the proof to the appendix.
Theorem 3.1 (Message passing in FMs). The gradient descent operator GD (Equation (7)) on the node embeddings of a DistMult model (Equation (4)) with the maximum likelihood objective in Equation (3) and a multi-relational graph T defined over entities & induces message-passing operator whose composing functions funcction are:
(n(olu) r, d(w]) =
<|w] o g(r)
if(r,) E A (r, N
(8)
(1 Po(ulu, r)][w e g(r)
(fmml,,,,,)) (r, w) [ (1
Σ
m|u, ,,
(9)
(o(ofu), 2(1]) = 2la + +z([o] - Bn(u),
(10)

---

where, defining the sets of triplets T- ((s,r,0) ET + uo
IT
n/u]
EP x (uwrr((())))()))) @ olu] +
Ep, y Polls.)) o[s],
(11)
IT
[T]
where PN] and P are the empirical probability distributions associated to the respective sets.
What emerges from the equations that each GD step contains an explicit information flow from the neighbourhood of each node, which is then aggregated with simple summation. Through this direct information path, & GD steps cover the t-hop neighbourhood of As goes towards infinity or in practice as training converges, FMs capture the global graph structure. The update function (10) somewhat deviates from classic message passing frameworks as ni(v] of Equation (11) involves global information. However, we note that we can interpret this mechanism under the framework of augmented message passing [41] and, in particular, as an instance of graph rewiring.
Based on Theorem 3.1 and Equation (5), we can now view & as the transient node states h (cf. Section 2.2) and GD on node embeddings as a message-passing layer. This dualism sits at the core of the ReFactor GNN model, which we describe next.
4 REFACTOR GNNs
FMs trained by minimising the objective (3), initialising both sets of parameters (o and ()) and performing GD until approximate convergence (or until early stopping terminates the training). The implications are twofold: i) the initial value of the entity lookup table does not play any major role in the final model after convergence, and ii) if we introduce a new set of entities, the conventional wisdom to retrain the model on the expanded knowledge graph. This is computationally rather expensive compared to the "inductive" models that require no additional training and can leverage node features like entity descriptions. However, as we have just seen in Theorem 3.1, the training procedure of FMs may be naturally recast message-passien is possible use FMs for inductive learning tasks. In fact, we envision that there an entire novel spectrum of model architectures interpolating between pure FMs and (various instantiations of) GNNs. Here we propose one simple implementation of such an architecture which we dub REFACTOR GNNs. Figure 1 gives an overview of REFACTOR GNNs.
operation, which suggests that
The REFACTOR Layer A REFACTOR GNN contains L. REFACTOR layers, that we derive from Theorem 3. Aligning with the notations in Section 2.2, given a KG and entity representations h IR [ K the REFACTOR layer computes the representation of a node follows:
ht [u] = (' ( [(] = n [0]
frrlvi +
Σ
dhs (h'-1 [0), h' [w)),
(12)
(M
where the terms n' and y/a are derived from Equation (11) and Equation (8), respectively. We note that REFACTOR GNNS treat incoming and outgoing neighbourhoods differently instead treating them equally in the R-GCN, the first GNN on multi-relational graphs [33].
Equation (12) describes the full batch setting, which can be expensive the KG contains many edges. Therefore, in practice, whenever the graph is big, we adopt stochastic evaluation of the REFACTOR layer by decomposing the evaluation into several mini-batches. We partition T into a set of computationally tractable the subgraph induced by it and readjust the computation of n [v] to include only entities and edges present in it. We leave the investigation of other stochastic strategies (e.g. by taking Monte Carlo estimations of the expectations in Equation (1 (I) to future work. Finally, we cascade the mini-batch evaluation to produce one full layer evaluation.
For each of them, we restrict the neighbourhoods to
The learnable parameters of REFACTOR GNNS are the relation embeddings v. which parameterise g(r) in ghr: I E [1, LJ. Inspired by [5, 46), we learn vi by layer-wise (stochastic) gradient descent. This is in contrast to conventional GNN training, where we need to backpropagate through
Training
TTypccally until convergence, possibly by partially warm-starting 0.
5

---

P(v (w,)) r)
dlval @ g(rz)
V1
V4
33
Softmax
P 11-1)) Ølvy] O g(r))
P(y (1.12)
ri r2
Alyy g(r))
V/2
V3
W
Figure I: ReFactor GNN architecture the left figure describes the messages (coloured edges) used to update the representation of node U1. which depend on the type of relationship between the sender nodes and 21 the graph G {(02. r1, 01 (V3, r2, v1), (v1, F3, va)}; the right figure describes the computation graph for calculating P( | w, r), where representations of w, r, and v are used to score the edge (w, (,,r,) v) via the scoring function r, which then normalised via the Softmax function.
E E and r E R: the embedding
all the layers. A (full-batch) GD training dynamic for ab can be written as 1/++1 = 1/4 VV where L, (16x) = - 171 E log Pe. (wle, r), with:
Pv. (w|u,) = Softmax(T(rr (ww)
((,,,,))
and the node state update as
h² 1
X q² mod (T,h'=)) if mod L L=
(13)
otherwise.
Implementation-wisse such training dynamic equals to using external memory for storing historical node states 11-1 akin to the procedure introduced in [5]. The cached node states can then be queried to compute ht using Equation (12). From this perspective, we periodically clear the node state cache every full batches to force the model to predict based on on-the-fly L-layer message-passing. After training, we obtain u/* and perform inference by running L-layer message-passing passeepppnnnggggg with vhr In general, determines the number of effective message-passing layers in REFACTOR GNNs. A larger L enables REFACTOR GNNS to fuse information from more hops of neighbourhoods into the final node representations. In the meantime, it reduces the inductive applicability of REFACTOR GNNs due to seo-thnht and computational requirements. In the extreme case of L oo. where we never clear the node state cache during training. the final cached node states will be used for inference. Note that this latter inference regime is inherently transductive since there will be cached states for new nodes.
5 Experiments
We perform experiments to answer the following questions regarding REFACTOR GNNs:
Q1. REFACTOR GNNS are derived from a message-passing reformulation of FMs: do they also inherit FMs' predictive accuracy in transductive KGC tasks? (Section 5.1)
Q2. REFACTOR GNNs "inductivise" FMs. Are they more statistically accurate than other GNN baselines in inductive KGC tasks? (Section 5.2)
Q3. The term n/fe] involves nodes that are not in the 1-hop neighbourhood. Is such augmented message passing [41] necessary for good KGC performance? (Section 5.3)
For transductive experiments, we used three well-established KGC datasets: UMLS [14], CoDEx- S [31], and FB15K237 [38]. For inductive experiments, we used the inductive KGC bench- marks introduced by Grall. [37], which include pairs of knowledge graphs: (FBI5K237 vi, FB/5K237 vi vi_ind), (WNI8RR_H) vi, WNI8RR vi s__indd, and (NELL_pi, -i, NELL_vi_ine wi_jnnd), where E [1,2,3,4 4), and (ri, vi_ind) represents a pair of graphs with a shared relation vocabulary and non-overlapping entities. We follow the standard KGC evaluation protocol by fully ranking all the
'The implementation will be available https: //tg://gtttttt/t www.ywooonooooooeooooooo.ooooooe chen/RePactorOHI.

---

Entity Encoder
UMLS
CoDEx-S
FB15K237
R-GCN
0.33
0.25
Lookup (FM, specif. DistMult)
0.90
0.43
0.30
REFACTOR GNNS (L = o0)
0.93
0.44
0.33
Table I: Test MRR for transductive KGC tasks,
candidate entities and computing two metrics using the ranks of the ground-truth entities: Mean Reciprocal Ranking (MRR) and Hit Ratios at Top K (Hits@ K) with K E [1,3, 10). For the inductive KGC, we additionally consider the partial-ranking evaluation protocol used by GralL for a fair comparison. Empirically,, we find full ranking more difficult than partial ranking, and thus more suitable for reflecting the differences among models on GralL datasets we would like to call for future work on GralL datasets to also adopt a full ranking protocol on these datasets.
Our transductive experiments used L = oo, i.c. node states cache is never cleared, as we wanted to see if REFACTOR GNNs (L = 20) can reach the performance of the FMs; on the other hand, in our inductive experiments, we used REFACTOR GNNs with L E {1, 2, 3, 6, 9}. since we wanted to test their performances inductive settings akin to standard GNNs. We used a hidden size of 768 for the node representations. All the models are trained using [128, 512] in-batch negative samples and one global negative node for each positive link. We performed grid search over the other pyprrpparaeeters and selected the best configuration based on the validation MRR. Since training deep GNNs with full-graph message passing might be slow for large knowledge graphs, we follow the literature [10, 50, 47] to sample sub-graphs for training GNNs. Considering that sampling on the fly often prevents high utilisation of GPUs, we resort to a two-stage process: we first sampled and serialised sub- sub-graphs around the target edges in the mini- batches; we then trained the GNNs with the serialised sub- sab-graphs. To ensure we have sufficient sub-graphs for training the models, we sampled for 20 epochs for each knowledge graph, i.c. 20 full passes over the full graph. The sub-graph sampler we currently used is LADIES [50].
5.1 REFACTOR GNNS for Transductive Learning (Q1)
REFACTOR GNNS are derived from the message-passing reformulation of FMs. We expect them to approximate the performance of FMs for transductive KGC tasks. To verify this, we run experiments on the datasets UMLS, CoDEx-S, and FB15K237. For fair comparison, decoder and consider i) lookup embedding table as the entity encoder, which forms the FM when combined with the decoder (Section 2.1), and ii) REFACTOR GNNS as the entity encoder. REFACTOR GNNS are trained with L = do, i.e. we never clear the node state cache. Since transductive KGC tasks do not involve new entities, the node state cache in REFACTOR GNNS can be directly used for link prediction. Table summarises the result. We observe that REFACTOR GNNs achieve a similar or slightly better performance compared to the FM. This shows that REFACTOR GNNs are able to capture the essence of FMs and thus maintain strong at transductive KGC.
use Equation (2) the
5.2 REFACTOR GNNS for Inductive Learning (Q2)
Despite FMs' good empirical performance on transductive KGC tasks, they fail to be inductive as GNNs. According to our reformulation, this is due to the infinite message-passing layers hidden in FMs' optimisation. Discarding infinite message-passing layers, REFACTOR GNNs enable FMs to perform inductive reasoning tasks by learning to use finite set of message-passing layers for prediction similarly to GNNs.
Here we present experiments to verify REFACTOR GNNs's capability for inductive reasoning. Specifically, we study the task of inductive KGC and investigate whether REFACTOR GNNs can generalise to unseen entities. Following [37], on GralL datasets, we trained models on the original graph, and run 0-shot link prediction on the ind test graph. Similar to the transductive experiments, we use Equation (2) as the decoder and vary the entity encoder. We denote three-layer REFACTOR GNNS as REFACTOR GNNs (3) and six-layer REFACTOR GNNS as REFACTOR GNNs (6). We consider several baseline entity encoders: i) no-pretrain, models without any pretraining on the original graph; ii) (3), three-layer graph attention network [40]; iii) GAT(6), six-layer graph attention network; iv) GraIL, sub-graph-based relational GNN [37]; v) NBFNet, path-
7

---

With Random Features
With Textual Features
No Pretrain
0.15
0,242
GAT(3)
0.806
GAT(6)
0.826
ReFactor(3)
0.673
ReFactor(8)
0,787
Neural-LP
0.529
DRUM
0.529
RuleN
Grail.
(Teru 2020)
NBFNet (Zhu
0.00
0.25
0.50
0.75
1.00
Hits@10, Negative
Figure 2: Inductive KGC Performance. Models are trained the KG FBI5K237_v/ and tested another KG FB15K237_V' _t___v/_ind,, ind, where the entities are completely new. The results of GralL and NBFNet are taken from [49]. The grey bars indicate methods that are not devised incorporate node features.
based GNN [49], current SoTA on GralL datasets. In addition to randomly initialised vectors the node features, we also used textual node features, RoBERTa [20] Encodings of the entity descriptions, which are produced by SentenceBERT [29]. Due to space reason, we present the results on (FB15K237 y1, FB/5K237 yi_ind) in Figure 2. Results on other datasets are similar and can be found in the appendix. We can see that without textual node features, REFACTOR GNNs perform better than GralL (+23%); with textual node features, REFACTOR GNNs outperform both GralL (+43%% and NBFNet (+ (+10%), achieving new SoTA results on inductive KGC.
Performance vs Parameter Efficiency as #Message-Pasiine Layers Increases Usually, as the number of message-passing layers increases in GNNs, the over-smoothing issue occurs while the computational cost also increases exponentially. REFACTOR GNNS avoid this by layer-wise training and sharing the weights across layers. Here we compare REFACTOR GNNs with {1,3, 6, 9} message- -assiigg layer(s) with same-depth GATs results are summarised in Figure 3. We observe that increasing the number of message-passing layers in GATs does not necessarily improve the predictive accuracy - the best results were obtained with 3 while using and layers leads to performance degradation. On the other hand, REFACTOR GNNs obtain consistent improvements when increasing #Layers from 1 to 3, 6, and 9. REFACTOR GNNs (6, 6) and (9, 9) clearly outperform their GAT counterparts. Most importantly, REFACTOR GNNS are more parameter-efficien than GATs, with constant #Parameters #Layers increases.
passing layers on FB/5K237 /
5.3 Beyond Message-Passing (Q3)
As shown by Theorem 1. REFACTOR GNNs contain only terms capturing information flow from the 1-hop neighbourhood, which falls into the classic message- passing framework, but also term naue] that involve nodes outside the 1-hop neighbourhood. The term n(u] can be treated as augmented message-passing experiments to measure the impact of the vuls term. Table summarises the ablation results: we can see that, without the term nlv)., REFACTOR GNNS with random vectors as node features yield 2% lower MRR, while REFACTOR GNNs with RoBERTa textual encodings as node features produce 7% lower MRR. This suggests that augmented message-passing also plays significant role in
dynamically rewired graph [41]. Here we perform ablation

---

GAT ReFactorGNN #Params GAT
#Params ReFactorGNN
0.6
#Params (M)
MRR
0.2
0.0
#Message-Passing Layers
Figure 3: Performance Parameter Efficiency as #Layers Increases on FB15K237 vl. The left axis Test MRR while the right axis is #Parameters. The solid lines and dashed lines indicate the changes of Test MRR and the changes of #Parameters.
Test MRR
With Random Features
With Textual Features
with rffu]
0.425
0.486
without ni(e]
0.418
0.452
Table 2: Ablation on n/u] for REFACTOR GNNS (6) trained on FB15K237_v1.
REFACTOR GNNs' generalisation properties in downstream link prediction tasks. Future work might gain more insights by further dissecting the n(v] term.
Related Work
Graph Representation Learning Multi-relational graph representation learning concerns graphs with various edge types. Another relevant line of work would be representation learning over heterogeneous graphs, where node types are also considered. Previous work on multi-relational graph representation learning focused either on FMs [27, 39, 45, 17, 26, 3, 24. 2] or on GNN-based models [33, 44, 48, 18J. Similar to recent finding in benchmark study over heterogeneous GNNs [21], where the best choices of GNNs for heterogeneous graphs seem regress to simple homogeneous GNN basclines, the progress of multi-relational graph representation learning also mingles with FMs, the very classic multi-relational link predictors. Recently, FMs were found to be significantly more accurate than GNNs in KGC tasks, when coupled with specific training strategies [30, 12, 17]. While more advanced GNNs [49] for KBC are showing promise the cost of extra algorithm complexity, little effort has been devoted to establishing the links between plain GNNs and FMs, which are strong multi-relational link predictors despite their simplicity. Our work aims align GNNs with FMS so that we can combine the strengths from both families of models.
Relationships between FMs and GNNs A very recent work [35] builds theoretical link between structural GNNs and node (positional) embeddings. However, on one end of the link, second model category encompasses not merely factorisation-base models but also many practical graph neural networks, between which the connection is unknown. Our work instead offers more practical link between positional node embeddings produced by FMs and positional node embeddings produced by

---

GNNs, while at the same time focusing on KGC. Beyond FMs in KGC, using graph signal processing theory, [34] show that matrix factorisation (MF) based recommender models correspond to ideal low-pass graph convolutional filters. They also find infinite neighbourhood coverage in MF although using a completely different approach and focusing on a different domain in contrast to our work.
Message Passing Message-passing is itself a broad terminology people generally talk about it under two different contexts. Firstly, as computational technique, message passing allows recursively decomposing a global function into simple local, parallelisable computations [22], thus being widely used for solving inference problems in graphical model. Specifically, we note that message passing- based inference techniques were proposed for matrix completion-basee based recommendation [15] and Bayesian Boolean data decomposition [28] in the pre-deep-learning era. Secondly, as a paradigm of parameterising learnable functions over praph-structure data, message-passing has recently been used to provide unified reformulation [7] for various GNN architectures, including Graph Attention Networks [40], Gated Graph Neural Networks [19], and Graph Convolutional Networks [16]. In this work, we show that FMs can also be cast as a special type of pressage-passingg GNNs by considering the gradient descent updates [1] over node embeddings as message-passing operations between nodes. To the best of our knowledge, our work is the first to provide such connections between FMs and passsage-passing GNNs. We show that FMs can be seen instances of GNNs, with characteristic feature about the nodes being considered during the message- message-passing process: our REFACTOR GNNs can be seen using an Augmented Message-Passe Passing process dynamically re-wired graph [41].
7 Conclusion & Future Work
Conclusion. Motivated by the need of understanding FMs and GNNs despite the sharp differences in their analytical forms, our work establishes a link between FMs and GNNs on the task of multi- relational link prediction. The reformulation of FMs as GNNs addresses the question why FMs are stronger multi-relational link predictors compared to plain GNNs. Guided by the reformulation, we further propose a new variant of GNNs, REFACTOR GNNs, which combines the strengths of both GNNs and classic FMs. Empirical experiments show that REFACTOR GNNs produce significantly more accurate results than our GNN baselines on inductive link prediction tasks.
Limitations. Since we adopted two-stage (sub-graph serialisation and then model training) approach instead of online sampling, there can be side effects from the low sub-graph diversity. In our experiments, we used LADIES [50] for sub-graph sampling. Experiments with different sub-grap sub-graph sampling algorithms, such as GraphSaint [47] might affect the downstream link prediction results. Furthermore, it would be interesting to analyse decoders other than DistMult, as well as additional optimisation schemes beyond SGD and AdaGrad. We do not dive deeper into the expressiveness of REFACTOR GNNs. Nevertheless, we offer brief discussion in Appendix F.
Future Work. The most direct future work would be using the insight develop more sophisticated models at the crossroad between FMs and GNNs, e.g. by further parameterising the message/update function. One implication from our work is that reformulating FMs as weessage-passingg enables the idea of "learning to factorize". This might broaden the usages of FMs, going beyond link prediction, to tasks such as graph classification. Another implication comes from our approach of unpacking embedding updates into series of message-passine passing operations. This approach can be generalised to other dot-product-basee -baed models that use embedding layers for processing the inputs, e.g. transformers. In general, the direction of organising FMs, GNNs, and transformers under the same framework will allow a better understanding of all three models.
Acknowledgements
We would like to thank all reviewers for their constructive comments. We thank people with whom we had some really interesting chats throughout the project: Zhaocheng Zhu, Floris Geerts, Muhan Zhang, Patrick Lewis. Hanqing Zeng, Shalini Maiti, Yifei Shen, Yinglong Xia, Matthias Fey, Jing Zhu, Mare Deisenroth and Maximilian Nickel. Yihong would like to thank the UCL-Facebook Al Research joint PhD program for generously funding her PhD. Pasquale and Pontus were partially funded by the European Union's 's Horizon 2020 research and innovation programme under grant agreement no. 875160, and by an industry grant from Cisco.
10

---

References
[1] Léon Bottou, Stochastic Gradient Descent Tricks, pages 421-436. Springer Berlin Heidelberg. Berlin, Heidelberg, 2012.
[2] Yihong Chen, Pasquale Minervini, Sebastian Riedel, and Pontus Stenetorp. Relation prediction as an auxiliary training objective for improving mulaiirelational graph representations. In 3rd Conference on Automated Knowledge Base Construction, 2021.
[3] Tim Dettmers, Pasquale Minervini. Pontus Stenetorp, and Sebastian Riedel. Convolutional 2d knowledge graph embeddings. In AAAI, pages 181 1811-1818. AAAI Press, 2018.
[4] John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12(61):2121-2159 2011
[5] Matthias Fey, Jan Eric Lenssen, Frank Weichert, and Jure Leskovec. Gnnautoscale: Scalable and expressive graph neural networks via historical embeddings. In ICML, 2021.
[6] Floris Geerts and Juan I. Reutter. Expressiveness and approximation properties of graph neural networks. In International Conference on Learning Representations, 2021.
[7] Justin Gilmer, Samuel S Schoenholz, Patrick Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference on machine learning, pages 1263-1272. PMLR, 2017.
[8] Marco Gori, Gabriele Monfardini, and Franco Scarselli. A new model for learning in graph domains. Proceedings. 2005 IEEE International Joint Conference on Neural Networks, 2005., 2:729-734 vol. 2, 2005.
[9] William L. Hamilton. Graph representation learning. Synthesis Lectures on Artificial Intelligence and Machine Learning, 14(3)
[10] William L Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning large graphs. In Proceedings of the 31st International Conference on Neural Information Processing Systems, pages 1025-1035, 2017.
[11] Ziniu Hu, Yuxiao Dong, Kuansan Wang, Kai- Wei Chang, and Yizhou Sun. Gpt-gnn: Generative pre-training of graph neural networks. In Proceedings of the 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2020.
[12] Prachi Jain, Sushant Rathi, Mausam, and Soumen Chakrabarti. Knowledge base completion:
Baseline strikes back (again). CoRR, abs/2005. 00004, 2020.
[13] Seyed Mchran Kazemi and David Poole. Simple embedding for link prediction in knowledge graphs. Advances in neural information processing systems, 31, 2018.
[14] Charles Kemp. Joshua B. Tenenbaum, Thomas L. Griffiths, Takeshi Yamada, and Naonori Ueda. Learning systems of concepts with an infinite relational model. In AAAI, pages 381-388. AAAI Press, 2006.
[15] Byung- Hak Kim, Arvind Yedla, and Henry D Pfister. Imp: A message-passing algorithm for matrix completion. In 2010 6th International Symposium on Turbo Codes & Iterative Information Processing, pages 462-466. IEEE, 2010.
[16] Thomas N Kipf and Max Welling, Semi-supervised classification with graph convolutional 2016.
networks. arXiv preprint
[17] Timothée Lacroix, Nicolas Usunier, and Guillaume Obozinski. Canonical tensor decomposition for knowledge base completion. In ICML, volume 80 of Proceedings of Machine Learning Research, pages 2869-2878 PMLR, 2018.
[18] Ren Li, Yanan Cao, Qiannan Zhu, Guanqun Bi, Fang Fang, Liu, and Qian Li. How does knowledge graph embedding extrapolate to unseen data: semantic evidence view. CoRR, abs/2109. 1800, 2021.
[19] Yujia Li, Daniel Tarlow, Mare Brockschmidt, and Richard S. Zemel. Gated graph sequence neural networks. In ICLR (Poster), 2016.
[20] Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer I Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. Roberta: A robustly optimized BERT pretraining approach. CoRR, abs//100. 16622, 2019.

---

[21] Qingsong Lv, Ming Ding, Qiang Liu, Yuxiang Chen, Wenzheng Feng, Siming He, Chang Zhou, Jianguo Jiang, Yuxiao Dong, and Jie Tang. Are we really making much progress? revisiting, benchmarking and refining heterogeneous graph neural networks. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD '21, page 1150- 1660, New York, NY, USA, 2021. Association for Computing Machinery.
[22]
David JC MacKay. Information theory, inference and learning algorithms. Cambridge university press, 2003.
[23] Deepak Nathani, Jatin Chauhan, Charu Sharma, and Manohar Kaul. Learning attention-based embeddings for relation prediction in knowledge graphs. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 47 10-4723, 2019.
[24] Dai Quoe Nguyen, Tu Dinh Nguyen, Dat Quoc Nguyen, and Dinh Q. Phung. A novel embedding model for knowledge base completion based on convolutional neural network. In NAACL-HLT
(2). pages 327-333, Association for Computational Linguistics, 2018.
[25] Maximilian Nickel, Kevin Murphy, Volker Tresp, and Evgeniy Gabrilovich. A review of relational machine learning for knowledge graphs. Proc. IEEE, 104(1):11-33 2016.
[26] Maximilian Nickel, Lorenzo Rosasco, and Tomaso A. Poggio. Holographic embeddings of knowledge graphs. In AAAI, pages 1955-1961. AAAI Press, 2016.
[27] Maximilian Nickel, Volker Tresp, and Hans-Pete Kriegel. A three-way model for collective learning on multi-relational data. In ICML, pages 809-816. Omnipress, 2011.
[28] Siamak Ravanbakhsh, Barnabás Póczos, and Russell Greiner. Boolean matrix factorization and noisy completion via message passing. In International Conference on Machine Learning, pages 945-954, PMLR, 2016.
[29] Nils Reimers and Iryna Gurevych. Sentence-bert: Sentence embeddings using siamese bert- networks. Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing. Association for Computational Linguistics, 11 2019.
[30] Daniel Ruffinelli, Samuel Broscheit, and Rainer Gemulla. You can teach an old dog new tricks! on training knowledge graph embeddings. In International Conference on Learning Representations, 2020.
[31] Tara Safavi and Danai Koutra. Codex: A comprehensive knowledge graph completion bench- mark. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages
2020.
[32] Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Trans. Neural Networks, 20(1):61 2009.
[33] Michael Schlichtkrull, Thomas N Kipf, Peter Bloem, Rianne Van Den Berg, Ivan Titov, and Max Welling. Modeling relational data with graph convolutional networks. In European semantic web conference, pages 993-607. Springer, 2018.
[34] Yifei Shen, Yongji Wu, Yao Zhang, Caihua Shan, Jun Zhang, Khaled B Letaief, and Dongsheng Li. How powerful is graph convolution for recommendation? arXiv preprint arXiv:2108.00 07567 2021.
[35] Balasubramaniam Srinivasan and Bruno Ribeiro. On the equivalence between positional node embeddings and structural graph representations. In International Conference on Learning Representations, 2020.
[36] Zhiqing Sun, Shikhar Vashishth, Soumya Sanyal, Partha Talukdar, and Yiming Yang. A re-evaluation of knowledge graph completion methods. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 5516-5522, Online, July 2020. Association for Computational Linguistics.
[37] Komal K. Teru, Etienne G. Denis, and William L. Hamilton. Inductive relation prediction by subgraph reasoning. In ICML, volume 119 of Proceedings of Machine Learning Research, pages
PMLR, 2020.
[38] Kristina Toutanova and Danqi Chen. Observed versus latent features for knowledge base and text inference. In Proceedings of the 3rd workshop on continuous vector space models and their compositionality, pages 57-66, 2015.
12

---

[39]
Théo Trouillon, Johannes Welbl, Sebastian Riedel, Eric Gaussier, and Guillaume Bouchard. Complex embeddings for simple link prediction. In Maria Florina Balcan and Kilian Q. Weinberger, editors, Proceedings of The 33rd International Conference on Machine Learning. volume 48 of Proceedings of Machine Learning Research, pages 2071-20800 New York, New York, USA, 20-22 Jun 2016. PMLR.
[40] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liö, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations. 2018.
[41] Petar Veličković. Message passing all the way up, 2022.
[42] Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanie Jegelka. How powerful are graph neural networks? In ICLR. OpenReview.net, 2019.
[43] Xiaoran Xu, Wei Feng. Yunsheng Jiang, Xiaohui Xie. Zhiqing Sun, and Zhi-Hong Deng. Dynamically pruned message passing networks for large-scale knowledge graph reasoning, In International Conference on Learning Representations, 2020.
[44] Xiaoran Xu, Wei Feng, Yunsheng Jiang, Xiaohui Xie, Zhiqing Sun, and Zhi-Hong Deng. Dynamically pruned message passing networks for large-scale knowledge graph reasoning. In ICLR. OpenReview.net, 2020.
[45] Bishan Yang, Wen-tau Yih, Xiaodong He, Jianfeng Gao, and Li Deng. Embedding entities and relations for learning and inference in knowledge bases. In ICLR (Poster), 2015.
[46] Yuning You, Tianlong Chen, Zhangyang Wang, and Yang Shen. L2-gen: Layer-wise and learned efficient training of graph convolutional networks. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 2127-2135, 2020.
[47] Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. GraphSAINT: Graph sampling based inductive learning method. International Conference on Learning Representations, 2020.
[48] Zhao Zhang, Fuzhen Zhuang, Hengshu Zhu, Zhi-Ping Shi, Hui Xiong, and Qing He. Relational graph neural network with hierarchical attention for knowledge graph completion. In AAAI, pages 9612-9619, AAAI Press, 2020.
[49] Zhaocheng Zhu, Zuobai Zhang. Louis-Pascal C. Xhonneux, and Jian Tang. Neural bellman-ford networks: A general graph neural network framework for link prediction. CoRR, abs/2106 05/22106.06935 2021.
[50] Difan Zou, Ziniu Hu, Yewen Wang, Song Jiang, Yizhou Sun, and Quanquan Gu. Few-shot representation learning for out-of- vocaablayy words. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems, NeurIPS. 2019.
13


Reviews:
[{"review_id": "hsVbIdRCaJA", "reviewer": "Reviewer_jDqr", "summary": "This work proposes ReFactor GNNs that makes use of the message passing property of GNNs in order to cast he hugely successful factorization based embedding techniques, here DistMult, as a GNN. The idea is to formulate gradient descent in factorization based models as message passing in GNNs. The experimental section shows that the proposed model works well on different knowledge base completion tasks.", "questions": "In addition to the above 2 points raised in weaknesses, I have a few more questions:\n\n1. What is the running time of the proposed ReFactor GNNs?\n\n2. It would be great to have some comment on the expressiveness of the ReFACTOR GNNs.", "limitations": "I do not foresee any potential negative societal impact of this work.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. The idea is simple and quite intuitive and yet very clever at the same time. It's great to see this connection between DistMult's and GNNs in a more formal fashion.\n\n2. The paper is written nicely and is easily understandable.\n\nWeaknesses:\n\n1. The fact that the results presented are for $L=\\infty$ after explicitly saying that they \"periodically clear the node state cache every L full batches\" seems a bit strange. Is there any reason for not presenting resulting for L other than $\\infty$?\n\n2. There should be some comparisons on the link prediction task especially with RGCN. \n\nI have done an emergency review for this paper and thus have lowered my confidence. Overall, I like the idea behind the paper and would like to hear more from the authors in the rebuttal. My major concern remains the experimental part of the paper.\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "WVvFgfIodP2", "reviewer": "Reviewer_M1H8", "summary": "**DISCLAIMER: This is not my area of expertise, and this paper is very specific and quite technical. Nevertheless, the program chairs asked to review the submission based on my experience and broad knowledge anyway.  I do try.**\n\nThis paper proposes a new approach to the problem of knowledge graph completion. This problem resisted recent advances in geometric deep learning and the best approaches so far are still based on factorization-based models (FB).\nHere the authors note that FB models can be seen as GNNs \"by reformulating gradient descent on node embeddings using message-passing primitives\" and use this idea to build a new hybrid model called Refactor GNN, that achieves the performance of FB models using 1/10 parameters, sometimes even fixing a new state of the art.\n", "questions": "I do not have relevant questions to ask. My score is borderline because I am not able to judge too many aspects of this paper. ", "limitations": "There seems to be adequate discussion of the limitations, but I can't make an assessment.\n", "rating": 5, "confidence": 1, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Originality\nI am not able to assess whether these ideas were already existing under a different name. In particular I am not able to judge the novelty with respect to [28].\n\n### Quality\nAs far as I can tell, this work is of good quality. I appreciated the uncertainty estimated using different random seeds reported in the appendix. I peeked at the code and it seems well organized, even if mostly bare of comments.\n\n### Clarity\nThis paper is very specific and quite technical. The background section was easy to follow, which is a good thing, then for a non-expert it becomes quite harsh.\n\n### Significance\n\nSuppose I have to bet on how many citations this paper will receive in the next five years.\n\nFollowing the stats of accepted papers at Neurips 2014 tracked in 2019 (as can be found at https://github.com/rubai5/MLcites) a bookmaker could give the following betting odds:\n\n- A: Between 0 and 5 cits, proposed at 10/1.\n- B: Between 5 and 25 cits, proposed at 3/1.\n- C: Between 25 and 75 cits, proposed at 3/1.\n- D: More than 75 cits, proposed at 6/1.\n\nI would bet my money on A, maybe adjusting to B given the higher rate of citations in the NLP field. Actually this bet is based on my broad knowledge, and should be understood as a bet on the doom of knowledge graphs (KGs). The problem discussed here is very specific to KGs, and to me it seems that many use-cases of KGs were recently robbed by large language models, a short time ago enriched also with explicit memory and retrieval methods [RETRO].\n\n\n[RETRO] Borgeaud, Sebastian, et al. \"Improving language models by retrieving from trillions of tokens.\" arXiv preprint arXiv:2112.04426 (2021).  \n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "IDW6TTXB5Ep", "reviewer": "Reviewer_rRLn", "summary": "[Update after Rebuttal: Increased confidence, Accept]\n\n[REMARK: This is an emergency review, that is, the reviewer did neither select autonomously into this paper out of interest/expertise nor was the reviewer granted with sufficient time (with respect to standard time frames) to appropriately provide a review. Please take the review with caution, the confidence level will be adjusted accordingly.]\n\nThe presented paper proposes a bridge between the otherwise disjoint model classes of factorization-based models (FM) and the currently popular graph neural networks (GNN). The motivation for this lies in the fact that the success stories of said models remains disjoint as well i.e., GNNs are successful widely but in tasks such as multi-relational link prediction they fall short to FMs. The authors bridge aforementioned gap by providing a reformulation (Theorem 3.1) that shows how one can identify Message Passing a la GNN within FM. To corroborate on their theoretical result, the authors provide a first model living within the identified (or expected) spectrum of FM-GNN models and give an empirical account of said model (referred to as ReFactor GNN) showing that the addendum to plain GNN indeed improves the shortcomings.", "questions": "The questions are derived mostly from aspects mentioned in the \"Weaknesses\" section. I'd invite the authors to answer these questions to overcome the observed weaknesses for improving the paper to ultimately increase the chances of both contribution and visibility to the community. The list of questions is unordered and they range in quality and speed of expected answer (some are minor, quickly answerable whereas others are more fundamental, crucial, maybe difficult to answer):\n* How could we classify/analyze the spectrum of FM-GNN models?\n* In which way do the design choices (DistMult, optimizer etc.) affect the key result?\n* What type of guarantees could we possibly give to ReFactorGNN?", "limitations": "No contradictions or any sort of relevant mistake have been detected in the paper. The clarity of the paper is a clear advantage, even if (likely unavoidable) dense at times. Existing bodies of work are being referenced accordingly throughout the paper.\n\nSufficient details for reproduction are being provided. Also with actual code (however, the code was not reviewed). All key assumptions for the method are being pointed out explicitly. Societal impact is not being discussed explicitly, however, this was not necessary to begin with IMHO.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\nStudying the shortcomings of GNN in advent of their rise as dominant model class for structured-input predictions is an important step towards improving the model class to cope with more classical tasks such as knowledge graph completion. Bridging the gap to other existing model classes such as FMs, helps to broaden the understanding of what qualitative differences between our modelling choices of interest exist. It also enables (a foundation to) compilation back-and-forth and therefore allows for flexible use of existing tools. The presentation of the ideas is detailed and complimented by several modalities including the rigorous mathematization and a key figure. The empirical results suggest a sensible view on FM-GNNs and the idea of a spectrum of such models (which might have been identified by this work) leaves room for further investigations.\n\n**Weaknesses**\n\nIMHO there is only so much a contribution can propose and certainly the key results presented should not be deluted, therefore, the following weaknesses are rather extensions to be considered upon the existing work. Considering GNN literature, several theoretical findings have been made regarding their expressivity, tractability, etc. and in a similar fashion analyzing the presented initial FM-GNN, ReFactor GNN, would benefit our understanding of where to place the model within the zoo of existing methods. Furthermore, the focus has been on DistMult but also on optimizers such as SGD or AdaGrad (as also explicitly mentioned by the authors), yet, there exists the impression of more general schemes (the FM-GNN spectrum) and thereby it would be sensible to already provide a disclaimer on how the design choices already (strongly or weakly) influence the subsequent results.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept