#  MEKER: Memory Efficient Knowledge Embedding Representation for
Link Prediction and Question Answering

Viktoriia Chekalina1, Anton Razzhigaev1,2, Albert Sayapin1, Evgeny Frolov1 and
Alexander Panchenko1
1Skolkovo Institute of Science and Technology, 2Artificial Intelligence
Research Insitute (AIRI)

###### Abstract

Knowledge Graphs (KGs) are symbolically structured storages of facts. The KG
embedding contains concise data used in NLP tasks requiring implicit
information about the real world. Furthermore, the size of KGs that may be
useful in actual NLP assignments is enormous, and creating embedding over it
has memory cost issues. We represent KG as a 3rd-order binary tensor and move
beyond the standard CP decomposition Hitchcock (1927) by using a data-specific
generalized version of it Hong et al. (2020). The generalization of the
standard CP-ALS algorithm allows obtaining optimization gradients without a
backpropagation mechanism. It reduces the memory needed in training while
providing computational benefits. We propose a MEKER, a memory-efficient KG
embedding model, which yields SOTA-comparable performance on link prediction
tasks and KG-based Question Answering.

Figure 1: The CP decomposition scheme in the case of entity and relation KG
embedding in MEKER. This is a binary 3-dimensional tensor $\mathcal{X}$ of
knowledge graph facts that introduces objects, relations, and subjects indexes
along the three axes. $B$ contains relation embedding, while $A$ represents
entity vectors for the subject and object simultaneously. $\Lambda$ is the
diagonal core tensor, identity in our case.

##  1 Introduction

Natural Language Processing (NLP) models have taken a big step forward over
the past few years. For instance, language models can generate fluent human-
like text without any problems. However, some applications like question
answering and recommendation systems need correct, precise, and trustworthy
answers.

For this goal, it is appropriate to leverage knowledge graphs (KG) Bollacker
et al. (2008); Rebele et al. (2016) a structured repository of essential facts
about the real world. For convenience, the knowledge graph can be represented
as a set of triples. A triple is two entities bound with relation and
describes the fact. It takes the forms of $\langle e_{s},r,e_{o}\rangle$,
where $e_{s}$ and $e_{o}$ represent objects and subject entities,
respectively.

For efficient use of information from KG, there is a need for the low-
dimensional embedding of graph entities and relations. KG embedding models
usually use a standard Neural Networks (NN) backward mechanism for parameter
tuning, duplicating its memory consumption. Hence, existing approaches to
embedding learning have substantial memory requirements and can be deployed
only on small datasets under a single GPU card. Processing large KGs
appropriate for the custom downstream task is a challenge.

There are several libraries designed to solve this problem. Framework LibKGE
Ruffinelli et al. (2020) allows the processing of large datasets by using
sparse embedding layers. Despite the memory saving, sparse embedding has
several limitations - for example, in the PyTorch library, they are not
compatible with several optimizers. PyTorch-BigGraph Lerer et al. (2019)
operates with large knowledge graphs by dividing them into partitions -
distributed subgraphs. Subgraphs need a place for storing, embedding models
need modifications to work with partitions and perform poorly.

The main contribution of our paper is a memory-efficient approach to learning
Knowledge Graph embeddings MEKER (Memory Efficient Knowledge Embedding
Representation). It allows more efficient KG embedding learning, maintaining
comparable performance to state-of-the-art models. MEKER leverages generalized
canonical Polyadic (CP) decomposition Hong et al. (2020), which allows a
better approximation of given data and analytical computation of the
parameters’ gradient. MEKER is evaluated on a link prediction task using
several standard datasets and large datasets based on Wikidata. Experiments
show that MEKER achieves highly competitive results on these two tasks. To
demonstrate downstream usability, we create a Knowledge Base Question
Answering system Text2Graph and use embeddings in it. The system with MEKER
embeddings performs better as compared to other KG embeddings, such as PTBG
Lerer et al. (2019).

##  2 Related Work

There are three types of approaches for learning KG embedding: distance-based,
tensor-based, and deep learning-based models. The first group is based on the
assumption of translation invariance in the embedding vector space. In model
TransE Bordes et al. (2013) relations are represented as connection vectors
between entity representations. TransH Wang et al. (2014) implies relation as
a hyperplane onto which entities are being projected. QuatE Zhang et al.
(2019) extends the idea with hypercomplex space and represents entities as
embeddings with four imaginary components and relations as rotations in the
space.

Tensor-based models usually represent triples as a binary tensor and look for
embedding matrices as factorization products. RESCAL Nickel et al. (2011)
employs tensor factorization in the manner of DEDICOM Harshman et al. (1982),
which decomposes each tensor slice along the relationship axis. DistMult Yang
et al. (2015) adapts this approach by restricting the relation embedding
matrix to diagonal. On the one hand, it reduces the number of relation
parameters, on the other hand, it losses the possibility of describing
asymmetric relations. The ComplEX Trouillon et al. (2016) represents the
object and subject variants of a single entity as complex conjugates vectors.
It combines tensor-based and translation-based approaches and solves the
asymmetric problem. TuckER Balazevic et al. (2019) uses Tucker decomposition
Tucker (1966c) for finding representation of a knowledge graph elements. This
work can also be considered a generalization of several previous link
prediction methods.

Standard Canonical Polyadic (CP) Hitchcock (1927) decomposition in the link
prediction task does not show outstanding performance Trouillon et al. (2017).
Several papers address this problem by improving the CP decomposition
approach. SimplIE Kazemi and Poole (2018) states that low performance is due
to different representations of subject and object entity and deploys CP
decomposition with dependently learning of subjects and objects matrices.
CP-N3 Lacroix et al. (2018) highlights the statement that the Frobenius norm
regularizing is not fit for tensors of order more than 3 Cheng et al. (2016)
and proposes a Nuclear p-norm instead of it. Our approach also uses CP
decomposition with enhancement. We consider remark from SimplIE and set the
object and subject representations of one entity to be equals. At the same
time, inside the local step of the CP decomposition algorithm, the matrices of
subjects and objects consist of different elements and are different (see
Appendix). In contradistinction to CP-N3, we do not employ a regularizer to
improve training but change the objective. Instead of squared error, we use
logistic loss, which is appropriate for one-hot data. We abandon the gradient
calculation through the computational graph and count gradient analytically,
which makes the training process less resource-demanding.

Approaches based on Deep Learning convolutions and attention mechanisms ConvE,
GAT, GAAT Dettmers et al. (2017); Nathani et al. (2019); Wang et al. (2020)
achieve high performance in link prediction. Besides, they have their
disadvantages - it necessitate more time and memory resources than other types
of models and usually needs pre-training.

##  3 MEKER: Memory Efficient Knowledge Embedding Representation

Our approach to entity embeddings relies on generalized CP tensor
decomposition Hitchcock (1927). Namely, $R$-rank CP decomposition approximates
an N-dimensional tensor as a sum of $R$ outer products of $N$ vectors. Every
product can also be viewed as a rank-$1$ tensor. This approximation is
described by the following formula: $\mathcal{X}\approx\mathcal{M}=[|A,B,C|]$,
where $\mathcal{X}\in\mathbb{R}^{I\times J\times K}$ is original data and
$\mathcal{M}\in\mathbb{R}^{I\times J\times K}$ is its approximation. Factors
have the following shape $A\in\mathbb{R}^{I\times R}$,
$B\in\mathbb{R}^{J\times R}$, $C\in\mathbb{R}^{K\times R}$. The scheme of CP
decomposition applied to the KG elements representation task is in Figure 1.
We set matrix $A$ equal to matrix $C$ and simultaneously corresponding to
subject and object entities.

###  3.1 Generalization of Canonical Poliyadic (CP) Decomposition

Following the determination of the approximation type, the next task is to
find the parameters of the factor matrices that best match the ground truth
data. Battaglino et al. (2018); Dunlavy et al. (2011) describe the most widely
used CP decomposition algorithm, CP-ALS. The update rules for the factor
matrices are derived by alternating between minimizing squared error (MSE)
loss. Hong et al. (2020) demonstrates that MSE corresponds to Gaussian data
and is a particular case of a more general solution for an exponential family
of distributions. In general, the construction of optimal factors originates
the minimization problem:

$\begin{split}\min
F(\mathcal{M};\mathcal{X})&\equiv\sum_{i\in\Omega}f(x_{i},m_{i}),\\\
f(x,m)&\equiv\log p(x|l^{-1}(m)),\\\ \end{split}$ (1)

where $f$ \- elementwise loss function, $\Omega$ \- set of indices of known
elements of $\mathcal{X}$, $l$ \- link function, $x_{i}$ and $m_{i}$ \- the
$i$-th elements of $\mathcal{X}$ and $\mathcal{M}$, respectively. We also
introduce $\mathcal{Y}$ \- the tensor of derivatives of the elementwise loss
with the same size as $\mathcal{X}$ and being filled by zeros for
$i\not\in\Omega$. The data in the sparse one-hot triple tensor has a Bernoulli
distribution. The link function for Bernoulli is $l(\rho)=log(\rho/(1-\rho))$
and associated probability is $\rho=\exp(m)(1-\exp(m))$ so the loss function
and elements of the $\mathcal{Y}$ are defines as follows:

$\displaystyle f(x_{i},m_{i})$ $\displaystyle=\log(1+\exp{m_{i}})-x_{i}m_{i},$
(2) $\displaystyle y(x_{i},m_{i})$
$\displaystyle=\frac{\partial{f(x_{i},m_{i})}}{\partial{m_{i}}}=\frac{\exp{m_{i}}}{1+\exp{m_{i}}}-x_{i}.$

Hong et al. (2020) derives partial derivatives of $F$ w.r.t. factor matrices
and presents gradients G of it in a form similar to standard CP matrix update
formulas:

$\displaystyle G_{A}$ $\displaystyle=\mathcal{Y}_{[0]}(B\odot C)^{T\dagger},$
(3) $\displaystyle G_{B}$ $\displaystyle=\mathcal{Y}_{[1]}(A\odot
C)^{T\dagger},$ $\displaystyle G_{C}$ $\displaystyle=\mathcal{Y}_{[2]}(A\odot
B)^{T\dagger},$

where $\dagger$ \- pseudo-inverse matrix, $\odot$ \- Khartri-Rao operator,
$\mathcal{X_{[\text{n}]}}$ \- mode-n matricization, a reshaping of tensor
$\mathcal{X}$ along the $n$ axis. The importance of representation (3) is that
we can calculate the gradients via an essential tensor operation called the
matricized tensor times Khatri-Rao product (MTTKRP), implemented and optimized
in most programming languages. Algorithm 1 describes the procedure for
computing factor matrices gradients (3) in a Bernoulli distribution case (2).

###  3.2 Implementation Details

We use PyTorch Paszke et al. (2019) to implement the MEKER model. We set the
object and subject factors equal and correspond to matrix A for the
decomposition of the one-hot KG triplet tensor. Sparse natural and
reconstructed tensors are stored in Coordinate Format as a set of triplets
(COO). We combine actual triples and sampled negative examples in batches, and
process them. The corresponding pieces from the ground-truth tensor and
current factor matrices are cut out for each batch. Then the pieces are sent
to Algorithm 1 for the calculation of gradients of the matrix elements with
appropriate indexes. Algorithm 2 describes the pseudocode of factorization KG
tensor using GCP gradients.

We train the MEKER model using Bayesian search optimization to obtain the
optimal training parameters. We use the Wandb.ai tool Biewald (2020) for
experiment tracking and visualizations. The complete sets of tunable
hyperparameters are in the Appendix. Table 2 shows the best combinations of it
for the proposed datasets.

###  3.3 Baselines

As a comparison, we deploy related link prediction approaches that meet the
following criteria: 1) it should learn KG embedding from scratch 2) it should
report high performance 3) the corresponding paper should provide a runnable
code. We use the Tucker, Hyper, ConvKB, and QuatE implementations from their
respective repositories. For TransE, DistMult, ComplEx, and ConvE, we use
LibKGE Ruffinelli et al. (2020) library with the best parameter setting for
reproducing every model. We run each model five times for each observed value
and provide means and sample standard deviation.

