Event Causal Relationship Retrieval
Yasunobu Sumikawa
Takushoku University
Tokyo, Japanysumikaw@cs.takushoku-u.ac.jp

ABSTRACT

is important to identify the similarity of not only the words usedin the event descriptions, but also relationships such as cause-andAnalyzing history has numerous benefits, including understanding
effect relationships [7].
what the people in the past did for events and what results they
Although there have been studies on retrieving events, most ofobtained and using historical knowledge to the present. Several pastthem analyze how similar the words [9] and their categories [19]studies have analyzed historical events based on the assumption
are used in the descriptions instead of taking care of event-causalthat each event is described in texts. Most of them analyze how
relationships. By contrast, several studies on history teaching andsimilar the words and their categories used in the descriptions arelearning research fields have proposed methods that guide learners
instead of taking care of event-causal relationships.
to measure the similarity between causal relationships [8]. However,In this study, we propose an algorithm named the Event Causality
the methods use fixed causal relationships defined by researchers;
relationship similarity Measurement (ECM) to measure the similarthus, it is difficult to use other relationships.
ity between event-causal relationships. The ECM solves a maximum
In this study, we propose an algorithm, named Event Causality
weight matching problem on a bipartite graph, where the weights
relationshipsimilarity Measurement (ECM), to measure the similarare the similarities between the event-causal relationships. We evalityof
event-causal
relationships. This study uses two assumptions:
uated ECM with previous related works and confirmed that the1) each event-causal relationship includes at least two events andECM is the best.
2) the events are arranged in chronological order regarding when
they occur. The proposed algorithm creates a bipartite graph, whose
CCS CONCEPTS
nodes and weighted edges represent events and their similarities.
• Information systems → Similarity measures.
It then measures the similarity between the two event-causal relationships by solving a maximum weight matching problem on
KEYWORDS
the graph. We propose a novel matching problem that adds conEvent causal relationship, bipartite graph, a maximum weight matchstraint no intersection points on the edges that are the solutions to theing problem, event retrieval
problem to the general maximum weight matching problem. ThisACM Reference Format:
constraint allows us to evaluate the similarity between event-causal
Yasunobu Sumikawa. 2021. Event Causal Relationship Retrieval. In IEEE/WIC/ACM relationships.
International Conference on Web Intelligence (WI-IAT ’21), December 14–
Fig. 1 shows a motivation example. In this figure, there are three17, 2021, ESSENDON, VIC, Australia. ACM, New York, NY, USA, 8 pages.
event-causal relationships, and there exists an event ”Evacuation“
https://doi.org/10.1145/3486622.3493936
at their end. Looking at the cause of the events, (a) and (b) areboth ”Landslides“, but (c) is a ”Typhoon.“ Because we search for

1

INTRODUCTION

