# Event Causality Identification with Causal News Corpus
\- Shared Task 3, CASE 2022

Fiona Anting Tan
Institute of Data
Science, National
University of Singapore,
Singapore
<EMAIL_ADDRESS>
Hansi Hettiarachchi
School of Computing and Digital
Technology, Birmingham City
University, United Kingdom
hansi.hettiarachchi
@mail.bcu.ac.uk
Ali Hürriyetoğlu
KNAW Humanities
Cluster DHLab,
The Netherlands
ali.hurriyetoglu
@dh.huc.knaw.nl
Tommaso Caselli
CLCG,
University of Groningen,
The Netherlands
<EMAIL_ADDRESS>
Onur Uca
Department of Sociology,
Mersin University,
Turkey
<EMAIL_ADDRESS>
Farhana Ferdousi Liza
School of Computing Sciences,
University of East Anglia,
United Kingdom
<EMAIL_ADDRESS>
Nelleke Oostdijk
Centre for Language Studies,
Radboud University, The Netherlands
<EMAIL_ADDRESS>

###### Abstract

The Event Causality Identification Shared Task of CASE 2022 involved two
subtasks working on the Causal News Corpus. Subtask 1 required participants to
predict if a sentence contains a causal relation or not. This is a supervised
binary classification task. Subtask 2 required participants to identify the
Cause, Effect and Signal spans per causal sentence. This could be seen as a
supervised sequence labeling task. For both subtasks, participants uploaded
their predictions for a held-out test set, and ranking was done based on
binary F1 and macro F1 scores for Subtask 1 and 2, respectively. This paper
summarizes the work of the 17 teams that submitted their results to our
competition and 12 system description papers that were received. The best F1
scores achieved for Subtask 1 and 2 were 86.19% and 54.15%, respectively. All
the top-performing approaches involved pre-trained language models fine-tuned
to the targeted task. We further discuss these approaches and analyze errors
across participants’ systems in this paper.

##  1 Introduction

A causal relation represents a semantic relationship between a Cause argument
and an Effect argument, in which the occurrence of the Cause leads to the
occurrence of the Effect (Barik et al., 2016). Extracting causal information
from text has many downstream natural language processing (NLP) applications,
for summarization and prediction Radinsky et al. (2012); Radinsky and Horvitz
(2013); Izumi et al. (2021); Hashimoto et al. (2014), question answering Dalal
et al. (2021); Hassanzadeh et al. (2019); Stasaski et al. (2021), inference
and understanding Jo et al. (2021); Dunietz et al. (2020).

However, data for causal text mining is limited (Asghar, 2016; Xu et al.,
2020; Yang et al., 2022; Tan et al., 2021, 2022a). There are also not many
benchmarks to allow for fair model comparisons Asghar (2016). Therefore, in
this paper, we continue our efforts with the creation of the Causal News
Corpus (CNC). CNC is a corpus of news articles annotated with causal
information suitable for causal text mining. Additionally, we introduce a
shared task to promote modelling for two causal text mining tasks: (1) Causal
Event Classification and (2) Cause-Effect-Signal Span Detection. Figure 1
provides examples from the CNC in this shared task. To our knowledge, we are
the first dedicated causal text mining dataset and benchmark to include signal
span detection as an objective.

Figure 1: Examples from the CNC for the two subtasks. Cause spans are
indicated by Pink, while Effect spans are indicated by Green. Signals, if
present, are underlined.

The rest of the paper is organized as follows: Section 2 presents literature
on event causality datasets. Section 3 describes the dataset and annotation of
the corpus. Section 4 formally introduces the two subtasks for the shared
task. Section 5 describes the evaluation metrics and competition set-up.
Subsequently, Section 6 summarizes the methods used by participants during the
competition, while Section 7 analyzes the participants’ submissions. Finally,
Section 8 concludes this paper.

##  2 Related Work

In many papers about Event Causality Identification (ECI) (Gao et al., 2019;
Zuo et al., 2021b; Cao et al., 2021; Zuo et al., 2021a, 2020), the two
datasets used for benchmarking are CausalTimeBank Mirza et al. (2014); Mirza
and Tonelli (2014) and EventStoryLine Caselli and Vossen (2017). These
datasets are unsuitable for span detection since their arguments are event
headwords only.

There are two other efforts that intentionally introduce datasets for
benchmarking causal text mining systems. FinCausal (Mariko et al., 2021, 2020)
is a recurring shared task held within the FinNLP workshop focusing on
financial news. In the first subtask, participants also aim to identify if
sentences contain causal relations. In the second subtask, participants to
identify the Cause and Effect spans in the causal sentences. UniCausal Tan et
al. (2022b)111https://github.com/tanfiona/UniCausal is an open-source
repository for causal text mining that has consolidated six corpora for three
causal text mining tasks. The six corpora included in UniCausal are: AltLex
Hidey and McKeown (2016), BECAUSE 2.0 Dunietz et al. (2017), CausalTimeBank
Mirza et al. (2014); Mirza and Tonelli (2014), EventStoryLine V1.0 Caselli and
Vossen (2017), Penn Discourse Treebank V3.0 Webber et al. (2019), and SemEval
2010 Task 8 Hendrickx et al. (2010). The three tasks are: Causal Sentence
Classification, Causal Pair Classification and Cause-Effect Span Detection.

Similar to FinCausal and UniCausal, we included a signal span detection
objective. Our annotation guidelines differ slightly, in that our arguments
must contain events, and the spans are annotated in a manner that is minimally
sufficient. In general, we notice that spans from FinCausal are much longer.
Spans from UniCausal depend on the original data source.

Additionally, for Cause-Effect Span Detection in FinCausal, their approach to
handle multiple causal relations per unique sentence was to include index
numbers at the start of each sentence to differentiate the Cause-Effect
predictions. This approach is problematic because (1) it leaks information
that the sentence contains multiple causal relations to the model, and (2)
predictions that are submitted in a different order from the true labels are
unnecessarily penalised. Therefore, we differ from FinCausal when evaluating
multiple causal relations in span detection since we group relations by its
sentence index. This is described further in Section 5.1.

##  3 Dataset

###  3.1 Data Collection

Our shared task worked with the Causal News Corpus (CNC) (Tan et al.,
2022a)222https://github.com/tanfiona/CausalNewsCorpus, which consists of 869
news documents and 3,559 English sentences, annotated with causal information.
CNC builds on the randomly sampled articles Yörük et al. (2021) from multiple
sources and periods featured Hürriyetoğlu et al. (2021) in a series of
workshops directed at mining socio-political events from news articles
Hürriyetoğlu et al. (2020b, a, 2021a, 2021b); Hürriyetoğlu (2021). CNC follows
the train-test split of the original data source, with 3,248 training and 311
test examples. Later, we further split and randomly sampled 10% of the
original training set to obtain the development set. Later, Table 3 presents
the sentence counts per data split.

###  3.2 Annotation

####  3.2.1 Guidelines

For more information on our annotation guidelines, please refer to our
annotation manual333Available under the ”documentation” folder of CNC’s Github
repository..

##### Subtask 1

In CNC, sentences were labeled as _Causal_ or _Non-causal_ , where the
presence of causality indicates that “one argument provides the reason,
explanation or justification for the situation described by the other” (Webber
et al., 2019). Our sentences had to contain at least a pair of events, defined
as “things that happen or occur, or states that are valid" (Saurı et al.,
2006). These annotations correspond to the target labels for Subtask 1, Causal
Event Classification.

##### Subtask 2

For _Causal_ sentences, the words corresponding to the Cause-Effect-Signal
spans of a causal relation were also marked. These annotations correspond to
the target labels for Subtask 2, Cause-Effect-Signal Span Detection. However,
at the current stage of writing, only a small subset of our data contains
annotated spans. Span annotations are an on-going effort.

A Cause is a reason, explanation or justification that led to an Effect. We
defined a Cause or Effect span as a continuous set of words sufficient for the
interpretation of the causal relation meaning. This means that any context
modifying or describing the argument relevant to the causal relation was
included. Each Cause or Effect span must contain an event, where an event is
defined as a situation that ‘happen or occur’, or predicates that ‘describe
states or circumstances in which something obtains or holds true’ (Pustejovsky
et al., 2003).

Signals are words that help to identify the structure of the discourse. In our
case, signals highlight the relationship between the Cause and Effect.

####  3.2.2 Annotation Tool

We used the WebAnno tool (Eckart de Castilho et al., 2016) to conduct our
annotation process.

##### Subtask 1

Annotation at the sequence level was relatively straightforward, where
annotators selected “Yes" or “No" labels for each sentence.

##### Subtask 2

Figure 2: Screenshot of the annotation tool used to mark Cause-Effect-Signal
spans.

Annotators first marked the Cause span, Effect span, and Signal span.
Subsequently, they linked the spans together by pointing Cause to Effect and
Signal to Effect. An illustration is provided in Figure 2. Annotations were
then downloaded and sent through checking scripts on Python to identify if
there were any avoidable human errors. For example, if missing links (E.g. An
Effect has no Cause) or invalid links (E.g. An Effect points to Effect) were
present, and an error report was then sent to annotators for them to consider
correcting their annotations.

####  3.2.3 Annotation Process & Curation

Five annotators were involved and independently annotated for both subtasks
across the span of a few months. For each round of annotations, annotators
were presented with a subset of the dataset. After each round, the curator
consolidated the final annotations as follows:

##### Subtask 1

The majority voted label was retained as the final label. Every example in the
final corpus was annotated by at least two annotators. The curator has the
final vote if there are ties, or if only one annotation is present. Further
details are available in the CNC paper (Tan et al., 2022a).

##### Subtask 2

There was no straightforward way to take a majority label for span
annotations. Therefore, our approach was that the curator took into account
the spans highlighted by the annotators and decided on the final selection.

After each annotation round, the final span annotations were made available
for annotators to review and discuss.

####  3.2.4 Summary Statistics

##### Inter-annotator Agreement

| Train | Dev | Test | Total
---|---|---|---|---
K-Alpha | 34.42 | 29.77 | 48.55 | 34.99

Table 1: Subtask 1 Inter-annotator Agreement Scores. Reported in percentages.

Metric | Span | Train+Dev | Test | Total
---|---|---|---|---
Exact Match | Cause | 30.57 | 15.11 | 23.88
Effect | 36.30 | 19.86 | 29.19
Signal | 27.92 | 29.21 | 28.48
Total | 7.84 | 5.81 | 6.96
One-Side Bound | Cause | 57.55 | 39.86 | 49.90
Effect | 60.90 | 45.42 | 54.21
Signal | 31.93 | 32.96 | 32.37
Total | 24.05 | 22.25 | 23.27
Token Overlap | Cause | 63.65 | 49.18 | 57.39
Effect | 64.66 | 49.88 | 58.27
Signal | 32.09 | 33.15 | 32.55
Total | 26.94 | 27.78 | 27.31
K-Alpha | Cause | 46.36 | 42.51 | 44.32
Effect | 57.18 | 41.89 | 49.89
Signal | 29.30 | 23.42 | 27.08
Total | 50.90 | 41.54 | 46.27

Table 2: Subtask 2 Inter-annotator Agreement Scores. Reported in percentages
(%).

For Subtask 1, scores are reflected in Table 1. Also reported in Tan et al.
(2022a), overall, the dataset has a Krippendorff’s Alpha (K-Alpha) agreement
score of 34.99%.

For Subtask 2, the agreement metrics used were Exact Match (EM), Token Overlap
(TO), One-Side Bound (OSB), and K-Alpha. Scores are presented in Table 2.
Overall, the dataset had agreement scores of 6.96% EM, 23.27% OSB, 27.31% TO,
and 46.27% K-Alpha. Since OSB and TO are relaxed span evaluation metrics (Lee
and Sun, 2019), they are naturally much higher than EM, which is a strict
metric. How the metrics were calculated is described in the Appendix Section
A.1.

