Fake News Detection in Social Networks via Crowd Signals

Sebastian Tschiatschek∗ Adish Singla Manuel Gomez Rodriguez

Microsoft Research MPI-SWS MPI-SWS
Cambridge, United Kingdom Saarbrücken, Germany Kaiserslautern, Germany
setschia@microsoft.com adishs@mpi-sws.org manuelgr@mpi-sws.org

Arpit Merchant Andreas Krause

IIIT-H ETH Zurich
Hyderabad, India Zurich, Switzerland
arpitdm@gmail.com krausea@ethz.ch
arXiv:1711.09025v2 [cs.SI] 2 Mar 2018

ABSTRACT generating and spreading fake news, for instance, making polit-
Our work considers leveraging crowd signals for detecting fake ical gains, harming the reputation of businesses, as clickbait for
news and is motivated by tools recently introduced by Facebook increasing advertising revenue, and for seeking attention1 . As a
that enable users to flag fake news. By aggregating users’ flags, our concrete example, Starbucks recently fell victim to fake news with
goal is to select a small subset of news every day, send them to a hoax advertisement claiming that the coffee chain would give free
an expert (e.g., via a third-party fact-checking organization), and coffee to undocumented immigrants2 . While Starbucks raced to
stop the spread of news identified as fake by an expert. The main deny this claim by responding to individual users on social media,
objective of our work is to minimize the spread of misinformation the lightening speed of the spread of this hoax news in online social
by stopping the propagation of fake news in the network. It is media highlighted the seriousness of the problem and the critical
especially challenging to achieve this objective as it requires de- need to develop new techniques to tackle this challenge. To this
tecting fake news with high-confidence as quickly as possible. We end, Facebook has recently announced a series of efforts towards
show that in order to leverage users’ flags efficiently, it is crucial tackling this challenge [10, 11].
to learn about users’ flagging accuracy. We develop a novel algo- Detection via expert’s verification. Fake news and misinforma-
rithm, Detective, that performs Bayesian inference for detecting tion have historically been used as tools for making political or
fake news and jointly learns about users’ flagging accuracy over business gains [9]. However, traditional approaches based on veri-
time. Our algorithm employs posterior sampling to actively trade fication by human editors and expert journalists do not scale to the
off exploitation (selecting news that maximize the objective value volume of news content that is generated in online social networks.
at a given epoch) and exploration (selecting news that maximize In fact, it is this volume as well as the lightening speed of spread in
the value of information towards learning about users’ flagging these networks that makes this problem challenging and requires
accuracy). We demonstrate the effectiveness of our approach via ex- us to develop new computational techniques. We note that such
tensive experiments and show the power of leveraging community computational techniques would typically complement, and not
signals for fake news detection. replace, the expert verification process—even if a news is detected
as fake, some sort of expert verification is needed before one would
ACM Reference Format:
actually block it. This has given rise to a number of third-party
Sebastian Tschiatschek, Adish Singla, Manuel Gomez Rodriguez, Arpit
fact-checking organizations such as Snopes3 and Factcheck.org4 as
Merchant, and Andreas Krause. 2018. Fake News Detection in Social Networks
via Crowd Signals. In WWW ’18 Companion: The 2018 Web Conference well as a code of principles [25] that should be followed by these
Companion, April 23–27, 2018, Lyon, France. ACM, New York, NY, USA, organizations.
8 pages. https://doi.org/10.1145/3184558.3188722 Detection using computational methods. There has been a re-
cent surge in interest towards developing computational methods
1 INTRODUCTION for detecting fake news (cf., [7] for a survey)—we provide a more
detailed overview of these methods in the Related Work section.
Fake news (a.k.a. hoaxes, rumors, etc.) and the spread of misinfor-
These methods are typically based on building predictive models
mation have dominated the news cycle since the US presidential
to classify whether a news is fake or not via using a combina-
election (2016). Social media sites and online social networks, for
tion of features related to news content, source reliability, and
example Facebook and Twitter, have faced scrutiny for being unable
network structure. One of the major challenges in training such
to curb the spread of fake news. There are various motivations for
predictive models is the limited availability of corpora and the
∗ Work performed while at ETH Zurich. subjectivity of labelling news as fake [27, 33]. Furthermore, it is
difficult to design methods based on estimating source reliability
This paper is published under the Creative Commons Attribution 4.0 International
(CC BY 4.0) license. Authors reserve their rights to disseminate the work on their
1 Snopes compiles a list of top 50 fake news stories:
personal and corporate Web sites with the appropriate attribution.
WWW ’18 Companion, April 23–27, 2018, Lyon, France http://www.snopes.com/50-hottest-urban-legends/
2 http://uk.businessinsider.com/fake-news-starbucks-free-coffee-to-undocumented-
© 2018 IW3C2 (International World Wide Web Conference Committee), published
under Creative Commons CC BY 4.0 License. immigrants-2017-8
3 http://www.snopes.com/
ACM ISBN 978-1-4503-5640-4/18/04.
4 http://factcheck.org/
https://doi.org/10.1145/3184558.3188722
and network structure as the number of users who act as sources minimize the spread of misinformation, i.e., how many users end up
is diverse and gigantic (e.g., over one billion users on Facebook); seeing a fake news before it is blocked. We design our algorithm
and the sources of fake news could be normal users who unin- Detective, which implements a Bayesian approach for learning
tentionally share a news story without realizing that the news is about users’ accuracies over time as well as for performing inference
fake. A surge of interest in the problem and in overcoming these to find which news are fake with high confidence. In short, our
technical challenges has led to the establishment of a volunteer- main contributions include:
ing based association—FakeNewsChallenge5 —comprising over 100
• We formalize the problem of leveraging users’ flagging ac-
volunteers and 70 teams which organizes machine learning compe-
tivity for detection of fake news. We showcase the need to
titions related to the problem of detecting fake news.
learn about users’ accuracy in order to effectively leverage
their flags in a robust way.
1.1 Leveraging users’ flags. • We develop a tractable Bayesian algorithm, Detective, that
Given the limitation of the current state-of-the-art computational actively trades off between exploitation (selecting news that
methods, an alternate approach is to develop hybrid human-AI directly maximize the objective value) and exploration (se-
methods via engaging users of online social networks by enabling lecting news that helps towards learning about users’ flag-
them to report fake news. In fact, Facebook has recently taken ging accuracy).
steps towards this end by launching a fake news reporting tool in • We perform extensive experiments using a publicly available
Germany [11], as shown in Figure 1. The idea of this tool is that as Facebook dataset to demonstrate the effectiveness of our
news propagates through the network, users can flag the news as approach. We plan to make the code publicly available so
fake. that other researchers can build upon our techniques for this
important and timely problem of detecting fake news.

