Fake News Mitigation via Point Process Based Intervention

Introduction

The recent proliferation of malicious fake news in social media has been a source of widespread concern. Given that more than $62\%$ of U.S. adults turn to social media for news, with $18\%$ doing so often, fake news can have potential real-world consequences on a large scale (Gottfried & Shearer, 2016). For example, within the final three months of the 2016 U.S. presidential election, news stories that favored either of the two nominees–later proved to be fake–were shared over 37 million times on Facebook, and over half of those who recalled seeing fake news stories believed them (Allcott & Gentzkow, 2017). An analysis by Buzzfeed News shows that the top 20 false election stories from hoax websites generated nearly 1.5 million more user engagement activities on Facebook than the top 20 stories from reputable major news outlets (Silverman, 2016). Therefore, there is an urgent call to develop effective strategies to mitigate the impact of fake news.

Policies to counter fake news can be categorized by the level of manual oversight and the aggressiveness of action required. Aggressively acting on fake news has various drawbacks. For example, Facebook’s strategy allows users to report stories as potential fake news, sends these stories to fact-checking organizations, and flags them as disputed in users’ newsfeed (Mosseri, 2016). Such direct action on the offending news requires a high degree of human oversight, which can be costly and slow, and also may violate civil rights. The report-and-flag mechanism is also open to abuse by adversaries who maliciously report real news. Given these disadvantages, we consider an alternative strategy: optimizing the performance of real news propagation over the network, ensuring that people who are exposed to fake news are also exposed to real news, so that they are less likely to be convinced by fake news.

We face several key modeling and computational issues. For example, how to quantify the uncertainty of user activities and news propagation within the network? How to measure the effect of mitigation incentives and activities? Is it possible to steer the spontaneous user mitigation activities by an intervention strategy? To address these questions, we model the temporal randomness of fake news and mitigation events (“valid news”) as multivariate point processes with self and mutual excitations, in which the control incentivizes more spontaneous mitigation events by contributing to the exogenous activity of campaigner nodes. The influence of fake news and mitigation activities is quantified using event exposure counts (i.e. the number of times that a user is exposed to fake or real news posts from other users whom she follows).

Our key contributions are as follows. We present the first formulation of fake news mitigation as the problem of optimal point process intervention in a network. The goal is to optimize the activity policy of a set of campaigner nodes to mitigate a fake news process stemming from another set of nodes. This framework enables one to design a variety of objectives to quantify the meaning of ”mitigation”, such as minimizing the number of users who see fake news but were not reached by real news. We give the first derivation of second-order statistics of random exposure counts in the non-stationary case, which is essential in policy evaluation and improvement. By defining a state space for the network, formulating actions as exogenous intensity, and defining reward functions, we map the fake news mitigation problem to an optimal policy problem in a Markov decision process (MDP), which is solved by model-based least-squares temporal difference learning (LSTD) specific to the context of point processes. Furthermore, to the best of our knowledge, we are the first to conduct a real-time point process intervention experiment.

Related work. The emergence of social media as a prominent news source in the past few years raises concomitant concerns about the quality, truthfulness, and credibility of information presented (Mitra et al., 2017). To reduce the amount of labor-intensive manual fact-checking, there have been research efforts devoted to building classifiers to detect factuality of information, predicting credibility level of posts, and detecting controversial information from inquiry phrases (Mitra et al., 2017; Zeng et al., 2016; Zhao et al., 2015). These works mainly focused on extracting linguistic features from texts to determine the credibility of news and posts. Our focus in this paper, however, is to design an incentive strategy so that users can spontaneously take action to promote real news, in opposition to a real-world fake news epidemic.

Point process models have been recently used to model activities in networks (Farajtabar et al., 2015; Parikh et al., 2012; Hosseini et al., 2017; Karimi et al., 2016; Xiao et al., 2017). More especially Hawkes process (Hawkes, 1971) is a class of self- and mutually exciting point processes that has been applied to variety of problems in social networks including cascade modeling (Zarezade et al., 2015), reliability of crowd generated data (Tabibian et al., 2016), social media popularity (Rizoiu et al., ), community detection (Tran et al., 2015), causal inference (Xu et al., 2016a), linguistic influence (Guo et al., 2015), and change point detection in social networks (Li et al., 2016).

