# Precision Machine Learning

Eric J. Michaud<EMAIL_ADDRESS>Department of Physics, MIT  NSF AI Institute
for AI and Fundamental Interactions  Ziming Liu  Department of Physics, MIT
NSF AI Institute for AI and Fundamental Interactions  Max Tegmark  Department
of Physics, MIT  NSF AI Institute for AI and Fundamental Interactions  Center
for Brains, Minds and Machines

(October 24, 2022)

###### Abstract

We explore unique considerations involved in fitting ML models to data with
very high precision, as is often required for science applications. We
empirically compare various function approximation methods and study how they
_scale_ with increasing parameters and data. We find that neural networks can
often outperform classical approximation methods on high-dimensional examples,
by auto-discovering and exploiting modular structures therein. However, neural
networks trained with common optimizers are less powerful for low-dimensional
cases, which motivates us to study the unique properties of neural network
loss landscapes and the corresponding optimization challenges that arise in
the high precision regime. To address the optimization issue in low
dimensions, we develop training tricks which enable us to train neural
networks to extremely low loss, close to the limits allowed by numerical
precision.

##  Introduction

Most machine learning practitioners do not need to fit their data with much
precision. When applying machine learning to traditional AI tasks such as in
computer vision or natural language processing, one typically does not desire
to bring training loss all the way down to exactly zero, in part because
training loss is just a proxy for some other performance measure like accuracy
that one actually cares about, or because there is intrinsic uncertainty which
makes perfect prediction impossible, e.g., for language modeling. Accordingly,
to save memory and speed up computation, much work has gone into _reducing_
the numerical precision used in models without sacrificing model performance
much [1, 2, 3]. However, modern machine learning methods, and deep neural
networks in particular, are now increasingly being applied to science
problems, for which being able to fit models _very_ precisely to (high-
quality) data can be important. Small absolute changes in loss can make a big
difference, e.g., for the symbolic regression task of identifying an exact
formula from data.

It is therefore timely to consider what, if any, unique considerations arise
when attempting to fit ML models very precisely to data, a regime we call
Precision Machine Learning (PML). How does pursuit of precision affect choice
of method? How does optimization change in the high-precision regime? Do
otherwise-obscure properties of model expressivity or optimization come into
focus when one cares a great deal about precision? In this paper, we explore
these basic questions.

###  Problem Setting