2 RELATED WORK
Contemporary results. Kim et al. [16] explored the idea of detect-
ing fake news via leveraging users’ flagging activity. In particular,
they introduce a flexible representation of the above problem using
the framework of marked temporal point processes. They develop
an algorithm, Curb, to select which news to send for fact-checking
via solving a novel stochastic optimal control problem. The key
technical differences of the approach by Kim et al. [16] to ours are:
(1) we learn about the flagging accuracy of individual users in an
online setting; in contrast, they consider all users to be equally
reliable and estimate the flagging accuracy of the population of
users from historical data; (2) our algorithms are agnostic to the
actual propagation dynamics of news in the network; they model
Figure 1: Facebook has launched tools in Germany to report the actual propagation dynamics as a continuous-time dynamical
fake news. Image source: [11]. system with jumps and arrive at an algorithm by casting the prob-
lem as an optimal control problem; and (3) we use discrete epochs
with a fixed budget per epoch (i.e., the number of news that can
As proposed by Facebook [11], the aggregated users’ flags as well as
be sent to an expert for reviewing); they use continuous time and
well as other available signals can be used to identify a set of news
consider an overall budget for their algorithm.
which potentially is fake. These news can then be sent to an expert
Computational methods for detecting fake news. There is a
for review via a third-party fact-checking organization. If an expert
large body of related work on rumor detection and information
labels the news as fake, it could be removed from the network or
credibility evaluation (with a more recent focus on fake news de-
marked as disputed making it appear lower in news-feed ranking.
tection) that are applicable to the problem of detecting fake news.
The contemporary work by Kim et al. [16] explored the idea of
These methods are typically based on building predictive models
detecting fake news via leveraging users’ flagging activity by using
to classify whether a news is fake. At a high-level level, we can cat-
the framework of marked temporal point processes. We highlight
egorize these methods as follows: (i) based on features using news
the key differences of their approach to ours in the next section.
content via natural language processing techniques [13, 31, 34, 38];
(ii) via learning models of source reliability and trustworthiness
1.2 Our Contributions
[20, 22, 28]; (iii) by analyzing the network structure over which a
In this paper, we develop algorithmic tools to effectively utilize the news propagated [6]; and (iv) based on a combination of the above-
power of the crowd (flagging activity of users) to detect fake news. mentioned features, i.e., linguistic, source, and network structure
Given a set of news, our goal is to select a small subset of k news, [1, 17, 18, 35]. As we pointed out in the Introduction, there are
send them to an expert for review, and then block the news which several key challenges in building accurate predictive models for
are labeled as fake by the expert. We formalize our objective as to identifying fake news including limited availability of corpora, sub-
5 http://www.fakenewschallenge.org/ jectivity in ground truth labels, and huge variability in the sources
who generate fake news (often constituting users who do it unin- 3.1 News Generation and Spread
tentionally). In short, these methods alone have so far proven to be We assume that new news, denoted by the set X t , are generated
unsuccessful in tackling the challenge of detecting fake news. at the beginning of every epoch t (cf., line 4).6 In this paper, we
Leveraging crowd signals for web applications. Crowdsourcing consider a setting where each news has an underlying label (un-
has been used in both industrial applications and for research stud- known to the algorithm) of being “fake" (f ) or “not fake" ( f¯). We
ies in the context of different applications related to web security. use random variable Y ∗ (x) to denote this unknown label for a news
For instance, [23] and [5] have evaluated the potential of leveraging x and its realization is given by y ∗ (x) ∈ { f , f¯}. The label y ∗ (x) can
the wisdom of crowds for assessing phishing websites and web only be acquired if news x is sent to an expert for review who would
security. Their studies show a high variability among users—(i) then provide the true label. We maintain a set of “active" news At
the participation rates of users follows a power-law distribution, (cf., line 5) which consists of all news that have been generated
and (ii) the accuracy of users’ reports vary, and users with more by the end of epoch t but for which expert’s label have not been
experience tend to have higher accuracy. The authors also discuss acquired yet.
the potential of voting fraud when using users’ reports for security Each news x is associated with a source user who seeded this news,
related applications. Wang et al. [32] performed a crowdsourcing denoted as o x (cf., line 4). We track the spread of news in the set
study on Amazon’s Mechanical Turk for the task of sybil detection At via a function π t : At → 2U . For a news a ∈ At , the function
in online social networks. Their studies show that there is a huge π t (a) returns the set of users who have seen the news a by the end
variability among crowd users in terms of their reporting accura- of epoch t. During epoch t, let u t (a) ⊆ U \ π t −1 (a) be the set of
cies that needs to be taken into account for building a practical additional users (possibly the empty set) to whom news a ∈ At
system. Chen et al. [3], Zheleva et al. [39] present a system sim- propagates in epoch t, hence π t (a) = π t −1 (a) ∪ u t (a) (cf., line 9).
ilar to that of ours for the task of filtering email spam and SMS
spam, respectively. The authors discuss a users’ reputation system 3.2 Users’ Activity of Flagging the News
whereby reliable users (based on history) can be weighted more
In epoch t, when a news a ∈ At propagates to a new user u ∈ u t (a),
when aggregating the reports. However, their work assumes that
this user can flag the news to be fake. We denote the set of users
users’ reputation/reliability is known to the system, whereas the fo-
who flag news a as fake in epoch t via a set l t (a) ⊆ u t (a) (cf.,
cus of our paper is on learning users’ reputation over time. Freeman
line 10). Furthermore, the function ψ t (a) returns the complete set
[12] discusses the limitations of leveraging user feedback for fake
of users who have flagged the news a as fake by the end of epoch
account detection in online social networks—via data-driven stud-
t.7 For any news x and any user u ∈ U , we denote the label user
ies using Linkedin data, the authors show that there is only a small
u would assign to x via a random variable Yu (x). We denote the
number of skilled users (who have good accuracy that persists over
realization of Yu (x) as yu (x) ∈ { f , f¯} where yu (x) = f signifies
time) for detecting fake accounts.
that user has flagged the news as fake. In this paper, we consider a
Crowdsourcing with expert validation On a technical side, our
simple, yet realistic, probabilistic model of a user’s flagging activity
approach can be seen as that of a semi-supervised crowdsourcing
as discussed below.
technique where users’ answers can be validated via an external
User abstaining from flagging activity. Reflecting the behavior
expert. Hung et al. [14], Liu et al. [21] present probabilistic models
of real-world users, user u might abstain from actively reviewing
to select specific news instances to be labeled by experts that would
the news content (and by default, does not flag the news)—we model
maximize the reduction in uncertainty about users’ accuracy. With a
this happening with a probability γu ∈ [0, 1]. Intuitively, we can
similar flavor to ours, Zhao et al. [36] presents a Bayesian approach
think of 1 − γu as the engagement of user u while participating in
to aggregate information from multiple users, and then jointly
this crowdsourcing effort to detect fake news: γu = 1 means that
infer users’ reliability as well as ground truth labels. Similar to our
the user is not participating at all.
approach, they model users’ accuracy via two separate parameters
User’s accuracy in flagging the news. With probability (1 − γu ),
for false positive and false negative rates. However, their approach
user u reviews the content of news x and labels the news. We model
is studied in an unsupervised setting where no expert validation
the accuracy/noise in the user’s labels, conditioned on that the user
(ground truth labels) are available.
is reviewing the content, as follows:
• αu ∈ [0, 1] denotes the probability that user u would not flag
the news as fake, conditioned on that news x is not fake and
the user is reviewing the content.
3 THE MODEL • βu ∈ [0, 1] denotes the probability that user u would flag the
We provide a high-level specification of our model in Protocol 1. news as fake, conditioned on that news x is fake and the user
There is an underlying social network denoted as G = (U , E) where is reviewing the content.
U is the set of users in the network. We divide the execution into User’s observed activity. Putting this together, we can quantify
different epochs denoted as t = 1, 2, . . . ,T , where each epoch could the observed flagging activity of user u for any news x with the
denote a time window, for instance, one day. Below, we provide
details of our model—the process of news generation and spread, 6 Forsimplicity of presentation, we consider every news generated in the network to
users’ activity of flagging the news, and selecting news to get ex- be unique. In real-world settings, the same news might be posted by multiple users
pert’s labels. because of externalities, and it is easy to extend our model to consider this scenario.
7 Note that as per specification of Protocol 1, for any news x , the source user o doesn’t
x
participate in flagging x .
 Protocol 1: High-level specification of our model