Steering user activities by adding external incentives to the exogenous intensity of Hawkes processes was first considered in (Farajtabar et al., 2014). In (Farajtabar et al., 2016), a multistage campaigning method to optimally distribute incentive resources based on dynamic programming was developed. In these previous works, objective functions were designed using expected values of exposure counts rather than the stochastic exposure process, which may reduce the accuracy of solutions. Furthermore, it faced the demanding problem of computing the cost-to-go using the Hawkes model, while we address this using linear function approximation. For stationary Hawkes processes, second order statistics was derived in (Bacry & Muzy, 2014a, b); however, it is essential to compute both first and second order statistics for Hawkes processes in the non-stationary stages due to time sensitivity of the fake news mitigation task, and we derive it for the first time in this paper. Recent work has also applied methods in stochastic differential equations to the context of point processes, to find the best intensity for information guiding (Wang et al., 2016) and achieving highest visibility (Zarezade et al., 2017). While these works consider networks with only a single process, our work focuses on optimizing a mitigation process with respect to a second competing process. Finally, although our goal is related to influence maximization problems (Kempe et al., 2003; Bharathi et al., 2007), our point process approach is much more general and has greater temporal resolution, as it models continuous-time recurrent activity in networks, in contrast to binary discrete-time infection states in traditional influence maximization approaches. Moreover, our framework enables one to consider a variety of objectives (not only maximization) and incorporate budget constraints.

Reinforcement learning tackles the problem of finding good policies for actions to take in MDP where exact solutions are intractable, either due to size or lack of complete knowledge. Large-scale policy evaluation and iteration problems can be tackled by function approximation, which reduces the solution dimension using feature vector basis (Sutton & Barto, 1998). By adding control terms to a multivariate Hawkes process model of random network activities, fake news mitigation can be formulated as a policy optimization problem in an MDP. To address the randomness of Hawkes processes, batch reinforcement learning using samples collected from the trajectory of a fixed behavior policy can be applied (Antos et al., 2007). In particular, linear Least Squares Temporal Difference (LSTD) uses a batch of samples to learn a linear approximation of the value function under a policy with provable convergence (Bradtke & Barto, 1996). This policy evaluation step alternates with a model-based policy improvement step in a policy iteration to arrive at successively improved policies.

Preliminaries and Problem Statement

that tracks the number of events up to time $t$, where $h(t)$ is the standard Heaviside function such that $h(t)=1$ if $t\geq 0$ and $=0$ if $t<0$. The conditional intensity function of a point process is defined as the probability of observing an event in an infinitesimal window given the history. For Hawkes process it is given by

Goal. Given that both $F(t)$ and $M(t)$ are modeled by the Hawkes processes, our goal is to find the optimal mitigation strategy that specifies how to adjust the exogenous intensity of a few mitigator nodes, such that an objective function (rigorously defined in sec. 3.1) can be maximized under budget constraints. To this end, we measure the influence of fake news and mitigation activities using event exposures, describe the mechanism of mitigation interventions, and quantify the effect of interventions mathematically.

Event exposure. Event exposure is a quantitative measure of campaign influence, and is represented as a counting process, $\mathcal{E}(t)=\mathinner{\left(\mathcal{E}_{1}(t),\dots,\mathcal{E}_{n}(t)\right)}^{\mathsf{\top}}$. Here, $\mathcal{E}_{i}(t)$ records the number of times user $i$ is exposed to a campaign $N(t)$ by time $t$, where the exposure count increases whenever the user or a neighbor performs an activity. Let $B$ be the adjacency matrix of the user network, i.e., $b_{ij}=1$ if user $i$ follows user $j$, and assume $b_{ii}=1$ for all $i$. Then the exposure process is given by $\mathcal{E}(t)=BN(t)$. We define $\mathcal{F}(t)=BF(t)$ and $\mathcal{M}(t)=BM(t)$ as the fake news and mitigation exposure processes, respectively. Note that the MHP allows cascades of mutual excitations to occur among many nodes, so that non-adjacent users can also contribute to one another’s exposure counts, if there is a directed path between them.

Intervention. To maximize objectives defined for fake news mitigation in section 3.1, suppose we can perform intervention by incentivizing a subset of users in the $k$-th stage during time $[\tau_{k},\tau_{k+1})$ to trigger real news events. For simplicity, we consider uniform time duration $\tau_{k+1}-\tau_{k}=\Delta_{T}$ for $k=0,1,\dots$, since generalization to nonuniform time durations is trivial. We model the incentive by a constant intervention $u_{i}^{k}\geq 0$ added to the exogenous intensity $\mu_{i}$ during time $[\tau_{k},\tau_{k+1})$ for each stage $k=0,1,\dots$. The mitigation activity intensity at the $k$-th stage is

