# SAFRAN: An interpretable, rule-based link prediction method outperforming
embedding models

Simon Ott<EMAIL_ADDRESS>
Institute of Artificial Intelligence and Decision Support, Medical University
of Vienna, Austria Christian Meilicke<EMAIL_ADDRESS>
Data and Web Science Research Group, University Mannheim, Germany Matthias
Samwald<EMAIL_ADDRESS>
Institute of Artificial Intelligence and Decision Support, Medical University
of Vienna, Austria

###### Abstract

Neural embedding-based machine learning models have shown promise for
predicting novel links in knowledge graphs. Unfortunately, their practical
utility is diminished by their lack of interpretability. Recently, the fully
interpretable, rule-based algorithm AnyBURL yielded highly competitive results
on many general-purpose link prediction benchmarks. However, current
approaches for aggregating predictions made by multiple rules are affected by
redundancies. We improve upon AnyBURL by introducing the SAFRAN rule
application framework, which uses a novel aggregation approach called Non-
redundant Noisy-OR that detects and clusters redundant rules prior to
aggregation. SAFRAN yields new state-of-the-art results for fully
interpretable link prediction on the established general-purpose benchmarks
FB15K-237, WN18RR and YAGO3-10. Furthermore, it exceeds the results of
multiple established embedding-based algorithms on FB15K-237 and WN18RR and
narrows the gap between rule-based and embedding-based algorithms on YAGO3-10.

##  1 Introduction

Link prediction in knowledge graphs is a vibrant area of research and
development and encompasses a wide range of different approaches. Currently,
most state-of-the-art approaches use low-dimensional representations
(embeddings) of knowledge graphs to predict new knowledge. However, as such
approaches are black boxes, the validity of their predictions can be
questioned due to lack of interpretability. Recent research has focused on
learning symbolic rules from knowledge graphs that try to detect correlations
of entities in knowledge bases and express them as first-order Horn rules. In
contrast to neural models, such rule-based methods are fully transparent and
predictions can be explained intuitively.

However, while current research on rule-based approaches puts a lot of
emphasis on designing rule-mining algorithms, research on methods for applying
learned rules and aggregating their predictions in a meaningful way is
comparatively neglected.

AnyBURL Meilicke et al. (2019, 2020) is currently one of the best performing
symbolic rule learners and demonstrated results competitive with embedding
methods on link prediction benchmarks such as FB15k-237. However, the
application of rules generated by AnyBURL is currently limited by functional
redundancies, making it difficult to meaningfully aggregate predictions made
by different rules and thereby limiting predictive performance.

In this paper, we introduce the high-performance rule application framework
SAFRAN111Code can be found at https://github.com/OpenBioLink/SAFRAN (’Scalable
And fast non-redundant rule application’) that employs a novel aggregation
approach. We propose an algorithm called Non-redundant Noisy-OR that detects
redundant rules prior to aggregation, mitigating their negative effects and
improving predictive performance. This algorithm for aggregating predictions
is not necessarily restricted to rules learned by AnyBURL and could also be
applied to other rule-based systems.

##  2 Preliminaries

###  2.1 Link prediction

Knowledge graphs contain facts, such as “Amsterdam is the capital of the
Netherlands” or “Marie Curie was born in Warsaw”, which are represented as
semantic triples containing a subject (head $h$), predicate (relation $r$) and
object (tail $t$). Formally, a knowledge graph is a directed heterogeneous
multigraph $G=(E,R,T)$ where E and R are the set of entities and relations
respectively and T is a set of triples $\\{(h,r,t)\\}\subseteq E\times R\times
E$. The task of link prediction is to predict either the tail of a given head
and relation $(h,r,?)$ or the head of a given tail and relation $(?,r,t)$ such
that the resulting triple describes a correct fact which has not been in $G$
before.

###  2.2 AnyBURL

We now give an overview about the main AnyBURL algorithm, which is explained
in detail in Meilicke et al. (2019) and Meilicke et al. (2020). AnyBURL
(Anytime Bottom Up Rule Learning) is a novel walk-based method and is
currently one of the best symbolic rule learners, competing with current
state-of-the-art embedding approaches Rossi et al. (2021). Walk-based (bottom-
up) methods are based on the idea that sampled paths from a knowledge graph
(random walks) are examples of very specific rules, which can be transformed
into more general rules. Learned rules can then be applied to the knowledge
graph for the prediction of novel links between entities.

Cyclic (C) | $h(Y,X)$ | ${}\leftarrow b_{1}(X,A_{2}),\dots,b_{n}(A_{n},Y)$
---|---|---
Acyclic 1 (AC1) | $h(c_{0},X)$ | ${}\leftarrow b_{1}(X,A_{2}),\dots,b_{n}(A_{n},c_{n+1})$
Acyclic 2 (AC2) | $h(c_{0},X)$ | ${}\leftarrow b_{1}(X,A_{2}),\dots,b_{n}(A_{n},A_{n+1})$
Table 1: Different types of rules that can be learned by AnyBURL. Uppercase
letters represent variables and lowercase letters represent constants.
$h(\dots)$ is called the head, while $b_{1}(\dots),\dots,b_{n}(\dots)$ is
called the body of a rule. Note that variables or constants of a body atom can
be flipped.

AnyBURL learns rules in the form of first-order logic Horn rules of length
$n$. In each iteration of the algorithm for mining rules the algorithm samples
a random triple $h(c_{0},c_{1})$, f.e. $lives(max,uk)$ from the training set.
Starting from either the head or the tail of this triple, AnyBURL performs a
random walk of length $n$, resulting in a ground path in the form of
$h(c_{0},c_{1})\leftarrow b_{1}(c_{1},c_{2}),\dots,b_{n}(c_{n},c_{n+1})$, f.e.
$speaks(max,english)\leftarrow lives(max,uk),lang(uk,english)$. The sampled
ground path is subsequently generalized into three predefined types of rules
shown in Table 1. Cyclic rules can be generalized from cyclic paths
($c_{0}=c_{n+1}$), while AC2 rules can be generalized from acyclic paths
($c_{0}\neq c_{n+1}$). AC1 rules are hybrid, as they can be both generalized
from cyclic (if $c_{0}=c_{n+1}$) and acyclic (if $c_{0}\neq c_{n+1})$ paths.
All rules that can be generalized from the previous example ground path can be
seen in Table 2.

$speaks(Y,X)$ | ${}\leftarrow lives(X,A),lang(A,Y)$
---|---
$speaks(english,X)$ | ${}\leftarrow lives(X,A),lang(A,english)$
$speaks(Y,max)$ | ${}\leftarrow lives(max,A),lang(A,Y)$
Table 2: Rules that can be generalized from the ground path
$speaks(max,english)\leftarrow lives(max,uk),lang(uk,english)$

The following applies for inferring a set of head triples $\hat{H}_{r}$ from
the body of a rule $r$:

$\hat{H}_{r}=\begin{cases}\\{h(e_{y},e_{x})|e_{x},e_{y}\in E\land\exists
e_{2},...,e_{n}\ b_{1}(e_{x},e_{2}),\dots,b_{n}(e_{n},e_{y})\in T\\},&\text{if
type}=\text{C}\\\ \\{h(c_{0},e_{x})|e_{x}\in E\land\exists e_{2},...,e_{n}\
b_{1}(e_{x},e_{2}),\dots,b_{n}(e_{n},c_{n+1})\in T\\},&\text{if
type}=\text{AC1}\\\ \\{h(c_{0},e_{x})|e_{x}\in E\land\exists
e_{2},...,e_{n+1}\ b_{1}(e_{x},e_{2}),\dots,b_{n}(e_{n},e_{n+1})\in
T\\},&\text{if type}=\text{AC2}\\\ \end{cases}$

AnyBURL calculates the confidence of a rule as the size of the union of
inferred triples by a rule and the triples of the training set divided by the
number of inferred triples $conf(r)=|\hat{H}_{r}\cap T|/|\hat{H}_{r}|$, where
$T$ is the set of triples contained in the training set.

###  2.3 Aggregation

Rule-based link prediction methods, such as AnyBURL, produce many rules with
different confidences that are subsequently applied to the knowledge graph in
order to generate candidates for a link prediction task. Upon a link
prediction task $p(s,?)$, rule $r$ generates the set of predictions
$\\{y|p(s,y)\in\hat{H}_{r}\\}$ that could act as substitutions for the
question mark. Rules can either predict zero, one or multiple entities. As the
same entities can be proposed by multiple rules which may differ in
confidence, an aggregation of these confidences is required to assess the
final confidence of a prediction. Table 3 shows the confidences and results of
five fictional rules.

Rule | Results | Confidence
---|---|---
$R_{0}$ | $\\{a,b\\}$ | 0.9
$R_{1}$ | $\\{c\\}$ | 0.8
$R_{2}$ | $\\{c\\}$ | 0.7
$R_{3}$ | $\\{b\\}$ | 0.3
$R_{5}$ | $\\{a\\}$ | 0.1
$R_{5}$ | $\emptyset$ | 0.1
Table 3: Example of different rules generating either zero, one or multiple
predictions.

One aggregation approach called Maximum aggregation is using the maximum of
these confidences Meilicke et al. (2019). The score of an entity

$score(e)=\ max\\{conf(r_{1}),\dots,\text{conf}(r_{k})\\}$

is the maximum confidence of all rules $r_{1},\dots,r_{k}$ that predict entity
$e$. If the maximum confidences of two or more entities are the same, these
entities are further ranked by their second best confidence and so on, until
all top-k candidates can be distinguished or all rules are processed. This
approach results in the following list of ranked candidates when applied to
the solutions of Table 3:
$ranking_{max}=\langle(b,0.9),(a,0.9),(c,0.8)\rangle$. As the second best rule
that proposes $b$ has a higher confidence than the second best rule which
proposes $a$, $b$ is ranked before $a$.

Unfortunately, the Maximum aggregation is constrained to relatively simple
predictions: Each prediction is primarily informed by only a single rule with
the highest confidence; it is not possible to make predictions based on a
weighted combination of different rules. These limitations of maximum
aggregation are potentially addressed by noisy-or aggregation, first proposed
in this context by Galárraga et al. (2015). Instead of taking the maximum of
confidences, the probability that at least one of the rules proposed the
correct candidate is used for generating a list of ranked candidates. The
score of an entity $e$ can thus be calculated as

$score(e)=1-\prod_{i=1}^{k}(1-conf(r_{i}))$

where $r_{1},\dots,r_{k}$ are rules that predict entity $e$. Applying the
Noisy-OR approach to the results of Table 3, the entities are ranked as
follows: $ranking_{noisy}=\langle(c,0.94),(b,0.93),(a,0.9)\rangle$. This
ranking differs from the maximum approach. As $c$ is proposed by the second
and third most confident rules, its aggregated confidence is higher than $a$
or $b$, entities proposed by the most confident rule.

In theory, Noisy-OR allows for more sophisticated confidence aggregation.
However, it assumes independence/non-redundancy of all rules. As most rules
that can be derived from real-world knowledge bases are in some way redundant
with other rules, Noisy-OR was found to perform worse than maximum aggregation
in practice.

###  2.4 The detrimental effect of redundancy on Noisy-OR aggregation

Redundancies in rules can lead to overestimation of confidences of predicted
entities when aggregating using Noisy-OR. As two redundant rules generate the
same predictions for the same reasons, the confidences of entities predicted
by both rules are overestimated due to double counting. Consider the rules
shown in Table 4 where this problem becomes apparent. If the training set
contains the ground path $lives(john,uk),lang(uk,english)$, each rule would
predict $speaks(john,english)$ upon the prediction task $speaks(john,?)$ for
the same reasons. Aggregating the confidences of all three rules using Noisy-
OR would result in an overestimated confidence of $0.988$ for the entity
english.

$speaks(X,Y)$ | ${}\leftarrow lives(X,A),lang(A,Y)$ | 0.9
---|---|---
$speaks(john,Y)$ | ${}\leftarrow lives(john,A),lang(A,Y)$ | 0.7
$speaks(X,english)$ | ${}\leftarrow lives(X,A),lang(A,english)$ | 0.6
Table 4: Examples of obvious redundancies between rules.