##### Shared Task Data

The summary statistics for Subtask 1 and 2 are available in Tables 3 and 4
respectively.

It is worth noting that for Subtask 2, the test set contained sentences that
were much longer than those in the training sets. This is because we were
annotating the shorter sentences first based on annotators’ feedback that
working with shorter sentences at the beginning helps them to familiarise
themselves with the annotation rules. Since there were more sentences in the
training set, the training set naturally also had more short sentences for us
to annotate first. Once we are done with span annotations, the average number
of words for Subtask 2 should tally with the causal sentences of Subtask 1,
shown earlier in Table 3.

Stat. |  Label | Train | Dev | Test | Total
---|---|---|---|---|---
# Sent-ences |  _Causal_ | 1603 | 178 | 176 | 1957
_Non-causal_ | 1322 | 145 | 135 | 1602
Total | 2925 | 323 | 311 | 3559
Avg. # words |  _Causal_ | 35.48 | 36.86 | 41.27 | 36.13
_Non-causal_ | 27.34 | 27.35 | 30.25 | 27.59
Total | 31.80 | 32.59 | 36.49 | 32.28

Table 3: Subtask 1 Data Summary Statistics.

Stat. | Train | Dev | Test | Total
---|---|---|---|---
# Sentences | 160 | 15 | 89 | 264
# Relations | 183 | 18 | 119 | 320
Avg. rels/sent | 1.14 | 1.20 | 1.34 | 1.21
Avg. # words | 17.21 | 16.13 | 28.45 | 20.94
Cause | 6.52 | 7.28 | 12.76 | 8.89
Effect | 7.80 | 6.44 | 10.20 | 8.62
Signal | 1.55 | 1.60 | 1.36 | 1.47
Avg # signals/rel | 0.67 | 0.56 | 0.82 | 0.72
Prop. of rels w/ signals | 0.64 | 0.56 | 0.76 | 0.68

Table 4: Subtask 2 Data Summary Statistics.

##  4 Task Description

The shared task is comprised of two subtasks related to Event Causality
Identification. The objective of each task is described in detail as follows:

###  4.1 Subtask 1: Causal Event Classification

The objective of this task is to classify whether an event sentence contains
any cause-effect meaning. Systems had to predict _Causal_ or _Non-causal_
labels per test sentence. An event sentence was defined to be _Causal_ if it
contains at least one causal relation.

###  4.2 Subtask 2: Cause-Effect-Signal Span Detection

The objective of this task is the detection of the consecutive spans relevant
to a _Causal_ relation. There are three types of spans involved in a _Causal_
relation: The _Cause_ span refers to words that describe the event that
triggers another _Effect_ event. The _Effect_ span refers to words that
describe the resulting event arising from a _Cause_ event. _Signals_ are
optionally present, and are words that explicitly indicate a _Causal_ relation
is present. In our dataset, multiple _Causal_ relations can exist in a
sentence, and participants have to identify all of them.

##  5 Evaluation & Competition

###  5.1 Evaluation Metrics

####  5.1.1 Subtask 1

We evaluated participants’ predictions using Accuracy (Acc), Precision (P),
Recall (R), F1, and Matthews Correlation Coefficient (MCC) scores.

####  5.1.2 Subtask 2

Following previous evaluation metrics for Cause-Effect Span Detection (Mariko
et al., 2020, 2021) and text chunking (Tjong Kim Sang and Buchholz, 2000), we
assessed predictions using Macro P, R and F1 metrics.

Participants uploaded sentences with Cause-Effect-Signal spans marked directly
in the text using ARG0, ARG1 and SIG start and end boundary markers. We
converted these marked sentences into two white-space tokenized sequences, one
corresponding to the token labels for Cause and Effect, and another
corresponding to the token labels for Signals. We used the token
classification evaluation scheme from seqeval (Nakayama, 2018; Ramshaw and
Marcus, 1995)444https://github.com/chakki-works/seqeval provided through
Huggingface (Wolf et al., 2020)555https://huggingface.co/spaces/evaluate-
metric/seqeval.

Evaluation was conducted at the relation level. In other words, examples with
multiple causal relations were unpacked and each relation contributed equally
to the final score.

##### Handling multiple relations

Since one input sequence can return multiple causal relations, we adjusted the
evaluation code to automatically extract the combination that results in the
best F1 score. As such, participants could submit multiple Cause-Effect-Signal
span predictions per input sequence in any order. An illustration is provided
in Figure 3.

In evaluation, we only compare with the number of causal relations that the
true label has. Let the number of predicted relations be $n_{p}$, and the
number of actual relations be $n_{a}$. Our evaluation script does the
following:

  * •

If the number of predicted relations exceeds the number of actual relations
($n_{p}>n_{a}$), we kept only the first $n_{a}$ predictions.

  * •

If the number of predicted relations is less than the number of actual
relations ($n_{p}<n_{a}$), the missing $n_{a}-n_{p},n_{a}-n_{p}+1,...,n_{a}$
relation predictions were represented by tokens that all correspond to the
Other (O) label.

Figure 3: Illustration of how we process multi-relation examples for sequence
evaluation.

###  5.2 Baseline

For Subtask 1, we duplicated the BERT Devlin et al. (2019) and LSTM Hochreiter
and Schmidhuber (1997) baselines from our previous work (Tan et al., 2022a)
that achieved F1 scores of 81.20% and 78.22% respectively.

For Subtask 2, a random
baseline666https://github.com/tanfiona/CausalNewsCorpus/blob/master/random_st2.py
was created for reference. This baseline first randomly identifies start
positions for Cause and Effect spans, and then identifies end positions for
these spans with a linearly increasing probability as we move away from the
start location in order to reflect our preference for longer spans. We also
randomly predicted words to be signals with a 10% chance. The baseline F1
score was 0.45%.

###  5.3 Competition Set-up

We used the Codalab website to host our competition.777The competition page is
at https://codalab.lisn.upsaclay.fr/competitions/2299. The additional scoring
page is at https://codalab.lisn.upsaclay.fr/competitions/7046.

##### Registration

37 participants requested to participate on the Codalab page. However, we
required participants to email us some personal details (Name, Institution and
Email) to avoid teams from creating multiple accounts to cheat. Subsequently,
29 participants were successfully registered, but only 17 accounts
participated by uploading predictions.

##### Trial and Test Periods

The trial period started on April 15, 2022 and the validation labels were
released on August 01, 2022. Participants could upload any number of
submissions against the validation set, and they could also submit predictions
for the validation set at any point in time. The main purpose of this setting
is for participants to familiarise themselves with the Codalab platform.

The test period started on August 01, 2022 and ended on August 31, 2022. Each
participant was allowed only 5 submissions to prevent participants from over-
fitting to the test set. After the competition ended, an additional scoring
page was created,888The additional scoring page is at
https://codalab.lisn.upsaclay.fr/competitions/7046. where participants could
upload one prediction a day to generate more scores for their description
papers. Any scores from this additional scoring page is not included into the
final leaderboard.

For both subtasks, models were ranked based on F1 performance on the
competition test set.

##  6 Participant Systems

###  6.1 Overview

13 participants successfully submitted scores to Subtask 1 while only 4
successfully submitted scores to Subtask 2 during test period. Table 5 and 6
reflects the leaderboard for Subtask 1 and 2 respectively for evaluation
metrics described earlier in Section 5.1. For Subtask 2, we further provided
the performance for each span type (i.e., Cause, Effect and Signal).

Rank | Team Name | Codalab Username | R | P | F1 | Acc | MCC
---|---|---|---|---|---|---|---
1 | CSECU-DSG (Aziz et al., 2022) | csecudsg | 88.64 | 83.87 | 86.19 | 83.92 | 67.14
2 | ARGUABLY (Kohli et al., 2022) | guneetsk99 | 91.48 | 81.31 | 86.10 | 83.28 | 66.02
3 | LTRC (Adibhatla and Shrivastava, 2022) | hiranmai | 88.64 | 82.11 | 85.25 | 82.64 | 64.51
4 | NLP4ITF (Krumbiegel and Decher, 2022) | pogs2022 | 88.07 | 82.45 | 85.16 | 82.64 | 64.49
5 | IDIAPers (Burdisso et al., 2022) | msingh | 87.50 | 82.80 | 85.08 | 82.64 | 64.49
6 | NoisyAnnot (Nguyen and Mitra, 2022) | thearkamitra | 88.07 | 82.01 | 84.93 | 82.32 | 63.83
7 | SNU-Causality Lab (Kim et al., 2022) | JuHyeon_Kim | 90.34 | 79.50 | 84.57 | 81.35 | 62.04
8 | LXPER AI Research | brucewlee | 86.36 | 82.61 | 84.44 | 81.99 | 63.18
9 | 1Cademy (Nik et al., 2022) | nika | 86.36 | 81.72 | 83.98 | 81.35 | 61.85
10 | - | quynhanh | 85.80 | 79.06 | 82.29 | 79.10 | 57.19
11 | BERT Baseline (Tan et al., 2022a) | tanfiona | 84.66 | 78.01 | 81.20 | 77.81 | 54.52
12 | GGNN (Trust et al., 2022) | PaulTrust | 88.07 | 74.88 | 80.94 | 76.53 | 52.05
13 | LSTM Basline (Tan et al., 2022a) | hansih | 84.66 | 72.68 | 78.22 | 73.31 | 45.15
14 | Innovators | lapardnemihk9989 | 78.98 | 72.02 | 75.34 | 70.74 | 39.81
15 | - | necva | 81.25 | 59.09 | 68.42 | 57.56 | 9.44

Table 5: Subtask 1 Leaderboard. Ranked by Binary F1. All scores are reported
in percentages (%). Highest score per column is in bold.

Ra-nk | Team Name | Codalab Username | Overall | Cause (n=119) | Effect (n=119) | Signal (n=98)
---|---|---|---|---|---|---
R | P | F1 | Acc | R | P | F1 | R | P | F1 | R | P | F1
1 | 1Cademy (Chen et al., 2022) |  gezhang | 53.87 | 55.09 | 54.15 | 43.15 | 55.46 | 57.98 | 56.47 | 55.46 | 57.14 | 56.13 | 50.00 | 49.09 | 48.92
2 | IDIAPers (Fajcik et al., 2022) |  msingh | 47.62 | 51.21 | 48.75 | 40.83 | 45.38 | 45.38 | 45.38 | 42.86 | 42.86 | 42.86 | 56.12 | 68.44 | 60.01
3 | SPOCK (Saha et al., 2022) |  spock | 43.75 | 57.62 | 47.48 | 36.87 | 37.82 | 49.19 | 41.40 | 39.50 | 59.66 | 46.29 | 56.12 | 65.39 | 56.32
4 | LTRC (Adibhatla and Shrivastava, 2022) |  hiranmai | 5.65 | 2.34 | 3.23 | 33.03 | 2.52 | 1.10 | 1.53 | 13.45 | 5.51 | 7.60 | 0.00 | 0.00 | 0.00
5 | Random Baseline |  tanfiona | 0.30 | 0.89 | 0.45 | 21.94 | 0.84 | 2.52 | 1.26 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00

Table 6: Subtask 2 Leaderboard. Ranked by Overall Macro F1. All scores are
reported in percentages (%). Highest score per column is in bold.

For Subtask 1, the top performing team was CSECU-DSG (Aziz et al., 2022),
scoring 86.19% F1. CSECU-DSG also topped the charts for P, Acc, and MCC
scores. Team ARGUABLY (Kohli et al., 2022) followed closely after, with 86.10%
F1 score and a high recall score of 91.48%. Both methods fine-tuned SOTA pre-
trained BERT variants (RoBERTA (Liu et al., 2019) and DeBERTa (He et al.,
2021)) to the classification task.