for $t\in[\tau_{k},\tau_{k+1})$. Note that the intervention itself exhibits a stochastic nature: adding $u_{i}^{k}$ to $\mu_{i}$ is equivalent to incentivizing user $i$ to increase her activity rate, but it is still uncertain when she will perform an activity, which appropriately mimics the randomness of the real world.

Reward function. For each stage $k$, let $x^{k}$ (defined in section 3.3) be the state of the whole MDP that encodes all the information from previous stages, and let $u^{k}$ be the current control imposed at this stage. Let $\mathcal{M}_{i}^{k}(t;x^{k},u^{k})\mathrel{\mathop{\mathchar 58\relax}}=\sum_{j}b_{ij}\int_{\tau_{k}}^{t}\operatorname{d\!}M_{j}(s)$ be the number of times user $i$ is exposed to the mitigation campaign by time $t\in[\tau_{k},\tau_{k+1})$ within stage $k$, and define $\mathcal{F}_{i}^{k}(t;x^{k},u^{k})$ similarly for the fake news exposure process. The reward function $R(x^{k},u^{k})$ can then be designed as a composite function of $\mathcal{M}$ and $\mathcal{F}$ (section 3.1).

Problem statement. By observing the counting process in previous stages (summarized in a sequence of $x^{k}$) and taking the future uncertainty into account, the control problem is to design a policy $\pi$ such that the controls $u^{k}=\pi(x^{k})$ can maximize the total discounted objective

where $\gamma\in(0,1]$ is the discount rate and $R^{k}$ is the observed reward at stage $k$. In addition, we may have constraints on the amount of control, such as a budget constraint on the sum of all interventions to users at each stage, or a cap over the amount of intensity a user can handle. A feasible set or an action space over which we find the best intervention is represented as

Proposed Method

In this section, we present the formulation of reward functions in terms of event exposures of fake news and mitigation activities. Then we derive the key statistics of the MHP required for reward function evaluation, followed by the policy iteration scheme to find the optimal intervention.

As we discussed above, the total reward of policy $\pi$ is defined by the value function

for the initial state $x^{0}$ of fake and mitigation processes, where the observed reward $R$ quantifies the effect of mitigation activities $M(t)$ in each stage and $\gamma\in(0,1]$ is the discount rate. We consider two types of reward functions $R(x,u)$:

1) Correlation Maximization: One possible way is to require correlation between mitigation exposures and fake news exposures: people exposed more to fake news should also be exposed more to the true news, so that they are less likely to believe completely in fake news. Therefore, we can design the reward function $R$ in stage $k$ to be:

2) Difference Minimization: Suppose the goal is to minimize the number of unmitigated fake news events, then we can form a reward function $R$ in stage $k$ as the least squares of unmitigated numbers:

2 Second order statistics of non-stationary MHP

To evaluate the reward function $R$ defined previously, we need to derive second order statistics of multivariate Hawkes process $N(t)$ in its non-stationary stage. The following theorem states the key ingredients for the second order statistics. The proof is provided in the appendix.

Let $N(t)$ be an $n$-dim MHP with exogenous intensity $\mu$ and Hawkes kernel $\Phi$ defined in sec. 2, then the second order statistics of $N(t)$ for $t,t^{\prime}\geq 0$ is given by

Moreover $G(t^{\prime},t)^{\mathsf{\top}}\Sigma(t^{\prime})=\Sigma(t)G(t,t^{\prime})$ for all $t,t^{\prime}\geq 0$.

3 State Representation

Hawkes process is non-Markovian and one needs complete knowledge of the history to characterize the entire process. However, when the standard exponential kernel $\Phi(t,s)=Ae^{-\omega(t-s)}h(t-s)$ is employed, the effect of history up to time $\tau_{k}$ on the future $t>\tau_{k}$ can be cleverly summarized by one scalar per dimension (Simma & Jordan, 2012; Farajtabar et al., 2016). For $1\leq i\leq n$, define $y^{k}_{i}\mathrel{\mathop{\mathchar 58\relax}}=\lambda^{k-1}_{i}(\tau_{k})-u^{k-1}_{i}-\mu_{i}$, (and $y_{0}^{i}=0$ by convention), then the intensity due to events of all previous $k$ stages can be written as $\int_{0}^{\tau_{k}}Ae^{-\omega(t-s)}\,\operatorname{d\!}N(s)=y^{k}e^{-\omega(t-\tau_{k})}$. In other words, $y^{k}$ is sufficient to encode the information of activities in the past $k$ stages that are relevant to future. Note that we have two separate $y^{k}_{M}$ and $y^{k}_{F}$ to track the dynamics of both mitigation and fake processes.