Algorithm 1 GCP GRAD Bernuilli

Input: $\mathcal{X}$ $\triangleright$ Ground Truth Tensor
$A$, $B$, $C$ $\triangleright$ Factor matrices

Output: $F$, $G_{A}$, $G_{B}$, $G_{C}$

$\mathcal{M}=\\{A,B,C\\}$ $\triangleright$ Model Restored tensor

$F=\sum_{i}f(x_{i},m_{i})=\sum log(1+e^{m}_{i})-x_{i}m_{i}$ $\triangleright$
Loss

$\mathcal{Y}=\sum_{i}\frac{\delta f(x_{i},m_{i})}{\delta m_{i}}=$
$\triangleright$ Derivative tensor

$=\sum\frac{1}{1+e^{(-m_{i})}}-x_{i}$

$G_{A}=\mathcal{Y}_{[0]}(B\odot C)^{T\dagger}$. $\triangleright$ Element-wise
gradient for A

$G_{B}=\mathcal{Y}_{[1]}(A\odot C)^{T\dagger}$ $\triangleright$ Element-wise
gradient for B

$G_{C}=\mathcal{Y}_{[2]}(A\odot B)^{T\dagger}$ $\triangleright$ Element-wise
gradient for C

Algorithm 2 Factorization of the KG tensor using GCP gradients

Input: $\mathcal{X}$ $\triangleright$ Ground Truth Tensor
Triplets $\triangleright$ List of triplets
$LR$ $\triangleright$ learning rate
$R$ $\triangleright$ Desired size of embeddings
$N$ $\triangleright$ Number of epoch

Output: $A$, $B$ $\triangleright$ Updated factor matrices

Initialize factor matrices $A\in\mathbb{R}^{R\times n_{e}}$,
$B\in\mathbb{R}^{R\times n_{r}}$

for $i=1\dots N$ do

for $[\text{inds}_{a},\text{inds}_{b},\text{inds}_{c}]$ in Triplets do

$\mathcal{X}_{batch}=\mathcal{X}[\text{inds}_{a},\text{inds}_{b},\text{inds}_{c}]$

$g_{a}$, $g_{b}$, $g_{c}$, $loss$ =

GCP_GRAD$(\mathcal{X}_{batch},A[\text{inds}_{a}]$, $B[\text{inds}_{b}]$,
$A[\text{inds}_{c}]$)

$A[\text{inds}_{a}]\text{.grad}=g_{a}$

$B[\text{inds}_{b}]\text{.grad}=g_{b}$

$A[\text{inds}_{c}]\text{.grad}=g_{c}$

UPDATE($A$, $B$, $LR$)

Dataset |  |  |  FB15k237 |  |  |  WNRR18 |  |
---|---|---|---|---|---|---|---|---
Model |  MRR |  Hit@10 |  Hit@3 |  Hit@1 |  MRR |  Hit@10 |  Hit@3 |  Hit@1
ConvKB Nguyen et al. (2018) |  0.2985 |  0.4785 |  0.3270 |  0.2296 |  0.2221 |  0.5074 |  0.3777 |  0.0347
HypER Balazevic et al. (2018) |  0.3423 |  0.5228 |  0.3774 |  0.2536 |  0.4653 |  0.5228 |  0.4774 |  0.4361
TuckER Balazevic et al. (2019) |  0.3455 |  0.5408 |  0.3899 |  0.2606 |  0.4654 |  0.5215 |  0.4784 |  0.4368
QuatE Zhang et al. (2019) |  0.3614 |  0.5538 |  0.4014 |  0.2711 |  0.4823 |  0.5719 |  0.4955 |  0.4360
CP-N3 Lacroix et al. (2018) |  0.3514 |  0.5294 |  0.3876 |  0.2646 |  0.4402 |  0.4858 |  0.4485 |  0.4207
LibKGE ConvE Dettmers et al. (2017) |  0.3367 |  0.5213 |  0.3682 |  0.2381 |  0.4282 |  0.5049 |  0.4492 |  0.3934
LibKGE TransE Bordes et al. (2013) |  0.3121 |  0.4962 |  0.3175 |  0.2195 |  0.2274 |  0.5189 |  0.3677 |  0.0516
LibKGE DistMult Yang et al. (2015) |  0.3331 |  0.5185 |  0.3673 |  0.2410 |  0.4505 |  0.5215 |  0.4634 |  0.4162
LibKGE ComplEx Trouillon et al. (2016) |  0.3390 |  0.5265 |  0.3724 |  0.2468 |  0.4752 |  0.5467 |  0.4809 |  0.4366
MEKER |  0.3588 |  0.5393 |  0.3915 |  0.2682 |  0.4768 |  0.5447 |  0.4875 |  0.4371
Table 1: Link Prediction scores for various models on the FB15k237 and WN18RR datasets. The embedding size is 200. The winner scores are highlighted in bold font, and the second results are underlined. Dataset | FB15k237 | WN18RR
---|---|---
Optimizer | AdamW | AdamW
LR | 0.01 | 0.009
Batch Size | 156 | 128
L2 reg | 0.001 | 0.0
Number of negative | 6 | 8
Step of decay LR | 3 | 15
Gamma of decay LR | 0.8 | 0.6
Table 2: The best hyperparameters of the MEKER.

##  4 Experiments on Standard Link Prediction Datasets

###  4.1 Experimental settings

The Link prediction task estimates the quality of KG embedding. Link
prediction is a classification predicting if triple over graph elements is
true or not. The scoring function $\Phi(e_{s},rel,e_{o})$ returns the
probability of constructing a true triple. We test our model on this task
using standard Link prediction datasets.

FB15k237 Toutanova and Chen (2015) is a dataset based on the FB15k237 adapted
Freebase subset, which contains triples with the most mentioned entities.
FB15k237 devised the method of selecting the most frequent relations and then
filtering inversions from test and valid parts. The WN18RR Bordes et al.
(2013) version of WN18 is devoid of inverse relations. WN18 is a WordNet
database that contains the senses of words as well as the lexical
relationships between them. Table 3 shows the number of entities, relations,
and train-valid-test partitions for each dataset used in the proposed work. As
an evaluation, we obtain complementary candidates from the entity set for each
pair entity-relation from each test triple and estimate the probability score
of the received triple being true. The presence of a rising real supplement
entity at the top indicates a hit. Candidate ranking is provided using a
filtered setting, which was first used in Bordes et al. (2013). In a filtered
setting, all candidates who completed a true triple on the current step are
removed from the set, except for the expected entity. We use $\text{Hit@}1$,
$\text{Hit@}3$, $\text{Hit@}10$ as evaluation metrics. We also use mean
reciprocal rank (MRR) to ensure that true complementary elements are ranked
correctly.

|  |  | Number of Triplets
---|---|---|---
Dataset |  #ents |  #rels |  Train |  Valid |  Test
Fb15k237 |  14,541 |  237 |  27.2$\cdot 10^{4}$ |  17,535 |  20,466
WN18RR |  40,943 |  11 |  8.6$\cdot 10^{4}$ |  30,034 |  3,134
Wiki4M |  4,316$\cdot 10^{4}$ |  1,245 |  1,367$\cdot 10^{4}$ |  30,000 |  35,815
Wikidata5m |  4,594$\cdot 10^{4}$ |  822 |  2,061$\cdot 10^{4}$ |  5,163 |  5,133
Table 3: Statistics of link prediction datasets.

###  4.2 Link Prediction

Table 1 shows the mean value of the experiment on small datasets for the
embedding of size 200. The $\text{Hit@}10$ standard deviation for MEKER is
$0.0034$ for the FB15k237 dataset and $0.0026$ for the WNRR18 dataset. Due to
space constraints, the table with deviations from all experiments, comparable
to Table 1, is in Appendix.

The best score belongs to QuatE Zhang et al. (2019) model due to its highly
expressive 4-dimensional representations. Among the remaining approaches,
MEKER outperforms its contestants’ overall metrics except for the Hit@10 -
Tucker model surpasses MEKER for Fb15k237, ComplEX by LibKGE for WNRR18. In
general, MEKER shows decent results comparable to strong baselines Zhang et
al. (2019); Balazevic et al. (2019). It is also worth noting that MEKER
significantly improves MRR and Hit@1 metrics on freebase datasets, whereas on
word sense, according to data, it has been enhanced in Hit@10.

###  4.3 Model efficiency in case of parameter size increasing

With a strong memory assumption, we can reduce the size of pre-trained MEKER
embeddings by tenfold while losing only a few percent of performance.

Figure 2: MRR score in dependence of embedding ranks

Figure 3: Hit@1 score in dependence of embedding ranks

Figures 3, 3 show MRR and Hit@1 scores for MEKER, TuckER, and ComplEX models
at various embedding sizes. Each model approaches a constant value on both
metrics around rank 100. For ranks 200 and 300, the performance difference
between the three models is approximately consistent for both metrics, with
MEKER scoring the highest on rank 20. It means that the number of MEKER
parameters can be reduced while maintaining or improving quality. The quality
loss is significant for other presented models.

###  4.4 Memory Complexity Analysis

The theoretical space complexity of models mentioned in the current work is
shown in the right column of Table 4. In the context of the Link Prediction
task, all approaches have asymptotic memory complexity
$\mathcal{O}((n_{e}+n_{r})d)$, which is proportional to the size of the full
dictionary of KG elements, i.e. the embedding layer or look-up table. Other
aspects of the proposed models are less significant: the convolutional layers
are not very extensive. The implementation determines the amount of real
memory used by the model during the training process. The Neural Network
backpropagation mechanism is used to tune parameters in the most related work.
Backpropagation in Figure 4 creates computational graph in which all model
parameters are duplicated. It results in a multiplicative constant $2$,
insignificant in a small dictionary but becomes critical in a large one. To
summarize, the following factors account for the decrease in MEKER’s required
memory:

  1. 1.

In the MEKER algorithm gradients are computed analytically.

  2. 2.

MEKER does not have additional neural network layers (linear, convolutional,
or attention).

To measure GPU RAM usage, we run each considered embedding model on FB15k-237
into a single GPU and print peak GPU memory usage within the created process.
The left column of a Table 4 demonstrates that MEKER has objective memory
complexity that is at least twice lower than that of other linear approaches.
This property reveals the possibility of obtaining representations of specific
large databases using a single GPU card.

Figure 4: The scheme of the augmented computational graph of the Neural Network. Model | GPU Memory | Theoretical Approximation
---|---|---
| Usage, MB | of Space Complexity
TuckER | 357 | $2\cdot((n_{e}+n_{r}+c\cdot lin)\cdot d)$
HypER | 208 | $2\cdot((n_{e}+n_{r}+c\cdot lin)\cdot d)$
ConvKB | 3 563 | $2\cdot((n_{e}+n_{r})\cdot d+c\cdot conv)$
ConvE | 229 | $2\cdot((n_{e}+n_{r})\cdot d+c\cdot conv)$
ComplEX | 252 | $2\cdot(n_{e}+n_{r})\cdot d$
DistMult | 174 | $2\cdot(n_{e}+n_{r})\cdot d$
QuatE | 2 367 | $2\cdot 4\cdot(n_{e}+n_{d}+c\cdot lin)$
CP (N3) | 138 | $2\cdot(n_{e}+n_{r})\cdot d$
MEKER | 79 | $((n_{e}+n_{r})\cdot d)$
Table 4: Memory, reserved in the PyTorch Framework during the training process
and theoretical approximation of given implementations’ complexity. On the
FB15k237 dataset, we train 200-size representations with a batch size of 128.
$Lin$ denotes the number of output features in a linear layer, $conv$ denotes
the size of convolutional layer parameters. The constant $c$ represents the
number of different layers.

##  5 Experiments on Large-Scale KG Datasets

###  5.1 Experimental settings

To test the model on large KG, we employ two WikiData-based datasets. The
first English dataset, Wikidata5m Wang et al.
(2021)111https://deepgraphlearning.github.io/project/wikidata5m, is selected
due to the presence of related works and reproducible baseline Ruffinelli et
al. (2020). This dataset is created over the 2019 dump of WikiData and
contains of elements with links to informative Wikipedia pages. Our
experiments use the transductive setting of Wikidata5m - triplet sets to
disjoint across training, validation, and test.