For Subtask 2, the top performing team was 1Cademy (Chen et al., 2022),
scoring 54.15% F1. Team IDIAPers (Fajcik et al., 2022) and SPOCK (Saha et al.,
2022) followed closely after, with 48.75% and 47.48% F1 scores respectively.
Each team approached the span detection task in a different way: 1Cademy
treated the task as a reading comprehension challenge and predicted start and
end boundaries of the spans. IDIAPers treated the task as a decoding
challenge, while SPOCK generated and classified candidate spans. All
participants used pre-trained models in their frameworks.

###  6.2 Methods

Each teams’ systems are summarized below, sorted according to their
leaderboard ranking.

####  6.2.1 Subtask 1

##### CSECU-DSG

(Aziz et al., 2022) proposed a way to unify predictions obtained from two
neural network models, by combining the prediction scores generated from each
model using a weighted arithmetic mean. The two models used were, Twitter
RoBERTa and RoBERTa-base, and each was attached to a linear layer to predict
the causal labels. The weights per model were 0.4 and 0.6 respectively,
selected through experiments on training data. Their findings on the test set
showed that the fused model achieves higher P, R, and F1 score than each model
alone, and their approach clinched the top place during the competition.

##### ARGUABLY

(Kohli et al., 2022) proposed using sentence-level data augmentation to fine-
tune language models (LMs). They involved contextualised word embeddings of
DistilBERT (Sanh et al., 2019) to construct new data. As for the LMs, DeBERTa
and dual cross attention RoBERTa models have been experimented with. According
to the results, the DeBERTa model fine-tuned on augmented data outperformed
the unaugmented DeBERTa model and RoBERTa models.

##### LTRC

(Adibhatla and Shrivastava, 2022) used various transformers-based language
models followed by a classification head. The pre-trained models explored by
them were: BART-large (Lewis et al., 2020), RoBERTa-base+Linear Layer,
RoBERTa-large+Linear Layer, RoBERTa-base+Adapter and RoBERTa-large+Adapter.
Their best model slightly beats the baseline scores on the development set.

##### NLP4ITF

(Krumbiegel and Decher, 2022) proposed building a RoBERTa model with
linguistic features. They mainly involved named entities (NE) and cause-
effect-signal (CES) spans from Subtask 2 to incorporate linguistic features
with the input text. Based on their findings, the model trained with the PER
(person) NE class with CES, achieved the best results, outperforming the
RoBERTa baseline (model trained on data with no linguistic features).

##### IDIAPers

(Burdisso et al., 2022) proposed a prompt-based approach for fine-tuning LMs
in which the classification task is modeled as a masked language modeling
problem (MLM). This approach allows LMs natively pre-trained on MLM problems,
like RoBERTa, to directly generate textual responses to domain-specific
prompts. This approach allow the model to be trained in a few-shot
configuration, keeping most of available data for measuring the generalization
power the model. The best-performing model was trained with only 256 instances
per class and yet was able to obtain the second-best precision and third-best
accuracy.

##### NoisyAnnot

(Nguyen and Mitra, 2022) proposed fine-tuning different LMs with customised
cross-entropy loss functions that exploit annotation information such as the
number of annotators and their agreement. They used several language models
including BERT, RoBERTa and XLNET models and showed that the involvement of
annotation information improves the model performance.

##### SNU-Causality Lab

(Kim et al., 2022) proposed fine-tuning an ELECTRA model using the CNC dataset
and augmented data. They followed two approaches for data augmentation: (1)
concatenating SemEval-2010 to CNC and (2) generating new samples using POS
tagging. With the POS tagging-based approach they mainly targeted replacing
causality irrelevant words with POS tags, to generate more data while
preserving the causality relevant information in the original dataset.

##### 1Cademy

(Nik et al., 2022) experimented with self-training to generate more sequence
classification examples from unlabeled Wikipedia sentences. They experimented
with three pretrained models (BERT, RoBERTa and ELECTRA), and also
experimented with three ratios of positive to negative self-labeled examples
(1:3, 1:1, 3:1). Their experiments showed that including self-labeled data
during training always returns higher F1 scores. Their best model during test
time was the RoBERTa-based model with 1:1 self-training ratio, which surpassed
the competition baseline scores.

##### GGNN

(Trust et al., 2022) injected word embeddings into a Gated Graph Neural
Network (GGNN), which were attached to a RNN decoder to predict the sequence
label. Two word embeddings were explored: Word2Vec and BERT. Their BERT+GGNN
combination outperforms the BERT baseline provided during the competition for
both the development and test sets for P, F1 and Acc.

####  6.2.2 Subtask 2

##### 1Cademy

(Chen et al., 2022) approached this task in a reading comprehension manner,
and created a baseline BERT-based neural network that predicted the start and
end positions of each Cause, Effect, and Signal span. They introduced beam-
search methods (BSS) as post-processing constraints suited to the task. They
also introduced a signal classifier that detects if a Signal exists in the
sequence or not via a joint model (JS) or a separate model (ES). Additionally,
BART was fine-tuned for paraphrasing to re-write Cause and Effect phrases
within each sentence for data augmentation (DA). In the end, their best model
is a combination of Baseline+BSS+ES+DA method, where the DA generated 3 new
phrases per span. This model achieved F1 score of 54.15% on the test set,
clinching the top place during the competition.

##### IDIAPers

(Fajcik et al., 2022) approached the task in an encoder-decoder framework.
They conditioned the T5 language model three times per example to generate up
to four causal relations per example. In each round, given the history of a
sentence, the model generates Cause, followed by Effect, and then Signal. This
model is their vanilla model known as T5-CES. History refers to the input
sequence with any annotated spans from the previous round, if applicable. In
experiments, they also explored (1) variants involving a version without
historical annotations, (2) T5-large pre-trained model, and (3) changing the
order of generation to be Effect, Cause then Signal. Their best model on the
test set (T5-CES) achieved 48.8 F1 score, coming in second in the competition.

##### SPOCK

(Saha et al., 2022) designed two separate frameworks for the span detection
task, span-based modelling and token classification. Both approaches far
exceed the random baseline provided by the organizers during the competition
period. Their span-based modelling approach achieved an F1 score of 47.48%,
ranking third in the competition. This model classifies a list of candidate
spans to a Cause, Effect, Signal or None label. The candidate spans are
generated by considering all possible spans up to a maximum length. The model
receives inputs comprising a CLS token embedding, concatenated with a width
embedding, plus the span embedding representation itself. To select the final
Cause-Effect-Signal span, spans below a certain threshold are removed, and
then the span with the highest probability for that label is retained.

##### LTRC

(Adibhatla and Shrivastava, 2022) approached the task as a token
classification task, and designed a BERT-based IOB predicting model alongside
some heuristics adjusted for the task. Their approach slightly beats the
baseline scores on the development set.

##  7 Analysis & Discussion

(a) Subtask 1

(b) Subtask 2

Figure 4: Histogram of exact matches.

###  7.1 Trends

Consistent with NLP trends, pre-trained language models are popular and
employed by all teams and for both subtasks.

For Subtask 1, teams found novel ways to improve from the BERT and LSTM
baseline by combining multiple models, adding linguistic features,
incorporating additional neural network layers, and working with augmented
data.

For Subtask 2, there is a wide variation in framing the task. Teams approached
it as a reading comprehension, encoder-decoder, candidate span classification
and token classification task. Additionally, there are two constraints that
models had to accommodate: (1) The task involves predicting multiple causal
relations per input sentence, and (2) Not all causal relations have a signal
span. The top three teams carefully adjust their models to work with the two
constraints. For (1), IDIAPers predicted different relations using rounds
while incorporating the predicted annotations of the previous round. For (2),
1Cademy included a separate classification task, while IDIAPers and SPOCK
permitted "empty" or "None" span predictions. Interestingly, the F1 score for
signals is highest for IDIAPers, suggesting merits to predict signal spans in
a manner that includes Cause and Effect predictions as inputs.

###  7.2 Participation

Subtask | Finished | Failed | Total
---|---|---|---
Subtask 1 | 58 | 8 | 66
Subtask 2 | 12 | 24 | 36
Table 7: Number of submissions received for test set.

More submissions were received for Subtask 1 than for Subtask 2, as shown in
Table 7. Unsurprisingly, there is a high proportion of failed submissions in
Subtask 2. Since Subtask 2 requires specific formatting of argument markings
and compiling of multiple predictions into a list, it is easy to face
formatting errors. For Subtask 2, although 12 participants did try to submit
for the competition, only 4 managed to submit predictions of the right format.
A closer look at the submission files suggests that most of the time, these
participants intended to upload predictions for Subtask 1. However, because
the default Codalab tab falls on Subtask 2, they make submissions to the wrong
task. Nevertheless, we are aware of 1 participant who reached out to try and
resolve formatting issues and did not manage to resubmit their predictions in
the right format in time. This team ran into issues trying to match the
spacing of the original input text.

###  7.3 Error Analysis

For Subtask 1, we had 13 participants while for Subtask 2, we had 4
participants. For Subtask 1, we counted the number of teams that matched the
true labels exactly per example. For Subtask 2, if any predicted span exactly
match the true Cause-Effect-Signal span, we considered there to be an accurate
count. A histogram per subtask reflecting the accuracy counts are reflected in
Figure 4.

For Subtask 1, 100 examples were predicted correctly, while 4 examples were
predicted wrongly by all participants. There is a total of 52 examples that
are challenging, where less than half of the participants were able to get a
correct prediction.

For Subtask 2, no examples were predicted correctly by all participants. This
is because LTRC’s submission was very close to the Random Baseline and had no
exactly correct predictions. 6 causal relations were predicted correctly by
the remaining three participants. Nevertheless, most examples were predicted
wrongly by all participants (i.e., 70 examples received all wrong
predictions). Clearly, Subtask 2 is a challenging task and has a lot of room
for growth.

##  8 Conclusion

In conclusion, our shared task investigated two important tasks in causal text
mining, namely: (1) Causal Event Classification, and (2) Cause-Effect-Signal
Span Detection. Our shared task attracted 29 registered participants and 17
active participants who made over 100 submissions on the test set. Based on
the 12 description papers received, many novel methods that exceeded our
initial baseline were proposed. The best F1 scores achieved for Subtask 1 and
2 were 86.19% and 54.15% respectively.

We intend to re-launch this shared task next year with even more data for
Subtask 2. Additionally, we will also investigate the challenging examples in
Subtask 1 that are predicted wrongly by many teams.