4 Least Squares Temporal Difference

The optimal value function satisfies the Bellman equation:

where $x^{\prime}$ is the next state after taking action based on policy $\pi$ at state $x$. Least squares temporal difference learning (LSTD) is a sample-efficient procedure for policy evaluation, which subsequently facilitates policy improvement. The value function is approximated by $\hat{V}^{\pi}(x)=\sum_{d=1}^{D}w^{\pi}_{d}\psi_{d}(x)$, where $\psi_{d}$ is the $d$-th feature of state $x$ and $w^{\pi}_{d}$ is its coefficient for policy $\pi$. This can be compactly represented as $\hat{V}^{\pi}(x)=\psi(x)^{\top}w^{\pi}$, where $\psi(x)=(\psi_{1}(x),\ldots,\psi_{D}(x))^{\top}$. The following presents our choice of features and the policy evaluation and improvement steps of LSTD(0) (Sutton & Barto, 1998).

Features. The number of events in a few recent consecutive intervals of point processes have been used as a reliable feature to parameterize point processes (Parikh et al., 2012; Qin & Shelton, 2015; Lian et al., 2015). Following their work we take $L$ prior intervals of length $\Delta_{f}$ for each dimension of the fake news process and record the number of events in that period as one feature. $\psi^{k}_{(l-1)n+i}=z^{k}_{(l-1)n+i}$ for $1\leq i\leq n$ and $1\leq l\leq L$. This will count for $nL$ features. Similarly we take $nL$ features from the mitigation process. Finally, we add a last feature $\psi^{k}_{2nL+1}=1$ as the bias term. Therefore, $\psi^{k}=[z^{k}_{M};z^{k}_{F};1]$ and the feature space has dimension $D=2nL+1$.

Policy Evaluation. Substituting the approximation into the Bellman equation, we have:

To find the best fit of $w^{\pi}$ we have to consider all possible $x$; however, since the state space is infinite-dimensional, enumerating all states is impossible and we utilize a set ${\mathcal{S}}$ of samples $\mathcal{S}=\{x_{1},\ldots,x_{S}\}$.

where $T^{\pi}$ is the Bellman optimality operator. A way to find a good estimate is to force the approximate value function to be a fixed point of the optimality equation under the Bellman operator, i.e., $T^{\pi}\hat{v}^{\pi}\approx\hat{v}^{\pi}.$ (Lagoudakis & Parr, 2003). For that, the fixed point has to lie in the space of approximate value functions, spanned by the basis functions $\Psi$. $\hat{v}^{\pi}$ lies in that space by definition, but $T^{\pi}\hat{v}^{\pi}$ may have an orthogonal component and must be projected. This is achieved by the orthogonal projection operator $(\Psi(\Psi^{\top}\Psi)^{-1}\Psi^{\top})$. Therefore the approximate value function $\hat{v}^{\pi}$ must be invariant under one application of the Bellman operator $T^{\pi}$ followed by orthogonal projection:

By substituting the linear approximation $\Psi w^{\pi}=v^{\pi}$ into the above equation and some manipulations, we get a $D\times D$ linear systems of equations $A^{\pi}\omega^{\pi}=b^{\pi}$, where $A^{\pi}=\Psi^{\top}(\Psi-\gamma\Psi^{\prime})$ and $b^{\pi}=\Psi^{\top}r^{\pi}$, and whose solution is the fitted coefficients $w^{\pi}$. It has been shown that the estimated $w^{\pi}$ converges to the best $w^{*}$ as the available number of samples tends to infinity (Bradtke & Barto, 1996). Appendix B presents a detailed derivation.

Policy Improvement. The second part of the algorithm implements policy improvement, i.e., getting an improved policy $\pi^{\prime}$ via one-step look-ahead as follows:

LSTD(0) alternates between the policy improvement and policy evaluation iteratively until $w^{\pi}$ converges (Bradtke & Barto, 1996). Alg. 1 summarizes this procedure.

We require much fewer samples to learn $V^{\pi}(x)$ compared to learning an approximate $Q^{\pi}(x,u)$, and in particular compared to LSPI, we avoid explicitly discretizing the continuous action space from which the action $u$ is chosen.