The second English-Russian dataset is formed since its suitability for the NLP
downstream task. We leverage KG-based fact retrieval over Russian Knowledge
Base Questions (RuBQ) Rybin et al. (2021) benchmark. This benchmark is a
subset of Wikidata entities with Russian labels. Some elements in RuBQ are not
covered with Wikidata5m, so we created a link-prediction Wiki4M dataset over
RuBQ. We select triples without literal objects and obtain approximately 13M
triples across 4M entities (see Table 3). Wiki4M also fits the concept of
multilingualism is intended to be used in a cross-lingual transfer or few-shot
learning.

Model | MRR | Hit@1 | Hit@3 | Hit@10 | Memory, GB | Storage, GB
---|---|---|---|---|---|---
English: Wikidata5m dataset
PTBG (ComplEX) | 0.184 | 0.131 | 0.210 | 0.287 | 45.15 | 9.25
PTBG (TransE) | 0.150 | 0.091 | 0.176 | 0.263 | 43.64 | 9.25
LibKGE sparse (TransE) | 0.142 | 0.153 | 0.211 | 0.252 | 33.29 | 0.00
LibKGE sparse (ComplEX) | 0.202 | 0.160 | 0.233 | 0.316 | 21.42 | 0.00
MEKER (ours) | 0.211 | 0.149 | 0.238 | 0.325 | 22.27 | 0.00
Russian: Wiki4M dataset
PTBG (ComplEX) | 0.194 | 0.141 | 0.212 | 0.293 | 42.83 | 9.25
LibKGE sparse (TransE) | 0.183 | 0.126 | 0.191 | 0.275 | 26.75 | 0.00
LibKGE sparse (ComplEX) | 0.247 | 0.196 | 0.275 | 0.345 | 20.22 | 0.00
MEKER (ours) | 0.269 | 0.199 | 0.303 | 0.410 | 21.04 | 0.00
Table 5: Unfiltered link prediction scores for MEKER and PyTorch-BigGraph
approaches for Wiki4M and Wikidata5m datasets and memory needed in leveraging
every model. Storage means additional memory demanded for auxiliary
structures. Batch size 256. Here “RAM” is GPU RAM or main memory RAM if GPU
limit of 24 GB is reached. Sparse means sparse embeddings. Models without
sparse mark employ dense embeddings matrix.

###  5.2 Link Prediction

We embed the datasets for ten epochs on a 24.268 Gb GPU card with the
following model settings: LR $2.5\cdot 10^{-4}$, increasing in $0.5$ steps
every $10$ epoch, batch size $256$, number of negative samples $4$ for Wiki4M
and $2$ for Wikidata5m.

As a comparison, we use the PyTorch-BigGraph large-scale embedding system
Lerer et al. (2019). PyTorch-BigGraph modifies several traditional embedding
systems to focus on the effective representation of KG in memory. We select
ComplEX and TransE and train graphs for these embedding models, dividing large
datasets into four partitions. With a batch size of $256$, the training
process takes $50$ epochs.

We also deploy LibKGE Ruffinelli et al. (2020) to evaluate TransE and ComplEX
approaches. For ComplEX model training, we use the best parameter
configuration from the repository, for TransE, we obtain a set of training
parameters by greed search. The learning rate for TransE is $0.5$, decaying in
factor $0.45$ every $5$ step and train model in $100$ epochs. In both cases,
we use sparse embedding in the corresponding model setting and batch size of
$256$. Models from both wrappers that did not fit in 24 GB, we train on the
CPU.

Embedding sets yielded by we these experiments we then test on the link
prediction task. We provide scoring without filters because the partition-
based setup of PyTorch-Biggraph does not support filtering evaluation. Tables
5 shows that MEKER significantly improves the results of PyTorch-Biggraph
models across all proposed metrics. The ComplEX model with sparse embedding,
fine-tuned by LibKGE, gives results almost approaching the MEKER and exceeding
the Hit@1 in Wiki4M. The right part of Tables 5 shows that the baseline
approaches consume twice as much memory as MEKER, but sparse ComplEX slightly
improves memory consumption. TransE does not give such significant results as
ComplEX.

###  5.3 Knowledge Base Question Answering (KBQA)

In this section, to further evaluate the proposed MEKER embeddings we test
them in an extrinsic way within on a KBQA task on two datasets for English and
Russian.

####  5.3.1 Experimental Setting

We perform experiment with two datasets: for English we use the common dataset
SimpleQuestions Bordes et al. (2015) aligned with Wiki4M
KG222https://github.com/askplatypus/wikidata-simplequestions (cf. Table 3),
and for Russian we use RuBQ 2.0 dataset Rybin et al. (2021) which comes with
the mentioned above Wiki4M KG (cf. Table 3). RuBQ 2.0 is a Russian language QA
benchmark with multiple types of questions aligned with Wikidata. For both
SimpleQuestions and RuBQ, for each question, an answer is represented by a KG
triple.

For training we use a training set of SimpleQuestions for verification we use
a test set of SimpleQuestions and RuBQ 2.0 dataset for English and Russian,
respectively. These Q&A pairs provide ground truth answers linked to exact
this version of KG elements.

More specifically, in these experiments, we test answers to 1-hop questions
which are questions corresponding to one subject and one relation in the
knowledge graph, and takes their object as an answer.

We want to leverage the KBQA model, which can process questions both in
English and Russian. To measure the performance of a KBQA system, we measure
the accuracy of the retrieved answer/entity. This metric was used in
previously reported results on SimpleQuestions and RuBQ. If the subject of the
answer triple matches the reference by ID or name, it is considered correct.

Figure 5: Text2Graph method used in our experiments: 1-Hop QA pipeline. First,
we take original entity and relation embeddings. The question is embedded
using m-BERT. This embedding is then processed by MLP, yielding candidate
representations of an object, relation, and subject. The sum of the subject,
relation, and object cosines is the final score of triple candidates.

####  5.3.2 KBQA methods

The key idea of the KBQA approaches is mapping questions in natural language
to the low-dimensional space and comparing them to graph elements’ given
representation. In KEQA Huang et al. (2019) LSTM models detect the entity and
predicates from the question text and project it further into the entity and
predicate embedding spaces. The closest subject in terms of similarity to the
entity and predicate embeddings is selected as the answer.

We created a simple approach Text2Graph which stems from the KEQA and differs
from the original work in improved question encoder, entity extractor,
additional subject embedding space and simplified retrieval pipeline. The
Algorithm 3 describes the procedure of projecting the input question to graph
elements. The multilingual-BERT Devlin et al. (2019) model encodes the input
question, and all word vectors are averaged into a single deep contextualized
representation $e_{q}$. This representation then goes through three MLPs
jointly learning candidate embeddings of an object, relation, and subject. We
minimize MSE between predicted embeddings and the corresponding KGE model’s
embeddings. The appropriateness score of every fact in KG is a sum of cosine
similarity between MLP outputs and ground truth model representation for every
element in the triple. The triple with the highest score is considered to be
an answer. The scheme is trained using an AdamW optimizer with default
parameters for $10$ epochs.

###  5.4 Baselines

####  5.4.1 RuBQ 2.0

We compare our method to several QA approaches compatible with questions from
this benchmark.

Algorithm 3 Text2Graph question projection algorithm

Input: $\mathcal{Q}$, $\mathcal{G}$, E,
text encoder $M_{enc}$,
projection modules: $M_{s},M_{r},M_{o}$,
Subject Candidates Extractor: NER
Output: answer $\langle o_{a},r_{a},s_{a}\rangle$

$e_{q}=M_{enc}(\mathcal{Q})$

Initialize answers-candidates list with empty list A=[]

Initialize scores list with empty list S=[]

Initialize entities-candidates list with empty list C=[]

for entity in $\mathcal{G}$ do

if entity.name in $\text{NER}(\mathcal{Q})$ then

C.append(entity)

for entity in C do

for relation in entity.relations do

s = entity.id

r = relation.id

o = entity[r]

triple = $\langle s,r,o\rangle$

A.append(triple)

$\mathbf{e_{s}}=\textbf{E}$[s]

$\mathbf{e_{r}}=\textbf{E}$[r]

$\mathbf{e_{o}}=\textbf{E}$[o]

$\mathbf{y_{s}}=M_{s}(e_{q})$

$\mathbf{y_{r}}=M_{r}(e_{q})$

$\mathbf{y_{o}}=M_{o}(e_{q})$

$score=\text{cos}(\mathbf{e_{o}},\mathbf{y_{o}})+\text{cos}(\mathbf{e_{r}},\mathbf{y_{r}})+\text{cos}(\mathbf{e_{s}},\mathbf{y_{s}})$

S.append($score$)

ind = argmax(S)

$\langle s_{a},r_{a},o_{a}\rangle=\textbf{A}$[ind]

return $\langle s_{a},r_{a},o_{a}\rangle$

QAnswer333https://www.qanswer.eu is a rule-based system addressing questions
in several languages, including Russian. SimBa is a baseline presented by RuBQ
2.0 authors. It is a SPARQL query generator based on an entity linker and a
rule-based relation extractor. KBQA module of DeepPavlov Dialogue System
Library Burtsev et al. (2018) also based on query processing.

####  5.4.2 SimpleQuestions

Simple Question is an English language benchmark aligned with FB5M KG - the
subset of Freebase KG. Its train and validation parts consist of 100k and 20k
questions, respectively. As a baseline solution we employ KEQA Huang et al.
(2019). We realign answers from this benchmark to our system, which is
compatible with Wikidata5m. Not all of the questions from FB5M have answers
among Wiki4M, that is why we test both systems on a subset of questions whose
answers are present in both knowledge graphs.

####  5.4.3 Experimental Results

KBQA Model | Embedding Model | Accuracy 1-Hop
---|---|---
DeepPavlov | - | 30.5 $\pm$ 0.04
SimBa | - | 32.3 $\pm$ 0.05
QA-En | - | 32.3 $\pm$ 0.08
QA-Ru | - | 30.8 $\pm$ 0.03
Text2Graph | PTBG (ComplEX) Wiki4M | 48.16 $\pm$ 0.05
Text2Graph | PTBG (TransE) Wiki4M | 48.84 $\pm$ 0.06
Text2Graph | MEKER Wiki4M | 49.06 $\pm$ 0.06

Table 6: Comparison of the Text2Graph system with the various KG embeddings
with existing solutions (QA-Ru, QA-En, SimBa) on RuBQ 2.0 benchmark.

KBQA Model | Embedding Model | Accuracy 1-Hop
---|---|---
KEQA | TransE FB5M | 40.48 $\pm$ 0.10
Text2Graph | PTBG (TransE) Wikidata5m | 59.97 $\pm$ 0.15
Text2Graph | MEKER Wikidata5m | 61.81 $\pm$ 0.13

Table 7: Comparison of the Text2Graph system with the various KG embeddings
with existing embedding-based solution on the SimpleQuestions benchmark.

We compare the results of the Text2Graph with PTBG embeddings versus MEKER
embedding and baseline KBQA models. Results on the RuBQ 2.0 dataset are shown
in Table 6. Text2Graph outperforms baselines. Using MEKER embeddings instead
of the PTBG version of ComplEX and TransE demonstrates slightly better
accuracy.

Table 7 presents results on the SimpleQuestions dataset. As Huang et al.
(2019) model uses FB5M KG and Text2Graph uses Wikidata5m KG we test both
models on the subset of questions, which answers are present in both knowledge
graphs for a fair comparison. Our model demonstrates superior performance and
regarding the comparison within different embeddings in a fixed system, MEKER
provides better accuracy of answers than TransE embeddings on the
SimpleQuestions benchmark.

##  6 Conclusion

We propose MEKER, a linear knowledge embedding model based on generalized CP
decomposition. This method allows for the calculation of gradient
analytically, simplifying the training process under memory restriction. In
comparison to previous KG embedding linear models Balazevic et al. (2019), our
approach achieves high efficiency while using less memory during training. On
the standard link prediction datasets WN18RR and FB15k-237, MEKER shows quite
competitive results.

