通过群体信号在社交网络中检测假新闻

∗5170通过群体信号在社交网络中检测假新闻0Microsoft ResearchCambridge, United Kingdomsetschia@microsoft.com0Adish Singla MPI-SWSSaarbrücken, Germanyadishs@mpi-sws.org0Manuel Gomez RodriguezMPI-SWS Kaiserslautern,Germanymanuelgr@mpi-sws.org0Arpit MerchantIIIT-H Hyderabad,Indiaarpitdm@gmail.com0Andreas KrauseETH Zurich Zurich,Switzerlandkrausea@ethz.ch0摘要0我们的工作考虑利用群体信号来检测假新闻，并受到Facebook最近推出的允许用户举报假新闻的工具的启发。通过汇总用户的举报，我们的目标是每天选择一小部分新闻，将它们发送给专家（例如通过第三方事实核查组织），并停止专家认定为假的新闻的传播。我们的工作的主要目标是通过尽快高可信地检测假新闻来最小化误导信息的传播。要有效利用用户的举报，了解用户的举报准确性至关重要。我们开发了一种新的算法Detective，通过贝叶斯推理来检测假新闻，并在时间上共同学习用户的举报准确性。我们的算法采用后验抽样来积极权衡开发（在给定时期选择最大化目标值的新闻）和探索（选择最大化关于学习用户举报准确性的信息价值的新闻）。通过广泛的实验，我们证明了我们方法的有效性，并展示了利用社区信号进行假新闻检测的能力。0ACM参考格式：Sebastian Tschiatschek, Adish Singla, Manuel GomezRodriguez, Arpit Merchant和AndreasKrause。2018年。通过群体信号在社交网络中检测假新闻。在WWW '18Companion：2018年Web会议伴随会议论文集，2018年4月23日至27日，法国里昂。ACM，纽约，美国，8页。https://doi.org/10.1145/3184558.318872201 引言0自2016年美国总统选举以来，假新闻（也称为谣言等）和错误信息的传播一直是新闻界的主题。社交媒体网站和在线社交网络，例如Facebook和Twitter，因无法遏制假新闻的传播而受到审查。存在各种各样的动机0本文根据知识共享署名4.0国际（CC BY4.0）许可发布。作者保留在其个人和公司网站上传播作品的权利，并附上适当的归属。WWW '18 Companion，2018年4月23日至27日，法国里昂 © 2018IW3C2（国际万维网会议委员会），根据知识共享CC BY 4.0许可发布。ACM ISBN978-1-4503-5640-4/18/04。https://doi.org/10.1145/3184558.31887220生成和传播假新闻的动机包括为了政治利益、损害企业声誉、作为点击诱饵以增加广告收入，以及寻求关注[1]。举个具体例子，星巴克最近成为假新闻的受害者，有人发布了一则虚假广告声称这家咖啡连锁店将为无证移民提供免费咖啡[2]。尽管星巴克迅速在社交媒体上回应个别用户，否认了这一说法，但这则虚假新闻在在线社交媒体上迅速传播的速度突显了这个问题的严重性，以及迫切需要开发新技术来应对这一挑战。为此，Facebook最近宣布了一系列努力来应对这一挑战[10,11]。通过专家验证进行检测。历史上，假新闻和错误信息一直被用作获取政治或商业利益的工具[9]。然而，基于人工编辑和专业记者的验证的传统方法无法适应在线社交网络中生成的新闻内容的数量。事实上，正是这种数量以及在这些网络中传播的速度使得这个问题具有挑战性，并需要我们开发新的计算技术。我们注意到，这种计算技术通常会补充而不是取代专家验证过程，即使一条新闻被检测出是假的，仍然需要某种形式的专家验证才能实际上阻止它。这催生了一些第三方事实核查组织，如Snopes[3]和Factcheck.org[4]，以及一套应该由这些组织遵循的原则[25]。使用计算方法进行检测。近年来，人们对于开发用于检测假新闻的计算方法的兴趣有所增加（参见[7]进行调查）——我们在相关工作部分提供了这些方法的更详细概述。这些方法通常基于构建预测模型，通过使用与新闻内容、来源可靠性和网络结构相关的特征的组合来分类判断一条新闻是否为假新闻。在训练这种预测模型时面临的主要挑战之一是可用语料库的有限性以及将新闻标记为假的主观性[27,33]。此外，设计基于估计来源可靠性的方法也是困难的01Snopes编制了一个前50个假新闻故事的列表：http://www.snopes.com/50-hottest-urban-legends/ 2http://uk.businessinsider.com/fake-news-starbucks-free-coffee-to-undocumented-immigrants-2017-8 3 http://www.snopes.com/ 4 http://factcheck.org/0主题：新闻报道、错误信息、事实核查 主题 WWW 2018，2018年4月23日至27日，法国里昂5180由于充当信息源的用户数量众多且庞大（例如Facebook上有超过十亿用户），假新闻的来源可能是无意中分享新闻故事而没有意识到新闻是假的普通用户。对于这个问题以及克服这些技术挑战的兴趣激增，导致成立了一个基于志愿者的协会FakeNewsChallenge[5]，该协会拥有100多名志愿者和70个团队，组织与检测假新闻相关的机器学习竞赛。01.1 利用用户的举报。0鉴于当前最先进的计算方法的局限性，另一种方法是通过让在线社交网络的用户举报假新闻来开发混合的人工智能方法。事实上，Facebook最近推出了在德国举报假新闻的工具[11]，如图1所示。这个工具的想法是随着新闻在网络中传播，用户可以将新闻标记为假的。0图1：Facebook已在德国推出了举报假新闻的工具。图片来源：[11]。0根据Facebook的提议[11]，聚合的用户举报以及其他可用的信号可以用来识别一组潜在的假新闻。然后可以将这些新闻发送给专家进行审查，通过第三方事实核查组织。如果专家将新闻标记为假的，可以将其从网络中删除或标记为有争议，使其在新闻推送排名中显示较低。Kim等人的现代工作[16]通过利用用户的举报活动，使用标记的时间点过程框架来探索检测假新闻的想法。我们在下一节中强调了他们的方法与我们的方法的主要区别。01.2我们的贡献0在本文中，我们开发了算法工具，以有效利用众包（用户的标记活动）来检测虚假新闻。给定一组新闻，我们的目标是选择一小部分k个新闻，将它们发送给专家进行审核，然后阻止专家标记为虚假的新闻。我们将我们的目标形式化为最小化“谣言传播”，即在新闻被阻止之前有多少用户看到虚假新闻。我们设计了我们的算法Detective，它实现了一种贝叶斯方法，用于随着时间的推移学习用户的准确性，并进行推断以找出哪些新闻是虚假的，并具有高置信度。简而言之，我们的主要贡献包括：05 http://www.fakenewschallenge.org/0最小化“谣言传播”，即在新闻被阻止之前有多少用户看到虚假新闻。我们设计了我们的算法Detective，它实现了一种贝叶斯方法，用于随着时间的推移学习用户的准确性，并进行推断以找出哪些新闻是虚假的，并具有高置信度。简而言之，我们的主要贡献包括：0•我们对利用用户的标记活动来检测虚假新闻的问题进行了形式化。我们展示了为了有效地利用他们的标记，需要学习用户的准确性。•我们开发了一种可行的贝叶斯算法Detective，它在利用用户的标记活动方面在开发和探索之间进行权衡。•我们使用一个公开可用的Facebook数据集进行了大量实验，以证明我们的方法的有效性。我们计划公开发布代码，以便其他研究人员可以在这个重要而及时的检测虚假新闻问题上构建我们的技术。02相关工作0现代结果。Kim等人通过利用用户的标记活动来检测虚假新闻。特别是，他们使用标记的时间点过程框架对上述问题进行了灵活的表示。他们开发了一个名为Curb的算法，通过解决一个新颖的随机最优控制问题来选择要发送进行事实检查的新闻。Kim等人的方法与我们的方法的关键技术差异在于：（1）我们在在线环境中学习个体用户的标记准确性；相反，他们认为所有用户的可靠性都是相等的，并从历史数据中估计用户群体的标记准确性；（2）我们的算法对于网络中新闻的实际传播动态是不可知的；他们将实际传播动态建模为具有跳跃的连续时间动力系统，并通过将问题作为最优控制问题来得到一个算法；（3）我们使用固定预算的离散时期（即每个时期可以发送给专家进行审核的新闻数量）；他们使用连续时间，并考虑算法的整体预算。检测虚假新闻的计算方法。有大量相关工作用于谣言检测和信息可信度评估（最近更关注检测虚假新闻），这些工作适用于检测虚假新闻的问题。这些方法通常基于构建预测模型来分类新闻是否为虚假。在高层次上，我们可以将这些方法分类如下：（i）基于使用自然语言处理技术的新闻内容特征[13, 31, 34,38]；（ii）通过学习源可靠性和可信度模型[20, 22,28]；（iii）通过分析新闻传播的网络结构[6]；（iv）基于上述特征的组合，即语言、源和网络结构[1, 17, 18,35]。正如我们在引言中指出的，构建准确的用于识别虚假新闻的预测模型存在一些关键挑战，包括语料库的有限可用性，基准标签的主观性以及信息源的巨大变异性。0Track:新闻学，错误信息，事实检查Track WWW 2018年4月23日至27日，法国里昂5190生成虚假新闻的人（通常是无意识地这样做的用户）是无法成功解决检测虚假新闻的挑战的。利用众包信号进行网络应用。众包已经在工业应用和与网络安全相关的不同应用的研究中被使用。例如，[23]和[5]评估了利用众包智慧评估网络钓鱼网站和网络安全的潜力。他们的研究显示用户之间存在很大的变异性 -（i）用户的参与率遵循幂律分布，（ii）用户报告的准确性有所不同，经验更丰富的用户往往具有更高的准确性。作者还讨论了在使用用户报告进行安全相关应用时的投票欺诈的潜力。Wang等人在亚马逊的MechanicalTurk上进行了一项众包研究，用于在线社交网络中的伪造检测任务。他们的研究表明，在用户报告的准确性方面，众包用户之间存在巨大的变异性，这需要在构建实际系统时加以考虑。Chen等人，Zheleva等人提出了一个与我们类似的系统，用于过滤电子邮件垃圾邮件和短信垃圾邮件。作者讨论了一个用户声誉系统，可在聚合报告时对可靠用户（基于历史）进行加权。然而，他们的工作假设系统已知用户的声誉/可靠性，而我们的论文的重点是随着时间的推移学习用户的声誉。Freeman讨论了利用用户反馈检测在线社交网络中的虚假账户的局限性 -通过使用Linkedin数据进行数据驱动的研究，作者表明，只有少数几个熟练的用户（具有随时间持续的良好准确性）可以检测出虚假账户。众包与专家验证技术从技术上来说，我们的方法可以看作是一种半监督的众包技术，其中用户的答案可以通过外部专家进行验证。Hung等人，Liu等人提出了选择特定新闻实例由专家进行标记的概率模型，以最大程度地减少对用户准确性的不确定性。与我们的方法类似，Zhao等人提出了一种贝叶斯方法，以聚合来自多个用户的信息，然后共同推断用户的可靠性以及真实标签。与我们的方法类似，他们通过两个独立参数来建模用户的准确性，分别是假阳性和假阴性率。然而，他们的方法是在无监督的环境中研究的，即没有专家验证（真实标签）可用。03模型0我们在协议1中提供了我们模型的高级规范。有一个被表示为G = (U,E)的底层社交网络，其中U是网络中的用户集合。我们将执行分为不同的时期，表示为t = 1, 2, ...,T，其中每个时期可以表示一个时间窗口，例如一天。下面，我们提供我们模型的细节 -新闻生成和传播过程，用户标记新闻的活动，以及选择新闻以获得专家标签。0我们假设每个时期t（参见第4行）的新闻由集合Xt生成。在本文中，我们考虑每个新闻都有一个潜在标签（算法不知道），“假”（f）或“非假”（¯f）。我们使用随机变量Y�(x)来表示新闻x的未知标签，其实现由y�(x)∈{f,¯f}给出。只有当新闻x被发送给专家进行审核时，我们才能获得标签y�(x)的信息，专家会提供真实的标签。我们维护一组“活跃”的新闻At0（参见第5行），其中包括到时期t结束时已生成但尚未获取专家标签的所有新闻。每个新闻x与种子该新闻的源用户相关联，表示为ox（参见第4行）。我们通过函数πt：At→ 2U来跟踪新闻在集合At中的传播。对于新闻a ∈At，函数πt(a)返回到时期t结束时已经看到新闻a的用户集合。在时期t期间，令ut(a) � U\ πt−1(a)为更多用户（可能为空集）传播新闻a ∈ At的集合。0在时期t中，新闻a传播，因此πt(a) = πt−1(a) ∪ut(a)（参见第9行）。0在时期t中，当新闻a ∈ At传播到新用户u ∈ut(a)时，该用户可以标记该新闻为假。我们将在时期t中标记新闻a为假的用户集合记为lt(a) �ut(a)（参见第10行）。此外，函数ψt(a)返回在时期t结束时将新闻a标记为假的所有用户的完整集合。对于任何新闻x和任何用户u ∈U，我们用随机变量Yu(x)表示用户u对x的标记，将Yu(x)的实现表示为yu(x) ∈ {f, ¯f}，其中yu(x) =f表示用户将该新闻标记为假。在本文中，我们考虑一个简单但现实的用户标记活动的概率模型，如下所述。用户不参与标记活动。反映现实世界用户的行为，用户u可能会选择不积极审查新闻内容（默认情况下不标记新闻）-我们用概率γu ∈ [0,1]来模拟这种情况。直观地说，我们可以将1 -γu视为用户u参与检测假新闻的众包活动的参与度：γu =1表示用户根本不参与。用户标记新闻的准确性。在（1 -γu）的概率下，用户u会审查新闻x的内容并对其进行标记。我们将用户标记的准确性/噪声建模如下：0• αu ∈ [0,1]表示用户u在新闻x不是假的且用户正在审查内容的情况下不标记新闻的概率。• βu ∈ [0,1]表示用户u在新闻x是假的且用户正在审查内容的情况下标记新闻为假的概率。0用户的观察活动。综合起来，我们可以量化用户u对任何新闻x的观察到的标记活动。0为了简化演示，我们认为网络中生成的每条新闻都是唯一的。在现实世界的设置中，由于外部因素，同一条新闻可能由多个用户发布，我们可以轻松扩展我们的模型以考虑这种情况。请注意，根据协议1的规定，对于任何新闻x，源用户ox不参与标记x。0追踪：新闻报道，错误信息，事实核查追踪WWW 2018，2018年4月23日至27日，法国里昂1 10 0�5200协议1：我们模型的高级规范01输入：社交网络图G = (U, E)；每个时期的标记预算k。02初始化：活跃新闻A0 = {}（即尚未获取专家标签的新闻）。03对于t = 1, 2, ..., T，执行以下操作：04使用ox ∈ U作为x ∈ Xt的起源/来源生成新闻Xt。05将活跃新闻集合更新为At = At−1 ∪ Xt。�x ∈ Xt，执行以下操作：06将暴露给新闻x的用户初始化为πt−1(x) = {}。07将标记新闻x的用户初始化为ψt−1(x) = {}。/*在时期t期间*/08新闻At在网络中继续传播。�a ∈ At，执行以下操作：09新闻a传播到更多用户ut(a) � U \ πt−1(a)；即πt(a) = πt−1(a) ∪ ut(a)。010新闻a被用户lt(a) � ut(a)标记为假，即ψt(a) = ψt−1(a) ∪ lt(a)。/*在时期t结束时*/011算法Algo选择一个大小最多为k的子集St � At，给出由y�(s) ∈ {f, ¯f} �s ∈ St给出的专家标签。012阻止假新闻，即�s ∈ St s.t. y�(s) = f，从网络中移除s。013将活跃新闻集合更新为At = At \ St0请注意，对于y�(s) = ¯f的新闻s ∈ St，仍然保留在网络中，继续传播，并被用户标记。0由变量（θu, ¯f, θu, f）定义的以下矩阵：0� θu, ¯f 1 - θu, f 1 -θu, ¯f θu, f0= γu0+ (1 - γu)0� αu 1 - βu 1 - αuβu0其中0θu, ¯f ≡ P � Yu(x) = ¯f | Y�(x) = ¯f �01 - θu, ¯f ≡ P � Yu(x) = f | Y�(x) = ¯f �0θu, f ≡ P � Yu(x) = f | Y�(x) = f �01 - θu,f ≡ P � Yu(x) = ¯f | Y�(x) = f �0这两个参数（αu,βu）允许我们模拟在现实世界中可能遇到的不同类型的用户。例如，0• αu ≥ 0.5，βu ≤0.5的用户可以被视为“新闻爱好者”，他们通常倾向于认为新闻不是假的；另一方面，αu ≤ 0.5，βu ≥0.5的用户可以被视为“新闻厌恶者”，他们通常倾向于持怀疑态度并标记新闻（即将其标记为假）。• αu = 1，βu =1的用户可以被视为“专家”，他们总是正确标记；αu = 0，βu=0的用户可以被视为“垃圾邮件发送者”，他们总是错误标记。03.3选择要获取专家标签的新闻0在每个时期t结束时，我们代表网络提供商应用算法Algo，选择新闻St � At发送给专家进行审查并获取真实标签y�(s) � s ∈St（参见第11行）。如果专家将新闻标记为假（即y�(s) =f），则将阻止该新闻进入网络（参见第12行）。在时期结束时，算法更新活跃新闻集合为At = At \St（参见第13行）。我们将在下一节中开发我们的算法；下面我们介绍通过网络中的假新闻最小化误导传播的形式目标。03.4目标：最小化假新闻的传播0让我们从量化阻止新闻的效用开始，a ∈ At0在时期t，阻止新闻a的效用很重要-需要注意的是，按设计，只有假新闻被阻止在网络中。回顾|πt(a)|表示到时期t结束时已经看到新闻a的用户数量。我们引入|π∞(a)|来量化如果让新闻在网络中传播，最终会看到新闻a的用户数量。然后，如果新闻a是假的，我们定义在时期t阻止新闻a的效用为valt(a) = |π∞(a)| -|πt(a)|，即效用对应于被拯救免受假新闻a的影响的用户数量。如果算法Algo在时期t选择了集合St，则算法在t = 1，...，T的总预期效用为0Util(T, Algo) =0t = 1 0s ∈ St 1{y�(s) = f}valt(s) � (1)0其中期望是在新闻传播的随机性和选择St�t∈{1,...,T}的随机性上。在这项工作中，我们将假设方程1中的量valt(a)可以通过算法进行估计。例如，可以通过在迄今为止对新闻a的传播πt(a)上拟合信息级联模型的参数，然后使用学到的参数模拟未来的传播[8,26,37]来完成这一点。给定效用值valt(∙)，我们可以考虑一个具有对所有新闻的真实标签y�(∙)访问权限的Oracle，通过选择具有最高效用的k个假新闻来最大化方程1中的目标。在下一节中，我们开发我们的算法侦探，通过执行贝叶斯推断来计算y�(∙)，使用用户的标记活动以及通过历史数据学习用户的标记准确性{θu, ¯f, θu, f}u∈U。04我们的方法论0在本节中，我们介绍我们的方法和我们的算法侦探。我们首先描述如何推断新闻标签0Track: Journalism, Misinformation, Fact Checking Track WWW 2018, April 23-27, 2018, Lyon, France.5210对于用户参数固定的情况，我们考虑用户参数未知并使用贝叶斯方法推断新闻标签和学习用户参数的情况。给定用户参数的先验分布和观察到的数据历史（用户的标记活动和获得的专家标签），一种常见的方法是计算用户参数的点估计（例如MAP）并使用它。然而，由于对学习用户参数的有限探索，这可能导致次优解。在侦探中，我们通过采用后验抽样的思想[24,29]来克服这个问题。04.1 推断新闻标签：固定用户参数0我们采用贝叶斯方法来处理最大化方程1中的未知标签y�(∙)的问题。作为热身，我们从一个更简单的设置开始，其中我们固定所有用户u∈U的标签参数(θu, ¯f, θu,f)。让我们考虑时期t和新闻a∈At，我们想要推断真实标签y�(a)。设ω为新闻是假的先验；然后，我们有兴趣计算：0))0∝ ω 0u ∈ ψt(a) P � Yu(a) = f | Y�(a) = f, θu, f �∙0u ∈ πt(a)\ψt(a) P � Yu(a) = ¯f | Y�(a) = f, θu,f �0= ω ∙0u ∈ ψt(a) θu, f ∙ �0u ∈ πt(a)\ψt(a)(1 −θu, f)0在最后两个步骤中，我们应用贝叶斯规则，并假设用户的标签是独立生成的。请注意，用户参数{θu, ¯f, θu,f}u∈U都会影响新闻是假的后验概率，因为归一化常数取决于P(Y�(a)= f | ∙)和P(Y�(a) = ¯f |∙)。在每个时间t∈{1,...,T}，我们可以使用推断的后验概率贪婪地选择k个新闻St�At，|St| = k，以最大化总体预期效用，即�0s ∈ St P(Y�(s) = f | ∙) ∙ valt(s). (2)0通过选择具有最高预期效用的k个新闻，可以以最优方式执行这种贪婪选择。这在我们的算法TopX中实现，如算法2所示。04.2 推断新闻标签：学习用户参数0在我们的设置中，用户参数{θu, ¯f, θu,f}u∈U是未知的，需要随时间学习。学习用户。我们假设用户参数(Θ¯f,Θf)在所有用户之间共享先验分布。对于每个用户u∈U，我们以以下矩阵形式维护数据历史：0Dtu = 0dtu, ¯f | ¯f dtu, ¯f |f dtu, f | ¯f dtu, f |f0������0该矩阵的条目是从获取专家标签的新闻中计算得出的。例如，dtu, ¯f |¯f表示用户u将新闻标记为非假并且获得的专家标签不是假的次数。给定Dtu，我们可以使用贝叶斯规则计算用户参数的后验分布，如下所示：0算法2：算法TopX01 输入：0• 活跃新闻At；信息价值valt(∙)，lt(∙)，πt(∙)；预算k；新闻先验ω；用户参数{θu, ¯f, θu, f}u∈U。02 计算所有a∈At的p(a)为P(Y�(a) = f | {θu, ¯f, θu,f}u∈U, ω, lt(a), πt(a))03 选择S t = arg max S � At, |S|≤k � a ∈ Sp(a)valt(a)04 返回：St0计算用户u将新闻标记为非假并且获取的专家标签不是假的次数。给定Dtu，我们可以使用贝叶斯规则计算用户参数的后验分布，如下所示：0P(θu, ¯f | Θ ¯f, Dtu) ∝ P(Dtu | θu, ¯f) ∙ P(θu, ¯f| 0= (θ u, ¯ f)dtu, ¯ f | ¯ f ∙ (1 − θ u, ¯ f)dtu, f |¯ f ∙ P(θ u, ¯ f | Θ ¯ f)0类似地，可以计算P(θu, f |∙)。推断标签。现在，我们可以使用用户参数的后验分布来推断标签，例如，首先计算MAP参数0θ MAP u, ¯ f = arg max θ u, ¯ fP(θ u, ¯ f | Θ ¯ f, Dtu)0（类似地，θMAPu, f）并调用先前部分的结果0section. 8然后，在每个时期t，我们可以使用用户参数的点估计来调用TopX，以选择一组新闻St。然而，与知道真实用户参数的算法（我们将其称为Opt）相比，这种方法可能表现得任意糟糕，如我们在分析中所示。这里的关键挑战是在探索（选择最大化学习用户参数信息价值的新闻）和开发（在给定时期直接选择预期效用的新闻）之间进行积极权衡。这是顺序决策问题中的一个基本挑战，例如，在多臂赌博机[2]，主动搜索[4,30]和强化学习中。04.3 我们的算法侦探0在本节中，我们介绍我们的算法侦探，如算法3所示，通过后验抽样（即汤普森抽样）[24，29]主动平衡探索和开发之间的权衡。在每次调用中，算法从当前用户的后验分布中对用户参数进行抽样，并使用这些参数调用TopX。直观地说，我们可以认为这种方法是根据他们是最优的概率对用户参数进行抽样。0分析。我们在Protocol1的简化变体中分析我们的算法，特别是我们进行以下简化：08注意，在这种情况下，完全贝叶斯方法用于消除关于用户参数的不确定性等效于使用后验分布的均值点估计。0Track: Journalism, Misinformation, Fact Checking Track WWW 2018, April 23-27, 2018, Lyon, France2 Samθu, ¯f ∼ P(θu, ¯f | Θ ¯f , Dtu), θu,f ∼ P(θu,f | Θf , Dtu)3 St ← Invoke TopX with parameters {θu, ¯f ,θu,f }u ∈U4 Return: StRegret T, Algo = Util T, OptUtil T, Algo .Proposition 1. Any algorithm Algo using deterministic pointestimates for the users’ parameters suffers linear regret, i.e.,Proof sketch. The proof follows by considering a simple prob-lem involving two users, where we have perfect knowledge aboutone user with parameters (0.5 +ϵ, 0.5 +ϵ) and the other user eitherhas parameters (1, 1) or (0, 0) (expert or spamer). The key idea hereis that any algorithm using point estimates can be tricked into al-ways making decisions based on the first user’s flagging activitiesand is never able to learn about the perfect second user.□Theorem 1.Proof sketch. The proof of this theorem follows via interpret-ing the simplified setting as a reinforcement learning problem. Then,we can apply the generic results for reinforcement learning via pos-terior sampling of Osband et al. [24]. In particular, we map ourproblem to an MDP with horizon 1 as follows. The actions in theMDP correspond to selecting k news from the M sources, the re-ward for selecting a set of news S is given by Equation 2 (evaluatedusing the true users’ parameters).□) (i.e., sublinear in T),erges to Opt as T → ∞.However, as a conservative bound on C could be exponential in5EXPERIMENTAL SETUPSocial network graph and news generation. We consider thesocial circles Facebook graph [19], consisting of 4,039 users (nodes)U and 88,234 edges, computed from survey data collected by usinga Facebook app for identifying social circles. Every user can be theseed of news as described shortly and to every user a probabilityis assigned with which it (hypothetically) generates fake news incase it seeds news. In particular, 20% of the users generate fakenews with probability 0.6, 40% of the users generate fake news withprobability 0.2 and the remaining 40% of the users generate fakenews with probability 0.01 (the class of a user is assigned randomly).For determining the seeds of news, we partition the users into usersUn which commonly spread news and usersUr = U \Un which onlyoccasionally spread news. That is, in every iteration of Protocol 1,we select M = 25 users for generating news, where users in Un areselected with probability0.5 and users in Ur are selected with• Fixed-CM. This algorithm leverages users’ flags withoutlearning about or distinguishing between users. It uses fixedusers parameters θu, ¯f = θu,f = 0.6 for invoking TopX.• No-Learn. This algorithm does not learn about users anddoes not consider any user flags. It greedily selects thosenews with highest valt (·), i.e.,St = argmaxS ⊆At, |S |=k�s ∈Svalt (s).• Random. This algorithm selects a random set St ⊆ At, |St | =k of active news for labeling by experts.5220算法3：算法侦探01 输入：0• 用户先验 Θf，Θ¯f；用户历史 {Dtu}u∈U。0(1) 有 M 个源 o 1 , . . . , o M ，每个源每个时期 t 生成新闻。 (2)对于在时期 t 种植的新闻 x ，只有在 τ = t 时 val τ ( x ) >0。这意味着新闻 x 在下一个时刻 t + 1达到最大传播，因此检测到该新闻的效用降至0。为了陈述我们的理论结果，让我们引入算法 Algo 的遗憾0我们现在可以立即陈述我们的第一个理论结果，强调探索的必要性。0遗憾 ( T ,  Algo )  =  Θ ( T) 。0上述结果是对不充分探索的结果，而我们的算法 Detective克服了这一问题，如下定理所示。0M ′ T  log ( CM ′ T )) ，其中 M ′ = � M k � ， C是一个问题相关的参数。C 量化了 M 条新闻传播到 U个用户以及这些用户如何标记新闻的总实现次数。0考虑到遗憾只增长为 O( √0| U  | 和  M ，收敛可能很慢。然而，在实践中，我们观察到Detective 相对于 Opt的竞争性表现。因此，Detective克服了命题1中的问题，并积极权衡了探索和利用。0| U r  | .因此，在我们的实验设置中，这相当于种植虚假新闻的先验概率约为20％，即 ω ≈0.2。新闻传播。在我们的实验中，新闻按独立级联模型传播[15]，即每个新闻的传播过程是一个单独的独立级联，感染概率为0.1 + U[0,0.1]（当新闻被种植时固定）。在协议1的每个时期，我们执行两次独立级联模型的迭代，以确定下一个时期的新闻传播情况。我们通过执行独立级联模型来估计最终会看到新闻 a 的用户数量，即 | π ∞ (a )|，对于每个新闻执行600次迭代。用户参数。在我们的实验中，我们考虑三种类型的用户，即好用户（ α u = β u = 0.9），垃圾用户（α u = β u = 0.1）和漠不关心的用户（ α u = β u =0.5）。除非另有说明，否则每个用户都随机分配给这三种类型之一。此外，我们设置 γ u = 0，除非另有说明（注意 1 − γ u表示用户的参与度）。算法。我们对 T = 100个时期执行协议1。在协议1的每个时期，评估的算法选择由专家审查的 k = 5 条新闻。在我们的实验中，我们比较了Detective、Opt（不现实：使用真实用户参数调用的TopX）、Oracle（不现实：知道真实新闻标签）。此外，我们考虑以下基线：0追踪：新闻报道，虚假信息，事实核查追踪WWW 2018，2018年4月23-27日，法国里昂120406080100time t0.00.20.40.60.81.01.2 ×10−2RANDOMORACLENO-LEARNDETECTIVEOPT(a) Learning about users0.00.20.40.60.81.00.00.20.40.60.81.0utilityRANDOMORACLENO-LEARNDETECTIVEOPT(b) Users’ engagement in flagging.0.00.20.40.60.81.00.00.20.40.60.81.0utilityRANDOMORACLENO-LEARNDETECTIVEOPTFIXED-CMFigure 2: Experimental results. (a) Learning about users: Detective achieves average utility competitive compared to thatof Oracle (which knows the true news labels). The average utility of Detective converges to that of Opt as Detectiveprogressively learns the users’ parameters. (b) Users’ engagement in flagging: even with low engagement Detective caneff