## References

  * Adibhatla and Shrivastava (2022) Hiranmai Sri Adibhatla and Manish Shrivastava. 2022.  LTRC @ Causal News Corpus 2022: Extracting and identifying causal elements using adapters.  In _Proceedings of the 5th Workshop on Challenges and Applications of Automated Extraction of Socio-political Events from Text (CASE 2022)_ , Online. Association for Computational Linguistics.
  * Asghar (2016) Nabiha Asghar. 2016.  Automatic extraction of causal relations from natural language texts: a comprehensive survey.  _arXiv preprint arXiv:1605.07895_.
  * Aziz et al. (2022) Abdul Aziz, Md. Akram Hossain, and Abu Nowshed Chy. 2022.  CSECU-DSG @ Causal News Corpus 2022: Fusion of RoBERTa transformer variants for causal event classification.  In _Proceedings of the 5th Workshop on Challenges and Applications of Automated Extraction of Socio-political Events from Text (CASE 2022)_ , Online. Association for Computational Linguistics.
  * Barik et al. (2016) Biswanath Barik, Erwin Marsi, and Pinar Öztürk. 2016.  Event causality extraction from natural science literature.  _Res. Comput. Sci._ , 117:97–107.
  * Burdisso et al. (2022) Sergio Burdisso, Juan Zuluaga-Gomez, Martin Fajcik, Esaú Villatoro-Tello, Muskaan Singh, Petr Motlicek, and Pavel Smrz. 2022.  IDIAPers @ Causal News Corpus 2022: Causal relation identification using a few-shot and prompt-based fine-tuning of language models.  In _The 5th Workshop on Challenges and Applications of Automated Extraction of Socio-political Events from Text (CASE @ EMNLP 2022)_ , Online. Association for Computational Linguistics.
  * Cao et al. (2021) Pengfei Cao, Xinyu Zuo, Yubo Chen, Kang Liu, Jun Zhao, Yuguang Chen, and Weihua Peng. 2021.  Knowledge-enriched event causality identification via latent structure induction networks.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pages 4862–4872, Online. Association for Computational Linguistics.
  * Caselli and Vossen (2017) Tommaso Caselli and Piek Vossen. 2017.  The event StoryLine corpus: A new benchmark for causal and temporal relation extraction.  In _Proceedings of the Events and Stories in the News Workshop_ , pages 77–86, Vancouver, Canada. Association for Computational Linguistics.
  * Chen et al. (2022) Xingran Chen, Ge Zhang, Adam Nik, Mingyu Li, and Jie Fu. 2022.  1Cademy @ Causal News Corpus 2022: Enhance causal span detection via beam-search-based position selector.  In _Proceedings of the 5th Workshop on Challenges and Applications of Automated Extraction of Socio-political Events from Text (CASE 2022)_ , Online. Association for Computational Linguistics.
  * Dalal et al. (2021) Dhairya Dalal, Mihael Arcan, and Paul Buitelaar. 2021.  Enhancing multiple-choice question answering with causal knowledge.  In _Proceedings of Deep Learning Inside Out (DeeLIO): The 2nd Workshop on Knowledge Extraction and Integration for Deep Learning Architectures_ , pages 70–80, Online. Association for Computational Linguistics.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  BERT: Pre-training of deep bidirectional transformers for language understanding.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pages 4171–4186, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Dunietz et al. (2020) Jesse Dunietz, Greg Burnham, Akash Bharadwaj, Owen Rambow, Jennifer Chu-Carroll, and Dave Ferrucci. 2020.  To test machine comprehension, start by defining comprehension.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 7839–7859, Online. Association for Computational Linguistics.
  * Dunietz et al. (2017) Jesse Dunietz, Lori Levin, and Jaime Carbonell. 2017.  The BECauSE corpus 2.0: Annotating causality and overlapping relations.  In _Proceedings of the 11th Linguistic Annotation Workshop_ , pages 95–104, Valencia, Spain. Association for Computational Linguistics.
  * Eckart de Castilho et al. (2016) Richard Eckart de Castilho, Éva Mújdricza-Maydt, Seid Muhie Yimam, Silvana Hartmann, Iryna Gurevych, Anette Frank, and Chris Biemann. 2016.  A web-based tool for the integrated annotation of semantic and syntactic structures.  In _Proceedings of the Workshop on Language Technology Resources and Tools for Digital Humanities (LT4DH)_ , pages 76–84, Osaka, Japan. The COLING 2016 Organizing Committee.
  * Fajcik et al. (2022) Martin Fajcik, Muskaan Singh, Juan Zuluaga-Gomez, Esaú Villatoro-Tello, Sergio Burdisso, Petr Motlicek, and Pavel Smrz. 2022.  IDIAPers @ Causal News Corpus 2022: Extracting cause-effect-signal triplets via pre-trained autoregressive language model.  In _The 5th Workshop on Challenges and Applications of Automated Extraction of Socio-political Events from Text (CASE @ EMNLP 2022)_ , Online. Association for Computational Linguistics.
  * Gao et al. (2019) Lei Gao, Prafulla Kumar Choubey, and Ruihong Huang. 2019.  Modeling document-level causal structures for event causal relation identification.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pages 1808–1817, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Hashimoto et al. (2014) Chikara Hashimoto, Kentaro Torisawa, Julien Kloetzer, Motoki Sano, István Varga, Jong-Hoon Oh, and Yutaka Kidawara. 2014.  Toward future scenario generation: Extracting event causality exploiting semantic relation, context, and association features.  In _Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 987–997, Baltimore, Maryland. Association for Computational Linguistics.
  * Hassanzadeh et al. (2019) Oktie Hassanzadeh, Debarun Bhattacharjya, Mark Feblowitz, Kavitha Srinivas, Michael Perrone, Shirin Sohrabi, and Michael Katz. 2019.  Answering binary causal questions through large-scale text mining: An evaluation using cause-effect pairs from human experts.  In _Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI-19_ , pages 5003–5009. International Joint Conferences on Artificial Intelligence Organization.
  * He et al. (2021) Pengcheng He, Xiaodong Liu, Jianfeng Gao, and Weizhu Chen. 2021.  Deberta: decoding-enhanced bert with disentangled attention.  In _9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021_. OpenReview.net.
  * Hendrickx et al. (2010) Iris Hendrickx, Su Nam Kim, Zornitsa Kozareva, Preslav Nakov, Diarmuid Ó Séaghdha, Sebastian Padó, Marco Pennacchiotti, Lorenza Romano, and Stan Szpakowicz. 2010.  SemEval-2010 task 8: Multi-way classification of semantic relations between pairs of nominals.  In _Proceedings of the 5th International Workshop on Semantic Evaluation_ , pages 33–38, Uppsala, Sweden. Association for Computational Linguistics.
  * Hidey and McKeown (2016) Christopher Hidey and Kathy McKeown. 2016.  Identifying causal relations using parallel Wikipedia articles.  In _Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 1424–1433, Berlin, Germany. Association for Computational Linguistics.
  * Hochreiter and Schmidhuber (1997) Sepp Hochreiter and Jürgen Schmidhuber. 1997.  Long Short-Term Memory.  _Neural Computation_ , 9(8):1735–1780.
  * Hürriyetoğlu (2021) Ali Hürriyetoğlu, editor. 2021.  _Proceedings of the 4th Workshop on Challenges and Applications of Automated Extraction of Socio-political Events from Text (CASE 2021)_. Association for Computational Linguistics, Online.
  * Hürriyetoğlu et al. (2021a) Ali Hürriyetoğlu, Osman Mutlu, Erdem Yörük, Farhana Ferdousi Liza, Ritesh Kumar, and Shyam Ratan. 2021a.  Multilingual protest news detection - shared task 1, CASE 2021.  In _Proceedings of the 4th Workshop on Challenges and Applications of Automated Extraction of Socio-political Events from Text (CASE 2021)_ , pages 79–91, Online. Association for Computational Linguistics.
  * Hürriyetoğlu et al. (2021b) Ali Hürriyetoğlu, Hristo Tanev, Vanni Zavarella, Jakub Piskorski, Reyyan Yeniterzi, Osman Mutlu, Deniz Yuret, and Aline Villavicencio. 2021b.  Challenges and applications of automated extraction of socio-political events from text (CASE 2021): Workshop and shared task report.  In _Proceedings of the 4th Workshop on Challenges and Applications of Automated Extraction of Socio-political Events from Text (CASE 2021)_ , pages 1–9, Online. Association for Computational Linguistics.
  * Hürriyetoğlu et al. (2020a) Ali Hürriyetoğlu, Erdem Yörük, Vanni Zavarella, and Hristo Tanev, editors. 2020a.  _Proceedings of the Workshop on Automated Extraction of Socio-political Events from News 2020_. European Language Resources Association (ELRA), Marseille, France.
  * Hürriyetoğlu et al. (2020b) Ali Hürriyetoğlu, Vanni Zavarella, Hristo Tanev, Erdem Yörük, Ali Safaya, and Osman Mutlu. 2020b.  Automated extraction of socio-political events from news (AESPEN): Workshop and shared task report.  In _Proceedings of the Workshop on Automated Extraction of Socio-political Events from News 2020_ , pages 1–6, Marseille, France. European Language Resources Association (ELRA).
  * Hürriyetoğlu et al. (2021) Ali Hürriyetoğlu, Erdem Yörük, Osman Mutlu, Fırat Duruşan, Çağrı Yoltar, Deniz Yüret, and Burak Gürel. 2021.  Cross-Context News Corpus for Protest Event-Related Knowledge Base Construction.  _Data Intelligence_ , 3(2):308–335.
  * Izumi et al. (2021) Kiyoshi Izumi, Hitomi Sano, and Hiroki Sakaji. 2021.  Economic causal-chain search and economic indicator prediction using textual data.  In _Proceedings of the 3rd Financial Narrative Processing Workshop_ , pages 19–25, Lancaster, United Kingdom. Association for Computational Linguistics.
  * Jo et al. (2021) Yohan Jo, Seojin Bang, Chris Reed, and Eduard H. Hovy. 2021.  Classifying argumentative relations using logical mechanisms and argumentation schemes.  _Trans. Assoc. Comput. Linguistics_ , 9:721–739.
  * Kim et al. (2022) Juhyeon Kim, Yesong Choe, and Sanghack Lee. 2022.  SNU-Causality Lab @ Causal News Corpus 2022: Detecting causality by data augmentation via part-of-speech tagging.  In _Proceedings of the 5th Workshop on Challenges and Applications of Automated Extraction of Socio-political Events from Text (CASE 2022)_ , Online. Association for Computational Linguistics.
  * Kohli et al. (2022) Guneet Kohli, Prabsimran Kaur, and Jatin Bedi. 2022.  ARGUABLY @ Causal News Corpus 2022: Contextually augmented language models for event causality identification.  In _Proceedings of the 5th Workshop on Challenges and Applications of Automated Extraction of Socio-political Events from Text (CASE 2022)_ , Online. Association for Computational Linguistics.
  * Krumbiegel and Decher (2022) Theresa Krumbiegel and Sophie Decher. 2022.  NLP4ITF @ Causal News Corpus 2022: Leveraging linguistic information for event causality classification.  In _Proceedings of the 5th Workshop on Challenges and Applications of Automated Extraction of Socio-political Events from Text (CASE 2022)_ , Online. Association for Computational Linguistics.
  * Lee and Sun (2019) Grace E. Lee and Aixin Sun. 2019.  A study on agreement in PICO span annotations.  In _Proceedings of the 42nd International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR 2019, Paris, France, July 21-25, 2019_ , pages 1149–1152. ACM.
  * Lewis et al. (2020) Mike Lewis, Yinhan Liu, Naman Goyal, Marjan Ghazvininejad, Abdelrahman Mohamed, Omer Levy, Veselin Stoyanov, and Luke Zettlemoyer. 2020.  BART: denoising sequence-to-sequence pre-training for natural language generation, translation, and comprehension.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, ACL 2020, Online, July 5-10, 2020_ , pages 7871–7880. Association for Computational Linguistics.
  * Liu et al. (2019) Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. 2019.  Roberta: A robustly optimized BERT pretraining approach.  _CoRR_ , abs/1907.11692.
  * Mariko et al. (2020) Dominique Mariko, Hanna Abi-Akl, Estelle Labidurie, Stephane Durfort, Hugues De Mazancourt, and Mahmoud El-Haj. 2020.  The financial document causality detection shared task (FinCausal 2020).  In _Proceedings of the 1st Joint Workshop on Financial Narrative Processing and MultiLing Financial Summarisation_ , pages 23–32, Barcelona, Spain (Online). COLING.
  * Mariko et al. (2021) Dominique Mariko, Hanna Abi Akl, Estelle Labidurie, Stephane Durfort, Hugues de Mazancourt, and Mahmoud El-Haj. 2021.  The financial document causality detection shared task (FinCausal 2021).  In _Proceedings of the 3rd Financial Narrative Processing Workshop_ , pages 58–60, Lancaster, United Kingdom. Association for Computational Linguistics.
  * Mirza et al. (2014) Paramita Mirza, Rachele Sprugnoli, Sara Tonelli, and Manuela Speranza. 2014.  Annotating causality in the TempEval-3 corpus.  In _Proceedings of the EACL 2014 Workshop on Computational Approaches to Causality in Language (CAtoCL)_ , pages 10–19, Gothenburg, Sweden. Association for Computational Linguistics.
  * Mirza and Tonelli (2014) Paramita Mirza and Sara Tonelli. 2014.  An analysis of causality between events and its relation to temporal information.  In _Proceedings of COLING 2014, the 25th International Conference on Computational Linguistics: Technical Papers_ , pages 2097–2106, Dublin, Ireland. Dublin City University and Association for Computational Linguistics.
  * Nakayama (2018) Hiroki Nakayama. 2018.  seqeval: A python framework for sequence labeling evaluation.  Software available from https://github.com/chakki-works/seqeval.
  * Nguyen and Mitra (2022) Quynh Anh Nguyen and Arka Mitra. 2022.  NoisyAnnot @ Causal News Corpus 2022: Causality detection using multiple annotation decision.  In _Proceedings of the 5th Workshop on Challenges and Applications of Automated Extraction of Socio-political Events from Text (CASE 2022)_ , Online. Association for Computational Linguistics.
  * Nik et al. (2022) Adam Nik, Ge Zhang, Xingran Chen, Mingyu Li, and Jie Fu. 2022.  1Cademy @ Causal News Corpus 2022: Leveraging self-training in causality classification of socio-political event data.  In _Proceedings of the 5th Workshop on Challenges and Applications of Automated Extraction of Socio-political Events from Text (CASE 2022)_ , Online. Association for Computational Linguistics.
  * Pustejovsky et al. (2003) James Pustejovsky, José M. Castaño, Robert Ingria, Roser Saurí, Robert J. Gaizauskas, Andrea Setzer, Graham Katz, and Dragomir R. Radev. 2003.  Timeml: Robust specification of event and temporal expressions in text.  In _New Directions in Question Answering, Papers from 2003 AAAI Spring Symposium, Stanford University, Stanford, CA, USA_ , pages 28–34. AAAI Press.
  * Radinsky et al. (2012) Kira Radinsky, Sagie Davidovich, and Shaul Markovitch. 2012.  Learning causality for news events prediction.  In _Proceedings of the 21st World Wide Web Conference 2012, WWW 2012, Lyon, France, April 16-20, 2012_ , pages 909–918. ACM.
  * Radinsky and Horvitz (2013) Kira Radinsky and Eric Horvitz. 2013.  Mining the web to predict future events.  In _Sixth ACM International Conference on Web Search and Data Mining, WSDM 2013, Rome, Italy, February 4-8, 2013_ , pages 255–264. ACM.
  * Ramshaw and Marcus (1995) Lance Ramshaw and Mitch Marcus. 1995.  Text chunking using transformation-based learning.  In _Third Workshop on Very Large Corpora_.
  * Saha et al. (2022) Anik Saha, Alex Gittens, Jian Ni, Oktie Hassanzadeh, Bulent Yener, and Kavitha Srinivas. 2022.  SPOCK @ Causal News Corpus 2022: Cause-effect-signal span detection using span-based and sequence tagging models.  In _Proceedings of the 5th Workshop on Challenges and Applications of Automated Extraction of Socio-political Events from Text (CASE 2022)_ , Online. Association for Computational Linguistics.
  * Sanh et al. (2019) Victor Sanh, Lysandre Debut, Julien Chaumond, and Thomas Wolf. 2019.  Distilbert, a distilled version of BERT: smaller, faster, cheaper and lighter.  _CoRR_ , abs/1910.01108.
  * Saurı et al. (2006) Roser Saurı, Jessica Littman, Bob Knippen, Robert Gaizauskas, Andrea Setzer, and James Pustejovsky. 2006.  Timeml annotation guidelines version 1.2.1.
  * Stasaski et al. (2021) Katherine Stasaski, Manav Rathod, Tony Tu, Yunfang Xiao, and Marti A. Hearst. 2021\.  Automatically generating cause-and-effect questions from passages.  In _Proceedings of the 16th Workshop on Innovative Use of NLP for Building Educational Applications_ , pages 158–170, Online. Association for Computational Linguistics.
  * Tan et al. (2021) Fiona Anting Tan, Devamanyu Hazarika, See-Kiong Ng, Soujanya Poria, and Roger Zimmermann. 2021.  Causal augmentation for causal sentence classification.  In _Proceedings of the First Workshop on Causal Inference and NLP_ , pages 1–20, Punta Cana, Dominican Republic. Association for Computational Linguistics.
  * Tan et al. (2022a) Fiona Anting Tan, Ali Hürriyetoğlu, Tommaso Caselli, Nelleke Oostdijk, Tadashi Nomoto, Hansi Hettiarachchi, Iqra Ameer, Onur Uca, Farhana Ferdousi Liza, and Tiancheng Hu. 2022a.  The causal news corpus: Annotating causal relations in event sentences from news.  In _Proceedings of the Language Resources and Evaluation Conference_ , pages 2298–2310, Marseille, France. European Language Resources Association.
  * Tan et al. (2022b) Fiona Anting Tan, Xinyu Zuo, and See-Kiong Ng. 2022b.  Unicausal: Unified benchmark and model for causal text mining.
  * Tjong Kim Sang and Buchholz (2000) Erik F. Tjong Kim Sang and Sabine Buchholz. 2000.  Introduction to the CoNLL-2000 shared task chunking.  In _Fourth Conference on Computational Natural Language Learning and the Second Learning Language in Logic Workshop_.
  * Trust et al. (2022) Paul Trust, Provia Kadusabe, Rosane Minghim, Ahmed Zahran, Evangelos Milos, Kizito Omala, and Haseeb Yonais. 2022.  GGNN @ Causal News Corpus 2022: Gated graph neural networks for causal event classification from social-political news articles.  In _Proceedings of the 5th Workshop on Challenges and Applications of Automated Extraction of Socio-political Events from Text (CASE 2022)_ , Online. Association for Computational Linguistics.
  * Webber et al. (2019) Bonnie Webber, Rashmi Prasad, Alan Lee, and Aravind Joshi. 2019.  The penn discourse treebank 3.0 annotation manual.  _Philadelphia, University of Pennsylvania_.
  * Wolf et al. (2020) Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Remi Louf, Morgan Funtowicz, Joe Davison, Sam Shleifer, Patrick von Platen, Clara Ma, Yacine Jernite, Julien Plu, Canwen Xu, Teven Le Scao, Sylvain Gugger, Mariama Drame, Quentin Lhoest, and Alexander Rush. 2020.  Transformers: State-of-the-art natural language processing.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations_ , pages 38–45, Online. Association for Computational Linguistics.
  * Xu et al. (2020) Jinghang Xu, Wanli Zuo, Shining Liang, and Xianglin Zuo. 2020.  A review of dataset and labeling methods for causality extraction.  In _Proceedings of the 28th International Conference on Computational Linguistics_ , pages 1519–1531, Barcelona, Spain (Online). International Committee on Computational Linguistics.
  * Yang et al. (2022) Jie Yang, Soyeon Caren Han, and Josiah Poon. 2022.  A survey on extraction of causal relations from natural language text.  _Knowl. Inf. Syst._ , 64(5):1161–1186.
  * Yörük et al. (2021) Erdem Yörük, Ali Hürriyetoğlu, Fırat Duruşan, and Çağrı Yoltar. 2021.  Random sampling in corpus design: Cross-context generalizability in automated multicountry protest event collection.  _American Behavioral Scientist_ , 0(0):00027642211021630.
  * Zuo et al. (2021a) Xinyu Zuo, Pengfei Cao, Yubo Chen, Kang Liu, Jun Zhao, Weihua Peng, and Yuguang Chen. 2021a.  Improving event causality identification via self-supervised representation learning on external causal statement.  In _Findings of the Association for Computational Linguistics: ACL-IJCNLP 2021_ , pages 2162–2172, Online. Association for Computational Linguistics.
  * Zuo et al. (2021b) Xinyu Zuo, Pengfei Cao, Yubo Chen, Kang Liu, Jun Zhao, Weihua Peng, and Yuguang Chen. 2021b.  LearnDA: Learnable knowledge-guided data augmentation for event causality identification.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pages 3558–3571, Online. Association for Computational Linguistics.
  * Zuo et al. (2020) Xinyu Zuo, Yubo Chen, Kang Liu, and Jun Zhao. 2020.  KnowDis: Knowledge enhanced data augmentation for event causality detection via distant supervision.  In _Proceedings of the 28th International Conference on Computational Linguistics_ , pages 1544–1550, Barcelona, Spain (Online). International Committee on Computational Linguistics.