In addition, we created a Text2Graph — KBQA system based on the learned KB
embeddings to demonstrate the model’s effectiveness in NLP tasks. We obtained
the required representations using MEKER on the Wikipedia-based dataset Wiki4M
for questions in Russian and on Wikidata5m for questions in English.
Text2Graph outperforms baselines for English and Russian, while using MEKER’s
embeddings provides additional performance gain compared to PTBG embeddings.
Furthermore, our model’s link prediction scores on Wiki4M and Wikidata5m
outperform the baseline results. MEKER can be helpful in question-answering
systems over specific KG, in other words, in systems that need to embed large
sets of facts with acceptable quality.

All codes to reproduce our experiments are available
online.444https://github.com/skoltech-nlp/meker

## Acknowledgements

The work was supported by the Analytical center under the RF Government
(subsidy agreement 000000D730321P5Q0002, Grant No. 70-2021-00145 02.11.2021).

We thank Dr. Evgeny Frolov for providing advice and assistance in developing
the MEKER method.

## References

  * Balazevic et al. (2019) Ivana Balazevic, Carl Allen, and Timothy Hospedales. 2019.  TuckER: Tensor factorization for knowledge graph completion.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 5185–5194, Hong Kong, China. Association for Computational Linguistics.
  * Balazevic et al. (2018) Ivana Balazevic, Carl Allen, and Timothy M. Hospedales. 2018.  Hypernetwork knowledge graph embeddings.  _CoRR_ , abs/1808.07018.
  * Battaglino et al. (2018) Casey Battaglino, Grey Ballard, and Tamara G. Kolda. 2018.  A practical randomized CP tensor decomposition.  _SIAM J. Matrix Anal. Appl._ , 39(2):876–901.
  * Biewald (2020) Lukas Biewald. 2020.  Experiment tracking with weights and biases.  Software available from wandb.com.
  * Bollacker et al. (2008) Kurt Bollacker, Colin Evans, Praveen Paritosh, Tim Sturge, and Jamie Taylor. 2008\.  Freebase: A collaboratively created graph database for structuring human knowledge.  pages 1247–1250.
  * Bordes et al. (2015) Antoine Bordes, Nicolas Usunier, Sumit Chopra, and Jason Weston. 2015.  Large-scale simple question answering with memory networks.
  * Bordes et al. (2013) Antoine Bordes, Nicolas Usunier, Alberto Garcia-Durán, Jason Weston, and Oksana Yakhnenko. 2013.  Translating embeddings for modeling multi-relational data.  In _Proceedings of the 26th International Conference on Neural Information Processing Systems - Volume 2_ , NIPS’13, page 2787–2795, Red Hook, NY, USA. Curran Associates Inc.
  * Burtsev et al. (2018) Mikhail Burtsev, Alexander Seliverstov, Rafael Airapetyan, Mikhail Arkhipov, Dilyara Baymurzina, Nickolay Bushkov, Olga Gureenkova, Taras Khakhulin, Yuri Kuratov, Denis Kuznetsov, Alexey Litinsky, Varvara Logacheva, Alexey Lymar, Valentin Malykh, Maxim Petrov, Vadim Polulyakh, Leonid Pugachev, Alexey Sorokin, Maria Vikhreva, and Marat Zaynutdinov. 2018.  DeepPavlov: Open-source library for dialogue systems.  In _Proceedings of ACL 2018, System Demonstrations_ , pages 122–127, Melbourne, Australia. Association for Computational Linguistics.
  * Cheng et al. (2016) Hao Cheng, Yaoliang Yu, Xinhua Zhang, Eric Xing, and Dale Schuurmans. 2016.  Scalable and sound low-rank tensor learning.  In _Proceedings of the 19th International Conference on Artificial Intelligence and Statistics_ , volume 51 of _Proceedings of Machine Learning Research_ , pages 1114–1123, Cadiz, Spain. PMLR.
  * Dettmers et al. (2017) Tim Dettmers, Pasquale Minervini, Pontus Stenetorp, and Sebastian Riedel. 2017.  Convolutional 2d knowledge graph embeddings.  _CoRR_ , abs/1707.01476.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  BERT: Pre-training of deep bidirectional transformers for language understanding.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pages 4171–4186, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Dunlavy et al. (2011) Daniel M. Dunlavy, Tamara G. Kolda, and Evrim Acar. 2011.  Temporal link prediction using matrix and tensor factorizations.  _ACM Trans. Knowl. Discov. Data_ , 5(2):10:1–10:27.
  * Harshman et al. (1982) Richard A. Harshman, Paul E. Green, Yoram Wind, and Margaret E. Lundy. 1982.  A model for the analysis of asymmetric data in marketing research.  _Marketing Science_ , 1(2):205–242.
  * Hitchcock (1927) F. L. Hitchcock. 1927.  The expression of a tensor or a polyadic as a sum of products.  _J. Math. Phys_ , 6(1):164–189.
  * Hong et al. (2020) David Hong, Tamara G. Kolda, and Jed A. Duersch. 2020.  Generalized canonical polyadic tensor decomposition.  _SIAM Review_ , 62(1):133–163.
  * Huang et al. (2019) Xiao Huang, Jingyuan Zhang, Dingcheng Li, and Ping Li. 2019.  Knowledge graph embedding based question answering.  In _Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining_ , WSDM ’19, page 105–113, New York, NY, USA. Association for Computing Machinery.
  * Kazemi and Poole (2018) Seyed Mehran Kazemi and David Poole. 2018.  Simple embedding for link prediction in knowledge graphs.  In _Proceedings of the 32nd International Conference on Neural Information Processing Systems_ , NIPS’18, page 4289–4300, Red Hook, NY, USA. Curran Associates Inc.
  * Lacroix et al. (2018) Timothee Lacroix, Nicolas Usunier, and Guillaume Obozinski. 2018.  Canonical tensor decomposition for knowledge base completion.  In _Proceedings of the 35th International Conference on Machine Learning_ , volume 80 of _Proceedings of Machine Learning Research_ , pages 2863–2872. PMLR.
  * Lerer et al. (2019) Adam Lerer, Ledell Wu, Jiajun Shen, Timothee Lacroix, Luca Wehrstedt, Abhijit Bose, and Alex Peysakhovich. 2019.  PyTorch-BigGraph: A Large-scale Graph Embedding System.  In _Proceedings of the 2nd SysML Conference_ , Palo Alto, CA, USA.
  * Nathani et al. (2019) Deepak Nathani, Jatin Chauhan, Charu Sharma, and Manohar Kaul. 2019.  Learning attention-based embeddings for relation prediction in knowledge graphs.  _CoRR_ , abs/1906.01195.
  * Nguyen et al. (2018) Dai Quoc Nguyen, Tu Dinh Nguyen, Dat Quoc Nguyen, and Dinh Phung. 2018.  A novel embedding model for knowledge base completion based on convolutional neural network.  In _Proceedings of the 16th Annual Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (NAACL-HLT)_ , pages 327–333.
  * 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 _Proceedings of the 28th International Conference on International Conference on Machine Learning_ , ICML’11, page 809–816, Madison, WI, USA. Omnipress.
  * Paszke et al. (2019) Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. 2019.  Pytorch: An imperative style, high-performance deep learning library.  In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, _Advances in Neural Information Processing Systems 32_ , pages 8024–8035. Curran Associates, Inc.
  * Rebele et al. (2016) Thomas Rebele, Fabian M. Suchanek, Johannes Hoffart, Joanna Biega, Erdal Kuzey, and Gerhard Weikum. 2016.  YAGO: A multilingual knowledge base from wikipedia, wordnet, and geonames.  In _The Semantic Web - ISWC 2016 - 15th International Semantic Web Conference, Kobe, Japan, October 17-21, 2016, Proceedings, Part II_ , pages 177–185.
  * Ruffinelli et al. (2020) Daniel Ruffinelli, Samuel Broscheit, and Rainer Gemulla. 2020.  You CAN teach an old dog new tricks! on training knowledge graph embeddings.  In _International Conference on Learning Representations_.
  * Rybin et al. (2021) Ivan Rybin, Vladislav Korablinov, Pavel Efimov, and Pavel Braslavski. 2021.  Rubq 2.0: An innovated russian question answering dataset.  In _The Semantic Web - 18th International Conference, ESWC 2021, Virtual Event, June 6-10, 2021, Proceedings_ , volume 12731 of _Lecture Notes in Computer Science_ , pages 532–547. Springer.
  * 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. (2017) Théo Trouillon, Christopher R. Dance, Éric Gaussier, Johannes Welbl, Sebastian Riedel, and Guillaume Bouchard. 2017.  Knowledge graph completion via complex tensor factorization.  _J. Mach. Learn. Res._ , 18(1):4735–4772.
  * Trouillon et al. (2016) Théo Trouillon, Johannes Welbl, Sebastian Riedel, Eric Gaussier, and Guillaume Bouchard. 2016.  Complex embeddings for simple link prediction.  In _Proceedings of The 33rd International Conference on Machine Learning_ , volume 48 of _Proceedings of Machine Learning Research_ , pages 2071–2080, New York, New York, USA. PMLR.
  * Tucker (1966c) L. R. Tucker. 1966c.  Some mathematical notes on three-mode factor analysis.  _Psychometrika_ , 31:279–311.
  * Wang et al. (2020) Rui Wang, Bicheng Li, Shengwei Hu, Wenqian Du, and Min Zhang. 2020.  Knowledge graph embedding via graph attenuated attention networks.  _IEEE Access_ , 8:5212–5224.
  * Wang et al. (2021) Xiaozhi Wang, Tianyu Gao, Zhaocheng Zhu, Zhengyan Zhang, Zhiyuan Liu, Juanzi Li, and Jian Tang. 2021.  Kepler: A unified model for knowledge embedding and pre-trained language representation.  _Transactions of the Association for Computational Linguistics_ , 9:176–194.
  * Wang et al. (2014) Zhen Wang, Jianwen Zhang, Jianlin Feng, and Zheng Chen. 2014.  Knowledge graph embedding by translating on hyperplanes.  In _Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence_ , AAAI’14, page 1112–1119. AAAI Press.
  * Yang et al. (2015) B. Yang, Wen tau Yih, X. He, Jianfeng Gao, and L. Deng. 2015.  Embedding entities and relations for learning and inference in knowledge bases.  _CoRR_ , abs/1412.6575.
  * Zhang et al. (2019) Shuai Zhang, Yi Tay, Lina Yao, and Qi Liu. 2019.  Quaternion knowledge graph embeddings.  In _Advances in Neural Information Processing Systems_ , volume 32. Curran Associates, Inc.


# On uniquely packable trees

A. Alochukwu111Financial support by the DSI-NRF Centre of Excellence in
Mathematical and Statistical Sciences (CoE-MaSS), South Africa is gratefully
acknowledged. Department of Mathematics, Computer Science and Physics, Albany
State University, USA  DSI-NRF Centre of Excellence in Mathematical and
Statistical Sciences (CoE-MaSS), South Africa.  M. Dorfling  Department of
Mathematics and Applied Mathematics, University of Johannesburg, South Africa
E. Jonck  School of Mathematics, University of the Witwatersrand, South Africa
DSI-NRF Centre of Excellence in Mathematical and Statistical Sciences (CoE-
MaSS), South Africa.

###### Abstract

An $i$-packing in a graph $G$ is a set of vertices that are pairwise at
distance more than $i$. A _packing colouring_ of $G$ is a partition
$X=\\{X_{1},X_{2},\ldots,X_{k}\\}$ of $V(G)$ such that each colour class
$X_{i}$ is an $i$-packing. The minimum order $k$ of a packing colouring is
called the packing chromatic number of $G$, denoted by $\chi_{\rho}(G)$. In
this paper we investigate the existence of trees $T$ for which there is only
one packing colouring using $\chi_{\rho}(T)$ colours. For the case
$\chi_{\rho}(T)=3$, we completely characterise all such trees. As a by-product
we obtain sets of uniquely $3$-$\chi_{\rho}$-packable trees with monotone
$\chi_{\rho}$-colouring and non-monotone $\chi_{\rho}$-colouring respectively.