While these redundancies are apparent, redundancies between rules are often
less obvious in practice. Redundancy between two rules can arise from special
relationships between relations, such as relations that are nearly equivalent,
symmetric relations or relations entailing other relations. Consider the rules
shown in Table 5. The first example shows two rules being redundant based on
entailment, as every capital of a country is a city within that country. The
second example shows redundancy based on the symmetric relationship married.
Both rules generate predictions for languages spoken by a person, based on
what language its spouse speaks. The third example shows that such
relationships are not restricted to single relations, but can arise from a
combination of relations, as the combination parent $\rightarrow$ brother is a
duplicate of the relation uncle.

$citizen(X,Y)$ | ${}\leftarrow born(X,A),city(A,Y)$ | 0.7
---|---|---
$citizen(X,Y)$ | ${}\leftarrow born(X,A),capital(A,Y)$ | 0.7
$speaks(X,Y)$ | ${}\leftarrow married(X,A),speaks(A,Y)$ | 0.6
$speaks(X,Y)$ | ${}\leftarrow married(A,X),speaks(A,Y)$ | 0.6
$lives(X,Y)$ | ${}\leftarrow parent(X,A),brother(A,B),lives(B,Y)$ | 0.6
$lives(X,Y)$ | ${}\leftarrow uncle(X,A),lives(A,Y)$ | 0.6
Table 5: Examples of less apparent redundancies between rules.

It is important to understand that there is usually no explicit information
available about the symmetry of married nor do we know that capital is more
specific than city. It is not even possible to grasp this information from the
dataset itself as it might be incomplete and noisy. This makes it impossible
to decide redundancy via a procedure that makes use of relevant background
knowledge.

##  3 Approach

###  3.1 Algorithm

To overcome the problem of redundancy when using the Noisy-OR aggregation
method, we propose an approach to cluster rules based on their redundancy
degree prior to aggregation. Predictions of rules in a cluster are aggregated
using the Maximum approach, as this approach is not susceptible to
redundancies. Predictions of the different clusters are then further
aggregated using the Noisy-OR approach. We call the resulting aggregation
technique Non-redundant Noisy-OR. A pseudocode of Non-redundant Noisy-OR can
be seen in Appendix G.

As a metric for redundancy between two rules $r_{i}$, $r_{j}$ the Jaccard
Index
$sim(r_{i},r_{j})=|\hat{H}_{r_{i}}\cap\hat{H}_{r_{j}}|/|\hat{H}_{r_{i}}\cup\hat{H}_{r_{j}}|$
of the sets of inferred triples is used. As the calculation of the Jaccard
coefficient is very inefficient for large sets, the Jaccard coefficient is
estimated using the MinHash scheme Broder (1997), which makes time complexity
linear and memory usage constant.

Naturally rules are pre-clustered by their relation of the head atom, as two
rules having a different relation in the head are never used in the same
prediction task and the union of their inferred triples is always empty
$h_{r_{i}}\neq
h_{r_{j}}\rightarrow\hat{H}_{r_{i}}\cap\hat{H}_{r_{j}}=\emptyset$. Thus,
similarity matrices of rules are calculated for each head relation and used to
cluster the rules.

Two rules $r_{i}$, $r_{j}$ are considered redundant and assigned to the same
cluster if $sim(r_{i},r_{j})>t$, where $t$ is a threshold. However a global
threshold $t$ is not capable of defining the cutoff point for redundancy for
all relations, rule types and directions of prediction (prediction of head
entities or tail entities). As the sets of rules that predict for different
relations may vary in distribution of type, length or specificity, the
threshold that generates the optimal clustering for a relation may not
generate the optimal clustering for a different relation. Furthermore as
relations may vary in multiplicity the direction of the prediction has to
taken into account. Therefore, a distinct threshold for the prediction of
heads and prediction of tails for each relation is required in order to be
able to optimally cluster an entire rule set. Furthermore, within a set of
rules that predict for the same relation, optimal thresholds may vary between
types of rules. As can be seen by the examples in Table 4, the type
combination of C and AC1 often tends to form set-subset relation. The Jaccard
Index is very insensitve to such relationships. While e.g. a Jaccard index of
0.25 between a rule of type C and a rule of type AC1 may indicate a high
redundancy due to the dominance of set-subset relationships within rules of
this type combination, it may be considered as a fairly low evidence level for
a redundancy between two rules of type C, where such relationships are not as
prominent. Thus a differentiation of rule types is needed when defining the
cutoff value for redundancy between two rules of a certain relation. For each
combination of rule types an independent threshold parameter is used to
determine redundancy. Conclusively, the threshold of similarity for rules that
predict entities of direction $d$ (head or tail) of a $h$-triple (we use $h$
to refer to a relation, while $r$ is used to refer to rules) is given by
$t_{hd}=[t_{C/C},t_{C/AC1},t_{C/AC2},t_{AC1/AC2},t_{AC1/AC1},t_{AC2/AC2}]$.
Note that if $t_{hd}=[0,0,0,0,0,0]$ only the Maximum aggregation is used and
if $t_{hd}=[1,1,1,1,1,1]$ only Noisy-OR.

An optimal clustering of rules that predict $h$-triples is given by the type
combination thresholds $t_{hd}$ that maximize the fitness of the clusters for
predicting new links. This fitness is evaluated on the validation set using
the mean-reciprocal rank based on the top-k predicted entities. SAFRAN uses
one of two search strategies for finding the optimal thresholds: grid search
(parameter sweep) and random search. For grid search the range of possible
thresholds $[0.0,1.0]$ is divided by $n$ equally distant steps and each
threshold is subsequently used for clustering. For the grid search, we do not
distinguish between rule-type specific parameters but use a single relation-
specific fix parameter $t_{hd}$ to limit the search space. Contrary to this,
the random search randomly samples the six rule-type-specific thresholds of
$t_{hd}$.

###  3.2 An Example and its Explanation

Figure 1: Comparing the list of predicted entities for the prediction task
genre_artist(?, Bryan Adams) for Non-redundant Noisy-OR and maximum approach.

Figure 1 demonstrates the effect of our algorithm. It has two parts that both
illustrate the list of predicted entities for the prediction task
genre_artist(?, Bryan Adams). The upper half of the figure shows the result of
applying the Non-redundant Noisy-OR approach, while the lower part presents
the results of the maximum aggregation. In addition to the candidate lists
some explanations in terms of the rules or rule clusters that predict these
entities are shown. For the Non-redundant Noisy-OR we depict the two clusters
that have the highest maximum confidence. By aggregating these clusters via
the Noisy-OR multiplication, the highest rank candidate is Pop rock.

A different result can be observed for the maximum aggregation. The correct
entity Pop rock is ranked at the third position, while the first position is
occupied by Heavy Metal. The example illustrates nicely that the influence of
a single rule can be too strong in the maximum approach, while the Non-
redundant Noisy-OR approach allows to aggregate the results in a more
meaningful way. This holds in particular if the clusters make sense and
combine similar reasons for a prediction within the same cluster. Therefore,
in addition to improving predictive performance, our algorithm provides
explanations that are easier to understand and that provide deeper insights
about the underlying data and the rules derived from them.

##  4 Experiments

We conducted experiments with three established link prediction datasets,
including FB15k-237 Toutanova and Chen (2015), WN18RR Dettmers et al. (2018)
and YAGO3-10 Dettmers et al. (2018). An overview of these datasets can be seen
in Table 6. For our experiments we selected only datasets without train-test
leakage. We abstained from performing experiments on the parent datasets FB15k
(WN18) Bordes et al. (2013) of FB15k-237 (WN18RR) as they were found to suffer
from heavy testing leakage (f.e. some triples in the test data are present as
inverse triples in the training data).

Training, inferencing and evaluations were run on a machine with 24 physical
(48 logical) Intel(R) Xeon(R) CPU E5-2650 v4 @ 2.20GHz cores and 264 GB of
RAM. As SAFRAN and AnyBURL do not utilize GPU-accelerated computing, only CPUs
were used. For optimal comparison with the best results using the maximum
aggregation approach presented in Meilicke et al. (2020), the same learning
parameters were adopted for the same datasets. Rulesets used for the results
were learned for 1000 seconds each, using 22 threads. For rules learned from
WN18RR the maximum length of cyclic rules was set to 5, while for all other
datasets a maximum length of 3 was used. The maximum length of acyclic rules
was set to 1 for all datasets. As FB15k-237 contains reflexive triples in the
form of $r(c,c)$ a flag was set that allows AnyBURL to use such reflexive
triples for learning rules. The same rulesets were used for inference and
evaluation with AnyBURL and SAFRAN. Random search was performed using a $n$ of
10 and 10000 iterations, while grid search was performed with a $n$ of 200.

| # Entities | # Relations | # Training | # Test | # Validation
---|---|---|---|---|---
FB15k-237 | 14,541 | 237 | 272,115 | 17,535 | 20,466
WN18RR | 40,943 | 11 | 86,845 | 3,034 | 3,134
YAGO3-10 | 123,182 | 37 | 1,079,040 | 5,000 | 5,000
Table 6:  Dataset statistics. Number of entities, relations and triples in
each dataset.

|  |  |  | FB15K-237 | WN18RR |  | YAGO3-10
---|---|---|---|---|---|---|---
| Approach |  |  | MRR | hits@1 | hits@10 | MRR | hits@1 | hits@10 |  | MRR | hits@1 | hits@10
Latent | RESCAL |  | $\star$ | .357 | .263 | .541 | .468 | .439 | .521 |  |  |  |
TransE |  | $\star$ | .313 | .221 | .497 | .227 | .053 | .526 | $\P$ | .501 | .405 | .673
DistMult |  | $\star$ | .343 | .250 | .531 | .452 | .413 | .531 | $\P$ | .501 | .412 | .661
ComplEx |  | $\star$ | .348 | .253 | .534 | .477 | .438 | .543 | $\P$ | .576 | .505 | .704
ConvE |  | $\star$ | .339 | .248 | .521 | .447 | .411 | .508 | $\P$ | .488 | .399 | .657
RotatE |  | $\P$ | .336 | .238 | .531 | .475 | .426 | .574 | $\P$ | .498 | .405 | .670
TuckER |  | $\P$ | .352 | .259 | .536 | .459 | .430 | .514 | $\P$ | .544 | .465 | .680
| HAKE |  | $\bigtriangledown$ | .346 | .250 | .542 | .497 | .452 | .582 |  | .545 | .462 | .694
Interpretable | C-NN |  | $\bigtriangleup$ | .296 | .222 | .446 | .469 | .444 | .519 |  |  |  |
DRUM |  | $\ddagger$ | .343† | .255† | .516† | .486† | .425† | .586† |  |  |  |
Neural LP |  | $\diamondsuit$ | .240† |  | .362† | .435† | .371† | .566† |  |  |  |
GPFL |  | $\diamondsuit$ | .322 | .247 | .504 | .480 | .449 | .552 |  |  |  |
AMIE+ |  | $\clubsuit$ |  | .174 | .409 |  | .358 | .388 |  |  |  |
RuleN |  | $\clubsuit$ |  | .182 | .420 |  | .427 | .536 |  |  |  |
RLvLR |  | $\sharp$ | .240 |  | .393 |  |  |  |  |  |  |
AnyBURL with SAFRAN | Maximum |  | .355 | .270 | .519 | .494 | .452 | .572 |  | .559 | .487 | .686
Noisy-OR |  | .342 | .258 | .502 | .454 | .399 | .562 |  | .524 | .444 | .672
VS |  | .363 | .277 | .526 | .497 | .455 | .572 |  | .560 | .489 | .689
NRNO * (grid) |  | .370 | .287 | .531 | .501 | .457 | .581 |  | .564 | .492 | .691
NRNO * (random) |  | .389 | .298 | .537 | .502 | .459 | .578 |  | .564 | .491 | .693

Table 7:  MRR, Hits@1, Hits@10 results for FB15K-237, WN18RR and YAGO3-10.
Best results for each metric and dataset are marked in bold. *Denotes our
approach. †Results were evaluated with top policy for dealing with same score
entities (see Appendix A) and are not directly comparable to other approaches.
Results marked with $\star$ are from Ruffinelli et al. (2020), $\P$ from Rossi
et al. (2021), $\bigtriangleup$ from Ferré (2020), $\ddagger$ from Sadeghian
et al. (2019), $\diamondsuit$ from Gu et al. (2020b), $\clubsuit$ from
Meilicke et al. (2019), $\sharp$ from Omran et al. (2018) and
$\bigtriangledown$ from Zhang et al. (2020).

