# Sharing Parameter by Conjugation for Knowledge Graph Embeddings
in Complex Space

Xincan Feng†‡, Zhi Qu†, Yuchang Cheng‡, Taro Watanabe†, Nobuhiro Yugami‡
†Natural Language Processing Laboratory, Nara Institute of Science and
Technology
‡Multilingual Knowledge Computing Laboratory, Fujitsu Ltd.
{feng.xincan.fy2, qu.zhi.pv5<EMAIL_ADDRESS>
{cheng.yuchang<EMAIL_ADDRESS>

###### Abstract

A Knowledge Graph (KG) is the directed graphical representation of entities
and relations in the real world. KG can be applied in diverse Natural Language
Processing (NLP) tasks where knowledge is required. The need to scale up and
complete KG automatically yields Knowledge Graph Embedding (KGE), a shallow
machine learning model that is suffering from memory and training time
consumption issues. To mitigate the computational load, we propose a
parameter-sharing method, i.e., using conjugate parameters for complex numbers
employed in KGE models. Our method improves memory efficiency by 2x in
relation embedding while achieving comparable performance to the state-of-the-
art non-conjugate models, with faster, or at least comparable, training time.
We demonstrated the generalizability of our method on two best-performing KGE
models $5^{\bigstar}\mathrm{E}$ Nayyeri et al. (2021) and $\mathrm{ComplEx}$
Trouillon et al. (2016) on five benchmark datasets.

##  1 Introduction

A Knowledge Graph (KG) is a representation of confident information in the
real world and employed in diverse Natural Language Processing (NLP)
applications, e.g., recommender system, question answering, and text
generation. A triple in the form of $(head,relation,tail)$ is widely used as
the representation of elements in the KG instead of raw text for scalability.
Cite $(clinician,synset\\_domain\\_topic\\_of,psychology)$ as an example,
$clinician$ and $psychology$ is the head and tail entity respectively, and
$synset\\_domain\\_topic\\_of$ is the relation of the head entity pointing to
the tail entity.

Knowledge Graph Embedding (KGE) models are designed for automatic link
prediction. Relations in KG have multiple categories, e.g., symmetry,
antisymmetry, inversion, and hierarchical. Missing links indicate incomplete
ties between entities and are a common phenomenon as finding the missed
connections is labor-intensive work.

The theoretical space complexity of KGE models are often
$\mathcal{O}(n_{e}d_{e}+n_{r}d_{r})$, which is proportional to the number of
KG elements, i.e. entities $n_{e}$ and relations $n_{r}$, and embedding
dimension $d_{e},d_{r}$ respectively. Scaling a KG is problematic as
$n_{e},n_{r}$ can go up to millions; also because KGE models are often shallow
machine learning models composed of simple operations, e.g., matrix
multiplication. Caution that a shallow model needs a large dimension size $d$
to depict the data feature, yielding the issue of the drastic increase of
embedding parameters Dettmers et al. (2018).

KGE models represented using complex numbers have state-of-the-art
performance, while they demand high memory costs. E.g., if using one of the
best models $\mathrm{ComplEx}$ Trouillon et al. (2016) to create embedding for
the benchmark dataset FB15K whose $n_{e}=14,951,n_{r}=1,345$, and the best-
performing dimensionalities $d_{e}=4000,d_{r}=4000$, will result in the
parameter size of $65,184,000$. Considering the data type 64-bit integer
(signed), who has a size of 8 bytes in PyTorch, the memory cost will be
$65,184,000\times 8\approx 497$ MB. A KG for real-world application could have
a much larger size, e.g., IBM’s KG contains entities > 100 million and
relations > 5 billion, which is actively in use and continually growing Noy et
al. (2019), would need > $148$ TB memory to do link prediction task.

Inspired by the improved performance of complex number representation and Non-
Euclidean models where transformation parameters attempt to interact rather
than be independent, we intuited the idea of sharing parameters for memory
efficiency.

We demonstrate a parameter-sharing method for complex numbers employed in KGE
models. Specifically, our method formulates conjugate parameters in
appropriate dimensions of the transformation functions to reduce relation
parameters. By using our method, models can reduce their space complexity to
$\mathcal{O}(n_{e}d_{e}+n_{r}d_{r}/2)$, which means the relation embedding
size is half the original model. In the second place, using conjugate
parameters may help save training time, especially on the datasets who have
more parameter patterns. Further, our method can be easily applied to various
complex number represented models.

We verified our method on two best-performing KGE models, i.e.,
$\mathrm{ComplEx}$ Trouillon et al. (2016) and $5^{\bigstar}\mathrm{E}$
Nayyeri et al. (2021). The experiments were conducted on five benchmark
datasets, i.e., FB15K-237, WN18RR, YAGO3-10, FB15K, and WN18, by which we
empirically show that our method reserves the models’ ability to achieve
state-of-the-art results. We also see 31% training time saved on average for
$5^{\bigstar}\mathrm{E}$ in addition to the memory. Our method is implemented
in PyTorch111https://pytorch.org/ and the code with hyperparameter
settings222github.com/xincanfeng/dimension are available online.

##  2 Related Works

We describe the categorizations of KGE models according to the representation
method and the vector space that inspired our idea.

#### Representation Method

Real and complex number representations are used to quantify entities and
relations.

Translation approaches including $\mathrm{TransE}$ Bordes et al. (2013) and
its variants Ji et al. (2015); Lin et al. (2015) describe embeddings using
real number representation. Although these simple models cost fewer
parameters, they can only encode two or three relation patterns, e.g.,
$\mathrm{TransE}$ cannot encode symmetric relations.

$\mathrm{ComplEx}$ Trouillon et al. (2016) creates embedding with complex
number representation, which can handle a wider variety of relations than
using only real numbers, among them symmetric and antisymmetric relations
Trouillon et al. (2016). $5^{\bigstar}\mathrm{E}$ Nayyeri et al. (2021)
utilizes Möbius transformation, a projective geometric function that supports
multiple simultaneous transformations in complex number representation and can
embed entities in much lower ranks.

#### Vector Space

Euclidean and Non-Euclidean spaces are practiced for the calculation of triple
plausibility.

Factorization models such as $\mathrm{RESCAL}$ Nickel et al. (2011) and
$\mathrm{DistMult}$ Yang et al. (2014) employ element-wise multiplication in
Euclidean space. Correspondingly, the plausibility of a triple is measured
according to the angle of transformed head and tail entities.

$\mathrm{MuRP}$ Balazevic et al. (2019) minimizes hyperbolic distances other
than Euclidean. It needs fewer parameters than its Euclidean analog.
$\mathrm{ATTH}$ Chami et al. (2020) leverages trainable hyperbolic curvatures
for each relation to simultaneously capture logical patterns and hierarchies.
Compared with Euclidean, the Hyperbolic models can save more structures using
variational curvatures in different areas to depict hierarchical relations.

#### Relational Constrain on Parameters

Replacing real number with complex number representation enables the imaginary
part to have an effect on the real part parameters, the boosted performance of
which indicates the hidden relation among parameter. Using hyperbolic space
other than Euclidean enables the distances or angles at different positions to
vary, the increased accuracy hints us to add various constraints on
parameters. Learning from the work by Hayashi and Shimbo (2017), the potential
of improving representations through conjugate symmetric constraint is
revealed. Therefore, we hypothesize the efficiency of relational parameters
and propose a parameter-sharing method using conjugate numbers.

##  3 Method

Complex number employed in current KGE models enforces multiplicative
constraint on representations; our method further adds conjugate constraint
within the parameters. Note that we don’t reduce the dimensions of the
parameters, instead, we share the dimensions.

We economize 50% of the memory in relation embedding by sharing half of the
parameters in the conjugate form. Our approach is at least comparable in
accuracy to the baselines. In addition, our method reduces calculation in the
regularization process, e.g., for the $5^{\bigstar}\mathrm{\epsilon}$ model,
31% of training time is saved on average for five benchmark datasets.

###  3.1 Preliminaries

Link prediction task inquires if a triple $(h,r,t)$ constructed by existing
head and tail entities $h,t\in\mathbb{V}^{d_{e}}$ and relations
$r\in\mathbb{V}^{d_{r}}$ ($\mathbb{V}^{d}$ is a $d$-dimensional vector space)
is true or not. In KGE models, the relations are often represented as the
transformation function $\vartheta$ that maps a head entity into a tail entity
which are described as vectors in corresponding space, i.e., $\vartheta(h)=t$.
Then, the score function
$f:\mathbb{V}^{d_{e}}\times\mathbb{V}^{d_{r}}\times\mathbb{V}^{d_{e}}\rightarrow\mathbb{R}$
returns the plausibility $p$ of constructing a true triple:
$f(h,r,t)=p(\vartheta(h),t)$.

$a,b,c,d\in\mathbb{C}$ denote the parameters in the relation embedding
matrices. $x\in\mathbb{C}$ is the parameter of the entity embedding matrices.
$a_{i},x_{i}$ are the parameters of the submatrices of $[a]$ and $[x]$
respectively. $Re(z)$ is the real part of the complex number $z$,
$\overline{z}$ is the complex conjugate of $z$.

#### $\mathrm{\mathbf{ComplEx}}$

This is the first and one of the best-performing complex models in Euclidean
space. Trouillon et al. (2016) demonstrated that complex number multiplication
could capture antisymmetric relations while retaining the efficiency of the
dot product, i.e., linearity in both space and time complexity. Balancing
between model expressiveness and parameter size is also discussed as the
keystone of KGE. However, targeting SOTA is still computational-expensive
because Trouillon et al. (2016) didn’t solve the performance deterioration
problem when reducing parameters directly.

Performance deterioration can be severe whenever the KG needs to be expanded
because the mispredicted links could lead to further misinformation. Hence we
should always endeavour to adopt the best-performing embedding size in doing
link prediction task, even though it could be hundreds of TB.

To obtain the best results, $\mathrm{ComplEx}$ needs embedding size of
$rank=2000$ on dataset FB15K-237, WN18RR, FB15K, WN18, and $rank=1000$ on
dataset YAGO3-10. $rank$ denotes the vector dimension of a single-functional
parameter. Each entity and relation in this model needs $2\times rank$
parameters, representing real and imaginary part, respectively.

In this model, relations are represented as the real part of low-rank matrix
$\begin{bmatrix}a\\\ \end{bmatrix}$, which act as weights on each entity
dimension $x$, followed by a projection onto the real subspace. The
transformation of $\mathrm{ComplEx}$ is

$x\rightarrow\begin{bmatrix}a\end{bmatrix}x\rightarrow ax.$ (1)

#### $\mathbf{5^{\bigstar}}\mathrm{\mathbf{E}}$

This is a novel model applying complex numbers in Non-Euclidean space. Nayyeri
et al. (2021) tackled the problem of multiple subgraph structures in the
neighborhood, e.g., combinations of path and loop structures. Unlike the
$\mathrm{ComplEx}$ model, they replaced the dot product with the Möbius
function which has several favorable theoretical properties. This model
subsumes $\mathrm{ComplEx}$ in that it embeds entities in much lower ranks,
i.e., about 25% or even smaller to achieve the state-of-the-art performance.
However, $5^{\bigstar}\mathrm{E}$ is inferior to $\mathrm{ComplEx}$ in that it
needs almost the same large size of relation parameters to do much more
sophisticated calculation.

Following the hyperparameter search range of Nayyeri et al. (2021), the
embedding sizes we tested for $5^{\bigstar}\mathrm{E}$ to obtain the best
result are $rank=500$ for all datasets. Each entity needs $2\times rank$
parameters, and each relation needs $8\times rank$ parameters that function
differently.

In this model, relations are represented as $\begin{bmatrix}a&b\\\ c&d\\\
\end{bmatrix}$. The transformation function $\vartheta$ of
$5^{\bigstar}\mathrm{E}$ is

$x\rightarrow\begin{bmatrix}x\\\
1\end{bmatrix}\rightarrow\begin{bmatrix}a&b\\\ c&d\\\
\end{bmatrix}\begin{bmatrix}x\\\ 1\end{bmatrix}\rightarrow\frac{ax+b}{cx+d}.$
(2)

Möbius function $\vartheta$ is capable of representing various relations
simultaneously because it combines five subsequent transformations:
$\vartheta=\vartheta_{4}\circ\vartheta_{3}\circ\vartheta_{2}\circ\vartheta_{1}$,
where $\vartheta_{1}=x+\frac{d}{c}$ is describing translation by
$\frac{d}{c}$, $\vartheta_{2}=\frac{1}{x}$ is describing inversion and
reflection w.r.t. real axis, $\vartheta_{3}=\frac{bc-ad}{c^{2}}x$ is
describing homothety and rotation, and $\vartheta_{4}=x+\frac{a}{c}$ is
describing translation by $\frac{a}{c}$.

(a)  Transformed entities by $\mathrm{ComplEx}$ (left) and
$\mathrm{Compl\epsilon x}$ (right). In the left graph, a black point describes
a transformed entity, and the vector values of a point are unrelated in each
dimension. While in the right graph, half of the value $z_{i},i\in[1,d/2]$ of
a vector $z_{1},z_{2},...,z_{d}$ that is describing a point are constrained as
the other half $z_{i},i\in[d/2+1,d]$ correspondingly. The linear constrain
$z_{i}=a_{i}x_{i}+b_{i}y_{i}$ is illustrated in the right graph.

(b)  Transformed entities by $5^{\bigstar}\mathrm{E}$ (left) and
$5^{\bigstar}\mathrm{\epsilon}_{n}$ (right). Note that we illustrate the
negative conjugated model instead of the positive conjugated one for
simplicity in plotting. Blue traces are the original entities and their
projections in the Non-Euclidean space. Green traces are the multiple copies
of the blue traces under iterations of the Möbius transformation. Red traces
are the inverse of green traces. Apparently, the right graph has much neater
geometric properties.

Figure 1: Transformed entities illustrated in 3D

###  3.2 Method Formulation

Let $\begin{bmatrix}a_{1}&a_{2}\\\ \end{bmatrix}$ denotes the relation
embedding matrix. Our method constrains half of the parameters $a_{2}$ using
the complex conjugate of the other half $\overline{a_{1}}$, i.e.,
$a_{2}=\overline{a_{1}}$; it is model-dependent to specify which parameters
are suitable for conjugation. We formulated our method on above two baseline
models.

#### $\mathrm{\mathbf{Compl\epsilon x}}$

By using our method, the original model $\mathrm{ComplEx}$ is adapted to the
parameter-sharing model $\mathrm{Compl\epsilon x}$, where relations are
represented as the real part of low-rank matrices with conjugate parameters.
Specifically, we set the original square relation embedding matrices
$\begin{bmatrix}a_{1}&a_{2}\\\ \end{bmatrix}$ to be half the normal parameters
and the other half their conjugation, i.e.,
$\begin{bmatrix}a_{1}&\overline{a_{1}}\\\ \end{bmatrix}$. In this model, since
each parameter is functioning equally, the positions of the conjugate
parameters can be set randomly.

#### $\mathbf{5^{\bigstar}}\mathrm{\mathbf{\epsilon}}$

Our method transforms the original model $5^{\bigstar}\mathrm{E}$ into the
parameter-sharing model $5^{\bigstar}\mathrm{\epsilon}$, where relations are
represented as the real part of low-rank matrices using conjugate parameters.
Specifically, we set the original square relation embedding matrices
$\begin{bmatrix}a&b\\\ c&d\\\ \end{bmatrix}$ to be half the normal parameters
and the other half their conjugate parameters, i.e., $\begin{bmatrix}a&b\\\
\overline{b}&\overline{a}\\\ \end{bmatrix}$. In this model, parameters play
distinct roles at different positions, and the best conjugation positions are
the principal and secondary diagonal positions. Note that experiments showed
that, the following negative conjugation method, i.e., $\begin{bmatrix}a&b\\\
-\overline{b}&\overline{a}\\\ \end{bmatrix}$, achieves similar performance as
above. Although the negative conjugation on this model is equivalent to
restricting the original Möbius function to the unitary Möbius transformation,
our approach is much more general to a variety of representations.

###  3.3 Transformation Analysis

#### $\mathrm{\mathbf{Compl\epsilon x}}$

Let $a_{2}=\overline{a_{1}}$, then the transformation of conjugate model
$\mathrm{Compl\epsilon x}$ is

$\begin{bmatrix}x_{1}&x_{2}\end{bmatrix}\rightarrow\begin{bmatrix}a_{1}&\overline{a_{1}}\end{bmatrix}\begin{bmatrix}x_{1}&x_{2}\end{bmatrix}\rightarrow\begin{bmatrix}a_{1}x_{1}&\overline{a_{1}}x_{2}\end{bmatrix}.$
(3)

We can see that the resulted relation embedding is constrained to
$\begin{bmatrix}a_{1}&\overline{a_{1}}\end{bmatrix}$ other than
$\begin{bmatrix}a_{1}&a_{2}\end{bmatrix}$; the predicted tail entity is
constrained to $\begin{bmatrix}a_{1}x_{1}&\overline{a_{1}}x_{2}\end{bmatrix}$
instead of $\begin{bmatrix}a_{1}x_{1}&a_{2}x_{2}\end{bmatrix}$ in original
model, which does not narrow the rang of relation or tail embedding since the
$a_{1},x_{2}$ can be any value. Further, since tail entities also act as head
entities, we can say that the range of both the entities and relations are not
constrained.

Dataset | #Train | #Valid | #Test | Ent | Rel | Exa
---|---|---|---|---|---|---
FB15K-237 | 272,115 | 17,535 | 20,466 | 14,541 | 237 | 544,230
WN18RR | 86,835 | 3,034 | 3,134 | 40,943 | 11 | 173,670
YAGO3-10 | 1,079,040 | 5,000 | 5,000 | 123,188 | 37 | 2,158,080
FB15K | 483,142 | 50,000 | 59,071 | 14,951 | 1,345 | 966,284
WN18 | 141,442 | 5,000 | 5,000 | 40,943 | 18 | 282,884
Table 1: Datasets statistics. #: Split in terms of number of triples; Ent:
Entities; Rel: Relations; Exa: Examples.

#### $\mathbf{5^{\bigstar}}\mathrm{\mathbf{\epsilon}}$

Let $c=\overline{b},d=\overline{a}$, then the transformation of conjugate
model $5^{\bigstar}\mathrm{\epsilon}$ is

$x\rightarrow\begin{bmatrix}x\\\
1\end{bmatrix}\rightarrow\begin{bmatrix}a&b\\\ \overline{b}&\overline{a}\\\
\end{bmatrix}\begin{bmatrix}x\\\
1\end{bmatrix}\rightarrow\frac{ax+b}{\overline{b}x+\overline{a}}.$ (4)

The five subsequent transformations turn into:
$\vartheta_{1}=x+\frac{\overline{a}}{\overline{b}}$ which depicts translation
by $\frac{\overline{a}}{\overline{b}}$, $\vartheta_{2}=\frac{1}{x}$ which
depicts inversion and reflection w.r.t. real axis,
$\vartheta_{3}=\frac{b\overline{b}-a\overline{a}}{\overline{b}^{2}}x$ which
depicts homothety and rotation, and $\vartheta_{4}=x+\frac{a}{\overline{b}}$
which depicts translation by $\frac{a}{\overline{b}}$. We can see that,
although the relation parameters are constrained comparing to the original
model, the five sub-transformations are reserved in this conjugate model.

#### Characteristics

For this reason, we consider our conjugate models retain expressiveness in
function level for various relation patterns compared to their original
counterparts. The difference between original models and our conjugate models
is that, the latter ones have more linear constrain in its value of each
embedding parameter, as illustrated in Figure 1.

###  3.4 Reduced Calculation

Sharing half of the parameters also reduces the computation for the
regularization terms into half, where each parameter of relation is squared to
the sum. For example, the original calculation $r_{1}^{2}+r_{2}^{2}$ is turned
into $r_{1}^{2}\times 2$ in both baseline models, where $r_{1},r_{2}$ denote
the real or imaginary part of a complex number, and in which $r_{1}$
represents the shared parameter. However, the final time consumption depends
on multiple aspects, such as formulation and coding, thus is not necessarily
reduced.

##  4 Experiments

###  4.1 Experimental Setup

#### Metrics

We followed the standard evaluation protocal for KGE models. $T$: the rank set
of truth, $r_{i}$: the rank position $r$ of the first true entity for the
$i$-th query. We computed two rank-based metrics: (i) Mean Reciprocal Rank
(MRR), which computes the arithmetic mean of reciprocal ranks of all true
entities from the ranked list of answers to queries $T$, and (ii) Hits@$N$
($N$ = 1, 3, 10), which counts the true entities $\mathbb{I}$ and calculate
their proportion in the truth $T$ in top $N$ sorted predicted answers list.

$\mathrm{MRR}=\frac{1}{T}\sum_{i=1}^{T}\frac{1}{r_{i}}$ (5)
$\mathrm{Hits@}N=\frac{1}{T}\sum_{r\in T,r\leq N}\mathbb{I}$ (6)

We also use additional metric Time (seconds/epoch) to measure how many seconds
each training epoch costs to demonstrate the time saved by our method. To do
this, we conducted all experiments using the same GPUs. GeForce GTX 1080 Ti is
used for all datasets except for the largest dataset YAGO3-10 who needs a
larger GPU and we used Tesla V100S-PCIE-32GB for it.

#### Datasets

We evaluated our method on five widely used benchmark datasets (See Table 1).
FB15K Bordes et al. (2013) is a subset of Freebase, the contents of which are
general facts. WN18 Bordes et al. (2013) is a subset of Wordnet, a database
that features lexical relations between words. YAGO3-10 Dettmers et al. (2018)
is the largest common dataset, which mostly describes attributes of persons,
and contains entities associated with at least ten different relations.

As was first noted by Toutanova and Chen (2015), FB15K and WN18 suffer from
test leakage through inverse relations, e.g., the test set frequently contains
triples such as $(s,hyponym,o)$ while the training set contains its inverse
$(o,hypernym,s)$. To create a dataset without this property, they introduced
FB15K-237, a subset of FB15K where inverse relations are removed. WN18RR was
created for the same reason by Dettmers et al. (2018).

We adopted all of the five datasets for comprehensive comparison of models.

#### Hyperparameter Settings

We explored the influence of hyperparameter settings to our method. To do
this, we used the best hyperparameter settings for the original models (marked
as $\nabla$ or no mark), and applied the same settings on our conjugate models
and ablation models. We adopted the best hyperparameter settings for
$\mathrm{ComplEx}$ provided by Nayyeri et al. (2021), and fine-tuned the best
hyperparameters ourselves for $5^{\bigstar}\mathrm{E}$ since there was no
published best hyperparameter settings for this model at the time we did the
experiments. We also fine-tuned the best hyperparameters for one of our
conjugate model $5^{\bigstar}\mathrm{\epsilon}$ (noted as $\diamondsuit$) to
explore the upper bound.

We selected the hyperparameters based on the MRR on the validation set. Our
grid search range refered to but was larger than Nayyeri et al. (2021). The
optional optimizers are {Adagrad, Adam, SGD}. The range of embedding
dimensions are {100, 500} with learning rates range in {1E-02, 5E-02, 1E-01}.
The batch sizes attempted range in {100, 500, 1000, 2000}. Regularization
coefficients are tested among {2.5E-03, 5E-03, 1E-02, 5E-02, 1E-01, 5E-01}.

Model | Time | MRR | H@1 | H@3 | H@10
---|---|---|---|---|---
$\mathrm{ComplEx}$ | 42$\pm$8 | 0.366$\pm$4e-4 | 0.271 | 0.402 | 0.558
$\mathrm{Compl\epsilon x}$ | 46$\pm$11 | 0.363$\pm$5e-4 | 0.268 | 0.400 | 0.555
$5^{\bigstar}\mathrm{E}$ | 18$\pm$3 | 0.350$\pm$8e-4 | 0.257 | 0.386 | 0.538
$5^{\bigstar}\mathrm{\epsilon}_{\nabla}$ | 14$\pm$4 | 0.353$\pm$7e-4 | 0.259 | 0.390 | 0.541
$5^{\bigstar}\mathrm{\epsilon}_{\diamondsuit}$ | 17$\pm$9 | 0.354$\pm$8e-4 | 0.259 | 0.391 | 0.544

(a) FB15K-237

Model | Time | MRR | H@1 | H@3 | H@10
---|---|---|---|---|---
$\mathrm{ComplEx}$ | 139$\pm$21 | 0.488$\pm$1e-3 | 0.442 | 0.503 | 0.579
$\mathrm{Compl\epsilon x}$ | 146$\pm$45 | 0.475$\pm$9e-4 | 0.433 | 0.488 | 0.558
$5^{\bigstar}\mathrm{E}$ | 16$\pm$1 | 0.490$\pm$5e-4 | 0.444 | 0.506 | 0.587
$5^{\bigstar}\mathrm{\epsilon}_{\nabla}$ | 11$\pm$1 | 0.493$\pm$8e-4 | 0.442 | 0.512 | 0.588
$5^{\bigstar}\mathrm{\epsilon}_{\diamondsuit}$ | - | - | - | - | -

(b) WN18RR

Model | Time | MRR | H@1 | H@3 | H@10
---|---|---|---|---|---
$\mathrm{ComplEx}$ | 370$\pm$2 | 0.577$\pm$1e-3 | 0.502 | 0.622 | 0.712
$\mathrm{Compl\epsilon x}$ | 371$\pm$2 | 0.574$\pm$2e-3 | 0.500 | 0.618 | 0.707
$5^{\bigstar}\mathrm{E}$ | 415$\pm$2 | 0.574$\pm$2e-3 | 0.502 | 0.617 | 0.701
$5^{\bigstar}\mathrm{\epsilon}_{\nabla}$ | 297$\pm$1 | 0.576$\pm$2e-3 | 0.505 | 0.619 | 0.702
$5^{\bigstar}\mathrm{\epsilon}_{\diamondsuit}$ | - | - | - | - | -

(c) YAGO3-10

Table 2: Link prediction results on FB15K-237, WN18RR, YAGO3-10 datasets.
Time, MRR and H@n are presented as mean ($\pm$ standard deviation).

Model | Time | MRR | H@1 | H@3 | H@10
---|---|---|---|---|---
$\mathrm{ComplEx}$ | 346$\pm$124 | 0.855$\pm$1e-3 | 0.823 | 0.874 | 0.910
$\mathrm{Compl\epsilon x}$ | 293$\pm$16 | 0.855$\pm$1e-3 | 0.827 | 0.871 | 0.907
$5^{\bigstar}\mathrm{E}$ | 42$\pm$9 | 0.812$\pm$1e-3 | 0.767 | 0.840 | 0.889
$5^{\bigstar}\mathrm{\epsilon}_{\nabla}$ | 26$\pm$0 | 0.794$\pm$2e-3 | 0.743 | 0.827 | 0.882
$5^{\bigstar}\mathrm{\epsilon}_{\diamondsuit}$ | 29$\pm$5 | 0.813$\pm$2e-3 | 0.766 | 0.844 | 0.894

(a) FB15K

Model | Time | MRR | H@1 | H@3 | H@10
---|---|---|---|---|---
$\mathrm{ComplEx}$ | 57$\pm$3 | 0.951$\pm$3e-4 | 0.944 | 0.954 | 0.961
$\mathrm{Compl\epsilon x}$ | 58$\pm$5 | 0.950$\pm$3e-4 | 0.945 | 0.953 | 0.960
$5^{\bigstar}\mathrm{E}$ | 43$\pm$6 | 0.952$\pm$5e-4 | 0.946 | 0.955 | 0.962
$5^{\bigstar}\mathrm{\epsilon}_{\nabla}$ | 29$\pm$6 | 0.949$\pm$6e-4 | 0.944 | 0.953 | 0.959
$5^{\bigstar}\mathrm{\epsilon}_{\diamondsuit}$ | 26$\pm$2 | 0.952$\pm$3e-4 | 0.947 | 0.955 | 0.962

(b) WN18

Table 3: Link prediction results on FB15K and WN18 datasets. Instructions for
this table are the same as those in Table 2.

Model | Time | MRR | H@1 | H@3 | H@10
---|---|---|---|---|---
$5^{\bigstar}\mathrm{\epsilon}_{\nabla}$ | 14$\pm$4 | 0.353$\pm$7e-4 | 0.259 | 0.390 | 0.541
$5^{\bigstar}\mathrm{\epsilon}_{n}$ | 13$\pm$2 | 0.353$\pm$8e-4 | 0.259 | 0.389 | 0.541
$5^{\bigstar}\mathrm{E_{r}}$ | 16$\pm$0 | 0.326$\pm$1e-3 | 0.238 | 0.357 | 0.505
$5^{\bigstar}\mathrm{\epsilon}_{v}$ | 13$\pm$1 | 0.264$\pm$4e-4 | 0.192 | 0.288 | 0.404
$5^{\bigstar}\mathrm{\epsilon}_{h}$ | 12$\pm$0 | 0.301$\pm$4e-4 | 0.221 | 0.329 | 0.458

(a) FB15K-237

Model | Time | MRR | H@1 | H@3 | H@10
---|---|---|---|---|---
$5^{\bigstar}\mathrm{\epsilon}_{\nabla}$ | 11$\pm$1 | 0.493$\pm$8e-4 | 0.442 | 0.512 | 0.588
$5^{\bigstar}\mathrm{\epsilon}_{n}$ | 14$\pm$3 | 0.485$\pm$1e-3 | 0.432 | 0.506 | 0.589
$5^{\bigstar}\mathrm{E_{r}}$ | 16$\pm$0 | 0.410$\pm$3e-3 | 0.391 | 0.417 | 0.447
$5^{\bigstar}\mathrm{\epsilon}_{v}$ | 12$\pm$5 | 0.026$\pm$2e-4 | 0.015 | 0.025 | 0.045
$5^{\bigstar}\mathrm{\epsilon}_{h}$ | 14$\pm$3 | 0.026$\pm$3e-4 | 0.016 | 0.025 | 0.046

(b) WN18RR

Model | Time | MRR | H@1 | H@3 | H@10
---|---|---|---|---|---
$5^{\bigstar}\mathrm{\epsilon}_{\nabla}$ | 297$\pm$1 | 0.576$\pm$2e-3 | 0.505 | 0.619 | 0.702
$5^{\bigstar}\mathrm{\epsilon}_{n}$ | 298$\pm$1 | 0.574$\pm$1e-3 | 0.502 | 0.618 | 0.701
$5^{\bigstar}\mathrm{E_{r}}$ | 416$\pm$2 | 0.569$\pm$2e-3 | 0.499 | 0.611 | 0.695
$5^{\bigstar}\mathrm{\epsilon}_{v}$ | 297$\pm$1 | 0.562$\pm$8e-4 | 0.488 | 0.607 | 0.695
$5^{\bigstar}\mathrm{\epsilon}_{h}$ | 298$\pm$1 | 0.546$\pm$1e-3 | 0.471 | 0.592 | 0.680

(c) YAGO3-10

Table 4: Ablation studies on FB15K-237, WN18RR, YAGO3-10 datasets.
Instructions for this table are the same as those in Table 2.

Model | Time | MRR | H@1 | H@3 | H@10
---|---|---|---|---|---
$5^{\bigstar}\mathrm{\epsilon}_{\nabla}$ | 26$\pm$0 | 0.794$\pm$2e-3 | 0.743 | 0.827 | 0.882
$5^{\bigstar}\mathrm{\epsilon}_{n}$ | 31$\pm$12 | 0.799$\pm$2e-3 | 0.750 | 0.831 | 0.883
$5^{\bigstar}\mathrm{E_{r}}$ | 37$\pm$1 | 0.807$\pm$3e-3 | 0.760 | 0.838 | 0.888
$5^{\bigstar}\mathrm{\epsilon}_{v}$ | 31$\pm$7 | 0.801$\pm$8e-4 | 0.753 | 0.833 | 0.885
$5^{\bigstar}\mathrm{\epsilon}_{h}$ | 28$\pm$2 | 0.787$\pm$2e-3 | 0.735 | 0.822 | 0.877

(a) FB15K

Model | Time | MRR | H@1 | H@3 | H@10
---|---|---|---|---|---
$5^{\bigstar}\mathrm{\epsilon}_{\nabla}$ | 29$\pm$6 | 0.949$\pm$6e-4 | 0.944 | 0.953 | 0.959
$5^{\bigstar}\mathrm{\epsilon}_{n}$ | 26$\pm$0 | 0.952$\pm$3e-4 | 0.946 | 0.955 | 0.962
$5^{\bigstar}\mathrm{E_{r}}$ | 40$\pm$0 | 0.943$\pm$9e-4 | 0.935 | 0.950 | 0.954
$5^{\bigstar}\mathrm{\epsilon}_{v}$ | 31$\pm$11 | 0.892$\pm$2e-3 | 0.836 | 0.944 | 0.958
$5^{\bigstar}\mathrm{\epsilon}_{h}$ | 26$\pm$0 | 0.822$\pm$2e-3 | 0.719 | 0.920 | 0.949

(b) WN18

Table 5: Ablation studies on FB15K and WN18 datasets. Instructions for this
table are the same as those in Table 2.

##  5 Results

###  5.1 Main Results and Analysis

The main experimental results are shown in Table 2 and Table 3. The numbers
with boldface indicate the best results among all the models.

We mainly tested whether the conjugate models perform consistent with their
original counterparts, especially whether they can achieve the same state-of-
the-art results. We conducted one set of experiments using the best
hyperparameters of the original models (marked as $\nabla$ or no mark), and
the other set of experiments tuning the hyperparameters for one of our
conjugate model (marked as $\diamondsuit$).

The results show that both $\mathrm{Compl\epsilon x}$ and
$5^{\bigstar}\mathrm{\epsilon}$ consistently achieve results comparable to
their original models on the datasets without test set leakage, including the
largest dataset, i.e., YAGO3-10; and obtain the same optimal accuracies as the
original models on all datasets with possibly-required fine-tuning. From the
perspective of training time, we see $5^{\bigstar}\mathrm{\epsilon}$ spends
31% less time on average for all datasets; and both conjugate models perform
substantially best in training time on datasets FB15K, who have the most
relations.

#### $\mathrm{\mathbf{Compl\epsilon x}}$

Under the best hyperparameter settings of the original model, the performance
of $\mathrm{Compl\epsilon x}$ are consistently comparable with
$\mathrm{ComplEx}$ on all five datasets. We speculate the reason for the
consistent but tiny performance drop might come from the computation
precision, but we will leave it as our future studies.

Although our method reduces the computation, applying the method on this model
requires splitting and concatenating matrices to keep the shape of outputs
which incurs additional time-consuming operations. Consequently, the total
time cost is not reduced much. However, training time on dataset FB15K, who
has the most relations, becomes very stable.

Overall results imply our conjugate model $\mathrm{Compl\epsilon x}$ is at
least comparative with its baseline model $\mathrm{ComplEx}$.

#### $\mathbf{5^{\bigstar}}\mathrm{\mathbf{\epsilon}}$

Under the best hyperparameter settings of the original
$5^{\bigstar}\mathrm{E}$, the conjugate
$5^{\bigstar}\mathrm{\epsilon}_{\nabla}$ consistently achieve competitive
results on the datasets FB15K-237, WN18RR and YAGO3-10. The tiny but
consistent accuracy enhancement on these three datasets is probably caused by
similar programming artifacts as observed in $\mathrm{ComplEx}$.

We hypothesize that the accuracy fluctuation of
$5^{\bigstar}\mathrm{\epsilon}_{\nabla}$ on FB15K and WN18 is caused by the
test leakage issue which makes the model sensitive to its hyperparameter
setting. Because the only difference of these two datasets comparing to their
subsets FB15K-237 and WN18RR is the 81% and 94% inverse relations Toutanova
and Chen (2015), i.e., $(s,hyponym,o)$ and $(o,hypernym,s)$ in the training
set and the test set respectively, which is known as test leakage. Note that
the accuracy fluctuation was simply solved by fine-tuning the hyperparameters
(See results marked as $5^{\bigstar}\mathrm{\epsilon}_{\diamondsuit}$).

Notice that in Table 2, we didn’t report the fine-tuned results of
$5^{\bigstar}\mathrm{\epsilon}_{\diamondsuit}$ on datasets WN18RR and
YAGO3-10, because the results abtained with the original settings $\nabla$ is
already the best.

Training time in this model was reduced by 22%, 31%, 28%, 38% and 33% on each
dataset respectively, and 31% on average. $5^{\bigstar}\mathrm{E}$ has eight
parameter matrices in the coding. By using our method, the parameter matrices
are directly reduced to four with no additional coding operations, which makes
the significant saved training time.

Above results mean our conjugate model $5^{\bigstar}\mathrm{\epsilon}$ exceeds
the baseline model $5^{\bigstar}\mathrm{E}$ in all respect of accuracy,
memory-efficiency and time footprint.

###  5.2 Ablation Studies

We did two kinds of ablation studies. The results are shown in Table 4 and
Table 5. We know the reduced calculation is mainly in the regularization
process because we only use half of the parameters. Thus we experimented where
the regularization term is only half of the parameters on the original model
(See results for $5^{\bigstar}\mathrm{E}_{r}$) to explore whether the effect
of our method is similar to the reduced parameters regularization.

Then we experimented with conjugations in different positions to explore how
the models perform differently. We set negative conjugation
$c=-\overline{b},d=\overline{a}$ in model $5^{\bigstar}\mathrm{\epsilon}_{n}$,
where half of the conjugate parameters are using negative conjugation instead
of positive conjugation; we set vertical conjugation
$c=\overline{a},d=\overline{b}$ in model $5^{\bigstar}\mathrm{\epsilon}_{v}$,
where parameters are conjugated in their vertical direction instead of the
diagonal direction; and we let $b=\overline{a},d=\overline{c}$ in model
$5^{\bigstar}\mathrm{\epsilon}_{h}$, the horizontal conjugation, where
parameters are conjugated in their horizontal direction.

The studies show that, first, by comparing the accuracy of
$5^{\bigstar}\mathrm{\epsilon}$ and $5^{\bigstar}\mathrm{E}_{r}$, we know that
reducing parameters in the regularization process hurts the accuracy
significantly, which indicates our conjugation method indeedly reserves
model’s ability even when the parameters are reduced. Second, the negative
conjugate model $5^{\bigstar}\mathrm{\epsilon}_{n}$ performs as well as
$5^{\bigstar}\mathrm{\epsilon}$. Last but not least, conjugate method should
choose suitable positions, e.g., $5^{\bigstar}\mathrm{\epsilon}_{v}$ and
$5^{\bigstar}\mathrm{\epsilon}_{h}$ do not perform as well.

###  5.3 Statistical Methods

To clarify the difference between original models and their conjugate models,
we took the highest mean as the best result, with the standard deviation as a
secondary judgement, and ultimately two-sample t-tests (See Table 6 in
Appendix) are conducted to decide whether two similar results can be
considered statistically equivalent and which is the best.

The two-sample t-test estimates if two population means are equal. Here we use
the t-test to judge if the Time or MRR means of two models are equal. We set
significance level $\alpha=0.05$, and the null hypothesis assumed that the two
data samples are from normal distributions with unknown and unequal variances.
$(h,p)$ means the result $h$ and $p$-value of the hypothesis test. $h=1,0$.
$h=1$ means rejection to the null hypothesis at the significance level
$\alpha$. $h=0$ indicates the failure to reject the null hypothesis at the
significance level $\alpha$. $p\in[0,1]$ is a probability of observing a test
statistic as extreme as, or more extreme than, the observed value under the
null hypothesis. A small $p$ value suggests suspicion on the validity of the
null hypothesis.

To prepare data for the t-tests, experiments on $\mathrm{ComplEx}$,
$\mathrm{Compl\epsilon x}$, $5^{\bigstar}\mathrm{E}$,
$5^{\bigstar}\mathrm{\epsilon}_{\nabla}$,
$5^{\bigstar}\mathrm{\epsilon}_{\diamondsuit}$ and
$5^{\bigstar}\mathrm{\epsilon}_{n}$ are conducted 17 times each. Apart from
that, the $5^{\bigstar}\mathrm{E}_{r}$, $5^{\bigstar}\mathrm{\epsilon}_{v}$,
$5^{\bigstar}\mathrm{\epsilon}_{h}$ apparently perform worse than the former
six models, thus the t-tests are not needed and their experiments are
conducted 5 times each.

Most of our t-tests were done among the original model and its conjugate
models as the distribution differs significantly if the base model is
different. However, since the accuracies among different models are similar on
the YAGO3-10 and WN18 datasets, we did several supplementary t-tests
(indicated in italics). The supplementary t-tests showed that the
distributions are different indeed when based on different original models
even though they appear to be similar. On the contrary, there exist similar
distributions among the results distribution of the original model and its
conjugate model.

###  5.4 Advantages of Parameter Sharing

Approching for the best accuracy in link prediction task has the trade off of
misinformation effect or inevitable high memory and time costs. Our parameter-
sharing method by using half conjugate parameters is very easy to apply and
can help control these costs, and potentially no trade off.

The original $\mathrm{ComplEx}$ and $5^{\bigstar}\mathrm{E}$ each has their
own strength in the perspective of accuracy on different datasets; while
$\mathrm{ComplEx}$ costs much more memory and time than
$5^{\bigstar}\mathrm{E}$ when compared under similar accuracy.

Our conjugate models consume less memory and time, and not inferior to the
original models in accuracy, which shows that our parameter-sharing method
makes a complex number represented KGE model superior to itself.

##  6 Conclusions

We propose using shared conjugate parameters for transformations, which
suffices to accurately represent the structures of the KG.

Our method can help scaling up KG with less carbon footprints easily: first,
it reduces parameter size and consumes less or at least comparable training
time while achieving consistent accuracy as the non-conjugate model, including
reaching state-of-the-art results; second, it is easily generalizable across
various complex number represented models.

##  7 Future Work

We would like to deal with the interpretation of the linear constrain of our
method. For example, to explore the effect of this method on different
relation patterns. Moreover, many KG applications like the work done by
Hongwimol et al. (2021) regard visual appeal as important, where appropriate
visuals can better convey the points of the data and facilitate user
interaction. We can see that the vector representations of transformed
entities using this method have more substantial geometric constrains (See
transformed entities illustrated in Figure 1). We want to explore if our
method can obtain better KG visualization.

## Acknowledgements

This work was supported by JSPS KAKENHI Grant Numbers 21H05054.

## References

  * Balazevic et al. (2019) Ivana Balazevic, Carl Allen, and Timothy Hospedales. 2019.  Multi-relational poincaré graph embeddings.  In _Advances in Neural Information Processing Systems_ , volume 32. Curran Associates, Inc.
  * Bordes et al. (2013) Antoine Bordes, Nicolas Usunier, Alberto Garcia-Duran, Jason Weston, and Oksana Yakhnenko. 2013.  Translating embeddings for modeling multi-relational data.  In _Advances in Neural Information Processing Systems_ , volume 26. Curran Associates, Inc.
  * Chami et al. (2020) Ines Chami, Adva Wolf, Da-Cheng Juan, Frederic Sala, Sujith Ravi, and Christopher Ré. 2020.  Low-dimensional hyperbolic knowledge graph embeddings.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 6901–6914, Online. Association for Computational Linguistics.
  * Dettmers et al. (2018) Tim Dettmers, Pasquale Minervini, Pontus Stenetorp, and Sebastian Riedel. 2018.  Convolutional 2d knowledge graph embeddings.  In _AAAI_.
  * Hayashi and Shimbo (2017) Katsuhiko Hayashi and Masashi Shimbo. 2017.  On the equivalence of holographic and complex embeddings for link prediction.  In _Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)_ , pages 554–559, Vancouver, Canada. Association for Computational Linguistics.
  * Hongwimol et al. (2021) Pollawat Hongwimol, Peeranuth Kehasukcharoen, Pasit Laohawarutchai, Piyawat Lertvittayakumjorn, Aik Beng Ng, Zhangsheng Lai, Timothy Liu, and Peerapon Vateekul. 2021.  ESRA: Explainable scientific research assistant.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing: System Demonstrations_ , pages 114–121, Online. Association for Computational Linguistics.
  * Ji et al. (2015) Guoliang Ji, Shizhu He, Liheng Xu, Kang Liu, and Jun Zhao. 2015.  Knowledge graph embedding via dynamic mapping matrix.  In _Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pages 687–696, Beijing, China. Association for Computational Linguistics.
  * Lin et al. (2015) Yankai Lin, Zhiyuan Liu, Maosong Sun, Yang Liu, and Xuan Zhu. 2015.  Learning entity and relation embeddings for knowledge graph completion.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 29(1).
  * Nayyeri et al. (2021) Mojtaba Nayyeri, Sahar Vahdati, Can Aykul, and Jens Lehmann. 2021.  5* knowledge graph embeddings with projective transformations.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 35(10):9064–9072.
  * Nickel et al. (2011) Maximilian Nickel, Volker Tresp, and Hans-Peter Kriegel. 2011.  A three-way model for collective learning on multi-relational data.  In _ICML_.
  * Noy et al. (2019) Natasha Noy, Yuqing Gao, Anshu Jain, Anant Narayanan, Alan Patterson, and Jamie Taylor. 2019.  Industry-scale knowledge graphs: Lessons and challenges.  _Communications of the ACM_ , 62 (8):36–43.
  * Toutanova and Chen (2015) Kristina Toutanova and Danqi Chen. 2015.  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, Beijing, China. Association for Computational Linguistics.
  * Trouillon et al. (2016) Théo Trouillon, Johannes Welbl, Sebastian Riedel, Éric Gaussier, and Guillaume Bouchard. 2016.  Complex embeddings for simple link prediction.  _CoRR_ , abs/1606.06357.
  * Yang et al. (2014) Bishan Yang, Wen-tau Yih, Xiaodong He, Jianfeng Gao, and Li Deng. 2014.  Embedding entities and relations for learning and inference in knowledge bases.

##  Appendix A Two-sample t-test

| Time t-test (h, p)
---|---
| $\mathrm{ComplEx}$ | $\mathrm{Compl\epsilon x}$ | $5^{\bigstar}\mathrm{E}$ | $5^{\bigstar}\mathrm{\epsilon}_{\nabla}$ | $5^{\bigstar}\mathrm{\epsilon}_{\diamondsuit}$ | $5^{\bigstar}\mathrm{\epsilon}_{n}$
$\mathrm{ComplEx}$ | - | (0, 2e-1) | - | - | - | -
$\mathrm{Compl\epsilon x}$ | - | - | - | - | - | -
$5^{\bigstar}\mathrm{E}$ | - | - | - | (1, 8e-3) | (0, 6e-1) | (1, 4e-5)
$5^{\bigstar}\mathrm{\epsilon}_{\nabla}$ | - | - | - | - | (0, 4e-1) | (0, 4e-1)
$5^{\bigstar}\mathrm{\epsilon}_{\diamondsuit}$ | - | - | - | - | - | (0, 2e-1)
$5^{\bigstar}\mathrm{\epsilon}_{n}$ | - | - | - | - | - | -
MRR t-test (h, p)
---
$\mathrm{ComplEx}$ | $\mathrm{Compl\epsilon x}$ | $5^{\bigstar}\mathrm{E}$ | $5^{\bigstar}\mathrm{\epsilon}_{\nabla}$ | $5^{\bigstar}\mathrm{\epsilon}_{\diamondsuit}$ | $5^{\bigstar}\mathrm{\epsilon}_{n}$
- | (1, 8e-17) | - | - | - | -
- | - | - | - | - | -
- | - | - | (1, 1e-12) | (1, 1e-14) | (1, 1e-10)
- | - | - | - | (1, 6e-3) | (1, 1e-2)
- | - | - | - | - | (1, 7e-6)
- | - | - | - | - | -

(a) FB15K-237

| Time t-test (h, p)
---|---
| $\mathrm{ComplEx}$ | $\mathrm{Compl\epsilon x}$ | $5^{\bigstar}\mathrm{E}$ | $5^{\bigstar}\mathrm{\epsilon}_{\nabla}$ | $5^{\bigstar}\mathrm{\epsilon}_{\diamondsuit}$ | $5^{\bigstar}\mathrm{\epsilon}_{n}$
$\mathrm{ComplEx}$ | - | (0, 6e-1) | - | - | - | -
$\mathrm{Compl\epsilon x}$ | - | - | - | - | - | -
$5^{\bigstar}\mathrm{E}$ | - | - | - | (1, 4e-11) | - | (1, 6e-3)
$5^{\bigstar}\mathrm{\epsilon}_{\nabla}$ | - | - | - | - | - | (1, 2e-2)
$5^{\bigstar}\mathrm{\epsilon}_{\diamondsuit}$ | - | - | - | - | - | -
$5^{\bigstar}\mathrm{\epsilon}_{n}$ | - | - | - | - | - | -
MRR t-test (h, p)
---
$\mathrm{ComplEx}$ | $\mathrm{Compl\epsilon x}$ | $5^{\bigstar}\mathrm{E}$ | $5^{\bigstar}\mathrm{\epsilon}_{\nabla}$ | $5^{\bigstar}\mathrm{\epsilon}_{\diamondsuit}$ | $5^{\bigstar}\mathrm{\epsilon}_{n}$
- | (1, 3e-28) | - | - | - | -
- | - | - | - | - | -
- | - | - | (1, 9e-11) | - | (1, 2e-15)
- | - | - | - | - | (1, 4e-21)
- | - | - | - | - | -
- | - | - | - | - | -

(b) WN18RR

| Time t-test (h, p)
---|---
| $\mathrm{ComplEx}$ | $\mathrm{Compl\epsilon x}$ | $5^{\bigstar}\mathrm{E}$ | $5^{\bigstar}\mathrm{\epsilon}_{\nabla}$ | $5^{\bigstar}\mathrm{\epsilon}_{\diamondsuit}$ | $5^{\bigstar}\mathrm{\epsilon}_{n}$
$\mathrm{ComplEx}$ | - | (0, 4e-1) | - | - | - | -
$\mathrm{Compl\epsilon x}$ | - | - | - | - | - | -
$5^{\bigstar}\mathrm{E}$ | - | - | - | (1, 5e-47) | - | (1, 1e-46)
$5^{\bigstar}\mathrm{\epsilon}_{\nabla}$ | - | - | - | - | - | (0, 7e-1)
$5^{\bigstar}\mathrm{\epsilon}_{\diamondsuit}$ | - | - | - | - | - | -
$5^{\bigstar}\mathrm{\epsilon}_{n}$ | - | - | - | - | - | -
MRR t-test (h, p)
---
$\mathrm{ComplEx}$ | $\mathrm{Compl\epsilon x}$ | $5^{\bigstar}\mathrm{E}$ | $5^{\bigstar}\mathrm{\epsilon}_{\nabla}$ | $5^{\bigstar}\mathrm{\epsilon}_{\diamondsuit}$ | $5^{\bigstar}\mathrm{\epsilon}_{n}$
- | (1, 3e-6) | (1, 2e-7) | (1, 7e-3) | - | (1, 3e-8)
- | - | - | - | - | -
- | - |  | (1, 5e-4) | - | (0, 6e-1)
- | - | - | - | - | (1, 3e-4)
- | - | - | - | - | -
- | - | - | - | - | -

(c) YAGO3-10

| Time t-test (h, p)
---|---
| $\mathrm{ComplEx}$ | $\mathrm{Compl\epsilon x}$ | $5^{\bigstar}\mathrm{E}$ | $5^{\bigstar}\mathrm{\epsilon}_{\nabla}$ | $5^{\bigstar}\mathrm{\epsilon}_{\diamondsuit}$ | $5^{\bigstar}\mathrm{\epsilon}_{n}$
$\mathrm{ComplEx}$ | - | (0, 1e-1) | - | - | - | -
$\mathrm{Compl\epsilon x}$ | - | - | - | - | - | -
$5^{\bigstar}\mathrm{E}$ | - | - | - | (1, 2e-6) | (1, 3e-5) | (1, 8e-3)
$5^{\bigstar}\mathrm{\epsilon}_{\nabla}$ | - | - | - | - | (1, 3e-2) | (0, 1e-1)
$5^{\bigstar}\mathrm{\epsilon}_{\diamondsuit}$ | - | - | - | - | - | (0, 5e-1)
$5^{\bigstar}\mathrm{\epsilon}_{n}$ | - | - | - | - | - | -
MRR t-test (h, p)
---
$\mathrm{ComplEx}$ | $\mathrm{Compl\epsilon x}$ | $5^{\bigstar}\mathrm{E}$ | $5^{\bigstar}\mathrm{\epsilon}_{\nabla}$ | $5^{\bigstar}\mathrm{\epsilon}_{\diamondsuit}$ | $5^{\bigstar}\mathrm{\epsilon}_{n}$
- | (0, 8e-2) | - | - | - | -
- | - | - | - | - | -
- | - | - | (1, 2e-21) | (1, 2e-2) | (1, 6e-21)
- | - | - | - | (1, 1e-23) | (1, 3e-9)
- | - | - | - | - | (1, 3e-22)
- | - | - | - | - | -

(d) FB15K

| Time t-test (h, p)
---|---
| $\mathrm{ComplEx}$ | $\mathrm{Compl\epsilon x}$ | $5^{\bigstar}\mathrm{E}$ | $5^{\bigstar}\mathrm{\epsilon}_{\nabla}$ | $5^{\bigstar}\mathrm{\epsilon}_{\diamondsuit}$ | $5^{\bigstar}\mathrm{\epsilon}_{n}$
$\mathrm{ComplEx}$ | - | (0, 5e-1) | - | - | - | -
$\mathrm{Compl\epsilon x}$ | - | - | - | - | - | -
$5^{\bigstar}\mathrm{E}$ | - | - | - | (1, 1e-7) | (1, 4e-9) | (1, 6e-9)
$5^{\bigstar}\mathrm{\epsilon}_{\nabla}$ | - | - | - | - | (0, 2e-1) | (0, 8e-2)
$5^{\bigstar}\mathrm{\epsilon}_{\diamondsuit}$ | - | - | - | - | - | (0, 1e-1)
$5^{\bigstar}\mathrm{\epsilon}_{n}$ | - | - | - | - | - | -
MRR t-test (h, p)
---
$\mathrm{ComplEx}$ | $\mathrm{Compl\epsilon x}$ | $5^{\bigstar}\mathrm{E}$ | $5^{\bigstar}\mathrm{\epsilon}_{\nabla}$ | $5^{\bigstar}\mathrm{\epsilon}_{\diamondsuit}$ | $5^{\bigstar}\mathrm{\epsilon}_{n}$
- | (0, 8e-2) | - | - | (1, 1e-17) | (1, 1e-13)
- | - | - | - | (1, 5e-21) | (1, 2e-16)
- | - |  | (1, 3e-14) | (1, 5e-5) | (0, 2e-1)
- | - | - | - | (1, 4e-15) | (1, 5e-14)
- | - | - | - | - | (1, 3e-5)
- | - | - | - | - | -

(e) WN18 Table 6: t-test (h, p) of Time and MRR on FB15K-237, WN18RR,
YAGO3-10, FB15K and WN18 datasets.


Stochastic Characteristics and Simulation of the Random Waypoint Mobility
Model

Ahuja, Aditya 1, Venkateswarlu K. 1, and Venkata Krishna, P. 1

1School of Computing Science and Engineering, VIT University, Vellore - 632
014

<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
## Abstract

Simulation results for Mobile Ad-Hoc Networks (MANETs) are fundamentally
governed by the underlying Mobility Model. Thus it is imperative to find
whether events functionally dependent on the mobility model ‘converge’ to well
defined functions or constants. This shall ensure the long-run consistency
among simulation performed by disparate parties. This paper reviews a work on
the discrete Random Waypoint Mobility Model (RWMM), addressing its long run
stochastic stability. It is proved that each model in the targeted discrete
class of the RWMM satisfies Birkhoff’s pointwise ergodic theorem [13], and
hence time averaged functions on the mobility model surely converge. We also
simulate the most common and general version of the RWMM to give insight into
its working.

Keywords: Random Waypoint Mobility Model, Asymptotic Mean Stationary, Ergodic,
Simulation

## Introduction

Mobility models are used for the generation of node movement in simulations of
MANETs. Protocol development is a consequence of such a simulation. The
probabilistic aspects of the founding mobility model has direct implications
on the simulation results. Many papers [2]-[5] have already concluded that
stochastically unstable mobility models shall result in simulation results
that diverge in time.

The Random Trip Mobility Model, through the presence of a unique stationary
distribution for the location of nodes, has already been proved to be stable
[5]. _The work presented in this paper is purely a review of the stability of
the discrete version of the RWMM proved by Timo, Blackmore and Hanlen_ [1].
Therein the notion of stability is considered to be the satisfaction of
Birkhoff’s Pointwise Ergodic Theorem by the mobility model. If to the contrary
the mobility model is unstable, the simulation results are bound to be
unreliable.

The stimulus for this line of work is that the stability or lack thereof of
the mobility model is possibly passed up the layers of the protocol stack. For
instance the DSR protocol preserves the mobility model’s stability [6]: if the
node location random process is stable, then so is the route selection random
process. The consequence of this is that the strong law of large numbers also
holds for the simulations at the network layer.

A mobility model is quantified using a random process. It is stationary if the
set of probability laws regulating the movement of the nodes are independent
of time. Many works have come up with the transformation of non-stationary
models into (in some places pointwise ergodic theorem satisfying) stationary
models with the motivation that the strong law of large numbers may be
applicable.

The classic RWM model does display starting transients and local
nonstationarity. Thus we analyze its properties by means of imposing a
mathematically weaker ‘asymptotic stationarity’ property. A random process,
the mean of which is governed asymptotically by a process with a stationary
distribution is called Asymptotically Mean Stationary (AMS). It has been
proved [8][Theorem 1] that a random process is AMS if and only if it satisfies
Birkhoff’s pointwise ergodic theorem. By consequence a mobility model is
stable if and only if it is AMS [1].

In the classic RWMM [1], every node, using an independent and identically
uniformly distributed (IID) random process $\\{W_{k}\\}_{k=0}^{\infty}$,
selects a sequence of waypoints $\mathbf{w}=w_{0},w_{1},w_{2},...$. For every
pair $(w_{i},w_{i+1}),i\in\mathcal{Z^{*}}$, the node chooses a speed randomly
and uniformly distributed from the closed interval $[min\\_s,max\\_s]$. At
this chosen speed it then travels in a straight line from $w_{i}$ to
$w_{i+1}$.

In this review, the main result addressed is: a) The general discrete class of
the RWMM is asymptotically mean stationary (by virtue of which it is stable)
and ergodic. b) For stable node movement the following conditions suffice -
(i) Node waypoint selection is an AMS random process, (ii) Speed selection
random process is stationary.