Keywords: colouring, broadcast, packing, tree, uniquely colourable, monotone
colouring, packing chromatic number

2020 MSC: 05C15, 05C70

##  1 Introduction

Packing colourings were inspired by a frequency assignment problem in
broadcasting. The distance between broadcasting stations is directly related
to the frequency they may receive, since two stations may only be assigned the
same frequency if they are located far enough apart for their frequencies not
to interfere with each other. This colouring was first introduced by Goddard
et al. [16] where it was called _broadcast colouring_. Brešar et al. [1] were
the first to use the term packing colouring.

Let $G=(V(G),E(G))$ be a simple graph of order $n$ and let $i$ be a positive
integer. A set $X\subseteq V(G)$ is called an _$i$ -packing_ if vertices in
$X$ are pairwise distance more than $i$ apart. A _packing colouring_ of $G$ is
a partition $X=\\{X_{1},X_{2},\ldots,X_{k}\\}$ of $V(G)$ such that each colour
class $X_{i}$ is an $i$-packing. Hence, two vertices may be assigned the same
colour if the distance between them is greater than the colour. The minimum
order $k$ of a packing colouring is called the _packing chromatic number_ of
$G$, denoted by $\chi_{\rho}(G)$.

Note that every packing colouring is a proper colouring. For terms and
concepts not defined here, see [3].

Goddard et al. [16] investigated among other things, the packing chromatic
number of paths, trees and the infinite square lattice, $Z^{2}$. They found
that for a tree of diameter two (that is, a star) the packing chromatic number
is $2$; for a tree of diameter three the packing chromatic number is $3$, and
for a tree of diameter $4$, they gave an explicit formula based on the number
of large neighbors (degree $4$ or more) and small neighbors (degree $3$ or
less) of the central vertex. They proved also that for all trees $T$ of order
$n$ it holds that $\chi_{\rho}(T)\leq\frac{n+7}{4}$, except when $n=4$ or
$n=8$ (when the bound is $\frac{1}{4}$ more) and these bounds are sharp.
Furthermore they proved that the minimum order of a tree $T$ with
$\chi_{\rho}(T)=2$, is 2; for a tree $T$ with $\chi_{\rho}(T)=3$, the minimum
order is $4$ and for a tree with $\chi_{\rho}(T)=4$, the minimum order is $8$.

The packing chromatic number of lattices, trees, and Cartesian products in
general is also considered in [1, 6, 7, 10, 13, 14] and [17]. Determining the
packing chromatic number is considered to be difficult. Finding $\chi_{\rho}$
for general graphs is NP-hard [16], and in fact, deciding whether
$\chi_{\rho}(G)\leq 4$ is already NP-complete. In [12], Fiala and Golovach
showed that the decision whether a tree allows a packing colouring with at
most $k$ classes is NP-complete.

Brešar, Klavžar and Rall introduced monotone colourings in [1]. Let $G$ be a
graph. For a colouring $c:V(G)\rightarrow\\{1,\ldots,k\\}$, and a colour $l$,
$1\leq l\leq k$, we denote by $c_{l}$ the cardinality of the class of vertices
coloured by $l$. A $\chi_{\rho}(G)$-colouring is monotone if $c_{1}\geq
c_{2}\geq\cdots\geq c_{k}$. They proved that for any graph $G$ and any $l$,
where $l\leq\left\lfloor\frac{\chi_{\rho}(G)}{2}\right\rfloor$, there exists a
$\chi_{\rho}(G)$-colouring $c:V(G)\rightarrow\\{1,...,k\\}$ such that
$c_{l}\geq c_{j}$ for all $j\geq 2l$. Note that this implies that for any
graph $G$ there exists an optimal colouring in which $c_{1}\geq c_{i}$ for
$2\leq i\leq k$. They also showed however, that there exists a class of trees
$T_{k}$, $k\geq 2$, in which no optimal colouring is monotone. The authors
proved that for any $k\geq 2$, $\chi_{\rho}(T_{k})=3$ and moreover, there
exists a unique optimal colouring of $T_{k}$ with $c_{1}=k+5$, $c_{2}=2$ and
$c_{3}=k+1$. In particular, $c_{3}>c_{2}.$

Several researchers have also investigated related topics on the packing
chromatic number and packing colourings for specific graph types, see [2, 5,
8, 9, 11, 15, 19] for results on cubic graphs, subdivided plane graphs,
Petersen graphs, Moore graphs, subcubic outerplanar graphs etc. In addition,
an integer linear programming and a satisfiability test model for the packing
colouring problem of graphs were developed in [18]. The proposed models in
[18] outperforms other exact methods such as a back-tracking and dynamic
algorithm.

Given the volume of publications that have been written on the packing
chromatic number and its growing interest, we refer the reader to the survey
article [4] on packing colourings by Brešar et al. for more details.

We call a graph $G$ uniquely $k$-$\chi_{\rho}$-packable if $\chi_{\rho}(G)=k$
and $G$ has a unique packing colouring of order $k$. By uniqueness of a
packing colouring we mean uniqueness up to identity. In other words, we work
with labelled graphs. For instance, $K_{2}$ has packing chromatic number 2,
but is not uniquely 2-$\chi_{\rho}$-packable.

The following terminology is used throughout: Given a graph $G$ and a
colouring of $V(G)$, an $i$-vertex is a vertex of colour $i$. We similarly use
the terms $i$-neighbour and $i$-leaf. We also use these terms if $G$ is
uniquely colourable, even if no colouring is specified.

In this paper we investigate uniquely-packable trees. We characterise the
uniquely $3$-$\chi_{\rho}$-packable trees, and investigate the existence of
uniquely $k$-$\chi_{\rho}$-packable trees for $k>3$. Our characterisation is
constructive. We proved that a tree is uniquely $3$-$\chi_{\rho}$-packable if
and only if it can be constructed from one of the three trees described in
Figure 1 by iteratively applying some finite sequence of operations as
described in 2.1. Furthermore, we showed that the monotonicity of the packing
colourings can also be determined by performing the same operations. As a by-
product of our investigation, we obtain sets of uniquely
$3$-$\chi_{\rho}$-packable trees with monotone $\chi_{\rho}$-colouring and
non-monotone $\chi_{\rho}$-colouring respectively.

The remainder of this paper is organised as follows. In Section 2 we
characterise those trees that are uniquely $3$-$\chi_{\rho}$-packable and
describe all operations that would be useful when constructing uniquely
$3$-$\chi_{\rho}$-packable trees. Section 3 investigates the monotonicity of
the packing colourings, by considering the three graphs, from which all
uniquely $3$-$\chi_{\rho}$-packable trees are constructed and show that their
colourings are monotone. This leads us to establishing sets of uniquely
$3$-$\chi_{\rho}$-packable trees with monotone $\chi_{\rho}$-colouring and
non-monotone $\chi_{\rho}$-colouring respectively. In the concluding Section
4.1 we considered the existence of uniquely $k$-$\chi_{\rho}$-packable trees
for $k>3$ and present a way to construct such trees for $4\leq k\leq 7$.

##  2 Uniquely $3$-$\chi_{\rho}$-packable trees

In this section we characterise those trees that are uniquely
$3$-$\chi_{\rho}$-packable. The special case of Claim 1 with $k=3$ and Lemma 1
will be used repeatedly throughout this section.

######  Claim 1.

If $c$ is a $k$-$\chi_{\rho}$-packing of a graph $G$, then every 1-vertex $v$
has degree at most $k-1$.

###### Proof.

Since no two neighbours of $v$ can have the same colour because of the
distance restraint between vertices of the same colour, $v$ is adjacent to at
most $k-1$ vertices. ∎

######  Lemma 1.

If $c$ is a $3$-$\chi_{\rho}$-packing of a graph $G$ with a 2-vertex $x$
adjacent to a 3-vertex $y$, then all neighbours of $x$ other than $y$ have
colour 1 and these vertices have no neighbours other than $x$.

###### Proof.

Clearly, vertices of $G$ can only be coloured with colours $1$, $2$ or $3$
since $c$ is a $3$-$\chi_{\rho}$-packing of the graph $G$. As a result, all
neighbours of $x$ other than $y$ can only have colour 1 because colour 2 and
colour 3 are not possible due to the distance constraint in the definition of
a packing colouring. In addition, observe that a 1-neighbour of the 2-vertex
$x$ does not have any new neighbour since since such a vertex can’t be
coloured in a $3$-$\chi_{\rho}$-packing of $G$. ∎

###  2.1 Characterisation of uniquely $3$-$\chi_{\rho}$-packable trees

Our characterisation is constructive. We start with one of the coloured trees
depicted in Figure 1, and iteratively apply one of the operations described
below and depicted in Figure 2. This produces all uniquely
$3$-$\chi_{\rho}$-packable trees, and only such trees, with the unique
3-colouring assigned.

Figure 1: The three graphs from which all uniquely 3-$\chi_{\rho}$-packable
trees are constructed.

${\mathcal{O}}_{1}$

Attach a new $1$-vertex to a $2$-vertex.

${\mathcal{O}}_{2}$

Attach a new $1$-vertex to a $3$-vertex that has a $2$-neighbour.

${\mathcal{O}}_{3}$

Attach a new $2$-vertex to a $1$-vertex that has no $2$-neighbours.

${\mathcal{O}}_{4}$

Attach a new $3$-vertex to a $1$-vertex that is at distance at least 3 from
all $3$-vertices.

${\mathcal{O}}_{5}$

Let $u$ be a 3-vertex. Add a path $P:v_{1},v_{2},v_{3}$, and the edge
$uv_{1}$. Give $v_{1}$, $v_{2}$ and $v_{3}$ the colours 1, 2 and 1,
respectively.

Note that ${\mathcal{O}}_{5}$ is a combination of
${\mathcal{O}}_{2},{\mathcal{O}}_{3}$ and ${\mathcal{O}}_{1}$ if $u$ has a
$2$-neighbour.

${\mathcal{O}}_{6}$

Let $u$ be a 3-vertex with no 2-neighbour. Add a path $P:v_{1},v_{2},v_{3}$,
and the edge $uv_{2}$. Give $v_{1}$, $v_{2}$, and $v_{3}$ the colours 1, 2 and
1, respectively.

${\mathcal{O}}_{7}$

Replace an edge $uv$, where $c(u)=3$, $c(v)=1$, and $\deg(u)=2$, with a path
$u,w_{1},w_{2},w_{3},w_{4},v$. Assign the colours 1,2,1 and 3 to
$w_{1},w_{2},w_{3}$, and $w_{4}$, respectively.

${\mathcal{O}}_{1}$$2$$1$${\mathcal{O}}_{2}$$2$$3$$1$${\mathcal{O}}_{3}$$1$$2$${\mathcal{O}}_{4}$$1$$3$${\mathcal{O}}_{5}$$3$$1$$2$$1$${\mathcal{O}}_{6}$$3$$2$$1$$1$$\rightarrow$${\mathcal{O}}_{7}$$3$$1$$3$$1$$2$$1$$3$$1$
Figure 2: The seven operations used to construct all uniquely
3-$\chi_{\rho}$-packable trees.

######  Lemma 2.

1

$F_{1}$, $F_{2}$ and $F_{3}$ are uniquely $3$-$\chi_{\rho}$-packable.

2

If any of the operations ${\mathcal{O}}_{i}$ is applied to a uniquely
$3$-$\chi_{\rho}$-packable tree $T^{\prime}$, the resulting tree $T$ is
uniquely $3$-$\chi_{\rho}$-packable.

3

If a uniquely $3$-$\chi_{\rho}$-packable tree $T$ is obtained from a tree
$T^{\prime}$ using operation ${\mathcal{O}}_{7}$, then $T^{\prime}$ is
uniquely $3$-$\chi_{\rho}$-packable.

###### Proof.

  * 1

This is easily verified by inspection.

  * 2

In the case of ${\mathcal{O}}_{2}$, ${\mathcal{O}}_{5}$ or
${\mathcal{O}}_{6}$, the new vertices can only be coloured in one way, given
the colours of the existing vertices.