1 Input: social network graph G = (U , E); labeling budget per epoch k.
2 Initialize: active news A0 = {} (i.e., news for which expert’s label is not acquired yet).
3 foreach t = 1, 2, . . . ,T do
/* At the beginning of epoch t */
4 News X t are generated with o x ∈ U as the origin/source of x ∈ X t .
5 Update the set of active news as At = At −1 ∪ X t . ∀x ∈ X t , do the following:
6 Initialize users exposed to the news x as π t −1 (x) = {}.
7 Initialize users who flagged the news x as ψ t −1 (x) = {}.
/* During the epoch t */
8 News At continue to propagate in the network. ∀a ∈ At , do the following:
9 News a propagates to more users u t (a) ⊆ U \ π t −1 (a); i.e., π t (a) = π t −1 (a) ∪ u t (a).
10 News a is flagged as fake by users l t (a) ⊆ u t (a); i.e., ψ t (a) = ψ t −1 (a) ∪ l t (a).
/* At the end of epoch t */
11 Algorithm Algo selects a subset S t ⊆ At of up to size k to get expert’s labels given by y ∗ (s) ∈ { f , f¯} ∀ s ∈ S t .
12 Block the fake news, i.e., ∀s ∈ S t s.t. y ∗ (s) = f , remove s from the network.
13 Update the set of active news as At = At \ S t
Note that news s ∈ S t s.t. y ∗ (s) = f¯ remain in the network, continue to propagate, and being flagged by users