We compare our results with the established latent models RESCAL Nickel et al.
(2011), TransE Bordes et al. (2013), DistMult Yang et al. (2015), ComplEx
Trouillon et al. (2016), ConvE Dettmers et al. (2018), RotatE Sun et al.
(2019), TuckER Balazevic et al. (2019) and the rule-based methods AMIE+
Galárraga et al. (2015), RuleN Meilicke et al. (2018), C-NN Ferré (2020),
Neural LP Yang et al. (2017), RLvLR Omran et al. (2018), DRUM Sadeghian et al.
(2019), GPFL Gu et al. (2020b). For details on these approaches we refer to
their respective original papers. For each approach we report the filtered
mean reciprocal rank (MRR), filtered hits@1 and filtered hits@10, where
predicted triples that are already known are filtered out, except the test
triple itself. The results for FB15k-237, WN18RR and YAGO3-10 can be seen in
Table 4. All results reported by us were evaluated according to the average
policy Rossi et al. (2021) (see Appendix A), where the rank of a target entity
within a group of same score entities is the average rank of this group.
Reported results from Rossi et al. (2021), Ruffinelli et al. (2020) were
evaluated using the same protocol. Results of C-NN, GPFL, AMIE+, RuleN were
evaluated using ordinal (random) policy which results in very similar results
than average policy, while to the best of our knowledge there is no
information available about the policy used for evaluating RLvLR. Results of
DRUM and Neural LP were evaluated using the top policy which is biased towards
producing better evaluations results and cannot be compared directly to other
results.

Our aggregation method in the more exhaustive random search outperforms both
symbolic and subsymbolic approaches on FB15k-237 and WN18RR. This is a
surprising result as both data sets have been used for years to evaluate and
improve performance of latent methods that are build on the concept of
embeddings. On YAGO3-10 the results are slightly worse. For this data set
ComplEx achieves an MRR that is 0.012 higher. However, AnyBURL together with
the Non-redundant Noisy-OR is still among the top performing techniques. With
our approach we offer a fully interpretable symbolic approach, that allows to
explain the results in terms of the rules that generated them, while we are
still able to compete with or even outperform latent approaches. The
improvement against the AnyBURL default maximum aggregation technique differs
a lot between datasets. While we observe a clear improvement of more than 3%
in terms of MRR for FB15k-237, the improvement for the other datasets is
around 0.5% to 1%. Currently we do not understand the reason for this
differences. The most probable explanation is a lower degree of redundancy in
the rules that describe the regularities encoded in these datasets.

Another reason for this may be the small validation set sizes of WN18RR and
YAGO3-10. While the training set of YAGO3-10 is the biggest of the three
datasets used in the experiments, the size of its validation set is only 0.46%
of the dataset, compared to 6.6% in FB15k-237. However, non-redundant Noisy-OR
needs an appropriate sized validation set that represents a broad spectrum of
relations and entities to be able to fully recognize redundancies. The
validation set size of WN18RR is 3.4% of the dataset. However as the overall
dataset is considerably small, the absolute size of its validation set is only
3,134 triples. As rules generated by AnyBURL can generalize to unseen entities
Ferré (2020), this size may not be sufficient to generate the most optimal
clustering.

In our experiments we used two different search techniques. The random search
performs better in most cases. As explained above, it learns thresholds that
distinguish between different rule types. Thus, only a random selection of all
possible threshold combinations is visited during the search. Nevertheless,
type-specific thresholds seem to make sense as the results are in most cases
slightly better compared to the grid search, which learns a single threshold
per relation.

To support our claim that Non-redundant Noisy-OR could potentially be applied
to other rule-based approaches, we performed experiments on all used data sets
using rules learned by AMIE+. The results can be seen in Appendix F. We used
AMIE in its default setting. This means that it mines only cyclic rules. This
could be the reason that we observed no or only a very limited improvement on
each data sets with the exception of FB15k-237.

To ascertain the importance of optimal thresholds, we performed another
experiment. We evaluated each relation in the validation set using Noisy-OR
and Maximum aggregation and apply the approach with the maximum MRR of each
relation to the test set. Results for the datasets can be seen in Table 4
denoted as VS. All metrics improved compared to the Maximum aggregation but
could not achieve the gain of Non-redundant Noisy-OR.

##  5 Related Work

One of the most prominent rule mining systems is AMIE, which has been
described first in Galárraga et al. (2015) and later, including several
extension and improvements in Lajus et al. (2020). These papers focus mainly
on mining rules (including the confidence computation) rather than their
application. This is typical for most rule-mining or inductive logic
programming (ILP) papers. The authors touch the topic of how to aggregate
confidences only in a single experiment where they compare maximum and the
Noisy-OR aggregation. According to their results the Noisy-OR approach works
better.

In Ferré (2020) another interesting variation of Noisy-OR, the Dempster–Shafer
score Denoeux (1995), has been applied. This approach is not based on rules,
but relies on another symbolic representation using concepts of nearest
neighbours. In their experiments the authors found that the aggregation using
the Dempster–Shafer score performs at best 1.3 % worse than the maximum score
Ferré (2020).

It might make sense to decouple the learning of rules from the model used for
their application. ProbLogic De Raedt et al. (2007) offers a well-defined
model for applying probabilistic rules to a given set of facts (or triples).
ProbLog evaluates probabilistic logic programs by combining Selective Linear
Definite clause resolution (SLD-resolution) with methods for computing the
probability of Boolean formulae. Using ProbLog for applying the rules learned
by a rule miner would be similar to the Noisy-OR aggregation we described
above. As ProbLog is based on a model-theoretic notion of entailment,
predictions created by a rule might enable other rules to fire, which might
again result into further predictions (and so on). While this makes sense from
a conceptual point of view, such an approach results in runtime problems for
larger datasets.

In Kuželka and Davis (2020) the authors proposed Markov Logic as a powerful
framework for solving knowledge base completion tasks. Instead of learning
rules, the authors propose to learn the weights of a Markov logic network. As
a consequence, dependencies between regularities are modeled in a complex way,
which would lead to a non-trivial aggregation of evidences. However, the
analysis remains entirely theoretical and, so it is doubtful whether the
approach is applicable to larger knowledge graphs.

The concept of rule redundancy is crucial for rule aggregation. If two rules
predict the same candidate for the same reason, a Noisy-OR aggregation makes
no sense. In Gu et al. (2020a) a rule hierarchy was used to detect redundant
rules. However, the application model is based on the maximum aggregation
strategy, which means that the removal has no positive impact on the
predictive quality. Indeed, the authors focus their experiments on runtime
performance and report about a positive impact without a decrease in the
predictive quality.

It is important to understand that the notion of rule redundancy is not
limited to logical or extentional equivalence. Approaches to detect equivalent
duplicate rules are well known in ILP, and have for example been implemented
in QuickFOIL Zeng et al. (2014). Instead of that, we have to deal with
problems where two rules are only partially or nearly redundant.

We note that there are a few approaches that try to generate post-hoc
explanations of predictions made by latent models such as knowledge graph
embeddings. However, as opposed to AnyBURL/SAFRAN which provides ad-hoc
explanations for every predicted triple, such approaches often fail to find
explanations. F.e. the approach proposed in Zhang et al. (2019) applied to the
knowledge graph embedding CrossE can only find explanations for 40% of triples
in the test set of the FB15K dataset. Furthermore it is not fully transparent
if generated explanations actually represent the reason for a prediction of a
latent model.

##  6 Conclusion

Interpretable models drastically improve the trust and practical utility of
predictions, and help to address current concerns about intransparency and
unwanted bias in machine learning models. We introduced a novel method for
fully interpretable link prediction that yields new state-of-the-art results
among interpretable methods and outperforms state-of-the-art embedding models
on some of the established benchmarks. Furthermore, our approach provides
explanations that reveal clustering patterns in underlying data and derived
rulesets. While our approach can significantly improve predictive performance
of rule-based approaches, a more in-depth analysis is needed to assess the
quality of generated clusters, which we plan to do in future work. We hope
that beyond their direct practical utility, our results help to reinvigorate
interest into novel rule-based approaches to complement the embedding- and
deep learning-based approaches that have been at the center of attention in
machine learning research over the past years.

Acknowledgments

This work received funding from netidee grant 5171 (’OpenBioLink’).