For ${\mathcal{O}}_{1}$, note that the existing 2-vertex must be at distance
at most 2 from a 3-vertex, otherwise $T^{\prime}$ is a star, which is not
uniquely $3$-$\chi_{\rho}$-packable. The new vertex can therefore only receive
colour 1. Similar arguments apply to ${\mathcal{O}}_{3}$ and
${\mathcal{O}}_{4}$.

Next, we prove the lemma for the case of ${\mathcal{O}}_{7}$.

Let $T$ be obtained from $T^{\prime}$ by ${\mathcal{O}}_{7}$, and let $u$, $v$
and $w_{i}$ be as in the description of ${\mathcal{O}}_{7}$. Let $c^{\prime}$
be the unique $3$-$\chi_{\rho}$-packing of $T^{\prime}$ and let $c$ be a
$3$-$\chi_{\rho}$-packing of $T$ that differs from the
$3$-$\chi_{\rho}$-packing produced by ${\mathcal{O}}_{7}$.

If $c(u)=3$ and $c(v)=1$, there is only one way to colour the $w_{i}$’s, and
restricting $c$ to $T^{\prime}$ yields a $3$-$\chi_{\rho}$-packing of
$T^{\prime}$ different from $c^{\prime}$, contradicting the uniqueness of
$c^{\prime}$. Similarly if $c(u)=1$ and $c(v)=3$, or $c(u)=2$ and $c(v)=1$, or
$c(u)=1$ and $c(v)=2$.

Suppose $c(u)=3$ and $c(v)=2$. Again there is only one way to colour the
$w_{i}$’s $(c(w_{1})=1,c(w_{2})=2,c(w_{3})=1,c(w_{4})=3)$. Now suppose that
restricting $c$ to $T^{\prime}$ does not yield a proper colouring. Then the
neighbour $x$ of $u$ other than $w_{1}$ must have colour 2. Since $c(w_{4})=3$
and $c(v)=2$, and $c(u)=3$ and $c(x)=2$, it follows that $T^{\prime}$ is
obtained from two stars with centers corresponding to $x$ and $v$ by
identifying a leaf (corresponding to $u$) from each. But such a graph is not
uniquely $3$-$\chi_{\rho}$-packable.

A similar argument applies if $c(u)=2$ and $c(v)=3$.

We cannot have $c(u)=c(v)=2$ or $c(u)=c(v)=3$, since there is no way to colour
the $w_{i}$’s. That leaves $c(u)=c(v)=1$: The only possibility is for $w_{1}$,
$w_{2}$, $w_{3}$ and $w_{4}$ to be coloured 2, 1, 3 and 2, respectively. (The
fact that $u$ has degree 2 eliminates 2, 3, 1, 2.) So $v$ has degree 1 and we
can change its colour to 2 and restrict to $T^{\prime}$ to obtain a valid
colouring of $T^{\prime}$ that differs from $c^{\prime}$ on $u$.

  * 3

Let $c$ be the unique $3$-$\chi_{\rho}$-packing of $T$, suppose that
$T^{\prime}$ is not uniquely $3$-$\chi_{\rho}$-packable and let $c^{\prime}$
be a $3$-$\chi_{\rho}$-packing that differs from $c$ on $T^{\prime}$. Let $u$
and $v$ be the $3$\- and $1$-vertices (under $c$) of $T^{\prime}$ to which
${\mathcal{O}}_{7}$ is applied, respectively. We consider the following cases:
(Note that cases 2, 4, and 6 are not symmetric to their counterparts, because
of the degree constraint on $u$. This only plays a role in Case 5 and Case 6
though.)

Case 1: $c^{\prime}(u)=3$ and $c^{\prime}(v)=1$.
We extend $c^{\prime}$ to $T$ by colouring $w_{1}$, $w_{2}$, $w_{3}$ and
$w_{4}$ with 1, 2, 1 and 3, respectively, to contradict the uniqueness of $c$.

Case 2: $c^{\prime}(u)=1$ and $c^{\prime}(v)=3$.
We can reverse the sequence of colours in Case 1 above, that is extend
$c^{\prime}$ to $T$ by colouring $w_{1}$, $w_{2}$, $w_{3}$ and $w_{4}$ with
3,1,2 and 1, respectively.

Case 3: $c^{\prime}(u)=3$ and $c^{\prime}(v)=2$.
We extend $c^{\prime}$ to $T$ by colouring $w_{1}$, $w_{2}$, $w_{3}$ and
$w_{4}$ with 1, 2, 1 and 3, respectively.

Case 4: $c^{\prime}(u)=2$ and $c^{\prime}(v)=3$.
We reverse the sequence in Case 3, that is extend $c^{\prime}$ to $T$ by
colouring $w_{1}$, $w_{2}$, $w_{3}$ and $w_{4}$ with 1, 3, 1 and 2,
respectively, to contradict the uniqueness of $c$.

Case 5: $c^{\prime}(u)=1$ and $c^{\prime}(v)=2$.
The other neighbour $w$ of $u$ can only have $c^{\prime}(w)=3$, so $v$ has no
$3$-neighbour under $c^{\prime}$ and we can extend $c^{\prime}$ to $T$ by
colouring $w_{1}$, $w_{2}$, $w_{3}$ and $w_{4}$ with 2, 1, 3 and 1,
respectively..

Case 6: $c^{\prime}(u)=2$ and $c^{\prime}(v)=1$.
If the other neighbour $w$ of $u$ has $c^{\prime}(w)=1$, we extend
$c^{\prime}$ to $T$ by colouring $w_{1}$, $w_{2}$, $w_{3}$ and $w_{4}$ with 1,
3, 1 and 2, respectively. Otherwise, $c^{\prime}(w)=3$, so by Lemma 1, $v$ has
no other neighbours. Here we change the colour of $u$ to 1, and colour
$w_{1}$, $w_{2}$, $w_{3}$ and $w_{4}$ with 2, 1, 3 and 2, respectively.
Although we changed the colour of $u$, the extended colouring does differ from
$c$ because $c^{\prime}(w)=3$ but $c(w)\neq 3$ as $c(u)=3$.

All other cases are ruled out by the fact that $uv$ is an edge of
$T^{\prime}$. ∎

######  Lemma 3.

If $G$ is a uniquely $3$-$\chi_{\rho}$-packable graph, then $G$ has a 2-vertex
adjacent to a 3-vertex.

###### Proof.

Let $c$ be the unique $3$-$\chi_{\rho}$-packing of $G$ and suppose no 2-vertex
is adjacent to a 3-vertex. Then no two 2-vertices $x$ and $y$ are at distance
3, otherwise both $u$ and $v$ on any path $x,u,v,y$ must have colour 1. But
then we can interchange the colour classes 2 and 3, contradicting the
uniqueness of $c$. ∎

######  Lemma 4.

Let $F\subseteq T$ be trees, where $F$ is uniquely $3$-$\chi_{\rho}$-packable,
and let $v$ be any 3-vertex of $F$. For any $3$-$\chi_{\rho}$-packing $c$ of
$T$, the 3-vertices are precisely those vertices whose distance from $v$ is a
multiple of 4.

###### Proof.

Let $u$ be any vertex other than $v$ and consider the unique $v$–$u$ path
$P:v,v_{1},\ldots,v_{k}=u$. There are two possibilities for $c(v_{1})$, that
is, $c(v_{1})=2$ or $c(v_{1})=1$. If $c(v_{1})=2$, then $c(v_{2})=1$ (if
$v_{2}$ exists). It follows immediately from Lemma 1 that $k\leq 2$.
Otherwise, $c(v_{1})=1$, $c(v_{2})=2$, $c(v_{3})=1$ and $c(v_{4})=3$ (if these
vertices exist). Next, if $v_{5}$ exists, then there are again two
possibilities for $c(v_{5})$ that is, $c(v_{5})=2$ or $c(v_{5})=1$. Thus,
repeating the above process and continuing in this way the result follows. ∎

An immediate consequence of Lemma 4 is the following, which we will use
repeatedly henceforth.

######  Lemma 5.

Let $F\subseteq S\subseteq T$ be trees, where $F$ is uniquely
$3$-$\chi_{\rho}$-packable, and let $c$ be any $3$-$\chi_{\rho}$-packing of
$T$. For every $u\in V(S)$ and every $3$-$\chi_{\rho}$-packing $c^{\prime}$ of
$S$, we have $c^{\prime}(u)=3$ iff $c(u)=3$.

###### Proof.

Let $F\subseteq S$. Since $F$ is uniquely $3$-$\chi_{\rho}$-packable and
$c^{\prime}$ a $3$-$\chi_{\rho}$-packing on $S$, we have by Lemma 4 that for
each $v\in V(F)$ with $c(v)=3$, the $3$-vertices in $S$ are those at distance
$4i,i\in\mathbb{N}$, from $v$. Next, let $F\subseteq T$. Since $F$ is uniquely
$3$-$\chi_{\rho}$-packable and $c$ a $3$-$\chi_{\rho}$-packing on $T$, a
similar argument shows that for each $v\in V(F)$ with $c(v)=3$, the
$3$-vertices in $T$ are those at distance $4i,i\in\mathbb{N}$, from $v$. Hence
$c^{\prime}(u)=3$ iff $c(u)=3$ for all $u\in V(S)$. ∎

######  Theorem 6.

A tree $T$ is uniquely $3$-$\chi_{\rho}$-packable iff it is obtained from
$F_{1}$, $F_{2}$ or $F_{3}$ by zero or more applications of the operations
${\mathcal{O}}_{i}$, $i=1,\ldots,7$.

###### Proof.

It follows from the first two parts of Lemma 2 that all trees obtained in this
way are uniquely $3$-$\chi_{\rho}$-packable.

For the converse, let $T$ be a counterexample of minimum order. So, $T$ is
uniquely $3$-$\chi_{\rho}$-packable but $T$ cannot be obtained from any
smaller uniquely $3$-$\chi_{\rho}$-packable tree using the operations
${\mathcal{O}}_{i}$, $i=1,\ldots,7$. Let $c:V(T)\rightarrow\\{1,2,3\\}$ be the
3-$\chi_{\rho}$-packing of $T$.

Claim: $T$ contains $F_{1}$, $F_{2}$ or $F_{3}$ as a subgraph.

Let, according to Lemma 3, $x$ and $y$ be adjacent vertices with colours 2 and
3, respectively. By Lemma 1, all other neighbours of $x$ have colour 1 and can
have no further neighbours. Moreover, we show that there are at least two
vertices of colour 1 adjacent to $x$ in $T$. If none, we can recolour $x$ with
1 and so $T$ is not uniquely $3$-$\chi_{\rho}$-packable. If there exists a
unique vertex of colour 1 adjacent to $x$, say $u_{1}$, then we can give
$u_{1}$ colour 2 and $x$ colour 1. This again is a contradiction to the fact
that $T$ is uniquely $3$-$\chi_{\rho}$-packable.

Let $P:u_{1},x,y,u_{2},u_{3},\ldots,u_{\ell}$ be a longest path with end-
vertex $u_{1}$. We must have $\ell\geq 3$, otherwise $T$ is clearly not
uniquely $3$-$\chi_{\rho}$-packable.

If $y$ has degree at least 3, then $T$ contains $F_{1}$. Now assume
$\deg(y)=2$. Since $u_{2}$ has colour 1, it follows from Claim 1 that $u_{2}$
has degree 2. If $\ell<5$, then $c$ is not unique (interchange the colours of
$y$ and $u_{2}$). Assume therefore that $\ell\geq 5$.

Now if $\deg(u_{3})>2$, we have $F_{2}$ as subgraph, so let $\deg(u_{3})=2$.
Since $c(u_{4})=1$ we also have $\deg(u_{4})=2$. Again, if $\ell=5$, then $c$
is not unique since vertices of $P:$ $u_{1}$, $x$, $y$, $u_{2}$, $u_{3}$,
$u_{4}$, $u_{5}$ can be coloured $1,2,1,3,1,2,1$.