following matrix defined by variables (θu, f¯, θu, f ): 3.4 Objective: Minimizing the Spread of Fake
News
Let’s begin by quantifying the utility of blocking a news a ∈ At
" # " # " #
θu, f¯ 1 − θu, f 11 αu 1 − βu
= γu + (1 − γu ) at epoch t—it is important to note that, by design, only the fake
1 − θu, f¯ θu, f 00 1 − αu βu
news are being blocked in the network. Recall that |π t (a)| denotes
the number of users who have seen news a by the end of epoch t.
where
We introduce |π ∞ (a)| to quantify the number of users who would
θu, f¯ ≡ P Yu (x) = f¯ | Y ∗ (x) = f¯ eventually see the news a if we let it spread in the network. Then, if




a news a is fake, we define the utility of blocking news a at epoch

1 − θ ≡ P Yu (x) = f | Y ∗ (x) = f¯



u, f¯
t as valt (a) = |π ∞ (a)| − |π t (a)|, i.e., the utility corresponds to the

θu, f ≡ P Yu (x) = f | Y ∗ (x) = f


number of users saved from being exposed to fake news a. If an



 1 − θu, f ≡ P Yu (x) = f¯ | Y ∗ (x) = f algorithm Algo selects set S t in epoch t, then the total expected




utility of the algorithm for t = 1, . . . ,T is given by
The two parameters (αu , βu ) allow us to model users of different
T
types that one might encounter in real-world settings. For instance,
1 {y ∗ (s)=f } valt (s)
Õ h Õ i
Util(T , Algo) = E (1)
• a user with (αu ≥ 0.5, βu ≤ 0.5) can be seen as a “news t =1 s ∈S t
lover" who generally tends to perceive the news as not fake; where the expectation is over the randomness of the spread of news
on the other hand, a user with (αu ≤ 0.5, βu ≥ 0.5) can be and the randomness in selecting S t ∀t ∈ {1, . . . ,T }.
seen as a “news hater" who generally tends to be skeptical In this work, we will assume that the quantity valt (a) in Equation 1
and flags the news (i.e., label it as fake). can be estimated by the algorithm. For instance, this can be done by
• a user with (αu = 1, βu = 1) can be seen as an “expert” who fitting parameters of an information cascade model on the spread
always labels correctly; a user with (αu = 0, βu = 0) can be π t (a) seen so far for news a, and then simulating the future spread
seen as a “spammer” who always labels incorrectly. by using the learnt parameters [8, 26, 37].
Given the utility values valt (·), we can consider an oracle Oracle
3.3 Selecting News to Get Expert’s Label that has access to the true labels y ∗ (·) for all the news and maxi-
At the end of every epoch t, we apply an algorithm Algo—on behalf mizes the objective in Equation 1 by simply selecting k fake news
of the network provider—which selects news S t ⊆ At to send to an with highest utility. In the next section, we develop our algorithm
expert for reviewing and acquiring the true labels y ∗ (s) ∀s ∈ S t (cf., Detective that performs Bayesian inference to compute y ∗ (·) using
line 11). If a news is labeled as fake by the expert (i.e., y ∗ (s) = f ), the flagging activity of users as well as via learning users’ flagging
this news is then blocked from the network (cf., line 12). At the accuracy {θu, f¯, θu, f }u ∈U from historic data.
end of the epoch, the algorithm updates the set of active news as
At = At \ S t (cf., line 13). We will develop our algorithm in the next 4 OUR METHODOLOGY
section; below we introduce the formal objective of minimizing the In this section we present our methodology and our algorithm
spread of misinformation via fake news in the network. Detective. We start by describing how news labels can be inferred
for the case in which users’ parameters are fixed. Next, we consider Algorithm 2: Algorithm TopX
the case in which users’ parameters are unknown and employ a
1 Input:
Bayesian approach for inferring news labels and learning users’ pa-
rameters. Given a prior distributions on the users’ parameters and • Active news At ; information valt (·), l t (·), π t (·)
a history of observed data (users’ flagging activities and experts’ • budget k; news prior ω
labels obtained), one common approach is to compute a point esti- • users’ parameters {θu, f¯, θu, f }u ∈U .
mate for the users’ parameters (such as MAP) and use that. However, 2 Compute p(a) for all a ∈ At as
this can lead to suboptimal solutions because of limited exploration P(Y ∗ (a) = f | {θu, f¯, θu, f }u ∈U , ω, l t (a), π t (a))
towards learning users’ parameters. In Detective, we overcome
3 Select
this issue by employing the idea of posterior sampling [24, 29].
S t = arg maxS ⊆At , |S | ≤k a ∈S p(a)valt (a)
Í

4.1 Inferring News Labels: Fixed Users’ Params 4 Return: S t

