# Detecting Stance in Tweets : A Signed Network based Approach

Roshni Chakraborty  Indian Institute of Technology PatnaPatnaIndia
<EMAIL_ADDRESS>,  Maitry Bhavsar  Indian Institute of Technology
PatnaPatnaIndia<EMAIL_ADDRESS>,  Sourav Kumar Dandapat  Indian
Institute of Technology PatnaIndia<EMAIL_ADDRESS>and  Joydeep Chandra
Indian Institute of Technology PatnaIndia<EMAIL_ADDRESS>
###### Abstract.

Identifying user stance related to a political event has several applications,
like determination of individual stance, shaping of public opinion,
identifying popularity of government measures and many others. The huge volume
of political discussions on social media platforms, like, Twitter, provide
opportunities in developing automated mechanisms to identify individual stance
and subsequently, scale to a large volume of users. However, issues like short
text and huge variance in the vocabulary of the tweets make such exercise
enormously difficult. Existing stance detection algorithms require either
event specific training data or annotated twitter handles and therefore, are
difficult to adapt to new events. In this paper, we propose a sign network
based framework that use external information sources, like news articles to
create a signed network of relevant entities with respect to a news event and
subsequently use the same to detect stance of any tweet towards the event.
Validation on $5,000$ tweets related to $10$ events indicates that the
proposed approach can ensure over $6.5\%$ increase in average F1 score
compared to the existing stance detection approaches.

##  1\. Introduction

A deeper understanding of the user opinions in Twitter can help in building
automated feedback system that would be useful in applications, like
government surveys (d2019monitoring, ), product reviews and election opinion
polls (lai2018stance, ). Though several sentiment analysis techniques
(mohammad2016sentiment, ; paradis2018visual, ), that mainly classify a piece
of text as positive or negative polarity, have been proposed, stance detection
focuses on identifying the sentiment towards an event from a text. For
example, the tweet Corruption is sucking our country like leeches and has deep
roots, what else other than demonetization could have worked reflects a
negative sentiment but has a positive stance towards the event Demonetization
in India111https://en.wikipedia.org/wiki/2016_Indian_banknote_demonetisation.
Thus, the opinion towards the event may be obfuscated with extraneous
information that makes stance detection a challenging task. Further, events
are often represented through multiple targets222A target is a mentioned
entity (person, name) or a phrase in the text related to an event, towards
which the author of the text expresses either a positive or negative
sentiment. (krejzl2017stance, ) that are either used to express positive or
negative sentiment towards the event. For example, sudden demonetization of
certain currency notes in India in 2016 led to long ATM queues but was
expected to increase the economic progress of the country. Both of these
italicized phrases became representative target keywords of the event and were
frequently used to express sentiment with respect to the event. Certain tweets
supporting Demonetization in India specifically mentioned positively about the
possible economic growth, whereas those against it made negative mentions
about the long queues and sufferings of the people. Thus, stance detection in
tweets towards an event initially requires identification of the possible set
of representative targets related to the event and the underlying polarity
between the targets and the event and is different from identifying user
stance towards an event. Further, the usage of non-vocabulary words, inherent
noise, abbreviations, sarcasm (tsagkias2011linking, ) and absence of
contextual information in tweets makes it a challenging job to detect stance
from tweets.

To handle these issues, existing research works on stance detection in tweets
rely on supervised or weakly supervised based approaches. Existing supervised
approaches (shenoy2017performing, ; dey2017twitter, ) often rely on manually
curated features, like target specific bag of words, event associated
sentiments from the training set to determine stance of the tweets. However,
these approaches require event-specific training data and predefined knowledge
of the targets and thus, fail to provide a generic framework that can be
adapted to newer set of events. Though existing weakly supervised algorithms
reduce this dependency by using contextual information extracted from twitter
handles of political personalities and hashtags, their accuracy diminishes
when the pre-defined targets are not mentioned in the tweet texts
(du2017stance, ). Therefore, recent works (du2017stance, ) incorporate target
specific embedding information to capture the stance related to a target with
better accuracy. These existing approaches mostly consider predefined set of
targets whose polarity towards an event is known apriori. However, such
approach is not suitable for events where number of targets is huge and manual
identification is difficult. Therefore, we intend to develop an automated
stance detection system which can identify the targets automatically. However,
implementing such a system would require addressing several challenges, such
as identification of the targets of the event and automatic determination of
polarity of those targets towards the event. We discovered recent works that
consider the presence of multiple targets, however these works consider a very
small set of specific targets, like Hillary Clinton, Donald Trump, Ted Cruz
and Bernie Sanders whose political alignment are already known (e.g., Hillary
Clinton and Donald Trump are always likely to oppose each other irrespective
of the event) (sobhani2017dataset, ; wei2018multi, ) or require target
specific training for deep learning based frameworks. However, it is highly
difficult to attain target specific annotated dataset when the number of
targets increase. Thus, we need to develop an automated stance detection
technique which does not require target specific annotated dataset and can
address these challenges.

In this paper, we propose a generic framework for automated stance detection
that exploits extraneous information sources, like news articles, to identify
the possible targets of the event. We create a signed network of the targets
associated with the event that can be effectively used to determine the
polarity relationship with the event. The novelty of our proposed approach is
in identifying the relevant targets from the articles and generating the
signed network representing the polarity of these targets towards the event or
among themselves. The signed network representation of an event provides a
holistic view of the polarity relationships of a set of targets towards the
event which aids in identifying the stance of the tweet. Further, for those
set of targets whose polarity relationship towards the event is not directly
evident, the signed network representation provides a way to capture the same
through application of network theoretic concepts. Identifying the stance of a
tweet towards the most closely mapped targets in the signed network helps in
identifying the stance expressed through the tweet. We rigorously validate our
proposed approach on $5,000$ tweets related to $10$ different events. Our
investigations reveal that the proposed approach can ensure over $6.5\%$
increase in average F1 score than the existing approaches. The organization of
the paper is as follows: We discuss few preliminaries related to the proposed
approach in Section 2 followed by the related works in Section 3. In Section
4, we present a formal definition of the problem followed by our proposed
approach in Section 5. We discuss the experimental settings in Section 6 and
the observations in Section 7. We finally draw our conclusions in Section 8.

##  2\. Definitions

In this Section, we describe some of the terminologies that have been
frequently used in the paper. As these terminologies are already discussed in
existing works, we highlight them for the ease of the readers.

  * •

Target : A target is a mentioned entity (person, name) or a phrase in the text
related to an event, towards which the author of the text expresses either a
positive or negative sentiment (krejzl2017stance, ). We refer to the phrases
that are used as targets as key-phrases and the entity as key-players in this
paper.

  * •

Polarity Relationship : We consider the polarity of a target towards an event
as positive if it is used to express a positive opinion about the event, and
negative otherwise. The polarity between two targets is assumed to be positive
if they are used to reflect a similar opinion about the event. For example,
the target phrase ”crackdown on black money hoarders” is considered as a
positive effect of demonetization and hence would have a positive polarity
towards the event, whereas target key-phrase like long ATM queues would have a
negative polarity. The polarity of the relationship between these key-phrases
would be negative as they are used to reflect two different opinions about the
event. The polarity of the relationship of a key-player towards an event would
be positive if the key-player supports the event and negative otherwise.

  * •

Signed Network : It is a network in which each edge either has a positive or a
negative sign (leskovec2010signed, ), reflecting the polarity of the
relationship among the connected nodes.

  * •

Structural Balance of a Network : A signed network is said to be structurally
balanced if it can be divided into two groups, where the edges connecting
nodes of a same group are always positive and those connecting nodes in
different groups are negative (cartwright1956structural, ).

##  3\. Related Works

There is a plethora of research works that determine stance from long texts
like debates and discussions through feature based machine learning as well as
deep learning techniques (mohtarami2018automatic, ; rajendran2018stance, ;
zhang2018ranking, ; ruder2018360, ). Existing feature driven research works
consider textual features (rajendran2018something, ), contextual features
(anand2011cats, ; hasan2013stance, ), author’s opinion history and interaction
patterns (hasan2012predicting, ; trabelsi2018unsupervised, ), deep learning
models (mohtarami2018automatic, ). However applying these methods directly to
detect stance from social media contents, like Twitter, is difficult due to
the absence of contextual information, presence of noise and usage of informal
language (tsagkias2011linking, ). Thus, we discuss the major works detecting
stance on tweets related to different methodology next.

###  3.1. Supervised Approach

Existing supervised techniques have studied the use of both feature driven
machine learning algorithms (mourad2018stance, ; siddiqua2018stance, ) and
deep learning models (wei2018multi, ; ma2018detect, ) to detect stance from
short length texts. Existing feature based machine learning algorithms
consider several features like the language components (skeppstedt2016active,
; simaki2018detection, ), content attributes(n-grams, hashtags and named
entities) (kuccuk2018stance, ; wojatzki2016ltl, ), interactions between
sentiment-stance-input variables (ebrahimi2016joint, ), word co-occurrences
(chuang2015stance, ), presence of claims (bar2017stance, ), contextual
information (sasaki2016stance, ; lai2016friends, ; wojatzki2016ltl, ), user
previous information (sasaki2018predicting, ), and target specific bag of
keywords (shenoy2017performing, ; patra2016ju_nlp, ). Creating target specific
keywords is widely used in stance detection and different mechanisms have been
proposed to generate the same. While Shenoy et al. (shenoy2017performing, )
create a target specific bag of POS-tagged keywords along with sentiments,
Patra et al. (patra2016ju_nlp, ) create target-specific topic bags that
include dependency information among lexicons and hashtags to detect stance in
tweets. Various machine learning frameworks, like an ensemble of classifiers
(liu2016iucl, ) and character level and word level CNN
(vijayaraghavan2016deepstance, ) have been proposed. However, most of these
existing approaches fail to detect stance related to multiple targets. Recent
deep learning approaches have proposed attention mechanisms (wei2018multi, ;
du2017stance, ; gao2018stance, ) or ensemble of several neural models
(sobhani2017dataset, ; sobhaniexploring, ) identify stance related to multiple
targets. However, these approaches consider a very small predefined set of
targets who shares similar polarity relationship irrespective of an event,
like Hillary Clinton, Donald Trump and Bernie Sanders, thus making it
inapplicable for stance detection of tweets towards an event which might
comprise of a large number of possible targets and further, the polarity
relationship between the targets related to an event varies across events
(contrary to the assumption of the existing works).

Therefore, stance detection approaches that rely on supervised algorithms are
highly dependent on event-specific labeled data and hence, fail to provide a
generic framework to detect stance in tweets. Further, these approaches
utilize a set of event related tweets or a predefined list of targets related
to an event which cannot cover the entire range of possible targets related to
the event or their polarity relationships and thus, fail to ensure stance
detection of tweets related to an event. Our empirical analysis indicates that
there could be a large number of possible targets related to an event (as
shown in table 4) which is difficult to be captured by the existing supervised
research works on stance detection of a tweet. Further, most of the existing
works don’t consider capturing the polarity of the target towards an event
which is of high importance.

###  3.2. Weak Supervised Approach

Existing supervised learning approaches require huge annotated data related to
each event for effective stance detection in tweets. In order to reduce this
dependency on labeled dataset, there is a line of research works that have
proposed machine learning frameworks that require weak supervision. Weak
supervised stance detection works rely on different characteristics related to
an event, like stance related information from annotated hashtags
(dias2016inf, ; misra2017semi, ; krejzl2016uwb, ), user behavior and
information (klenner2017stance, ; rajadesingan2014identifying, ;
fraisier2018stance, ), specific key-phrases related to events
(johnson2016identifying, ) and topical information (dey2018topical, ).
However, all of these approaches require annotated event-specific twitter
handles, hashtags or key-phrases. Further, as these proposed approaches are
largely dependent on the annotated hashtags and twitter handles, it can’t
ensure complete coverage of all the related targets towards the event.
Further, most of these approaches rely on event-specific keywords,
relationships among targets and sentiment dictionary that might require
significant manual annotation.