##  Appendix A Appendix

###  A.1 Subtask 2 Agreement Score Calculations

For span annotations, the agreement scores were calculated by taking a
weighted average of the subset level agreement scores that takes into account
the example counts per subset.

We split the training plus development set into 8 subsets and the test set
into 2 subsets. While conducting the annotations, the agreement scores were
evaluated at a subset level so that we can consistently assess the annotators’
performance. The subset level scores takes the average scores between each
pair of annotators. For example, if there were three annotators (Annotator A,
B, and C) for the subset, then we took the average agreement score when
comparing (A,B), (B,C) and (A,C) annotator pairs. Each pair was weighted
equally.

The annotator pair level scores were computed by taking the average scores
across the sentences. Each sentence was weighted equally.

At the sentence level, agreement scores were obtained by taking the average
scores of each causal relation pair. Each causal relation pair was weighted
equally.

Since annotators might annotate multiple spans per example, there are many
ways to match the annotated relations between two annotators. We approached
this conflict by considering every possible combination pair, after which, we
retained the match that returned the highest possible sum of EM, OSB and TO
scores. If one annotator identified more causal relations than the other, then
EM, OSB and TO scores for that relation is automatically zero.

The KAlpha script was an open-source code999https://github.com/emerging-
welfare/kAlpha. The other three metrics were coded based on previous work (Lee
and Sun, 2019).


# Toward Efficient and Incremental Spectral Clustering via Parametric Spectral
Clustering

Jo-Chun Chen, Hung-Hsuan Chen
Computer Science and Information Engineering
National Central University
Taoyuan, Taiwan
<EMAIL_ADDRESS><EMAIL_ADDRESS>

###### Abstract

Spectral clustering is a popular method for effectively clustering nonlinearly
separable data. However, computational limitations, memory requirements, and
the inability to perform incremental learning challenge its widespread
application. To overcome these limitations, this paper introduces a novel
approach called parametric spectral clustering (PSC). By extending the
capabilities of spectral clustering, PSC addresses the challenges associated
with big data and real-time scenarios and enables efficient incremental
clustering with new data points. Experimental evaluations conducted on various
open datasets demonstrate the superiority of PSC in terms of computational
efficiency while achieving clustering quality mostly comparable to standard
spectral clustering. The proposed approach has significant potential for
incremental and real-time data analysis applications, facilitating timely and
accurate clustering in dynamic and evolving datasets. The findings of this
research contribute to the advancement of clustering techniques and open new
avenues for efficient and effective data analysis. We publish the experimental
code at https://github.com/109502518/PSC_BigData.

_K_ eywords spectral clustering $\cdot$ incremental clustering $\cdot$ online
clustering $\cdot$ nonlinear clustering

##  1 Introduction

Clustering, as a fundamental technique in various fields such as data mining
and pattern recognition, plays a critical role in analyzing large datasets by
dividing them into smaller and more coherent groups, facilitating the analysis
of large datasets. The importance of clustering is further underscored by its
frequent usage as a preprocessing step for subsequent analyses [1]. Despite
the extensive development of clustering techniques, it remains an active
research area due to its wide-ranging applications and inherent challenges
[2].