We study regression in the setting of supervised learning, in particular the
task of fitting functions $f:\mathbb{R}^{d}\rightarrow\mathbb{R}$ to a dataset
of $D=\\{(\vec{x}_{i},y_{i}=f(\vec{x}_{i})\\}_{i=1}^{|D|}$. In this work, we
mostly restrict our focus to functions $f$ which are given by symbolic
formulas. Such functions are appropriate for our purpose, of studying
precision machine learning for science applications, since they (1) are
ubiquitous in science, fundamental to many fields’ descriptions of nature, (2)
are precise, not introducing any intrinsic noise in the data, making extreme
precision possible, and (3) often have interesting structure such as
_modularity_ that sufficiently clever ML methods should be able to discover
and exploit. We use a dataset of symbolic formulas from [4], collected from
the Feynman Lectures on Physics [5].

Just how closely can we expect to fit models to data? When comparing a model
prediction $f_{\theta}(\vec{x}_{i})$ to a data point $y_{i}$, the smallest
nonzero difference allowed is determined by the numerical precision used. IEEE
754 64-bit floats [6] have 52 mantissa bits, so if $y_{i}$ and
$f_{\theta}(\vec{x}_{i})$ are of order unity, then the smallest nonzero
difference between them is $\epsilon_{0}=2^{-52}\sim 10^{-16}$. We should not
expect to achieve _relative RMSE loss_ below $10^{-16}$, where relative RMSE
loss, on a dataset $D$, is:

$\ell_{\text{rms}}\equiv\left(\frac{\sum_{i=1}^{|D|}|f_{\theta}(\vec{x}_{i})-y_{i}|^{2}}{\sum_{i=1}^{|D|}y_{i}^{2}}\right)^{\frac{1}{2}}=\frac{|f_{\theta}(\vec{x}_{i})-y_{i}|_{\text{rms}}}{y_{\text{rms}}}.$
(1)

In practice, precision can be bottlenecked earlier by the computations
performed within the model $f_{\theta}$. The task of precision machine
learning is to try to push the loss down many orders of magnitude, driving
$\ell_{\text{rms}}$ as close as possible to the numerical noise floor
$\epsilon_{0}$.

###  Decomposition of Loss

One can similarly define _relative MSE loss_
$\ell_{\text{mse}}\equiv\ell_{\text{rms}}^{2}$, as well as non-relative
(standard) MSE loss
$L_{\text{mse}}(f)=\frac{1}{|D|}\sum_{i=1}^{D}(f_{\theta}(\vec{x}_{i})-y_{i})^{2}$,
and $L_{\text{rms}}=\sqrt{L_{\text{mse}}}$. Minimizing
$\ell_{\text{rms}},\ell_{\text{mse}},L_{\text{rms}},L_{\text{mse}}$ are
equivalent up to numerical errors. Note that (relative) expected loss can be
defined on a probability distribution
$\mathds{P}_{(\mathbb{R}^{d},\mathbb{R})}$, like so:

$\ell^{\mathds{P}}_{\text{rms}}=\left(\frac{\mathop{\mathbb{E}}_{(\vec{x},y)\sim\mathds{P}}[(f_{\theta}(\vec{x})-y)^{2}]}{\mathop{\mathbb{E}}_{(\vec{x},y)\sim\mathds{P}}[y^{2}]}\right)^{\frac{1}{2}}.$
(2)

When we wish to emphasize the distinction between loss on a dataset $D$
(empirical loss) and a distribution $\mathds{P}$ (expected loss), we write
$\ell^{D}$ and $\ell^{\mathds{P}}$. In the spirit of [7], we find it useful to
decompose sources of error into different sources, which we term _optimization
error_ , _sampling luck_ , the _generalization gap_ , and _architecture
error_. A given model architecture parametrizes a set of expressible functions
$\mathcal{H}$. One can define three functions of interest within
$\mathcal{H}$:

$f^{\text{best}}_{\mathds{P}}\equiv\underset{f\in\mathcal{H}}{\operatorname*{argmin}}\\{\ell^{\mathds{P}}(f)\\},$
(3)

the best model on the expected loss $\ell^{\mathds{P}}$,

$f^{\text{best}}_{D}\equiv\underset{f\in\mathcal{H}}{\operatorname*{argmin}}\\{\ell^{D}(f)\\},$
(4)

the best model on the empirical loss $\ell^{D}$, and

$f_{D}^{\text{used}}=\mathcal{A}(\mathcal{H},D,L),$ (5)

the model found by a given learning algorithm $\mathcal{A}$ which performs
possibly imperfect optimization to minimize empirical loss $L$ on $D$.

We can therefore decompose the empirical loss as follows:

$\ell^{D}(f^{\text{used}}_{D})=\underbrace{[\ell^{D}(f^{\text{used}}_{D})-\ell^{D}(f^{\text{best}}_{D})]}_{\text{optimization
error}}+\underbrace{[\ell^{D}(f^{\text{best}}_{D})-\ell^{\mathds{P}}(f^{\text{best}}_{D})]}_{\text{sampling
luck}}+\underbrace{[\ell^{\mathds{P}}(f^{\text{best}}_{D})-\ell^{\mathds{P}}(f^{\text{best}}_{\mathbb{P}})]}_{\text{generalization
gap}}+\underbrace{\ell^{\mathds{P}}(f^{\text{best}}_{\mathbb{P}})}_{\text{architecture
error}},$ (6)

where all terms are positive except possibly the _sampling luck_ , which is
zero on average, has a standard deviation shrinking with data size $|D|$
according to the Poisson scaling $|D|^{-1/2}$, and will be ignored in the
present paper. The generalization gap has been extensively studied in prior
work, so this paper will focus exclusively on the optimization error and the
architecture error.

To summarize: the architecture error is the best possible performance that a
given architecture can achieve on the task, the generalization gap is the
difference between the optimal performance on the training set $D$ and the
architecture error, and the optimization error is the error introduced by
imperfect optimization – the difference between the error on the training set
found by imperfect optimization and the optimal error on the training set.
When comparing methods and studying their scaling, it useful to ask which of
these error sources dominate. We will see that both architecture error and
optimization error can be quite important in the high-precision regime, as we
will elaborate on in Sections 2-3 and Section 4, respectively.

###  Importance of Scaling Exponents

In this work, one property that we focus on is how methods _scale_ as we
increase parameters or training data. This builds on a recent body of work on
scaling laws in deep learning [8, 9, 10, 11, 12, 13, 14, 15, 16] which has
found that, on many tasks, loss decreases predictably as a power-law in the
number of model parameters and amount of training data. Attempting to
understand this scaling behavior, [17, 18] argue that in some regimes, cross-
entropy and MSE loss should scale as $N^{-\alpha}$, where $\alpha\gtrsim 4/d$,
$N$ is the number of model parameters, and $d$ is the _intrinsic
dimensionality_ of the _data manifold_ of the task.

Consider the problem of approximating some analytic function
${f:[0,1]^{d}\rightarrow\mathbb{R}}$ with some function which is a piecewise
$n$-degree polynomial. If one partitions a hypercube in $\mathbb{R}^{d}$ into
regions of length $\epsilon$ and approximates $f$ as a $n$-degree polynomial
in each region (requiring $N=\mathcal{O}(1/\epsilon^{d})$ parameters),
absolute error in each region will be $\mathcal{O}(\epsilon^{n+1})$ (given by
the degree-$(n+1)$ term in the Taylor expansion of $f$) and so absolute error
scales as $N^{-\frac{n+1}{d}}$. If neural networks use ReLU activations, they
are piecewise linear, $n=1$ and so we may expect $\ell_{\text{rmse}}(N)\propto
N^{-\frac{2}{d}}$. However, in line with [17], we find that ReLU NNs often
scale as if the problem was lower-dimensional than the input dimension, though
we suggest that this is a result of the computational modularity of the
problems in our setting, rather than a matter of low intrinsic dimensionality
(though these perspectives are related).

If one desires very low loss, then the exponent $\alpha$, the rate at which
methods approach their best possible performance111The best possible
performance can be determined either by precision limits or by noise intrinsic
to the problem, such as intrinsic entropy of natural language. matters a great
deal. Kaplan et al. [17] note that $4/d$ is merely a lower-bound on the
scaling rate – we consider ways that neural networks can improve on this
bound. Understanding model scaling is key to understanding the feasibility of
achieving high precision.

###  Organization

This paper is organized as follows: In Section 2 we discuss piecewise linear
approximation methods, comparing ReLU networks with linear simplex
interpolation. We find that neural networks can sometimes outperform simplex
interpolation, and suggest that they do this by discovering modular structure
in the data. In Section 3 we discuss nonlinear methods, including neural
networks with nonlinear activation functions. In Section 4 we discuss the
optimization challenges of high-precision neural network training – how
optimization difficulties can often make total error far worse than the limits
of what architecture error allows. We attempt to develop optimization methods
for overcoming these problems and describe their limitations, then conclude in
Section 5.

(a)

(b)

Figure 1: In 1(a) (top), we show the solutions learned by a ReLU network and
linear simplex interpolation on the 1D problem $y=\cos(2x)$. In 1(b) (bottom),
we visualize linear regions for a ReLU network, trained on unnormalized data
(left) and normalized data (center), as well as linear simplex interpolation
(right) on the 2D problem $z=xy$. In general, we find that normalizing data to
have zero mean and unit variance improves network performance, but that linear
simplex interpolation outperforms neural networks on low-dimensional problems
by better vertex placement.

##  Piecewise Linear Methods

Figure 2: Scaling of linear simplex interpolation versus ReLU NNs. While
simplex interpolation scales very predictably as $N^{-2/d}$, where $d$ is the
input dimension, we find that NNs sometimes scale better (at least in early
regimes) as $N^{-2/{d^{*}}}$, where $d^{*}=2$, on high dimensional problems.
Figure 3: ReLU neural networks are seen to initially scale roughly as if they
were modular. Networks with enforced modularity (dark blue and red, dashed
line), with architecture depicted on the right, perform and scale similarly,
though slightly better, than standard dense MLPs of the same depth (light blue
and red).

We first consider approximation methods which provide a piecewise linear fit
to data. We focus on two such methods: linear simplex interpolation and neural
networks with ReLU activations.

To review, linear simplex interpolation works as follows: given our dataset of
$|D|$ input-output pairs $\\{(\vec{x}_{i},y_{i})\\}_{i=1}^{|D|}$, linear
simplex interpolation first computes a Delaunay triangulation from
$\vec{x}_{1},\ldots,\vec{x}_{|D|}$ in the input space $\mathbb{R}^{d}$,
partitioning the space into a collection of $d$-simplices, each with $d+1$
vertices, whose union is the convex hull of the input points. Since $d+1$
points determine a linear (affine) function
$\mathbb{R}^{d}\rightarrow\mathbb{R}$, the function $f$ can be approximated
within each $d$-simplex as the unique linear function given by the value of
the function $f$ at the vertices. This gives a piecewise linear function on
the convex hull of the training points. Linear simplex interpolation needs to
store $N=|D|(d+1)$ parameters: $|D|d$ values for the vertices $\vec{x}_{i}$,
and $|D|$ values for the corresponding function values $y_{i}$.

Neural networks with ReLU activations also give a piecewise linear fit
$f_{\theta}$. We consider only fully-connected feedforward networks, a.k.a.
multilayer perceptrons (MLPs). Such networks consist of a sequence of
alternating affine transformations $T:\vec{x}\mapsto W\vec{x}+b$ and element-
wise nonlinearities $\sigma(\vec{x})_{i}=\sigma(\vec{x}_{i})$ for an
activation function $\sigma:\mathbb{R}\rightarrow\mathbb{R}$:

$f_{\theta}=T_{k+1}\circ\sigma\circ T_{k}\circ\cdots\circ
T_{2}\circ\sigma\circ T_{1}$

Following [19], we define the depth of the network as the number of affine
transformations in the network, which is one greater than the number of hidden
layers $k$. As shown in [19], any piecewise linear function on
$\mathbb{R}^{d}$ can be represented by a sufficiently wide ReLU NN with at
most $\lceil\log_{2}(d+1)\rceil+1$ depth. Therefore, sufficiently wide and
deep networks are able to exactly express functions given by linear simplex
interpolation. A natural question then is: given the same amount of data and
parameters, how do the two methods compare? We find that simplex interpolation
performs better on 1D and 2D problems, but that neural networks can outperform
simplex interpolation on higher-dimensional problems. So although simplex
interpolation and ReLU NNs both parametrize the same function class (piecewise
linear functions), their performance can differ significantly in practice.

In our experiments, we use the implementation of simplex interpolation from
SciPy [20]. When training neural networks, we use the Adam optimizer [21] with
a learning rate of $10^{-3}$, and train for 20k steps. We use a batch size of
$\min(|D|,10^{4})$. While we report loss using RMSE, we train using MSE loss.
Training points are sampled uniformly from intervals specified by the AI
Feynman dataset [4] (typically $[1,5]\subset\mathbb{R}$ for each input), but
when training neural networks, we normalize the input points [22] so that they
have zero mean and unit variance along each dimension. We estimate test loss
on datasets of 30k samples.222Project code can be found at
https://github.com/ejmichaud/precision-ml.

In Figure 1, we show for 1D and 2D problems the linear regions given both by
simplex interpolation and by neural networks trained a with comparable number
of parameters . For 2D problems, Figure 1(b) illustrates the importance of
normalizing input data for ReLU networks. We see that there is a far higher
density of linear regions around the data when input data is normalized, which
leads to better performance. Neural networks, with the same number of
parameters and trained with the same low-dimensional data, often have fewer
linear regions than simplex interpolation.

In Figure 2, we show how the precision of linear simplex interpolation and
neural networks scale empirically. Since simplex interpolation is a piecewise
linear method, from the discussion in Section 1.3, we expect its RMSE error to
scale as $N^{-2/d}$, and find that this indeed holds333Scaling as $D^{-2/d}$
only holds when the model is evaluated on points not too close to the boundary
of the training set. At the boundary, simplices are sometimes quite large,
leading to a poor approximation of the target function close to the boundary,
large errors, and worse scaling. In our experiments, we therefore compute test
error only for points at least 10% (of the width of the training set in each
dimension) from the boundary of the training set.. To provide a fair
comparison with simplex interpolation when evaluating neural networks on a
dataset of size $D$, we give it the same number of parameters $N=|D|(d+1)$.
From Figure 2, we see that simplex interpolation outperforms neural networks
on low dimensional problems but that neural networks do better on higher-
dimensional problems.

For the 1D example in Figure 2 (top left), we know that the amount by which
the neural networks under-perform simplex interpolation is entirely due to
optimization error. This is because any 1D piecewise linear function $f(x)$
with $m$ corners at $x_{1},...,x_{m}$ can trivially be can trivially be
written as a linear combination of $m$ functions ReLU$(x-x_{i})$.

Interestingly, we see that, at least early in the scaling curves, neural
networks usually appear to scale not as $N^{-2/d}$, but rather as
$N^{-2/d^{*}}$ where $d^{*}$ is the _maximum arity_ of the problem. Symbolic
expressions typically have modular structure, and can be viewed as a series of
computations each acting on fewer variables than are in the whole expression.
For instance, for the expression $x_{1}\cdot x_{2}\cdot x_{3}$, one can
decompose the operation as a multiplication between $x_{1}$ and $x_{2}$, and
then a second multiplication between the result and $x_{3}$. At each stage,
only two variables are operated on, so the maximum arity of the computational
graph is $2$. If neural networks can discover this modularity, they can scale
as $N^{-2/d^{*}}$ where $d^{*}=2$, and outperform simplex interpolation when
$d>2$.

To test this idea that better neural network scaling comes from exploiting
modularity, we train networks where we hard-code the modularity of the problem
into the architecture, as depicted in Figure 3. Figure 3 indeed reveals how
models for which we enforce the modularity of the problem perform and scale
similarly to same-depth dense neural networks without modularity enforced. A
modular architecture can be created from a dense one by forcing weight
matrices to be block-diagonal (where we do not count off-diagonal entries
towards the number of model parameters), but in practice we create modular
architectures by creating a separate MLP for each node in the symbolic
expression computation graph and connecting them together in accordance with
the computation graph. See the diagrams in Figure 3 for an illustration of the
modular architecture. In Figure 3, we plot modular and dense network
performance against number of model parameters, but we also find that holding
width constant, rather than number of parameters, modular networks still
slightly outperform their dense counterparts. For instance, depth-6 width-100
modular networks outperform dense networks of the same width and depth,
despite dense networks having $\approx$2.5x fewer parameters. Such “less is
more” results are to be expected if the optimal architecture is in fact
modular, in which case a fully connected architecture wastes resources
training large numbers of parameters that should be zero.

The fact that neural networks can scale as if the problem dimension was the
maximum arity of the computational graph, rather than the input dimension, is
similar to, although more general than, a result from [17]. They found that if
the problem “data manifold” is a product $X_{1}\times X_{2}\times\cdots\times
X_{n}$, and the prediction problem decomposes as $F(x)=\sum_{i}f_{i}(x_{i})$,
then the effective dimension is given by the maximum dimension of the
manifolds $X_{1},\ldots,X_{n}$. Successfully scaling in the maximum arity of
the computation graph requires the network to learn a particular
_compositional_ structure consisting of modules which are sparse, acting on a
lower number of variables. This relates to a literature beginning to emerge on
compositional sparsity in deep learning [23, 24].

##  Nonlinear Methods

Figure 4: Interpolation methods, both linear and nonlinear, on 2D and 3D
problems, seen to approximately scale as $D^{-(n+1)/d}$ where $n$ is the order
of the polynomial spline, $d$ is the input dimension.

We now turn our attention to approximations methods that are thoroughly
nonlinear (as opposed to piecewise linear). As discussed in the introduction,
methods approximating the target function $f$ by a piecewise polynomial have a
scaling exponent $\alpha=\frac{n+1}{d}$ where $n$ is the degree of the
polynomial.

In Figure 4, we plot the performance of approximation methods which are
piecewise polynomial, for 1D, 2D and 3D problems. For 1D and 2D problems, we
use splines of varying order. For 3D problems, we use the cubic spline
interpolation method of [25]. We see empirically that these methods have
scaling exponent $\alpha=(n+1)/d$. If the order of the spline interpolator is
high enough, and the dimension low enough, we see that relative RMSE loss
levels out at $\epsilon_{0}\approx 10^{-16}$ at the precision limit.
Unfortunately, a basic limitation of these methods is that they are limited to
low-dimensional problems.

There are relatively few options for high-dimensional nonlinear
interpolation.444One method, which we have not tested, is radial basis
function interpolation. A particularly interesting parametrization of
nonlinear functions is given by neural networks with nonlinear activation
functions (and not piecewise linear like ReLUs). In Figure 5, we show how
neural networks with tanh activations scale in increasing width. We observe
that on some problems, they do better than the ideal scaling achievable with
linear methods (shown as a green dashed line). However, in our experiments,
they can sometimes scale worse, perhaps the result of imperfect optimization.
Also, we find that scaling is typically not nearly as clean as a power law as
it was for ReLU networks.

For some problems, one can show theoretically that architecture error can be
made arbitrarily low, and that the loss is due entirely to optimization error
and the generalization gap. As shown in [26], a two-layer neural network with
only four hidden units can perform multiplication between two real numbers,
provided that a twice-differentiable activation function is used. See Figure
6(b) for a diagram of such a network, taken from [26]. Note that this network
becomes more accurate in the limit that some of its parameters become very
small and others become very large. This result, that small neural networks
can express multiplication arbitrarily well, implies that neural network
architecture error is effectively zero for some problems. However, actually
_learning_ this multiplication circuit in practice is challenging since it
involves some network parameters _diverging_ $\rightarrow\infty$ while others
$\rightarrow 0$ in a precise ratio. This means that for some tasks, neural
network performance is mainly limited not by architecture error, but by
optimization error.

Indeed, on some problems, a failure to achieve high precision can be blamed
entirely on the optimization error. In Figure 6(a), we show neural network
scaling on the equation
$f(x_{1},x_{2},x_{3},y_{1},y_{2},y_{3})=x_{1}y_{1}+x_{2}y_{2}+x_{3}y_{3}$. For
this problem, a 2-layer network with 12 hidden units (implementing three
multiplications in parallel, with their results added in the last layer) can
achieve $\approx 0$ architecture error. Yet we see a failure to get anywhere
near that architecture error or the noise floor set by machine precision.
Instead, as one scales up the network size on this task, we see that despite
architecture error abruptly dropping to zero early on, the actually attained
loss continues to scales down smoothly.

It is therefore important to analyze the problem of optimization for high
precision, which we do in the next section.

Figure 5: Scaling of linear simplex interpolation vs tanh NNs. We also plot
ReLU NN performance as a dotted line for comparison. While simplex
interpolation scales very predictably as $N^{-2/d}$, where $d$ is the input
dimension, tanh NN scaling is much messier.

(a)

(b)

Figure 6: (a) Scaling of neural networks on a target function which can be
arbitrarily closely approximated by a network of finite width. (b) diagram
from [26] showing how a 4-neuron network can implement multiplication
arbitrarily well. Therefore a depth-2 network of width at least 12 has an
architecture error at the machine precision limit, yet optimization in
practice does not discover solutions within at least 10 orders of magnitude of
the precision limit.

##  Optimization

As seen above, when deep neural networks are trained with standard optimizers,
they can produce significant optimization error, i.e. fail to find the best
approximation. In this section, we discuss the difficulty of optimization in
the high-precision regime and explore a few tricks for improving neural
network training.

###  Properties of Loss Landscape

To understand the difficulty of optimizing in the high-precision regime, we
attempt to understand the local geometry of the loss landscape at low loss. In
particular, we compute the Hessian of the loss and study its eigenvalues. In
Figure 7, we plot the spectrum of the Hessian, along with the magnitude of the
gradient projected onto each of the corresponding eigenvectors, at a point in
the loss landscape found by training with the Adam optimizer for 30k steps in
a teacher-student setup. The teacher is a depth-3, width-3 tanh MLP and the
student is a depth-3, width-40 tanh MLP. In line with [27, 28, 29], we find
that at low loss, the loss landscape has a top cluster of directions of high
curvature (relatively large positive eigenvalues) and a bulk of directions of
very low curvature. Furthermore, the gradient tends to point most strongly in
directions of higher curvature, and has very little projection onto directions
of low curvature magnitude.

Figure 7: Eigenvalues (dark green) of the loss landscape Hessian (MSE loss)
after training with the Adam optimizer, along with the magnitude of the
gradient’s projection onto each corresponding eigenvector (thin red line). We
see a cluster of top eigenvalues and a bulk of near-zero eigenvalues. The
gradient (thin jagged red curve) points mostly in directions of high-
curvature.

The basic picture emerging from this analysis is that of a canyon, i.e., a
very narrow, very long valley around a low-loss minimum. The valley has steep
walls in high-curvature directions and a long basin in low-curvature
directions. Further reducing loss in this environment requires either (1)
taking very precisely-sized steps along high-curvature directions to find the
exact middle of the canyon or (2) moving along the canyon in low-curvature
directions instead, almost orthogonally to the gradient. In this landscape,
typical first-order optimizers used in deep learning may struggle to do either
of these things, except perhaps if learning rates are chosen extremely
carefully. Instead, they tend to waste time rapidly oscillating between the
side walls of the canyon.

###  Optimization Tricks For Reducing Optimization Error

How can we successfully optimize in such a poorly-conditioned, low-loss
regime? We first find that switching from first-order optimizers like Adam to
second-order optimizers like BFGS [30] can improve RMSE loss by multiple
orders of magnitude. Second-order methods often both (1) employ line searches,
and (2) search in directions not strongly aligned with the gradient, allowing
optimization to progress within low-curvature subspaces. However, methods like
BFGS are eventually bottlenecked by numerical precision limitations. To
further lower loss, we tested the following two methods:

#### Low-Curvature Subspace Optimization

We find that by restricting our optimization to low-curvature subspaces, we
can further decrease loss past the point where loss of precision prevented
BFGS from taking further steps. Our method has a single hyperparameter $\tau$.
The method is as follows: let $g=\nabla_{\theta}\mathcal{L}$ be the gradient
and $H$ be the Hessian of the loss. Denote an eigenvector-eigenvalue pair of
$H$ by $(e_{i},\lambda_{i})$. Instead of stepping in the direction $-g$, we
instead compute $\hat{g}=\sum_{i:\lambda_{i}<\tau}e_{i}(e_{i}\cdot g)$.
Essentially, we just project $g$ onto the subspace spanned by eigenvalues of
$e_{i}$ such that $\lambda_{i}<\tau$. We then perform a line search to
minimize loss along the direction $-\hat{g}$, and repeat the process. Note
that this requires computing eigenvectors and eigenvalues for the whole
Hessian $H$.

Figure 8: Comparison of Adam with BFGS + low-curvature subspace training +
boosting. Using second-order methods like BFGS, but especially using boosting,
leads to an improvement of many orders of magnitude over just training with
Adam. Target functions are a teacher network (top) and a symbolic equation
(bottom).

#### Boosting: staged training of neural networks

Instead of training a full network to fit the target $f$, one can train two
networks $f^{(1)}_{\theta_{1}},f^{(2)}_{\theta_{2}}$ sequentially: first train
$f^{(1)}_{\theta_{1}}$ to fit $f$, then train $f^{(2)}_{\theta_{2}}$ to fit
the residual $\frac{f-f^{(1)}_{\theta_{1}}}{c}$, where $c\ll 1$ normalizes the
residual to be of order unity. One can then combine the two networks into a
single model $f(x)\approx f^{(1)}_{\theta_{1}}(x)+cf^{(2)}_{\theta_{2}}(x)$.
If networks $f^{(1)}_{\theta_{1}},f^{(2)}_{\theta_{2}}$ have widths
$w_{1},w_{2}$ respectively, then they can be combined into one network of
width $w_{1},w_{2}$, with block-diagonal weight matrices, and where the
parameters of the last layer of $f^{(2)}_{\theta_{2}}$ are scaled down by $c$.

We find that, for low-dimensional problems, we can achieve substantially lower
loss with these techniques. We use the following setup: we train width-40
depth-3 tanh MLPs to fit single-variable polynomials with the BFGS optimizer
on MSE loss. The SciPy [20] BFGS implementation achieves $\leavevmode\nobreak\
10^{-7}$ RMSE loss before precision loss prevents further iterations.
Subsequently using low-curvature subspace training with a threshold
$\tau=10^{-16}$ can further lower RMSE loss a factor of over 2x. On similar
low-dimensional problems, as shown in Figure 8, applying boosting, training a
second network with BFGS on the residual of the first can lower RMSE loss
further by 5-6 orders of magnitude. In Figure 8, we compare training runs with
these tricks to runs with the Adam optimizer for a variety of learning rates.
For our Adam training runs, we use width-40 tanh MLPs. When training with
boosting, we train a width-20 network for $f^{(1)}_{\theta_{1}}$ and a
width-20 network for $f^{(2)}_{\theta_{2}}$, for a combined width of 40. We
also plot a width-40 network trained solely with BFGS for comparison. We find,
unsurprisingly, that BFGS significantly outperforms Adam. With our tricks,
particularly boosting, we can sometimes outperform even well-tuned Adam by 8
orders of magnitude, driving RMSE loss down to $\approx 10^{-14}$, close to
the machine precision limit.

Figure 9: Comparison of Adam with BFGS + low-curvature subspace training +
boosting, for a 2D problem (top) and a 6D problem (bottom), the equation we
studied in Figure 6(a). As we increase dimension, the optimization tricks we
tried in this work show diminishing benefits.

###  Limitations and Outlook

The techniques we described above are not a silver bullet for fitting neural
networks to any data with high precision. Firstly, second-order optimizers
like BFGS scale poorly with the number of model parameters $N$ (since the
Hessian is an $N\times N$ matrix), limiting their applicability to small
models. Also, we find that the gains from boosting diminish quickly as the
input dimension of the problem grows. In Figure 9, we see that on the
6-dimensional problem discussed earlier (Figure 6(a)), BFGS + boosting
achieves only about a 2-order of magnitude improvement, bringing the RMSE loss
from $10^{-2}$ to $10^{-4}$.

While boosting does not help much for high-dimensional problems, its success
on low-dimensional problems is still noteworthy. By training two parts of a
neural network separately and sequentially, we were able to dramatically
improve performance. This suggests that perhaps there are other methods, not
yet explored, for training and assembling neural networks in nonstandard ways
to achieve dramatically better precision. The solutions found with boosting,
where some network weights are at a much smaller scale than others, are not
likely to be found with typical training. An interesting avenue for future
work would be exploring new initialization schemes, or other ways of training
networks sequentially, to discover better solutions in underexplored regions
of parameter space.

##  Conclusions

We have studied the problem of fitting scientific data with a variety of
approximation methods, analyzing sources of error and their scaling.

  * •

Linear Simplex Interpolation provides a piecewise linear fit to data, with
RMSE loss scaling reliably as $D^{-2/d}$. Linear simplex interpolation always
fits the training points exactly, and so error comes from the generalization
gap and the architecture error:

  * •

ReLU Neural Networks also provide a piecewise linear fit to data. Their
performance (RMSE loss) often scales as $D^{-2/{d^{*}}}$, where $d^{*}$ is the
_maximum arity_ of the task (typically $d^{*}=2$). Accordingly, they can scale
better than linear simplex interpolation when $d>2$. Unfortunately, they are
often afflicted by optimization error making them scale worse than linear
simplex interpolation on 1D and 2D problems, and even in higher dimensions in
the large-network limit.

  * •

Nonlinear Splines approximate a target function piecewise by polynomials. They
scale as $D^{-(n+1)/d}$ where $n$ is the order of the polynomial.

  * •

Neural Networks with smooth activations provide a nonlinear fit to data. Quite
small networks with twice-differentiable nonlinearities can perform
multiplication arbitrarily well [26], and so for many of the tasks we study
(given by symbolic formulas), their architecture error is zero. We find that
their inaccuraccy does not appear to scale cleanly as power-laws. Optimization
error is unfortunately a key driver of the error of these methods, but with
special training tricks, we found that we could reduce RMSE loss on 1D
problems down within 2-4 orders of magnitude of the 64-bit machine precision
limit $\epsilon_{0}\sim 10^{-16}$.

For those seeking high-precision fits, These results suggest the following
heuristics, summarized in Figure 10 as a “User’s Guide to Precision”: If data
dimensionality $d$ is low($d\leq 2$), polynomial spline interpolation can
provide a fit at machine precision if you (1) have enough data and (2) choose
a high enough polynomial order. Neural networks with smooth activations may in
some cases also approach machine precision, possibly with less data, if they
are trained with second-order optimizers like BFGS and boosted. For higher-
dimensional problems ($d\geq 3$), neural networks are typically the most
promising choice, since they can learn compositional modular structure that
allows them to scale _as if_ the data dimensionality were lower.

Figure 10: User’s Guide for Precision: which approximation is best depends on
properties of the problem.

In summary, our results highlight both advantages and disadvantages of using
neural networks to fit scientific data. We hope that they will help provide
useful building blocks for further work towards precision machine learning.

Acknowledgements This work was supported by The Casey Family Foundation, the
Foundational Questions Institute, the Rothberg Family Fund for Cognitive
Science, the NSF Graduate Research Fellowship (Grant No. 2141064), and IAIFI
through NSF grant PHY-2019786.

## References

  * [1] Suyog Gupta, Ankur Agrawal, Kailash Gopalakrishnan and Pritish Narayanan  “Deep Learning with Limited Numerical Precision”  In _Proceedings of the 32nd International Conference on Machine Learning_ 37, Proceedings of Machine Learning Research  Lille, France: PMLR, 2015, pp. 1737–1746  URL: https://proceedings.mlr.press/v37/gupta15.html
  * [2] Paulius Micikevicius et al.  “Mixed precision training”  In _arXiv preprint arXiv:1710.03740_ , 2017
  * [3] Dhiraj Kalamkar et al.  “A study of BFLOAT16 for deep learning training”  In _arXiv preprint arXiv:1905.12322_ , 2019
  * [4] Silviu-Marian Udrescu and Max Tegmark  “AI Feynman: A physics-inspired method for symbolic regression”  In _Science Advances_ 6.16 American Association for the Advancement of Science, 2020, pp. eaay2631
  * [5] Robert B Leighton and Matthew Sands  “The Feynman lectures on physics”  Addison-Wesley Boston, MA, USA, 1965
  * [6] “IEEE Standard for Floating-Point Arithmetic”  In _IEEE Std 754-2019 (Revision of IEEE 754-2008)_ , 2019, pp. 1–84  DOI: 10.1109/IEEESTD.2019.8766229
  * [7] Ingo Gühring, Mones Raslan and Gitta Kutyniok  “Expressivity of deep neural networks”  In _arXiv preprint arXiv:2007.04759_ , 2020
  * [8] Joel Hestness et al.  “Deep learning scaling is predictable, empirically”  In _arXiv preprint arXiv:1712.00409_ , 2017
  * [9] Jared Kaplan et al.  “Scaling laws for neural language models”  In _arXiv preprint arXiv:2001.08361_ , 2020
  * [10] Tom Henighan et al.  “Scaling laws for autoregressive generative modeling”  In _arXiv preprint arXiv:2010.14701_ , 2020
  * [11] Danny Hernandez, Jared Kaplan, Tom Henighan and Sam McCandlish  “Scaling laws for transfer”  In _arXiv preprint arXiv:2102.01293_ , 2021
  * [12] Behrooz Ghorbani et al.  “Scaling laws for neural machine translation”  In _arXiv preprint arXiv:2109.07740_ , 2021
  * [13] Mitchell A Gordon, Kevin Duh and Jared Kaplan  “Data and parameter scaling laws for neural machine translation”  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_ , 2021, pp. 5915–5922
  * [14] Xiaohua Zhai, Alexander Kolesnikov, Neil Houlsby and Lucas Beyer  “Scaling vision transformers”  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2022, pp. 12104–12113
  * [15] Jordan Hoffmann et al.  “Training Compute-Optimal Large Language Models”  In _arXiv preprint arXiv:2203.15556_ , 2022
  * [16] Aidan Clark et al.  “Unified scaling laws for routed language models”  In _International Conference on Machine Learning_ , 2022, pp. 4057–4086  PMLR
  * [17] Utkarsh Sharma and Jared Kaplan  “A neural scaling law from the dimension of the data manifold”  In _arXiv preprint arXiv:2004.10802_ , 2020
  * [18] Yasaman Bahri et al.  “Explaining neural scaling laws”  In _arXiv preprint arXiv:2102.06701_ , 2021
  * [19] Raman Arora, Amitabh Basu, Poorya Mianjy and Anirbit Mukherjee  “Understanding deep neural networks with rectified linear units”  In _arXiv preprint arXiv:1611.01491_ , 2016
  * [20] Pauli Virtanen et al.  “SciPy 1.0: fundamental algorithms for scientific computing in Python”  In _Nature methods_ 17.3 Nature Publishing Group, 2020, pp. 261–272
  * [21] Diederik P Kingma and Jimmy Ba  “Adam: A method for stochastic optimization”  In _arXiv preprint arXiv:1412.6980_ , 2014
  * [22] Yann A LeCun, Léon Bottou, Genevieve B Orr and Klaus-Robert Müller  “Efficient backprop”  In _Neural networks: Tricks of the trade_ Springer, 2012, pp. 9–48
  * [23] Wolfgang Dahmen  “Compositional Sparsity, Approximation Classes, and Parametric Transport Equations”  In _arXiv preprint arXiv:2207.06128_ , 2022
  * [24] Tomaso Poggio et al.  “Why and when can deep-but not shallow-networks avoid the curse of dimensionality: a review”  In _International Journal of Automation and Computing_ 14.5 Springer, 2017, pp. 503–519
  * [25] Francois Lekien and J Marsden  “Tricubic interpolation in three dimensions”  In _International Journal for Numerical Methods in Engineering_ 63.3 Wiley Online Library, 2005, pp. 455–471
  * [26] Henry W Lin, Max Tegmark and David Rolnick  “Why does deep and cheap learning work so well?”  In _Journal of Statistical Physics_ 168.6 Springer, 2017, pp. 1223–1247
  * [27] Levent Sagun, Leon Bottou and Yann LeCun  “Eigenvalues of the hessian in deep learning: Singularity and beyond”  In _arXiv preprint arXiv:1611.07476_ , 2016
  * [28] Levent Sagun et al.  “Empirical analysis of the hessian of over-parametrized neural networks”  In _arXiv preprint arXiv:1706.04454_ , 2017
  * [29] Guy Gur-Ari, Daniel A Roberts and Ethan Dyer  “Gradient descent happens in a tiny subspace”  In _arXiv preprint arXiv:1812.04754_ , 2018
  * [30] Jorge Nocedal and Stephen J Wright  “Numerical optimization”  Springer, 1999


11institutetext: School of Computing, University of Georgia
11email<EMAIL_ADDRESS>

# Knowledge Graph Completion using Structural and Textual Embeddings††thanks:
Accepted in AIAI 2024 - 20th International Conference on Artificial
Intelligence Applications and Innovations

Sakher Khalil Alqaaidi 11 Krzysztof Kochut 11

###### Abstract

Knowledge Graphs (KGs) are widely employed in artificial intelligence
applications, such as question-answering and recommendation systems. However,
KGs are frequently found to be incomplete. While much of the existing
literature focuses on predicting missing nodes for given incomplete KG
triples, there remains an opportunity to complete KGs by exploring relations
between existing nodes, a task known as relation prediction. In this study, we
propose a relations prediction model that harnesses both textual and
structural information within KGs. Our approach integrates walks-based
embeddings with language model embeddings to effectively represent nodes. We
demonstrate that our model achieves competitive results in the relation
prediction task when evaluated on a widely used dataset.

###### Keywords:

Knowledge Graphs Text Mining.

##  1 Introduction

Knowledge Graphs (KGs) store informational facts in a structured format of
connected triples. A triple consists of a semantic relation that binds a head
(subject) entity node with a tail (object) entity node. KGs have been widely
employed in several artificial intelligence applications on a global data
scale, such as question-answering [33] and recommendation systems [24]. Due to
their enormous sizes [13, 2], Knowledge Graphs suffer from being incomplete
[32]. Given that the KG incompleteness problem affects its utilization,
several works proposed Knowledge Graph Completion (KGC) models. These works
tackled three types of KGC, that are Link Prediction (LP), Relation Prediction
(RP), and Triple Classification (TC). The LP task aims at finding the missing
head or tail node in a triple. The RP task aims at finding the valid relations
for a given pair of head and tail nodes. The TC task aims at determining the
plausibility of a complete triple.

After surveying the literature, we found that much of the literature works
focused on the LP task, whereas the RP task remained a secondary objective in
some models [23]. A few models proposed an RP variant based on a link
prediction-oriented design [14]. However, we see that the RP task holds equal
importance to the LP task and can effectively contribute to KGC. That is by
identifying all the possible relations between node pairs. For instance, if
Apple and California are two nodes in a knowledge graph and connected using
the relation has_store_in, we could be interested in exploring other possible
relations between them. For example, one relation that can be established
between them is headquarters_in after identifying Apple as the node for the
technological company.

Recently, KGC models have achieved remarkable accomplishments by representing
graphs in the form of multi-dimensional float vectors [23]. Therefore, KGC
models can be categorized into three groups according to the representation
type used. First, KGC models utilized the graph’s structural information [3,
25]. Second, KGC models utilized the nodes’ meta information [34]. Third, KGC
models utilized a combination of the two information types [32, 29, 35]. In
terms of meta information utilization, several models have used the textual
content within node entity names as input for language models, enabling the
generation of representation embeddings. This approach has demonstrated
efficacy, particularly in inductive settings [6], that is when prediction is
conducted for nodes not seen during model training. Notably, Masked Language
Models (MLMs) showed astonishing results in the KGC task using nodes’ text.
However, these language models suffer from a costly fine-tuning phase in terms
of computational resource usage, such as time and memory. In contrast, Pre-
trained Language Models (PLMs) have significantly lower computational load and
still provide meaningful representation of words without training the model
again.

Although language models cap present powerful text representation, employing
the graph structural information is still crucial in the KGC task [29],
primarily due to the entity ambiguity problem encountered when encoding text
content. Particularly, because language models cannot represent an entity
efficiently relying on short text. Similar to the previous Apple and
California example, language model embeddings for the Apple node cannot lead
to determining whether it is the technological company or just the fruit
without having additional clues other than the node name. Otherwise, the
relation planted_in would be predicted because Apple could also be a node for
the fruit. Indeed, determining the node identity would be possible only if the
text content is detailed as in this sentence: Apple is a technology company
headquartered in California. However, such detailed description is not usually
provided in KGs without employing connections to external knowledge resources.
In contrast, the node’s structural details can support revealing the node’s
identity depending on topological information, such as the neighborhood and
the walks obtained from there [19].

To this end, we propose a relations prediction model (RPEST) that utilizes the
embeddings of structural and textual features in knowledge graphs. Our model
employs a walk-based graph structure algorithm, namely Node2Vec [9], to
replace the language model fine-tuning step with structural embeddings
training. Additionally, we exploit pre-trained language models efficiently to
capture text contextualized representation and to avoid the costly fine-tuning
phase in MLMs. We show that our choice of language model has significantly
lower overhead compared to masked language models. Notably, our model achieves
competitive results in the relation prediction task when compared to the best
accomplishments in Freebase, a widely used benchmark. Furthermore, we analyze
the effectiveness of our model’s components in a dense ablation study. To the
best of our knowledge, this is the first work that considers textual
embeddings along with graph walks-based embeddings for the RP task. The code
to reproduce the results is available online 111https://github.com/sa5r/KGRP

##  2 Background and Related Work

Given a knowledge graph
$\mathcal{G}=\\{\mathcal{E},\mathcal{R},\mathcal{T}\\}$, where $\mathcal{E}$
is a set of entity nodes, $\mathcal{R}$ is a set of relations of size $k$, and
$\mathcal{T}$ is a set of entities text. $\mathcal{G}$ is constructed of
facts; each fact is represented as a directed triple $(h,r,t)$, where
$h,t\in\mathcal{E}$, $h$ is a head entity node, $t$ is a tail entity node,
$r\in\mathcal{R}$, and $r$ is a relation with a direction from $h$ to $t$; the
direction is essential to hold the fact, thus $(t,r,h)$ is not equivalent to
$(h,r,t)$. The relation prediction task targets finding the probability of all
relations in $\mathcal{R}$ for the given nodes $h$ and $t$, formally:

$\phi(h,t)=Pr(\mathcal{R})$ (1)

where $\phi$ is a probability values scoring function. In contrast, the link
prediction task aims to find a missing head node $(?,r,t)$ or a missing tail
node $(h,r,?)$ in a triple. Recent achievements in knowledge graph completion
have followed a representation learning approach [4]. Specifically, models
targeted learning a function that can efficiently represent knowledge graph
triples in a multi-dimensional float values space $\mathbb{R}$, i.e.,
continuous vector embeddings. KGC models can be categorized into methods based
on the node’s structural information, textual content information, or a
combination of both.

###  2.1 Graph Structural Approaches

Several translation-based methods have achieved remarkable results in the link
prediction task [25, 3, 15]. TransE [3] started a translation-based stream of
methods for unsupervised graph embeddings learning. The translation technique
uses distance-based scoring function to find close embedding values of head
and tail nodes given the relation between them. Specifically, finding the
minimum value of the embeddings of the three triple elements in this equation
$|h+r-t|$, where $h,r,$ and $t$ are represented in a d-dimensional space
$\mathbb{R}^{d}$, i.e., $h,r,t\in\mathbb{R}^{d}$. Since TransE used a unified
space for nodes and relations. TransR [15] proposed a multi-relational spaces
model to tackle the problem of nodes involved in multiple facts in the
knowledge graph. Formally, each relation is represented in the space
$\mathbb{R}^{k}$, and the knowledge graph facts are represented in the space
$\mathbb{R}^{k\times d}$. However, this approach came at the cost of
additional computation due to the extended spaces. TaRP is a relation
prediction model [5]. TaRP employed different translation-based methods such
as TransE and RotateE, to generate representation embeddings. Additionally,
TaRP incorporated the node type identification and encoding to boost the
relation prediction results. A different course to generate node embeddings is
using neural networks. Shallom [7] proposed a shallow neural network layers
for the relation prediction task.

###  2.2 Textual Content Approaches

The textual content in KGs has been exploited in different ways. The node’s
long description helped in predicting the relations for nodes that were not
seen during model training, i.e., inductive settings [26]. However, retrieving
each node’s text description requires additional steps and the employment of
external knowledge bases.

BERT [8] emerged as a masked language model with a state of the art
performance on a variety of Natural Language Processing (NLP) tasks KG-BERT
[34] was one of the first models to utilize BERT for the KGC task; KG-BERT
targeted mainly the LP task. Additionally, two variants were proposed for the
RP and TC tasks. Inspired by this work, BERTRL [36] linearized the triples
around each relation and trained the model to have better inductive
performance. Nevertheless, language model-based approaches suffered from
serious issues. BERT and its successors of masked language models [16],
incorporate a costly fine-tuning phase in terms of time and memory. In large
language models (LLMs) such as GPT and Llama, the computation needs are worst
[27, 20].

In contrast, pre-trained language models (PLMs) have significant lower
computational load. Furthermore, PLMs provide meaningful representation of
text words for new datasets without retraining the model. For instance, Glove
[18] is a PLM that provides multi-dimensional vectors representation for a
single word with $O(n)$ complexity, where $n$ is the PLM’s vocabulary size.
However, Glove operates at the word level, unlike MLMs and LLMs that can
represent text sequences as contextualized embeddings. Text sequences can
consist of mutli-word terms or sentences. A node’s text content can include
multiple words, such as ‘Alfred Nobel’.

###  2.3 Hybrid Approaches

Here we review KGC models that employed a hybrid approach based on textual and
structural representation. LASS model [22] employed BERT’s fine-tuning for the
textual encoding and used the resulted loss values to construct the semantic
embeddings. A variant for triple classification was proposed in the paper.
StAR model [29] targeted handling the overwhelming performance in language
models by reusing the graph elements’ embeddings. However, the model achieved
a satisfactory performance only after combining the its textual representation
with an existing graph embeddings, such as RotateE. The KGLM model [35] re-ran
the original Roberta language model training with additional text generated
from translating KG triples into normal sentences. The model added an
entity/relation-type embedding layer to include the graph structure in
training. In KEPLER [31], authors jointly optimized the language model
training objective with the structural training objective for the link
prediction task.

Some models achieved better results in the link prediction task through trying
different negative sampling (contrastive learning) approaches in the text
embeddings training [30, 11]. The SimKGC model [30] incorporated the
structured information by re-ranking candidates based on path distances
between target nodes in the graph, whereas the MoCoSA model [11] used the
independently trained structural embeddings and fused them with the textual
embeddings.

Figure 1: Our model’s diagram showing the node representation component and
the relations prediction component.

##  3 Methodology

Our model aims to find the probability of every predefined relation that can
establish a fact by connecting a head node to a tail node. Formally,
$Pr(\mathcal{R}|h,t)$ where $\mathcal{R}$ is a set of predefined relations,
$h$ is the head node, and $t$ is the tail node. Our model takes as an input a
combination of the node structural representation and the node textual
representation. Our model conducts a supervised learning for a neural network
to predict the relations’ probabilities. Accordingly, our model consists of
two main components, the representation component and the relations prediction
component. The former incorporates our approach to generate the structural
representation and the textual representation, whereas the later incorporates
a recurrent neural network and the prediction layer. Figure 1 shows the
architecture of our model.

###  3.1 Structural Representation Training

We incorporate the nodes structural information using the Node2Vec [9] model.
Node2Vec has been known for its efficiency and for being versatile. The model
is an unsupervised learning algorithm for graph features representation.
Training in Node2Vec aims at optimizing a function that maximizes the log-
probability of observing a neighborhood for a node, based on the neighborhood
nodes’ representation as the following:

$\max\limits_{f}\sum_{u\in V}log\,Pr(N_{s}(u)|f(u))$

where $V$ is the nodes set in a graph $\mathcal{G}$, $N_{s}(u)$ is the
neighborhood for a node $u$, and $f(u)$ is the features representation for the
node $u$. The source node neighborhood is constructed from sampling nodes
identified following biased random walk strategies. The strategies could be
either Breadth-First Sampling (BFS) or Depth-First Sampling (DFS). In the
former, the sampled nodes are adjacent to the source node, whereas in the
later, the sampled nodes are found while taking further steps in the walk
paths, so it is not necessary for the nodes to be immediately connected to the
source node, but a direct path should lead to the source node.

Node2Vec is used in our model as a preliminary step before training the
prediction neural network, that is described in section 3.3, this initial
phase replaces the fine-tuning step in MLMs, which is not needed in our
implementation as described in section 3.2. After training the Node2Vec
algorithm on the graph, we get a representation $v^{{}^{\prime}}$ of $d$
vectors for each node as shown in Figure 1.

###  3.2 Text Encoding

We employ Glove [18] pre-trained word embeddings to represent the nodes’
textual content. Glove language model is an unsupervised learning algorithm
trained on a word-word co-occurrence probabilities using a global scale text
corpus. The training objective in Glove is minimizing the difference between
two words co-occurrence as the following:

$J=\sum^{V}_{i,j=1}f(X_{ij})(w^{T}_{i}\tilde{w_{j}}+b_{i}+\tilde{b_{j}}-log\,X_{ij})^{2}$

where $V$ is the number of words in Glove’s vocabulary, $i$ and $j$ are
identification numbers for two words, $w_{i}$ and $b_{i}$ are the vector and
the bias for word $i$, $w_{j}$ and $b_{j}$ are the vector and bias for word
$j$, $X_{ij}$ is the number of times word $i$ occurred in the context of word
$j$, and $f$ is a weighting function for the co-occurrences.

We chose Glove due to it is superiority among other language models, such as
the skip-gram and continuous bag-of-words (CBOW) [17], and for providing
immediate text representation without fine-tuning. However, Glove works at the
word level, accordingly, the pre-trained embeddings $E^{d}$ represent each
word in Glove’s vocabulary with vectors of size $d$ dimensions. In our
implementation, Glove encodes each node as $n\times d$ two-dimensional vector
matrix, where n is the number of words to be considered in each node. When the
number of words in a node is greater than $n$, we omit the words of index
$(n+1)$ and greater. In contrast, for nodes with number of words below $n$, we
append embeddings of zeros to keep the embeddings consistent; each padding
embedding has $d$ vectors.

KG node names usually consist of multiple words. For instance, in Freebase
[2], the average entity name length is 2.7 words. Although multi-word terms
and sentences can be represented efficiently in MLMs and LLMs, PLMs still can
present a contextualized encoding by employing a Recurrent Neural Network
(RNN). Consequently, we employ a bidirectional long-short term memory (LSTM)
layer in our model’s neural network. RNNs are capable of encoding the latent
features in text sequences [21]. For the Out-of-Vocabulary (OOV) words problem
[37], we find the longest possible match for a word in Glove’s vocabulary or
take the word letter embeddings average in the worst case. However, OOV words
still occupy less than 2% for most datasets when using Glove, due to its large
vocabulary.

We enhance the recognition of the relation direction in the input by appending
additional vector at the top of each node’s representation, this approach has
been proven to help predicting the proper relations based on the direction
[1]. The head node uses a fixed value in the added vector and the tail node
uses the same value but multiplied by -1.

###  3.3 Relation Prediction

The architecture of our model’s neural network ensures the utilization of the
latent features in the combined node embeddings. The input embeddings for each
pair of nodes consist of a head node representation concatenated with a tail
node representation. Each node’s representation consists of the textual
embeddings concatenated with the structural embeddings as shown in Figure 1.
For each pair of nodes, the bidirectional LSTM layer generates new
contextualized embeddings, that are forwarded to an attention layer to
selectively focus on certain parts of the input data, allowing the model to
weigh different inputs differently based on their relevance to the task [28].
In the following dropout layer [12] we enhance the generalization performance.
Ultimately, the output layer uses the Sigmoid function [10] to give the
probability of each relation. Our model computes the neural network training
loss using the cross entropy loss function.

##  4 Experiments

We evaluated our model on FB15K, a subset of the FreeBase dataset [2].
FreeBase has been maintained by Google for several years and has been widely
used for KG-related tasks; its content includes data collected from several
sources such as Wikipedia. The last release of the complete dataset holds
about 1.9 billion triples 222https://developers.google.com/freebase/. The
FB15K subset holds 1,345 relations and 14,951 entities. The number of triples
in the training portion is 483,142, the validation portion has 50,000 triples,
and the testing portion has 59,071 triples.

We used PyTorch to train our model. The used hardware consisted of NVIDIA
A100-SXM-80GB GPU node, a main memory of 50GB, and AMD EPYC MILAN (3rd gen)
CPU processor; we utilized 8 cores of the CPU. Table 1 shows our training
settings. We used Glove 300 dimensional word embeddings trained on 6 Billion
tokens with a 400,000 words vocabulary. For the Node2Vec training, we used
balanced settings in the biased walks. Specifically, we used equal parameters
for the breadth-first and the depth-first sampling. For the model training
optimization, we employed Adam algorithm. In the following sections we explain
the evaluation metrics, the comparison models, the main results analysis, and
the model components ablation study.

Table 1: The training settings. Settings | Value
---|---
Training Epochs | 50
Early stopping epochs | 5
Batch size | 32
LSTM features in the hidden state | 400
LSTM recurrent layers | 2
Dropout probability | 15%
Learning rate | 0.0008
Optimizer decay | 35%
Node representation padding | 40
Node2Vec walk length | 50
Node2Vec node walks | 50

###  4.1 Evaluation Metrics

We evaluate our model on two commonly used metrics. First, the mean rank of
the ground truth relation in the predicted relation probabilities set. Items
in the set follow a descending order. Accordingly, the lower the mean rank the
better the result. Since any pair of nodes may incur multiple correct
relations, the rank of a correct relation should be decremented by the number
of the valid relations that appeared on top of the correct one. This
evaluation behaviour is called the filtered settings [3] and is reported in
our experiments along with the raw mean rank. The second evaluation metric is
called Hits@1, that is the ratio of ground truth relations appeared as the
first item in the ordered relations probability values. We also report the
filtered settings for this metric.

###  4.2 Comparison Models

We perform a comparison with models that used the structural information and
the textual information in the RP task. Although some models showed
significant results in the same task, we excluded these results from our
comparison because of the utilization of node information other than the node
name, such as the description or the node entity type. For instance TaRP [5]
employed the node type information to achieve the reported performance.
Nevertheless, most datasets do not have the node type information provided by
default and that requires external knowledge bases with added load to retrieve
and encode the type information. Additionally, TaRP did not generate
embeddings for nodes but instead depended on existing models to do so.
Similarly, the work in [26] used the entity description of long text to
achieve similar results. In the following we show the models we consider in
our comparison.

TransE [3] was originally evaluated on the link prediction task. However,
several works used the method for the RP task, and we use the reported rank
and hits results in our comparison. TransE utilized the structural information
to represent nodes. TransR [15] was evaluated on the link prediction and
triple classification tasks. Similarly, other works reported TransR’s
performance in the RP task. TransR also utilized the structural information to
represent nodes. KG-BERT [34] reported their relation prediction performance
in the FB15K dataset. As described in Section 2, the model’s main design
targeted the link prediction task. KG-BERT was also evaluated on the triple
classification task. Shallom [7] tackled the RP task and utilized neural
networks embedding layers to represent nodes.

Table 2: The results of our model and the comparison models on the FB15K dataset. Model | Mean Rank | Hits@1 | Filtered Mean Rank | Filtered Hits@1
---|---|---|---|---
TransE [3] | - | 65 | 2.5 | 84
TransR [15] | - | 42 | 2.1 | 91
KG-BERT [34] | 1.69 | 69 | 1.25 | 96
Shallom [7] | 1.59 | 73 | 1.26 | 95
Ours | 1.53 | 74 | 1.18 | 94
Table 3: The results of RPEST variants on the FB15K dataset. Model | Mean Rank | Hits@1 | Filtered Mean Rank | Filtered Hits@1 | Epoch Timemin
---|---|---|---|---|---
RPESTGlove | 1.63 | 68 | 1.26 | 94 | 5
RPESTBERT | 1.70 | 67 | 1.31 | 92 | 13
RPEST | 1.53 | 74 | 1.18 | 94 | 6

###  4.3 Main Results

We show our main results in Table 2. The results show superiority of our
relation prediction model compared to the best results in other RP models.
However, KG-BERT has equivalent filtered Hits@1 score. Nevertheless, our model
beats the scores of the same model on the remaining metrics with good margin.
The mean rank scores for TransE and TransR were not reported or found in any
other study. We reason our model’s superiority by the combination of the
structural and textual details for every node. More precisely, we find the
efficient utilization of the textual content leading the performance to this
level as we show in the ablation study.

###  4.4 Ablation Study

To evaluate the effectiveness of our model’s units, we created two variants to
observe the model results after excluding some of its modules. Particularly,
we created a variant that does not employ the nodes’ structural information in
the input. Therefore, we excluded the usage of Node2Vec in our model and we
only kept Glove text encoder by creating a variant named RPESTGlove.
Furthermore, we evaluated our choice of language models by replacing Glove
with BERT language model in a variant named RPESTBERT. We show the evaluation
metric scores of the different variants in Table 3. The table also shows the
epoch time in minutes for each variant, and we rely on the time values to
emphasize the performance difference.

The lower scores of the RPESTGlove variant proofed the importance of employing
the structural information in representing nodes. However, the variant had the
fastest performance due to the reduced embeddings size after excluding
Node2Vec vectors. On the other hand, the Glove variant scored better results
compared to the RPESTBERT variant. We reason that by the efficient
exploitation of the latent features in Glove’s embeddings using the bi-
directional LSTM layer along with the attention layer and the employment of
the additional node type vector. The node type vector enhanced the relation
direction detection in our model. Regarding the slowest performing variant,
the large embeddings size led to the reported speed in BERT’s variant.

##  5 Conclusion

In this paper we explain that the relation prediction task has equal
importance to the link prediction task. We also show that the usage of nodes’
content information along with the structural information is important to have
efficient graph representation. Accordingly, we propose a relation prediction
model that utilizes a walks-based algorithm to retrieve the node structural
information along with the utilization of pre-trained language models to
represent the textual content of the nodes. We argue that masked language
models are costly in terms of computational resources and pre-trained language
models can achieve equivalent results with effective exploitation. Our model
does not require the nodes’ description and shows competitive results when
compared to the state of the art models in the same task.

## References

  * [1] Alqaaidi, S.K., Bozorgi, E., Kochut, K.J.: Multiple relations classification using imbalanced predictions adaptation. arXiv preprint arXiv:2309.13718 (2023)
  * [2] Bollacker, K., Evans, C., Paritosh, P., Sturge, T., Taylor, J.: Freebase: a collaboratively created graph database for structuring human knowledge. In: Proceedings of the 2008 ACM SIGMOD international conference on Management of data. pp. 1247–1250 (2008)
  * [3] Bordes, A., Usunier, N., Garcia-Duran, A., Weston, J., Yakhnenko, O.: Translating embeddings for modeling multi-relational data. Advances in neural information processing systems 26 (2013)
  * [4] Chen, Z., Wang, Y., Zhao, B., Cheng, J., Zhao, X., Duan, Z.: Knowledge graph completion: A review. Ieee Access 8, 192435–192456 (2020)
  * [5] Cui, Z., Kapanipathi, P., Talamadupula, K., Gao, T., Ji, Q.: Type-augmented relation prediction in knowledge graphs. In: Proceedings of the AAAI Conference on Artificial Intelligence. vol. 35, pp. 7151–7159 (2021)
  * [6] Daza, D., Cochez, M., Groth, P.: Inductive entity representations from text via link prediction. In: Proceedings of the Web Conference 2021. pp. 798–808 (2021)
  * [7] Demir, C., Moussallem, D., Ngomo, A.C.N.: A shallow neural model for relation prediction. In: 2021 IEEE 15th International Conference on Semantic Computing (ICSC). pp. 179–182. IEEE (2021)
  * [8] Devlin, J., Chang, M.W., Lee, K., Toutanova, K.: Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810.04805 (2018)
  * [9] Grover, A., Leskovec, J.: node2vec: Scalable feature learning for networks. In: Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining. pp. 855–864 (2016)
  * [10] Han, J., Moraga, C.: The influence of the sigmoid function parameters on the speed of backpropagation learning. In: International workshop on artificial neural networks. pp. 195–201. Springer (1995)
  * [11] He, J., Jia, L., Wang, L., Li, X., Xu, X.: Mocosa: Momentum contrast for knowledge graph completion with structure-augmented pre-trained language models. arXiv preprint arXiv:2308.08204 (2023)
  * [12] Hinton, G.E., Srivastava, N., Krizhevsky, A., Sutskever, I., Salakhutdinov, R.R.: Improving neural networks by preventing co-adaptation of feature detectors. arXiv preprint arXiv:1207.0580 (2012)
  * [13] Hu, W., Fey, M., Zitnik, M., Dong, Y., Ren, H., Liu, B., Catasta, M., Leskovec, J.: Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems 33, 22118–22133 (2020)
  * [14] Lin, Y., Liu, Z., Luan, H., Sun, M., Rao, S., Liu, S.: Modeling relation paths for representation learning of knowledge bases. arXiv preprint arXiv:1506.00379 (2015)
  * [15] Lin, Y., Liu, Z., Sun, M., Liu, Y., Zhu, X.: Learning entity and relation embeddings for knowledge graph completion. In: Proceedings of the AAAI conference on artificial intelligence. vol. 29 (2015)
  * [16] Liu, Y., Ott, M., Goyal, N., Du, J., Joshi, M., Chen, D., Levy, O., Lewis, M., Zettlemoyer, L., Stoyanov, V.: Roberta: A robustly optimized bert pretraining approach. arXiv preprint arXiv:1907.11692 (2019)
  * [17] Mikolov, T., Chen, K., Corrado, G., Dean, J.: Efficient estimation of word representations in vector space. arXiv preprint arXiv:1301.3781 (2013)
  * [18] Pennington, J., Socher, R., Manning, C.D.: Glove: Global vectors for word representation. In: Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP). pp. 1532–1543 (2014)
  * [19] Perozzi, B., Al-Rfou, R., Skiena, S.: Deepwalk: Online learning of social representations. In: Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining. pp. 701–710 (2014)
  * [20] Radford, A., Wu, J., Child, R., Luan, D., Amodei, D., Sutskever, I., et al.: Language models are unsupervised multitask learners. OpenAI blog 1(8), 9 (2019)
  * [21] Sak, H., Senior, A., Beaufays, F.: Long short-term memory based recurrent neural network architectures for large vocabulary speech recognition. arXiv preprint arXiv:1402.1128 (2014)
  * [22] Shen, J., Wang, C., Gong, L., Song, D.: Joint language semantic and structure embedding for knowledge graph completion. arXiv preprint arXiv:2209.08721 (2022)
  * [23] Shen, T., Zhang, F., Cheng, J.: A comprehensive overview of knowledge graph completion. Knowledge-Based Systems p. 109597 (2022)
  * [24] Sheu, H.S., Li, S.: Context-aware graph embedding for session-based news recommendation. In: Proceedings of the 14th ACM Conference on Recommender Systems. pp. 657–662 (2020)
  * [25] Sun, Z., Deng, Z.H., Nie, J.Y., Tang, J.: Rotate: Knowledge graph embedding by relational rotation in complex space. arXiv preprint arXiv:1902.10197 (2019)
  * [26] Tagawa, Y., Taniguchi, M., Miura, Y., Taniguchi, T., Ohkuma, T., Yamamoto, T., Nemoto, K.: Relation prediction for unseen-entities using entity-word graphs. In: Proceedings of the Thirteenth Workshop on Graph-Based Methods for Natural Language Processing (TextGraphs-13). pp. 11–16 (2019)
  * [27] Touvron, H., Martin, L., Stone, K., Albert, P., Almahairi, A., Babaei, Y., Bashlykov, N., Batra, S., Bhargava, P., Bhosale, S., et al.: Llama 2: Open foundation and fine-tuned chat models, 2023. URL https://arxiv. org/abs/2307.09288 (2023)
  * [28] Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A.N., Kaiser, Ł., Polosukhin, I.: Attention is all you need. Advances in neural information processing systems 30 (2017)
  * [29] Wang, B., Shen, T., Long, G., Zhou, T., Wang, Y., Chang, Y.: Structure-augmented text representation learning for efficient knowledge graph completion. In: Proceedings of the Web Conference 2021. pp. 1737–1748 (2021)
  * [30] Wang, L., Zhao, W., Wei, Z., Liu, J.: Simkgc: Simple contrastive knowledge graph completion with pre-trained language models. arXiv preprint arXiv:2203.02167 (2022)
  * [31] Wang, X., Gao, T., Zhu, Z., Zhang, Z., Liu, Z., Li, J., Tang, J.: Kepler: A unified model for knowledge embedding and pre-trained language representation. Transactions of the Association for Computational Linguistics 9, 176–194 (2021)
  * [32] Xu, J., Chen, K., Qiu, X., Huang, X.: Knowledge graph representation with jointly structural and textual encoding. arXiv preprint arXiv:1611.08661 (2016)
  * [33] Yani, M., Krisnadhi, A.A.: Challenges, techniques, and trends of simple knowledge graph question answering: a survey. Information 12(7), 271 (2021)
  * [34] Yao, L., Mao, C., Luo, Y.: Kg-bert: Bert for knowledge graph completion. arXiv preprint arXiv:1909.03193 (2019)
  * [35] Youn, J., Tagkopoulos, I.: Kglm: Integrating knowledge graph structure in language models for link prediction. arXiv preprint arXiv:2211.02744 (2022)
  * [36] Zha, H., Chen, Z., Yan, X.: Inductive relation prediction by bert. In: Proceedings of the AAAI Conference on Artificial Intelligence. vol. 36, pp. 5923–5931 (2022)
  * [37] Zhuang, Z., Liang, Z., Rao, Y., Xie, H., Wang, F.L.: Out-of-vocabulary word embedding learning based on reading comprehension mechanism. Natural Language Processing Journal 5, 100038 (2023)