# ACTC: Active Threshold Calibration
for Cold-Start Knowledge Graph Completion

Anastasiia Sedova1 Benjamin Roth1,2
1 Research Group Data Mining and Machine Learning, University of Vienna,
Austria
2 Faculty of Philological and Cultural Studies, University of Vienna, Austria
{anastasiia.sedova<EMAIL_ADDRESS>
###### Abstract

Self-supervised knowledge-graph completion (KGC) relies on estimating a
scoring model over (entity, relation, entity)-tuples, for example, by
embedding an initial knowledge graph. Prediction quality can be improved by
calibrating the scoring model, typically by adjusting the prediction
thresholds using manually annotated examples. In this paper, we attempt for
the first time _cold-start_ calibration for KGC, where no annotated examples
exist initially for calibration, and only a limited number of tuples can be
selected for annotation.

Our new method ACTC finds good per-relation thresholds efficiently based on a
limited set of annotated tuples. Additionally to a few annotated tuples, ACTC
also leverages unlabeled tuples by estimating their correctness with Logistic
Regression or Gaussian Process classifiers. We also experiment with different
methods for selecting candidate tuples for annotation: density-based and
random selection. Experiments with five scoring models and an oracle annotator
show an improvement of 7% points when using ACTC in the challenging setting
with an annotation budget of only 10 tuples, and an average improvement of 4%
points over different budgets.

##  1 Introduction

Knowledge graphs (KG) organize knowledge about the world in the form of a
graph where entities (nodes) are connected by different relations (edges).
Knowledge-graph completion (KGC) task aims at adding the new information in a
form of (entity, relation, entity) triples to the knowledge graph. The main
objective is assigning to each triple a plausibility score, which defines how
likely this triple belongs to the underlying knowledge base. These scores are
usually predicted by the knowledge graph embedding (KGE) models. However, most
of the KGC approaches do not make any binary decision and provide a ranking,
not classification, which does not allow one to use them as-is to populate the
KGs Speranskaya et al. (2020). To transform the scores into predictions (i.e.,
how probable is it that this triple should be included in the knowledge base),
decision thresholds need to be estimated. Then, all triples that have a
plausibility score above the threshold are classified as positive and included
in the KG; the others are predicted to be negatives and not added to the KG.
Since the initial KG includes only positive samples and thus cannot be used
for threshold calibration, the calibration is usually performed on manually
annotated set of positive and negative tuples (decision set). However, manual
annotation is costly and limited, and, as most knowledge bases include dozens
Ellis et al. (2018), hundreds Toutanova and Chen (2015) or even thousands Auer
et al. (2007) of different relation (types), obtaining a sufficient amount of
labeled samples for each relation may be challenging. This raises a question:
How to efficiently solve the cold-start thresholds calibration problem with
minimal human input?

We propose a new method for Active Threshold Calibration ACTC, which estimates
the relation thresholds by leveraging unlabeled data additionally to human-
annotated data. In contrast to already existing methods Safavi and Koutra
(2020); Speranskaya et al. (2020) that use only the annotated samples, ACTC
labels the additional samples automatically with a trained predictor (Logistic
Regression or Gaussian Process model) estimated on the KGE model scores and
available annotations. The multiple experiments on several datasets and with
different KGE models demonstrate the efficiency of ACTC for different amounts
of available annotated samples, even for as little as one.

##  2 Related Work

Knowledge graph embedding methods Dettmers et al. (2017); Trouillon et al.
(2016); Bordes et al. (2013); Nickel et al. (2011) have originally been
evaluated on ranking metrics, not on the actual task of triple classification,
which would be necessary for KGC. More recent works have acknowledged this
problem by creating data sets for evaluating KGC (instead of ranking), and
proposed simple algorithms for finding prediction thresholds from annotated
triples Speranskaya et al. (2020); Safavi and Koutra (2020). In our work, we
study the setting where only a limited amount of such annotations can be
provided, and experiment with different strategies of selection samples for
annotation, and analyse how to use them best. Ostapuk et al. (2019) have
studied active learning for selecting triples for training a scoring model for
KG triples, but their method cannot perform the crucial step of calibration.
They consequently only evaluate on ranking metrics, not measuring actual link
prediction quality. In contrast, our approach focuses on selecting much fewer
samples for optimal _calibration_ of a scoring model (using positive, negative
and unlabeled samples).

##  3 ACTC: Active Threshold Calibration

ACTC consists of three parts: selection of samples for manual annotation,
automatic labeling of additional samples, and estimating the per-relation
thresholds basing on all available annotations. A graphical illustration is
provided in Figure 1, the pseudocodes can be found in Appendix A111The code
will be publicly released on acceptance. In the current submission, the code
is uploaded as suppl. material..

The first step is selecting unlabeled samples for human annotation. In ACTC
this can be done in two ways. One option is simple random sampling from the
set of all candidate tuples ($\textbf{ACTC}_{rndm}$). However, not all
annotations are equally helpful and informative for estimation. To select the
representative and informative samples that the system can profit the most
from, especially with a small annotation budget, we also introduce density-
based selection $\textbf{ACTC}_{dens}$, inspired by the density-based
selective sampling method in active learning Agarwal et al. (2020); Zhu et al.
(2008). The sample density is measured by summing the squared distances
between this sample’s score (predicted by the KGE model) and the scores of
other samples in the unlabeled dataset. The samples with the highest density
are selected for human annotation.

Figure 1:  ACTC method. The manually annotated samples are used to train a
Logistic Regression or Gaussian Processes classifier, which labels the
additional tuples using their scores predicted by a KGE model. All annotations
(manual and automatic) are later used to estimate the per-relation thresholds.

Considering the costs and hence the limited amount of manual annotations
available, there are sometimes only a few samples annotated for some relations
and not even one for others. To mitigate this negative effect and obtain a
decent result even in such strict conditions, ACTC labels more samples
(additionally to the manual annotations) with a classifier trained on the
manually annotated samples to predict the labels based on the KGE model
scores. We experiment with two classifiers: Logistic Regression (ACTC-LR) and
Gaussian Processes (ACTC-GP). The amount of automatically labeled samples
depends on hyper-parameter $n$, which reflects the minimal amount of samples
needed for estimating each threshold (see ablation study of different n values
in Section 5). If the size of the annotation budget $l_{r}$ for a relation $r$
is larger or equal to $n$, only these $l_{r}$ annotated samples are used for
threshold estimation. If the amount of manually annotated samples is
insufficient (i.e., less than $n$), the additional $n-l_{r}$ samples are
randomly selected from the dataset and labeled by a LR or GP classifier. The
automatically labeled and manually annotated samples build a threshold
decision set, which contains at least $n$ samples with labels (manual or
predicted ones).

| CoDEx-s | CoDEx-m | Avg
---|---|---|---
| ComplEx | ConvE | TransE | RESCAL | ComplEx | ConvE | TransE | RESCAL |  |
| Acc | F1 | Acc | F1 | Acc | F1 | Acc | F1 | Acc | F1 | Acc | F1 | Acc | F1 | Acc | F1 | Acc | F1
LocalOpt (Acc) | 70 | 70 | 72 | 72 | 69 | 68 | 74 | 73 | 72 | 70 | 68 | 66 | 65 | 64 | 68 | 67 | 70 | 69
Safavi and Koutra (2020) | $\pm 3$ | $\pm 3$ | $\pm 3$ | $\pm 2$ | $\pm 3$ | $\pm 3$ | $\pm 2$ | $\pm 2$ | $\pm 2$ | $\pm 2$ | $\pm 3$ | $\pm 2$ | $\pm 3$ | $\pm 3$ | $\pm 3$ | $\pm 2$ |  |
LocalOpt (F1) | 67 | 69 | 69 | 70 | 65 | 67 | 70 | 71 | 70 | 69 | 66 | 66 | 63 | 64 | 66 | 67 | 67 | 68
$\pm 3$ | $\pm 3$ | $\pm 3$ | $\pm 2$ | $\pm 3$ | $\pm 3$ | $\pm 2$ | $\pm 2$ | $\pm 2$ | $\pm 2$ | $\pm 2$ | $\pm 2$ | $\pm 3$ | $\pm 3$ | $\pm 3$ | $\pm 2$ |  |
GlobalOpt (F1) | 70 | 74 | 74 | 77 | 68 | 71 | 76 | 79 | 73 | 75 | 68 | 70 | 65 | 68 | 68 | 71 | 70 | 73
Speranskaya et al. (2020) | $\pm 2$ | $\pm 2$ | $\pm 1$ | $\pm 2$ | $\pm 2$ | $\pm 2$ | $\pm 1$ | $\pm 1$ | $\pm 1$ | $\pm 2$ | $\pm 1$ | $\pm 2$ | $\pm 2$ | $\pm 2$ | $\pm 1$ | $\pm 2$ |  |
$ACTC-LR_{dens}$ | 72 | 72 | 77 | 78 | 69 | 71 | 80 | 81 | 78 | 77 | 72 | 71 | 64 | 65 | 72 | 70 | 73 | 73
$\pm 3$ | $\pm 2$ | $\pm 1$ | $\pm 1$ | $\pm 2$ | $\pm 2$ | $\pm 1$ | $\pm 1$ | $\pm 0$ | $\pm 1$ | $\pm 1$ | $\pm 1$ | $\pm 1$ | $\pm 1$ | $\pm 1$ | $\pm 1$ |  |
$ACTC-GP_{dens}$ | 72 | 72 | 76 | 78 | 69 | 71 | 80 | 80 | 78 | 77 | 72 | 70 | 64 | 65 | 73 | 71 | 73 | 73
$\pm 3$ | $\pm 2$ | $\pm 1$ | $\pm 1$ | $\pm 1$ | $\pm 2$ | $\pm 1$ | $\pm 1$ | $\pm 0$ | $\pm 0$ | $\pm 1$ | $\pm 1$ | $\pm 2$ | $\pm 2$ | $\pm 2$ | $\pm 1$ |  |
$ACTC-LR_{rndm}$ | 74 | 74 | 77 | 77 | 73 | 72 | 79 | 79 | 78 | 78 | 72 | 72 | 69 | 69 | 73 | 73 | 74 | 74
$\pm 3$ | $\pm 2$ | $\pm 2$ | $\pm 2$ | $\pm 3$ | $\pm 3$ | $\pm 1$ | $\pm 1$ | $\pm 1$ | $\pm 1$ | $\pm 2$ | $\pm 2$ | $\pm 3$ | $\pm 2$ | $\pm 2$ | $\pm 2$ |  |
$ACTC-GP_{rndm}$ | 74 | 74 | 77 | 77 | 73 | 72 | 81 | 81 | 77 | 77 | 71 | 71 | 67 | 66 | 72 | 71 | 74 | 74
$\pm 3$ | $\pm 2$ | $\pm 2$ | $\pm 2$ | $\pm 3$ | $\pm 3$ | $\pm 1$ | $\pm 1$ | $\pm 1$ | $\pm 1$ | $\pm 2$ | $\pm 2$ | $\pm 3$ | $\pm 3$ | $\pm 2$ | $\pm 2$ |  |
Table 1: ACTC results in % averaged across different sizes of annotation
budget reported with the standard error of the mean. The experiment with each
annotation budget was repeated 100 times.

The final part of the algorithm is the estimating of the relation-specific
thresholds. Each sample score from the decision set is tried out as a
potential threshold; the relation-specific thresholds that maximize the
calculated for this decision set local accuracy are selected.

##  4 Experiments

Figure 2: $ACTC-LR_{rndm}$ (upper) and $ACTC-LR_{dens}$ (lower) performance
for different amounts of manually annotated samples and with different KGE
models.

We evaluate our method on two KGC benchmark datasets extracted from Wikidata
and augmented with manually verified negative samples: CoDEx-s and
CoDEx-m222The third CoDEx dataset, CoDEx-L, is not used in our experiments as
it does not provide negative samples. Safavi and Koutra (2020). Some details
on their organization are provided in Appendix B. The KGE models are trained
on the training sets333We use the trained models provided by dataset authors..
The ACTC algorithm is applied on the validation sets: the gold validation
labels are taken as an oracle (manual annotations; in an interactive setting
they would be presented to human annotators on-the-fly); the remaining samples
are used unlabeled. The test set is not exploited during ACTC training and
serves solely for testing purposes. The dataset statistics is provided in
Table 2.

Data | #Train | #Val | #Test | #Ent | #Rel
---|---|---|---|---|---
CoDEx-S | 32,888 | 3,654 | 3,656 | 2,034 | 42
CoDEx-M | 185,584 | 20,620 | 20,622 | 17,050 | 51
Table 2:  Datasets statistics. The training sets contain only positive
triples. The ratio of positive to negative samples in validation and test sets
is 1:1.

We run our experiments with four KGE models: ComplEx Trouillon et al. (2016),
ConvE Dettmers et al. (2017), TransE Bordes et al. (2013), RESCAL Nickel et
al. (2011). More information is provided in Appendix C.

###  4.1 Baselines

ACTC is compared to three baselines. The first baseline LocalOpt (Acc)
optimizes the per-relation thresholds towards the accuracy: for each relation,
the threshold is selected from the (embedding) scores assigned to the samples
with manual annotations that contain this relation, so that the local accuracy
(i.e., accuracy, which is calculated only for these samples) is maximized
(Safavi and Koutra, 2020). We also modified this approach into LocalOpt (F1)
by changing the maximization metric to the local F1 score. The third baseline
is GlobalOpt, where the thresholds are selected by iterative search over a
manually defined grid Speranskaya et al. (2020). The best thresholds are
selected based on the global F1 score calculated for the whole
dataset444Labels for samples that include relations for which thresholds have
not yet been estimated are calculated using the default threshold of 0.5.. In
all baselines, the samples for manual annotation are selected randomly.

###  4.2 Results

We ran the experiments for the following number of manually annotated samples:
1, 2, 5, 10, 20, 50, 100, 200, 500, and 1000. Table 1 provides the result
averaging all experiments (here and further, $n=500$ for a fair comparison;
see Section 5 for analyze of $n$ value). Experimental setup details are
provided in Appendix E. Our method ACTC outperforms the baselines in every
tried setting as well as on average. Figure 2a also demonstrates the general
improvement of $ACTC_{rndm}$ over the baselines for every tried amount of
manually annotated samples on the example of CoDEx-s dataset; the exact
numbers of experiments with different budgets are provided in Appendix F. On
the other hand, the density-based selection allows obtaining considerably
better results when a few manually annotated samples are available (see Figure
2b). Indeed, choosing representative samples from the highly connected
clusters can be especially useful in the case of lacking annotation. In
contrast, the setting with enough available manual annotations can profit more
from an unbiased random selection.

##  5 Ablation Study

More ablation study of different ACTC settings can be found provided in
Appendix D.

Figure 3: The universal threshold calibration methods compared to the per-
relation methods.

#### Global Thresholds.

All methods described above calibrate the per-relation thresholds. Another
option is to define a uniform (uni) threshold, which would work as a generic
threshold for all tuples regardless the relations involved. We implemented it
as $ACTC-LR_{uni}$ method, where the additional samples are automatically
labeled and used to build a decision dataset together with the manually
annotated ones - in the same way as done for the relation-specific version,
but only once for the whole dataset (thus, significantly reducing the
computational costs). We also applied the LocalOpt(Acc) and LocalOpt(F1)
baselines in the uniform setting. Figure 3 demonstrates the results obtained
with the Conve KGE model and random selection mechanism on the CodEX-s
dataset. Although the universal versions generally perform worse than the
relation-specific, $ACTC_{uni}$ still outperforms the universal baselines and
even relation-specific ones for a small annotation budget.

#### Different n values.

An important parameter in ACLC is n, the minimal sufficient amount of
(manually or automatically) labeled samples needed to calibrate the threshold.
The ablation study of different n values is provided in Figure 4 on the
example of $ACTC-LR_{dens}$ setting, averaged across all annotation budgets.
ACTC performs as a quite stable method towards the n values. Even a
configuration with a minimum value of $n=5$ outperforms baselines with a small
annotation budget or even with quite large one (e.g. for RESCAL; see Figure
2).

Figure 4: Ablation study for different n values.

##  6 Conclusion

In this work, we explored for the first time the problem of cold-start
calibration of scoring models for knowledge graph completion. Our new method
for active threshold calibration ACTC provides different strategies of
selecting the samples for manual annotation and automatically labels
additional tuples with Logistic Regression and Gaussian Processes classifiers
trained on the manually annotated data. Experiments on datasets with oracle
positive and negative triple annotations, and several KGE models, demonstrate
the efficiency of our method and considerable increase in the classification
performance even for tiny annotation budgets.

##  7 Limitations

A potential limitation of our experiments is the use of oracle validation
labels instead of human manual annotation as in the real-world setting.
However, all validation sets we used in our experiments were collected based
on the manually defined seed set of entities and relations, carefully cleaned
and augmented with manually labeled negative samples. Moreover, we chose this
more easy-to-implement setting to make our results easily reproducible and
comparable with future work.

Another limitation of experiments that use established data sets and focus on
isolated aspects of knowledge-graph construction is their detachment from the
real-world scenarios. Indeed, in reality knowledge graph completion is done in
a much more complicated environment, that involves a variety of stakeholders
and aspects, such as data verification, requirements consideration, user
management and so on. Nevertheless, we do believe that our method, even if
studied initially in isolation, still can be used as one component for the
real world knowledge graph construction.

##  8 Ethics Statement

Generally, the knowledge graphs used in the experiments are biased towards the
North American cultural background, and so are evaluations and predictions
made on them. As a consequence, the testing that we conducted in our
experiments might not reflect the completion performance for other cultural
backgrounds. Due to the high costs of additional oracle annotation, we could
not conduct our analysis on more diverse knowledge graphs. However, we have
used the most established and benchmark dataset with calibration annotations,
CoDEx, which has been collected with significant human supervision. That gives
us hope that our results will be as reliable and trustworthy as possible.

While our method can lead to better and more helpful predictions from
knowledge graphs, we cannot guarantee that these predictions are perfect and
can be trusted as the sole basis for decision-making, especially in life-
critical applications (e.g. healthcare).

## References

  * Agarwal et al. (2020) Sharat Agarwal, Himanshu Arora, Saket Anand, and Chetan Arora. 2020.  Contextual diversity for active learning.  In _Computer Vision – ECCV 2020_ , pages 137–153, Cham. Springer International Publishing.
  * Auer et al. (2007) Sören Auer, Christian Bizer, Georgi Kobilarov, Jens Lehmann, Richard Cyganiak, and Zachary Ives. 2007.  Dbpedia: A nucleus for a web of open data.  In _The Semantic Web_ , pages 722–735, Berlin, Heidelberg. Springer Berlin Heidelberg.
  * 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.
  * Dettmers et al. (2017) Tim Dettmers, Pasquale Minervini, Pontus Stenetorp, and Sebastian Riedel. 2017.  Convolutional 2d knowledge graph embeddings.  _CoRR_ , abs/1707.01476.
  * Ellis et al. (2018) Joe Ellis, Jeremy Getman, and Stephanie Strassel. 2018.  TAC KBP English Entity Linking - Comprehensive Training and Evaluation Data 2009-2013.
  * Minasny and McBratney (2005) Budiman Minasny and Alex. B. McBratney. 2005.  The matérn function as a general model for soil variograms.  _Geoderma_ , 128(3):192–207.  Pedometrics 2003.
  * 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.
  * Ostapuk et al. (2019) Natalia Ostapuk, Jie Yang, and Philippe Cudre-Mauroux. 2019.  Activelink: Deep active learning for link prediction in knowledge graphs.  In _The World Wide Web Conference_ , WWW ’19, page 1398–1408, New York, NY, USA. Association for Computing Machinery.
  * Pedregosa et al. (2011) Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, et al. 2011.  Scikit-learn: Machine learning in python.  _Journal of machine learning research_ , 12(Oct):2825–2830.
  * Safavi and Koutra (2020) Tara Safavi and Danai Koutra. 2020.  CoDEx: A Comprehensive Knowledge Graph Completion Benchmark.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 8328–8350, Online. Association for Computational Linguistics.
  * Speranskaya et al. (2020) Marina Speranskaya, Martin Schmitt, and Benjamin Roth. 2020.  Ranking vs. classifying: Measuring knowledge base completion quality.  In _Conference on Automated Knowledge Base Construction, AKBC 2020, Virtual, June 22-24, 2020_.
  * 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, 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.
  * Zhu et al. (2008) Jingbo Zhu, Huizhen Wang, Tianshun Yao, and Benjamin K Tsou. 2008.  Active learning with sampling by uncertainty and density for word sense disambiguation and text classification.  In _Proceedings of the 22nd International Conference on Computational Linguistics (Coling 2008)_ , pages 1137–1144, Manchester, UK. Coling 2008 Organizing Committee.

| CoDEx-s | CoDEx-m | Avg
---|---|---|---
| ComplEx | ConvE | TransE | RESCAL | ComplEx | ConvE | TransE | RESCAL |  |
| Acc | F1 | Acc | F1 | Acc | F1 | Acc | F1 | Acc | F1 | Acc | F1 | Acc | F1 | Acc | F1 | Acc | F1
LocalOpt (Acc) | 70 | 70 | 72 | 72 | 69 | 68 | 74 | 73 | 72 | 70 | 68 | 66 | 65 | 64 | 68 | 67 | 70 | 69
Safavi and Koutra (2020) | $\pm 3$ | $\pm 3$ | $\pm 3$ | $\pm 2$ | $\pm 3$ | $\pm 3$ | $\pm 2$ | $\pm 2$ | $\pm 2$ | $\pm 2$ | $\pm 3$ | $\pm 2$ | $\pm 3$ | $\pm 3$ | $\pm 3$ | $\pm 2$ |  |
LocalOpt (F1) | 67 | 69 | 69 | 70 | 65 | 67 | 70 | 71 | 70 | 69 | 66 | 66 | 63 | 64 | 66 | 67 | 67 | 68
$\pm 3$ | $\pm 3$ | $\pm 3$ | $\pm 2$ | $\pm 3$ | $\pm 3$ | $\pm 2$ | $\pm 2$ | $\pm 2$ | $\pm 2$ | $\pm 2$ | $\pm 2$ | $\pm 3$ | $\pm 3$ | $\pm 3$ | $\pm 2$ |  |
GlobalOpt (F1) | 70 | 74 | 74 | 77 | 68 | 71 | 76 | 79 | 73 | 75 | 68 | 70 | 65 | 68 | 68 | 71 | 70 | 73
Speranskaya et al. (2020) | $\pm 2$ | $\pm 2$ | $\pm 1$ | $\pm 2$ | $\pm 2$ | $\pm 2$ | $\pm 1$ | $\pm 1$ | $\pm 1$ | $\pm 2$ | $\pm 1$ | $\pm 2$ | $\pm 2$ | $\pm 2$ | $\pm 1$ | $\pm 2$ |  |
$ACTC-LR_{dens}$ | 72 | 72 | 77 | 78 | 69 | 71 | 80 | 81 | 78 | 77 | 72 | 71 | 64 | 65 | 72 | 70 | 73 | 73
$\pm 3$ | $\pm 2$ | $\pm 1$ | $\pm 1$ | $\pm 2$ | $\pm 0$ | $\pm 1$ | $\pm 1$ | $\pm 0$ | $\pm 1$ | $\pm 1$ | $\pm 1$ | $\pm 1$ | $\pm 1$ | $\pm 1$ | $\pm 1$ |  |
$ACTC-GP_{dens}$ | 72 | 72 | 76 | 78 | 69 | 71 | 80 | 80 | 78 | 77 | 72 | 70 | 64 | 65 | 73 | 71 | 73 | 73
$\pm 3$ | $\pm 2$ | $\pm 1$ | $\pm 1$ | $\pm 1$ | $\pm 2$ | $\pm 1$ | $\pm 1$ | $\pm 0$ | $\pm 0$ | $\pm 1$ | $\pm 1$ | $\pm 2$ | $\pm 2$ | $\pm 2$ | $\pm 1$ |  |
$ACTC-LR_{rndm}$ | 74 | 74 | 77 | 77 | 73 | 72 | 79 | 79 | 78 | 78 | 72 | 72 | 69 | 69 | 73 | 73 | 74 | 74
$\pm 3$ | $\pm 2$ | $\pm 2$ | $\pm 2$ | $\pm 3$ | $\pm 3$ | $\pm 1$ | $\pm 1$ | $\pm 1$ | $\pm 1$ | $\pm 2$ | $\pm 2$ | $\pm 3$ | $\pm 2$ | $\pm 2$ | $\pm 2$ |  |
$ACTC-GP_{rndm}$ | 74 | 74 | 77 | 77 | 73 | 72 | 81 | 81 | 77 | 77 | 71 | 71 | 67 | 66 | 72 | 71 | 74 | 74
$\pm 3$ | $\pm 2$ | $\pm 2$ | $\pm 2$ | $\pm 3$ | $\pm 3$ | $\pm 1$ | $\pm 1$ | $\pm 1$ | $\pm 1$ | $\pm 2$ | $\pm 2$ | $\pm 3$ | $\pm 3$ | $\pm 2$ | $\pm 2$ |  |
$ACTC-LR_{dens}(F1)$ | 72 | 72 | 73 | 75 | 63 | 66 | 78 | 79 | 78 | 77 | 72 | 72 | 64 | 66 | 72 | 71 | 72 | 73
$\pm 3$ | $\pm 2$ | $\pm 0$ | $\pm 0$ | $\pm 0$ | $\pm 1$ | $\pm 0$ | $\pm 1$ | $\pm 1$ | $\pm 1$ | $\pm 1$ | $\pm 2$ | $\pm 2$ | $\pm 1$ | $\pm 3$ | $\pm 2$ |  |
$ACTC-GP_{dens}(F1)$ | 72 | 73 | 76 | 78 | 68 | 70 | 79 | 80 | 78 | 77 | 71 | 71 | 64 | 66 | 71 | 73 | 72 | 74
$\pm 2$ | $\pm 1$ | $\pm 1$ | $\pm 1$ | $\pm 1$ | $\pm 2$ | $\pm 1$ | $\pm 1$ | $\pm 1$ | $\pm 2$ | $\pm 2$ | $\pm 1$ | $\pm 1$ | $\pm 1$ | $\pm 1$ | $\pm 3$ |  |
$ACTC-LR_{rndm}(F1)$ | 73 | 74 | 77 | 78 | 72 | 74 | 79 | 80 | 76 | 75 | 69 | 70 | 66 | 67 | 70 | 70 | 73 | 74
$\pm 3$ | $\pm 2$ | $\pm 2$ | $\pm 1$ | $\pm 3$ | $\pm 2$ | $\pm 1$ | $\pm 1$ | $\pm 2$ | $\pm 1$ | $\pm 2$ | $\pm 2$ | $\pm 3$ | $\pm 2$ | $\pm 2$ | $\pm 2$ |  |
$ACTC-GP_{rndm}(F1)$ | 74 | 74 | 77 | 77 | 72 | 73 | 79 | 79 | 77 | 77 | 70 | 71 | 67 | 68 | 71 | 72 | 73 | 74
$\pm 1$ | $\pm 2$ | $\pm 2$ | $\pm 2$ | $\pm 3$ | $\pm 2$ | $\pm 1$ | $\pm 1$ | $\pm 3$ | $\pm 2$ | $\pm 1$ | $\pm 2$ | $\pm 1$ | $\pm 3$ | $\pm 1$ | $\pm 1$ |  |
Table 3: ACTC results in % averaged across different size of annotation budget
reported with the standard error of the mean. The ACTC method is provided in
two local optimization setting: first, the thresholds maximize accuracy (in
the same way as it was presented in Figure 1), second, the thresholds are
maximized towards F1 score. The experiment with each annotation budget was
repeated 100 times.

##  Appendix A ACTC Pseudocodes

Algorithm 1 $ACTC_{rndm}$ algorithm

Input: unlabeled dataset $\mathcal{X}$, annotation budget size $l$, minimal
decision set size $n$, KGE model $M$, classifier
$\mathcal{C}:\mathbb{R}\to[0,1]$
Output: set of per-relation thresholds $T$

1:# Step 1: samples selection for human annotation

2:$T\leftarrow$ a set of per-relational thresholds

3:$\mathcal{X}_{gold}\leftarrow$ randomly selected $l$ samples from
$\mathcal{X}$

4:manually annotate $\mathcal{X}_{gold}$ with $y_{gold}$ labels

5:for relation $r$ do

6: $\mathcal{X}_{{gold}_{r}}\leftarrow$ samples from $\mathcal{X}_{gold}$ with
relation $r$

7: $y_{{gold}_{r}}\leftarrow$ manual labels for $\mathcal{X}_{{gold}_{r}}$

8: $scores_{{gold}_{r}}\leftarrow$ KGE model scores for
$\mathcal{X}_{{gold}_{r}}$

9: $l_{r}\leftarrow|\mathcal{X}_{{gold}_{r}}|$

10:

11:# Step 2: automatically label additional samples

12: if $n>l_{r}$ then

13: Train a classifier $\mathcal{C}_{r}$ on $scores_{{gold}_{r}}$ and
$y_{{gold}_{r}}$

14: $\mathcal{X}_{{auto}_{r}}\leftarrow$ rand. selected $n-l_{r}$ samples from
$\mathcal{X}$

15: $scores_{{auto}_{r}}\leftarrow$ KGE model scores for
$\mathcal{X}_{{auto}_{r}}$

16: Predict $y_{{auto}_{r}}=\mathcal{C}_{r}(scores_{{auto}_{r}})$

17:
$\mathcal{X}_{dec}=(\mathcal{X}_{{gold}_{r}},y_{{gold}_{r}})\bigcup(\mathcal{X}_{{auto}_{r}},y_{{auto}_{r}})$

18: else

19: $\mathcal{X}_{dec}=(\mathcal{X}_{{gold}_{r}},y_{{gold}_{r}}$)

20:

21:# Step 3: estimate per-relation threshold $\tau_{r}$

22: $\tau\leftarrow 0,best\\_acc\leftarrow 0$

23: for $score$ in $scores_{{gold}_{r}}$ do

24: $\tau_{i}\leftarrow score$

25: $accuracy_{i}\leftarrow acc(scores_{{gold}_{r}},y_{{gold}_{r}}|\tau_{i})$

26: if $accuracy_{i}>best\\_acc$ then

27: $\tau\leftarrow\tau_{i}$

28: $best\\_acc\leftarrow accuracy_{i}$

29: $T.append(\tau)$

Algorithm 2 $ACTC_{dens}$ algorithm

Input: unlabeled dataset $\mathcal{X}$, annotation budget size $l$, minimal
decision set size $n$, KGE model $M$, classifier
$\mathcal{C}:\mathbb{R}\to[0,1]$
Output: set of per-relation thresholds $T$

1:# Step 1: samples selection for human annotation

2:$T\leftarrow$ a set of per-relational thresholds

3:for $i=0,1,...,|\mathcal{X}|$ do

4: $density_{x_{i}}=\sum_{j=0}^{|\mathcal{X}|}(score_{j}-score_{i})^{2}$

5:$\mathcal{X}_{gold}\leftarrow$ top $l$ samples with maximal
$density_{x_{i}}$

6:manually annotate $\mathcal{X}_{gold}$ with $y_{gold}$ labels

7:[the rest is the same as in $ACTC_{rndm}$]

8:# Step 2: automatically label additional samples

9:[same as Step 2 in $ACTC_{rndm}$]

10:# Step 3: estimate per-relation threshold $\tau_{r}$

11:[same as Step 3 in $ACTC_{rndm}$]

##  Appendix B CoDEx datasets

In our experiments, we use benchmark CoDEx datasets Safavi and Koutra (2020).
The dataset were collected based on the Wikidata in the following way: a seed
set of entities and relations for 13 domains (medicine, science, sport etc)
was defined and used as queries to Wikidata in order to retrieve the entities,
relations, and triples. After additional postprocessing (e.g. removal of
inverse relations), the retrieved data was used to construct 3 datasets:
CoDEx-S, CoDEx-M, and CoDEx-L. For the first two datasets the authors
additionally constructed hard negative samples (by annotating manually the
candidate triples which were generated using a pre-trained embedding model),
what allows us to use them in our experiments.

  * •

An example of positive triple: (Senegal, part of, West Africa).

  * •

An example of negative triple: (Senegal, part of, Middle East).

##  Appendix C Embedding models

We use four knowledge graph embedding models. This section highlights their
main properties and provides their scoring functions.

#### ComplEX

Trouillon et al. (2016) uses complex-numbered embeddings and diagonal relation
embedding matrix to score triples; the scoring function is defined as
$s(h,r,t)=\mathbf{e}_{\mathbf{h}}^{T}\operatorname{diag}\left(\mathbf{r}_{\mathbf{r}}\right)\mathbf{e}_{\mathbf{t}}$.

#### ConvE

Dettmers et al. (2017) represents a neural approach to KGE scoring and
exploits the non-linearities:
$s(h,r,t)=f(\operatorname{vec}(f([\mathbf{e_{h}};\overline{\mathbf{r}}]*\omega)(\mathbf{W})\mathbf{t}$.

#### TransE

Bordes et al. (2013) is an example of translation KGE models, where the
relations are tackled as translations between entities; the embeddings are
scored with
$s(h,r,t)=-\left\|\mathbf{e}_{\mathbf{h}}+\mathbf{r}_{\mathbf{r}}-\mathbf{e}_{\mathbf{t}}\right\|_{p}$.

#### RESCAL

Nickel et al. (2011) treats the entities as vectors and relation types as
matrices and scores entities and relation embeddings with the following
scoring function:
$s(h,r,t)=\mathbf{e}_{\mathbf{h}}^{T}\mathbf{R}_{\mathbf{r}}\mathbf{e}_{\mathbf{t}}$.

These models were selected, first, following the previous works Safavi and
Koutra (2020); Speranskaya et al. (2020), and, second, to demonstrate the
performance of our method using the different KGE approaches: linear (ComplEX
and RESCAL), translational (TransE), and neural (ConvE).

##  Appendix D Ablation Study

#### Optimization towards F1 score.

Just as we converted the LocalOpt (Acc) baseline from Safavi and Koutra (2020)
to a LocalOpt(F1) setting, we also converted ACTC into ACTC(F1). The only
difference is the metric, which the thresholds maximize: instead of accuracy,
the threshold that provide the best F1 score are looked for. Table 3 is an
extended result table, which provides the ACTC(F1) numbers together with the
standard ACTC (optimizing towards accuracy) and baselines. As can be seen,
there is no dramatic change in ACTC performance; naturally enough, the F1 test
score for ACTC(F1) experiments is slightly better than the F1 test score for
experiments where thresholds were selected based on accuracy value.

| CoDEx-s | CoDEx-m
---|---|---
| ComplEx | ConvE | TransE | RESCAL | ComplEx | ConvE | TransE | RESCAL
| Acc | F1 | Acc | F1 | Acc | F1 | Acc | F1 | Acc | F1 | Acc | F1 | Acc | F1 | Acc | F1
LocalOpt (Acc)1 | 0.60 | 0.58 | 0.65 | 0.65 | 0.60 | 0.57 | 0.68 | 0.66 | 0.66 | 0.63 | 0.61 | 0.59 | 0.55 | 0.50 | 0.62 | 0.58
Safavi and Koutra (2020) | (0.5) | (1.7) | (0.7) | (1.5) | (0.5) | (1.5) | (0.9) | (1.9) | (0.8) | (1.8) | (0.6) | (1.4) | (0.3) | (1.8) | (0.6) | (1.6)
LocalOpt (F1)1 | 0.60 | 0.58 | 0.65 | 0.65 | 0.60 | 0.57 | 0.68 | 0.66 | 0.66 | 0.63 | 0.61 | 0.59 | 0.55 | 0.50 | 0.62 | 0.58
(0.5) | (1.7) | (0.7) | (1.5) | (0.5) | (1.5) | (0.9) | (1.9) | (0.8) | (1.8) | (0.6) | (1.4) | (0.3) | (1.8) | (0.6) | (1.6)
GlobalOpt (F1)1 | 0.61 | 0.67 | 0.67 | 0.72 | 0.57 | 0.65 | 0.70 | 0.75 | 0.65 | 0.72 | 0.60 | 0.66 | 0.55 | 0.62 | 0.61 | 0.67
Speranskaya et al. (2020) | (0.3) | (1.0) | (0.3) | (0.4) | (0.4) | (0.6) | (0.4) | (0.3) | (0.6) | (0.3) | (0.4) | (0.1) | (0.2) | (1.0) | (0.3) | (0.4)
$ACTC-LR_{dens}^{1}$ | 0.67 | 0.68 | 0.76 | 0.77 | 0.65 | 0.66 | 0.78 | 0.79 | 0.71 | 0.75 | 0.69 | 0.66 | 0.57 | 0.65 | 0.68 | 0.62
(0.0) | (0.0) | (0.0) | (0.0) | (0.0) | (0.0) | (0.0) | (0.0) | (0.0) | (0.0) | (0.0) | (0.0) | (0.0) | (0.0) | (0.0) | (0.0)
$ACTC-GP_{dens}^{1}$ | 0.59 | 0.47 | 0.72 | 0.76 | 0.61 | 0.59 | 0.50 | 0.67 | 0.76 | 0.76 | 0.71 | 0.70 | 0.58 | 0.66 | 0.68 | 0.62
(0.0) | (0.0) | (0.0) | (0.0) | (0.5) | (1.4) | (0.0) | (0.0) | (0.0) | (0.0) | (0.0) | (0.0) | (0.0) | (0.0) | (0.0) | (0.0)
$ACTC-LR_{rndm}^{1}$ | 0.63 | 0.60 | 0.70 | 0.69 | 0.61 | 0.58 | 0.76 | 0.75 | 0.69 | 0.67 | 0.63 | 0.62 | 0.57 | 0.52 | 0.63 | 0.60
(0.4) | (1.4) | (0.5) | (0.9) | (0.5) | (1.5) | (0.5) | (1.3) | (0.0) | (1.6) | (0.0) | (1.1) | (0.0) | (1.9) | (0.0) | (1.5)
$ACTC-GP_{rndm}^{1}$ | 0.63 | 0.61 | 0.71 | 0.70 | 0.61 | 0.59 | 0.76 | 0.76 | 0.74 | 0.73 | 0.64 | 0.65 | 0.56 | 0.64 | 0.65 | 0.64
(0.5) | (0.8) | (0.4) | (0.8) | (0.5) | (1.4) | (0.5) | (1.4) | (0.01) | (0.01) | (0.01) | (0.01) | (0.0) | (0.02) | (0.0) | (0.01)
Table 4: ACTC results for $l=1$, $n=500$, averaged across 100 tries for each
experiment and reported with the standard error of the mean

#### Estimate All Samples

Apart from automatic labeling of additional samples discussed in Section 3
(i.e. the additional samples are labeled in case of insufficient manual
annotations, so that the size of the decision set build from manually
annotated and automatically labeled samples equals $n$), we also experimented
with annotating all samples. All samples that were not manually labeled are
automatically labeled with a classifier. However, the performance was slightly
better only for the middle budgets (i.e., for the settings with 5, 10, 20
manually annotated samples) and became considerably worse for large budgets
(i.e., 100, 200, etc), especially in the denstity_selection setting. Based on
that, we can conclude that a lot of (automatically) labeled additional data is
not what the model profits the most; the redundant labels (which are also not
gold and potentially contain mistakes) only amplify the errors and lead to
worse algorithm performance.

#### Hard VS Soft Labels.

The classifier’s predictions can be either directly used as real-valued soft
labels or transformed to the hard ones by selecting the class with the maximum
probability. In most of our experiments, the performance of soft and hard
labels was practically indistinguishable (yet with a slight advantage of the
latter). All the results provided in this paper were obtained with hard
automatic labels.

##  Appendix E Experimental Setting

As no validation data is available in our setting, the ACTC method does not
require any hyperparameter tuning. We did not use a GPU for our experiments;
one ACTC run takes, on average, 2 minutes. All results are reproducible with a
seed value $12345$.

ACTC does not imply any restrictions on the classifier architecture. We
experimented with two classifiers: Logistic Regression classifier and Gaussian
Processes classifier. For both of them, we used a Scikit-learn implementation
Pedregosa et al. (2011). The Logistic Regression classifier was used in the
default Scikit-learn setting, with L2 penalty term and inverse of
regularization strength equals 100. In the Gaussian Processes classifier, we
experimented with the following kernels:

  * •

squared exponential RBF kernel with $length\\_scale=10$

  * •

its generalized and smoothed version, Matérn kernel, with $length\\_scale=0.1$

  * •

a mixture of different RBF kernels, RationalQuadratic kernel, with
$length\\_scale=0.1$

All the results for Gaussian Processes classifier provided in this paper are
obtained with the Matérn kernel Minasny and McBratney (2005) using the
following kernel function:

$k\left(x_{i},x_{j}\right)=\frac{1}{\Gamma(\nu)2^{\nu-1}}\left(\frac{\sqrt{2\nu}}{l}d\left(x_{i},x_{j}\right)\right)^{\nu}*\\\
*K_{\nu}\left(\frac{\sqrt{2\nu}}{l}d\left(x_{i},x_{j}\right)\right)$ (1)

where $K_{\nu}$ is a Bessel function and $\Gamma$ is a Gamma function.

##  Appendix F Results for Different Annotation Budgets

Tables 4, 5, and 6 demonstrate the performance of the different ACTC settings
for different annotation budgets (1, 10, and 50, respectively). The results
are averaged over all settings, each setting was repeated 100 times. Table 4
demonstrates how useful and profitable the density-selection methods are in a
lower budget setting. However, the non-biased random selection works better
when there are more manually annotated samples (e.g. 50).

| CoDEx-s | CoDEx-m
---|---|---
| ComplEx | ConvE | TransE | RESCAL | ComplEx | ConvE | TransE | RESCAL
| Acc | F1 | Acc | F1 | Acc | F1 | Acc | F1 | Acc | F1 | Acc | F1 | Acc | F1 | Acc | F1
LocalOpt (Acc)10 | 0.62 | 0.62 | 0.65 | 0.64 | 0.60 | 0.59 | 0.67 | 0.66 | 0.67 | 0.65 | 0.63 | 0.59 | 0.57 | 0.57 | 0.63 | 0.60
Safavi and Koutra (2020) | (0.6) | (0.8) | (0.6) | (0.8) | (0.7) | (0.9) | (0.6) | (1.0) | (0.6) | (0.9) | (0.6) | (0.9) | (0.5) | (1.0) | (0.6) | (1.1)
LocalOpt (F1)10 | 0.57 | 0.61 | 0.61 | 0.62 | 0.55 | 0.59 | 0.63 | 0.64 | 0.65 | 0.63 | 0.60 | 0.60 | 0.55 | 0.58 | 0.60 | 0.60
(0.7) | (0.7) | (0.7) | (0.8) | (0.7) | (0.8) | (0.7) | (0.9) | (0.6) | (0.9) | (0.6) | (0.8) | (0.6) | (0.9) | (0.6) | (0.9)
GlobalOpt (F1)10 | 0.66 | 0.71 | 0.71 | 0.74 | 0.65 | 0.67 | 0.73 | 0.76 | 0.7 | 0.73 | 0.65 | 0.68 | 0.61 | 0.66 | 0.64 | 0.68
Speranskaya et al. (2020) | (0.5) | (0.5) | (0.5) | (0.6) | (0.6) | (0.7) | (0.4) | (0.4) | (0.5) | (0.4) | (0.4) | (0.3) | (0.4) | (0.6) | (0.5) | (0.5)
$ACTC-LR_{dens}^{10}$ | 0.70 | 0.73 | 0.74 | 0.76 | 0.66 | 0.67 | 0.79 | 0.80 | 0.77 | 0.77 | 0.71 | 0.70 | 0.61 | 0.61 | 0.73 | 0.72
(0.0) | (0.0) | (0.0) | (0.0) | (0.0) | (0.0) | (0.0) | (0.0) | (0.0) | (0.0) | (0.0) | (0.0) | (0.0) | (0.0) | (0.0) | (0.0)
$ACTC-GP_{dens}^{10}$ | 0.64 | 0.71 | 0.73 | 0.76 | 0.68 | 0.65 | 0.48 | 0.08 | 0.77 | 0.77 | 0.72 | 0.70 | 0.61 | 0.61 | 0.73 | 0.72
(0.0) | (0.0) | (0.0) | (0.0) | (0.6) | (1.1) | (0.0) | (0.0) | (0.0) | (0.0) | (0.0) | (0.0) | (0.0) | (0.0) | (0.0) | (0.0)
$ACTC-LR_{rndm}^{10}$ | 0.70 | 0.70 | 0.74 | 0.73 | 0.68 | 0.66 | 0.77 | 0.77 | 0.74 | 0.73 | 0.67 | 0.66 | 0.62 | 0.62 | 0.67 | 0.66
(0.5) | (0.8) | (0.3) | (0.7) | (0.5) | (1.0) | (0.4) | (0.8) | (0.0) | (0.6) | (0.0) | (0.7) | (0.0) | (1.0) | (0.0) | (0.9)
$ACTC-GP_{rndm}^{10}$ | 0.71 | 0.70 | 0.73 | 0.73 | 0.68 | 0.65 | 0.77 | 0.77 | 0.75 | 0.74 | 0.68 | 0.67 | 0.62 | 0.61 | 0.68 | 0.67
(0.3) | (0.9) | (0.4) | (0.7) | (0.6) | (1.1) | (0.5) | (0.9) | (0.4) | (1.0) | (0.5) | (0.8) | (0.7) | (0.9) | (0.6) | (0.7)
Table 5: ACTC results for $l=10$, $n=500$, averaged across 100 tries for each experiment and reported with the standard error of the mean | CoDEx-s | CoDEx-m
---|---|---
| ComplEx | ConvE | TransE | RESCAL | ComplEx | ConvE | TransE | RESCAL
| Acc | F1 | Acc | F1 | Acc | F1 | Acc | F1 | Acc | F1 | Acc | F1 | Acc | F1 | Acc | F1
LocalOpt (Acc)50 | 0.72 | 0.73 | 0.73 | 0.74 | 0.71 | 0.71 | 0.74 | 0.74 | 0.73 | 0.72 | 0.70 | 0.69 | 0.67 | 0.68 | 0.71 | 0.70
Safavi and Koutra (2020) | (0.3) | (0.4) | (0.3) | (0.4) | (0.3) | (0.4) | (0.3) | (0.4) | (0.3) | (0.3) | (0.3) | (0.4) | (0.3) | (0.4) | (0.3) | (0.4)
LocalOpt (F1)50 | 0.65 | 0.69 | 0.66 | 0.70 | 0.64 | 0.68 | 0.67 | 0.71 | 0.69 | 0.71 | 0.66 | 0.68 | 0.64 | 0.67 | 0.67 | 0.69
(0.7) | (0.5) | (0.7) | (0.5) | (0.7) | (0.5) | (0.7) | (0.5) | (0.4) | (0.3) | (0.5) | (0.4) | (0.5) | (0.4) | (0.4) | (0.4)
GlobalOpt (F1)50 | 0.73 | 0.76 | 0.75 | 0.78 | 0.71 | 0.73 | 0.77 | 0.79 | 0.74 | 0.76 | 0.70 | 0.72 | 0.67 | 0.71 | 0.69 | 0.72
Speranskaya et al. (2020) | (0.2) | (0.2) | (0.2) | (0.3) | (0.3) | (0.3) | (0.2) | (0.2) | (0.3) | (0.2) | (0.2) | (0.2) | (0.3) | (0.2) | (0.3) | (0.2)
$ACTC-LR_{dens}^{50}$ | 0.76 | 0.76 | 0.78 | 0.79 | 0.72 | 0.72 | 0.80 | 0.81 | 0.79 | 0.79 | 0.72 | 0.72 | 0.63 | 0.64 | 0.73 | 0.73
(0.0) | (0.0) | (0.0) | (0.0) | (0.0) | (0.0) | (0.0) | (0.0) | (0.0) | (0.0) | (0.0) | (0.0) | (0.0) | (0.0) | (0.0) | (0.0)
$ACTC-GP_{dens}^{50}$ | 0.75 | 0.78 | 0.78 | 0.80 | 0.77 | 0.78 | 0.77 | 0.78 | 0.79 | 0.78 | 0.72 | 0.72 | 0.64 | 0.64 | 0.74 | 0.74
(0.0) | (0.0) | (0.0) | (0.0) | (0.3) | (0.4) | (0.0) | (0.0) | (0.0) | (0.0) | (0.0) | (0.1) | (0.0) | (0.0) | (0.0) | (0.0)
$ACTC-LR_{rndm}^{10}$ | 0.76 | 0.78 | 0.79 | 0.79 | 0.76 | 0.77 | 0.80 | 0.80 | 0.78 | 0.78 | 0.71 | 0.71 | 0.69 | 0.70 | 0.73 | 0.73
(0.2) | (0.3) | (0.2) | (0.3) | (0.3) | (0.3) | (0.2) | (0.3) | (0.0) | (0.2) | (0.0) | (0.3) | (0.0) | (0.3) | (0.0) | (0.3)
$ACTC-GP_{rndm}^{10}$ | 0.75 | 0.78 | 0.79 | 0.80 | 0.77 | 0.78 | 0.80 | 0.80 | 0.78 | 0.78 | 0.72 | 0.71 | 0.69 | 0.70 | 0.73 | 0.74
(0.4) | (0.3) | (0.2) | (0.3) | (0.3) | (0.4) | (0.2) | (0.3) | (0.1) | (0.3) | (0.3) | (0.4) | (0.2) | (0.5) | (0.1) | (0.2)
Table 6: ACTC results for $l=50$, $n=500$, averaged across 100 tries for each
experiment and reported with the standard error of the mean


Dark Matter Freeze-out in a Matter Dominated Universe
BY

SALEH HAMDAN

B.S., North Carolina State University, 2009

M.S., University of Illinois at Chicago, Chicago, 2015

THESIS

Submitted as partial fulfillment of the requirements

for the degree of Doctor of Philosophy in Physics

in the Graduate College of the

University of Illinois at Chicago, 2018

Chicago, Illinois

Defense Committee:
Wai-Yee Keung, Chair
James Unwin, Advisor
Arthur Licht, Advisor
Richard Cavanaugh
Christopher Kolda, University of Notre Dame

## Dedication

I dedicate this work to my dear mother, brother, and remaining family, without
whose support this work would have been impossible.

## Acknowledgements

First and foremost I wish to sincerely thank my advisor James A. Unwin for his
guidance and help. I especially want to thank him for suggesting matter-
dominated freeze-out as a novel scenario worth researching, which is what grew
into this thesis. His guidance was vital throughout my research, writing,
publishing, as well as all the other processes that academics must undertake.

I would also wish to express gratitude to my advisor Arthur (Lew) Licht, who
guided me through advanced physics that was essential in completing this
thesis, and was helpful and patient with me as I explored research topics. I
wish to further express my gratitude toward other members of my thesis and
preliminary exam committee: Richard Cavanaugh, Wai-Yee Keung, Mikhail
Stephanov, and Christopher Kolda.

I am deeply thankful for the teachers I have had throughout my graduate
tenure. In particular, Arthur (Lew) Licht taught me Statistical Mechanics,
General Relativity, and String Theory; Tom Imbo taught me Quantum Field
Theory; Richard Cavanaugh taught me Particle Physics; Wai-Yee Keung taught me
Quantum Mechanics; and Mikhail Stephanov taught me Electromagnetism. No words
can express the amount of gratitude and respect I hold towards them for
passing on their wisdom and knowledge to me.

I would also like to thank the UIC Physics Department and the UIC Mathematics,
Statistics, and Computer Science Department for accommodating me as I took
classes in their departments and did research. Last, but certainly not least,
I thank Fermilab for accommodating me during my early research in particle
physics there.

## Statement of Originality

The ideas contained in chapters of this thesis have appeared in S. Hamdan, and
J. Unwin [Hamdan:2017psw], arXiv:1710.03758. Additionally, Chapters LABEL:Ch5
and LABEL:Ch6 are expected to appear in a separate forthcoming publication. In
all of the original work presented in this thesis I am responsible for the
major derivations and calculations, while J. Unwin provided direction,
guidance, and checks.

## Summary

Dark Matter Freeze-out in a Matter Dominated Universe
A thesis submitted for the degree of Doctor of Philosophy.
Saleh Hamdan
University of Illinois at Chicago

The universe has evolved through several phases as its various constituents
dominated its energy content. Candidate dark matter particles may have
undergone freeze-out during any such phase. While the standard freeze-out
scenarios have been explored during the radiation-dominated era, and more
recently during scalar field decay, this work extends the study of dark matter
freeze-out to a potential early period during which the universe is matter-
dominated and its evolution adiabatic. Decoupling during an adiabatic matter
dominated era changes the freeze-out dynamics, since the Hubble rate is
parametrically different for matter and radiation domination. Furthermore, for
successful Big Bang Nucleosynthesis the state dominating the early universe
energy density must decay, this dilutes (or repopulates) the dark matter. As a
result, the masses and couplings required to match the observed dark matter
relic density can differ significantly from radiation dominated freeze-out.

###### Contents

  1. Nomenclature

## Nomenclature

  * Abbreviations
  * BBN

Big Bang Nucleosynthesis

  * BE

Boltzmann Equation

  * DM

Dark matter

  * FLWR

Friedmann–Lemaitre–Robertson–Walker

  * LHC

Large Hadron Collider

  * MB

Maxwell-Boltzmann

  * MD

Matter domination

  * MDFO

Matter dominated freeze-out

  * RD

Radiation domination

  * RDFO

Radiation dominated freeze-out

  * SM

Standard Model

  * Symbols
  * $\alpha$

Used to parameterize thermally-averaged cross-section

  * $\beta$

Parameter used to define matter domination

  * $\Gamma_{\Phi}$

Decay width of decaying species

  * $\hat{\gamma}$

Ratio of relativistic degrees of freedom at $T_{\star}$ to $T_{\rm RH}$

  * $\mathcal{A}$

Ratio of $a_{\star}$ to scale factor

  * $\mathcal{T}$

Ratio of $t_{\star}$ to comoving time

  * $\mathcal{T}_{\rm EV}$

$\mathcal{T}$ when entropy violation becomes considerable

  * $\Omega h^{2}$

Fractional critical density with Hubble parameter uncertainty $h$

  * $\rho_{\star}$

Energy density at $T_{\star}$

  * $\zeta$

Dilution factor

  * $a_{\star}$

Scale factor at $T_{\star}$

  * $g_{*}$

Energy relativistic degrees of freedom

  * $g_{*S}$

Entropic relativistic degrees of freedom

  * $H_{\star}$

Hubble parameter at $T_{\star}$

  * $H_{\rm MD}$

Hubble parameter when matter domination ensues

  * $r$

Fraction of energy in radiation at $T_{\star}$

  * $s_{\rm RH}$

Entropy after dilution

  * $s_{\rm R}$

Entropy before dilution

  * $T_{\Gamma}$

Temperature when decay ensues

  * $T_{\star}$

Temperature of thermal bath when decaying species evovles as matter

  * $t_{\star}$

Comoving time at $T_{\star}$

  * $T_{F}$

Freeze-out temperature

  * $T_{\rm BBN}$

Minimum reheating temperature to fulfill BBN constraint

  * $T_{\rm EV}$

Temperature when entropy violation becomes considerable

  * $t_{\rm EV}$

Comoving time when entropy violation becomes considerable

  * $T_{\rm MD}$

Temperature when matter domination ensues

  * $T_{\rm RH}$

Reheat temperature

  * $w$

Parameter relating pressure and energy density

  * $x_{F}$

Dimensionless freeze-out parameter

  * $Y_{\infty}$

Freeze-out abundance