Among the various clustering methods, spectral clustering has gained
considerable popularity and demonstrated superior performance. Spectral
clustering has a significant benefit in that it can manage datasets with
patterns that are not linearly separable. This is accomplished by dividing the
data points in a transformed space rather than directly dividing them in the
original feature space. This unique property makes spectral clustering
suitable for a variety of complex applications and domains, and it is often
able to uncover clusters that other clustering techniques are unable to
detect.

Although spectral clustering is a widely used clustering method that has shown
remarkable performance in various applications, it suffers from significant
limitations: its computation time and memory usage are huge, and it cannot
perform incremental clustering. Therefore, it could be challenging to apply
spectral clustering to a large dataset. Furthermore, once a spectral
clustering model is trained, it cannot cluster new data points without
retraining the entire model. These limitations can be critical issues in
applications with big data or when the data streams continuously arrive, and
the clustering results must be updated in real-time.

To overcome these limitations and enable spectral clustering for handling big
data and supporting incremental clustering, this paper presents an innovative
approach called parametric spectral clustering (PSC). Essentially, PSC learns
a parametric function to project data points into low-dimensional
representations. This is a critical step in spectral clustering, although it
requires a lot of computing resources. The approximated low-dimensional
representations of both the new and original data points are then utilized
altogether for clustering.

We evaluate the effectiveness and efficiency of PSC based on real-world
datasets. The experimental results demonstrate that PSC handles big data more
efficiently and enables incremental clustering while maintaining clustering
quality comparable to the standard spectral clustering method. Thus, PSC has
broad applications in various fields with large datasets, such as user
behavior segmentation, social media content grouping, real-time anomaly
detection, and many more [3, 4, 5, 6].

The rest of the paper is organized as follows. Section 2 reviews previous
studies on spectral clustering and incremental clustering. Section 3
introduces the training process, the inference process, and the properties of
PSC. Section 4 presents the experimental results. Finally, Section 5
summarizes our contributions and discusses future research directions.

##  2 Related Work

Spectral clustering leverages the eigenvalues and eigenvectors of a Laplacian
matrix to transform the data into a lower-dimensional but more representative
space, where a base clustering algorithm, such as $k$-means, can be applied to
the transformed data instances. Spectral clustering has been extensively
discussed in the literature, with notable works including [7, 8]. Numerous
variants and enhancements of spectral clustering have been proposed to improve
its robustness and scalability [9, 10, 11, 12].

Incremental clustering (a.k.a. online clustering) addresses the challenge of
clustering large datasets in real-time. Unlike traditional batch clustering,
incremental clustering algorithms continuously cluster new data points (and
possibly update the cluster ID of the original data points) as the new data
points arrive. This incremental property allows efficient handling of dynamic
datasets and enables the detection of evolving patterns. Various approaches
have been proposed for incremental clustering, including stream clustering
algorithms [13, 14] and online clustering methods [15]. Famous algorithms
alone this line includes CluStream [16], DenStream [17], and BIRCH [18].
However, these models are mostly used in the data stream environment and are
sometimes sensitive to the selected hyperparameters. Additionally, studies on
data streams commonly assume that old data points become less important, which
may ease the computation burden and accelerate the computation. However,
gradually retiring old data points may not be a valid assumption in many
cases. A tutorial on online clustering can be found in [19].

Previous studies have addressed the computational challenges associated with
spectral clustering, primarily through approximation or sampling techniques
[20, 21]. In contrast to these methods, our proposed method is distinct by
leveraging the parametric modeling technique, making PSC stand out in
comparison to prior work.

##  3 Methodology

###  3.1 Preliminary: Spectral Clustering

Algorithm 1 Spectral clustering algorithm

1:$\bm{X}=\\{\bm{x}_{1},\ldots,\bm{x}_{n}\\}$: $n$ data points, each
$\bm{x}_{i}\in R^{d}$

2:$p$: the length of the low-dimensional space, $p<d$

3:$\bm{C}=\\{c_{1},\ldots,c_{n}$}: the cluster IDs for the input data points
$\bm{x}_{1},\ldots,\bm{x}_{n}$

4:Compute the similarity matrix $\bm{S}=[s_{i,j}]\in R^{n\times n}$, where
$s_{i,j}$ represents the similarity score between $\bm{x}_{i}$ and
$\bm{x}_{j}$

5:Compute the normalized Laplacian matrix
$\bm{L}=\bm{D}^{-1/2}\bm{S}\bm{D}^{-1/2}$, where $\bm{D}=[d_{i,j}]\in
R^{n\times n}$ is a diagonal matrix with $d_{i,i}=\sum_{j=1}^{n}s_{i,j}$

6:Compute the $p$ eigenvectors $\bm{v}_{1},\ldots,\bm{v}_{p}$ of $\bm{L}$
whose corresponding eigenvalues are the $p$ largest ones and form the matrix
$\bm{V}=[\bm{v}_{1},\ldots,\bm{v}_{p}]\in R^{n\times p}$ (i.e., the columns of
$\bm{V}$ are the eigenvectors)

7:Treat each row in $\bm{V}$ as a data point in $R^{p}$ and apply a clustering
algorithm (e.g., $k$-means) on these data points. The output cluster IDs
$c_{1},\ldots c_{n}$ are that of the data points
$\bm{x}_{1},\ldots\bm{x}_{n}$.

Spectral clustering transforms input data points into a low-dimensional (but
probably more representative) space and clusters the data points in the low-
dimensional space. The transformation uses spectral properties, often
identifying distinctive patterns not easily detected by alternative clustering
algorithms.

The spectral clustering algorithm separates data points according to several
key steps [7]. The algorithm begins by computing a similarity matrix
(typically using the Gaussian kernel as a proxy of the similarity score, which
will be explained in Section 3.2) that captures the pairwise distances between
the input data points. This similarity matrix is the foundation for
constructing a graph representation of the dataset, with the data points
acting as nodes, and the edges and weights reflecting the pairwise
similarities. The algorithm calculates the Laplacian matrix from this graph
representation that captures the relationships among the data points. The next
step involves calculating the eigenvalues and eigenvectors of the Laplacian
matrix. Finally, these eigenvectors serve as the transformed lower-dimensional
representation, where a base clustering algorithm, such as $k$-means, can be
applied. Algorithm 1 provides the pseudocode.

Although spectral clustering is powerful, it requires many computational
resources in terms of time and space. First, the computational demands
associated with spectral clustering are intensive. Tasks such as eigenvalue
decomposition (as seen in line 3 of Algorithm 1) and matrix operations (as
seen in line 2 of Algorithm 1) are computationally expensive and typically
exhibit a time complexity of $O(n^{3})$. Furthermore, the memory requirements
for storing the similarity matrix and performing eigenvalue decomposition can
quickly become prohibitive as the size of the dataset increases with the
complexity of the space of $O(n^{2})$ [21]. These computational and memory
constraints limit the scalability of spectral clustering.

Another limitation of spectral clustering is the lack of support for
incremental clustering. Once the spectral clustering model is trained on a
fixed dataset, incorporating new data points, even just a single data point,
into the existing model without retraining the entire model becomes
challenging. This limitation hinders the application of spectral clustering in
scenarios involving enormous datasets clustering or data stream clustering, as
it becomes impractical to retrain the model whenever new data points arrive in
real-time.

###  3.2 Parametric Spectral Clustering – Training

Algorithm 2 Training procedure of PSC

1:$\bm{X}=\\{\bm{x}_{1},\ldots,\bm{x}_{n}\\}$: $n$ data points, each
$\bm{x}_{i}\in R^{d}$

2:$p$: the length of the low-dimensional space, $p<d$

3:$r$: sampling rate, $0<r\leq 1$

4:A trained model $M$

5:$\nu=\textrm{round}(rn)$

6:Sample $\nu$ data points
$\bm{X}^{\prime}=\\{\bm{x}_{1}^{\prime},\ldots,\bm{x}_{\nu}^{\prime}\\}$ from
$\bm{X}$

7:Compute the similarity matrix $\bm{S}=[s_{i,j}]\in R^{\nu\times\nu}$, where
$s_{i,j}$ represents the similarity score between $\bm{x}_{i}^{\prime}$ and
$\bm{x}_{j}^{\prime}$ (usually using Gaussian kernel)

8:Compute the normalized Laplacian matrix
$\bm{L}=\bm{D}^{-1/2}\bm{S}\bm{D}^{-1/2}$, where $\bm{D}=[d_{i,j}]\in
R^{\nu\times\nu}$ is a diagonal matrix with $d_{i,i}=\sum_{j=1}^{n}s_{i,j}$

9:Compute the $p$ eigenvectors $\bm{v}_{1},\ldots,\bm{v}_{p}$ of $\bm{L}$
whose corresponding eigenvalues are the $p$ largest ones and form the matrix
$\bm{V}=[\bm{v}_{1},\ldots,\bm{v}_{p}]\in R^{\nu\times p}$, i.e., with the
eigenvectors as columns of $\bm{V}$

10:Train a neural network $M$ (structure in Table 1) that maps $\bm{x}_{i}$ to
$\bm{v}_{i*}$ (row $i$ of matrix $\bm{V}$)

Table 1: The structure of a simple neural network that learns to map $\bm{x}_{i}\in R^{d}$ to a smaller vector $\bm{v}_{i*}\in R^{p}~{}(p<d)$. Layer Type | Number of Neurons | Activation Function
---|---|---
Input feature | $d$ | None
First fully connected layer | $n_{1}$ | ReLU
Second fully connected layer | $n_{2}$ | ReLU
Third fully connected layer | $n_{3}$ | ReLU
Fourth fully connected layer | $p$ | None

Parametric spectral clustering consists of two key steps. The first step is
almost identical to the first half of the spectral clustering algorithm. Given
a sampling rate $r~{}(0<r\leq 1)$, we sample $\nu=\textrm{round}(nr)$ data
points
$\bm{X}^{\prime}=\\{\bm{x}_{1}^{\prime},\ldots,\bm{x}_{\nu}^{\prime}\\}$ from
the initially available data points
$\bm{X}=\\{\bm{x}_{1},\ldots,\bm{x}_{n}\\}$. We treat each data point
$\bm{x}_{i}^{\prime}\in R^{d}$ as a node and connect all edges in the graph.
Next, we select a kernel function (typically a Gaussian kernel [7]) to define
$s_{i,j}$ the similarity between two data points $\bm{x}_{i}^{\prime}$ and
$\bm{x}_{j}^{\prime}$. Once the similarity matrix
$\bm{S}=\left[s_{i,j}\right]\in R^{\nu\times\nu}$ is generated, we construct
the Laplacian matrix $\bm{L}$ and compute $\bm{v}_{1},\ldots,\bm{v}_{p}$ the
$p$ eigenvectors of $\bm{L}$ whose eigenvalues are the largest. We create a
matrix $\bm{V}=[v_{i,j}]\in R^{\nu\times p}$ where the $i$th row in matrix
$\bm{V}$ is denoted as $\bm{v}_{i*}$. This matrix $\bm{V}$ is a crucial
component in the subsequent training phase.

The second step aims to train a supervised learning model $M$ that maps a
training instance $\bm{x}_{i}$ to $\bm{v}_{i*}$, the $i$th row of matrix
$\bm{V}$, in which the columns are the $p$ largest eigenvectors of the
Laplacian matrix $\bm{L}$. In other words, the model $M$ learns to project a
data instance onto the directions of the $p$ most important principal
components. We apply a simple multilayer perceptron (MLP) for the model $M$,
whose structure is illustrated in Table 1. However, it can be easily replaced
with other neural networks or supervised learning models.

The training procedure for the parametric spectral clustering algorithm is
given in Algorithm 2.

###  3.3 Parametric Spectral Clustering – Inference

Algorithm 3 Inference (clustering) procedure of PSC

1:$\bm{X}=\\{\bm{x}_{1},\ldots,\bm{x}_{n},\bm{x}_{n+1},\ldots,\bm{x}_{n+m}\\}$:
$n+m$ data points. The first $n$ data points are available initially; the
extra $m$ data points need to be clustered but available after model training