Several deep learning based frameworks which require less amount of labelled
information than the supervised deep learning approaches has been proposed,
like convolutional neural network (wei2016pkudblab, ) that utilizes word
embedding from Google News database and bidirectional LSTM model
(augenstein2016stance, ) utilizes stance related to a target to determine
stance related to different targets. Although this approach can detect stance
from tweets even when the target name is not explicitly mentioned, it is
applicable only for targets for whom the polarity is already known, like
Hillary Clinton and Donald Trump who mostly belong to different polarity
irrespective of the event. However, an event might have a large set of
possible targets and their polarity among themselves and also with the event
might differ across the events and hence, knowledge about very specific
targets can’t ensure stance detection in tweets related to any event. Further,
the deep learning frameworks do require event specific training data which
makes it dependent on user intervention and event specific knowledge for it’s
applications.

Thus, none of the existing research works that detect stance from tweets
provide a generic mechanism which does not require event specific labeled
dataset. Information extracted from annotated twitter handles, labeled
training set or stance specific hashtags can not cater to the huge vocabulary
diversity related to an event. Further, most of the existing works do not
consider the polarity relationship between the targets or the target with the
event which makes it inapplicable to detect stance of a tweet related to an
event. Although few recent research works incorporate an understanding of the
polarity between multiple targets, they consider a very small set of pre-
defined targets, like Hillary Clinton and Donald Trump making it inapplicable
for stance detection in tweets towards an event which comprises of a huge set
of possible targets and different polarity relationships. Therefore, we
propose a generic framework that can automatically identify the possible set
of targets related to an event and the underlying relationship (positive or
negative) of those targets towards the event. Extraction of this knowledge and
representation through a signed network ensures detection of stance in tweets
with high accuracy irrespective of the inherent limitations of tweets, like
absence of contextual information and presence of inherent noise in tweets. We
discuss the proposed approach in details in section 5 and provide a formal
definition of the problem along with an overview of the proposed approach
next.

Event | $K_{p_{T}w}$ | $K_{l_{T}w}$ | $Tw$ | $K_{p}$ | $K_{l}$ | $Nw_{st}$
---|---|---|---|---|---|---
$E_{1}$ | 28 | 18 | 5000 | 37 | 110 | 612
$E_{2}$ | 22 | 35 | 5000 | 102 | 112 | 1720
$E_{3}$ | 53 | 27 | 5000 | 73 | 34 | 987
Table 1. The number of targets extracted from tweets($Tw$) and news
articles($Nw$) related to each of the $10$ events is shown. The target set
related to an event extracted from news article sentences($Nw_{st}$) are key-
phrases as $K_{p}$ and key-players as $K_{l}$ respectively and those from
tweets are key-phrases as $K_{p_{T}w}$ and key-players as $K_{l_{T}w}$.

##  4\. Overview of the Problem

Assuming an event $E$ and a set of tweets $Tw$ related to $E$, the objective
is to find the stance (positive, negative or neutral) of each tweet ($Tw_{z}$)
in $Tw$ with respect to $E$. Therefore, we assume that the event $E$ is
associated with unknown targets, $g_{1},g_{2},\ldots,g_{m}$, each of which has
certain polarity (positive or negative) towards $E$ and $Tw_{z}$ mentions a
subset of these targets. If $\mathcal{S}(Tw_{z},g_{i})$ denotes the sentiment
(positive, negative or neutral) of the tweet $Tw_{z}$ towards $g_{i}$, and
$\mathcal{R}(E,g_{i})$ represents the polarity of the relationship of $g_{i}$
towards the event $E$, then the stance, $\mathcal{X}(Tw_{z},E)$ of $Tw_{z}$
towards $E$ would be represented as

(1)
$\displaystyle\mathcal{X}(Tw_{z},E)=\mathcal{S}(Tw_{z},g_{i})\mathcal{R}(E,g_{i})$

As evident from Equation 1, the stance of a tweet is positive if either the
tweet reports positively about a target that is positively related to the
event (both $\mathcal{S}(Tw_{z},g_{i})$ and $\mathcal{R}(E,g_{i})=positive$),
or it reports negatively about a target that in turn is negatively related to
$E$ (both $\mathcal{S}(Tw_{z},g_{i})$ and $\mathcal{R}(E,g_{i})=negative$).
Thus, our stance detection approach consists of three major sub-tasks:

  1. (1)

Identification of the targets of the event.

  2. (2)

Identification of the polarity relationship among the targets and the event.

  3. (3)

Identification of the sentiment expressed through a tweet towards the target.

As already discussed, the targets related to an event can either be a phrase
or an entity and there can be a number of possible targets related to the
event. Identifying the targets directly from the tweets requires automatic
determination of the relevance of a target towards an event from the tweet
text. For that, we require manual labeling the appropriate targets which is
extremely tedious and requires a huge volume of tweets to capture all the
relevant targets. To validate this claim, we conducted a study in which we
simultaneously applied our proposed target extraction approach (details in
Section 5.1) on $5000$ tweets and news articles related to an event. We
considered $3$ different events for this study. Our observations as shown in
Table 1 indicate a small fraction of the targets could be identified from the
tweets as compared to the news articles. To investigate whether this
difference can be reduced by increasing the size of the tweet set, we
increased the tweet set size to $22,000$ for each of the $3$ events. We did
not observe any significant change in the number of targets identified. These
observations motivated the use of external information sources, like, news
articles to identify the targets. We intuitively believe as the sentences in a
news articles are more focused towards the event than the tweets, it helps in
precise identification of the targets. We propose a a signed network based
approach to determine the polarity relationship of the targets which could be
eventually to identify the stance of a tweet. An outline of the steps of the
proposed approach is provided in Figure 1 and we describe each of the steps in
details next.

Figure 1. Block Diagram Representing the Proposed Approach

##  5\. Proposed Approach

In this Section, we discuss the proposed approach in details.

SNo | Tweet | Target | Stance
---|---|---|---
1 |  9cmThis is a major step by BJP government to remove black money | BJP government | Positive
2 |  9cmcashless transactions has reduced Terrorism | cashless transactions | Positive
4 |  9cmnote ban has caused huge collateral damage to the Indian economy | note ban | Negative
5 |  9cm Mamata claims Modi is looting people’s money by note ban | Mamata | Negative
Table 2. Tweets that indicate stance related to the event Demonetization in
India but does not comprise of the event name in the tweet are shown.

###  5.1. Identification of Targets of the Event

Identifying the targets with respect to a news event is important for stance
detection. There are several challenges, like high diversity of the keywords
in the tweets and presence of a large number of possible targets for an event
and the targets mentioned in the tweets can either be key-phrases or key-
players related to the event. In Table 2, we show few example tweets related
to the Demonetization event. We discuss how we automatically extract the key-
phrases and the key-players with respect to an event next.

Extraction of key-phrases: We use RAKE (rose2010automatic, ), a key-phrase
technique that computes the importance score of the phrases based on the
importance of the constituent words with respect to the event and their co-
occurrence frequency. If $w_{1}$, $w_{2}$,…$w_{m}$ be the constituent words in
the phrase $P_{p}$, then the phrase importance score, $I(P_{p})$ would be
given as

(2) $\displaystyle I(P_{p})$ $\displaystyle=f(P_{p})*\sum_{i=1}^{m}g(w_{i})$

where, $f(P_{p})$ represents the frequency of co-occurrence of the words of
$P_{p}$ in the news article and $g(w_{i})$ represents the frequency of the
word $w_{i}$ in the news article. We select the phrases which have an
importance score higher than the threshold $\theta_{p}$ (i.e., $I(P_{p})$
$\geq$ $\theta_{p}$) as the key-phrases, $K_{p}$ of the event. The choice of
the threshold is determined based on a manual study by $3$ different
annotators on around $1270$ phrases selected from news articles of $3$
different events. We asked the annotators to identify those phrases that could
be considered as key-phrases, without looking at their importance scores. We
observed that the importance scores that are one standard deviation greater
than the mean can be considered as target key-phrases. In Table 3, we show the
number of phrases extracted by RAKE, the number of key-phrases which have an
importance score higher than the threshold along with the maximum, mean and
the standard deviation of the importance score of the phrases (details of the
events are given in Section 6.1). We show the key-phrases through word cloud
in Figure 2.

Event | $p$ | $K_{p}$ | Max $I(P_{p})$ | Mean $I(P_{p})$ | SD $I(P_{p})$
---|---|---|---|---|---
$E_{1}$ | 147 | 37 | 7.04 | 2.13 | 1.08
$E_{2}$ | 702 | 102 | 12.50 | 2.41 | 1.68
$E_{3}$ | 417 | 73 | 12.29 | 2.23 | 1.45
Table 3. The number of phrases extracted by RAKE, the number of key-phrases
which have an importance score higher than the threshold, maximum importance
score, average importance score and the standard deviation of the importance
score of the phrases related to $3$ events is shown.

Extraction of key-players: We use SpaCY333honnibal.github.io/spaCy tool to
extract the names of all the persons who have featured in the news articles
related to the event. The set $K_{l}$ comprises of all the collected names is
the key-players set of the event. We form the possible set of targets of the
event as the set of key-phrases and key-players identified related to an
event. In Table 4, we show the number of key-phrases ($K_{p}$) and key-players
($K_{l}$) identified for $10$ events (the details of the events is discussed
in Section 6.1). We next discuss the procedure to identify the polarity
relationship of the targets towards the event.

$E$ | $K_{p}$ | $K_{l}$ | $E$ | $K_{p}$ | $K_{l}$
---|---|---|---|---|---
$E_{1}$ | 37 | 110 | $E_{6}$ | 58 | 28
$E_{2}$ | 102 | 112 | $E_{7}$ | 27 | 37
$E_{3}$ | 73 | 34 | $E_{8}$ | 82 | 63
$E_{4}$ | 20 | 32 | $E_{9}$ | 46 | 68
$E_{5}$ | 67 | 33 | $E_{10}$ | 73 | 64
Table 4. The number of targets, i.e., $K_{p}$ and $K_{l}$, related to each of
the $10$ events is shown.

###  5.2. Identification of polarity of a target towards the event

We adopt a two-pass method to extract the relationships among targets. In
Pass-I, we utilize the news articles to extract either $a)$ directly the
polarity of a target towards the event or, $b)$ the polarity of a target
towards another target. Due to the inherent complexity of the sentences, it is
very challenging to capture the polarity relationships of all the targets
toward the event. Therefore, in Pass-II, we create a signed network of the
targets from the relations derived in Pass-I and then, determine the polarity
relationship of the unresolved targets by structural balance theory
(cartwright1956structural, ; derr2018signed, ). Therefore, the proposed
approach integrates the knowledge from the textual contents and signed network
based concepts to identify the polarity of targets towards an event. We
discuss in details each of these steps next.

####  5.2.1. Pass-I: Identifying target polarity based on sentence types

In a sentence, the polarity relationships can be identified depending on the
type of speech (direct or indirect speech) and the sentence type (simple,
compound or complex). For example, in a simple sentence like INC party to
begin nationwide campaign against demonetization, the polarity relation
between target INC and the event demonetization could be directly established
by lexicon based sentiment analysis by Taboada et al. (taboada2011lexicon, ).
However, for complex sentences, requires understanding of the conjunction and
the clauses present in the sentence to extract the polarity relationship
(savanur2017feature, ). Further, extraction of polarity relationships from
direct or indirect speech requires both identification of the speaker and his
view expressed through the speech.