Therefore $\ell\geq 6.$ Suppose first that $u_{5}$ has a 2-neighbour $v$. If
$v$ is adjacent to one vertex, say $v_{1}$, then the colours of $v$ and
$v_{1}$ can be interchanged, which implies that $c$ is not unique. It follows
that $v$ has at least two neighbours other than $u_{5}$ (these have colour 1)
and they have no neighbours other than $v$. If $\deg(u_{5})>2$, $T$ contains
$F_{1}$, and so we let $\deg(u_{5})=2$. But then $c$ is not unique since we
can colour vertices $u_{1}$, $x$, $y$, $u_{2}$, $u_{3}$, $u_{4}$, $u_{5}$, $v$
with $1,2,1,3,1,2,1$ and $3$, respectively.

Suppose now that all neighbours of $u_{5}$ have colour 1. Any such neighbour
$z$ must have a $2$-neighbour $w$, otherwise we can change the colour of $z$
to 2 and $u_{5}$ has a $2$-neighbour as in the argument above. Also, $w$ must
have another $1$-neighbour, otherwise the colours of $z$ and $w$ can be
switched. Now, if $\deg(u_{5})>2$, $T$ contains $F_{3}$. Otherwise if
$\deg(u_{5})=2$, then $T$ is obtained from a smaller uniquely
$3$-$\chi_{\rho}$-packable tree by ${\mathcal{O}}_{7}$, using Lemma 2(3),
which is a contradiction.

Note that “being $k$-$\chi_{\rho}$-packable” is an hereditary property of
graphs: If a graph $G$ has the property, so does any subgraph $H$ of $G$,
since for any two vertices $u$, $v$ in $X_{i}\cap V(H)$, where $X_{i}$ is an
$i$-packing in $G$, the following holds: $d_{H}(u,v)\geq d_{G}(u,v)\geq i+1$.

Now we prove that any uniquely $3$-$\chi_{\rho}$-packable tree $T$ can only be
obtained from $F_{i}$, $i=1,2$ or $3$.

Let $F$ be the subtree $F_{1}$, $F_{2}$ or $F_{3}$ of the claim. If $T=F$ we
are done, so let $x$ be a leaf of $T$ that is not in $F$, and let $u$ be its
neighbour. We consider the following cases.

Case 1: $c(x)=2$.
Since $c(x)=2$, we have that $c(u)=1$, otherwise we can set $c(x)=1$,
contradicting the uniqueness of $c$. Then $u$ has degree $2$ and its neighbour
other than $x$, say $w$, must have colour $3$.

Let $T^{\prime}=T-x$. If $T^{\prime}$ is uniquely $3$-$\chi_{\rho}$-packable,
the minimality of $T$ is contradicted, since $T$ is obtained from $T^{\prime}$
using ${\mathcal{O}}_{3}$. So let $c^{\prime}$ be a $3$-$\chi_{\rho}$-packing
of $T^{\prime}$ that differs from $c$ on $T^{\prime}$.

We must have $c^{\prime}(u)=1$, otherwise we can extend $c^{\prime}$ to $T$,
by setting $c^{\prime}(x)=1$, to obtain a colouring of $T$ that differs from
$c$. By Lemma 5, $c^{\prime}(w)=3$, so we can set $c^{\prime}(x)=2$ and again
obtain a colouring of $T$ different from $c$, contradicting the fact that $c$
is a uniquely $3$-$\chi_{\rho}$-packing of $T$.

Case 2: $c(x)=3$.
Clearly, $c(x)=3$ implies that $c(u)=1$, otherwise we can set $c(x)=1$,
contradicting the uniqueness of $c$. Then $u$ has degree $2$ and its neighbour
other than $x$, say $w$, must have colour $2$. Let $T^{\prime}=T-x$. By the
minimality of $T$ and the fact that $T$ is obtained from $T^{\prime}$ using
${\mathcal{O}}_{4}$, there is a 3-$\chi_{\rho}$-packing $c^{\prime}$ of
$T^{\prime}$ that differs from $c$ on $T^{\prime}$. Again, $c^{\prime}(u)=1$,
following a similar argument as in Case 1 above.

From Lemma 5 it follows that we can extend $c^{\prime}$ to $T$ by setting
$c^{\prime}(x)=3$, contradicting the uniqueness of $c$.

Case 3: $c(x)=1$. For this case, we have two possibilities for $c(u)$.

  * •

$c(u)=3$.
If $c(u)=3$, then $u$ must have a 2-neighbour, otherwise we can change $c(x)$
to 2, contradicting the uniqueness of $c$. Again, if we let $T^{\prime}=T-x$,
then by the minimality of $T$, and the fact that $T$ is obtained from
$T^{\prime}$ using ${\mathcal{O}}_{2}$, there is a 3-$\chi_{\rho}$-packing
$c^{\prime}$ of $T^{\prime}$ that differs from $c$ on $T^{\prime}$. Hence, it
follows from Lemma 5 that any colouring of $T^{\prime}$ can be extended to $T$
by giving $x$ colour 1, and a contradiction follows as before.

  * •

$c(u)=2$.
Let $T^{\prime}=T-x$ and let $c^{\prime}$ be a 3-packing colouring of
$T^{\prime}$ that differs from $c$ on $T^{\prime}$. Such a colouring
$c^{\prime}$ exists by the minimality assumption of $T$ and the fact that $T$
is obtained from $T^{\prime}$ by applying ${\mathcal{O}}_{1}$.

Suppose first that the degree of $u$ is at least $4$ in $T$ (that is at least
3 in $T^{\prime}$). Then, $c^{\prime}(u)\neq 1$ by Claim 1, and we can extend
$c^{\prime}$ to $T$ by letting $c^{\prime}(x)=1$. This contradicts our
assumption that $T$ is uniquely $3$-$\chi_{\rho}$-packable since $c$ and
$c^{\prime}$ differ on at least one vertex of $T^{\prime}$. Thus, we now
assume that the degree of $u$ in $T$ is either $2$ or $3$.

Suppose that $\deg(u)=2$. Let $v$ be the other neighbour of $u$. Then
$c(v)=1$, otherwise we can swap the colours of $x$ and $u$. Now, $v$ has
degree 2 and its other neighbour, $w$ say, has colour 3. Let $T^{\prime}$ be
obtained from $T$ by removing those of $x$, $u$ and $v$ that do not belong to
$F$. (If $u\in V(F)$, then so is $v$, hence $T^{\prime}$ is a tree.) Note that
$T$ is obtained from $T^{\prime}$ using some combination of
${\mathcal{O}}_{1}$, ${\mathcal{O}}_{2}$ and ${\mathcal{O}}_{3}$ in most
cases. If $T^{\prime}=T-\\{x,u,v\\}$, then $T$ can be obtained from
$T^{\prime}$ by using ${\mathcal{O}}_{5}$. Consider a
$3$-$\chi_{\rho}$-packing $c^{\prime}$ of $T^{\prime}$ that differs from $c$
on $T^{\prime}$. By Lemma 5 we have $c^{\prime}(w)=3$. Those of $u$ and $v$
that belong to $F$ can only be coloured as by $c$. Those not belonging to $F$
can be replaced, together with $x$, and coloured as by $c$, contradicting the
uniqueness of $c$.

Therefore, we have $\deg(u)=3$. Let $y$ and $z$ be the other two neighbours of
$u$. Suppose first that both have colour 1. One of them, say $y$, must have
another neighbour $w$, which can only have colour 3. Since $T^{\prime}=T-x$
and considering that in any $3$-$\chi_{\rho}$-packing $c^{\prime}$ of
$T^{\prime}$, we have $c^{\prime}(w)=3$ by Lemma 5, there is only one way to
colour $u$, $y$ and $z$, hence a contradiction with the minimality of $T$
follows.

So $y$, say, has colour 1 and $z$ has colour 3. Examining the graphs $F_{i}$,
it is easily checked that $u$ and $y$ cannot belong to $F$. (Note that $y$ has
degree 1.) We remove $x$, $y$ and $u$ to obtain $T^{\prime}$, note that $T$ is
obtained from $T^{\prime}$ using ${\mathcal{O}}_{6}$ and consider a
$3$-$\chi_{\rho}$-packing $c^{\prime}$ of $T^{\prime}$ that differs from $c$
on $T^{\prime}$.

By Lemma 5, $c^{\prime}(z)=3$. If $z$ has no neighbour $w$ with
$c^{\prime}(w)=2$, we are done, as $c^{\prime}$ can be extended to $T$ in the
obvious way, so suppose that such a $w$ exists. We must have $c(w)=1$, so,
since $c^{\prime}(w)\neq c(w)$, we cannot have $w\in V(F)$, because $F$ is
uniquely $3$-$\chi_{\rho}$-packable. If $w$ is a leaf we therefore have the
case $c(u)=3$, so suppose $w$ has another neighbour $s$. Then
$c^{\prime}(s)=1$, $c(s)=2$ and $s$ is a leaf (considering $c^{\prime}(z)=3$
and $c^{\prime}(w)=2$). Therefore we have Case 1 and the proof is complete.

∎

##  3 Monotonocity of the packing colouring

In this section, we consider the three graphs, $F_{1}$-$F_{3}$, described in
2.1, from which all uniquely $3$-$\chi_{\rho}$-packable trees are constructed
and show that their colourings are monotone. In addition, we show that by
iteratively applying any one of the operations
${\mathcal{O}}_{1}-{\mathcal{O}}_{7}$, we show that there exists a uniquely
$3$-$\chi_{\rho}$-packable tree, $T_{k}$, with no monotone
$\chi_{\rho}$-colouring. As a by-product we obtain sets of uniquely
$3$-$\chi_{\rho}$-packable trees with monotone $\chi_{\rho}$-colouring and
non-monotone $\chi_{\rho}$-colouring respectively.

######  Definition 7.

Let $G$ be a graph. For a colouring $c:V(G)\rightarrow\\{1,2,3\\}$, and a
colour $m$, $1\leq m\leq 3$, let $c_{m}=|\\{v\in V(G):c(v)=m\\}|$, that is,
$c_{m}$ is the cardinality of the class of vertices, coloured by $m$. We say
that $c$ is monotone if

$c_{1}\geq c_{2}\geq c_{3}.$

######  Proposition 8.

[1] For any graph $G$ and any $m$, where
$m\leq\lfloor\chi_{\rho}(G)/2\rfloor$, there exists a
$\chi_{\rho}(G)$-colouring $c:V(G)\rightarrow\\{1,\cdots,k\\}$ such that
$c_{m}\geq c_{n}$ for all $n\geq 2m$.

Note that Proposition 8 above implies that for any graph that is
$\chi_{\rho}$-packable, $c_{m}\geq c_{2m}$ and $c_{m}\geq c_{2m+1}$ and
$c_{m}\geq c_{2m+2}$ etc. In particular, for any graph $G$, there exists an
optimal colouring in which vertices of colour 1 are the most frequent.

Recall the illustrations of the trees $F_{1}$, $F_{2}$ and $F_{3}$ in Figure
1. Observe that for $F_{1}$ and $F_{3}$, $c_{1}>c_{2}>c_{3}$ and for $F_{2}$,
$c_{1}>c_{2}\geq c_{3}$. Hence, we conclude that $F_{i}$’s are uniquely
$3$-$\chi_{\rho}$-packable trees with monotone optimal colouring.

Clearly, by iteratively applying any of the operations ${\mathcal{O}}_{i}$
defined in 2.1 to our $F_{i}$’s, we have by Lemma 2 that the resulting trees
are uniquely $3$-$\chi_{\rho}$-packable. We show in the next section that
applying some of the operations ${\mathcal{O}}_{i}$ to the $F_{i}$’s, we
obtain uniquely $3$-$\chi_{\rho}$-packable trees, say $T_{\ell,k}$ and
$T_{k}$, with monotone and non-monotone colouring respectively. We begin by
labeling the vertices of $F_{i}$’s, as illustrated in Figure 3.

$u$$2$$1$$1$$1$$y$$v$$x$$2$$3$$1$$u$$2$$1$$1$$1$$y$$z$$v$$x$$2$$3$$1$$1$$3$
$u$$2$$1$$1$$y$$v$$x$$2$$3$$1$$1$$3$$1$$2$$1$$1$$2$$1$ Figure 3: The trees
$F_{1}$, $F_{2}$ and $F_{3}$ from which all uniquely 3-$\chi_{\rho}$-packable
trees are constructed.