2:A trained model $M$

3:$\bm{C}=\\{\bm{c}_{1},\ldots,\bm{c}_{n},\bm{c}_{n+1},\ldots,\bm{c}_{n+m}\\}$:
the cluste IDs of $n+m$ data points in $\bm{X}$

4:for $i=1$ to $n+m$ do

5: $\bm{u}_{i}\leftarrow M(\bm{x}_{i})$

6:Apply a base clustering algorithm (e.g., $k$-means) to cluster data points
$\bm{u}_{1},\ldots,\bm{u}_{n+m}$. The output cluster IDs
$\bm{c}_{1},\ldots,\bm{c}_{n+m}$ for $\bm{u}_{1},\ldots,\bm{u}_{n+m}$ is that
of the data point for $\bm{x}_{1},\ldots,\bm{x}_{n+m}$

Regarding the inference or clustering phase in PSC, we aim to efficiently
cluster an instance $\bm{x}_{i}$, even if $\bm{x}_{i}$ does not appear in the
initial training data. The model $M$ obtained in the training phase converts
each $\bm{x}_{i}$ into $\bm{u}_{i}$, which serves as an approximation of the
$p$ most significant representations of $\bm{x}_{i}$. Using this
transformation, we can efficiently emulate the computations performed in lines
1 to 4 of Algorithm 1, eliminating the need to construct large similarity and
Laplacian matrices and perform computationally expensive matrix operations and
eigendecomposition. Consequently, we achieve significant computational savings
in time and space but still generate low-dimensional embeddings for the data
points $\bm{x}_{i}$-s that well preserve the main characteristics.

Once each instance $\bm{x}_{i}$ has been transformed into $\bm{u}_{i}$, we
apply a base clustering algorithm, e.g., $k$-means, on $\bm{u}_{i}$-s. The
resulting cluster assignments for $\bm{u}_{i}$-s are then considered cluster
assignments for $\bm{x}_{i}$-s. We follow the convention by employing the
popular $k$-means algorithm as the clustering method for the low-dimensional
data points. However, other base clustering algorithms, e.g., DBSCAN and the
Gaussian Mixture Model, can also be applied.

Algorithm 3 gives the inference/clustering procedure.

##  4 Experiments

###  4.1 Experimental datasets

We conducted experiments on both tabular datasets and image datasets. The
tabular datasets include the famous Iris, Wine, and BreastCancer datasets. The
image datasets include UCIHW, MNIST, and Fashion-MNIST.

###  4.2 A Comparison of Clustering Quality

Table 2: A comparison of the clustering quality of spectral clustering and parametric spectral clustering. We report the mean $\pm$ standard deviation for each score. | SC | PSC
---|---|---
| ClusterAcc | ARI | AMI | ClusterAcc | ARI | AMI
Iris | $0.889\pm 0.00$ | $0.712\pm 0.00$ | $0.77\pm 0.00$ | $0.92\pm 0.025$ | $0.781\pm 0.06$ | $0.813\pm 0.038$
Wine | $0.963\pm 0.00$ | $0.876\pm 0.00$ | $0.855\pm 0.00$ | $0.966\pm 0.02$ | $0.892\pm 0.061$ | $0.875\pm 0.071$
BreastCancer | $0.953\pm 0.00$ | $0.819\pm 0.00$ | $0.732\pm 0.00$ | $0.932\pm 0.018$ | $0.745\pm 0.062$ | $0.632\pm 0.071$
UCIHW | $0.801\pm 0.067$ | $0.743\pm 0.078$ | $0.858\pm 0.026$ | $0.825\pm 0.061$ | $0.764\pm 0.055$ | $0.855\pm 0.026$
MNIST | $0.794\pm 0.04$ | $0.748\pm 0.03$ | $0.842\pm 0.013$ | $0.775\pm 0.046$ | $0.73\pm 0.049$ | $0.839\pm 0.013$
Fashion-MNIST | $0.609\pm 0.015$ | $0.484\pm 0.009$ | $0.644\pm 0.009$ | $0.615\pm 0.041$ | $0.475\pm 0.028$ | $0.634\pm 0.009$
Table 3: The network structure of the autoencoder to convert images in MNIST into embeddings ($w$: width of input image; $h$: height of input image). Layer | Type | Input shape | Output shape | Activation
---|---|---|---|---
1 | Flatten | $(w,h)$ | $w\times h$ | ReLU
2 | Linear | $w\times h$ | 1568 | ReLU
3 | Linear | 1568 | 784 | ReLU
4 | Linear | 784 | 392 | ReLU
5 | Linear | 392 | 49 | None
6 | Linear | 49 | 392 | ReLU
7 | Linear | 392 | 784 | ReLU
8 | Linear | 784 | 1568 | ReLU
9 | Linear | 1568 | $w\times h$ | None
10 | Unflatten | $w\times h$ | $(w,h)$ | None
Table 4: The convolutional neural network structure of the autoencoder to convert images in Fashion-MNIST into embeddings. Layer | Type | Input shape | Output shape | Kernel num | Kernel size | Stride | Padding | with BN | Activation
---|---|---|---|---|---|---|---|---|---
1 | Conv. | $(w,h,1)$ | $(w,h,16)$ | 16 | $5\times 5$ | 1 | Same | True | ReLU
2 | Pooling | $(w,h,16)$ | $(w/2,h/2,16)$ | None | $2\times 2$ | 2 | Valid | False | None
3 | Conv. | $(w/2,h/2,16)$ | $(w/2,h/2,32)$ | 32 | $3\times 3$ | 1 | Same | True | ReLU
4 | Pooling | $(w/2,h/2,32)$ | $(w/4,h/4,32)$ | None | $2\times 2$ | 2 | Valid | False | None
5 | Conv. | $(w/4,h/4,32)$ | $(w/4,h/4,1)$ | 1 | $3\times 3$ | 1 | Same | False | Sigmoid
6 | ConvTrans. | $(w/4,h/4,1)$ | $(w/4,h/4,32)$ | 32 | $3\times 3$ | 1 | Same | True | ReLU
7 | ConvTrans. | $(w/4,h/4,32)$ | $(w/2,h/2,16)$ | 16 | $3\times 3$ | 2 | Double | True | ReLU
8 | ConvTrans. | $(w/2,h/2,16)$ | $(w,h,1)$ | 1 | $5\times 5$ | 2 | Double | False | Sigmoid

We would like to know whether PSC’s clustering result is comparable to SC. We
compare the SC and PSC’s clustering results based on clustering accuracy
(ClusterAcc), adjusted rand index (ARI), and adjusted mutual information
(AMI).

Since the experimental datasets contain ground-truth labels, we use these
labels to evaluate the quality of a clustering algorithm. However, a
clustering algorithm may assign an arbitrary label to each cluster it forms.
Therefore, the standard accuracy computation usually underestimates the
clustering result. For example, given 5 instances with ground-truth labels as
$[1,1,2,2,3]$, if a clustering algorithm assigns their cluster IDs as
$[2,2,3,3,1]$, the standard accuracy computation outputs $0\%$ because none of
the predicted cluster IDs matches the ground-truth labels. However, a careful
reexamination reveals that the clustering is perfect because all instances of
the same ground-truth class belong to the same predicted cluster (and vice
versa). Essentially, if two labeled lists are given, and one can become
another simply by remapping the label IDs, the cluster assignments of the two
lists are identical. In the above example, remapping labels 2 to 1, 3 to 2,
and 1 to 3 for the second list makes the two lists identical. As a result, we
define the clustering accuracy based on the equation below.

$ClusterAcc\left(\bm{y},\bm{\hat{y}}\right):=\max_{\forall{\bm{\check{y}}}\in
P(\bm{\hat{y}})}\left\\{\frac{1}{n}\sum_{i=1}^{n}I\left(\check{y}^{(i)}=y^{(i)}\right)\right\\},$
(1)

where $\bm{y}=[y^{(1)},\ldots,y^{(n)}]$ is the list of ground-truth labels of
size $n$, $\bm{\hat{y}}=[\hat{y}^{(1)},\ldots,\hat{y}^{(n)}]$ is a list of
predicted cluster IDs, $P(\bm{\hat{y}})$ returns a set of all identical lists
for $\bm{\hat{y}}$, $I()$ is an indicator function, and
$\bm{\check{y}}=[\check{y}^{(1)},\ldots,\check{y}^{(n)}]$ is an identical list
of $\bm{\hat{y}}$. In other words, we compute the accuracies based on the
ground-truth label list with all the identical lists of the prediction and
return the largest accuracy score.

In addition to clustering accuracy, we also use ARI and AMI to evaluate the
quality of the clustering results. ARI and AMI are biased towards different
clustering assignments: ARI likes a balanced partition [22], and AMI favors an
unbalanced partition. We report both to fairly assess different situations.

Since both SC and PSC are nondeterministic, executing either multiple times on
a consistent dataset produces varied clustering outcomes. To fairly evaluate
each method, we conduct each experiment 5 times and subsequently present the
mean and standard deviation derived from these 5 trials.

Table 2 gives the three quality measurements for the SC and PSC clustering
results in the six datasets. SC and PSC yield comparable results on all
datasets. Interestingly, PSC sometimes outperforms SC even though PSC
approximates the low-dimensional representations computed by SC. This is
probably because the learning process implicitly introduces regularization
factors so that PSC learns a better mapping.

Raw images are often characterized by complex structures, which hinders the
effectiveness of traditional clustering algorithms. Therefore, we applied an
autoencoder as a preprocessing step to extract the essential information of
each image in the MNIST dataset into a compact vector that captures the
critical patterns in an image. The structure of the autoencoder is shown in
Table 3. We use the bottleneck layer (the output of layer 5 in Table 3) as the
compact representation of the input image. Fashion-MNIST images are more
complicated than MNIST, so we use an image autoencoder to convert images into
vectors so that the spatial structures are reserved. Table 4 gives the
structure of the image autoencoder. We use the output of layer 7 as the
extracted features.

Regarding the hyperparameters, we define $n_{1},n_{2},n_{3}$ (as specified in
Table 1) as follows: 32, 64, 32 for the Iris dataset; 26, 52, 26 for the Wine
dataset; 60, 120, 60 for the BreastCancer dataset; 196, 392, 196 for both the
MNIST dataset and the Fashion-MNIST. While further fine-tuning these
hyperparameters may yield better clustering results, we did not spend much
effort tuning them, as our primary focus is to show that PSC can cluster big
data.

###  4.3 Training Data Size, Clustering Quality, Empirical Execution Time, and
Empirical Memory Usage

Table 5: A comparison of SC and PSC with different sampling ratios in terms of the execution time (seconds), peak memory usage (MB), and clustering quality on the MNIST dataset. Method | Execution time (s) | Peak memory usage (MB) | ClusterAcc | ARI | AMI
---|---|---|---|---|---
SC | 2462 | 5331 | $0.794\pm 0.04$ | $0.748\pm 0.03$ | $0.842\pm 0.014$
PSC $(r=1/6)$ |  Training: $453$ ($\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\downarrow 82\%$) Inference: $0.443\pm 0.027$ |  Training: $1032$ ($\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\downarrow 81\%$) Inference: $92.83\pm 1.965$ | $0.732\pm 0.076$ | $0.684\pm 0.068$ | $0.792\pm 0.03$
PSC $(r=2/6)$ |  Training: $533$ ($\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\downarrow 78\%$) Inference: $0.419\pm 0.088$ |  Training: $1717$ ($\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\downarrow 68\%$) Inference: $92.63\pm 2.09$ | $0.739\pm 0.089$ | $0.68\pm 0.066$ | $0.798\pm 0.02$
PSC $(r=3/6)$ |  Training: $706$ ($\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\downarrow 71\%$) Inference: $0.437\pm 0.048$ |  Training: $2532$ ($\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\downarrow 53\%$) Inference: $96.21\pm 1.785$ | $0.764\pm 0.041$ | $0.712\pm 0.044$ | $0.825\pm 0.016$
PSC $(r=4/6)$ |  Training: $1029$ ($\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\downarrow 58\%$) Inference: $0.379\pm 0.06$ |  Training: $3328$ ($\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\downarrow 38\%$) Inference: $96.54\pm 2.271$ | $0.775\pm 0.046$ | $0.73\pm 0.049$ | $0.839\pm 0.013$
PSC $(r=5/6)$ |  Training: $1472$ ($\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\downarrow 40\%$) Inference: $0.491\pm 0.036$ |  Training: $4937$ ($\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\downarrow 7\%$) Inference: $96.5\pm 2.15$ | $0.819\pm 0.039$ | $0.753\pm 0.023$ | $0.84\pm 0.01$