The importance of having a good knowledge of history and theability to apply that knowledge in the present society has been
gaining attention in recent years [1][4]. In fact, the importanceof history is widely recognized, as many countries have classes
for learning history from elementary school, and history curriculaand learning support research emphasize the development of theability to use knowledge in the present society rather than merely
memorizing history [9]. As the saying goes, “History does notrepeat itself, but rhythms repeat themselves,” events occurring in
the past and present often contain similarities as well as differences.
In other words, to utilize knowledge from the past in the present, it
Permission to make digital or hard copies of all or part of this work for personal orclassroom use is granted without fee provided that copies are not made or distributedfor profit or commercial advantage and that copies bear this notice and the full citationon the first page. Copyrights for components of this work owned by others than theauthor(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or
republish, to post on servers or to redistribute to lists, requires prior specific permission
and/or a fee. Request permissions from permissions@acm.org.
WI-IAT ’21, December 14–17, 2021, ESSENDON, VIC, Australia© 2021 Copyright held by the owner/author(s). Publication rights licensed to ACM.
ACM ISBN 978-1-4503-9115-3/21/12. . . $15.00
https://doi.org/10.1145/3486622.3493936

Earthquake

Landslide

Heavy rain
Same cause

Landslide

Evacuation

Evacuation

(a)

(b)
TyphoonEvacuation(c)Figure 1: Example of causality relationship similarity measurement

WI-IAT ’21, December 14–17, 2021, ESSENDON, VIC, Australia

similar causality relationships in this study, we consider that the two
causality relationships represented by Landslide and Evacuation are
more similar to each other than the causal relationships represented
by Typhoon and Evacuation. Therefore, if the causal relationshipof (a) is input, our algorithm outputs (b) as a result.
We evaluated ECM using a Wikipedia-based dataset named W2E,
which included 322 topics and 1,041 events. We confirmed that ECM
is the best algorithm in terms of MAP, precision, recall, and 𝐹 1 -scorecompared with baselines.
The remainder of this paper is organized as follows. We present
the definitions in Section 2 and the related work in Section 3. In Section 4, we describe the proposed algorithm. Section 5 presents theresults of the experimental evaluation. The last section concludes
the paper and describes future work.

2 DEFINITIONS
2.1 Event and Causal relationshipWe define an event as a text of a single event. This means that events
that include multiple events, such as World War I and World War
II, are excluded. We also define a causal relationship as a collectionof two or more events. Within this collection, we assume that theentire sequence can be defined in terms of the time series when
events occur. For example, if we consider this definition using WorldWar II, World War II can be regarded as a representation of a causal
relationship and the events include the attack on Pearl Harbor and
the Potsdam Declaration.

2.2

Bipartite Graph

Let 𝐺 = (𝐴, 𝐵, 𝐸) be the bipartite graph where 𝐴 and 𝐵 are twonode sets and 𝐸 is an edge set. Each node of 𝐴 and 𝐵 represents anevent. Weight of an edge (𝑎𝑖 , 𝑏𝑖 ) where 𝑎𝑖 ∈ 𝐴, 𝑏𝑖 ∈ 𝐵 represents
the similarity between events of the nodes 𝑎𝑖 and 𝑏𝑖 .

2.3

Sumikawa and Ikejiri extended this study from single-label classification to multi-label classification [17]. These studies propose
classification frameworks rather than search algorithms.
Several studies have proposed event detection methods basedon texts. The method proposed by Manaskasemsak et al. detected
emerging events from Twitter [13]. This method first identifies
events by grouping similar tweets on a tweet graph whose nodes
and edges represent tweets and their similarities. If the events areclassified as trend lines, the method regards them as emerging
events. The purpose of this study was to identify events instead of
measuring the similarity between several events.

3.2

Causal Relationship Extraction

Causal relationships extraction is one of the most widely studied
research topics. The problems that have been addressed in previous
studies can be broadly divided into two categories: learning causal
effects and learning causal relations [5]. Focusing on research using
event texts, studies have been conducted to learn causal relationships from past events to predict possible future events. Radinsky
and Davidovich proposed an algorithm to predict possible future
events after mining causal relationship [15]. This algorithm firstextracts causal relationships from the descriptions of past events.
It then calculates the probability that an event will occur in thenear future. As a causal relationship includes several events, causal
relationship extraction is a task of topic detection and tracking.
Looking at topic detection and tracking studies, there are methods
to detect hot events from online news streams and track hot events[14], detect global hot events and local hot events using local community detection mechanisms [20], and reporting real-life events
to users in the human-readable form [12].
These studies as well as our study focus on the causal relationship between events; however, our algorithm assumes that thecausal relationship between events is already given and uses causal
relationships to measure the similarity between events.

Ordered Bipartite Graph

An ordered bipartite graph 𝐺 ′ defines the total order in two nodesets 𝐴 and 𝐵. That is, it defines the total order for all the subscripts
𝑖, 𝑗 of 𝑎𝑖 , 𝑎 𝑗 ∈ 𝐴.

2.4

Y. Sumikawa

Maximum Weight Matching

For a given graph 𝐺, matching is an edge set 𝑀 ⊂ 𝐸 that does
not share any nodes. Maximum weight matching is the problem offinding the highest sum of weights 𝑀 ′ ∈ 𝑀 of the edges selected
as 𝑀.

3 RELATED WORK
3.1 Event Classification and Detection
One of the most studied research in analyzing event texts is classification. Kosmerlj et al. proposed event categories that were originally defined by Wikipedia editors, and then investigated automaticclassification using Term frequency-inverse document frequency(TF-IDF) model created from news articles [10]. This study uses
whole news article texts; however, several events are referred to in
texts with several words. Sumikawa and Jatowt proposed a feature
selection method for classifing short documents of past events [18].

4ECM ALGORITHM

In this section, we first describe the theory of ECM solving our
maximum weight matching problem. We then describe dynamic
programming that solves this problem.

4.1

TheoryIn this study, we add a constraint with no intersection points on theedges that are the solutions to the problem to the general maximum
weight matching problem. We assume that the graph is defined in aflat space. Fig. 2 shows the solutions obtained by solving the generalmaximum weight matching problem and the extended problem ofthis study. In the figure, the blue and red edges indicate the solutionsof the general and extended maximum weight matching problem,
respectively. Green edges represent the solutions shared by the two
problems. Looking at the 𝑎 1 , the node has two connected edges.
The weight of the edge that is also connected to 𝑏 4 is higher thanthat of the other edge; thus, the blue edge is chosen as the solution
in the general maximum weight matching. However, because it has
intersections with the edges (𝑎 2 , 𝑏 2 ) and (𝑎 3 , 𝑏 3 ), it is not chosen as
the solution in this study, and the other edge (𝑎 1 , 𝑏 1 ) is chosen as
the solution.

Event Causal Relationship Retrieval

WI-IAT ’21, December 14–17, 2021, ESSENDON, VIC, Australia

2

b1

a1

b1

10

b2

a2

bj

b3

ʀ
ʀ
ʀ

a1

a2
1

a3

ʀ
ʀ
ʀ

ai

4

b|B|-1b4

ʀʀʀFigure 2: Example of solution difference between the general maximum weight matching problem and proposed
problem in this study.

a|A|
4.1.1 Ordered Bipartite Graph Construction. We assume that allnodes 𝑁 are given before applying ECM. In addition, the given
nodes are already divided into sub-sets respecting causal relationships and indexed respecting their chronological order about when
their corresponding events occurred. For example, if an event 𝑎 1
causes another event 𝑎 2 , then two nodes 𝑎 1 and 𝑎 2 are defined andgrouped in the same node set 𝐴.
We construct the ordered bipartite graph 𝐺 = (𝐴, 𝐵) with thegiven node sets. To define edges, the algorithm uses the similarity
between events corresponding to the nodes taken from each set of
𝐴 and 𝐵 as weights of their edges.
4.1.2 Solving Proposed Maximum Weight Matching Problem on
Ordered Bipartite Graph. The intuitive idea is that ECM measuressimilarity in the order when events have occurred from the past
towards the present on the bipartite graph that represents the causal
relationships as defined in Section 4.1.1.
Let 𝑒 = (𝑎𝑖 , 𝑏 𝑗 ) and 𝑒 ′ = (𝑎𝑘 , 𝑏𝑙 ) be the edges that are includedin the solution (𝑒 ≠ 𝑒 ′ ). In this case, we define the constraint nointersection points on the edges that are the solutions of the problem
as follows.
• If 𝑘 < 𝑖, then 𝑙 < 𝑗.
• If 𝑙 < 𝑗, then 𝑘 < 𝑖.
The ECM selects edges that are candidates for the solution one
by one in order from the one with the smallest index and calculates
the sum of the weights of all the edges selected as the solution. It
then chooses the edge set that maximizes the sum.

4.2

Implementation

In the remainder of this section, we describe the implementationof ECM as a dynamic programming solver. First, we explain how
to fill a basic table in dynamic programming, and then present a
detailed algorithm.
Figs. 3 and 4 show a graph and a table of an example of how
to solve the constrained maximum weight matching problem onb|B|

Figure 3: Example solutions of the proposed maximum
weight matching problem

1

2

3

ʞ

j

ʞ

|B|

1

70

66

99

57

56

76

94

2

2

18

73

10

82

69

3

3

27

26

13

96

79

89

22

ʞ

58

85

54

38

46

67

30

i

8

55

14

78

ʞ
|A|

Figure 4: Dynamic programming solver

bipartite graphs by dynamic programming. The two figures color
the edges/cells green, red, and blue if they are already analyzed,
are currently being analyzed, and will be analyzed in the future,
respectively. As the implementation is dynamic programming, thealgorithm uses a table DP to record the sum of the weights ofthe selected edges. In addition, ECM records all the weights ofthe edges in a table 𝑊 . ECM analyzes the nodes in 𝐴 and 𝐵 of abipartite graph 𝐺 = (𝐴, 𝐵) in ascending index order. If the edge
currently being analyzed is selected as the solution, the sum of theweights is memorized in the table DP in addition to the set of edges
previously selected as the solution. In other words, as shown by
the arrows in Fig. 4, the weights of the selected edges from thegreen area are transferred to the red cells, and the edge with thehighest value is finally selected as the solution. If the edge selected
as one of the solutions is (𝑎𝑖 , 𝑏𝑖 ), the algorithm then excludes all

WI-IAT ’21, December 14–17, 2021, ESSENDON, VIC, Australia

b1

b2

b3

b4

a1

2

0

0

4

a2

0

10

0

0

a3

0

0

1

0

Y. Sumikawa

(a) W

0

0

0

0

0

0

2

2

2

6

0

2

12

12

12

0

2

12

13

13

(b) DP

Figure 5: Solutions of Fig. 3 solved by dynamic programming

cells corresponding edges connected 𝑎𝑖 or 𝑏𝑖 other than the cell of(𝑎𝑖 , 𝑏𝑖 ) from subsequent analysis such that they cannot be selected
as solutions. The ECM repeats this process until all the cells in thetable are filled with values.
Fig. 5 shows the two tables 𝑊 and DP, which record all theweights of the edges and the sum of the weights of the selectededges, respectively, that are created in this algorithm for Fig. 2. If
there is no edge on the ordered bipartite graph, 0 is recorded in
𝑊 . ECM records a value to the table DP by adding the highest of
the three values from the left, upper left, and upper right of thetable DP and the value of 𝑊 corresponding to the current cell. This
process is performed until all the cells have recorded their values.
As a result, the sum of the weights of the edge set selected by thismethod can be recorded in the lower right corner of the table DP,
and the actual edge set is obtained by scanning its component edges
in the reverse direction.
In the following, we present the formal definitions of ECM. Let
𝑊 be a matrix whose elements are the weights of each edge of the
bipartite graph 𝐺 = (𝐴, 𝐵). That is, using the function weight that
returns the weight of the edge given as the argument, we define eachelement of 𝑊 as 𝑊𝑖,𝑗 = weight (𝑒 (𝑎𝑖 , 𝑏 𝑗 )) for any 𝑒𝑎𝑖 ∈ 𝐴, 𝑒𝑏 𝑗 ∈ 𝐵.
We then consider the process of recording values to table DP.
Let 𝑇𝑊𝑖 𝑗 be a total weight by adding the weight of 𝑒 (𝑎𝑖 , 𝑏 𝑗 ) and thesolution edges whose indexes are from (0, 0) to (𝑖 − 1, 𝑗 − 1). From
the definition of Section 4.1.2, 𝑇𝑊𝑖 𝑗 is larger than the total weightsof the other edges connected to 𝑎𝑖 or 𝑏 𝑗 selected as solutions. This isbecause the indexes of the nodes connected to the edges previouslychosen as solutions are less than 𝑖 and 𝑗, respectively. Thus, if theedge 𝑒 (𝑎𝑖 , 𝑏 𝑗 ) is selected as the solution, the result of adding 𝑊𝑖,𝑗
to DP 𝑖−1,𝑗−1 should be larger than DP 𝑖,𝑗−1 or DP 𝑖−1,𝑗 ; otherwise,
the value is larger than the case where 𝑒 (𝑎𝑖 , 𝑏 𝑗 ) is not the solution.
The formal equation of this idea is as follows:
DP 𝑖,𝑗 = max (DP 𝑖−1,𝑗−1 + 𝑊𝑖,𝑗 , DP 𝑖−1,𝑗 , DP 𝑖,𝑗−1 ) + W𝑖,𝑗(1)

Algorithm 1 ECM implemented as dynamic programming
Input: A weighted matrix 𝑊 , tables DP and rmax
Output: A set of edge SubE
1: Function ECM (𝑊 , DP, rmax)
2:// Table calculation
3:
for 𝑖 = 1 to ColumnSize(𝑊 )4:for 𝑗 = 1 to RowSize(𝑊 )5:prev_max ← Val(rmax𝑖−1,𝑗−1 )6:
DP 𝑖,𝑗 ← prev_max + 𝑊𝑖,𝑗7:
rmax𝑖,𝑗 ← tuple_val_max (rmax𝑖−1,𝑗 , rmax𝑖,𝑗−1 )8:
if DP 𝑖,𝑗 > val(rmax𝑖,𝑗 )9:rmax𝑖,𝑗 ← (DP 𝑖,𝑗 , (𝑖, 𝑗))
10:
end if
11:
end for12:
end for13:// Solution determination
14: 𝑖, 𝑗 ← ColumnSize(𝑊 ), RowSize(𝑊 )15:SubE ← ∅16:
while 𝑖 ≠ −1 and 𝑗 ≠ −1
17:
SubE.append(𝑒𝑖,𝑗 )18:
𝑖, 𝑗 ← Index (rmax𝑖−1,𝑗−1 )19:
end while
20:
return SubE
Algorithm1 shows the ECM algorithm1 . ECM assumes that table
DP is initialized with all the components of the first row and firstcolumn as 0. ECM also uses table rmax to record the edges as
solutions while filling in table DP. rmax comprises a pair of a weightvalue of the edge to be solved and an index index of the connected
nodes.
The 2nd∼12th lines record the calculation results of Eq. 1 ineach component of the table DP. ColumnSize (3rd line) is a functionthat returns the number of rows in the table of arguments. The
function RowSize (4th line) returns the number of columns in thetable of arguments. Looking at the 5th line, the Val function returns
a value from a pair of values and subscripts given as arguments. The
tuple_val_max on line 7 is a function that returns the largest value
among the pairs of values and subscripts given as arguments. The
function Index on line 18 returns indexes from a pair of the value
and index given as arguments. During the filling DP, the algorithm
records the subscripts of the selected edges as the solution in rmax.
Because the indexes of the edges to be selected as solutions arearranged in ascending order, we can obtain the edge set requiredby this method by tracing the subscripts of rmax in reverse order,
as shown in lines 13–19.
Computational complexity. Because the DP matrix and rmax
can be calculated simultaneously, each DP 𝑖,𝑗 and rmax𝑖,𝑗 can beobtained in constant time. In other words, the time calculation is
𝑂 (|𝐴||𝐵|). On the other hand, the spatial computation is 𝑂 (|𝐴||𝐵|)
because the table size is determined by the number of nodes.
Theory. ECM obtains the optimum solution for 𝑆,𝑇 ∈ N.
Proof. We prove that the algorithm obtains the optimal result bymathematical induction on the number of vertices of the bipartite
graph 𝐺 = (𝐴, 𝐵).
1 The source code is available on our project repository: https://github.com/sumilab/programs/tree/

master/ecm

Event Causal Relationship Retrieval

WI-IAT ’21, December 14–17, 2021, ESSENDON, VIC, Australia

Table 1: Example of test dataset. The first column represents topic categories of the second and forth columns. The second
column is the topic ID of the third column’s topic in W2E dataset. The forth and fifth columns are results of ECM if the thirdcolumn’s topic. Due to space limitations, some sentences and events are omitted.
Cat.

TOPIC IDPE

TOPIC-896

Event texts
2016-07-14 Elizabeth Truss is named Secretaryof State for Justice and first ever female Lord
Chancellor of the United Kingdom as former
chancellor Michael Gove is ousted from the cabinet.
2016-07-13 The new Prime Minister of theUnited Kingdom Theresa May begins forming
her ministry following the end of the Second
Cameron ministry.

TOPIC ID
TOPIC-1780

Event texts
2016-06-29 The process to elect a new leaderof the Conservative Party to replace outgoing
Prime Minister David Cameron begins in the
United Kingdom.
2016-07-11 Prime Minister David Cameron announces he will step down on Wednesday, July13.
2016-06-30 Former Mayor of London Boris Johnson rules himself out of running in the Toryleadership contest, a move believed to be influenced by Michael Gove’s announcement earlier
in the day to run for the leadership.
2016-07-05 Home Secretary Theresa May gets
165 votes after the first ballot of Conservative
members of parliament to select a new Leader
and the next Prime Minister.

S

TOPIC-1534

2016-09-10 In tennis, German Angelique Kerber
defeats Czech Karolína Plíšková in three sets to
win the 2016 US Open women’s singles title.

2016-09-11 In tennis, Swiss Stan Wawrinka defeats Serbian Novak Djokovic in four sets toclaim the 2016 US Open men’s

Base case: When |𝐴| = |𝐵| = 1, the DP is DP 1,1 . This indicatesthat the solution is to use only the edge (1, 1). It is trivial to use theedge as the solution. Therefore, ECM obtains the optimal result for|𝐴| = |𝐵| = 1.
Induction step: Let 𝑆,𝑇 ∈ N be given and suppose ECM obtains
the optimal result for 𝑆 = |𝐴|,𝑇 = |𝐵|. Consider the case of |𝐴| =𝑆 + 1. We consider how to find the optimal solution when any edge
connected to the node 𝐴𝑆+1 is selected as the bottom side. At thistime, the optimal solution must already be found for all the edges
above the selected edge. From the condition, the optimal solution
has already been found for all edges except the edge connected to
the node 𝐴𝑆+1 . Moreover, the other edges connected to node 𝐴𝑆+1
are not the upper edges of the selected edge. Therefore, because
the optimal solution is found for all the edges above the selectededge, the optimal solution may be found even when |𝐴| = 𝑆 + 1.
The optimum solution can be obtained for |𝐵| = 𝑇 + 1 in thesame way.

TOPIC-1996

2016-01-31 In tennis, defending champion Novak Djokovic of Serbia defeats second seed
Andy Murray of the United Kingdom in the
men’s singles in straight sets. It is Djokovic’s
third straight Grand Slam title.
2016-01-30 In tennis, Angelique Kerber of Germany tops (2–1) defending champion Serena
Williams of the United States, 6-4, 3–6, 6–4, to
win the Women’s Singles. This is Kerber’s first
Grand Slam title.

5 EXPERIMENTAL EVALUATIONS
5.1 Experimental setting
5.1.1 Dataset. We used the W2E dataset [6] that contains events
listed as a topic in this evaluation. The W2E dataset contains 3,083
topics consisting of 5,160 events recorded in Wikipedia’s current
event portal as of 2016. The events in the W2E dataset were collectedfrom 10 categories of events, including the US presidential election,
UK’s European Union membership referendum, Middle East wars,
Summer Olympics, and disasters in North America. These eventswere manually aggregated with multiple related events as topics.
In addition, each topic has one of the following 10 categories: Sport(S), Armed conflicts and attacks (AA), Business and economy (BE),Science and technology (ST), Arts and culture (AC), Law and crime(LC), Politics and elections (PE), International relations (IR), Disasters and accidents (DA), and Health and medicine (HM). Tab. 1
shows examples of W2E dataset topic categories, topics, and theirevents.
As some W2E topics contain only one event, we used topics formore than one event to construct the bipartite graph in this study.
Furthermore, we prepared pairs of similar topics before performing

WI-IAT ’21, December 14–17, 2021, ESSENDON, VIC, Australia

Y. Sumikawa

Table 2: Statistics of test dataset.
Num. of events
Ave. num. of tokens
Num. of topics
Ave. num. of events per topic

Table 4: Similarity scores for feature creation. ”-“ indicatesthat no results were obtained correctly. The bold-faced numbers indicate the best for a particular term.

1,041
31.79
322
3.23

CosSim𝐸𝑢𝑐𝑙𝑖𝑑𝐽𝑆

Table 3: Statistics of test dataset by category.

Ave. Num. of events
Num. of topics
Ave. Num. of tokens
Ave. Num. of events
Num. of topics
Ave. Num. of tokens

S
2.92
13
29.44
LC
3.06
32
34.53

AA
3.26
73
27.15
PE
3.14
84
31.87

BE
3.85
7
34.59
IR
3.43
57
38.20

ST
2.0
2
23.25
DA
3.11
45
29.54

AC
2.66
3
34.37
HM
4.66
6
28.25

the experimental evaluation2 . Two volunteers were asked if thepairs were similar or not. If both of them agreed that the pairs weresimilar to each other, we maintained them; otherwise, we discarded
them. Tab. 2 shows the statistics of the subset of the W2E dataset
used in this evaluation. In addition, Tab. 3 shows the statistics by
topic category.
5.1.2 Baselines. We compare ECM with the following two methods.
• BM25: Okapi BM25 [16] is a widely used ranking functionthat ranks a set of documents based on the query terms
appearing in each document.
• TF-IDF + dynamic time warping (DTW): DTW measures thesimilarity between time series data by finding the distance
between each point of the two-time series in a brute force
fashion and then finding the path where the two-time series
are shortest after finding all of them.
TF-IDF indicates the importance of a word to a document in
the dataset. This score is a multiplication of the term frequency
and inverse document frequency. Term frequency refers to how
frequently each term (word) occurs in each document whereas
the inverse document frequency represents how rarely each term
occurs in all documents. The formal definition is as follows.
|D|
TFIDF (w, d, D) = tf 𝑤,𝑑 ∗(2)| {𝑑 ′ ∈ D | 𝑤 ∈ 𝑑 ′ } |where tf 𝑤,𝑑 is the number of times a word 𝑤 occurs in a document𝑑, and | • | is the size of •. The second term of this equation gives
the number of all labeled data divided with labeled data including𝑤.
5.1.3 Evaluation Criteria. In this paper, we evaluate the aforementioned algorithms and ECM by mean average precision (MAP),
precision (𝑃), recall (𝑅), and F1-score (𝐹 1 ). The MAP is calculated
by considering the mean AverageP, which averages precision at
K (ap@K) indicating precision among the top K documents. The
2 The dataset is available in http://www.ysumi.sakura.ne.jp/sim_event_causalities.csv

TF-IDF
59.8%
17.7%
14.0%

LSA
48.8%
11.2%
-

LDA
26.4%
20.2%
17.7%

Doc2Vec
14.3%
15.0%
-

formal equation of average precision is defined as follows:𝑘

Precision(k)=AverageP

=

1Õ
𝑟𝑖
𝑘 𝑖
1 Õ
| D𝑡 |(3)
𝑟𝑘 Precision(k)

(4)

𝑘<𝑁

where 𝑟𝑖 represents whether the prediction is correct or not using
1 (correct) or 0 (wrong), D 𝑡 is a set of test data and 𝑁 is the last
rank where a classifier assigns a correct label to the test data.
To calculate 𝑃, 𝑅, and 𝐹 1 scores, we use only k = 1, which represents the highest score of the results of applying each searchalgorithm.

5.2

Results

5.2.1 Bipartite graph creation. We first analyze feature vector creation and the measurement of similarity between the two vectorsthat are necessary to build a bipartite graph.
Q. Which feature vector construction method and similarity
evaluation method should be used to construct a bipartite
graph to apply ECM?
A. The combination of TF-IDF and cosine similarity is thebest.
To create feature vectors, we used TF-IDF, latent semantic analysis (LSA) [3], latent Dirichlet allocation (LDA) [2], and Doc2Vec[11], which capture latent semantic text structures. LSA performs amatrix decomposition on the term-document matrix whereas LDA
is a probabilistic model assuming a Dirichlet prior over the latent
topics. Doc2Vec is a neural network-based algorithm.
Pairwise similarities of events are then computed using the cosine similarity (CosSim), Euclidean distance (𝐸𝑢𝑐𝑙𝑖𝑑), and JensenShannon divergence (𝐽𝑆).
Tab. 4 shows the evaluation result of 𝑃 (precision) for bipartite
graph construction. These scores are the results of ECM indicatingthat each score represents the difference in how to build a bipartite
graph whereas the topic search algorithm by dynamic programmingis the same. From this result, we can observe that using TF-IDF
and cosine similarity is the best for the graph construction. In
the following, we use only the two methods for bipartite graphconstruction.
5.2.2 Retrieval results. In the remainder of this section, we analyze
the retrieval results of the three algorithms.

Event Causal Relationship Retrieval

WI-IAT ’21, December 14–17, 2021, ESSENDON, VIC, Australia

Table 5: Evaluation results. The bold-faced numbers indicate
the best for a particular term given the metric.
BM25
DTW
ECM

MAP
33.1%
54.4%
62.5%

𝑃
25.8%
49.4%
59.8%

𝑅
25.8%
49.4%
59.8%

𝐹1
25.8%
49.4%
59.8%

T
r
u
e

Table 6: Correct retrieval results by ECM.

Num. of correct results
Ratio
Num. of correct results
Ratio
Num. of correct results
Ratio

S
8
61.54%
AC
0
0.00%
DA
26
57.78%

AA
46
63.01%
LC7
21.88%
HM
6
100.00%BE
342.86%
PE56
66.67%

ST
1
50.00%
IR35
61.40%Q. Which is the best search algorithm among BM25, DTW,
and ECM?
A. ECM is the best.
Tab. 5 shows the results for the three algorithms. The results
showed that the proposed algorithm obtained the best result. It
also shows that the order of events is important to consider whenevaluating the similarity between events when considering causal
relationships because all scores of the BM25 were the lowest among
the three algorithms.

5.3

Error Analysis

In the following section, we discuss the results of analyzing only
the proposed algorithm. In addition, we focus on the case of k = 1,
which represents the result that the ECM is the most similar to thequery.
Q. Which category ECM searched most correctly?
A. All HM topics obtained the correct results. In addition,over 60% of the topics in the PE, AA, S, and IR categories
yielded correct results.
At the beginning, we analyze the distribution of topic categories
for which ECM has achieved correct results. This counts the numberof matches between the categories of the topic given as the input
and output by the ECM as k=1.
Tab. 6 shows the results. First, we can observe that ECM obtained
the correct results for all topics in HM. PE, AA, S, and IR also
yielded good results because more than 60% of the topics in theircategories obtained correct results. However, many topics in AC
and LC have missed obtaining correct results.

OutputFigure 6: ECM wrong retrieving results

Q. Which category of topics was wrongly predicted for eachcategory topic?
A1. PE topics were often misjudged as AA.
A2. LC topics were often misjudged as AA or DA.
Next, we analyze the results that the ECM wrongly determined
to be the most similar. This counts which category the expected
result topic category is wrong with.
Fig. 6 shows the results. In this figure, each row represents the
expected result’s topic category whereas each column indicates the
topic category that resulted as the most similar.
As shown in the results, we can see that topics of PE were
often misjudged as topics of AA. One possible reason for this misjudgment is that the number of topics in AA is the second largest
number of topics. Compared with the number of topics between AA
and others excluding PE, AA has approximately 2∼37 times more
topics than other categories. In addition, LC is often misjudged aseither AA or DA. We discuss this point in the following analysis.
Q. Why were the results of AC and LC weak?
A1. LC topics tend to have relatively higher values of mutual information than topics in other categories.
A2. In AC and LC categories, the Jaccard coefficient scores
between topics in each category are lower than the average.
Next, we explore why ECM obtained the wrong results for many
topics in AC and LC. We first analyze the similarity of the topics
using the Jaccard coefficient and mutual information (MI). The
Jaccard coefficient counts the number of words shared between the
two texts. MI measures the mutual dependence between the two
texts. Their formal definitions are as follows:
Jaccard (𝐴, 𝐵)=

𝑀𝐼 (𝐴, 𝐵)=| 𝑇𝐴 ∩ 𝑇𝐵 || 𝑇𝐴 ∪ 𝑇𝐵 |ÕÕ𝑝 (𝑎, 𝑏)𝑝 (𝑎, 𝑏) log
𝑝 (𝑎)𝑝 (𝑏)

(5)
(6)

𝑎 ∈𝐴𝑏 ∈𝐵

where: | · | is the size of the set and 𝑇𝐴 and 𝑇𝐵 are the tokens
included in category 𝐴 and 𝐵, respectively. The higher the score of
the measurements, the more correlated they are.

WI-IAT ’21, December 14–17, 2021, ESSENDON, VIC, Australia

Y. Sumikawa

0.080
S
AA

0.075

BE

0.070

ST

0.065

AC
0.060

LC
PE

0.055

IR

0.050

DA
0.045
HM
S AA BE ST AC LC PE IR DA HM

Figure 7: Topic similarity by Jaccard coefficient between categories
0.0200SAA

0.0175BE

0.0150ST

0.0125AC

0.0100LC
0.0075PE
0.0050IR

0.0025DA
HM

0.0000S AA BE ST AC LC PE IR DA HM

Figure 8: Correlation measure using Mutual Information between topics of different categories
Table 7: Topic similarity in the same category.
Jaccard
MI
Jaccard
MI

S
0.11
0.10
LC
0.10
0.09

AA
0.11
0.10
PE
0.12
0.13

BE
0.09
0.11
IR
0.10
0.10

ST
0.19
0.27
DA
0.13
0.13

AC
0.08
0.05
HM
0.13
0.10

Total
0.12
0.12

Figs. 7 and 8 show Jaccard coefficients and MI scores between
topics in different categories. As shown in Fig. 8, LC topics tend tohave relatively higher values of mutual information between AA
and DA. This is probably the reason why several LC topics were
misjudged as topics in the two categories.
Next, Tab. 7 shows the Jaccard coefficient and MI scores of the
topics in the same category. We can observe that both AC and
LC are smaller than the overall average value in both scores; inparticular, the MI scores of AC are the lowest among all categories.
These results indicate that news descriptions in category AC rarely
share the same words.

6

CONCLUSIONSIn this paper, we proposed an algorithm for measuring the similarity between events focusing on causal relationships. The algorithm

solves a maximum weight matching problem with a novel constraint in which the edges that are solutions do not intersect on
a bipartite graph whose nodes and edges represent events andtheir similarity, respectively. We implemented this algorithm andcompared it to previous studies. We confirmed that the proposed
algorithm obtained the best results.
There are three possible directions for future works. The first is
to implement a search engine using this algorithm. The second is togeneralize the problem by using causal relationships expressed in atree structure. The third is to evaluate how this algorithm enhances
the historical analogy of learners.
Acknowledgements. This work was supported in part by MEXT
Grant-in-Aids (#19K20631).

REFERENCES[1] Robert P. Abelson and Ariel Levi. 1985. Decision Making and Decision Theory,
Handbook of Social Psychology. 231–309.
[2] David M. Blei, Andrew Y. Ng, and Michael I. Jordan. 2003. Latent Dirichlet
Allocation. J. Mach. Learn. Res. 3 (March 2003), 993–1022.
[3] Scott Deerwester, Susan T. Dumais, George W. Furnas, Landauer Thomas K., andRichard Harshman. 1990. Indexing by latent semantic analysis. Journal of theAmerican Society for Information Science 41, 6 (1990), 391–407.
[4] Thomas Gilovich. 1981. Seeing the Past in the Present: The Effect of Associations
to Familiar Events on Judgments and Decisions. Journal of Personality and Social
Psychology 40, 5 (1981), 797.
[5] Ruocheng Guo, Lu Cheng, Jundong Li, P. Richard Hahn, and Huan Liu. 2020. A
Survey of Learning Causality with Data: Problems and Methods. ACM Comput.
Surv. 53, 4, Article 75 (July 2020), 37 pages.
[6] Tuan-Anh Hoang, Khoi Duy Vo, and Wolfgang Nejdl. 2018. W2E: A WorldwideEvent Benchmark Dataset for Topic Detection and Tracking. In Proceedings of the27th ACM International Conference on Information and Knowledge Management(Torino, Italy) (CIKM ’18). Association for Computing Machinery, New York, NY,
USA, 1847–1850.
[7] Ryohei Ikejiri. 2011. Designing and Evaluating the Card Game which Fosters theAbility to Apply the Historical Causal Relation to the Modern Problems. Japan
Society for Educational Technology 34, 4 (april 2011), 375–386. (in Japanese).
[8] Ryohei Ikejiri. 2011. Rekishi no ingakankei wo gendai ni ouyou suru tikara
wo ikusei suru ka-do ge-mu kyouzai no dezain to hyouka. Japan Society for
Educational Technology 34, 4 (2011), 375–386.
[9] Ryohei Ikejiri and Yasunobu Sumikawa. 2016. Developing World History Lessons
to Foster Authentic Social Participation. Journal of educational research on social
studies 84 (July 2016), 37–48.
[10] Aljaž Košmerlj, Evgenia Belyaeva, Gregor Leban, Marko Grobelnik, and Blaž Fortuna. 2015. Towards a Complete Event Type Taxonomy (WWW ’15 Companion).
ACM, New York, NY, USA, 899–902.
[11] Quoc Le and Tomas Mikolov. 2014. Distributed Representations of Sentences
and Documents, Vol. 32. ICML’14, Bejing, China, 1188–1196.
[12] Zhen Lei, Ling-da Wu, Ying Zhang, and Yu-chi Liu. 2005. A System for Detecting
and Tracking Internet News Event (PCM’05). Springer-Verlag, Berlin, Heidelberg,
754–764.
[13] Bundit Manaskasemsak, Bodin Chinthanet, and Arnon Rungsawang. 2016. Graph
Clustering-Based Emerging Event Detection from Twitter Data Stream (ICNCC’16). ACM, New York, NY, USA, 37–41.
[14] Yajie Qi, Li Zhou, Huayou Si, Jian Wan, and Ting Jin. 2017. An Approach to News
Event Detection and Tracking Based on Stream of Online News, Vol. 2. 193–196.
[15] Kira Radinsky and Sagie Davidovich. 2012. Learning to Predict from Textual
Data. J. Artif. Int. Res. 45, 1 (Sept. 2012), 641–684.
[16] Stephen Robertson, S. Walker, S. Jones, M. M. Hancock-Beaulieu, and M. Gatford.
1995. Okapi at TREC-3. In Overview of the Third Text REtrieval Conference (TREC3). Gaithersburg, MD: NIST, 109–126.
[17] Yasunobu Sumikawa and Ryohei Ikejiri. 2021. Feature selection for classifying
multi-labeled past events. Int. J. Digit. Libr. 22, 1 (2021), 63–83.
[18] Yasunobu Sumikawa and Adam Jatowt. 2018. Classifying Short Descriptions of
Past Events (ECIR ’18). Springer International Publishing, 729–736.
[19] Yasunobu Sumikawa and Adam Jatowt. 2018. System for Category-driven Retrieval of Historical Events (JCDL ’18). ACM, New York, NY, USA, 413–414.
[20] Zhicong Tan, Peng Zhang, Jianlong Tan, and Li Guo. 2014. A Multi-layer Event
Detection Algorithm for Detecting Global and Local Hot Events in Social Networks. Procedia Computer Science 29 (2014), 2080–2089. 2014 International
Conference on Computational Science.