In Pass-I, we initially identify sentences that are direct or indirect
speeches by the presence of reporting verbs (an exhaustive list of reporting
verbs is given by Krestel et al. (krestel2008minding, )) and further,
segregate the speech into either direct or indirect speech based on the
presence of quotes and finally, classify each sentence which are neither
direct nor indirect speech into simple, complex or compound sentences based on
the clauses and the conjunctions present in the sentence following the
approach proposed by Puscaso et al. (puscasu2004multilingual, ).

Simple Sentences: As a simple sentence has only one main clause, we directly
use the lexicon based approach proposed in Taboada et al. (taboada2011lexicon,
) on the extracted clause to determine the polarity of a target towards the
event or towards another target present in the clause by capturing the
polarity of the sentence towards the subject. We calculate the polarity of the
sentence by the semantic orientation which considers both polarity and
strength of each lexicon of the sentence. The semantic orientation of each
lexicon is calculated on the basis of Semantic Orientation CALculator (SO-CAL)
444http://www.cs.sfu.ca/ sentimen/socal/login.php?page=111 that considers both
the strength and polarity of each lexicon, presence of intensifiers in the
neighborhood, like most and slightly either increase or decrease,
respectively, the semantic orientation of the lexicon and the presence of
negations reverse the polarity of the lexicon. Thus, if
$w_{1},w_{2}\ldots,w_{n}$ represent the lexicons in a sentence, $s$, and have
semantic orientations as $S(w_{1}),S(w_{2}),\ldots,S(w_{n})$ respectively,
then the semantic orientation, $S(s)$, is given as

(3) $\displaystyle S(s)$ $\displaystyle=\sum_{i=1}^{n}S(w_{i})$

$S(w_{i+1})$ is also affected by the presence of intensifier or negation as
$w_{i}$. If $w_{i}$ is an intensifier or negation, then the following rule
applies for calculating $S(w_{i+1})$:

Itensifier : An intensifier can either be an amplifier or downtoner. When
$w_{i}$ is an amplifier with an amplifier score of $I(w_{i})$, then the
semantic orientation of $w_{i+1}$ is increased by
$S(w_{i+1})\frac{I(w_{i})}{100}$ and would be given as
$S_{w+1}(1+\frac{I(w_{i})}{100})$. For example, if $w_{i}$ is the lexicon very
which is an amplifier and $I(very)$ is $+25$ and the lexicon(i.e., $w_{i+1}$)
is good with $S(good)$ being $+3$, then $S(very$ $good)$ is calculated as
$S(good)*(1+I(very)/100)$ which is $3*(1+0.25)$, i.e., $+3.75$. Similarly,
when $w_{i}$ is a downtoner, then then the semantic orientation of $w_{i+1}$
is decreased by $S(w_{i+1})\frac{I(w_{i})}{100}$.

Downtoner :When $w_{i}$ is a negation, then the semantic orientation of
$w_{i+1}$ is decreased by the semantic orientation of $w_{i}$, and would be
given as $S(w_{i+1})-S(w_{i})$. For example, if $w_{i}$ is the lexicon not
which is a negation with $S(not)=4$ followed by the lexicon good (i.e.,
$w_{i+1}$) with $S(good)$ being $+3$, then $S(not$ $good)$ is calculated as
${S(good)-S(not)}$ which is $(3-4)$, i.e., $-1$. To calculate the semantic
orientation of the sentence $s$, we calculate the semantic orientation of the
constituent lexicons $w_{i}$ and apply equation 3 to derive the semantic
orientation of the sentence, $S(s)$ that represents the polarity relationship
between the subject and the object in $s$. Therefore, if ($S(s)>0$), then the
polarity between the subject and the object is taken as positive and if
($S(s)<0$), then the polarity between the subject and the object is taken as
negative. The subject and the object represents either a pair of targets or a
target and the event respectively.

Compound and Complex Sentence: Determination of the polarity relationship from
a compound or complex sentence requires understanding of the present clause
and conjunction. We rely on the approach proposed by Puscasu et al.
(puscasu2004multilingual, ) to identify the clauses, identify the sentiment of
each clause by (taboada2011lexicon, ). We, finally, follow Savanur et al.
(savanur2017feature, ) to determine the clause boundaries and then, identify
the polarity relationship of the sentence on the basis of the rules regarding
each conjunction. We summarize the rules (savanur2017feature, ) that we follow
in Table 5. Although there can be other conjunctions that are not mentioned in
the table 5, we consider only these mentioned conjunctions. For example,
complex sentences that express cause-effect relations, like sentences with the
subordinating conjunction, because requires understanding of only the effect
relation (by rule $1$ in table 5).

Direct and Indirect Speech: For sentences that express direct or indirect
speech, we identify the speaker and the polarity of the speaker towards the
subject mentioned in the reporting clause. We identify the speaker from direct
or indirect speech by Krestel et al. (krestel2008minding, ) and use Taboada et
al. (taboada2011lexicon, ) to calculate the polarity. Although the reporting
clause might be a complex or compound sentence, the proposed approach
considers only those direct and indirect speech in which the reporting clause
is a simple sentence.

No | Conjunction | Sentence | Rule
---|---|---|---
1 |  3cmcause and effect relation shown by because, as, since |  6cmBihar CM supported Demonetization because he believed it could curb corruption. |  3cmconsider the effect relation
2 |  3cmalthough, though |  6cmAlthough the opposition parties have different ideologies, they are united against Prime Minister Modi. |  3cmconsider the subordinate clause
3 |  3cmbut, yet |  6cmAll opposition parties may march separately, but they have attacked the demonetization move together |  3cmconsider the clause following but or yet conjunction
4 |  3cmand, or |  6cmDemonetization has caused political disappointment and people are frustrated waiting in the long queues at ATM |  3cmconsider both the clauses
5 |  3cmrelative clauses shown by who, which, whom, that, whose |  6cmPeople in villages don’t trust cashless transactions which Modi is advertising for. |  3cmconsider the main clause
Table 5. The rules related to different types of conjunctions as discussed in
existing research works (savanur2017feature, ) and (puscasu2004multilingual, )
are shown here.

Our observations on $10$ events (with article count varying from $10$ to $86$
for each event) reveal that the percentage of targets whose polarity
relationship towards the event is resolved by Pass-I varies from $14-62.5\%$
(as shown in Table 6). Therefore, we observe that we could resolve the
polarity for a significant proportion of the targets which we resolve by
creating a signed network of the targets and the event.

####  5.2.2. Pass-II: Identifying target polarity using signed network
analysis

We propose utilization of structural balance theory (cartwright1956structural,
) in signed networks to resolve the polarity of those targets which could not
be resolved in Pass-I towards the event. Structural balance theory in
sentiment networks (rawlingSociology2017, ) shows that these networks move
towards specific structural configurations over time. The structural balance
theory (burt2000network, ; leskovec2010signed, ; cartwright1956structural, )
states that the structural balance of a triad micro-structure in the network
is determined by the configurations of the positive and negative relations
among the nodes in the triad where positive relations signify friends and
negative relations as enemies. Further, a sentiment network is said to be
structurally balanced if it holds all the following properties:

  1. (1)

($P_{1}$) A friend of a friend is friend

  2. (2)

($P_{2}$) A friend of an enemy is enemy

  3. (3)

($P_{3}$) An enemy of a friend is an enemy

  4. (4)

($P_{4}$) An enemy of an enemy is a friend

Each of the properties of structural balance triads can be directly applied to
determine the polarity relationship of certain targets, whose individual
polarity relationships with the event are not known. For example, if a target
$g_{i}$ shares a positive polarity with another target $g_{j}$ whose polarity
relationship towards the event is known, then based on properties $P_{1}$ and
$P_{3}$ of the balance model, $g_{i}$ would share the same polarity
relationship with $E$ as $g_{j}$. On the other hand if $g_{i}$ shares a
negative polarity with $g_{j}$, then based on properties $P_{2}$ and $P_{4}$
its polarity relationship towards $E$ would be opposite to that of $g_{j}$.
This is quite intuitive in the sense that a positive polarity between targets
$g_{i}$ and $g_{j}$ implies that they are used to convey the same sentiment
towards the event, hence the polarity relationship of $g_{i}$ towards $E$
would be the same as $g_{j}$ itself. On the other hand, a negative polarity
between targets $g_{i}$ and $g_{j}$ indicates that they are used to convey
different opinions and hence, $g_{i}$ must share a different polarity towards
$E$ as $g_{j}$. We use the signed network to derive the polarity relation
$\mathcal{R}(E,g_{i})$ of a target $g_{i}$ towards the event, $E$, for cases
where the same could not be derived directly from Pass-I, if $g_{i}$ satisfies
one of the following cases:

  1. (1)

Target $g_{i}$ is not directly connected to $E$ but is connected to another
target $g_{j}$ that in turn is connected to $E$ .

  2. (2)

Target $g_{i}$ is connected to $E$ through a path
$g_{i},g_{i+1},g_{i+2},\ldots,g_{i+k}$, where the polarity of relationship
between targets $g_{i}$ and $g_{i+1}$ is known.

We maintain the properties of structural balance in the target network and use
the following construct rules to derive the polarity relationships of the
target $g_{i}$ towards the event.

Case 1 : Based on properties $P_{1}$ to $P_{4}$, the polarity
$\mathcal{R}(E,g_{i})$ of $g_{i}$ towards $E$ would be given as

(4) $\displaystyle\mathcal{R}(E,g_{i})$ $\displaystyle=$
$\displaystyle\mathcal{R}(g_{i},g_{j})\mathcal{R}(E,g_{j})$

Case 2 : To determine the polarity of relation of target $g_{i}$ towards $E$,
we use a method proposed in (kim2018side, ). We add a hypothetical edge from
each of the targets $g_{i}$, $g_{i+1}$, …, $g_{i+k-1}$ to event $E$. Thus,
again based on the properties $P_{1}$ to $P_{4}$, the polarity of relationship
of $g_{i}$ towards $E$ would then be given as

(5) $\displaystyle\mathcal{R}(E,g_{i})$ $\displaystyle=$
$\displaystyle\mathcal{R}(g_{i},g_{i+1})\mathcal{R}(E,g_{i+1})$
$\displaystyle=$
$\displaystyle\mathcal{R}(g_{i},g_{i+1})\mathcal{R}(g_{i+1},g_{i+2})\mathcal{R}(E,g_{i+2})$
$\displaystyle=$
$\displaystyle\mathcal{R}(g_{i},g_{i+1})\cdots\mathcal{R}(g_{i+k-1},g_{i+k})\mathcal{R}(E,g_{i+k})$

We next prove using a theorem that the polarity relationships derived using
the above construct rules clusters the network into two groups of positively
connected targets, where the polarity of all the targets of one group is
positive towards $E$ and those in the other group have negative polarity
towards $E$. This also implies that the polarity relation between a pair of
targets in two different groups would always be negative.

###### Theorem 5.1.

Following the construct rules of cases $1$ and $2$, if the target network is
clustered into 2 groups, $G^{+}$ and $G^{-}$, based on the polarity relation
$\mathcal{R}(E,g_{i})$ of the nodes $g_{i}$ being $(+)ve$ or $(-)ve$,
respectively, then if for any two target nodes $g_{i}$ and $g_{j}$,
$\mathcal{R}(g_{i},g_{j})$ is $(+)$ve then $g_{i},g_{j}\in G^{+}$ (or
$G^{-}$).

Proof If $\mathcal{R}(g_{i},g_{j})$ is $(+)$ve then based on equation 4,
$\mathcal{R}(g_{i},g_{j})=\frac{\mathcal{R}(E,g_{i})}{\mathcal{R}(E,g_{j})}>0$,
thus indicating that both $\mathcal{R}(E,g_{i})$ and $\mathcal{R}(E,g_{j})$
must both be either positive or negative. Thus both $g_{i}$ and $g_{j}$ would
either belong to $G^{+}$ or $G^{-}$.