## References

  * Balazevic et al. [2019] Ivana Balazevic, Carl Allen, and Timothy Hospedales.  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, November 2019. Association for Computational Linguistics.  doi: 10.18653/v1/D19-1522.  URL https://www.aclweb.org/anthology/D19-1522.
  * Bordes et al. [2013] Antoine Bordes, Nicolas Usunier, Alberto Garcia-Duran, Jason Weston, and Oksana Yakhnenko.  Translating embeddings for modeling multi-relational data.  2013\.  URL https://papers.nips.cc/paper/5071-translating-embeddings-for-modeling-multi-relational-data.
  * Broder [1997] Andrei Zary Broder.  On the resemblance and containment of documents.  In _Proceedings. Compression and Complexity of SEQUENCES 1997 (Cat. No.97TB100171)_ , page 21–29. IEEE Comput. Soc, 1997.  doi: 10.1109/SEQUEN.1997.666900.
  * De Raedt et al. [2007] Luc De Raedt, Angelika Kimmig, and Hannu Toivonen.  Problog: A probabilistic prolog and its application in link discovery.  In _IJCAI_ , volume 7, pages 2462–2467. Hyderabad, 2007.
  * Denoeux [1995] T. Denoeux.  A k-nearest neighbor classification rule based on dempster-shafer theory.  _IEEE Transactions on Systems, Man, and Cybernetics_ , 25(5):804–813, 1995.  doi: 10.1109/21.376493.
  * Dettmers et al. [2018] Tim Dettmers, Pasquale Minervini, Pontus Stenetorp, and Sebastian Riedel.  Convolutional 2d knowledge graph embeddings.  In _Thirty-Second AAAI Conference on Artificial Intelligence_ , 2018\.
  * Ferré [2020] Sébastien Ferré.  Application of concepts of neighbours to and knowledge graph completion.  _Data Science_ , Preprint:1–28, 2020.  ISSN 2451-8492.  doi: 10.3233/DS-200030.  URL https://doi.org/10.3233/DS-200030.  Preprint.
  * Galárraga et al. [2015] Luis Galárraga, Christina Teflioudi, Katja Hose, and Fabian M. Suchanek.  Fast rule mining in ontological knowledge bases with amie+.  _The VLDB Journal_ , 24(6):707–730, Dec 2015\.  ISSN 0949-877X.  doi: 10.1007/s00778-015-0394-1.  URL https://doi.org/10.1007/s00778-015-0394-1.
  * Gu et al. [2020a] Yulong Gu, Yu Guan, and Paolo Missier.  Building rule hierarchies for efficient logical rule learning from knowledge graphs, 2020a.
  * Gu et al. [2020b] Yulong Gu, Yu Guan, and Paolo Missier.  Towards learning instantiated logical rules from knowledge graphs, 2020b.
  * Kuželka and Davis [2020] Ondřej Kuželka and Jesse Davis.  Markov logic networks for knowledge base completion: A theoretical analysis under the mcar assumption.  In Ryan P. Adams and Vibhav Gogate, editors, _Proceedings of The 35th Uncertainty in Artificial Intelligence Conference_ , volume 115 of _Proceedings of Machine Learning Research_ , pages 1138–1148. PMLR, 22–25 Jul 2020.  URL http://proceedings.mlr.press/v115/kuzelka20a.html.
  * Lajus et al. [2020] Jonathan Lajus, Luis Galárraga, and Fabian Suchanek.  Fast and exact rule mining with amie 3.  In _European Semantic Web Conference_ , pages 36–52. Springer, 2020\.
  * Meilicke et al. [2018] Christian Meilicke, Manuel Fink, Yanjie Wang, Daniel Ruffinelli, Rainer Gemulla, and Heiner Stuckenschmidt.  Fine-grained evaluation of rule- and embedding-based systems for knowledge graph completion.  In Denny Vrandečić, editor, _The Semantic Web ? ISWC 2018 : 17th International Semantic Web Conference, Monterey, CA, USA, October 8?12, 2018, Proceedings, Part I_ , pages 3–20, Cham, 2018. Springer.  doi: 10.1007/978-3-030-00671-6“˙1.  URL https://madoc.bib.uni-mannheim.de/45092/.
  * Meilicke et al. [2019] Christian Meilicke, Melisachew Wudage Chekol, Daniel Ruffinelli, and Heiner Stuckenschmidt.  Anytime bottom-up rule learning for knowledge graph completion.  In Sarit Kraus, editor, _Proceedings of International Joint Conferences on Artificial Intelligence_ , pages 3137–3143, California, aug 2019\.  ISBN 978-0-9992411-4-1.  doi: 10.24963/ijcai.2019/435.
  * Meilicke et al. [2020] Christian Meilicke, Melisachew Wudage Chekol, Manuel Fink, and Heiner Stuckenschmidt.  Reinforced anytime bottom up rule learning for knowledge graph completion.  _arXiv_ , apr 2020.  URL https://arxiv.org/abs/2004.04412.
  * Nickel et al. [2011] Maximilian Nickel, Volker Tresp, and Hans-Peter Kriegel.  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, 2011. Omnipress.  ISBN 9781450306195.
  * Omran et al. [2018] Pouya Ghiasnezhad Omran, Kewen Wang, and Zhe Wang.  Scalable rule learning via learning representation.  In _Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI-18_ , pages 2149–2155. International Joint Conferences on Artificial Intelligence Organization, 7 2018\.  doi: 10.24963/ijcai.2018/297.  URL https://doi.org/10.24963/ijcai.2018/297.
  * Rossi et al. [2021] Andrea Rossi, Denilson Barbosa, Donatella Firmani, Antonio Matinata, and Paolo Merialdo.  Knowledge graph embedding for link prediction: A comparative analysis.  _ACM Trans. Knowl. Discov. Data_ , 15(2), January 2021.  ISSN 1556-4681.  doi: 10.1145/3424672.  URL https://doi.org/10.1145/3424672.
  * Ruffinelli et al. [2020] Daniel Ruffinelli, Samuel Broscheit, and Rainer Gemulla.  You can teach an old dog new tricks! on training knowledge graph embeddings.  In _International Conference on Learning Representations_ , 2020.  URL https://openreview.net/forum?id=BkxSmlBFvr.
  * Sadeghian et al. [2019] Ali Sadeghian, Mohammadreza Armandpour, Patrick Ding, and Daisy Zhe Wang.  Drum: End-to-end differentiable rule mining on knowledge graphs.  In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , volume 32. Curran Associates, Inc., 2019.  URL https://proceedings.neurips.cc/paper/2019/file/0c72cb7ee1512f800abe27823a792d03-Paper.pdf.
  * Sun et al. [2019] Zhiqing Sun, Zhi-Hong Deng, Jian-Yun Nie, and Jian Tang.  Rotate: Knowledge graph embedding by relational rotation in complex space.  In _International Conference on Learning Representations_ , 2019.  URL https://openreview.net/forum?id=HkgEQnRqYQ.
  * Toutanova and Chen [2015] Kristina Toutanova and Danqi Chen.  Observed versus latent features for knowledge base and text inference.  In _Proceedings of the 3rd Workshop on Continuous Vector Space Models and their Compositionality_ , pages 57–66. Association for Computational Linguistics, jul 2015.
  * Trouillon et al. [2016] Théo Trouillon, Johannes Welbl, Sebastian Riedel, Eric Gaussier, and Guillaume Bouchard.  Complex embeddings for simple link prediction.  In Maria Florina Balcan and Kilian Q. Weinberger, editors, _Proceedings of The 33rd International Conference on Machine Learning_ , volume 48 of _Proceedings of Machine Learning Research_ , pages 2071–2080, New York, New York, USA, 20–22 Jun 2016. PMLR.  URL http://proceedings.mlr.press/v48/trouillon16.html.
  * Yang et al. [2015] Bishan Yang, Scott Wen-tau Yih, Xiaodong He, Jianfeng Gao, and Li Deng.  Embedding entities and relations for learning and inference in knowledge bases.  In _Proceedings of the International Conference on Learning Representations (ICLR) 2015_ , May 2015.
  * Yang et al. [2017] Fan Yang, Zhilin Yang, and William W. Cohen.  Differentiable learning of logical rules for knowledge base reasoning.  In _Proceedings of the 31st International Conference on Neural Information Processing Systems_ , NIPS’17, page 2316–2325, Red Hook, NY, USA, 2017. Curran Associates Inc.  ISBN 9781510860964.
  * Zeng et al. [2014] Qiang Zeng, Jignesh M Patel, and David Page.  Quickfoil: Scalable inductive logic programming.  _Proceedings of the VLDB Endowment_ , 8(3):197–208, 2014.
  * Zhang et al. [2019] Wen Zhang, Bibek Paudel, Wei Zhang, Abraham Bernstein, and Huajun Chen.  Interaction embeddings for prediction and explanation in knowledge graphs.  In _Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining_ , WSDM ’19, page 96–104, New York, NY, USA, 2019\. Association for Computing Machinery.  ISBN 9781450359405.  doi: 10.1145/3289600.3291014.  URL https://doi.org/10.1145/3289600.3291014.
  * Zhang et al. [2020] Zhanqiu Zhang, Jianyu Cai, Yongdong Zhang, and Jie Wang.  Learning hierarchy-aware knowledge graph embeddings for link prediction.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 34(03):3065–3072, Apr. 2020.  doi: 10.1609/aaai.v34i03.5701.  URL https://ojs.aaai.org/index.php/AAAI/article/view/5701.

##  A Evaluation metrics and same score policy

We now formally define used metrics in our experiments. Let $t=2*|T|$ be the
number of prediction tasks in test set $T$ and $rank_{i}$ be the rank of the
correct entity in the predicted list of entities for completion task $i$, then
Hits@k and mean-reciprocal rank (MRR) are defined as follows:

$\begin{split}Hits@k&=\frac{1}{t}\sum_{i=1}^{t}1\text{ if }rank_{i}<k\\\
MRR&=\frac{1}{t}\sum_{i=1}^{t}\frac{1}{rank_{i}}\end{split}$

There are multiple policies for dealing with entities that have the same score
as the correct entity Rossi et al. [2021]:

  * •

Top: The correct entity is given the best rank among a group of same score
entities.

  * •

Bottom: The correct entity is given the worst rank among a group of same score
entities. This policy is the most conservative.

  * •

Average: The rank of the correct entity is the mean rank of all predictions
that tie their score with the correct entity.

  * •

Ordinal: The rank of the correct entity is given the rank in which it appears
in the group of same score entities. This policy usually corresponds to the
random policy.

  * •

Random: The rank of the correct entity is given a random rank of the ranks
within the group of same score entities. This policy usually corresponds to
the average policy.

When comparing results from different sources it is important to use
comparable policies for dealing with same score entities. F.e. results
evaluated with the top policy can be artificially boosted and thus they cannot
be compared to results evaluated with the ordinal/random or average policy.

##  B Ruleset Statistics

| # C | # AC1 | # AC2 | # Total
---|---|---|---|---
FB15K-237 | 53,578 | 1,413,806 | 502,593 | 1,969,977
WN18RR | 7,329 | 38,816 | 25393 | 71,538
YAGO3-10 | 3,699 | 1,955,166 | 333,443 | 2,292,308
Table 8:  Total number of rules and rule type distributions of rule sets used
for the different datasets.

##  C Runtime comparison AnyBURL - SAFRAN

Table 9 shows a comparison of the runtimes of AnyBURL and SAFRAN, when
inferencing filtered predictions of all relevant rules for each prediction
task in the test set of a dataset. The experiment was performed with 8
physical (16 logical) AMD Ryzen 7 PRO 4750U @ 1700 MHz cores and 16 GB of RAM.
SAFRAN could drastically improve the runtime of rule application.

| AnyBURL | SAFRAN | Speed up
---|---|---|---
FB15K-237 | 2074.0 s | 82.0 s | 25.3
WN18RR | 18.6 s | 3.1 s | 6.0
YAGO3-10 | 3022.0 s | 47.5 s | 63.3
Table 9:  Comparison of the runtimes

##  D Threshold Statistics

|  |  | $t=0$ | $0<t<1$ | $t=1$ | $\sim$
---|---|---|---|---|---|---
|  |  | #R | #T | #R | #T | #R | #T | #R | #T
FB15K-237 | Grid | Head | 38 | 4890 | 181 | 15393 | 4 | 170 | 14 | 13
|  | Tail | 44 | 4479 | 178 | 15944 | 1 | 30 | 14 | 13
FB15K-237 | Random | Head | 21 | 2910 | 202 | 17543 | 0 | 0 | 14 | 13
|  | Tail | 34 | 1312 | 189 | 19141 | 0 | 0 | 14 | 13
FB15K-237 | VS | Head | 130 | 14288 | 0 | 0 | 93 | 6165 | 14 | 13
|  | Tail | 137 | 14801 | 0 | 0 | 86 | 5652 | 14 | 13
WN18RR | Grid | Head | 2 | 125 | 9 | 3009 | 0 | 0 | 0 | 0
|  | Tail | 2 | 27 | 9 | 3107 | 0 | 0 | 0 | 0
WN18RR | Random | Head | 1 | 3 | 10 | 3131 | 0 | 0 | 0 | 0
|  | Tail | 1 | 3 | 10 | 3131 | 0 | 0 | 0 | 0
WN18RR | VS | Head | 7 | 2659 | 0 | 0 | 4 | 475 | 0 | 0
|  | Tail | 6 | 1368 | 0 | 0 | 5 | 1766 | 0 | 0
YAGO3-10 | Grid | Head | 6 | 1516 | 27 | 3478 | 0 | 0 | 4 | 6
|  | Tail | 5 | 38 | 28 | 4956 | 0 | 0 | 4 | 6
YAGO3-10 | Random | Head | 7 | 1835 | 26 | 3159 | 0 | 0 | 4 | 6
|  | Tail | 9 | 1597 | 24 | 3397 | 0 | 0 | 4 | 6
YAGO3-10 | VS | Head | 19 | 4510 | 0 | 0 | 14 | 484 | 4 | 6
|  | Tail | 18 | 4210 | 0 | 0 | 15 | 784 | 4 | 6
Table 10:  Number of relations #R and the number of affected test triples #T
of each direction (head or tail) for which the Maximum aggregation ($t=0$),
Non-redundant Noisy-OR ($0<t<1$) and Noisy-OR ($t=1$) produced the best
results in the validation set. $\sim$ is the number of relations that appear
in the training set, but not in the validation set. As the different
thresholds could not be evaluated for these relations, the Maximum aggregation
is used.

##  E Clustering Statistics

Table 11 shows statistics of formed clusters for a selection of relations. As
can be seen, the average cluster size varies greatly between relations.
Extreme examples are the relations happenedIn where primarily small clusters
were formed and isAffiliatedTo where one big cluster and several smaller
clusters were formed.

Relation | #Total Rules | Min | Max | Avg | Std
---|---|---|---|---|---
created | 212176 | 1 | 1023 | 9.59 | 38.19
isLocatedIn | 164222 | 1 | 868 | 1.55 | 3.08
happenedIn | 18644 | 1 | 47 | 1.61 | 1.75
isAffiliatedTo | 884196 | 1 | 787452 | 16.12 | 3361.89
Table 11:  Number of total rules and the minimum, maximum, average and
standard deviation of sizes of clusters for selected relations of YAGO3-10.

##  F Experiments with AMIE+

Table 12 shows the results of Non-redundant Noisy-OR applied to rules learned
with AMIE+. Rules were learned with default settings, in which AMIE+ only
learns cyclic rules. The results can be seen in Table 12. As with rules
learned by AnyBURL, Non-redundant Noisy-OR could achieve the biggest
performance gain on the FB15k-237 dataset. However, the gains on other
datasets are significantly small due to the restriction of the default setting
to only cyclic rules. As the rule set only contains only rules of one type
(i.e. cyclic rules), only a grid search was performed with the same settings
as in Table 4.

|  | MRR | hits@1 | hits@10
---|---|---|---|---
FB15K-237 | Maximum | .172 | .121 | .285
| Noisy-OR | .181 | .128 | .291
| NRNO | .186 | .132 | .299
WN18RR | Maximum | .358 | .355 | .362
| Noisy-OR | .358 | .355 | .362
| NRNO | .358 | .356 | .362
YAGO3-10 | Maximum | .338 | .231 | .525
| Noisy-OR | .338 | .231 | .522
| NRNO | .339 | .231 | .526
Table 12:  Results of Non-redundant Noisy-OR on rules learned by AMIE+.

##  G Pseudocode of Non-redundant Noisy-OR