After learning the optimal policy (implicitly defined by $w^{\pi}$ of the linearly-approximated value function) we start at the real-time intervention part. Given a state observation, we find the optimal intervention intensity by solving eq. (15). Alg. 2 summarizes the real-time mitigation procedure.

Experiments

We evaluated our fake news mitigation framework by both simulated and real-time real-world experiments and show that our approach significantly outperforms several state-of-the-art methods and alternatives. First we verify the theoretical second order statistics in Fig. 2, whose proof can be found in appendix 2. Then we introduce the baseline methods against which we compare our proposed approach, and present the results of synthetic and real intervention experiments. The measure of performance for all methods was how much total reward could be accumulated by each method, where the reward function is defined via the objective functions in section 3.1. We conclude by examining convergence properties and representative power of the chosen linear features in section 3.4.

In this section, we empirically study the theoretical results of section 3.2. The mean and standard deviation of the empirical second order statistics averaged over 100 simulations was compared to the theoretical mean. This experiment helps to verify that it can be used in simulations to evaluate the merits of our proposed algorithm and versus the baselines. Fig. 2 demonstrates the second order correlation profile of 4 random pairs of users simulated 100 times. We see that the empirical average almost matches the theoretical average. Furthermore, it is interesting to see that the standard deviation increases with time. This is due to the aggregation of more random elements as time passes. Therefore, one should be careful with using the empirical mean without a sufficient number of random runs when the time interval is large.

2 Baselines

We compared our Least-squares Temporal Difference (LTD) intervention procedure with the following baselines. Sections 4.3 and 4.4 present experimental procedures and results.

1) CEC (Farajtabar et al., 2016): This is a recent network intervention algorithm based on point processes. It formulates a dynamic programming problem,

and uses approximate look-ahead dynamic programming implemented via Certainly Equivalence Control (CEC) (Bertsekas, 1995) to find the optimum intervention.

2) OPL (Farajtabar et al., 2014): An open loop dynamic programming control based on convex optimization that finds the best intervention for all stages in one shot:

Open Loop (OPL) is an important baseline, because comparing it against closed-loop strategies like CEC and LTD indicates how much feedback information helps improve future decisions. It quantifies the value of information in the context of dynamic programming and optimal control.

3) CLS: For each node $i$ belonging to the mitigation campaign, we compute its closeness centrality $cent_{i}=\frac{1}{\sum_{j}dis(i,j)}$, where $dis$ is the shortest distance from $i$ to $j$. Then, we assign the budget such that $u_{i}\propto cent_{i}$, meaning that budget is distributed to mitigation nodes based on their proximity to nodes according to network structure. Closeness Centrality (CLS) has been widely used in the literature as a baseline for finding influential nodes (Chen et al., 2012; De Arruda et al., 2014; Gao et al., 2015).

4) EXP: The CLS baseline is only structural and does not use the fake news infection data. EXP augments it by computing an Exposure-based Closeness Centrality, $cent^{k}_{i}=\sum_{j}\frac{\sum_{l=1}^{L}\mathcal{F}^{k-l}_{j}}{dis(i,j)}$, where the numerator is the total number of times node $j$ has been exposed to the fake news campaign in the $L$ intervals before stage $k$. The more times node $j$ has been exposed to the fake news, the more important it is for the mitigation campaign to reach it. EXP assigns the budget according to $u^{k}_{i}\propto cent^{k}_{i}$.

5) RND: This policy assigns a random solution in the convex space of feasible interventions. It serves as a baseline and improvement over this random policy makes comparison feasible across different settings.

3 Synthetic Experiments