The above theorem implies that by observing the mutual polarity relation
between any pair of targets we can determine the polarity relation with
respect to the event if it shares only either positive or negative polarity
relationship with one or more targets in the same group. We investigate the
effectiveness and accuracy of the proposed approach in Section 7. We observe
that nearly $88-94\%$ of the targets’ polarity could be resolved by combining
Pass-II with Pass-I as shown in Table 6. Therefore, our observations highlight
the importance of unifying information from both the news articles and
structural balance theory of signed networks to resolve the polarity of the
targets of an event. We next discuss the final step whereby we extract the
sentiment of the tweet towards one or more targets and use the polarity
relationships of the targets to derive the stance of the tweets.

Event | Pass-I | Pass-II | Unresolved Links
---|---|---|---
$E_{1}$ | 0.527 | 0.428 | 0.04
$E_{2}$ | 0.14 | 0.76 | 0.10
$E_{3}$ | 0.277 | 0.643 | 0.08
$E_{4}$ | 0.33 | 0.55 | 0.12
$E_{5}$ | 0.625 | 0.313 | 0.06
$E_{6}$ | 0.30 | 0.60 | 0.10
$E_{7}$ | 0.303 | 0.576 | 0.12
$E_{8}$ | 0.351 | 0.598 | 0.051
$E_{9}$ | 0.296 | 0.593 | 0.11
$E_{10}$ | 0.40 | 0.52 | 0.08
Table 6. The fraction of targets’ polarity relationship detected by analyzing
news articles and structural balance theory respectively along with the
fraction of unresolved links related to each of the $10$ events is shown.

###  5.3. Extraction of the sentiment of the tweet towards the event

The objective of this step is to extract the sentiment of the tweet towards
the event. As the sentiment towards the event may not be directly evident from
the tweet, we initially filter the target, $g_{i}$ mentioned in the tweet text
($Tw_{z}$) as either the event ($E$) or a target related to the event (from
the list of targets, $T$) and measure the sentiment of the tweet text towards
$g_{i}$. The calculation of the sentiment of the tweet text towards $g_{i}$,
$\mathcal{S}(Tw_{z},g_{i})$ is done on the basis of lexicon based sentiment
analysis approach (taboada2011lexicon, ). We use the polarity relation
$\mathcal{R}(E,g_{i})$ of the target mentioned in the tweet text, $g_{i}$
towards the event, $E$ from the created signed network and consider both the
relationships $\mathcal{S}(Tw_{z},g_{i})$ and $\mathcal{R}(E,g_{i})$ to
determine the stance of the tweet towards the event, $\mathcal{X}(Tw_{z},E)$
by the relation.

(6)
$\displaystyle\mathcal{X}(Tw_{z},E)=\mathcal{S}(Tw_{z},g_{i})\mathcal{R}(E,g_{i})$

Therefore, $\mathcal{X}(Tw_{z},E)$ is positive if $\mathcal{R}(E,g_{i})$ and
$\mathcal{S}(Tw_{z},g_{i})$ are either both positive or negative. We discuss
the dataset details and experimental settings next.

##  6\. Experimental Settings

In this Section, we discuss the events that we consider for the experiments
and outline the procedure to create the ground truth data, discuss the
existing research works with which we compare the proposed approach.

###  6.1. Dataset Collection and Pre-processing Details

For our experiments, we randomly select $10$ events that had occurred from
$2016$ to $2018$, from the Wikipedia list of
events555https://en.wikipedia.org/wiki/2018666https://en.wikipedia.org/wiki/2017.
To avoid any bias towards events with more number of news articles, we
selected events with varying number of news articles — the total number of
news articles related to an event ranged between $10-86$. We choose events
with different number of news articles to understand the difference in
performance of our proposed approach with respect to the number of articles
available for an event. The total number of news articles related to an event
was considered based on the news articles shown by Google News Search API
777https://news.google.com/?hl=en-IN&gl=IN&ceid=IN:en related to that event.
The details about the number of articles for each dataset along with the
average number of sentences is outlined in Table 7. In Section 7.2, we further
investigate other characteristics of the news articles, like the average
number of targets present in a news article along with the length of the news
articles related to each of $10$ events to ensure the proposed approach is not
biased by the selection of the news articles or the type of news event.

####  6.1.1. Dataset of the Events

The following events were selected randomly to investigate the proposed
approach.

  * •

Harvey Weinstein allegations ($E_{1}$) : In October $2017$, around $80$ women
had made sexual abuse allegations against Harvey Weinstein, a former US film
producer, that created a wave against sexual harrassment at work
places888https://en.wikipedia.org/wiki/Harvey_Weinstein. In Twitter, people
expressed their opinion either in favour or against Harvey Weinstein.

  * •

Demonetization in India ($E_{2}$) : On $8$ November $2016$, the Government of
India announced the demonetisation of all $500$ and $1000$ Indian rupee
banknotes of the Mahatma Gandhi Series
999https://en.wikipedia.org/wiki/2016_Indian_banknote_demonetisation. People
expressed their support or criticized the decision of demonetization in India
on Twitter.

  * •

Catalan Independence Movement ($E_{3}$) : The Catalan independence movement is
a social and political movement with roots in Catalan nationalism, which seeks
the independence of Catalonia from Spain which led to a resolution that was
passed by the Parliament of Catalonia on $27$ October $2017$, which declared
the independence of Catalonia from Spain and the founding of an independent
Catalan
Republic101010https://en.wikipedia.org/wiki/Catalan_independence_movement.
There was segregation in the opinion of people on this event as people either
supported or opposed the Catalan Independence movement.

  * •

Australian Ball Tampering Scandal ($E_{4}$) : In March 2018, the Australian
cricket team was involved in a ball-tampering scandal during and after the
third Test match against South Africa in Cape Town
111111https://en.wikipedia.org/wiki/2018_Australian_ball-tampering_scandal.
While there was a section of people who deeply criticized the three Australian
players involved and demanded huge punishment, another section of people were
sympathetic and believed the punishment meted was harsh and the players should
be forgiven.

  * •

Punjab National Bank Scam ($E_{5}$) : The Punjab National Bank, a nationalized
bank of India, made headlines after a case of fraudulent letter of undertaking
worth $14,356.84$ crore rupees issued by the Punjab National Bank surfaced and
the person responsible, Nirav Modi and his family absconded the
country121212https://en.wikipedia.org/wiki/Punjab_National_Bank_Scam. It led
to discussions about whether Indian government is negligent and responsible in
allowing the accused to flee the country.

  * •

Assassination of Jamal Khashoggi ($E_{6}$) : Jamal Ahmad Khashoggi was a Saudi
Arabian dissident, author, columnist for the Washington Post, and a general
manager and editor-in-chief of Al-Arab News Channel who was allegedly
assassinated at the Saudi Arabian consulate in Istanbul on $2$ October
$2018$131313https://en.wikipedia.org/wiki/Jamal_Khashoggi. Khashoggi was
primarily declared as missing and Saudi Arabia claimed he had left the
consulate and denied having any knowledge about his fate which led to debate
among people that whether US government should interfere and ensure justice
for Khashoggi.

  * •

2017 Zimbabwean coup d’état ($E_{7}$) : On the evening of 14 November 2017,
elements of the Zimbabwe Defence Forces (ZDF) gathered around Harare, the
capital of Zimbabwe, and seized control of the Zimbabwe Broadcasting
Corporation and key areas of the city which led to removal of President Mugabe
succeeded by Emmerson
Mnangagwa141414https://en.wikipedia.org/wiki/2017_Zimbabwean_coup_d%27%C3%A9tat.

  * •

United States withdrawal from the Joint Comprehensive Plan of Action ($E_{8}$)
: On May 8, 2018, the United States withdrew from the Joint Comprehensive Plan
of Action (unofficially known as the Iran Deal or the Iran Nuclear Deal). The
withdrawal caused concerns in Iran due to its impact on the economy and
received mixed reactions, like praise from the American conservatives in the
United States and criticism from the former president Barack Obama, his vice
president Joe Biden and
EU151515https://en.wikipedia.org/wiki/United_States_withdrawal_from_the_Joint_Comprehensive_Plan_of_Action.

  * •

2017 Nangarhar airstrike ($E_{9}$) : The 2017 Nangarhar airstrike refers to
the American bombing of the Achin District located in the Nangarhar Province
of eastern Afghanistan, near the border with Pakistan with the goal of
destroying tunnel complexes used by a branch of the Syria-based
ISIS161616https://en.wikipedia.org/wiki/2017_Nangarhar_airstrike.

  * •

Otto Warmbier ($E_{10}$) : Otto Frederick Warmbier was an American college
student who was imprisoned in North Korea in 2016 after being convicted of
theft of a propaganda poster. Although the U.S. government secured his release
in June 2017, Warmbier died six days after his return to the United States.
While a section of people believed that North Korea was responsible for the
death of Otto Warmbier and demanded justice, the others elaborated that it was
his own health issues that led to this unfortunate incident.
171717https://en.wikipedia.org/wiki/Otto_Warmbier

We next discuss the data related to the news articles and the tweets of each
of these events.

Event | $N_{a}$ | Avg $A_{len}$ | Event | $N_{a}$ | Avg $A_{len}$
---|---|---|---|---|---
$E_{1}$ | 34 | 18 | $E_{6}$ | 21 | 27
$E_{2}$ | 86 | 20 | $E_{7}$ | 25 | 17
$E_{3}$ | 47 | 21 | $E_{8}$ | 18 | 35
$E_{4}$ | 10 | 32 | $E_{9}$ | 32 | 23
$E_{5}$ | 16 | 18 | $E_{10}$ | 13 | 45
Table 7. The number of news articles, $N_{a}$ and the average length of a news
article, $A_{len}$ related to $10$ events is shown.

####  6.1.2. News Articles and Tweets Dataset

In this section, we discuss the details related to the news articles of an
event and the tweets considered for experimental analysis.
News Articles Dataset: As already discussed in Section 6.1, we consider
different events based on the number of the news articles published related to
that event. The total number of news articles published related to an event
was considered based on the news articles shown by Google News Search API
related to the event. We select the news articles related to the events
mentioned in Section 6.1.1. We used newspaper API to crawl the randomly
selected news articles related to an event. In Table 7, we further provide an
overview of the dataset related to the news articles of the events, i.e.
number of news articles and average number of sentences in the news article.
Observations from Table 7 indicates that each of these characteristics has a
high variance, i.e. the number of news articles ranges from $10-86$ and
average number of sentences in the news article ranges from $17-45$.
Tweets Dataset For each of the events, we followed a pseudo relevance feedback
based system (chakraborty2019predicting, ; chakraborty2017network, ) to
extract the relevant tweets related to the event and we randomly select $500$
relevant tweets for each event for our experimental analysis. Since we
determine the stance of a tweet towards an event from the tweet text, we
perform basic pre-processing on the tweet text, like removal of the hashtags,
URL and user-ids from the tweet text.

###  6.2. Ground Truth Preparation

We prepare the ground truth data through manual annotation of the stance of
the tweets identified in context to each of the events. Manual annotation of
the tweets required a contextual understanding of the event to correctly
identify the stance of the tweet. As stated above for each of the events we
selected $500$ tweets leading to a total of $5000$ tweets. A group of $3$
manual annotators with good knowledge in English and the background of the
events were given the task of labelling. An annotator marked the tweet as
positive or  negative with respect to the event. We strongly encouraged them
to try their best to understand the tweets before labeling as tweets are
sometimes confusing with informal expressions and sarcasm. The inter-rater
agreement was measured using Cohen’s kappa
coefficient181818https://en.wikipedia.org/wiki/Cohen%27s_kappa. We observed a
value of $89\%$, thus indicating a high agreement among the annotators. During
disagreement, the opinion of the majority of the three annotators was
considered.