This paper is organized as follows. The next section introduces the
preliminaries. Following that we describe the general RWMM. Next is the
contribution of the base paper in the form of a theorem. Simulation results
for the classic case and conclusion end this paper.

## Preliminaries

We will adopt the dynamical systems [9]-[10] model for a random process. Given
a discrete finite alphabet $\mathcal{X}$, let
$\mathbf{X}=\\{X_{k}\\}_{k=0}^{\infty}$ be the associated discrete time random
process. The distribution of $\\{X_{n}\\}_{n=0}^{\infty}$ is the set
$\\{\mu^{(k)}:k\geq 0\\}$ where $\mu^{(k)}$ is the probability measure on
$\mathcal{X}^{k}$ given by:
$\mu^{(k)}(x_{0}^{k-1})=Pr[X_{0}=x_{0},X_{1}=x_{1},...,X_{k-1}=x_{k-1}]$

In order to simplify our work, we use the Kolmogorov Representation Theorem
(where certain consistency conditions are satisfied) [9][Theorem I.1.2]. This
enables us to replace the distribution with a unique probability measure $\mu$
on the space $\mathcal{X}^{\infty}=\Pi_{i=0}^{\infty}\mathcal{X}$. Throughout
we shall be dealing with cylinder sets as elementary events:
$[x_{m}^{n}]=\\{\mathbf{\bar{x}}:\bar{x_{i}}=x_{i},m\leq i\leq n\\}$. The
$\sigma$-algebra $\mathcal{F_{X^{\infty}}}$ is generated using these cylinder
sets. Time is incorporated using the shift transform
$T_{\mathcal{X}}^{k}=x_{k},x_{k+1},x_{k+2},...,k\in\mathcal{Z^{*}}$.
Eventually we result with the dynamical system
$(\mathcal{X^{\infty}},\mathcal{F_{X^{\infty}}},\mu,T_{\mathcal{X}})$ which is
related to the original random process by
$\\{X_{k}\\}_{k=0}^{\infty}=\\{\Pi_{0}(T_{\mathcal{X}}^{k}\mathbf{x})\\}_{k=0}^{\infty}$,
$\Pi_{0}\mathbf{x}=x_{0}$.