Algorithm 1 Non-redundant Noisy-OR: Clustering

Input: Set of entities E, Set of relations R, Rule set RS, Thresholds TR of
size $|R|\times 6$, Test set T

for relation $rel$ in R do $\triangleright$ Calculation of clusters of
redundant rules

$relevantRules$ $\leftarrow$ rules in $RS$ having relation $rel$ in head;

for $r_{i}$ in $relevantRules$ do

for $r_{j}$ in $relevantRules$ do

$similarityMatrix[r_{i}][r_{j}]\leftarrow jaccard(r_{i},r_{j})$

end for

end for

$clusters[rel]\leftarrow\O$

for $r_{i}$ in $relevantRules$ do

$visited[r_{i}]\leftarrow 0$

end for

for $r_{i}$ in $relevantRules$ do

if $visited[r_{i}]=0$ then

$cluster\leftarrow\O$

$Q\leftarrow\\{r_{i}\\}$

while Q is not empty do

$r_{j}\leftarrow Q.dequeue()$

$cluster\leftarrow cluster\cup\\{r_{j}\\}$

$visited[r_{j}]\leftarrow 1$

for $r_{k}$ in $relevantRules$ do

if $similarityMatrix[r_{j}][r_{k}]>TR[rel][type(r_{j},r_{k})]$ then

if $visited[r_{k}]=0$ then

$Q.enqueue(r_{k})$

end if

end if

end for

end while

$clusters[rel]\leftarrow clusters[rel]\cup\\{cluster\\}$

end if

end for

end for

for prediction task $t$ in T do $\triangleright$ Application of clusters of
redundant rules

for $e$ in $E$ do

$nrnoisy[e]\leftarrow 0$

end for

for $cluster$ in $clusters[relation(t)]$ do

for $e$ in $E$ do

$maximum[e]\leftarrow 0$

end for

for $rule$ in $cluster$ do

$predictions\leftarrow prediction(rule,t)$

for $e$ in $E$ do

if $e\in predictions$ then

$maximum[e]\leftarrow max(maximum[e],confidence(rule))$;

end if

end for

end for

for $e$ in $E$ do

$nrnoisy[e]\leftarrow noisy(nrnoisy[e],maximum[e])$

end for

end for

end for


# Femtosecond photoelectron circular dichroism of chemical reactions

Vít Svoboda  Laboratory of Physical Chemistry, ETH Zürich, 8093 Zürich,
Switzerland<EMAIL_ADDRESS><EMAIL_ADDRESS>Niraghatam
Bhargava Ram  Laboratory of Physical Chemistry, ETH Zürich, 8093 Zürich,
Switzerland  Department of Physics, Indian Institute of Science Education and
Research - Bhopal, Bhauri, Bhopal 462066, India  Denitsa Baykusheva
Laboratory of Physical Chemistry, ETH Zürich, 8093 Zürich, Switzerland  Daniel
Zindel  Laboratory of Physical Chemistry, ETH Zürich, 8093 Zürich, Switzerland
Max D.J. Waters  Laboratory of Physical Chemistry, ETH Zürich, 8093 Zürich,
Switzerland  Benjamin Spenger  Institute of Chemistry and Biotechnology,
Zurich University of Applied Sciences, 8820 Wädenswil, Switzerland  Manuel
Ochsner  Laboratory of Physical Chemistry, ETH Zürich, 8093 Zürich,
Switzerland  Holger Herburger  Laboratory of Physical Chemistry, ETH Zürich,
8093 Zürich, Switzerland  Jürgen Stohner  Institute of Chemistry and
Biotechnology, Zurich University of Applied Sciences, 8820 Wädenswil,
Switzerland  Hans Jakob Wörner  Laboratory of Physical Chemistry, ETH Zürich,
8093 Zürich, Switzerland<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Understanding the chirality of molecular reaction pathways is essential for a
broad range of fundamental and applied sciences. However, the current ability
to probe chirality on the time scale of chemical reactions remains very
limited. Here, we demonstrate time-resolved photoelectron circular dichroism
(TRPECD) with ultrashort circularly polarized vacuum-ultraviolet (VUV) pulses
from a table-top source. We demonstrate the capabilities of VUV-TRPECD by
resolving the chirality changes in time during the photodissociation of atomic
iodine from two chiral molecules. We identify several general key features of
TRPECD, which include the ability to probe dynamical chirality along the
complete photochemical reaction path, the sensitivity to the local chirality
of the evolving scattering potential, and the influence of electron scattering
off dissociating photofragments. Our results are interpreted by comparison
with novel high-level ab-initio calculations of transient PECDs from molecular
photoionization calculations. Our experimental and theoretical techniques
define a general approach to femtochirality.

## Introduction

Most molecules of biochemical relevance are chiral. The mechanisms controlling
the chiral selectivity of chemical reactions have therefore been intensively
studied over many decades. In spite of fundamental advances, our ability to
track the dynamically evolving chirality of reacting molecules remains
surprisingly limited. The most mature techniques of chiral recognition rely on
tiny differences in the absorption of circularly polarized light by the
enantiomers of a chiral molecule, an effect known as circular dichroism (CD),
which arises from the interference of electric and magnetic dipole
transitions. Considerable efforts have been invested in the development of
time-resolved CD (TRCD) methods, which have been successfully applied to
liquid systems, as reviewed in Ref. [1] and recently in Ref. [2]. The latter
overcomes some initial struggles to achieve the desirable sensitivity and
temporal resolution because of the inherent weakness of the CD effect.

This situation has motivated a recent surge of research activity to find more
sensitive methods for chiral discrimination. These recent developments include
microwave three-wave mixing [3, 4], Coulomb-explosion imaging [5, 6], high-
harmonic generation (HHG) in weakly elliptical [7] and bicircular laser pulses
[8, 9], and photoelectron circular dichroism (PECD) [10, 11, 12]. Among these,
PECD has been applied to probe the photophysical relaxation dynamics in highly
electronically excited (Rydberg) states [13, 14] and HHG in bicircular fields
has been used to probe a photochemical reaction [15]. Most recently, the
Coulomb explosion of a core-ionized chiral molecule has been observed at LCLS
(Linac Coherent Light Source) [16], but the PECD measured at three pump-probe
delays did not display significant variations, in agreement with theory.

Here, we report the realization of TRPECD with vacuum-ultraviolet (VUV)
pulses, demonstrating a general probe of the chirality of photochemical
dynamics. This technique combines the benefits of VUV time-resolved
photoelectron spectroscopy [17, 18, 19, 20] with the chiral sensitivity of
PECD. The photon energy is sufficiently high for ionization along the entire
reaction pathway from the excited state through all intermediate
configurations to the final photoproducts. Additionally, depending on the
ionization energy of the unexcited molecules, the photon energy of the probe
may be sufficiently low to prevent their ionization, yielding a background-
free technique. Our technique transposes the remarkable chiral sensitivity of
PECD from probing static molecules in their electronic ground or excited
states [21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35] to probing
chiral light-induced dynamics in electronically excited states. This extension
opens many promising avenues since PECD effects have been reported for valence
orbitals all the way down to core orbitals [11, 21, 27, 36, 37], they have
been shown to be sensitive to molecular conformation and chemical substitution
[25, 38, 39, 40], and capable of identifying absolute configurations by
comparison with theoretical calculations [41]. These properties originate from
the fact that PECD mainly arises from the scattering of photoelectrons in the
chiral molecular potential.

We interpret our experimental results by additionally advancing the
theoretical methodology for PECD calculations. Whereas such calculations have
previously mainly been performed for static molecules in the electronic ground
state, we have developed the methods to calculate transient PECDs along
photochemical reaction pathways. Whereas previous single-photon-PECD
calculations relied on the continuum multiple scattering model using the
X-Alpha local-exchange potential (CMS-X-Alpha) [21, 22] and density-
functional-theory (DFT) [42] methods, here we employ accurate quantum
calculations of electron-molecular scattering to predict the PECD effects
based on single-center partial wave expansion (Schwinger iterative method)
[43, 44]. We have additionally developed the formalism to include
photoselection and molecular alignment into the calculations of PECD. The good
agreement between calculated and observed PECDs deepens the understanding of
the molecular quantum-scattering mechanisms underlying the observed PECD
effects.

Figure 1: Concept of VUV-TRPECD. A) A pump pulse excites the system of
interest and thereby initiates a photochemical reaction. A circularly
polarized VUV probe pulse ionizes the photoexcited molecule and maps its time-
dependent chirality onto a forward-backward asymmetry of the emitted
photoelectrons with respect to the probe-pulse propagation direction. B)
Illustration of time-resolved PECD in the photodissociation of CHBrFI.

The concept of VUV-TRPECD is illustrated in Fig. 1. We investigate the time
evolution of molecular chirality on the natural, femtosecond time scale of
photochemical reactions by combining a source of ultrashort circularly
polarized VUV pulses with photoelectron velocity-map imaging in a pump-probe
scheme. As an example, we study the photodissociation reaction of chiral
molecules excited by an ultrashort linearly polarized laser pulse and follow
changes in the forward-backward asymmetry of the photoelectron angular
distribution (PAD) represented by the sign and magnitude of the $2b_{1}$
coefficient (see the Supplementary Material SM, Section S2), which is a
measure of the chirality, via a femtosecond circularly polarized laser pulse
in the VUV range. For this purpose, we selected two molecules with
complementary characteristics, bromofluoroiodomethane (CHBrFI) and
2-iodobutane (C4H9I). In both cases, the C-I bond is selectively dissociated
following one-photon absorption at 266 nm. The subsequent dynamics is tracked
by a circularly polarized laser pulse centered at 133 nm generated with a new
table-top source described in the SM, Section S1 and Ref. [45]. Our
measurements reveal intriguing changes in the PECD signal on the time scale of
the bond-breaking dynamics and additionally reveal the chirality of the
radical products. A particular property of this scheme is the selectivity of
the probe, which discriminates between the fragments, revealing the chirality
changes in the nascent molecular radical.

## Results

Figure 2: Probing time-dependent chirality in the photodissociation of CHBrFI.
A) Time-resolved photoelectron spectra obtained with pump and probe laser
pulses centered at 266 nm and 133 nm, respectively (positive delays) and vice
versa (negative delays). Photoelectron spectrum of CHBrF radical (blue solid
line) is obtained by averaging the time-resolved spectra between 0.3 ps and 1
ps. B) Photoelectron signal integrated over kinetic energy from 0 eV to 1.5 eV
(left y-axis - black) and time-dependent PECD of the photodissociation of both
enantiomers of CHBrFI (right y-axis - red). CC stands for the cross-
correlation signal (green dash-dotted line).

The time-resolved photoelectron spectrum (TRPES) of the photodissociation of
CHBrFI (vertical ionization energy is 9.86 eV [46]) is presented in Fig. 2A.
The dynamics on the positive-delay side (Fig. 1B) corresponds to the CHBrFI
molecule photodissociating on the $\tilde{\text{A}}$-state potential energy
surface into a CHBrF∙ radical and an iodine atom. The observed spectra are
dominated by a time-zero feature corresponding to resonance-enhanced
(1+1′)-two-photon ionization. On the positive delay side, the photoelectron
signal decays rapidly within the first 300 fs and remains constant afterwards.
This constant signal forms a broad spectral feature spanning a kinetic-energy
range from 0 eV to $\sim$1 eV, which is assigned to the CHBrF∙ radical based
on its calculated adiabatic ionization energy of 8.32 eV [47]. The iodine atom
cannot be ionized by one photon of 133 nm (9.3 eV) because its ionization
energy is too high (10.45 eV[48]). The time-resolved map of the associated
asymmetry parameters $\beta_{2}$ is shown in the Supplementary Material (Fig.
S2).

The dissociation time is obtained from the signal in the photoelectron kinetic
energy range between 0 eV and 1.5 eV using a mono-exponential fit of the form
$A\cdot\exp(-t/\tau_{\mathrm{diss}})+B$ convoluted with a Gaussian cross-
correlation (cc, Fig. 2B). The extracted dissociation time is
$\tau_{\mathrm{diss}}=(70\pm 20)$ fs (see Fig. 2B). This value agrees well
with a theoretical estimate of $\tau_{\mathrm{diss}}^{(\mathrm{calc})}=77$ fs,
obtained using a classical propagation on a non-relativistic ab-initio
surface, which assumed that the dissociation is completed at $r(\ce{C-I})=4.5$
Å.