###  6.3. Comparison with Existing Techniques

We have considered the proven state-of-the-art stance detection approaches as
baselines. Several of these approaches are from the SemEval 2016 Task
(mohammad2016semeval, ). Although the existing research works (referred by
$Base_{1}$, $Base_{2}$, $Base_{3}$ and $Base_{4}$) is proposed to train the
respective models on annotated tweets, we intend to investigate the
performance of the baselines when trained on news articles related to an
event. The reason being that as the proposed approach utilizes information
extracted from news articles related to an event to determine stance of a
tweet, we wanted to investigate the performance of the existing research works
when trained on news articles statements rather than tweets. Hence, we
randomly selected the number of news article statements equal to the number of
tweets required for training for each of the baselines respectively and train
the corresponding baselines on news article statements. We refer to these
baselines by $Base_{5}$, $Base_{6}$, $Base_{7}$ and $Base_{8}$ respectively.
We briefly discuss all the these baselines next.

  * •

$Base_{1}$ : Zarrella et al. (zarrella2016mitre, ) used recurrent neural
network initialized with features learned from distant supervision to detect
stance in tweets which is referred by $Base_{1}$ in this paper hereby.

  * •

$Base_{2}$ : The work proposed in (wei2016pkudblab, ) used a convolutional
neural network for stance detection in tweets which would be referred by
$Base_{2}$ in this paper.

  * •

$Base_{3}$ : Mohammad et al. (mohammad2017stance, ) proposed an ensemble based
supervised approach that incorporates an extensive set of content features to
detect stance in tweets. This work is referred by $Base_{3}$ in this paper.

  * •

$Base_{4}$ : Tutek et al. (tutek2016takelab, ) proposed an ensemble of
learning algorithms and further, fine-tuned using a genetic algorithm. They
considered an exhaustive list of features, like word features (unigrams,
brigrams), word embeddings, counting features (average word length, number of
retweet symbols, number of hashtags, number of emoticons, etc), repeated
vowels and hashtag information. This work is referred by $Base_{4}$ in this
paper.

  * •

$Base_{5}$ : Although $Base_{1}$ was trained on a set of tweets, we trained
the same approach on news article statements to check the effectiveness of the
approach when trained on news articles. We refer to this baseline as
$Base_{5}$ in this paper.

  * •

$Base_{6}$ : We train $Base_{2}$ on news article statements related to each
event rather than tweets and refer it by $Base_{6}$ in this paper henceforth.

  * •

$Base_{7}$ : We refer to $Base_{3}$ when trained on news article statements
related to an event rather than tweets by $Base_{7}$ in this paper.

  * •

$Base_{8}$ : The baseline $Base_{4}$ when trained on news articles statements
rather than tweets is referred by $Base_{8}$.

We next describe the experiment details and the performance measures that we
use for our investigations.

###  6.4. Performance Evaluation and Measures

We rigorously validate the efficiency of the proposed approach. Initially we
compare the accuracy and F1 scores with the existing research works. We also
compare the effectiveness of the proposed approach when these existing
research works are trained on news articles (same dataset as proposed
approach) rather than tweets to understand whether the effectiveness of the
existing research works would have increased if they were trained on news
article statements rather than tweets. Subsequently, we study the properties
of the news events to investigate whether the proposed approach is biased
towards any specific characteristics. We further investigate the relevance of
the target set (both key-phrases and key-players) that we extract using our
approach, with respect to the event. Subsequently, we validate the importance
of the signed network approach in determining the polarity of the targets
towards the event by comparing the efficiency of the Pass-I and Pass-II steps.

##  7\. Results and Discussion

In this section, we discuss the findings of our experimental investigations.
Initially, we compare the performance of the proposed approach with the
baseline approaches.

###  7.1. Comparison with Baselines

For each of the $10$ different events we initially compare the proposed
approach with the baselines, in terms of average F1 scores. The results for
the same is shown in table 8. The proposed approach outperforms the other
existing research works by around by $6.5-43\%$ in terms of the average F1
score. The results indicate that the proposed approach is highly efficient in
determining the stance of the tweets.

| F1-score |  |  |  |  |
---|---|---|---|---|---|---
| Proposed | $Base_{1}$ | $Base_{2}$ | $Base_{3}$ | $Base_{4}$ | $Base_{5}$ | $Base_{6}$ | $Base_{7}$ | $Base_{8}$
| $E_{1}$ | $0.80$ | $0.62$ | $0.72$ | $0.71$ | $0.69$ | $0.53$ | $0.63$ | $0.45$ | $0.54$
$E_{2}$ | $0.61$ | $0.50$ | $0.57$ | $0.49$ | $0.50$ | $0.43$ | $0.41$ | $0.46$ | $0.40$
$E_{3}$ | $0.63$ | $0.45$ | $0.57$ | $0.47$ | $0.46$ | $0.40$ | $0.52$ | $0.41$ | $0.40$
$E_{4}$ | $0.66$ | $0.49$ | $0.57$ | $0.58$ | $0.50$ | $0.43$ | $0.52$ | $0.53$ | $0.41$
$E_{5}$ | $0.70$ | $0.63$ | $0.65$ | $0.60$ | $0.63$ | $0.59$ | $0.60$ | $0.55$ | $0.57$
$E_{6}$ | $0.69$ | $0.60$ | $0.37$ | $0.56$ | $0.54$ | $0.53$ | $0.35$ | $0.55$ | $0.44$
$E_{7}$ | $0.70$ | $0.64$ | $0.62$ | $0.57$ | $0.62$ | $0.54$ | $0.55$ | $0.54$ | $0.53$
$E_{8}$ | $0.76$ | $0.69$ | $0.71$ | $0.62$ | $0.69$ | $0.54$ | $0.56$ | $0.47$ | $0.54$
$E_{9}$ | $0.80$ | $0.61$ | $0.60$ | $0.72$ | $0.74$ | $0.54$ | $0.52$ | $0.66$ | $0.63$
$E_{10}$ | $0.71$ | $0.54$ | $0.58$ | $0.57$ | $0.70$ | $0.46$ | $0.53$ | $0.54$ | $0.61$
Table 8. The average F1 score of the proposed approach for different events in
comparison to other baselines is shown.

To obtain an alternative view of the above results we created a set of $2500$
tweets selected randomly from the $10$ events (details given in section 6.1).
We repeated the experiment on $10$ such different sets, the observations of
which are shown in table 9. We find that the proposed approach ensures an
accuracy of around $85-90\%$ and average F1-score of $0.77-0.82$, indicating a
high efficiency of the proposed approach. We also observe that the baselines
have higher performance when trained on tweets rather than news article
statements. The underlying reason probably being the features used in
baselines are more suitable for tweets rather than news articles and the text
characteristics of the tweets are not well captured through these news
articles texts. We next investigate whether certain specific properties of the
news articles is playing a role in the better performance of the proposed
approach.