We take a Bayesian approach to deal with unknown labels y ∗ (·) for
maximizing the objective in Equation 1. As a warm-up, we begin
with a simpler setting where we fix the users’ labeling parameters count of how often the user u labeled a news as not fake and the
(θu, f¯, θu, f ) for all users u ∈ U . Let’s consider epoch t and news acquired expert’s label was not fake.
Given Dut , we can compute the posterior distribution over the users’
a ∈ At for which we want to infer the true label y ∗ (a). Let ω be the
parameters using Bayes rules as follows:
prior that a news is fake; then, we are interested in computing:
P(θu, f¯ | Θf¯, Dut ) ∝ P(Dut | θu, f¯ ) · P(θu, f¯ | Θf¯ )
P(Y ∗ (a) = f | {θu, f¯, θu, f }u ∈U , ω,ψ t (a), π t (a))
dt dt
= (θu, f¯ ) u, f¯ | f¯ · (1 − θu, f¯ ) u, f | f¯ · P(θu, f¯ | Θf¯ )
Ö  
∝ω· P Yu (a) = f | Y ∗ (a) = f , θu, f ·
u ∈ψ t (a) Similarly, one can compute P(θu, f | ·).
 
Inferring labels. We can now use the users’ parameters posteriors
Ö
P Yu (a) = f¯ | Y ∗ (a) = f , θu, f
u ∈π t (a)\ψ t (a)
distributions to infer the labels, for instance, by first computing the
Ö Ö MAP parameters
=ω· θu, f · (1 − θu, f )
u ∈ψ t (a) u ∈π t (a)\ψ t (a) θ MAP = arg max P(θu, f¯ | Θf¯, Dut )
u, f¯ θ ¯ u, f
where the last two steps follow from applying Bayes rule and as-
suming that users’ labels are generated independently. Note that (and θu,
MAP similarly) and invoking the results from the previous
f
both users’ parameters {θu, f¯, θu, f }u ∈U affect the posterior proba- section.8 Then, at every epoch t we can invoke TopX with a point es-
bility of a news being fake as the normalization constant depends timate for the users’ parameters to select a set S t of news. However
on both P(Y ∗ (a) = f | ·) and P(Y ∗ (a) = f¯ | ·). this approach can perform arbitrarily bad compared to an algorithm
At every time t ∈ {1, . . . ,T }, we can use the inferred posterior prob- that knows the true users’ parameters (we refer to this algorithm
abilities to greedily select k news S t ⊆ At , |S t | = k that maximize as Opt) as we show in our analysis. The key challenge here is that
the total expected utility, i.e., of actively trading off exploration (selecting news that maximize
the value of information towards learning users’ parameters) and
P(Y ∗ (s) = f | ·) · valt (s).
Õ
(2) exploration (selecting news that directly expected utility at a given
s ∈S t epoch). This is a fundamental challenge that arises in sequential
This greedy selection can be performed optimally by selecting k decision making problems, e.g., in multi-armed bandits [2], active
news with the highest expected utility. This is implemented in our search [4, 30] and reinforcement learning.
algorithm TopX, shown in Algorithm 2.
4.3 Our Algorithm Detective
4.2 Inferring News Labels: Learning Users’ In this section, we present our algorithm Detective, shown in
Params Algorithm 3, that actively trades off between exploration and ex-
In our setting, the users’ parameters {θu, f¯, θu, f }u ∈U are unknown ploitation by the use of posterior sampling aka Thompson sam-
and need to be learnt over time. pling [24, 29]. On every invocation, the algorithm samples the
Learning about users. We assume a prior distribution over the users’ parameters from the current users’ posterior distributions
users’ parameters (Θf¯, Θf ) shared among all users. For each user and invokes TopX with these parameters. Intuitively, we can think
of this approach as sampling users’ parameters according to the
u ∈ U , we maintain the data history in form of the following matrix:
probability they are optimal.
d t t
 f¯ | f¯ du, f¯ |f 

Analysis. We analyze our algorithms in a simplified variant of
Dut =  u,
t t
.
du, d Protocol 1, in particular we make the following simplifications:

 f | f¯ u, f |f 
8 Note that a fully Bayesian approach for integrating out uncertainty about users’
The entries of this matrix are computed from the news for which
parameters in this case is equivalent to using the mean point estimate of the posterior
experts’ labels were acquired. For instance, d t ¯ ¯ represents the distribution.
u, f | f
 Algorithm 3: Algorithm Detective |U | and M, convergence may be slow. Nevertheless, in practice