The negative time-delay side represents the photo-excitation to Rydberg states
by the 133-nm pulse. The evolution on this Rydberg-state manifold is followed
by one-photon ionization with the 266-nm pulse. On the negative-delay side,
the signal decays to zero in about 0.5 ps. This decay is much faster than the
expected lifetime of the Rydberg states and is therefore attributed to the
photoexcited wave packet leaving the configurational space from where one-
photon ionization by the 266-nm pulse is possible. The signal in the energy
range between 2.5 eV and 5.0 eV (see Fig. 2A) is well represented by a mono-
exponential decay with a lifetime of $\tau_{\mathrm{Rydberg}}=(97\pm 6)$ fs.

After discussion of the TRPES results, we now turn to the TRPECD results.
Enantiomerically pure ($\sim 90$ % ee) samples of CHBrFI have been obtained by
chiral chromatographic separation of racemic samples as described in the SM
Section S4. The pump-probe measurements were performed by using circularly
polarized 133-nm pulses to ionize the molecule following excitation by a
linearly polarized 266-nm pulse. The PECD images are formed by subtracting
inverted photoelectron images measured with left- and right-circularly
polarized 133-nm pulses. These images are inverted using a modified version of
the Onion-peeling method, see SM Section S2 for more details. The resulting
difference image contains only the chiral contribution to the photoelectron
angular distribution (PAD). The chiral signal integrated over the
photoelectron kinetic energy range corresponding to the nascent CHBrF fragment
(0 eV to 1.5 eV) is determined by a fit of the form $2b_{1}\cos\theta$ to the
PECD image, where $\theta$ is the photoelectron emission angle with respect to
the propagation direction of the circularly polarized light.

The TRPECD observed during the photodissociation of CHBrFI is shown in Fig.
2B. Higher-order Legendre contributions to the PECD [49] are found to be
negligible ($b_{3}=(0.00\pm 0.01)$) for both enantiomers and all measured time
delays. In the case of the (S)-enantiomer, the PECD value at 0 fs time delay
amounts to $2b_{1}=(0.03\pm 0.01)$, followed by a sign inversion to
$2b_{1}=(-0.04\pm 0.01)$ at 100 fs delay, another sign inversion to delays of
200 fs and 300 fs, and a third inversion of the PECD up to delays of 500 fs.
Due to limitations in the quantity of enantiopure samples, the measurements on
the (R)-enantiomer were focused on the early time delays, which confirmed the
inversion of the PECD to lie between 50 fs and 80 fs, and a late time delay,
which confirmed the chirality of the photoproduct radical. Overall, the
measured PECD values display the inversion symmetry that is expected upon
exchange of the enantiomers.

Figure 3: Probing time-dependent chirality in the photodissociation of
2-iodobutane. A) Time-resolved photoelectron spectra obtained with pump and
probe laser pulses centered at 266 nm and 133 nm, respectively (positive
delays) and vice versa (negative delays). B) Photoelectron signal integrated
from 0.7 eV to 2.5 eV kinetic energy (left y-axis - black) and time-dependent
PECD of the photodissociation of 2-iodobutane (right y-axis - red). CC stands
for the cross-correlation signal (green dash dotted line).

The generality of our VUV-TRPECD method is demonstrated through its
application to another molecule, 2-iodobutane. This molecule is structurally
more complex because the atomic substituents (Br and F) at the chiral center
are replaced with methyl and ethyl groups that have internal degrees of
freedom (internal rotations and vibrations). As in the case of CHBrFI, we
study the selective C-I bond dissociation induced by a pump pulse centered at
266 nm.

The TRPES is shown in Fig. 3A. Positive time delays correspond to the
dissociation of the C-I bond. The dissociation produces a 2-butyl radical and
an iodine atom, whereby the latter does not contribute to the photoelectron
spectrum for the same energetic reasons as stated above. Since the vertical
ionization energy of the 2-butyl radical amounts to 7.6 eV [50], the
corresponding photoelectron band should lie at $\mathrm{PKE}=1.7$ eV. This
value agrees well with the measured transient spectrum. The signal at negative
time delays corresponds to an excitation to high-lying Rydberg states [51].
The time-resolved map of the associated asymmetry $\beta_{2}$ parameters is
shown in the Supplementary Material (Fig. S2).

The observed dynamics are analyzed by a fit to the spectrum in the energy
range between 0.7 eV and 2.5 eV. The fitting results are shown in Fig. 3B,
where a mono-exponential decay of the form
$A\cdot\exp(-t/\tau_{\mathrm{diss}})$, convoluted with a Gaussian cross-
correlation (cc), is fitted to the positive-delay side of the TRPES. The
dissociation is completed within the temporal overlap of the pump and probe
pulses. The photoelectron signal originating from the 2-butyl radical then
further decays with a time constant $\tau_{\mathrm{diss}}=(1.0\pm 0.5)$ ps,
which is assigned to vibrational relaxation [52]. A fit to the signal on the
negative-delay side yields a time constant $\tau_{\mathrm{Rydberg}}=(140\pm
20)$ fs for the wave packet dynamics created in the Rydberg states.

A distinctive feature of 2-iodobutane is that the ground state can be one-
photon ionized by 133-nm radiation. This allowed us to measure a static PECD
from the unexcited molecule as well as a transient PECD from the dissociating
state of the molecule. The static PECD for the ground state amounts to
$2b_{1}=(-0.11\pm 0.02)$, represented by a green diamond in Fig. 4B, which
additionally shows the PECD image. The PECD at the temporal overlap of the
pump and probe pulses is much smaller in magnitude ($2b_{1}=-0.02\pm 0.01$).
Subsequently, the PECD increases to reach a maximum of $2b_{1}=-0.03\pm 0.01$
at a delay of 30 fs and decays to zero by 60 fs, remaining close to zero for
all later time delays.

### Discussion

Figure 4: Comparison of calculated and measured PECDs and their
interpretation. A) TRPECD during the photodissociation of CHBrFI. The lines
connecting the calculated points are meant as a guide to the eyes only. B)
TRPECD (circles) of the photodissociation and ground state PECD (diamonds) of
the (R)-enantiomer of 2-iodobutane. The inset shows a PECD image in polar
coordinates obtained from the ground state of 2-iodobutane. Error bars
represent $\pm 2\sigma$ error from the non-linear fit. Details are given in
the main text.

To rationalize the observed TRPECD signals, we have developed a new method to
calculate the PECD effect on the basis of accurate electron-molecule
scattering methods. Details about this work are described in the SM Section
S3. The PECD associated with the electronically excited state of CHBrFI
prepared in the experiment was calculated as follows. The excited-state
wavefunction at the equilibrium geometry of the electronic ground state was
obtained through a state-specific complete-active-space self-consistent-field
(CASSCF) calculation using the Molpro package [53, 54]. The ePolyScat package
[44, 43] was then used to obtain the photoionization matrix elements from
which the chiral-sensitive PAD coefficient $b_{1}$ was extracted in a
subsequent step.

We first discuss the TRPECDs measured in the case of CHBrFI. The experimental
data is reproduced in Fig. 4A as open circles, whereas the calculated results
are shown as filled circles. Most importantly, the calculations reproduce the
sign alternation of the PECD observed in the experiment, as well as the order
of magnitude of the transient PECD effects. Specifically, the sign changes
from $t=0$ to $t=100$ fs, observed for both enantiomers, and the additional
inversions from $t=100$ fs to $t=200$ fs and from $t=200$ fs to $t=500$ fs,
observed for the (S)-enantiomer, are all reproduced. All calculated PECDs
shown in this article were obtained for isotropic axis distributions. The
effect of photoselection does not change qualitatively the results, as
discussed in the SM Section S3. Calculations for delays longer than $t=200$ fs
could not be numerically converged because they correspond to C-I bond lengths
larger than 4.65 Å, which cannot be efficiently described within the single-
center-expansion used in ePolyScat. Instead, the calculated PECD values given
for $t=500$ fs and $t=1000$ fs (blue squares) were obtained from a calculation
on the equilibrium geometry of the isolated CHBrF∙ radical in its electronic
ground state. At this delay, the CHBrF∙ radical can be safely assumed to
behave as an isolated entity. In this case, we even obtain a quantitative
agreement with the measured values obtained from both enantiomers.

The measured TRPECD signals of 2-iodobutane are reproduced in Fig. 4B in red.
At time zero, the experimental values of both the ground and the first excited
states are shown (green diamond and red circle, respectively). Both measured
PECDs are negative, but the ground-state PECD is significantly larger in
absolute value. In the case of the electronic ground state, the experimental
and calculated PECDs agree well. In the case of the electronically excited
state at temporal overlap of pump and probe pulses, the measured PECD is
significantly smaller than the calculated value. This discrepancy might be
caused by the contribution of a second photoionization channel, in which the
133-nm photon is absorbed first and the 266-nm photon second. This channel is
not included in our calculations. Attempts to calculate PECDs for longer time
delays, i.e. larger C-I separations, were not successful because the ePolyScat
calculations did not converge. However, the PECD of the 2-butyl radical in its
electronic ground state could be obtained. It is shown as the filled red
circle at a delay of 500 fs, which agrees well with the vanishing measured
PECD.

The most remarkable feature of the measured TRPECDs is their different
behavior in the two molecules. Whereas the TRPECD of CHBrFI shows pronounced
variations as a function of time, including at least three inversions of its
sign, the TRPECD of 2-iodobutane converges rapidly to zero. These different
dynamics can be explained in terms of the structural dynamics of the nascent
radicals. Whereas the CHBrF∙ radical has a single low frequency vibrational
mode, i.e. the umbrella motion, the 2-butyl radical has many soft modes,
including internal rotations and the H-wagging mode.

Figure 5: Illustration of the origin of photoproduct chirality. A) Potential
energy surface of the CHBrF radical along the umbrella mode and its lowest
lying vibrational eigenstates. B) Potential energy surface of the 2-iodobutane
radical along the hydrogen-wagging coordinate and its lowest lying vibrational
eigenstates. Blue solid and dashed lines discern the lower and upper
vibrational states in tunneling doublets.

To understand these differences, we discuss the topology of the potential
energy surfaces of the two radicals along the coordinate that interconverts
the two enantiomers, i.e. the umbrella mode in CHBrFI and the H-wagging mode
in the 2-butyl radical (see Fig. 5). The one-dimensional cut of the potential
energy surface of the CHBrF∙ radical along the umbrella mode exhibits a double
well structure as shown in Fig. 5A. The two minima correspond to two
enantiomeric pyramidal geometries of the radical, whereas the local maximum of
the potential corresponds to a planar achiral geometry. The characteristic
time scale for the transformation of one enantiomeric structure into the
other, which occurs by tunneling when the total energy lies below the barrier,
is also known as the stereomutation time $\tau_{\mathrm{stereo}}=h/(2\Delta
E_{10})$ [55], where $h$ is the Planck constant and $\Delta E_{10}$ is the
energy splitting between the lowest and the first excited vibrational states
of the inversion mode. The vibrational energy levels, calculated using a one-
dimensional discrete-variable-representation (DVR) approach [56] along the
umbrella-like coordinate, are shown as horizontal lines. The stereomutation
time for the CHBrF∙ radical in its lowest pair of eigenstates is
$\tau_{\mathrm{stereo}}=5.29$ ps. Because the dissociation time is much
shorter than the stereomutation time, the CHBrF∙ radical may be formed in one
of the two possible pyramidal forms, which corresponds to a coherent
superposition of at least the two lowest states of the umbrella mode. Our
observation of a non-vanishing PECD for pump-probe delays at which
dissociation is completed (0.5-1.0 ps) is consistent with a long
stereomutation time, i.e. the formation of a photoproduct that remains chiral
on the time scale of our measurements.

Figure 6: Effect of photoelectron scattering off the iodine atom (yellow
circles) on TRPECD. Calculations of the PECD of the dissociating molecule
(blue) and the CHBrF∙ radical using the same atomic coordinates, but removing
the iodine atom (green).

Figure 5B shows a one-dimensional cut of the potential energy surface of the
2-butyl radical along the H-wagging coordinate. This potential also has a
double well structure, but in this case, the barrier height is much lower.
This leads to a situation where the lowest vibrational state lies above the
barrier and results in an effectively achiral equilibrium structure. This
explains both the vanishing calculated PECD for the 2-butyl radical and the
rapid decay of the measured PECD to zero.