Tweet Set | Accuracy | F1-score | Tweet Set | Accuracy | F1-score
---|---|---|---|---|---
$I_{1}$ | 0.86 | 0.78 | $I_{6}$ | 0.90 | 0.81
$I_{2}$ | 0.86 | 0.79 | $I_{7}$ | 0.89 | 0.81
$I_{3}$ | 0.89 | 0.80 | $I_{8}$ | 0.87 | 0.80
$I_{4}$ | 0.90 | 0.82 | $I_{9}$ | 0.86 | 0.77
$I_{5}$ | 0.90 | 0.82 | $I_{10}$ | 0.85 | 0.77
Table 9. The accuracy and average F1 scores of $10$ sets of $2500$ tweets each, selected randomly from the tweets of $10$ events. Event | $A(K_{l})$ | $Munq(K_{l})$ | $Sunq(K_{l})$ | $A(K_{p})$ | $Munq(K_{p})$ | $Sunq(K_{p})$ | $F_{s}$ | $F_{cd}$ | $F_{cx}$
---|---|---|---|---|---|---|---|---|---
$E_{1}$ | 14.96 | 5.82 | 9.74 | 5.66 | 2.67 | 1.15 | 0.56 | 0.26 | 0.18
$E_{2}$ | 7.11 | 2.98 | 2.69 | 12.66 | 1.71 | 3.14 | 0.37 | 0.35 | 0.28
$E_{3}$ | 7.59 | 4.00 | 4.77 | 9.61 | 1.55 | 2.77 | 0.23 | 0.44 | 0.33
$E_{4}$ | 13.18 | 5.46 | 4.16 | 8.72 | 1.81 | 3.92 | 0.38 | 0.35 | 0.20
$E_{5}$ | 10.5 | 4.31 | 3.65 | 14.2 | 3.5 | 4.65 | 0.27 | 0.44 | 0.29
$E_{6}$ | 10.1 | 6.38 | 4.47 | 17.94 | 2.78 | 5.07 | 0.36 | 0.32 | 0.32
$E_{7}$ | 6.72 | 3.86 | 3.87 | 6 | 3.86 | 3.87 | 0.61 | 0.21 | 0.18
$E_{8}$ | 12.05 | 5.0 | 4.69 | 23.05 | 4.22 | 7.14 | 0.77 | 0.076 | 0.16
$E_{9}$ | 6.93 | 4.46 | 4.71 | 6.56 | 1.36 | 2.71 | 0.65 | 0.21 | 0.141
$E_{10}$ | 16.96 | 8.76 | 18.67 | 10.76 | 2.26 | 8.57 | 0.70 | 0.159 | 0.14
Table 10. The average number of key-players($A(K_{l})$) and key-
phrases($A(K_{p})$), the average number of unique key-players($Munq(K_{l})$)
and key-phrases($Munq(K_{p})$ and the standard deviation in finding unique
key-players($Sunq(K_{l})$ and key-phrases($Sunq(K_{p})$, fraction of simple
sentence $F_{s}$, compound sentence, $F_{cd}$ and complex sentence, $F_{cx}$
in the news articles related to each of the $10$ events is shown

###  7.2. Investigating the News Articles’ Dataset

We investigate whether the performance of the proposed approach is biased by
certain specific properties of the news articles. In this Section, we study
characteristics of the news articles and validate whether the differences
affects the performance of the proposed model. A high variance in these
properties would ensure that the performance of the proposed approach is not
dependent on the choice and nature of the articles. We have already
highlighted earlier in Section 6.1, that the news articles selected for the
$10$ events exhibit considerable difference in their number and the average
length (Table 7). In this Section, we focus on the total count of the key-
players and key-phrases that occurs in the articles and fraction of each type
of sentences in the news articles.

Our observations as shown in Table 10 indicate that average number of key-
players in the articles range from $6.72$-$16.96$, the average number of
unique key-players in the articles range from $2.98$-$8.76$ and the standard
deviation in number of unique key-players of an article ranges from
$2.67$-$18.67$, the average number of key-phrases in the articles range from
$5.66$-$23.05$, the average number of unique key-phrases in the articles range
from $1.55$-$4.22$ and the standard deviation in number of unique key-phrases
of an article ranges from $1.15$-$8.57$. On investigating the distribution of
different types of sentences in the news articles related to each of the
events, we observe as shown in Table 10 that there is considerable variance.
For example, Harvey Weinstein Allegations, Australian Ball Tampering Scandal
and Assasination of Jamal Khassogi have similar distribution of simple and
complex sentence while Demonetization in India has a majority of simple
sentence and Catalan Independence Movement and Punjab National Bank Scam have
a majority of complex sentences. Thus, these results shows that the
considerably high performance of the proposed approach for all the $10$ events
is unlikely due to any specific characteristics of the news articles and the
proposed approach is not biased by the type of news articles or event.

Further, we highlight on the target key-phrases that are extracted using our
approach by representing a sub-set of the identified key-phrases using a word
cloud related to $3$ events in Figure 2. For example, for the event, namely
Harvey Weinstein allegations, prominent personalities like Angelina Jolie,
Kate Winslet, Lena Dunham and Jodi Kantor who made allegations against him get
strongly represented. Further major key-phrases like sexual harrassment,
sexual assault and consensual sex that were key features of the debate are
also suitably captured. Similarly, for the demonetization event in India, key-
phrases like long queues, lack of certain denomination notes and parivartan
(change) that were being highly used to debate on the benefits and drawbacks
of demonetization are captured successfully.

(a) $E_{1}$

(b) $E_{2}$

(c) $E_{4}$

Figure 2. Word cloud representing the key-phrases generated related to each of
the $3$ events is shown.

###  7.3. Investigating the Polarity of Targets towards the Event

In this Section, we discuss the effectiveness of the proposed approach in
determining the polarity relationship of a target towards the event through
Pass-I and Pass-II respectively. Based on our earlier investigations in
Section 5.2, we observed that the fraction of targets related to an event
whose polarity could be extracted in Pass-I ranged from $14-62.5\%$, in Pass-
II ranged from $31.3-76\%$ (table 6). On studying the correctness of the
polarity relationships extracted in both Pass-I and Pass-II respectively, we
observe that the proposed approach achieves $100\%$ correctness in determining
the polarity of a target in both Pass-I and Pass-II.

However, even though the proposed approach can correctly identify the polarity
of the targets in both Pass-I and Pass-II, there remains a small fraction of
targets(around $4-12\%$) whose polarity relationship with the event could not
be extracted in both Pass-I and Pass-II. The polarity relationship of a
target, say $g_{i}$ towards the event, $E$, could not be resolved in Pass-I in
any of the following 2 cases: ($a$) if the target appeared in only news
article statements that are direct or indirect speech in which the reporting
clause comprised of complex or compound sentences or ($b$) if the target
appears in complex and compound sentences where the conjunction present is not
one of the conjunctions as shown in Table 5. Further, the polarity
relationship of $g_{i}$ towards the $E$ would not be resolved even in Pass-II
if it is not connected to any other target $g_{j}$ which is connected to $E$
through some path. Therefore, the proposed approach fails to extract the
polarity relationship of $g_{i}$ towards $E$ if it satisfies both the above
mentioned conditions for Pass-I and Pass-II, respectively. However, if neither
of these conditions hold true for $g_{i}$, then the proposed approach can
extract the polarity relationship of $g_{i}$ towards $E$ with $100\%$
accuracy.

###  7.4. The role of sentence types in identifying the polarity of a target
towards the event

extract the polarity relationship of the targets towards an event (Pass-I).
While extracting the polarities from the simple sentences is simpler and
precise as compared to the other two types, however, the fraction of simple
sentences in the news articles may be very less. In this Section, we
investigate the loss in efficiency of the proposed approach had we considered
only simple sentences from the news articles, i.e., we study the requirement
of all the three types of sentences than only simple sentences. We observe the
fraction of targets whose polarity relationship towards the event could be
extracted by handling only simple sentences and direct and indirect speeches
where the reporting clause is a simple sentence in Table 11. Our observations
indicate that using all the three types of sentences for target polarity
identification increases the efficiency by more than $40\%$.

Sentence | $E_{1}$ | $E_{2}$ | $E_{3}$ | $E_{7}$ | $E_{8}$
---|---|---|---|---|---
$Simple$ | $0.37$ | $0.10$ | $0.11$ | $0.20$ | $0.238$
$Pass-I$ | $0.527$ | $0.14$ | $0.277$ | $0.303$ | $0.351$
Table 11. The fraction of targets whose polarity towards an event was
extracted by considering only simple sentences and direct and indirect speech
where the reporting clause is simple (represented by $Simple$) and by
following Pass-I is shown. The number of events considered is $5$.

###  7.5. Analyzing failures

Although the proposed approach ensures high accuracy in comparison with the
existing baseline approaches irrespective of the type of event, we investigate
more closely certain cases where our proposed approach fails.

Extraction of Polarity Relationship from News Article : A typical example
sentence (related to the Demonetization event) where the proposed approach
fails to identify the polarity of the target towards the event is, The
opposition party leader claimed “Only $6\%$ of the black money is in cash form
while $94\%$ of the black money is either in foreign banks or in the form of
gold, land and estate”. A major characteristic of this sentence is it contains
a latent domain information related to the event. The sentence provides an
information that black money in cash is much less as compared to other forms;
however, it subtly hints that since demonetization would mainly impact black
money in cash, hence it would be unsuccessful. Thus, the polarity relation of
the target black money in cash with the demonetization event would not be
resolved and hence the stance of this tweet cannot be determined by our
proposed approach.

Identifying Target Polarity using Signed Network Analysis : Our proposed
approach fails to predict the polarity of a target towards the event if the
target (say, $a$) is connected to only another target (say, $b$) and neither
$a$ nor $b$ is connected to any other target or the event in the signed
network. Therefore, the proposed approach fails to extract the polarity
relationship of a target towards the event in Pass-II if it does not satisfy
either of the conditions mentioned in Section 5.2.2. Our empirical experiments
indicate the fraction of the targets whose polarity could not be resolved by
the proposed methodology ranges from $4-12\%$ of the total targets for the
$10$ events (as shown in Table 6). Thus, there remains a scope of improvement
of the proposed approach so as to resolve these cases.

Stance Detection of a Tweet towards the Event : There are few scenarios in
which the proposed approach in Section 5.3 fails to determine the stance of a
tweet towards an event. One of them being processing of sarcasm if present in
tweets. Understanding of sarcasm in tweets requires in-depth understanding of
both the content and context level information in the tweet text
(joshi2017automatic, ) which has not been covered in the current proposed
approach. The proposed approach also fails to extract stance of a tweet if the
tweet text is written in any other language except English. Although the
proposed approach follows an exhaustive mechanism to extract the targets
related to an event and we have experimentally verified the success of this
step, it cannot ensure that all the related targets of an event would be
captured. Therefore, if a tweet comprises of a target that has not been
identified previously by the proposed approach, it fails to identify the
stance of the tweet towards the event. Therefore, these issues provide
directions where the proposed approach can be further improved.

##  8\. Conclusion

In this paper, we propose an unsupervised approach to detect stance in tweets.
The novelty of the proposed approach is the use of a signed network to detect
stance of a tweet. Though signed networks have been proposed to understand the
relationships between the actors of a text/movie review, this is the first
work that leverages the information from the signed network for stance
detection in tweets. The created signed network serves as a rich knowledge
base related to an event — comprising of the possible exhaustive target set
related to the event and polarity relationships between any pair of targets
which is extracted by a combination of textual and signed network attributes.
This further ensures that stance detection by the proposed approach does not
require any human intervention. Validation on empirical data set of around
$10$ events shows that stance detected using the proposed approach outperforms
the existing stance detection approaches by a considerable margin.

## References

  * (1) Anand, P., Walker, M., Abbott, R., Tree, J. E. F., Bowmani, R., and Minor, M. Cats rule and dogs drool!: Classifying stance in online debate.  In Proceedings of the 2nd workshop on computational approaches to subjectivity and sentiment analysis (2011), Association for Computational Linguistics, pp. 1–9.
  * (2) Augenstein, I., Rocktäschel, T., Vlachos, A., and Bontcheva, K. Stance detection with bidirectional conditional encoding.  arXiv preprint arXiv:1606.05464 (2016).
  * (3) Bar-Haim, R., Bhattacharya, I., Dinuzzo, F., Saha, A., and Slonim, N. Stance classification of context-dependent claims, 2016.
  * (4) Burt, R. S. The network structure of social capital.  Research in organizational behavior 22 (2000), 345–423.
  * (5) Cartwright, D., and Harary, F. Structural balance: a generalization of heider’s theory.  Psychological review 63, 5 (1956), 277.
  * (6) Chakraborty, R., Bhavsar, M., Dandapat, S., and Chandra, J. A network based stratification approach for summarizing relevant comment tweets of news articles.  In International Conference on Web Information Systems Engineering (2017), Springer, pp. 33–48.
  * (7) Chakraborty, R., Kharat, A., Khatua, A., Dandapat, S. K., and Chandra, J. Predicting tomorrow’s headline using today’s twitter deliberations.  arXiv preprint arXiv:1901.09334 (2019).
  * (8) Chuang, J.-h., and Hsieh, S. Stance classification on ptt comments.  In Proceedings of the 29th Pacific Asia Conference on Language, Information and Computation (2015).
  * (9) D’Andrea, E., Ducange, P., Bechini, A., Renda, A., and Marcelloni, F. Monitoring the public opinion about the vaccination topic from tweets analysis.  Expert Systems with Applications 116 (2019), 209–226.
  * (10) Derr, T., Aggarwal, C., and Tang, J. Signed network modeling based on structural balance theory.  In Proceedings of the 27th ACM International Conference on Information and Knowledge Management (2018), ACM, pp. 557–566.
  * (11) Dey, K., Shrivastava, R., and Kaushik, S. Twitter stance detection-a subjectivity and sentiment polarity inspired two-phase approach.  In SENTIRE Workshop, ICDM (2017).
  * (12) Dey, K., Shrivastava, R., and Kaushik, S. Topical stance detection for twitter: A two-phase lstm model using attention.  In European Conference on Information Retrieval (2018), Springer, pp. 529–536.
  * (13) Dias, M., and Becker, K. Inf-ufrgs-opinion-mining at semeval-2016 task 6: Automatic generation of a training corpus for unsupervised identification of stance in tweets.  Proceedings of SemEval (2016), 378–383.
  * (14) Du, J., Xu, R., He, Y., and Gui, L. Stance classification with target-specific neural attention networks.  In SemEval@ NAACL-HLT (2017).
  * (15) Ebrahimi, J., Dou, D., and Lowd, D. A joint sentiment-target-stance model for stance classification in tweets.  In Proceedings of COLING 2016, the 26th International Conference on Computational Linguistics: Technical Papers (2016), pp. 2656–2665.
  * (16) Fraisier, O., Cabanac, G., Pitarch, Y., Besançon, R., and Boughanem, M. Stance classification through proximity-based community detection.  Proceedings of the 29th on Hypertext and Social Media (2018).
  * (17) Gao, W., Yang, Y., and Liu, Y. Stance detection with target and target towards attention.  In 2018 IEEE International Conference on Big Knowledge (ICBK) (2018), IEEE, pp. 432–439.
  * (18) Hasan, K. S., and Ng, V. Stance classification of ideological debates: Data, models, features, and constraints.  In IJCNLP (2013), pp. 1348–1356.
  * (19) Johnson, K., and Goldwasser, D. Identifying stance by analyzing political discourse on twitter.  In Proceedings of the First Workshop on NLP and Computational Social Science (2016), pp. 66–75.
  * (20) Joshi, A., Bhattacharyya, P., and Carman, M. J. Automatic sarcasm detection: A survey.  ACM Computing Surveys (CSUR) 50, 5 (2017), 73.
  * (21) Kim, J., Park, H., Lee, J.-E., and Kang, U. Side: representation learning in signed directed networks.  In Proceedings of the 2018 World Wide Web Conference on World Wide Web (2018), International World Wide Web Conferences Steering Committee, pp. 509–518.
  * (22) Klenner, M., Tuggener, D., and Clematide, S. Stance detection in facebook posts of a german right-wing party.  LSDSem 2017 (2017), 31.
  * (23) Krejzl, P., Hourová, B., and Steinberger, J. Stance detection in online discussions.  arXiv preprint arXiv:1701.00504 (2017).
  * (24) Krejzl, P., and Steinberger, J. Uwb at semeval-2016 task 6: Stance detection.  In SemEval@ NAACL-HLT (2016), pp. 408–412.
  * (25) Krestel, R., Bergler, S., Witte, R., et al. Minding the source: Automatic tagging of reported speech in newspaper articles.  Reporter 1, 5 (2008), 4.
  * (26) Küçük, D., and Can, F. Stance detection on tweets: An svm-based approach.  arXiv preprint arXiv:1803.08910 (2018).
  * (27) Lai, M., Farías, D. I. H., Patti, V., and Rosso, P. Friends and enemies of clinton and trump: Using context for detecting stance in political tweets.  arXiv preprint arXiv:1702.08021 (2017).
  * (28) Lai, M., Patti, V., Ruffo, G., and Rosso, P. Stance evolution and twitter interactions in an italian political debate.  In International Conference on Applications of Natural Language to Information Systems (2018), Springer, pp. 15–27.
  * (29) Leskovec, J., Huttenlocher, D., and Kleinberg, J. Signed networks in social media.  In Proceedings of the SIGCHI conference on human factors in computing systems (2010), ACM, pp. 1361–1370.
  * (30) Liu, C., Li, W., Demarest, B., Chen, Y., Couture, S., Dakota, D., Haduong, N., Kaufman, N., Lamont, A., Pancholi, M., et al. Iucl at semeval-2016 task 6: An ensemble model for stance detection in twitter.  In SemEval@ NAACL-HLT (2016), pp. 394–400.
  * (31) Ma, J., Gao, W., and Wong, K.-F. Detect rumor and stance jointly by neural multi-task learning.  In Companion of the The Web Conference 2018 on The Web Conference 2018 (2018), International World Wide Web Conferences Steering Committee, pp. 585–593.
  * (32) Misra, A., Ecker, B., Handleman, T., Hahn, N., and Walker, M. A. Nlds-ucsc at semeval-2016 task 6: A semi-supervised approach to detecting stance in tweets.  In SemEval@ NAACL-HLT (2016), pp. 420–427.
  * (33) Mohammad, S., Kiritchenko, S., Sobhani, P., Zhu, X., and Cherry, C. Semeval-2016 task 6: Detecting stance in tweets.  In Proceedings of the 10th International Workshop on Semantic Evaluation (SemEval-2016) (2016), pp. 31–41.
  * (34) Mohammad, S. M. Sentiment analysis: Detecting valence, emotions, and other affectual states from text.  In Emotion measurement. Elsevier, 2016, pp. 201–237.
  * (35) Mohammad, S. M., Sobhani, P., and Kiritchenko, S. Stance and sentiment in tweets.  ACM Transactions on Internet Technology (TOIT) 17, 3 (2017), 26\.
  * (36) Mohtarami, M., Baly, R., Glass, J., Nakov, P., Màrquez, L., and Moschitti, A. Automatic stance detection using end-to-end memory networks.  arXiv preprint arXiv:1804.07581 (2018).
  * (37) Mourad, S. S., Shawky, D. M., Fayed, H. A., and Badawi, A. H. Stance detection in tweets using a majority vote classifier.  In International Conference on Advanced Machine Learning Technologies and Applications (2018), Springer, pp. 375–384.
  * (38) NG, K. S. H. V., and Hasan, K. Predicting stance in ideological debate with rich linguistic knowledge.  In 24th International Conference on Computational Linguistics (2012), p. 451.
  * (39) Paradis, C. Visual analysis of sentiment and stance in social media texts.  In EuroVis 2018 (2018).
  * (40) Patra, B. G., Das, D., and Bandyopadhyay, S. Ju_nlp at semeval-2016 task 6: Detecting stance in tweets using support vector machines.  In SemEval@ NAACL-HLT (2016), pp. 440–444.
  * (41) Puscasu, G. A multilingual method for clause splitting.  In Proceedings of the 7th Annual Colloquium for the UK Special Interest Group for Computational Linguistics (2004).
  * (42) Rajadesingan, A., and Liu, H. Identifying users with opposing opinions in twitter debates.  In International Conference on Social Computing, Behavioral-Cultural Modeling, and Prediction (2014), Springer, pp. 153–160.
  * (43) Rajendran, G., Chitturi, B., and Poornachandran, P. Stance-in-depth deep neural approach to stance classification.  Procedia Computer Science 132 (2018), 1646–1653.
  * (44) Rajendran, P., Bollegala, D., and Parsons, S. Is something better than nothing? automatically predicting stance-based arguments using deep learning and small labelled dataset.  In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 2 (Short Papers) (2018), vol. 2, pp. 28–34.
  * (45) Rawlings, C. M., and Friedkin, N. E. The structural balance theory of sentiment networks: Elaboration and test.  American Journal of Sociology 123, 2 (2017), 510–548.
  * (46) Rose, S., Engel, D., Cramer, N., and Cowley, W. Automatic keyword extraction from individual documents.  Text Mining: Applications and Theory (2010), 1–20.
  * (47) Ruder, S., Glover, J., Mehrabani, A., and Ghaffari, P. 360° stance detection.  In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Demonstrations (2018), pp. 31–35.
  * (48) Sasaki, A., Hanawa, K., Okazaki, N., and Inui, K. Predicting stances from social media posts using factorization machines.  In Proceedings of the 27th International Conference on Computational Linguistics (2018), pp. 3381–3390.
  * (49) Sasaki, A., Mizuno, J., Okazaki, N., and Inui, K. Stance classification by recognizing related events about targets.  In Web Intelligence (WI), 2016 IEEE/WIC/ACM International Conference on (2016), IEEE, pp. 582–587.
  * (50) Savanur, S. R., and Sumathi, R. Feature based sentiment analysis of compound sentences.  In 2017 2nd International Conference On Emerging Computation and Information Technologies (ICECIT) (2017), IEEE, pp. 1–6.
  * (51) Shenoy, G. G., Dsouza, E. H., and Kübler, S. Performing stance detection on twitter data using computational linguistics techniques.  arXiv preprint arXiv:1703.02019 (2017).
  * (52) Siddiqua, U. A., Chy, A. N., and Aono, M. Stance detection on microblog focusing on syntactic tree representation.  In International Conference on Data Mining and Big Data (2018), Springer, pp. 478–490.
  * (53) Simaki, V., Simakis, P., Paradis, C., and Kerren, A. Detection of stance-related characteristics in social media text.  In The 10th Hellenic Conference on Artificial Intelligence (2018), ACM.
  * (54) Skeppstedt, M., Sahlgren, M., Paradis, C., and Kerren, A. Active learning for detection of stance components.  PEOPLES 2016 (2016), 50.
  * (55) Sobhani, P., Inkpen, D., and Zhu, X. A dataset for multi-target stance detection.  In Proceedings of the 15th Conference of the European Chapter of the Association for Computational Linguistics: Volume 2, Short Papers (2017), vol. 2, pp. 551–557.
  * (56) Sobhani, P., Inkpen, D., and Zhu, X. Exploring deep neural networks for multitarget stance detection.  Computational Intelligence (2019).
  * (57) Taboada, M., Brooke, J., Tofiloski, M., Voll, K., and Stede, M. Lexicon-based methods for sentiment analysis.  Computational linguistics 37, 2 (2011), 267–307.
  * (58) Trabelsi, A., and Zaiane, O. R. Unsupervised model for topic viewpoint discovery in online debates leveraging author interactions.  In Twelfth International AAAI Conference on Web and Social Media (2018).
  * (59) Tsagkias, M., De Rijke, M., and Weerkamp, W. Linking online news and social media.  In Proceedings of the fourth ACM international conference on Web search and data mining (2011), ACM, pp. 565–574.
  * (60) Tutek, M., Sekulic, I., Gombar, P., Paljak, I., Culinovic, F., Boltuzic, F., Karan, M., Alagić, D., and Šnajder, J. Takelab at semeval-2016 task 6: stance classification in tweets using a genetic algorithm based ensemble.  In Proceedings of the 10th International Workshop on Semantic Evaluation (SemEval-2016) (2016), pp. 464–468.
  * (61) Vijayaraghavan, P., Sysoev, I., Vosoughi, S., and Roy, D. Deepstance at semeval-2016 task 6: Detecting stance in tweets using character and word-level cnns.  arXiv preprint arXiv:1606.05694 (2016).
  * (62) Wei, P., Lin, J., and Mao, W. Multi-target stance detection via a dynamic memory-augmented network.  In The 41st International ACM SIGIR Conference on Research & Development in Information Retrieval (2018), ACM, pp. 1229–1232.
  * (63) Wei, W., Zhang, X., Liu, X., Chen, W., and Wang, T. pkudblab at semeval-2016 task 6: A specific convolutional neural network system for effective stance detection.  In SemEval@ NAACL-HLT (2016), pp. 384–388.
  * (64) Wojatzki, M., and Zesch, T. ltl. uni-due at semeval-2016 task 6: Stance detection in social media using stacked classifiers.  In SemEval@ NAACL-HLT (2016), pp. 428–433.
  * (65) Zarrella, G., and Marsh, A. Mitre at semeval-2016 task 6: Transfer learning for stance detection.  arXiv preprint arXiv:1606.03784 (2016).
  * (66) Zhang, Q., Yilmaz, E., and Liang, S. Ranking-based method for news stance detection.  In Companion of the The Web Conference 2018 on The Web Conference 2018 (2018), International World Wide Web Conferences Steering Committee, pp. 41–42.


# Bayesian post-hoc regularization of
random forests

Bastian Pfeifer
Institute for Medical Informatics, Statistics and Documentation
Medical University Graz, Austria

###### Abstract

Random Forests are powerful ensemble learning algorithms widely used in
various machine learning tasks. However, they have a tendency to overfit noisy
or irrelevant features, which can result in decreased generalization
performance. Post-hoc regularization techniques aim to mitigate this issue by
modifying the structure of the learned ensemble after its training.

Here, we propose Bayesian post-hoc regularization to leverage the reliable
patterns captured by leaf nodes closer to the root, while potentially reducing
the impact of more specific and potentially noisy leaf nodes deeper in the
tree. This approach allows for a form of pruning that does not alter the
general structure of the trees but rather adjusts the influence of leaf nodes
based on their proximity to the root node. We have evaluated the performance
of our method on various machine learning data sets. Our approach demonstrates
competitive performance with the state-of-the-art methods and, in certain
cases, surpasses them in terms of predictive accuracy and generalization.

###### Keywords:

Random forest, Feature importance, explainable AI, Regularization

##  I Introduction

Post-regularization techniques for random forests refer to methods used to
reduce overfitting and improve the generalization performance of random forest
models. Random forests are powerful ensemble learning algorithms that combine
multiple decision trees to make predictions. However, they can still suffer
from overfitting, especially when the trees in the forest become highly
complex and tailored to the training data. Post-regularization techniques aim
to address this issue by modifying or refining the random forest model after
the initial training phase. These techniques typically focus on adjusting the
complexity of individual trees or applying ensemble-level modifications. Some
commonly used post-regularization techniques for random forests include:

Pruning: Pruning involves removing unnecessary branches or nodes from
individual trees to simplify their structure. This helps prevent overfitting
and promotes better generalization by reducing the complexity of the trees
[1].

Feature selection: Random forests can sometimes include irrelevant or
redundant features, which can degrade performance. Feature selection
techniques aim to identify and remove such features from the model, allowing
it to focus on the most informative ones and potentially reducing overfitting
[2][3].

Calibration: Calibration techniques aim to refine the predicted probabilities
of random forests to better align with the true class probabilities. This can
be particularly useful in tasks where reliable probability estimates are
important, such as in certain risk assessment or medical diagnosis scenarios
[4].

These post-regularization techniques provide various approaches to combat
overfitting and enhance the generalization ability of random forest models. By
incorporating these techniques into the random forest workflow, practitioners
can often achieve better performance and more reliable predictions on unseen
data.

Here, we present a Bayesian post-hoc regularization method for the calibration
of the Dection trees’ leaf node probabilities. Our method is implemented
within the Python package TreeSmoothing, which seemingly interfaces with
sklearn functionalities and thus can be employed on any trained tree-based
classifier.

##  II Related Work - Hierarchical Shrinkage

Agarwal et al. (2022) [4] proposed a post-hoc regularization technique known
as Hierarchical Shrinkage (HS). Unlike modifying the tree structure, HS
focuses on shrinking tree predictions and adjusting sample weights during
training. This additional regularization improves generalization performance
and allows for smaller ensembles without sacrificing accuracy. HS also
enhances post-hoc interpretations by reducing noise in feature importance
measures, leading to more reliable and robust interpretations. The method
replaces the average prediction of a leaf node with a weighted average of the
mean responses of the leaf and its ancestors, controlled by a regularization
parameter $\lambda$ as defined in Eq. (2).

The following is a brief summary of the ideas proposed in [4]. Assume that we
are given a training set $\mathcal{D}_{n}=(X;y)$. Our goal is to learn a tree
model $\hat{f}$ that accurately represents the regression function based on
this training data. Given a query point $\mathbf{x}$, let $t_{L}\subset
t_{L-1}\subset\cdots\subset t_{0}$ denote its leaf-to-root path, with $t_{L}$
and $t_{0}$ representing its leaf node and the root node respectively. For any
node $t$, let $N(t)$ denote the number of samples it contains, and
$\hat{\mathbb{E}}_{t}\\{y\\}$ the average response. The tree model prediction
can be written as the telescoping sum

$\hat{f}(\mathbf{x})=\hat{\mathbb{E}}_{t_{0}}\\{y\\}+\sum_{l=1}^{L}{\left(\hat{\mathbb{E}}_{t_{l}}\\{y\\}-\hat{\mathbb{E}}_{t_{l-1}}\\{y\\}\right)}$
(1)

HS transforms $\hat{f}$ into a shrunk model $\hat{f}_{\lambda}$ via the
formula:

$\hat{f}_{\lambda}(\mathbf{x}):=\hat{\mathbb{E}}_{t_{0}}\\{y\\}+\sum_{l=1}^{L}{\frac{\hat{\mathbb{E}}_{t_{l}}\\{y\\}-\hat{\mathbb{E}}_{t_{l-1}}\\{y\\}}{1+\lambda/N(t_{l-1})}},$
(2)

where $\lambda$ is a hyperparameter chosen by the user, for example by cross
validation. HS maintains the tree structure, and only modifies the prediction
over each leaf node.

##  III Proposed approach: Bayesian post-hoc regularization

###  III-A Intuition of approach

The core idea of our approach is inspired by the pruning concept, where the
complexity of the trees is reduced by decreasing its depth. Here, we do not
aim to manipulate the general structure of the trees, but we are adopting the
leaf node probabilities such that more weight is given to nodes near my the
root node (pruning by calibration). According to this idea we propose to
update a conjugate Beta prior $\mathbf{B}_{prior}(\alpha,\beta)$ from the root
node to the leaf nodes by subsequently adding the number of classified samples
to the model parameters $\alpha$ (class 0) and $\beta$ (class 1). The leaf
node probabilities are determined using the probabilities to observing a
specific class given the inferred posterior Beta distribution
$\mathbf{B}_{posterior}(\alpha,\beta)$.

###  III-B Mathematical formulation

${\mathbf{B}}_{posterior}(\alpha,\beta)={\mathbf{B}}_{prior}(\alpha,\beta)+\sum_{l=0}^{L}{\mathbf{B}_{t_{l}}(\alpha+N_{0}(t_{l}),\beta+N_{1}(t_{l}))},$
(3)

where $N_{0}(t_{l})$ refers to the number of samples classified as class 0,
and $N_{1}(t_{l})$ is the number of samples classified as class 1 at node
$t_{l}$.

The leaf node probabilities are calculate as

$\hat{f}_{\alpha,\beta}(\mathbf{x})=\mathbf{PPF}(\frac{\alpha}{\alpha+\beta}|{\mathbf{B}}_{posterior}(\alpha,\beta)),$
(4)

where $\mathbf{PPF}$ is percent point function (inverse of the cumulative
distribution function - percentiles).

##  IV Evaluation

###  IV-A Data sets

We assessed the accuracy of our proposed methodology on four machine learning
benchmark datasets (see Table I), downloaded using the Python packages imodels
[5] and PMLB [6].

TABLE I: Benchmark datasets Datasets | Sample size | Features | Class 0 | Class 1
---|---|---|---|---
Breast cancer | 286 | 9 | 196 | 81
Habermann | 306 | 3 | 81 | 225
Heart | 270 | 15 | 150 | 120
Diabetes | 768 | 8 | 500 | 268

###  IV-B Evaluation strategy

In an first experiment, we used grid search-based on 5-fold crossvalidation to
infer the optimal values for the hyperparameters. Following we performed
5-fold crossvalidation and calculated the mean accuracy. The aforementioned
procedure was repeated 20 times and we report on results based on balanced
accuracy and ROC-AUC.

In an second experiment, we have splitted the data into a train and test
dataset. On the train dataset 5-fold crossvalidation was performed to tune the
hyperparameters. The tuned model was then tested on the independent test data
set. The described procedure was repeated 20 times and we again report results
based on balanced accuracy and ROC-AUC as a performance metric.

In case of the herein Bayesian regularization technique, the model-specific
$\alpha$ and $\beta$ hyperparameters were grid-searched within
$[1500,1000,800,500,100,50,30,10,1]$. For the Hierarchical Shrinkage method we
used $\lambda=[0.001,0.01,0.1,1,10,25,50,100,200]$.

###  IV-C Metrics used for evaluation

The Balanced Accuracy is a performance metric used in classification tasks to
measure the accuracy of a model by taking into account the imbalance in the
class distribution. It is defined as the average of the per-class accuracies,
where the per-class accuracy is the ratio of the correctly classified
instances to the total number of instances in that class. The formula for
calculating Balanced Accuracy is given by:

$\text{Balanced
Accuracy}=\frac{1}{N_{c}}\sum_{i=1}^{N_{c}}\frac{TP_{i}}{TP_{i}+FN_{i}}$ (5)

where $N_{c}$ is the number of classes, $TP_{i}$ represents the number of true
positive instances in class $i$, and $FN_{i}$ represents the number of false
negative instances in class $i$. The Balanced Accuracy ranges from 0 to 1,
where 1 indicates perfect classification performance and 0 indicates random
classification.

The Receiver Operating Characteristic Area Under the Curve (ROC-AUC)
quantifies the performance of a model by measuring the area under the receiver
operating characteristic curve. The ROC-AUC is computed as the area under the
ROC curve, which ranges from 0 to 1. An ROC-AUC score of 1 indicates a perfect
classifier, while a score of 0.5 suggests a random classifier. A higher ROC-
AUC score indicates better discriminative ability of the model in
distinguishing between the positive and negative classes.

To calculate the ROC-AUC, various methods can be used, including the
trapezoidal rule or the Mann-Whitney U statistic. The formula for calculating
ROC-AUC using the trapezoidal rule is given by:

$\text{ROC-AUC}=\int_{0}^{1}\text{TPR}(FPR^{-1}(t))\,dt$ (6)

where $\text{TPR}(FPR^{-1}(t))$ represents the true positive rate at the
threshold corresponding to the inverse of the false positive rate $t$, and
$FPR^{-1}(t)$ is the inverse of the false positive rate. The ROC-AUC provides
a single scalar value that summarizes the model’s performance across all
possible classification thresholds.

The difference between of the two metrics is that Balanced Accuracy focuses on
the accuracy of individual classes, accounting for class imbalance, while ROC-
AUC evaluates the overall discriminative ability of a classifier across all
possible classification thresholds, providing a single scalar value. Both
metrics have their own significance and are used in different contexts based
on the requirements of the classification problem at hand.

##  V Results and discussion

The results based on the herein analyzed four bechmark datasets suggests that
our approach is competitive with hierarchical shrinkage in terms of the ROC-
AUC values. When Balanced Accuracy is used as a performance metric, however,
our Bayesian post regularization procedure is superior in most cases (see
Figures 1-4). In all cases the post regularization techniques under
investigation clearly can improve the accuracy of the vanilla random forest.
Currently, we are working on an in-depth evaluation of the herein proposed
Bayesian regularization techniques, while enhancing our method also to
regression trees.

(a) Balanced accuracy

(b) AUC

(c) Balanced accuracy

(d) AUC

Figure 1: Breast cancer dataset. (a) and (b) 20 times 5-fold crossvaliation on
the whole dataset. (c) and (d) 20 times evaluation on independent test
dataset.

(a) Balanced accuracy

(b) AUC

(c) Balanced accuracy

(d) AUC

Figure 2: Habermann dataset. (a) and (b) 20 times 5-fold crossvaliation on the
whole dataset. (c) and (d) 20 times evaluation on independent test dataset.

(a) Balanced accuracy

(b) AUC

(c) Balanced accuracy

(d) AUC

Figure 3: Heart dataset. 20 times 5-fold crossvaliation on the whole dataset.
(c) and (d) 20 times evaluation on independent test dataset.

(a) Balanced accuracy

(b) AUC

(c) Balanced accuracy

(d) AUC

Figure 4: Diabetes dataset. 20 times 5-fold crossvaliation on the whole
dataset. (c) and (d) 20 times evaluation on independent test dataset.

##  VI Data availability

The proposed methodology is implemented within the Python package
TreeSmoothing, freely available on GitHub
(https://github.com/pievos101/TreeSmoothing).

##  VII Acknowledgments

We would like to thank Arne Gevaert, Martin Uhrschler, and Markus Loecher for
helpful discussions.

## References

  * [1] B. Liu and R. Mazumder, “ForestPrune: Compact depth-pruned tree ensembles,” in _Proceedings of The 26th International Conference on Artificial Intelligence and Statistics_ , ser. Proceedings of Machine Learning Research, F. Ruiz, J. Dy, and J.-W. van de Meent, Eds., vol. 206. PMLR, 25–27 Apr 2023, pp. 9417–9428. [Online]. Available: https://proceedings.mlr.press/v206/liu23h.html
  * [2] M. B. Kursa and W. R. Rudnicki, “Feature selection with the Boruta package,” _Journal of statistical software_ , vol. 36, pp. 1–13, 2010.
  * [3] B. Pfeifer, A. Holzinger, and M. G. Schimek, “Robust random forest-based all-relevant feature ranks for trustworthy AI,” _Studies in Health Technology and Informatics_ , vol. 294, pp. 137–138, 2022.
  * [4] A. Agarwal, Y. S. Tan, O. Ronen, C. Singh, and B. Yu, “Hierarchical shrinkage: Improving the accuracy and interpretability of tree-based models.” in _International Conference on Machine Learning_. PMLR, 2022, pp. 111–135.
  * [5] C. Singh, K. Nasseri, Y. S. Tan, T. Tang, and B. Yu, “imodels: a python package for fitting interpretable models,” _Journal of Open Source Software_ , vol. 6, no. 61, p. 3192, 2021. [Online]. Available: https://doi.org/10.21105/joss.03192
  * [6] J. D. Romano, T. T. Le, W. La Cava, J. T. Gregg, D. J. Goldberg, P. Chakraborty, N. L. Ray, D. Himmelstein, W. Fu, and J. H. Moore, “Pmlb v1.0: an open source dataset collection for benchmarking machine learning methods,” _arXiv preprint arXiv:2012.00058v2_ , 2021.