Suppose we have a mobility model quantified by the random process
$\\{X_{k}\\}_{k=0}^{\infty}$ and capture the location of each node for the
first $k$ time instances of a simulation given by
$x_{0}^{k-1}=x_{0},x_{1},x_{2},...,x_{k-1}$. The dynamical system associated
with this stochastic experiment is
$(\mathcal{X^{\infty}},\mathcal{F_{X^{\infty}}},\mu,T_{\mathcal{X}})$ and the
trajectory captured is the elementary event
$[x_{0}^{k-1}]\in\mathcal{F_{X^{\infty}}}$. If variable length shift must be
considered
$T_{\mathcal{X^{*}}}\mathbf{x}=T_{\mathcal{X}}^{f\mathbf{(x)}}\mathbf{x}$ as
is necessitated in certain cases by the random processes associated with the
updation of routing tables of network routers, we may study the probabilistic
properties of
$(\mathcal{X^{\infty}},\mathcal{F_{X^{\infty}}},\mu,T_{\mathcal{X^{*}}})$.

Now we come up with certain definitions and lemmas lifted from the base work
which serve as the foundation for future proof developments.
_Definition 1 (Stationarity)_[1]: The system
$(\mathcal{X^{\infty}},\mathcal{F_{X^{\infty}}},\mu,T_{\mathcal{X}})$ is
called stationary, and $T_{\mathcal{X}}$ is said to be measure preserving if,
$\forall A\in\mathcal{F_{X^{\infty}}}$, $\mu(A)=\mu(T^{-1}A)$ .
_Definition 2 (Ergodicity)_[1][13]: The stationary system
$(\mathcal{X^{\infty}},\mathcal{F_{X^{\infty}}},\mu,T_{\mathcal{X}})$ is said
to be ergodic if $A=T^{-1}A\Rightarrow\mu(A)=0$ or $1$ . Equivalently,
$(\mathcal{X^{\infty}},\mathcal{F_{X^{\infty}}},\mu,T_{\mathcal{X}})$ is
ergodic iff $\forall f\in L^{1}(\mu)$ the limit
$<f>=<f>(\mathbf{x})=\lim\limits_{n\to\infty}\frac{1}{n}\sum\limits_{k=0}^{n-1}f(T^{k}_{\mathcal{X}}\mathbf{x})$
is a constant almost everywhere in $\mu$.
_Definition 3 (Stability)_[1]: A mobility model associated with the random
process $(\mathcal{X^{\infty}},\mathcal{F_{X^{\infty}}},\mu,T_{\mathcal{X}})$
is said to be stable if for all bounded and measurable $f$, the limit
$<f>(\mathbf{x})=\lim\limits_{n\to\infty}\frac{1}{n}\sum\limits_{k=0}^{n-1}f(T^{k}_{\mathcal{X}}\mathbf{x})$
exists almost everywhere in $\mu$.
_Definition 4 (Asymptotic Mean Stationarity)_[1]: The system
$(\mathcal{X^{\infty}},\mathcal{F_{X^{\infty}}},\mu,T_{\mathcal{X}})$ is said
to be asymptotic mean stationary (AMS) if, $\forall
A\in\mathcal{F_{X^{\infty}}}$ the limit
$\overline{\mu}(A)=\lim\limits_{n\to\infty}\frac{1}{n}\sum\limits_{k=0}^{n-1}\mu(T^{-k}_{\mathcal{X}}A)$
exists.
Here the probability measure $\overline{\mu}$ is defined on the measurable
space $(\mathcal{X^{\infty}},\mathcal{F_{X^{\infty}}})$. It is called the
stationary mean of $\mu$ and describes the average of the long run behaviour
of the system.
_Lemma 1 (Birkhoff’s Pointwise Ergodic Theorem)_ [1][13]: Let the dynamical
system $(\mathcal{X^{\infty}},\mathcal{F_{X^{\infty}}},\mu,T_{\mathcal{X}})$
have $T_{\mathcal{X}}$ as a measure preserving map, and let $f$ be measurable
with $E(|f|)<+\infty$. Then
$\lim\limits_{n\to\infty}\frac{1}{n}\sum\limits_{k=0}^{n-1}f(T^{k}_{\mathcal{X}}\mathbf{x})=E(f|\mathcal{C})$.
Here $\mathcal{C}$ is the $\sigma$-algebra of invariant sets of
$T_{\mathcal{X}}$ . If the random process is ergodic, then $\mathcal{C}$ is
the trivial $\sigma$-algebra, and $E(f|\mathcal{C})=E(f)$ which is a constant.
It has been proved [8] that asymptotic mean stationarity is both a necessary
and sufficient condition for the pointwise ergodic theorem.
_Lemma 2 (AMS Pointwise Ergodic Theorem)_ [8][Theorem 1]: A dynamical system
$(\mathcal{X^{\infty}},\mathcal{F_{X^{\infty}}},\mu,T_{\mathcal{X}})$ is AMS
iff for all measurable $f$ with a finite expectation, the limit
$<f>(\mathbf{x})=\lim\limits_{n\to\infty}\frac{1}{n}\sum\limits_{k=0}^{n-1}f(T^{k}_{\mathcal{X}}\mathbf{x})$
exists almost everywhere in $\mu$.
Eventually we conclude, using definitions 3,4 and lemma 2:
Stability: A mobility model with
$(\mathcal{X^{\infty}},\mathcal{F_{X^{\infty}}},\mu)$ as the associated
probability space is stable with respect to $T_{\mathcal{X}}$ iff
$(\mathcal{X^{\infty}},\mathcal{F_{X^{\infty}}},\mu,T_{\mathcal{X}})$ is AMS.