###  3.1 Classes of uniquely $3$-$\chi_{\rho}$-packable trees with monotone
and non monotone colouring

We define a $\tau$-path to be a path of length $\tau$. Let $T_{k}$, $k\geq 2$,
be a class of trees that consists of a $3$-path on consecutive vertices
$u,v,x,y$, each of $u$ and $v$ having two leaves, and there are $k$ paths of
length $2$ that emerge from $y$. The tree $T_{k}$ was first described in [1].
Figure 4, depicts the family of trees $T_{k}$ from which a set of uniquely
3-$\chi_{\rho}$-packable trees with non-monotone colouring is constructed.

$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$u$$v$$x$$y$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$2$$1$$1$$3$$1$$1$$1$$2$$1$$3$$1$$3$$1$$3$$1$$3$
Figure 4: The tree $T_{k}$ from which a set of uniquely
$3$-$\chi_{\rho}$-packable trees with non-monotone colouring is constructed.

Clearly, $T_{k}$ is obtained from $F_{1}$ by applying the operations
${\mathcal{O}}_{i}$’s for $i\in\\{1,2,4\\}$ to the vertices. In particular,
$T_{k}$ is obtained from $F_{1}$ by applying ${\mathcal{O}}_{2}$ to $v$ once,
applying ${\mathcal{O}}_{1}$ to $y$, $k$-times, and finally applying
${\mathcal{O}}_{4}$ to the $k$ vertices adjacent to $y$ respectively.

Similarly, $T_{k}$ is obtained from $F_{2}$ by applying the operations
${\mathcal{O}}_{i}$’s for $i\in\\{1,2,4\\}$ to vertices $v$ and $y$ in a
manner described below. Apply ${\mathcal{O}}_{2}$ to $v$ twice,
${\mathcal{O}}_{1}$ to $y$, $t$-times such that $t=k-2$, and finally applying
${\mathcal{O}}_{4}$ to $z$ and the newly added $t$ vertices adjacent to $y$
respectively.

By applying similar operation to $F_{3}$, we obtain another tree, say
$F^{\prime}_{3}$, such that $T_{k}\subseteq F^{\prime}_{3}$. In particular,
$F^{\prime}_{3}$ is obtained by applying ${\mathcal{O}}_{2}$ to to $v$ twice,
applying ${\mathcal{O}}_{1}$ to $y$, $t^{\prime}$-times such that
$t^{\prime}=k-1\geq 3$, and finally applying ${\mathcal{O}}_{4}$ to the newly
added $t^{\prime}$ vertices adjacent to $y$ respectively. Since both $T_{k}$
and $F^{\prime}_{3}$ were obtained from $F_{i}$’s by applying the operations
${\mathcal{O}}_{1}$, ${\mathcal{O}}_{2}$ and ${\mathcal{O}}_{4}$, then by
Lemma 2.1, we have that $F^{\prime}_{3}$ is a uniquely
$3$-$\chi_{\rho}$-packable trees but with no monotone colouring.

The following shows that we can obtain a $3$-$\chi_{\rho}$-packable tree with
monotone colouring from $T_{k}$ by extending the definitions and applying some
of the operations ${\mathcal{O}}_{i}$ to some vertices of $T_{k}$.

For $\ell,k\geq 2$, define $T_{\ell,k}$ to be a class of trees that consists
of a $3$-path on consecutive vertices $u,v,x,y$, with vertex $u$ having two
leaves, and there are $\ell$ paths and $k$ paths of length $2$ emerging from
$v$ and $y$ respectively. Figure 5, shows the family of trees $T_{\ell,k}$
from which a set of uniquely 3-$\chi_{\rho}$-packable trees with monotone
colouring is constructed.

$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$u$$v$$x$$y$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$2$$1$$1$$3$$1$$1$$2$$2$$1$$2$$1$$2$$1$$2$$1$$3$$1$$3$$1$$3$$1$$3$
Figure 5: The tree $T_{\ell,k}$ from which a set of uniquely
3-$\chi_{\rho}$-packable trees with monotone colouring is constructed.

Clearly, the tree $T_{\ell,k}$ is an extension of $T_{k}$, which is obtained
by applying some of the operations ${\mathcal{O}}_{i}$’s in a manner described
below. Apply ${\mathcal{O}}_{2}$ to $v$, $t$-times such that $t=\ell-2\geq
k-3$, ${\mathcal{O}}_{3}$ to all $v^{\prime}$ in $N[v]-\\{u,x\\}$.

Since $T_{k}$ is a uniquely 3-$\chi_{\rho}$-packable tree and $T_{\ell,k}$ is
obtained from $T_{k}$ by applying the operations ${\mathcal{O}}_{i}$’s, we
have by Lemma 2.1 that $T_{\ell,k}$ is also a uniquely
3-$\chi_{\rho}$-packable tree. Moreover, since $T_{\ell,k}$ satisfies the
conditions of Definition 7, we conclude that $T_{\ell,k}$ is a set of uniquely
3-$\chi_{\rho}$-packable trees with monotone colouring.

##  4 Conclusion

In this paper we completely characterised all trees $T$ for which there is
only one packing colouring using $\chi_{\rho}(T)=3$ colours. We further
investigated the monotonicity of the packing colouring and obtained sets of
uniquely $3$-$\chi_{\rho}$-packable trees with monotone
$\chi_{\rho}$-colouring and non-monotone $\chi_{\rho}$-colouring respectively.
We now consider the existence of uniquely $k$-$\chi_{\rho}$-packable trees for
$k>3$ which pose an open question

###  4.1 Uniquely $k$-$\chi_{\rho}$-packable trees

We now consider the existence of uniquely $k$-$\chi_{\rho}$-packable trees for
$k>3$. In Figure 6 we give examples of uniquely $k$-$\chi_{\rho}$-packable
trees for $k=3,\ldots,7$. Here, a circle represents a vertex which has
sufficiently many unshown leaf neighbours so as to ensure its degree is at
least $k$, so that the vertex cannot receive colour 1 by Observation 1. Solid
vertices have no hidden neighbours. For instance, $T_{3}$ represents the graph
$F_{1}$ of the previous section. We mention that these examples can be adapted
to obtain examples of arbitrary diameter.

Figure 6: Uniquely $k$-$\chi_{\rho}$-packable trees, $k=3,\ldots,7$.

These examples were found and verified with the aid of a computer. While a
pattern seems to emerge, the approach fails for $k\geq 8$. In fact, we are not
sure that examples exist for all $k$. We will state this as:

######  Question 1.

Do uniquely $k$-$\chi_{\rho}$-packable trees exist for all $k$?

Proving uniqueness of the given colourings can be done with a straightforward
but tedious case analysis. We give a proof for $T_{6}$ to illustrate a useful
technique that considerably reduces the amount of work required:

Consider any $6$-$\chi_{\rho}$-packing $c$ of $T_{6}$. Let $F$ be the subgraph
of $T_{6}$ induced by all vertices at distance 2 or less from the 6-vertex.
Two copies of $F$ are depicted in Figure 7. There can be at most one 4-vertex,
at most one 5-vertex and at most one 6-vertex in $F$, since $F$ has diameter
4. Consider the sets $A_{1},A_{2},A_{3}$ and $B_{1},B_{2},B_{3}$ indicated in
Figure 7. The $A_{i}$’s form a partition of $V(F)$ and each $A_{i}$ has
diameter at most 2. Therefore there are at most three 2-vertices. The
$B_{i}$’s similarly partition $V(F)$ into sets of diameter at most 3, hence
there are at most three 3-vertices.

Since $F$ has nine vertices, it follows that there must be three 2-vertices,
one from each $A_{i}$, three 3-vertices, one from each $B_{i}$, and one vertex
of each of the colours 4, 5 and 6. But $B_{3}$ has only one element, call it
$x$, so $c(x)=3$. Since $|A_{3}-x|=1$, the neighbour of $x$ must have colour
2. Now the vertices of $F$ coloured 4,5 and 6 in Figure 6 must have those
colours, in some order.

Figure 7: The subgraph $F$ of $T_{6}$ used in the uniqueness proof. Figure 8:
The subgraph $F^{\prime}$ of $T_{6}$.

Now consider the subgraph $F^{\prime}$ of $T_{6}$ induced by all vertices at
distance 3 or less from the 6-vertex, and consider the subsets indicated in
Figure 8. Each of the four sets at the top must contain a 2-vertex, and each
of the two sets at the bottom must contain a 3-vertex. From this the positions
of these vertices follow easily.

Considering all of $T_{6}$ it follows that there must be two 4-vertices and
two 5-vertices, and there is only one way to place these and complete the
colouring. ∎

We have no conflicts of interest. No data was used for the research described
in the article.

## Acknowledgements

Financial support by the DSI-NRF Centre of Excellence in Mathematical and
Statistical Sciences (CoE-MaSS), South Africa is gratefully acknowledged.

## References

  * [1] B. Brešar, S. Klavžar, D.F. Rall, On the packing chromatic number of Cartesian products, hexagonal lattice, and trees, _Discrete Applied Mathematics_ , 155 (2007) 2303-2311
  * [2] B. Brešar and J. Ferme, An infinite family of subcubic graphs with unbounded packing chromatic number, _Discrete Math._ 341 (2018) 2337–2342.
  * [3] G. Chartrand, L. Lesniak, P. Zhang, Graphs & Digraphs, Fifth Edition, CRC Press, 2011.
  * [4] B. Brešar, J. Ferme, S. Klavžar, D.F. Rall, A survey on packing colorings. _Discussiones Mathematicae Graph Theory_ 40 (2020) 923–970.
  * [5] B. Brešar, S. Klavžar, D.F. Rall and K.Wash, Packing chromatic number, $(1,1,2,2)$-colorings, and characterizing the Petersen graph, _Aequationes Math._ 91 (2017) 169-184.
  * [6] B. Subercaseaux, M.J. Heule, The packing chromatic number of the infinite square grid is 15, _arXiv:2301.09757_ , (2023).
  * [7] C. Sloper, Broadcast-coloring in trees, TR 233, University of Bergen, 2002.
  * [8] J. Balogh, A. Kostochka and X. Liu, Packing chromatic number of cubic graphs, _Discrete Math._ 341 (2018), 474–483.
  * [9] J. Balogh, A. Kostochka and X. Liu, Packing chromatic number of subdivisions of cubic graphs, _Graphs Combin._ 35 (2019) 513–537.
  * [10] J. Ekstein, J. Fiala, P. Holub, B. Lidický, The packing chromatic number of the square lattice is at least 12, _arXiv:1003.2291v1_ , 2010.
  * [11] J. Ekstein, P. Holub and O. Togni, The packing coloring of distance graphs $D(k,t)$, _Discrete Appl. Math._ 167 (2014) 100–106.
  * [12] J. Fiala, P.A. Golovach, Complexity of the packing coloring problem for trees, _Discrete Applied Mathematics_ , 158 (2010) 771-778.
  * [13] J. Fiala, S. Klavžar, B. Lidický, The packing chromatic number of infinite product graphs, _European Journal of Combinatorics_ , 30 (2009) 1101-1113.
  * [14] A.S. Finbow, D.F. Rall, On the packing chromatic number of some lattices, _Discrete Applied Mathematics_ , 158 (2010) 1224-1228.
  * [15] J. Fresán-Figueroa, D. González-Moreno and M. Olsen, On the packing chromatic number of Moore graphs. _Discrete Applied Mathematics_ , 289 (2021) 185-193.
  * [16] W. Goddard, J.M. Harris, S.M. Hedetniemi, S.T. Hedetniemi, D.F. Rall, Broadcast chromatic numbers of graphs, _Ars Combinatoria_ , 86 (2008) 33-49.
  * [17] P. Holub, R. Soukal, A note on packing chromatic number of the square lattice, _Electronic Journal of Combinatorics_ , N17 (2010).
  * [18] Z. Shao, A. Vesel, Modeling the packing coloring problem of graphs, _Applied Mathematical Modelling. 39(13)_ (2015), 3588-3599
  * [19] O. Togni, On packing colorings of distance graphs, _Discrete Appl. Math. 167_ (2014) 280–289.