we observe competitive performance of Detective compared to
1 Input:
Opt as indicated in our experiments. Hence, Detective overcomes
• user priors Θf , Θf¯ ; users’ histories {Dut }u ∈U . the issues in Proposition 1, and actively trades off exploration and
2 Sample exploitation.
θu, f¯ ∼ P(θu, f¯ | Θf¯, Dut ), θu, f ∼ P(θu, f | Θf , Dut )
3 S t ← Invoke TopX with parameters {θu, f¯, θu,f }u ∈U
5 EXPERIMENTAL SETUP
Social network graph and news generation. We consider the
4 Return: S t
social circles Facebook graph [19], consisting of 4,039 users (nodes)
U and 88,234 edges, computed from survey data collected by using
a Facebook app for identifying social circles. Every user can be the
(1) There are M sources o 1 , . . . , o M , each generating news every
seed of news as described shortly and to every user a probability
epoch t.
is assigned with which it (hypothetically) generates fake news in
(2) For any news x seeded at epoch t, valτ (x) > 0 only for τ = t.
case it seeds news. In particular, 20% of the users generate fake
This means that news x reaches it maximum spread at the
news with probability 0.6, 40% of the users generate fake news with
next timestep t + 1, hence the utility of detecting that news
probability 0.2 and the remaining 40% of the users generate fake
drops to 0.
news with probability 0.01 (the class of a user is assigned randomly).
To state our theoretical results, let us introduce the regret of an For determining the seeds of news, we partition the users into users
algorithm Algo as Un which commonly spread news and users Ur = U \Un which only
Regret(T , Algo) = Util(T , Opt) − Util(T , Algo). occasionally spread news. That is, in every iteration of Protocol 1,
We can now immediately state our first theoretical result, highlight- we select M = 25 users for generating news, where users in Un are
selected with probability |U0.5 and users in U are selected with
ing the necessity of exploration. n | r
probability |U 0.5 . Hence, in our experimental setup this corresponds
r|
Proposition 1. Any algorithm Algo using deterministic point to a prior for seeding fake news of about 20%, i.e., ω ≈ 0.2.
estimates for the users’ parameters suffers linear regret, i.e., News spreading. In our experiments, news spread according to an
independent cascade model [15], i.e., the diffusion process of every
Regret(T , Algo) = Θ(T ). news is a separate independent cascade with infection probability
0.1 + U[0, 0.1] (fixed when the news is seeded). In every epoch of
Proof sketch. The proof follows by considering a simple prob- Protocol 1, we perform two iterations of the independent cascade
lem involving two users, where we have perfect knowledge about models to determine the news spread at the next epoch. We estimate
one user with parameters (0.5 + ϵ, 0.5 + ϵ) and the other user either the number of users who would eventually see news a, i.e., |π ∞ (a)|,
has parameters (1, 1) or (0, 0) (expert or spamer). The key idea here by executing the independent cascade models for each news for
is that any algorithm using point estimates can be tricked into al- 600 iterations.
ways making decisions based on the first user’s flagging activities Users’ parameters. In our experiments we consider three types
and is never able to learn about the perfect second user. □ of users, i.e., good users (αu = βu = 0.9), spammers (αu = βu = 0.1)
The above result is a consequence of insufficient exploration and indifferent users (αu = βu = 0.5). Unless specified otherwise,
which is overcome by our algorithm Detective, as formalized by each user is randomly assigned to one of these three types. Also,
the following theorem. we set γu = 0 unless specified otherwise (note that 1 −γu quantifies
the engagement of a user).
Theorem 1. The expected regret p of our algorithm Detective Algorithms. We execute Protocol 1 for T = 100 epochs. In every
is E[Regret(T , Detective)] = O(C M ′T log(CM ′T )), where M ′ = epoch of Protocol 1, the evaluated algorithms select k = 5 news
M

k and C is a problem dependent parameter. C quantifies the total
to be reviewed by an expert. In our experiments we compare the
number of realizations of how M news can spread to U users and how performance of Detective, Opt (unrealistic: TopX invoked with
these users label the news. the true users’ parameters), Oracle (unrealistic: knows the true
news labels). In addition, we consider the following baselines:
Proof sketch. The proof of this theorem follows via interpret-
ing the simplified setting as a reinforcement learning problem. Then, • Fixed-CM. This algorithm leverages users’ flags without
we can apply the generic results for reinforcement learning via pos- learning about or distinguishing between users. It uses fixed
terior sampling of Osband et al. [24]. In particular, we map our users parameters θu, f¯ = θu, f = 0.6 for invoking TopX.
problem to an MDP with horizon 1 as follows. The actions in the • No-Learn. This algorithm does not learn about users and
MDP correspond to selecting k news from the M sources, the re- does not consider any user flags. It greedily selects those
ward for selecting a set of news S is given by Equation 2 (evaluated news with highest valt (·), i.e.,
S t = arg max valt (s).
Õ
using the true users’ parameters). □
√ S ⊆At , |S |=k
s ∈S
Given that the regret only grows as O( T ) (i.e., sublinear in T ),
this theorem implies that Detective converges to Opt as T → ∞. • Random. This algorithm selects a random set S t ⊆ At , |S t | =
However, as a conservative bound on C could be exponential in k of active news for labeling by experts.
 ×10−2
1.2 1.0 1.0
O PT O RACLE O RACLE
1.0 O RACLE
0.8 O PT 0.8 O PT
average utility

0.8 D ETECTIVE D ETECTIVE

0.6 0.6 D ETECTIVE

utility

utility
0.6
0.4 0.4 F IXED -CM
0.4 N O -L EARN N O -L EARN N O -L EARN
0.2 0.2 0.2
R ANDOM R ANDOM R ANDOM
0.0 0.0 0.0
1 20 40 60 80 100 0.0 0.2 0.4 0.6 0.8 1.0 0.0 0.2 0.4 0.6 0.8 1.0
time t engagement fraction of good users

(a) Learning about users (b) Users’ engagement in flagging. (c) Robustness against spammers

Figure 2: Experimental results. (a) Learning about users: Detective achieves average utility competitive compared to that
of Oracle (which knows the true news labels). The average utility of Detective converges to that of Opt as Detective
progressively learns the users’ parameters. (b) Users’ engagement in flagging: even with low engagement Detective can
effectively leverage crowd signals to detect fake news. (c) Robustness against spammers: Detective is effective even if the
majority of users is adversarial, highlighting the importance of learning about users’ flagging accuracy for robustly leveraging
crowd signals.

6 EXPERIMENTAL RESULTS 7 CONCLUSIONS