## Discrete Version of the RWMM

We now initiate the study of a discrete time space version of the Random
Waypoint Mobility Model. Consider a MANET with each mobile node in the set
$\mathcal{V}=\\{v_{1},v_{2},...,v_{\mathcal{|V|}}\\}$ located in a discrete
finite geographical area described by the set $\mathcal{S}$. The following are
the random processes to exposit the discrete RWMM.

### Waypoint Random Process Per Node

From the geographical space $\mathcal{S}$, each mobile node $v\in\mathcal{V}$
selects an infinite tuple of waypoints $\mathbf{w}=w_{0},w_{1},w_{2},...$
randomly. Let us denote the waypoint selection random process as
$\mathbf{W}=\\{W_{k}\\}_{k=0}^{\infty}$ with the corresponding dynamical
system as
$(\mathcal{W^{\infty}},\mathcal{F_{W^{\infty}}},\mu_{\mathbf{w}},T_{\mathcal{W}})$,
and also $\mathcal{W=S}$.
_RWMM Correlation :_ In the classic RWM model, waypoint selection random
process is IID, and in most cases uniformly distributed. So the stochastic
process
$(\mathcal{W^{\infty}},\mathcal{F_{W^{\infty}}},\mu_{\mathbf{w}},T_{\mathcal{W}})$
is a Bernoulli Scheme[14].