The most intriguing aspect of our TRPECD results is the observation of
multiple sign changes of the PECD effect during the photodissociation of
CHBrFI. The time delays $t=100$ fs and $t=200$ fs correspond to C-I distances
of more than 4 Å over which the potential energy surfaces are flat. Since the
probe pulse cannot ionize atomic iodine, ionization happens exclusively from
the CHBrF∙ radical at both delays. The sign changes in the PECD effect could
therefore originate from inversions of the CHBrF∙ radical along the umbrella
mode. To verify this hypothesis, we have repeated the PECD calculations shown
in Fig. 4A by using the same molecular geometries but removing the iodine
atom, repeating the electronic structure and finally the photoionization
calculations to obtain the PECD of the CHBrF∙ fragment. The results, shown as
green circles in Fig. 6, are negative for all time delays, in contrast to the
PECD calculations including the iodine atom (blue circles). This shows that
the sign inversions of the PECD do not originate from the inversions of the
CHBrF∙ radical. They must therefore be caused by the presence of the
dissociating iodine atom. Since the latter is separated by $>4$ Å from the
CHBrF radical at delays $>100$ fs, and has therefore no effect on the
electronic structure of the radical, the inversions of the PECD must originate
from scattering of the photoelectrons originating from the CHBrF∙ radical on
the neutral iodine atom. The dramatic effect of electron scattering from the
iodine atom on the PECD is particularly apparent by comparing PECD values at
pump-probe delays $t=100$ fs and $t=200$ fs. At the earlier time delay, the
PECD values are very similar, whereas they are almost opposite at the later
delay. Remarkably, the sensitivity of this PECD effect extends well beyond
that of photoelectron spectroscopy. Whereas the photoelectron spectrum remains
essentially unchanged after $t=100$ fs (Fig. 2) because the dissociating wave
packet has reached the flat part of the potential energy surfaces, the PECD is
still highly sensitive to the presence of the dissociating atom, to the level
that it changes sign several times. These results highlight the extreme
sensitivity of TRPECD to the structural evolution of the dynamically evolving
molecular environment, beyond the simpler energetic aspects probed by TRPES.

In this work, we have demonstrated a new general technique for probing
chirality changes during a chemical reaction. We have revealed the potential
of VUV-TRPECD by time-resolving the changes in molecular chirality introduced
by the selective C-I bond dissociation of two chiral molecules with
complementary characteristics. Our results were interpreted by comparison with
a new theoretical method for calculating PECDs based on accurate electron-
molecule scattering calculations.

In the case of CHBrFI, we have observed a pronounced variation including sign
changes of the PECD during the photodissociation reaction. These inversions of
the PECD have been assigned to photoelectron scattering off the dissociating
iodine atom on the basis of our calculations. The measured PECD at long time
delays differs from zero and agrees with the calculated PECD of the chiral
equilibrium geometry of the CHBrF∙ radical. In the case of 2-iodobutane, we
have measured the PECD of both the excited and unexcited molecules. Our
measurements have revealed a rapid decay of the PECD to zero within 60 fs.
This observation is explained in terms of a rapid racemization of the nascent
2-butyl radical rationalized by the achiral equilibrium geometry of the
2-butyl radical.

Overall, we have demonstrated that VUV-TRPECD opens a general route to studies
of dynamical chirality during chemical reactions. This approach is
sufficiently sensitive to be applicable to molecules in the gas phase. This
general method gives access to the chirality of complete photochemical
reaction pathways from photoexcitation through conical intersections to the
final products, without the restrictions that are imposed by photon energies
in the VIS/UV range. Hence, this technique has the potential to drive major
new developments in the understanding of the dynamic evolution of molecular
chirality in chemical reactions and its role in chiral recognition and
enantioselective molecular processes in general.

## Materials and Methods

### Experiment

All experiments have been performed using a two-color pump-probe scheme
utilizing low-order-harmonic generation in a semi-infinite gas cell and a
velocity-map-imaging (VMI) spectrometer [57]. A Ti:Sa regenerative amplifier
operating at 1 kHz delivered 2.0 mJ pulses centered at 800 nm with 28-fs pulse
duration. The input beam was divided into two arms using an 80:20 beam
splitter. The reflected beam was frequency-doubled using a 300 $\upmu$m thick
$\beta$-barium borate crystal to obtain 570 $\upmu$J pulses at 400 nm ($\sim
35$ fs). The second harmonic beam was separated from the fundamental beam by
reflections on four dichroic mirrors. The polarization of the beam was
controlled by a motorized rotational stage with a quarter-wave plate for 400
nm [45]. The beam was focused by a $f=500$ mm spherical mirror into a semi-
infinite gas cell filled with Xe. The Xe pressure $p_{\mathrm{Xe}}=10$ mbar
was selected such that the third (133 nm $\sim$ 9.3 eV) harmonic of 400 nm was
optimized. The transmitted beam was used for the third harmonic generation
giving 1.2 $\upmu$J pulses of 266 nm ($\sim 70$ fs). Both beams were delivered
into a vacuum chamber using their respective dichroic mirrors and then focused
non-collinearly (with a crossing angle of less than 1∘) by two spherical
mirrors ($f=0.5$ m for the harmonic beam and $f=1$ m for the 266 nm beam). All
in-vacuum mirrors were motorized allowing for fine adjustment of the spatial
overlap.

Samples (racemic or enantiomerically enriched) were evaporated and mixed with
Ne as a carrier gas. The mixture was delivered into the vacuum chamber through
a pulsed nozzle (orifice 150 $\upmu$m, 1 kHz repetition rate). The gas jet
created by the nozzle was skimmed by a 500 $\upmu$m skimmer and propagated 10
cm downstream to reach the interaction region where it was ionized by the
combined action of the laser beams. A cross-correlation between both pulses
was determined by non-resonant two-color ionization (133 nm + 266 nm) of Xe.
The cross-correlation function was taken into account during data analysis as
an instrument-response function. Ejected photoelectrons were imaged using
electrostatic lenses fulfilling VMI conditions, and a dual microchannel-plate
detector in a Chevron configuration.

### Theory

Ground state geometries for both molecules are optimized with Orca program
package on MP2/aug-cc-pVTZ level of theory. All molecular geometries for the
first excited state needed for subsequent CASSCF and ePolyScat calculations
are obtained from ab-initio molecular dynamics calculations. The Born-
Oppenheimer molecular dynamics (BOMD) on the first excited singlet state,
calculated at the CIS/6-311G∗ level with 4 singlet states and no triplet
states, is performed using the Q-Chem program package. The time step of the
BOMD is 25 a.u. (0.6 fs) and the initial velocities are set to zero.

The electronic structure calculations are done in MOLPRO program package.
Since ePolyScat only works with Hartree-Fock-type wavefunctions in which each
orbital is either doubly occupied, singly occupied, or empty, we described the
first excited state of the molecules using a simple CASSCF-type wavefunction
using an active space consisting of two electrons in two orbitals, CAS(2,2),
with only two electronic states with the ground-state weight 0 and the first-
excited-state weight 1. We used cc-pVTZ basis set on all atoms except iodine
which was described with all electron 6-311G∗ basis set. As a result, the
first excited state was described as (…)2(HOMO)1(LUMO)1.

Photoionization matrix elements are calculated with ePolyScat program package
[44, 43], which calculates the matrix elements by solving the corresponding
quantum-mechanical scattering problem in a single-center partial wave
expansion using the Schwinger variational principle. For each time delay, two
calculations are done in which either the HOMO or LUMO orbital is ionized and
the other orbital is left singly occupied. From the calculated photoionization
matrix elements, $b_{1}$ coefficients are calculated in a separate custom-
built routine and HOMO and LUMO contributions are averaged to get the final
$b_{1}$ coefficient.

## Supplementary materials

Section S1. Polarization measurements
Section S2. PECD measurements
Section S3. PECD calculation
Section S4. Synthesis of CHBrFI
Section S5. Synthesis of 2-iodobutane
Section S6. Photoelectron angular distributions

## Acknowledgements

The authors thank Andreas Schneider, Mario Seiler, and Andres Laso for their
contributions to the construction and improvement of the experiment. J.S.
acknowledges help from and discussion with co-worker Manuela Meister, Vanessa
Galati, and Stole Manov, the latter also provided a first batch of enantiopure
2-iodobutane. V.S. and H.J.W. acknowledge a fruitful discussion with Prof.
Stephen Pratt. J.S. received financial support from ZHAW under grant AF-2018
and AF-2019. We gratefully acknowledge funding from ETH Zurich and the Swiss
National Science Foundation through the NCCR-MUST and grant 20021_172946.

## Author contributions statement

H.J.W. proposed the experiments. V.S. and N.B.R. designed and assembled the
experiment. V.S. conducted the experiments, analysed the data, and performed
the theoretical calculations. D.B. and H.H. developed the codes for the PECD
calculations. M.D.J.W. helped with some experiments. V.S., B.S. and J.S.
prepared the enantiopure samples of CHBrFI. M.O. and D.Z. prepared the
enantiopure sample of 2-iodobutane. The manuscript was written by V.S. and
H.J.W. All authors reviewed the manuscript.

## Additional information

Competing interests The authors declare that they have no competing interests.

Data and material availability All data needed to evaluate the conclusions in
the paper are present in the paper and/or the Supplementary Materials.