Setup. For all except the experiment over network size, the networks were generated synthetically with $n=300$ nodes. Endogenous intensity coefficients were set as $a_{ij}\sim\mathcal{U}[0,0.5]$. To mimic real world networks, sparsity was set to $0.02$, i.e., each edge was kept with probability 0.02. The influence matrix was scaled appropriately such that the spectral radius is a random number smaller than one to ensure the stability of the process. The Hawkes kernel parameter was set to $\omega=1$, which means loosing roughly 63 % of influence after 1 time unit (minutes, hours, etc). Both fake news and mitigation processes obey these network settings. Among $n$ nodes, we assume 20 nodes create fake news and another 20 nodes can be incentivized (via the exogenous intensity) to spread true news. Each stage has length of $\Delta_{T}=1$. The discount factor was set to $\gamma=0.7$. For determining features, we set $L=2$ and we choose $\Delta_{f}=\Delta_{T}$ for simplicity. The upper bound for the intervention intensity was chosen by $\alpha_{i}\sim\mathcal{U}[0,0.5]$. The price of each person was $c^{k}_{i}=1$, and the total budget at stage $k$ was randomly generated as $C_{k}\sim(n\times\mathcal{U}[0,0.5])$. 1000 randomly sampled states were used for the LSTD algorithm. To evaluate a policy (learned by an algorithm) we simulated the network under that policy 50 times and took the discounted total reward averaged over these 50 runs as an empirical valuation of the policy. Furthermore, each single run was simulated for 10 consecutive stages; from the eleventh stage onward, the objectives contribute 0.02 of the total reward and can be discarded. For all experiments, the above settings are assumed unless it is explicitly mentioned otherwise.

Intervention results. Fig. 3 demonstrates the performance of different methods. Performance of a policy is quantified as the ratio of the total reward achieved by running the policy, over the total reward achieved by the random policy (RND). This allows us to compare the effectiveness of the algorithms over a variety of settings. All the results reported are averages over 10 runs with random networks generated according to the above setup. Overall, it is clear that LTD is almost consistently the best. It improves over the random policy by roughly 20 percent. CEC is the second best and shows the effectiveness of multi-stage and closed loop intervention. This validates our intuition that although CEC computes the reward from both fake news and mitigation processes, the lack of explicit features corresponding to previous events in its value function prevents it from learning the reason for the reward. Roughly, OPL is the third best algorithm, due to its negligence of the state and the actual events that occurred. Next, comes the EXP algorithm followed by the CLS. The poor performance of these (compared to others) shows that structural properties are not sufficient to tackle the fake news mitigation problem. EXP is roughly better than CEC because it heuristically takes into account the fake news exposure.

Fig. 3-a shows the performance with respect to increasing network size. The difference between alternative methods and the gap between LTD and others increase with the network size. Furthermore, the performance of all methods show an increase over random policy when the problem size gets larger. This illustrates the fact that efficient distribution of budget matters more when confronted with problems of increasing complexity and size.

Fig. 3-b shows the performance with respect to increasing the mitigation campaign size. Larger campaigns imply greater flexibility of intervention, which can be exploited by clever algorithms to achieve higher performance.

Fig. 3-c shows the performance with respect to increasing sparsity of the network. Interestingly, the performance of all the algorithms move towards to the random policy as the network becomes denser. This can be understood by considering a complete graph, so that no matter how and to whom we distribute the mitigation budget, all the nodes are exposed to the mitigation campaign almost equally. However, since real social networks are usually sparse, the effectiveness of the proposed method stands out.

Finally, Fig. 3-d shows the performance with respect to the length of an stage. Longer stage lengths increase the potential for a good policy to attain higher reward than a random policy, and this is reflected by the sharp increase and larger performance gap between LTD and others for longer lengths. We observe the same patterns for the distance minimization in Fig. 4 problem and avoid repeating them.

4 Real experiments

In this section we explain our real-time intervention results. To the best of our knowledge, we are the first to employ a real-time experiment to evaluate a point process based social network intervention strategy.

Setup. Using five Twitter accounts, each of which made five posts on machine learning topics at random times per day for a span of two months (Nov.-Dec. 2016), we accumulated a network of 1894 real users with 23407 directed edges in total. We used this historical data to learn the network parameters $\{\alpha_{ij},\mu^{i}\}$ using maximum likelihood (similar to related work (Zhou et al., 2013; Farajtabar et al., 2014)) with one hour as the time resolution and the kernel decay parameter $\omega$ set to 0.1. As illustrated in Fig.1 the optimal policy was learned using LSTD and policy improvement. Then the real-time experiment starts: Two of the accounts, interpreted as the source of fake news, continued to behave using the same randomized policy as they did in the data collection stage, while the posting times of the other three accounts were generated from $(u_{1},u_{2},u_{3})^{T}$, produced by our LTD strategy or a competitor strategy. Each policy was run for 10 stages of length 12 hours. Therefore, $\-\Delta_{T}=\Delta_{f}=12$. Since both fake news and mitigation accounts were tweeting random posts on machine learning, we assume negligible bias in the content that can confound the performance. At the end of each stage, all retweets–by users within the network–of the posts made during the two most recent stages were used to construct the feature vector and compute the value function, which was used to find the optimal intervention for the next stage. The methods CEC and OPL belong to the same category, and it has been shown that CEC outperforms OPL in (Farajtabar et al., 2016). Furthermore, EXP and CLS also belong to similar families and our synthetic experiments confirm the superiority of the former. So, to save time in real interventions, we only test CEC from the first and EXP from the second pair, and compare them with the random policy (RND) and with our algorithm (LTD).