In this section we demonstrate the efficiency of our proposed al- In our paper we considered the important problem of leveraging
gorithm for fake news detection in a social network. All reported crowd signals for detecting fake news. We demonstrated that any
utilities are normalized by Util(T , Oracle) and all results are aver- approach that is not learning about users’ flagging behaviour is
aged over 5 runs. prone to failure in the presence of adversarial/spam users (who want
Learning about users and and exploiting user’s flags. In this to “promote” fake news). We proposed the algorithm Detective
experiment we compare the average utility, i.e., t1 Util(t, Algo) (cf., that performs Bayesian inference for detecting fake news and jointly
Equation 1), achieved by the different algorithms at epoch t for learns about users over time. Our experiments demonstrate that
t = 1, . . . ,T . The results are shown in Figure 2a. We observe that Detective is competitive with the fictitious algorithm Opt, which
Detective and Opt achieve performance close to that of Oracle. knows the true users’ flagging behaviour. Importantly, Detective
This is impressive, as these algorithms can only use the users’ (thanks to learning about users) is robust in leveraging flags even
flags and the users’ parameters {θu, f¯, θu, f }u ∈U (or their beliefs if a majority of the users is adversarial. There are some natural
about the users’ parameters in case of Detective) to make their extensions for future work. For instance, it would be useful to
predictions. We also observe that the performance of Detective extend our approach to model and infer the trustworthiness of
converges to that of Opt as Detective progressively learns the sources. It would also be important to conduct user studies by
users’ parameters. The algorithms No-Learn and Random achieve deploying our algorithm in a real-world social system.
clearly inferior performance compare to Detective.
Users’ engagement in flagging. In this experiment, we vary the ACKNOWLEDGMENTS
engagement 1−γu of the users. We report the utilities Util(T , Algo) This work was supported in part by the Swiss National Science
in Figure 2b. We observe that with increasing engagement the per- Foundation, and Nano-Tera.ch program as part of the Opensense II
formance of Detective and Opt improves while the performance project, ERC StG 307036, and a Microsoft Research Faculty Fellowship.
of the other shown algorithms is not affected by the increased Adish Singla acknowledges support by a Facebook Graduate Fellowship.
engagement. Importantly, note that also with a low engagement
Detective can effectively leverage crowd signals to detect fake REFERENCES
news. [1] Carlos Castillo, Marcelo Mendoza, and Barbara Poblete. 2011. Information credi-
Robustness against spammers. In this experiment we consider bility on twitter. In WWW. 675–684.
[2] Olivier Chapelle and Lihong Li. 2011. An empirical evaluation of thompson
only two types of users, i.e., good users and spammers. We vary sampling. In NIPS. 2249–2257.
the fraction of good users relative to the total number of users. [3] Liang Chen, Zheng Yan, Weidong Zhang, and Raimo Kantola. 2015. TruSMS:
We report the utilities Util(T , Algo) achieved by the different algo- a trustworthy SMS spam control system based on trust management. Future
Generation Computer Systems 49 (2015), 77–93.
rithms in Figure 2c. We also plot the additional baseline Fixed-CM. [4] Yuxin Chen, Jean-Michel Renders, Morteza Haghir Chehreghani, and Andreas
Observe that the performance of Fixed-CM degrades with a de- Krause. 2017. Efficient Online Learning for Optimizing Value of Information:
creasing fraction of good users. Detective (thanks to learning Theory and Application to Interactive Troubleshooting. In UAI.
[5] Pern Hui Chia and Svein Johan Knapskog. 2011. Re-evaluating the wisdom
about users) is effective even if the majority of users is adversar- of crowds in assessing web security. In International Conference on Financial
ial. This highlights the fact that it is crucial to learn about users’ Cryptography and Data Security. 299–314.
[6] Giovanni Luca Ciampaglia, Prashant Shiralkar, Luis M Rocha, Johan Bollen,
flagging accuracy in order to robustly leverage crowd signals. Filippo Menczer, and Alessandro Flammini. 2015. Computational fact checking
 from knowledge networks. PloS one 10, 6 (2015), e0128193. [24] Ian Osband, Dan Russo, and Benjamin Van Roy. 2013. (More) efficient reinforce-