### Path Random Process Per Node

Figure 1: Different paths corresponding to discrete time-space equivalent of
different speeds

In the classic RWMM, whenever an arbitrary node selects a sequence of
waypoints $\mathbf{w}$, then for each consecutive pair
$(w_{i},w_{i+1}),i\in\mathcal{Z^{*}}$, it also selects a speed uniformly
distributed from $[min\\_s,max\\_s]$ and traverses the straight line path
between $w_{i}$ and $w_{i+1}$. In discretized time and space, snapshot of the
node’s position per instance of time is taken during its trip between
waypoints. This shall result in a random path with finite possibilities per
waypoint pair $(w_{i},w_{i+1})$ (figure 1). For each combination of waypoints
$(w,w^{\prime})\in\mathcal{W\times W}$ construct the set of all paths
$\mathcal{P}_{w,w^{\prime}}$ and take the union of all such sets so as to
obtain all admissible paths $\mathcal{P}$: $\hskip
15.0pt\mathcal{P}_{w,w^{\prime}}=\\{p_{1},p_{2},p_{3},...,p_{|\mathcal{P}_{w,w^{\prime}}|}\\}$,
$\hskip 15.0pt\mathcal{P}=\bigcup\limits_{(w,\acute{w})\in\mathcal{W\times
W}}\mathcal{P}_{w,\acute{w}}$. In order to describe the stochastic process
$\mathbf{P}=\\{P_{k}\\}_{k=0}^{\infty}$, noting that $\mathbf{P}$ is
conditioned on $\mathbf{W}$, we first define the set of permitted path
sequences $\mathcal{P}_{\mathbf{w}}^{\infty}\subset\mathcal{P}^{\infty}$ given
$\mathbf{w}$ as
$\mathcal{P}_{\mathbf{w}}^{\infty}=\\{\mathbf{p}\in\mathcal{P}^{\infty}:p_{i}\in\mathcal{P}_{w_{i},w_{i+1}},\forall
i\in\mathcal{Z^{*}}\\}$. Here again let $\mathcal{F_{P^{\infty}}}$ be the
$\sigma$-algebra generated from $p_{m}^{n}\in\mathcal{P^{\infty}}$. Defining a
collection of probability measures
$\nu_{\mathbf{wp}}=\\{\nu_{\mathbf{w}}:\mathbf{w}\in\mathcal{W^{\infty}},\nu_{\mathbf{w}}(\mathcal{P}_{\mathbf{w}}^{\infty})=1\\}$
results in the channel [11] $(\mathcal{W},\nu_{\mathbf{wp}},\mathcal{P})$.
_Definition 5 (Stationary Channel)_[1]: If
$\forall\mathbf{w}\in\mathcal{W^{\infty}},\forall
A\in\mathcal{F_{P^{\infty}}}$, $\hskip
6.0pt\nu_{T_{\mathcal{W}}\mathbf{w}}(A)=\nu_{\mathbf{w}}(T_{\mathcal{P}}^{-1}A)$
, the channel $(\mathcal{W},\nu_{\mathbf{wp}},\mathcal{P})$ is said to be
$(T_{\mathcal{W}},T_{\mathcal{P}})$ stationary.
_RWMM Correlation:_ Considering elementary events
$[p_{0}^{n-1}]\in\mathcal{F_{P^{\infty}}}$:

$\nu_{\mathbf{w}}([p_{0}^{n-1}])=\prod_{i=0}^{n-1}\frac{1}{|\mathcal{P}_{w_{i},w_{i+1}}|}\hskip
10.0ptp_{i}\in\mathcal{P}_{w_{i},w_{i+1}},0\leq i\leq n-1$

And $\nu_{\mathbf{w}}$ is zero otherwise. To prove stationarity, see that on
the transformed $T_{\mathcal{W}}\mathbf{w}$ the non-zero probability for
$[p_{0}^{n-1}]$ is given by:

$\nu_{T_{\mathcal{W}}\mathbf{w}}([p_{0}^{n-1}])=\prod_{i=0}^{n-1}\frac{1}{|\mathcal{P}_{w_{i+1},w_{i+2}}|}\hskip
10.0ptp_{i}\in\mathcal{P}_{w_{i+1},w_{i+2}},0\leq i\leq n-1$

And if $T_{\mathcal{P}}^{-1}[p_{0}^{n-1}]=[\bar{p}_{1}^{n}]$ with
$\bar{p}_{m+1}=p_{m},0\leq m<n$ :

$\nu_{\mathbf{w}}(T_{\mathcal{P}}^{-1}[p_{0}^{n-1}])=\nu_{\mathbf{w}}([\bar{p}_{1}^{n}])=\prod_{i=0}^{n-1}\frac{1}{|\mathcal{P}_{w_{i+1},w_{i+2}}|}\hskip
10.0ptp_{i}\in\mathcal{P}_{w_{i+1},w_{i+2}},0\leq i\leq n-1$