Real-time intervention results. Fig. 5 shows the performance of our results compared to competitors. The results show that our approach outperforms the other three baselines by a reasonable margin. As expected CEC is the second best algorithm with a margin of 5 for the correlation maximization objective. It translates to increase in amount of correlation equal to 5, which is a noticeable amount. Furthermore, in the difference minimization task, our approach reached around 7 in difference. This means that we decreased the difference in exposure to the two processes to less 2.6 per user, which is considerable improvement. For both tasks, LTD made more mitigation posts over all daytime phases than it did over all nighttime phases, whereas the competitor strategies did the opposite. This could be a reason for its better performance. One surprising fact is that the number of retweets by users outside the network, which was not used for our features, can exceed the number of retweets by users within the network. This is because the “hashtag” feature on Twitter allows posts to be seen by a much larger set of users, who do not necessarily follow the source accounts. In addition to retweets, users can also “like” a post, indicating that they were exposed to fake or real news; while we measured this, we did not include it in the reward. Future experiments can use these two observations to widen the experimental scope and more accurately measure the effectiveness of a mitigation strategy. Despite having these limitations, our experiment serves as a proof-of-concept for the applicability of point process based intervention in networks, and–to the best of our knowledge–is the first to verify the superiority of a method in a real-time, real-world intervention setting.

Prediction evaluation results. The previous part described the evaluation scheme of real-time intervention in a social media platform. In this part, we used historical real data to mimic this procedure. We extracted 12 full 10-stage trajectories of events from the 2-month historical data under the random policy. For any of these 10 pairs, the methods were evaluated according to how well they predict the relative ordering among these 12 trajectories (with respect to the objective function). To evaluate each method, we created a sorted list of these 12 trajectories according to increasing objective, and created a second list sorted by increasing closeness to the intervention method. This closeness is the mean squared error between the prescribed intervention and actual intensity, which we inferred using maximum likelihood. Then, by computing the rank correlation of the two sorted lists, and repeating for each of the five methods, we can find out how well they perform on the prediction task. A better predictor is expected to be a better mitigation strategy. Fig. 6 shows the performance.

5 Linear approximation accuracy

In our LSTD algorithm we used a linear approximation for the value-function. One might ask how accurately can linear features approximate the value-function. To this end, we take a sample state $x$ as a state with no prior activity and intensity $\psi(x)=(0,\dots,0,1)$. This is the the initial state assumed in our experiment runs. First we empirically found $V^{\pi}(x)$ under the learned policy by simulating the process 100 times each with 10 stages. We compare the empirical average and the standard deviation of the total reward with the one estimated by the linear approximation $\psi^{\top}w^{\pi}$. Fig. 7 shows the results for correlation maximization and difference minimization. In both cases, by increasing the number of samples (used in LSTD), the estimated $w$ leads to better estimation of $V^{\pi}(x)$. First, the figure shows that we can achieve a reasonable accuracy with a fair amount of samples. Secondly, although it appears that the approximation is converging to the empirical value, we notice that increasing the number of samples beyond 4000 does not improve the error, which maintains a constant distance from 0. We believe this is because the optimal value function does not lie in the linear span of the feature space. Employing more complex features, such as polynomial features and deep neural network based representations, remain as interesting avenues for future work.

Discussion

The use of point process based intervention comes with a tradeoff: on one hand, the stochastic nature of multivariate point processes allows it to model the uncertainty of event occurrences in real-world networks; however, by adopting this stochastic model, the intervention policy can only set the optimal conditional intensity, rather than the precise best times, of fake news mitigation events. This can be improved in future experiments by choosing shorter time intervals for stages in the mitigation campaign. An assumption made in the real-world experiment is that all events by user $u$ are seen by user $v$ if $v$ follows $u$, meaning that fake or real news events at $u$ are seen by $v$. While it is true for Twitter that all tweets by $u$ will appear on the home timeline of $v$ who follows $u$ (Twitter, 2016), it is not necessarily true that a follower $v$ will see these tweets (suppose they did not access Twitter that day). Therefore, future experiments can improve the accuracy of reward and performance measurements by estimating the probability of users being online during certain time intervals and seeing tweets from accounts they follow.