[7] Niall J Conroy, Victoria L Rubin, and Yimin Chen. 2015. Automatic deception ment learning via posterior sampling. In NIPS. 3003–3011.
detection: Methods for finding fake news. Proceedings of the Association for [25] Poynter. 2016. International Fact-Checking Network: Fact-Checkers Code
Information Science and Technology 52, 1 (2015), 1–4. Principles. https://www.poynter.org/international-
[8] Nan Du, Le Song, Manuel Gomez-Rodriguez, and Hongyuan Zha. 2013. Scalable fact-checking-network-fact-checkers-
Influence Estimation in Continuous-Time Diffusion Networks. In NIPS. 3147– code-principles. (September 2016).
3155. [26] Marian-Andrei Rizoiu, Lexing Xie, Scott Sanner, Manuel Cebrián, Honglin Yu, and
[9] Stuart Ewen. 1998. PR!: a social history of spin. Basic Books. Pascal Van Hentenryck. 2017. Expecting to be HIP: Hawkes Intensity Processes
[10] Facebook. 2016. News Feed FYI: Addressing Hoaxes and Fake News. for Social Media Popularity. In WWW. 735–744.
https://newsroom.fb.com/news/2016/ [27] Victoria L Rubin, Yimin Chen, and Niall J Conroy. 2015. Deception detection for
12/news-feed-fyi-addressing-hoaxes-and- news: three types of fakes. Proceedings of the Association for Information Science
fake-news/. (December 2016). and Technology 52, 1 (2015), 1–4.
[11] Facebook. 2017. Umgang mit Falschmeldungen (Handling of false alarms). [28] Behzad Tabibian, Isabel Valera, Mehrdad Farajtabar, Le Song, Bernhard Schölkopf,
https://de.newsroom.fb.com/news/2017/ and Manuel Gomez-Rodriguez. 2017. Distilling information reliability and source
01/umgang-mit-falschmeldungen/. (January 2017). trustworthiness from digital traces. In WWW. 847–855.
[12] David Mandell Freeman. 2017. Can You Spot the Fakes?: On the Limitations of [29] William R Thompson. 1933. On the likelihood that one unknown probability
User Feedback in Online Social Networks. In WWW. 1093–1102. exceeds another in view of the evidence of two samples. Biometrika 25, 3/4 (1933),
[13] Aditi Gupta, Ponnurangam Kumaraguru, Carlos Castillo, and Patrick Meier. 2014. 285–294.
Tweetcred: Real-time credibility assessment of content on twitter. In International [30] Hastagiri P Vanchinathan, Andreas Marfurt, Charles-Antoine Robelin, Donald
Conference on Social Informatics. Springer, 228–243. Kossmann, and Andreas Krause. 2015. Discovering valuable items from massive
[14] Nguyen Quoc Viet Hung, Duong Chi Thang, Matthias Weidlich, and Karl Aberer. data. In KDD. 1195–1204.
2015. Minimizing efforts in validating crowd answers. In SIGMOD. 999–1014. [31] Svitlana Volkova, Kyle Shaffer, Jin Yea Jang, and Nathan Hodas. 2017. Separating
[15] David Kempe, Jon Kleinberg, and Éva Tardos. 2003. Maximizing the spread of Facts from Fiction: Linguistic Models to Classify Suspicious and Trusted News
influence through a social network. In KDD. 137–146. Posts on Twitter. In ACL, Vol. 2. 647–653.
[16] J. Kim, B. Tabibian, A. Oh, B. Schoelkopf, and M. Gomez-Rodriguez. 2018. [32] Gang Wang, Manish Mohanlal, Christo Wilson, Xiao Wang, Miriam J. Metzger,
Leveraging the Crowd to Detect and Reduce the Spread of Fake News and Haitao Zheng, and Ben Y. Zhao. 2013. Social Turing Tests: Crowdsourcing Sybil
Misinformation. In WSDM ’18: Proceedings of the 11th ACM International Detection. In NDSS.
Conference on Web Search and Data Mining. [33] William Yang Wang. 2017. "Liar, Liar Pants on Fire": A New Benchmark Dataset
[17] Srijan Kumar, Robert West, and Jure Leskovec. 2016. Disinformation on the web: for Fake News Detection. In ACL. 422–426.
Impact, characteristics, and detection of wikipedia hoaxes. In WWW. 591–602. [34] Wei Wei and Xiaojun Wan. 2017. Learning to Identify Ambiguous and Misleading
[18] Sejeong Kwon, Meeyoung Cha, and Kyomin Jung. 2017. Rumor detection over News Headlines. In IJCAI. 4172–4178.
varying time windows. PloS one 12, 1 (2017), e0168344. [35] Shu Wu, Qiang Liu, Yong Liu, Liang Wang, and Tieniu Tan. 2016. Information
[19] Jure Leskovec and Julian J Mcauley. 2012. Learning to discover social circles in Credibility Evaluation on Social Media.. In AAAI. 4403–4404.
ego networks. In NIPS. 539–547. [36] Bo Zhao, Benjamin IP Rubinstein, Jim Gemmell, and Jiawei Han. 2012. A bayesian
[20] Yaliang Li, Qi Li, Jing Gao, Lu Su, Bo Zhao, Wei Fan, and Jiawei Han. 2015. On approach to discovering truth from conflicting sources for data integration.
the discovery of evolving truth. In KDD. 675–684. Proceedings of the VLDB Endowment 5, 6 (2012), 550–561.
[21] Mengchen Liu, Liu Jiang, Junlin Liu, Xiting Wang, Jun Zhu, and Shixia Liu. [37] Qingyuan Zhao, Murat A. Erdogdu, Hera Y. He, Anand Rajaraman, and Jure
2017. Improving Learning-from-Crowds through Expert Validation. In IJCAI. Leskovec. 2015. SEISMIC: A Self-Exciting Point Process Model for Predicting
2329–2336. Tweet Popularity. In KDD. 1513–1522.
[22] Cristian Lumezanu, Nick Feamster, and Hans Klein. 2012. # bias: Measuring the [38] Zhe Zhao, Paul Resnick, and Qiaozhu Mei. 2015. Enquiring minds: Early detection
tweeting behavior of propagandists. In AAAI Conference on Weblogs and Social of rumors in social media from enquiry posts. In WWW. 1395–1405.
Media. [39] Elena Zheleva, Aleksander Kolcz, and Lise Getoor. 2008. Trusting spam reporters:
[23] Tyler Moore and Richard Clayton. 2008. Evaluating the wisdom of crowds in A reporter-based reputation system for email filtering. TOIS 27, 1 (2008), 3.
assessing phishing websites. Lecture Notes in Computer Science 5143 (2008),
16–30.