Twitter is a microblogging platform that allows users to post public short messages. Posts shared by users pertaining to real-world events or themes can provide a rich “on-theground” live update of the events for the benefit of everyone. Unfortunately, the posted information may not be all credible and rumours can spread over this platform. Existing credibility assessment work have focused on identifying features for discriminating the credibility of messages at the tweet level. However, they do not handle tweets that contain multiple pieces of information, each of which may have different level of credibility. In this work, we introduce the notion of a claim based on subject and predicate terms, and propose a framework to identify claims from a corpus of tweets related to some major event or theme. Specifically, we draw upon work done in open information extraction to extract from tweets, tuples that comprises of subjects and their predicate. Then we cluster these tuples to identify claims such that each claim refers to only one aspect of the event. Tweets corresponding to the tuples in each cluster serve as evidence supporting subsequent credibility assessment task. Extensive experiments on two real world datasets shows the effectiveness of the proposed approach in identifying claims.
Communications over the web have increasingly become user-driven where there exist multiple platforms for users to post their messages that can be seen by the general public. Unfortunately, there is little or no mechanisms to ensure the credibility of the posted messages, unlike traditional news media. Take the popular microblogging platform Twitter as an example, where users can freely post or re-post any short messages, known as tweets, from their mobile accounts. Such a platform allows for the fast dissemination of first hand and repeated information. When a major event occurs, many tweets are generated or re-tweeted containing messages that may be true, false or speculative.
In fact, our observation of collected tweets related to major events indicate that a majority of tweets were forwarded (re-tweeted) by multiple users with little or no changes to the content of the message. Considering the minimal changes by the users, the primary motivation of these users stem from their desire to disseminate the information in the tweet. Such dissemination of information would indeed serve a social utility if the information is true, but would otherwise be detrimental if the information is false or even speculative.
Research in information credibility has been gaining
momentum in recent years [
Methods to find topics in a corpus of tweets can be broadly
divided into feature-based and topic modeling based
approaches. The former extract features such as keywords
from each tweet and clusters the tweets based on these
features [
In this work, we formalize the concept of a “claim” in a corpus of tweets related to some major event. Our goal is to design a framework to identify the set of claims such that each claim refers to only one aspect of the event. Subsequently, the credibility of these claims can be verified against official sources. Note that the credibility assessment task is beyond the scope of this work.
We draw upon work done in the field of Open Information Extraction (IE) to extract entities in the tweets and the relationships between these entities. Then we construct tuples comprising of <subject, predicate> from these entities/relationships. Finally, we cluster the tuples to form claims. The tweets that correspond to the cluster of tuples can be regarded as evidence supporting any subsequent credibility classification task. Extensive experiments on two real-world datasets of tweets demonstrate the effectiveness of our proposed approach to identify meaningful claims.
The paper is organized as follows. Section 2 defines the problem. Section 3 describes the proposed approach, and Section 4 gives an incremental method to identify claims. We present experiment results in Sections 5, followed by related work in Section 6 and conclude in Section 7.
The objective of this work is to identify claims by grouping the tweets related to some major event such that tweets in each group refer to the same claim, of which can be true, false, speculative, conversational or simply spam in nature. We introduce the concept of a claim as follows: Definition 1. A claim is the assertion of a subject and the corresponding predicate expression for the subject. It has the structure (S, P ), where S is the set of words that refer to the same subject, P is the set of words that express the same predicate on S.
The set of words that refer to the same subject/predicate is very much context dependent. For example, in a corpus of tweets on the missing flight MH370 incident, the words “plane” and “MH370 aircraft” are likely to reflect the same subject whilst this may not be true in other context involving multiple planes such as news reports on manoeuvres between military planes1. Here, we assume that the major event 1http://edition.cnn.com/2014/08/22/world/asia/us-chinaair-encounter/ provides the context for the claims and we would want to identify the claims within the event.
Since we do not assume that a tweet contains only one
claim, we use an Open Information Extraction (OpenIE)
tool [
By partitioning the tuples, we obtain a soft clustering of the corresponding tweets since a tweet can contain more than a claim. The tweets that correspond to the tuples in each cluster provide evidence for the credibility assessment of the claim.
Example. To provide an intuition of the tuple clustering and claim identification process, Table 1 shows the OpenIE triples and the subject-predicate tuples obtained for 3 tweets. To simplify discussion, let us cluster these tuples based on the similarity of their subject words. For each cluster, we construct a claim by taking the union of the words in S and P respectively. Table 2 shows the clusters obtained and the corresponding claims. Note that our approach identifies the multiple claims contained in the tweets. For example, tweet 1 has two claims (c1 and c2), tweet 2 has two claims (c2 and c3), while tweet 3 has three claims (c3, c4 and c5).
We will elaborate on our approach to identify claims in the next section. 3.
Different from past tweets clustering work reviewed in
Section 6, this work focuses on claim identification by clustering
tuples mapped from OpenIE extractions of the tweets. We
propose a 3-step ClaimF inder method (see Algorithm 1)
which comprises of:
1. Preprocessing. We preprocess each tweet to remove
known noise and tokenize the sentences prior to
applying the OpenIE process.
2. Subject-predicate tuple extraction. We use the
stateof-the-art OpenIE technique, ClausIE [
Tweet Content Open IE Triples MAS CEO confirms SAR ops and says (mas ceo, confirm, sar ops) airline is working to verify speculation that (mh370, land, nanning) the mh370 may have landed in Nanning.
MH370 landing safely in Nanming is pure (mh370, land, nanming) speculation. No distress signal or call was (distress signal call, receive) received at all So you want me to believe that mh370 has (mh370, crash, water) crashed in water, Aussies found debris but (aussie, found, debris) still no signals captured (signal, capture) Subject-Predicate Tuples <{mas,ceo,sar,ops}, {confirm}> <{mh370,nanning}, {land}> <{mh370,nanming}, {land}> <{distress,signal,call}, {receive}> <{mh370,water}, {crash}> <{aussie,debris}, {found}> <{signal}, {capture}>
This phase corresponds to the function Preprocess in Algorithm 1 line 3. We preprocess each tweet via a series of data cleaning operations to reduce the noise that may affect subsequent OpenIE extraction. These include removing “rt” keywords (which indicate retweet message), URLs, user mentions, emoticons, colons, quote marks and hashtags’ “#” signs. The tweet content is tokenized using the twokenizer tool designed for Twitter content 2 3.2
After preprocessing the tweets, each sentence is subsequently fed to an OpenIE tool to generate a list of relation triples. This step corresponds to the OpenIE function call in Algorithm 1 Line 3.
We chose to use ClausIE, the state-of-the-art OpenIE technique in this work. ClausIE takes as input each sentence in a tweet and identifies the entities E1 and E2, as well as their relationship R. The output is a triple (E1, R, E2). Then each triple (E1, R, E2) is mapped to a subject-predicate tuple (Algorithm 1 Lines 4-5).
3.3
At this juncture, we have obtained a set T of
subjectpredicate tuples from the original corpus of tweets D. We
use the popular Porter Stemmer [
We define the similarity between each pair of subjectpredicate tuples ti = <Si, Pi> and tj = <Sj , Pj > as follows: similarity(ti, tj ) = w · ||SSii ∩∪ SSjj || + (1 − w) · ||PPii ∩∪ PPjj|| (1) where w is a weight, 0 ≤ w ≤ 1, which is empirically determined. Note that this similarity metric is based on the Jaccard index between sets from the respective tuples. This allows tuples comparison operations to be approximated and scaled up (see Section 4).
We can now apply existing clustering techniques to cluster the tuples in T . Here, we choose two commonly used methods, namely, agglomerative or spectral clustering in our evaluation. Agglomerative clustering is a bottom-up hierarchical clustering approach, which initializes each subjectpredicate tuple as a cluster by itself and successively merge the most similar pair of clusters at each step, till the specified number of clusters have been generated. Each cluster c is represented by a tuple tc which is formed by taking the union of the respective S and P terms of the tuples in the cluster, that is, tc =< {S1 ∪ · · · ∪ Sn}, {P1 ∪ · · · ∪ Pn} > ∀ < Si, Pi >∈ c On the other hand, spectral clustering takes in a similarity matrix between all pairs of tuples and construct a Laplacian matrix. Then it performs an Eigen decomposition to obtain the top m eigenvectors, effectively reducing the dimensionality to m. Finally, we use k-means to cluster these eigenvectors to obtain the desired clusters.
The output of ClaimF inder is a set C of tuple clusters. This corresponds to Lines 8-9 in Algorithm 1. Each cluster corresponds to a claim. For each tuple in the cluster, we can retrieve the corresponding tweets from which the tuple is derived. This forms a grouping of the tweets that can provide evidence to verify the credibility of the claim. Note that a tweet can belong to more than one grouping as it may contain multiple claims.
Considering the streaming nature of the tweets, especially for ongoing controversial major events rife with the propagation of rumours, we also propose an incremental approach to quickly identify claims from incoming tweets. Algorithm 2 gives the details of the ClaimF inderINC method.
Each incoming tweet is preprocessed and the tuples constructed as described in Sections 3.1 and 3.2. We create a set of empty buckets and assign a tuple to the bucket determined by a Locality Sensitive Hashing (LSH) function with MinHash (lines 2-6 of Algorithm 2). LSH allows us to quickly estimate the similarity between the set of subject and predicate words in the tuple and those in the bucket.
Let us first consider the subject term S in a tuple t. Since S is an arbitrary sized set of words, we choose its top n most frequent corpus words and apply m hash functions to this set of words S0. For each hash function hi, we obtain the minimum hash value among the n words, denoted by min(hi(S0)). With this, we form a vector
( min(h1(S0)), · · · , min(hm(S0)) ) Similarly, we form a second vector based on the predicate term P as
( min(h1(P 0)), · · · , min(hm(P 0)) ) where P 0 is the set of top n most frequent words in P . These two vectors form the MinHash signature of a tuple.
Next, we apply LSH on the MinHash signatures. Tuples with similar subject and predicate terms will be hashed to the same bucket. This is because if there exist some word that is present in both sets Si and Sj , then min(h(Si)) = min(h(Sj )). This eliminates the need for performing pairwise similarity computation between a tuple from an incoming tweet and each cluster. The corresponding tuples whose MinHash signatures have been mapped to the same bucket are subsequently merged into a cluster by taking the union of their S and P terms respectively.
Our incremental approach provides a mechanism to readjust the clusters should the size of a cluster increases beyond some threshold (lines 7-15 of Algorithm 2). This is achieved by treating the cluster as a mini-corpus to be further partitioned via standard clustering methods based on the similarity measure defined in Equation 1. After the adjustment, a merging operation may be applied to re-group clusters to specified number of clusters.
We implement the proposed algorithms ClaimF inder and ClaimF inderINC in Python, and carry out experiments on a 2.3 GHz CPU with 8 GB RAM running on Ubuntu 14.04.
Our concept of claims is based on subject-predicate
tuples. We also compare with the following representations:
• tweet: full text of the tweet
• keywords: a bag-of-words containing nouns, verbs,
hashtags and cardinal numbers present in a tweet. The
Algorithm 2 ClaimF inderINC
Input: incoming tweet twt; split threshold thres
Output: set of buckets B = {b1, b2, ...}
1: F = OpenIE(P reprocess(twt))
2: for triple ∈ F do
3: extract < S, P > tuple from triple
4: i = LSH(M inHash(< S, P >))
5: bi ← bi ∪ {< S, P >}
6: end for
7: if |bi| ≥ thres then
8: Split(bi) into c1 and c2
9: Let tc1 and tc2 be the representative tuples
of c1 and c2 respectively
Initialize bi = ∅
j = LSH(minHash(tc1))
10:
11:
12:
13:
14: bk ← bk ∪ {c2}
15: end if
bj ← bj ∪ {c1}
k = LSH(minHash(tc2))
Stanford POS tagger using a trained model for tweets
[
We try to identify the claims in the two real world datasets:
• MH370 Dataset. We crawled and collected tweets
on the crash of Malaysian Airline MH370 in 2014 for
our experiments. This event involve the mysterious
disappearance of a Boeing 777 plane en route from
Kuala Lumpur to Beijing on 8 March 2014. Perceived
mishandling of the public communication of the
situation created an unfortunate conducive environment for
the proliferation of various rumours related to MH370
with sustained public interest in the status of the flight
and the cause of the disappearance. Such rumours
range from the absurd such as alien abduction to more
plausible ones such as the plane’s safe landing in China
during the early stage of the crisis. The location of
the plane and cause of the disappearance remains
unknown today. The tweet corpus was collected using the
keyword “MH370” via Twitter’s REST API. In total,
510,433 tweets from 8 March to 9 April were collected.
We extracted a subset of tweets from the MH370 dataset
using keywords of 6 known rumour and credible claims.
Overall, 3,764 tweets have been identified and
manually labeled with the corresponding claims. Table 3
gives the details. These claims form the ground truth.
• Castillo Dataset. We also obtain a subset of tweets
with specific claims from 6 annotated topics in the
Castillo dataset [
tweets
168 85
283
39
104
233
67
tweets, of which 811 are unique. Nomenclature of the
claims follows that of the original annotated topics in
[
We evaluate the performance of the algorithms based on the proportion of claims they are able to identify. Let G be the set of ground truth claims and Dg be the set of tweets corresponding to a claim g ∈ G. The output of our algorithm is a set of tuple clusters, denoted C, where each cluster c ∈ C refers to a claim. In other words, C is the set of claims identified by an algorithm. For each tuple cluster c ∈ C, we retrieve all the tweets associated with the tuples in c, denoted by Dc.
We define a match function to compute the fraction of tweets common in both Dc and Dg as follows: match(c, g) = 2 × |Dc ∩ Dg| |Dc| + |Dg| Note that when C and G have identical sets of tweets, we have match(c, g) = 1. On the other hand, when C and G have totally different sets of tweets, then match(c, g) = 0. Given a claim c, we say that c sufficiently covers a ground truth claim g if match(c, g) ≥ 0.8.
We introduce a metric called Coverage to measure the ability of a method to identify claims as follows: Coverage = |Cmatch| |G| (2) (3) where Cmatch = {g ∈ G | ∃ c ∈ C, match(c, g) ≥ 0.8} The set Cmatch contains the ground truth claims that have been covered by some cluster in C.
We have two versions of ClaimF inder depending on the clustering technique used. ClaimF inder(Agglomerative) implements the bottom-up agglomerative clustering in Line 8 of Algorithm 1, while ClaimF inder(Spectral) utilizes spectral clustering.
We run an initial set of experiments on each of the datasets to find the optimal settings for the parameters to achieve the best coverage results in Figures 2, 3 for ClaimF inder. These parameters are the input number of clusters N and the weight w in Equation 1 that controls the relative importance of the S and P terms when computing the similarity scores between tuples. For the MH370 dataset, we have N = 18 and w = 0.6, whereas for the Castillo dataset, N = 6 and w = 0.8. In addition, words less than 3% or more than 30% of the number of tweets are filtered prior to clustering the MH370 dataset. For the smaller Castillo dataset, a higher minimum threshold of 4% is used. These thresholds are determined empirically based on the frequencies of words in the groundtruth claims.
Figures 2 and 3 show the coverage for ClaimF inder using the different representations and clustering techniques. Spectral clustering gives better performance in both datasets, while keywords and ngrams generally gives lower coverage regardless of the clustering techniques employed.
We observe that the proposed subject-predicate tuples consistently identify more claims in both datasets and argue that its effectiveness indicates merit in discriminating the entity and relation terms using different weights for the different types of terms. This is not possible using keywords or ngrams. In addition, it is not effective to discriminate between the subject and object entities obtained directly from the OpenIE triple due to the interchangeability of the positions of the entities in the sentence (e.g.plane abducted by alien vs alien abducts plane).
TwitterLDA [
In addition to the original TwitterLDA model, we also experimented with its variants using author pooling and temporal pooling. For the MH370 dataset, there are 3,764 tweets from 3,557 authors. These tweets are posted across a period of 15 days and thus, a daily (24 hour) time frame is chosen for its temporal pooling. For the Castillo dataset, there are 1,336 tweets from 1,100 authors, posted between 1 May to 20 August 2010. The longer timeframe motivates the use of a weekly (7 days) time frame for temporal pooling.
Implementation for the TwitterLDA based approaches is based on the publicly available code3, ran with default 100 iterations. TwitterLDA requires the number of topics as an input parameter. Our initial experiments show that the best performance is achieved when the number of topics is 12 for both datasets. We use this setting to obtain the coverage of the various TwitterLDA models.
Figures 4 and 5 show the results. We observe that using the subject-predicate tuples representation always achieves the best coverage regardless of the TwitterLDA models used. This indicates that the subject-predicate tuples are able to capture the underlying semantics of a claim.
Using keywords generally yields better coverage compared to using ngrams or the full text of the tweet. Using the full tweet results in relatively bad coverage indicating that when there are multiple claims in a tweet, some of these claims may be missed.
Overall, the best performance is obtained when the proposed subject-predicate tuples is used in conjunction with TwitterLDA(Weekly Pooled). This is because there is a temporal correlation among the claims, that is, posts containing the same claims are likely to be sent within similar time windows. In contrast, TwitterLDA(Author Pooled) does not perform well due to the low tweet-to-author ratio for both datasets.
When we compare the coverage of the best performing variant of TwitterLDA, i.e. TwitterLDA(Weekly Pooled) in Figures 4 and 5, and the best performing ClaimF inder version, i.e. ClaimF inder(Spectral) with subject-predicate tuples, we see that the latter significantly increases the number of claims identified in both datasets. We note that the MH370 dataset is noisier (more diverse set of words) than the Castillo dataset and believe that the larger improvement for the former is simply an indication of the weakness of TwitterLDA in dealing with the noise.
As a case study on the effectiveness of the proposed claim identification approach, we retrieve the sets of subject-predicate tuples in the cluster that match some ground truth claim, as well as their corresponding tweets.
The identified claims and sample tweets obtained using ClaimF inder(Spectral) are shown in Tables 5 and 6 for the MH370 and Castillo dataset respectively. We see that the tweets retrieved based on the clusters by ClaimF inder closely match the description of the ground truth claim, indicating that the subject-predicate tuples are able to capture the semantics of a claim.
Finally, we evaluate the scalability of the proposed incremental method ClaimF inderINC to identify claims.
We use 100 hash functions to generate the MinHash values, and spectral clustering for the splitting and merging operations. There are two parameters in ClaimF inderINC , namely the number of LSH vectors and the threshold to split a cluster. We use 50 LSH vectors for both the MH370 and Castillo datasets. The split threshold is 10 and 30 tuples for MH370 and Castillo dataset respectively.
Figure 6 shows the runtime of ClaimF inderINC compared to ClaimF inder (in log scale) under spectral clustering and ClaimF inder under agglomerative clustering. We observe ClaimF inderINC is several orders of magnitude faster than both versions of ClaimF inder and remains scalable as the number of tweets increases.
There are two main approaches to cluster tweets, namely
features-based and topic modeling based clustering.
Featurebased approach typically represent each tweet as a vector or
set of features from which a similarity measure can then
be used to quantify the distance between any given pair
of tweets. A commonly used set of features is the TFIDF
scores of the words present within the tweet content. Other
features useful for differentiating individual tweet to their
event include references to temporal, geographical and user
information extracted from the tweet content [
The alternative to features-based clustering is the
generative topic modeling approaches, e.g., LDA [
To date, prior work on tweet or keywords clustering are
designed mainly for topic or event detection, of which are
overly encompassing in nature for the credibility assessment
task. For example, an entity-oriented sample topic in [
In this work, we observed that tweets may contain multiple claims and define a claim as comprising of subjects and predicates terms. We described a method called ClaimF inder to identify claims in a corpus of tweets related to some real world event. In particular, we use OpenIE techniques to identify entities and their relationships in tweets and map them to subject-predicate tuples. These tuples are then clustered such that each cluster refers to a claim. We further introduced an incremental approach to quickly process incoming tweets. Empirical evaluation on two real world datasets demonstrate the effectiveness of ClaimF inder, and scalability of ClaimF inderINC . For future work, we plan to investigate existing features as well as information from other sources for credibility assessment. #Microposts2016