The last two equations are equal which proves that the channel is stationary.

Next it is proved that the channel is output mixing and consequently ergodic.
A channel is said to be output mixing[1] if, $\forall
A,B\in\mathcal{F_{P^{\infty}}},\forall\mathbf{w}\in\mathcal{W^{\infty}}$222Incorrect
sigma field in [1]:

$\lim_{n\to\infty}\left|\nu_{\mathbf{w}}\left(T_{\mathcal{P}}^{-n}A\bigcap
B\right)-\nu_{\mathbf{w}}(T_{\mathcal{P}}^{-n}A)\nu_{\mathbf{w}}(B)\right|=0$

The elementary events in case of the general RWMM are decoupled for $\tau\geq
b$ for $[p_{0}^{a-1}],[p_{0}^{b-1}]\in\mathcal{F_{P^{\infty}}}$ in the
following equation:

$\nu_{\mathbf{w}}\left(T_{\mathcal{P}}^{-\tau}[p_{0}^{a-1}]\bigcap[p_{0}^{b-1}]\right)=\nu_{\mathbf{w}}\left([\acute{p}_{\tau}^{\tau+a-1}]\bigcap[p_{0}^{b-1}]\right)=$
$\left(\prod_{i=\tau}^{\tau+a-2}\frac{1}{|\mathcal{P}_{w_{i+1},w_{i+2}}|}\right)\left(\prod_{j=0}^{b-2}\frac{1}{|\mathcal{P}_{w_{j+1},w_{j+2}}|}\right)\begin{array}[]{c}\acute{p}_{i}\in\mathcal{P}_{w_{i+1},w_{i+2}},\tau\leq
i\leq\tau+a-1\\\ p_{j}\in\mathcal{P}_{w_{j+1},w_{j+2}},0\leq j\leq
b-1\end{array}$
$=\nu_{\mathbf{w}}\left(T_{\mathcal{P}}^{-\tau}[p_{0}^{a-1}]\right)\nu_{\mathbf{w}}\left([p_{0}^{b-1}]\right)$

Hence the channel is output mixing and ergodic [11][Lemma 9.4.3].

Finally we define a probability measure $\mu_{\mathbf{p}}$ conditioning it on
the waypoint selection probability measure $\mu_{\mathbf{w}}$:
$\mu_{\mathbf{p}}(A)=\sum\limits_{\mathbf{w^{\prime}}\in\mathcal{W}^{\infty}}\mu_{\mathbf{w}}(\mathbf{w^{\prime}})\nu_{\mathbf{w^{\prime}}}(A),\hskip
5.0pt\forall A\in\mathcal{F_{P^{\infty}}}$ . Thus we result with
$(\mathcal{P^{\infty}},\mathcal{F_{P^{\infty}}},\mu_{\mathbf{p}},T_{\mathcal{P}})$
as the corresponding dynamical system for
$\mathbf{P}=\\{P_{k}\\}_{k=0}^{\infty}$.

### Location Random Process per node

We define the time taken $t(i)$ to reach $w_{i}$ from $w_{0}$ as a function of
the first $i$ paths $p_{0},p_{1},...,p_{i-1}$. We assume that each path length
$l(p)$ is a positive finite quantity. So $t(i)=\sum_{j=0}^{i-1}l(p_{j}),\hskip
5.0pti\geq 1$. Let the $i^{th}$ path $p_{i}$ take the form
$s_{t(i)},s_{t(i)+1},s_{t(i)+2},...,s_{t(i+1)}$, with $s_{j}\in\mathcal{S}$
and $s_{t(k)}=w_{k}$. Correlating with the given paths’ sequence $\mathbf{p}$,
we arrive at node location sequence $\mathbf{s}=s_{0},s_{1},...$. Thus we have
the node location random process $\mathbf{S}=\\{S_{k}\\}_{k=0}^{\infty}$ given
by the dynamical system
$(\mathcal{S^{\infty}},\mathcal{F_{S^{\infty}}},\mu_{\mathbf{s}},T_{\mathcal{S}})$.

### Location Random Process for all nodes

Consider the $\mathcal{|V|}$ tuple
$X_{n}=(S_{n,1},S_{n,2},...,S_{n,\mathcal{|V|}})$, with $S_{i,j}$ denoting
node $j$’s location at time $i$. This random variable’s alphabet is
$\mathcal{X}=\mathcal{S^{|V|}}$. Define
$(\mathcal{X^{\infty}},\mathcal{F_{X^{\infty}}},\mu_{\mathbf{p}},T_{\mathcal{X}})$
as the dynamical system for the random process $\\{X_{k}\\}_{k=0}^{\infty}$.

## Main Result and its Proof

Theorem [1]: Suppose the nodes
$\mathcal{V}=\\{v_{1},v_{2},...,v_{\mathcal{|V|}}\\}$ move in agreement with
the discrete RWMM already defined. Let $\mathbf{W}_{v}$ denote the waypoint
selection random process for node $v$ and $\mathbf{P}_{v}$ be the
corresponding path random process. Let
$(\mathcal{W}_{v},\nu_{\mathbf{wp}},\mathcal{P}_{v})$ denote the path and
waypoint stochastic processes’ connecting channel and let $\mathbf{X}$ denote
the location random process for all nodes. Then

  * •

If $\forall v\in\mathcal{V}$, $\mathbf{W}_{v}$ is AMS and the channel
$(\mathcal{W}_{v},\nu_{\mathbf{wp}},\mathcal{P}_{v})$ is stationary, then
$\mathbf{X}$ is AMS and stable.

  * •

If $\forall v\in\mathcal{V}$, $\mathbf{W}_{v}$ is ergodic and the channel
$(\mathcal{W}_{v},\nu_{\mathbf{wp}},\mathcal{P}_{v})$ is ergodic, then
$\mathbf{X}$ is ergodic.

Proof Sketch [1]:
Dropping the redundant subscript $v$ henceforth.

_Lemma A: If $\mathbf{W}$ is AMS and ergodic and
$(\mathcal{W},\nu_{\mathbf{wp}},\mathcal{P})$ is stationary and ergodic, then
$\mathbf{P}$ is AMS and ergodic._
_Proof:_ [11][Lemmas 9.3.1, 9.3.3] prove this lemma directly as the AMS and
ergodic waypoint random process and the path random process are connected by a
stationary, ergodic channel.

_Lemma B: If $\mathbf{P}$ is ergodic then $\mathbf{S}$ is ergodic._
_Proof:_ Given
$(\mathcal{P^{\infty}},\mathcal{F_{P^{\infty}}},\mu_{\mathbf{p}},T_{\mathcal{P}})$
is AMS. For all $p\in\mathcal{P}$ let $l(p)$ denote path length, let
$L=\max\\{l(p):\mathbf{p}\in\mathcal{P}\\}$ and let
$f:\mathcal{P}\to\bigcup_{i=1}^{L}\mathcal{S}^{i}$ be the breakdown of a path
to its corresponding geographic cells -
$f(p)=s_{0},s_{1},s_{2},...,s_{l(p)-1}$. So
$\mathbf{S}=\\{S_{k}\\}_{k=0}^{\infty}=f(P_{0}),f(P_{1}),f(P_{2}),...=S_{0},S_{1},...,S_{l(P_{0})},...,S_{l(P_{0})+l(P_{1})},...$.
For ease of working, define the encoder
$F:\mathcal{P}^{\infty}\to\mathcal{S}^{\infty}$ as
$\mathbf{s}=F(\mathbf{p})=f(p_{0}),f(p_{1}),f(p_{2}),...$. Now $\forall
A\in\mathcal{F_{S^{\infty}}},\mu_{\mathbf{s}}(A)=\mu_{p}(F^{-1}A)$. Here the
mapping $F$ is many to one.
Next it is described a pseudo-inverse
$G^{-1}:\hat{\mathcal{S}}^{\infty}\to\hat{\mathcal{P}}^{\infty}$ as
$G^{-1}\mathbf{s}=\mathbf{p_{s}}$ where
$\hat{\mathcal{P}}^{\infty}\subseteq\mathcal{P}^{\infty}$ according to
[8][Theorem 1] having full measure
$\mu_{\mathbf{p}}(\hat{\mathcal{P}}^{\infty})=1$ such that every bounded
measurable function on this set converges; $\hat{\mathcal{S}}^{\infty}$ is the
induced range of $F$ on $\hat{\mathcal{P}}^{\infty}$ and $\mathbf{p_{s}}$ is a
representative from the partition of $\hat{\mathcal{P}}^{\infty}$ induced by
$\mathbf{s}\in\hat{\mathcal{S}}^{\infty}$.
Define the length of the first $n$ paths in
$\mathbf{p}\in\mathcal{P}^{\infty}$ as
$\gamma_{\mathbf{p}}(n)=\sum_{i=0}^{n-1}l(p_{i})$111Wrong limit in [1]. Then
the variable length shift
$T_{\mathcal{S^{*}}}:\mathcal{S}^{\infty}\to\mathcal{S}^{\infty}$ is given by
$T_{\mathcal{S^{*}}}^{n}\mathbf{s}=T_{\mathcal{S}}^{\Gamma_{n}(\mathbf{s})}\mathbf{s}$
where