In Section 4.2, we have demonstrated the quality of SC and PSC clustering
using identical training instances. However, because PSC utilizes a parametric
model to map data points to lower-dimensional representations, there exists an
opportunity to use a subset of the provided data points as training data for
PSC. Here, we investigate the efficiency and effectiveness of PSC utilizing a
subset of training instances.

In particular, this section compares execution time, peak memory consumption,
and clustering quality between SC and PSC, considering the varying rates of
training data sampling for PSC. We use the MNIST dataset in this section for
experiments. Note that applying spectral clustering on the MNIST dataset using
a modern laptop is sometimes infeasible due to the substantial memory
requirements of the modern spectral clustering algorithm. For example, if we
want to cluster the entire MNIST dataset (which contains $70,000$ samples)
using spectral clustering, a naïve implementation requires creating large
matrices (e.g., $\bm{D}$ and $\bm{L}$ in Algorithm 1), each of them with shape
$70,000\times 70,000$. If each entry is a single-precision floating point (4
bytes), a single matrix needs $4~{}\textrm{bytes}\times 70,000^{2}\approx
19.6~{}\textrm{GB}$.

We empirically explore the influence of different training data sampling rates
on the clustering quality, execution time, and memory utilization of
parametric spectral clustering when applied to the MNIST dataset. Table 5
describes the experimental results. First, the training and inference duration
of the PSC is considerably faster than the execution time of the SC. The PSC’s
training process requires only a portion of the training data, which is why it
is faster than SC. The inference time for PSC is almost negligible. Second,
for the same reason, the peak memory utilization during the PSC’s training and
inference stages remains below the SC’s peak memory requirement. The peak
memory consumption is approximated using the memory profiler
mprof.111https://pypi.org/project/memory-profiler/ Third, we study the
connection between the training data sampling rate and the clustering quality
achieved by the PSC. The results demonstrate that increasing the sampling rate
can lead to an improvement in clustering quality. However, the enhancement is
not considerable, and the gap becomes insignificant when the sampling rate
exceeds a certain threshold. In essence, after reaching this threshold, the
incremental benefit arising from including additional training instances
becomes negligible and can significantly increase the cost of training.
Consequently, we conclude that the PSC generates satisfactory clustering
results using more economical training resources without sacrificing
substantial clustering quality.

###  4.4 Quality and Computational Cost of Incremental Clustering

Table 6: The quality and computation cost of incremental clustering when the number of extra instances varies Size of extra instances | Clustering time (s) | Peak memory usage (MB) | ClusterAcc | ARI | AMI
---|---|---|---|---|---
2,000 | $0.569\pm 0.012$ | $239.8\pm 2.949$ | $0.738\pm 0.045$ | $0.675\pm 0.054$ | $0.811\pm 0.022$
4,000 | $0.59\pm 0.026$ | $198.6\pm 3.66$ | $0.74\pm 0.042$ | $0.705\pm 0.022$ | $0.82\pm 0.01$
6,000 | $0.634\pm 0.022$ | $207.9\pm 3.145$ | $0.745\pm 0.071$ | $0.673\pm 0.099$ | $0.816\pm 0.032$
8,000 | $0.681\pm 0.095$ | $262.4\pm 4.366$ | $0.744\pm 0.052$ | $0.705\pm 0.039$ | $0.826\pm 0.018$
10,000 | $0.659\pm 0.058$ | $272.7\pm 3.838$ | $0.795\pm 0.057$ | $0.739\pm 0.072$ | $0.844\pm 0.026$

This section demonstrates the efficacy of PSC in handling incremental
clustering tasks.

We use a subset of $20,000$ instances from MNIST as initial training data to
train the PSC model. Subsequently, we simulate an incremental clustering
scenario by introducing incremental batches of new instances that require
clustering. Specifically, we consider scenarios with additional samples of
sizes $2,000$, $4,000$, $6,000$, $8,000$, and $10,000$. PSC is requested to
cluster the initial $20,000$ instances and the extra samples using the model
trained only on the initial $20,000$ training instances, thus fulfilling the
incremental clustering.

The results of these incremental clustering simulations are presented in Table
6. As the number of newly arrived instances increases, there are slight
changes in both the clustering time and the peak memory usage. This result
validates that the PSC exhibits remarkable efficiency for incremental
clustering tasks. Meanwhile, including more extra instances seems to improve
the clustering quality marginally. We suspect that more instances may reveal a
clearer pattern among different groups, thereby increasing the quality of the
clustering results. On the contrary, SC is not able to manage incremental
clustering. Therefore, even adding a small number of data points requires
complete retraining, which is time consuming and memory intensive.

##  5 Discussion

In this paper, we have proposed an innovative approach called parametric
spectral clustering to address the limitations of traditional spectral
clustering in the handling of large datasets and the support of incremental
clustering. By leveraging a combination of training with a subset of instances
and efficient low-dimensional projection, the PSC achieves efficient
computation and economical memory usage while maintaining competitive
clustering accuracy. Furthermore, we have demonstrated the effectiveness of
PSC through extensive experiments on various datasets. Our results show that
the PSC outperforms traditional spectral clustering regarding computational
efficiency and peak memory usage. Additionally, we have validated the
applicability of PSC in online clustering scenarios, where new data points can
be clustered on the fly without retraining the entire model. Overall, our
contribution extends the application of spectral clustering to domains with
big data and real-time clustering requirements, thus opening up new
possibilities for efficient and effective nonlinear clustering in various
fields.

As an ongoing work, we are developing a user-friendly library that provides a
scikit-learn-like interface for PSC. Users can use PSC with the commands
psc.fit(X) and psc.predict(X) to cluster the data points. This library will
simplify the implementation and usage of PSC, offering seamless integration
with existing machine learning workflows. By providing accessible tools and
resources, we aim to empower a broader range of users, including practitioners
and researchers with varying levels of expertise in machine learning and data
analysis, to explore the potential of PSC in their projects. This will
facilitate greater adoption and further advances in the field, fostering
collaboration and knowledge exchange among the research community.

A potential issue with the PSC is its inefficiency in adapting to data drift.
The computation of a new instance’s ground-truth embedding through
eigendecomposition in spectral clustering makes the acquisition of ground-
truth labels for training targets resource-intensive. Therefore, developing
methods to efficiently manage data drift is a direction we are eager to
explore.

## References

  * [1] Cheng-You Lien, Guo-Jhen Bai, and Hung-Hsuan Chen.  Visited websites may reveal users’ demographic information and personality.  In IEEE/WIC/ACM International Conference on Web Intelligence, pages 248–252, 2019.
  * [2] Jon Kleinberg.  An impossibility theorem for clustering.  Advances in neural information processing systems, pages 463–470, 2003.
  * [3] Ruei-Yuan Wang and Hung-Hsuan Chen.  Detecting inactive cyberwarriors from online forums.  In IEEE International Conference on Web Intelligence, 2023.
  * [4] Guo-Jhen Bai, Cheng-You Lien, and Hung-Hsuan Chen.  Co-learning multiple browsing tendencies of a user by matrix factorization-based multitask learning.  In IEEE/WIC/ACM International Conference on Web Intelligence, pages 253–257, 2019.
  * [5] Dennis Y. Wu, Tsu-Heng Lin, Xin-Ru Zhang, Chia-Pan Chen, Jia-Hui Chen, and Hung-Hsuan Chen.  Detecting inaccurate sensors on a large-scale sensor network using centralized and localized graph neural networks.  IEEE Sensors Journal, 23(15):16446–16455, 2023.
  * [6] Tzu-Heng Lin, Xin-Ru Zhang, Chia-Pan Chen, Jia-Huei Chen, and Hung-Hsuan Chen.  Learning to identify malfunctioning sensors in a large-scale sensor network.  IEEE Sensors Journal, 22(3):2582–2590, 2021.
  * [7] Andrew Ng, Michael Jordan, and Yair Weiss.  On spectral clustering: Analysis and an algorithm.  Advances in neural information processing systems, 14, 2001.
  * [8] Ulrike Von Luxburg.  A tutorial on spectral clustering.  Statistics and computing, 17:395–416, 2007.
  * [9] Jianbo Shi and Jitendra Malik.  Normalized cuts and image segmentation.  IEEE Transactions on pattern analysis and machine intelligence, 22(8):888–905, 2000.
  * [10] Xiaofeng Zhu, Shichao Zhang, Yonggang Li, Jilian Zhang, Lifeng Yang, and Yue Fang.  Low-rank sparse subspace for spectral clustering.  IEEE Transactions on knowledge and data engineering, 31(8):1532–1543, 2018.
  * [11] Romain Couillet and Florent Benaych-Georges.  Kernel spectral clustering of large dimensional data.  2016\.
  * [12] Wen-Yen Chen, Yangqiu Song, Hongjie Bai, Chih-Jen Lin, and Edward Y Chang.  Parallel spectral clustering in distributed systems.  IEEE transactions on pattern analysis and machine intelligence, 33(3):568–586, 2010.
  * [13] Shifei Ding, Fulin Wu, Jun Qian, Hongjie Jia, and Fengxiang Jin.  Research on data stream clustering algorithms.  Artificial Intelligence Review, 43:593–600, 2015.
  * [14] Charu C Aggarwal.  A survey of stream clustering algorithms.  In Data Clustering, pages 231–258. Chapman and Hall/CRC, 2018.
  * [15] Wesam Barbakh and Colin Fyfe.  Online clustering algorithms.  International journal of neural systems, 18(03):185–194, 2008.
  * [16] Charu C Aggarwal, S Yu Philip, Jiawei Han, and Jianyong Wang.  A framework for clustering evolving data streams.  In Proceedings 2003 VLDB conference, pages 81–92. Elsevier, 2003\.
  * [17] Feng Cao, Martin Estert, Weining Qian, and Aoying Zhou.  Density-based clustering over an evolving data stream with noise.  In Proceedings of the 2006 SIAM international conference on data mining, pages 328–339. SIAM, 2006.
  * [18] Tian Zhang, Raghu Ramakrishnan, and Miron Livny.  Birch: an efficient data clustering method for very large databases.  ACM sigmod record, 25(2):103–114, 1996.
  * [19] Jacob Montiel, Hoang-Anh Ngo, Minh-Huong Le-Nguyen, and Albert Bifet.  Online clustering: Algorithms, evaluation, metrics, applications and benchmarking.  In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 4808–4809, 2022.
  * [20] Donghui Yan, Ling Huang, and Michael I Jordan.  Fast approximate spectral clustering.  In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 907–916, 2009.
  * [21] Mu Li, Xiao-Chen Lian, James T Kwok, and Bao-Liang Lu.  Time and space efficient spectral clustering via column sampling.  In CVPR 2011, pages 2297–2304. IEEE, 2011.
  * [22] Simone Romano, Nguyen Xuan Vinh, James Bailey, and Karin Verspoor.  Adjusting for chance clustering comparison measures.  The Journal of Machine Learning Research, 17(1):4635–4666, 2016\.