Correspondence Correspondence and request for materials should be addressed to
H.J. Wörner (email<EMAIL_ADDRESS>or V. Svoboda
(email:vit.svoboda@phys.chem.ethz.ch).

## References

  * [1] Meyer-Ilse, J., Akimov, D. & Dietzek, B.  Ultrafast circular dichroism study of the ring opening of 7-dehydrocholesterol.  _Journal of Physical Chemistry Letters_ 3, 182–185, DOI: 10.1021/jz2014659 (2012).
  * [2] Oppermann, M. _et al._ Ultrafast broadband circular dichroism in the deep ultraviolet.  _Optica_ 6, 56–60, DOI: 10.1364/OPTICA.6.000056 (2019).
  * [3] Patterson, D., Schnell, M. & Doyle, J. M.  Enantiomer-specific detection of chiral molecules via microwave spectroscopy.  _Nature_ 497, 475–477, DOI: 10.1038/nature12150 (2013).
  * [4] Hirota, E.  Triple resonance for a three-level system of a chiral molecule.  _Proceedings of the Japan Academy, Series B_ 88, 120–128, DOI: 10.2183/pjab.88.120 (2012).
  * [5] Pitzer, M. _et al._ Direct determination of absolute molecular stereochemistry in gas phase by Coulomb explosion imaging.  _Science_ 341, 1096–1100, DOI: 10.1126/science.1240362 (2013).
  * [6] Herwig, P. _et al._ Imaging the absolute configuration of a chiral epoxide in the gas phase.  _Science_ 342, 1084–1086, DOI: 10.1126/science.1246549 (2013).
  * [7] Cireasa, R. _et al._ Probing molecular chirality on a sub-femtosecond timescale.  _Nature Physics_ 11, 654–658, DOI: 10.1038/nphys3369 (2015).
  * [8] Harada, Y., Haraguchi, E., Kaneshima, K. & Sekikawa, T.  Circular dichroism in high-order harmonic generation from chiral molecules.  _Physical Review A_ 98, 021401, DOI: 10.1103/physreva.98.021401 (2018).
  * [9] Baykusheva, D. & Wörner, H. J.  Chiral discrimination through bielliptical high-harmonic spectroscopy.  _Phys. Rev. X_ 8, 031060, DOI: 10.1103/PhysRevX.8.031060 (2018).
  * [10] Ritchie, B.  Theory of the angular distribution of photoelectrons ejected from optically active molecules and molecular negative ions.  _Physical Review A_ 13, 1411–1415, DOI: 10.1103/physreva.13.1411 (1976).
  * [11] Powis, I.  Photoelectron circular dichroism of the randomly oriented chiral molecules glyceraldehyde and lactic acid.  _Journal of Chemical Physics_ 112, 301–310, DOI: 10.1063/1.480581 (2000).
  * [12] Böwering, N. _et al._ Asymmetry in photoelectron emission from chiral molecules induced by circularly polarized light.  _Phys. Rev. Lett._ 86, 1187–1190, DOI: 10.1103/PhysRevLett.86.1187 (2001).
  * [13] Comby, A. _et al._ Relaxation dynamics in photoexcited chiral molecules studied by time-resolved photoelectron circular dichroism: Toward chiral femtochemistry.  _Journal of Physical Chemistry Letters_ 7, 4514–4519, DOI: 10.1021/acs.jpclett.6b02065 (2016).
  * [14] Beauvarlet, S. _et al._ Photoelectron elliptical dichroism spectroscopy of resonance-enhanced multiphoton ionization via the 3s, 3p and 3d Rydberg series in fenchone.  _Phys. Chem. Chem. Phys._ 24, 6415–6427, DOI: 10.1039/D1CP05618B (2022).
  * [15] Baykusheva, D. _et al._ Real-time probing of chirality during a chemical reaction.  _Proceedings of the National Academy of Sciences_ 116, 23923–23929, DOI: 10.1073/pnas.1907189116 (2019).
  * [16] Ilchen, M. _et al._ Site-specific interrogation of an ionic chiral fragment during photolysis using an X-ray free-electron laser.  _Communications Chemistry_ 4, 119, DOI: 10.1038/s42004-021-00555-6 (2021).
  * [17] Nugent-Glandorf, L. _et al._ Ultrafast time-resolved soft X-ray photoelectron spectroscopy of dissociating Br2.  _Phys. Rev. Lett._ 87, 193002, DOI: 10.1103/PhysRevLett.87.193002 (2001).
  * [18] Squibb, R. J. _et al._ Acetylacetone photodynamics at a seeded free-electron laser.  _Nature Communications_ 9, 63 (2018).
  * [19] von Conta, A. _et al._ Conical-intersection dynamics and ground-state chemistry probed by extreme-ultraviolet time-resolved photoelectron spectroscopy.  _Nature Communications_ 9, 1–10, DOI: 10.1038/s41467-018-05292-4 (2018).
  * [20] Svoboda, V., Wang, C., Waters, M. D. J. & Wörner, H. J.  Electronic and vibrational relaxation dynamics of NH3 Rydberg states probed by vacuum-ultraviolet time-resolved photoelectron imaging.  _Journal of Chemical Physics_ 151, 104306, DOI: 10.1063/1.5116707 (2019).
  * [21] Powis, I.  Photoelectron circular dichroism: Chiral asymmetry in the angular distribution of electrons emitted by (+)-S-carvone.  _Chirality_ 20, 961–968, DOI: 10.1002/chir.20537 (2008).
  * [22] Powis, I.  Communication: The influence of vibrational parity in chiral photoionization dynamics.  _Journal of Chemical Physics_ 140, 111103, DOI: 10.1063/1.4869204 (2014).
  * [23] Powis, I. _et al._ A photoionization investigation of small, homochiral clusters of glycidol using circularly polarized radiation and velocity map electron–ion coincidence imaging.  _Phys. Chem. Chem. Phys._ 16, 467–476, DOI: 10.1039/c3cp53248h (2014).
  * [24] Powis, I. _et al._ Chiral asymmetry in the angle-resolved O and C 1s-1 core photoemissions of the R enantiomer of glycidol.  _Physical Review A_ 78, DOI: 10.1103/physreva.78.052501 (2008).
  * [25] Garcia, G. A., Dossmann, H., Nahon, L., Daly, S. & Powis, I.  Photoelectron circular dichroism and spectroscopy of trifluoromethyl- and methyl-oxirane: a comparative study.  _Physical Chemistry Chemical Physics_ 16, 16214, DOI: 10.1039/c4cp01941e (2014).
  * [26] Garcia, G. A., Nahon, L., Daly, S. & Powis, I.  Vibrationally induced inversion of photoelectron forward-backward asymmetry in chiral molecule photoionization by circularly polarized light.  _Nature Communications_ 4, 1–6, DOI: 10.1038/ncomms3132 (2013).
  * [27] Hergenhahn, U. _et al._ Photoelectron circular dichroism in core level ionization of randomly oriented pure enantiomers of the chiral molecule camphor.  _Journal of Chemical Physics_ 120, 4553–4556, DOI: 10.1063/1.1651474 (2004).
  * [28] Lux, C., Senftleben, A., Sarpe, C., Wollenhaupt, M. & Baumert, T.  Photoelectron circular dichroism observed in the above-threshold ionization signal from chiral molecules with femtosecond laser pulses.  _Journal of Physics B: Atomic, Molecular and Optical Physics_ 49, 02LT01, DOI: 10.1088/0953-4075/49/2/02lt01 (2015).
  * [29] Lux, C., Wollenhaupt, M., Sarpe, C. & Baumert, T.  Photoelectron circular dichroism of bicyclic ketones from multiphoton ionization with femtosecond laser pulses.  _ChemPhysChem_ 16, 115–137, DOI: 10.1002/cphc.201402643 (2014).
  * [30] Lux, C. _et al._ Circular dichroism in the photoelectron angular distributions of camphor and fenchone from multiphoton ionization with femtosecond laser pulses.  _Angewandte Chemie International Edition_ 51, 5001–5005, DOI: 10.1002/anie.201109035 (2012).
  * [31] Miles, J. _et al._ A new technique for probing chirality via photoelectron circular dichroism.  _Analytica Chimica Acta_ 984, 134–139, DOI: 10.1016/j.aca.2017.06.051 (2017).
  * [32] Kastner, A. _et al._ Enantiomeric excess sensitivity to below one percent by using femtosecond photoelectron circular dichroism.  _ChemPhysChem_ 17, 1119–1122, DOI: 10.1002/cphc.201501067 (2016).
  * [33] Kastner, A. _et al._ Intermediate state dependence of the photoelectron circular dichroism of fenchone observed via femtosecond resonance-enhanced multi-photon ionization.  _Journal of Chemical Physics_ 147, 013926, DOI: 10.1063/1.4982614 (2017).
  * [34] Goetz, R. E., Isaev, T. A., Nikoobakht, B., Berger, R. & Koch, C. P.  Theoretical description of circular dichroism in photoelectron angular distributions of randomly oriented chiral molecules after multi-photon photoionization.  _The Journal of Chemical Physics_ 146, 024306, DOI: 10.1063/1.4973456 (2017).  https://doi.org/10.1063/1.4973456.
  * [35] Artemyev, A. N., Müller, A. D., Hochstuhl, D. & Demekhin, P. V.  Photoelectron circular dichroism in the multiphoton ionization by short laser pulses. I. propagation of single-active-electron wave packets in chiral pseudo-potentials.  _The Journal of Chemical Physics_ 142, 244105, DOI: 10.1063/1.4922690 (2015).  https://doi.org/10.1063/1.4922690.
  * [36] Ulrich, V. _et al._ Giant chiral asymmetry in the C 1s core level photoemission from randomly oriented fenchone enantiomers.  _Journal of Physical Chemistry A_ 112, 3544–3549, DOI: 10.1021/jp709761u (2008).
  * [37] Lehmann, C. S., Ram, N. B., Powis, I. & Janssen, M. H. M.  Imaging photoelectron circular dichroism of chiral molecules by femtosecond multiphoton coincidence detection.  _Journal of Chemical Physics_ 139, 234307, DOI: 10.1063/1.4844295 (2013).
  * [38] Nahon, L. _et al._ Determination of accurate electron chiral asymmetries in fenchone and camphor in the VUV range: sensitivity to isomerism and enantiomeric purity.  _Physical Chemistry Chemical Physics_ 18, 12696–12706, DOI: 10.1039/c6cp01293k (2016).
  * [39] Comby, A. _et al._ Real-time determination of enantiomeric and isomeric content using photoelectron elliptical dichroism.  _Nature Communications_ 9, 5212, DOI: 10.1038/s41467-018-07609-9 (2018).
  * [40] Blanchet, V. _et al._ Ultrafast relaxation investigated by photoelectron circular dichroism: an isomeric comparison of camphor and fenchone.  _Phys. Chem. Chem. Phys._ 23, 25612–25628, DOI: 10.1039/D1CP03569J (2021).
  * [41] Powis, I., Harding, C. J., Garcia, G. A. & Nahon, L.  A valence photoelectron imaging investigation of chiral asymmetry in the photoionization of fenchone and camphor.  _ChemPhysChem_ 9, 475–483 (2008).
  * [42] Stener, M., Fronzoni, G., Tommaso, D. D. & Decleva, P.  Density functional study on the circular dichroism of photoelectron angular distribution from chiral derivatives of oxirane.  _Journal of Chemical Physics_ 120, 3284–3296, DOI: 10.1063/1.1640617 (2004).
  * [43] Natalense, A. P. P. & Lucchese, R. R.  Cross section and asymmetry parameter calculation for sulfur 1s photoionization of SF6.  _Journal of Chemical Physics_ 111, 5344–5348, DOI: 10.1063/1.479794 (1999).
  * [44] Gianturco, F. A., Lucchese, R. R. & Sanna, N.  Calculation of low-energy elastic cross sections for electron-CF4 scattering.  _Journal of Chemical Physics_ 100, 6464–6471, DOI: 10.1063/1.467237 (1994).
  * [45] Svoboda, V., Waters, M. D. J., Zindel, D. & Wörner, H. J.  Generation and complete polarimetry of ultrashort circularly polarized extreme-ultraviolet pulses.  _Optics Express_ 30, 14358–14367, DOI: 10.1364/OE.449411 (2022).
  * [46] Novak, I., Li, D. B. & Potts, A. W.  Electronic structure of chiral halomethanes.  _Journal of Physical Chemistry A_ 106, 465–468, DOI: 10.1021/jp0116959 (2002).
  * [47] He, Y.-L. & Wang, L.  Cations of halogenated methanes: adiabatic ionization energies, potential energy surfaces, and ion fragment appearance energies.  _Structural Chemistry_ 20, 461–479, DOI: 10.1007/s11224-009-9444-x (2009).
  * [48] Imre, D. & Koenig, T.  The He(I) photoelectron spectrum of atomic iodine by photodissociation of molecular iodine.  _Chemical Physics Letters_ 73, 62–66, DOI: 10.1016/0009-2614(80)85203-1 (1980).
  * [49] Powis, I.  Photoelectron circular dichroism in chiral molecules.  In _Advances in Chemical Physics_ , 267–329, DOI: 10.1002/9780470259474.ch5 (John Wiley & Sons, Inc., 2008).
  * [50] Schultz, J. C., Houle, F. A. & Beauchamp, J. L.  Photoelectron spectroscopy of 1-propyl, 1-butyl, isobutyl, neopentyl, and 2-butyl radicals: free radical precursors to high-energy carbonium ion isomers.  _Journal of the American Chemical Society_ 106, 3917–3927, DOI: 10.1021/ja00326a006 (1984).
  * [51] Park, S. T., Kim, S. K. & Kim, M. S.  Vacuum-ultraviolet mass-analyzed threshold ionization spectra of iodobutane isomers: Conformer-specific ionization and ion-core dissociation followed by ionization.  _Journal of Chemical Physics_ 115, 2492–2498, DOI: 10.1063/1.1386786 (2001).
  * [52] Corrales, M. E. _et al._ Structural dynamics effects on the ultrafast chemical bond cleavage of a photodissociation reaction.  _Physical Chemistry Chemical Physics_ 16, 8812, DOI: 10.1039/c3cp54677b (2014).
  * [53] Werner, H.-J., Knowles, P. J., Knizia, G., Manby, F. R. & Schütz, M.  Molpro: a general-purpose quantum chemistry program package.  _Wiley Interdisciplinary Reviews: Computational Molecular Science_ 2, 242–253, DOI: 10.1002/wcms.82 (2011).
  * [54] Werner, H.-J. _et al._ Molpro, version 2015.1, a package of ab initio programs.
  * [55] Quack, M.  On the measurement of the parity violating energy difference between enantiomers.  _Chemical Physics Letters_ 132, 147–153, DOI: 10.1016/0009-2614(86)80098-7 (1986).
  * [56] Colbert, D. T. & Miller, W. H.  A novel discrete variable representation for quantum mechanical reactive scattering via the S-matrix Kohn method.  _Journal of Chemical Physics_ 96, 1982–1991, DOI: 10.1063/1.462100 (1992).
  * [57] Svoboda, V., Ram, N. B., Rajeev, R. & Wörner, H. J.  Time-resolved photoelectron imaging with a femtosecond vacuum-ultraviolet light source: Dynamics in the $\tilde{A}$/$\tilde{B}$\- and $\tilde{F}$-bands of SO2.  _Journal of Chemical Physics_ 146, 084301, DOI: 10.1063/1.4976552 (2017).