$\Gamma_{n}(\mathbf{s})=\begin{array}[]{c}\gamma_{G^{-1}(\mathbf{s})}(n),\hskip
10.0pt\mathbf{s}\in\hat{\mathcal{S^{*}}}\\\ 1,\hskip
50.0pt\mathbf{s}\notin\hat{\mathcal{S^{*}}}\end{array}$

Eventually it is proved that
$\lim_{n\to\infty}\frac{1}{n}\sum_{k=0}^{n-1}h(T_{\mathcal{S^{*}}}\mathbf{s})$
exists $\forall\mathbf{s}\in\hat{\mathcal{S^{*}}}$ and for all bounded
measurable $h$. Thus
$(\mathcal{S^{\infty}},\mathcal{F_{S^{\infty}}},\mu_{\mathbf{s}},T_{\mathcal{S^{*}}})$
is AMS. Note that one $T_{\mathcal{S^{*}}}$ shift is equivalent to one path
shift.
_Sublemma: If
$(\mathcal{S^{\infty}},\mathcal{F_{S^{\infty}}},\mu_{\mathbf{s}},T_{\mathcal{S^{*}}})$
is AMS with stationary mean $\bar{\mu}_{\mathbf{s}}^{*}$ then
$(\mathcal{S^{\infty}},\mathcal{F_{S^{\infty}}},\mu_{\mathbf{s}},T_{\mathcal{S}})$
is AMS where
$T_{\mathcal{S^{*}}}\mathbf{s}=T_{\mathcal{S}}^{\gamma(\mathbf{s})}\mathbf{s}$
and $1\leq\gamma(\mathbf{s})\leq L\hskip 3.0pt$. 222Typographical error in [1]
for $T_{\mathcal{S^{*}}}$ _
Define a new measure (inspired from [8][Ex.6]):

$\bar{\mu}_{\mathbf{s}}(A)=\frac{1}{E_{\bar{\mu}_{\mathbf{s}}}[\gamma(\mathbf{s})]}\sum_{k=1}^{L}\sum_{i=0}^{k-1}\bar{\mu}_{\mathbf{s}}^{*}(T_{\mathcal{S}}^{-i}A\cap\Delta_{k}^{-1})$

Here
$\Delta_{k}^{-1}=\\{\mathbf{s}\in\mathcal{S^{\infty}}:\gamma(\mathbf{s})=k\\}$,
and $\\{\Delta_{k}^{-1}\\}_{k=1}^{L}$ is a partition of $\mathcal{S^{\infty}}$
[8]. Thus we have
$T_{\mathcal{S^{*}}}^{-1}A=\cup_{k=1}^{L}(T_{\mathcal{S}}^{-k}A\cap\Delta_{k}^{-1})$.
We also have

$\bar{\mu}_{\mathbf{s}}^{*}(T_{\mathcal{S^{*}}}^{-1}A)=\bar{\mu}_{\mathbf{s}}^{*}(A)=\sum_{k=1}^{L}\bar{\mu}_{\mathbf{s}}^{*}(A\cap\Delta_{k}^{-1})=\sum_{k=1}^{L}\bar{\mu}_{\mathbf{s}}^{*}(T_{\mathcal{S}}^{-k}A\cap\Delta_{k}^{-1})$

The first two terms are equal by virtue of transformation invariance of
$\bar{\mu}_{\mathbf{s}}^{*}$. The next two terms are equal by virtue of
intersection distribution of $A$ on $\Delta_{k}^{-1}$. The first and the last
term are equal from the immediately preceding correlation between
$T_{\mathcal{S^{*}}}$ and $T_{\mathcal{S}}$. Substituting
$T_{\mathcal{S}}^{-1}A$ for $A$ in the definition of $\bar{\mu}_{\mathbf{s}}$
and using the above equation we arrive at the $T_{\mathcal{S}}$ invariance of
$\bar{\mu}_{\mathbf{s}}$. Further it is shown that $\bar{\mu}_{\mathbf{s}}$
asymptotically dominates $\bar{\mu}_{\mathbf{s}}^{*}$ under $T_{\mathcal{S}}$
which when taken with the $T_{\mathcal{S}}$ invariance of
$\bar{\mu}_{\mathbf{s}}$ and [8][Theorem 2] proves that
$\bar{\mu}_{\mathbf{s}}^{*}$ is AMS w.r.t. $T_{\mathcal{S}}$ .
Next it is proved that if $\bar{\mu}_{\mathbf{s}}(A)=0$ and
$T_{\mathcal{S}}^{-1}A=A$ then $\mu_{\mathbf{s}}(A)=0$. This in conjunction
with [12][Theorem 2.2] proves that $\mu_{\mathbf{s}}$ is AMS w.r.t.
$T_{\mathcal{S}}$.
Thus from the sublemma
$(\mathcal{S^{\infty}},\mathcal{F_{S^{\infty}}},\mu_{\mathbf{s}},T_{\mathcal{S}})$
is AMS which completes the proof.

_Lemma C: If $\mathbf{P}$ is ergodic, then $\mathbf{S}$ is ergodic _
_Proof:_ Let $A\in\mathcal{F_{S^{\infty}}}$ be $T_{\mathcal{S}}$ invariant and
let $\mathbf{s}=F(\mathbf{p})$ be an arbitrary member of $A$. Now
$F(\mathbf{p})\in A\Leftrightarrow T_{\mathcal{S}}^{n}F(\mathbf{p})\in A\hskip
3.0pt$ $\Rightarrow F(\mathbf{p})\in A\Leftrightarrow
T_{\mathcal{S}}^{l(p_{0})}F(\mathbf{p})\in A\hskip 3.0pt$ $\Rightarrow
F(\mathbf{p})\in A\Leftrightarrow F(T_{\mathcal{P}}\mathbf{p})\in A$
Taking $F^{-1}$ on both sides (as the equation holds for all $\mathbf{s}$ and
all $\mathbf{p}$ associated with each $\mathbf{s}$ )
$\mathbf{p}\in F^{-1}A\Leftrightarrow T_{\mathcal{P}}\mathbf{p}\in F^{-1}A$ .
Hence $F^{-1}A$ is $T_{\mathcal{P}}$ invariant. By the premise of the lemma,
$\mu_{\mathbf{p}}(F^{-1}A)=0$ or $1$. Hence $\mu_{\mathbf{s}}(A)=0$ or $1$.
Thus by definition,
$(\mathcal{S^{\infty}},\mathcal{F_{S^{\infty}}},\mu_{\mathbf{s}},T_{\mathcal{S}})$
is ergodic.

## Simulation

We have simulated a basic packet exchange in a MANET using NS2 with the node
movement generated according to the general continuous RWMM. The traffic
consisted of constant bitrate UDP packets with IEEE 802.11 protocol at the MAC
layer. The exchanges resulted in bursty traffic. The plot for the number of
bytes received as a function of time for a particular node is given in figure
2.

Figure 2: Number of bytes received as a function of time for a particular node

## Conclusion

In this paper we have successfully demonstrated that the discrete general RWMM
is AMS and hence stable. Thus simulations with RWMM as the underlying node
movement generation algorithm tend to be reliable. The stability preserving
protocols allow higher layers of the protocol stack to propagate this
stability hence permitting reliability of simulations at higher levels also.
Moreover we have simulated the continuous version of the RWMM with the intent
of seeing the local non-stationary properties (which is highlighted by the
bursty traffic).

## References

  * [1] R. Timo, K. Blackmore, and L. Hanlen, “Strong Stochastic Stability for MANET Mobility Models,”  15th IEEE International Conference on Networks , DOI: 10.1109/ICON.2007.4444054, pp. 13-18, November 2007
  * [2] S. Kurkowski, T. Camp, and M. Colagrosso, “MANET Simulation Studies: The Incredibles,”  ACM SIGMOBILE Mobile Comp. and Commun. Review $MC^{2}R$ , vol. 9, no. 4, pp. 50-60, October 2005.
  * [3] T. Andel and A. Yasinsac, “On the Credibility of MANET Simulations,” _Computer_ , vol. 39, no. 7, pp. 48-54, July 2006.
  * [4] J. Yoon, M. Liu, and B. Noble, “Sound Mobility Models,” in _Proc. IEEE Intl. Symp. Mobile Ad Hoc Net. and Comp., MobiHoc_ , September 2003, pp. 205-216.
  * [5] J. Boudec and M. Vojnovic,“The Random Trip Model: Stability, Stationary Regime, and Perfect Simulation,” _IEEE/ACM Trans. Networking_ , vol. 14, no. 6, pp. 1153-1166, December 2006.
  * [6] R. Timo, K. Blackmore, and J. Papandriopoulos, “Strong Stochastic Stability for Dynamic Source Routing,” Tech. Rep. PA006280, NICTA, August 2007.
  * [7] P. Billingsley, _Probability and Measure_ , Wiley series in probability and mathematical statistics. John Wiley and Sons, 3rd edition, 1995.
  * [8] R. Gray and J. Kieffer, “Asymptotically Mean Stationary Measures,” _J. Ann. Prob._ , vol. 8, no. 5, pp. 962-973, October 1980.
  * [9] P. Shields, _The Ergodic Theory of Discrete Sample Paths_ , vol. 13 of _Graduate Studies in Mathematics_ , American Mathematical Society, 1996.
  * [10] R. Gray, _Probability Random Processes, and Ergodic Properties_ , Springer Verlag, 2001 (Revision 1987), http://ee.stanford.edu/$\sim$gray/
  * [11] R. Gray, _Entropy and Information Theory_ , Springer Verlag, 2000 (Revision 1990), http://ee.stanford.edu/$\sim$gray/
  * [12] Y. Kakihara, “Ergodicity and Extremality of AMS Sources and Channels,” _International Journal of Mathematics and Mathematical Sciences_ , vol. 2003, no. 28, pp. 1755-1770, 2003.
  * [13] Wikipedia The Free Encyclopedia - Ergodic Theory, Retrieved April 5, 2011 http://en.wikipedia.org/wiki/Ergodic_theory
  * [14] Wikipedia The Free Encyclopedia - Bernoulli Scheme, Retrieved April 5, 2011 http://en.wikipedia.org/wiki/Bernoulli_scheme