It is important to note that mitigating fake news is a vague and qualitative goal, and it does not necessarily imply a reduction of fake news events. Matching the exposure of users to real and fake news is one of many possible objectives for arriving at a precise quantitative realization of mitigating fake news . One can define any objective function that accounts for the number of exposures or events from fake and real news cascades. Furthermore, the exposure itself can be interpreted in many different ways depending on the application. However, whenever there are multiple dependent event sequences and the rate function of one or many can be controlled, the point process framework naturally allows one to define objective functions based on events and to find an optimal policy with respect to the desired goal.

We acknowledge that the experiments conducted in this present work do not directly test for a reduction of fake news events, and that the content-neutral real-time experiment does not perfectly represent fake news processes, as semantic content may also contribute to propagation dynamics. From a modeling standpoint, introducing interactions between the fake and real news processes may allow one to design objectives that specifically reward the reduction of fake news events. Aside from subjecting real users to actual fake news, more complex real-world experiments that are not content-neutral, involving two competing opinions, may allow one to better measure the effectiveness of various methods in reducing the spread of one opinion. Furthermore, for future work we would like to incorporate more complex features, such as quadratic and nonlinear features. Utilizing deep neural nets is also an interesting future work for modeling complex feature set.

Acknowledgement. This project is supported in part by NSF IIS-1639792, CNS-1409635, NSF DMS-1620342, NSF IIS-1218749, NIH BIGDATA 1R01GM108341, NSF CAREER IIS-1350983, ONR N00014-15-1-2340, NVIDIA, Intel, and Amazon AWS.

References

Appendix A Proof of Theorem 2

Fix node index $j$ and $t^{\prime}\geq 0$, define $g_{ji}(t^{\prime},t)$ for all node $i$ and $t$ such that

Since the conditional intensity of $N_{i}(t)$ is $\lambda_{i}(t)$, we have

Furthermore, we have $\lambda_{i}(t)=\mu_{i}(t)+\sum_{k=1}^{n}\int_{0}^{t}\phi_{ki}(t-s)\operatorname{d\!}N_{k}(s)$ and hence

where we applied the definition of $g_{jk}$ in (18) to obtain the second equality. Combining the two equations above and using the fact that $\eta_{i}(t)=\mu_{i}(t)+\sum_{k=1}^{n}\int_{0}^{t}\phi_{ki}(t-s)\eta_{k}(s)\operatorname{d\!}s$, we obtain that

Since $j$ and $t^{\prime}$ are arbitrary, we let $G(t^{\prime},t)$ be the matrix such that the $(j,i)$-th entry of $G(t^{\prime},t)$ is $g_{ji}(t^{\prime},t)$, then we have

Note that the Wiener-Hopf equation (19) determines the unique solution $G(t^{\prime},t)$ for all $t\geq t^{\prime}$. Moreover, since MHP is simple and that $\operatorname{d\!}N_{i}(t)=0$ or $1$ a.s. for all $i$, we have

Similarly, we can switch $i$ and $j$, and $t$ and $t^{\prime}$ to obtain

i.e., $G(t^{\prime},t)^{\mathsf{\top}}\Sigma(t^{\prime})=\Sigma(t)G(t,t^{\prime})$, from which $G(t^{\prime},t)$ for $t<t^{\prime}$ is also uniquely determined. We therefore have

Appendix B Details of Policy Evaluation

We seek an approximate value function $\hat{v}^{\pi}$ that is invariant under one application of the Bellman operator $T^{\pi}$ followed by orthogonal projection:

By replacing the linear approximation, $\Psi w^{\pi}=v^{\pi}$ , and some manipulations we get:

Defining $A^{\pi}=\Psi^{\top}(\Psi-\gamma\Psi^{\prime})$ and $b^{\pi}=\Psi^{\top}r^{\pi}$ the estimated coefficients are the solution of a $D\times D$ linear systems of equation: $A^{\pi}\omega^{\pi}=b^{\pi}$.

Appendix C Details of Policy Improvement

Then, following (Farajtabar et al., 2016), we obtain

Here the second line is due to the fact that mitigation campaign and fake news process are independent of each other (given the network model). Note the linear dependence of the the objective on our intervention $u^{k}$ which combined with linear constraints result in a convex optimization problem.

The first and second order moments are computed by (Farajtabar et al., 2014) and Theorem 2, respectively.