as a function of content (or, rather, features thereof). This is a generalization of typical network inluence models which abstract away the nature of information being shared. It is also a crucial generalization in our setting, as it allows us to directly model the balancing act by the attacker between increasing social inluence and avoiding detection. Second, we consider the problem of designing a collection of heterogeneous statistical detectors which explicitly account for network structure and difusion at the level of individual nodes, rather than merely training data of past benign and malicious instances. We formalize the overall problem faced as a Stackelberg game between a defender (manager of the social network) who deploys a collection of heterogeneous detectors, and an attacker who optimally chooses both the starting node for malicious content, and the content itself. This results in a complex bi-level optimization problem, and we introduce a novel technical approach for solving it, irst considering a naive model in which the defender knows the node being attacked, which allows us to develop a projected gradient descent approach for solving this restricted problem, and subsequently utilizing this to devise a heuristic algorithm for tackling the original problem. We show that our approach ofers a dramatic improvement over both traditional homogeneous statistical detection and a common adversarial classiication approach. Related Work. A number of prior eforts have considered limiting adversarial inluence on social networks. Most of these pit two inluence maximization players against one another, with both choosing a subset of nodes to maximize the spread of their own inluence (blocking the inluence of the other). For example, Cerenet et al. [7] consider the problem of blocking a łbadž campaign using a łgoodž campaign that spreads and thereby neutralizes the łbadž inluence. Similarly, Tsai et al. [26] study a zero-sum game between two parties with competing interests in a networked environment, with each party choosing a subset of nodes for initial inluence. Vorobeychik et al. [28] considered an inluence blocking game in which the defender chooses from a small set of security conigurations for each node, while the attacker chooses an initial set of nodes to start a malicious cascade. The main diferences between this prior work and ours is that (a) our difusion process depends on the malicious content in addition to network topology, (b) detection at each node is explicitly accomplished using machine learning techniques, rather than an abstract small set of conigurations, and (c) we consider an attacker who, in addition to choosing the starting point of a malicious cascade, chooses the content in part to evade the machine learning-based detectors. The issue of using heterogeneous (personalized) ilters was previously studied by Laszka et al. [19], but this work did not consider network structure or adversarial evasion.

Our paper is also related to prior research in single-agent inluence maximization and adversarial learning. Kempe et al. [18] initiated the study of inluence maximization, where the goal is to select a set of nodes to maximize the total subset of network afected for discrete-time difusion processes. Rodriguez et al. [16] and Du et al. [13ś15] considered the continuous-time difusion process to model information difusion; we extend this model. Prior adversarial machine learning work, in turn, focuses on the design of a single detector (classiier) that is robust to evasion attacks [6,12,20].

However, this work does not consider malicious content spreading over a social network.

We are interested in protecting a set of agents on a social network from malicious content originating from an external source, while allowing regular (benign) content to difuse. The social network is represented by a graph G = (V ,E), where V is the set of vertices (agents) and E is the set of edges. An edge between a pair of nodes represents communication or inluence between them. For example, an edge from i to j may mean that j can see and repost a video or a news article shared by i. For simplicity, we assume that the network is undirected; generalization is direct.

We suppose that each message (benign or malicious) originates from a node on the network (which may difer for diferent messages) and then propagates to others. We utilize a inite set of instances difusing over the network (of both malicious and benign content) as a training dataset D. Each instance, malicious or benign, is represented by a feature vector x ∈ R n where n is the dimension of the feature space. The dataset D is partitioned into D + and D -, where D + corresponds to malicious and D -to benign instances.

To analyze the difusion of benign and malicious content on social networks in the presence of an adversary, we develop formal models of (a) the difusion process, (b) the defender who aims to prevent the spread of malicious content while allowing benign content difuse, (c) the attacker who attempts to maximize the inluence of a malicious message, and (d) the game between the attacker and defender. We present these next.

Given an undirected network with a known topology, we use a continuous-time difusion process to model the propagation of content (malicious or benign) through the social network, extending Rodriguez et al. [16]. In our model, difusion will depend not merely on the network structure, but also on the nature of the item propagating through the network, which we quantify by a feature vector x as above.

Suppose that the difusion process for a single message originates at a node s. First, x is transmitted from s to its direct neighbors. The time taken by a propagation through an edge e is sampled from a distribution over time, f e (t; w e ,x ), which is a function of the edge itself and the entity x, and parametrized by w e . The afected (inluenced) neighbors of s then propagate x to their neighbors, and so on. We assume that an afected agent remains afected through the difusion process.

Given a sample of propagation times over all edges, the time t i taken to afect an agent i is the length of the shortest path between s and i, where the weights of edges are propagation times associated with these edges. The continuous-time difusion process is supplied with a time window T , which is used to simulate time-sensitive natures of propagation, for example, people are generally concerned about a news for several months but not for years. An agent is afected if and only if its shortest path to s is less than or equal to T . The difusion process terminates when the path from s to every unafected agent is above T . We deine the inluence σ (s,x ) large. Consequently, we can formulate the attacker's optimization problem with respect to malicious content z for a given original feature vector x as max

The attacker aims to make 1/γ 2 for each edge as large as possible, which is captured by the objective function 1 T A l z, where 1 ∈ R N l is a vector with all elements equal to one. Intuitively, this means the attacker is trying to maximize on average the parameter 1/γ 2 of every edge at layer l.

is a vector of decreasing coeicients that provides more lexibility to modeling the attacker's behavior: they are used to re-weight the importance of each layer. For example, setting

models the attacker who tries to make malicious instances spread wider at the earlier layers of the difusion. We now use similar ideas to convert the upper-level optimization problem of (4) into a more tractable form. Suppose that the node being attacked is s (and known to the defender). Then the defender wants the detection model at j to accurately identify both malicious and benign contents. This is achieved by the two indicator functions inside 1 and 2 in the reformulated objective function of the defender (6):

Notice that this expression includes a vector c l,j ∈ R N l that does not appear in (5). c l,j is a function of Θ and x, for a given node j which triggers difusion (which we omit below for clarity):

Slightly abusing notation, we let

The term k l c T l,j A l x in 1 can be expanded as follows:

noting again that l and N l depend on j, the starting node of the difusion process. From the expression (8), the defender tries to ind Θ that minimizes the impact of false positives while maximizing the impact of true negatives. This is because if each benign instance x ∈ D -is correctly identiied (false-positive rates are zero and true-negative rates are one), the summation at the second line of expression (8) will attain its maximum possible value.

In addition to facilitating the propagation of benign contents, the defender wants to limit the propagation of malicious contents, which is embodied in 2 . The equations in 2 are similar to those in 1 , except that the summation is over malicious contents D + , and 2 is accounting for the false negatives. In this case, c l,s is a function of z(x ), the adversarial feature vector which transforms x into another, z.

We now re-formulate the problem (4) as a new bilevel optimization problem (9). The upper-level problem corresponds to the defender's strategy (6), and the lower-level problem to the attacker's optimization problem (5). Here, s is again the node chosen by the attacker. min

where the last constraint ensures that w T z(x ) ≥ 0 for all attacks z(x ).

The inal step, inspired by [24,25], is to convert (9) into a singlelevel optimization problem via the KKT [5] conditions of the lowerlevel problem. With appropriate norm constraints (e.g., l 2 norm) and a convex relaxation of the indicator functions (i.e., convex surrogates of the indicator functions), the lower-level problem of (9) is convex. A convex optimization problem can be equivalently represented by its KKT conditions [8]. The single-level optimization problem then becomes:

where Fd is the objective function of Problem (9), and λ, µ, η are vectors of lagrangian multipliers. д(z,x ) = ||z -x || p -ϵ ≤ 0 is the attacker's budget constraint. h(x, Θ) is the set of equality constraints

product between η and (-z) .

In this section we demonstrate how to solve the single-level optimization obtained above by projected gradient descent. The key technical challenge is that we don't have an explicit representation of the gradients with respect to the defender's decision Θ, as these are indirectly related via the optimal solution to the attacker's optimization problem. We derive these gradients based on the implicit function of the defender's utility with respect to Θ. We begin by outlining the overall iterative projected gradient descent procedure. In iteration t we update the parameters of detection models by taking a projected gradient step:

where A d is the feasible domain of Θ and β t is the learning rate. With Θ (t +1) we solve for z (t +1) , which is the optimal attack for a ixed Θ (t +1) . ∇ Θ Fd is the gradient of the upper-level problem.

Expanding ∇ Θ Fd using the chain rule and still using s as the initially attacked node, we obtain

In both 1 and 2 we note that

is dependent on the speciic detection models. We will give a concrete example of their derivation in Section 3.5.

In l k l c T l,s A l z(x ) there are two terms that are functions of Θ: c l,s and z(x ). Consequently, (a) can be expanded as:

Note that only the detection models of those agents at layer l have contribution to c l,s . Thus, ∂c l,s ∂Θ l is a Jacobian matrix with dimension N l × N l , where N l is the number of agents at layer l and Θ l denotes the detection models of those N l agents. Since c l,s is also dependent on the speciic detection models of agents, we defer its derivation to Section 3.5.

∂Θ l is a n × N l Jacobian matrix and is the main diiculty because we do not have an explicit function of the attacker's optimal decision z(x ) with respect to Θ l . Fortunately, the constraints in (10) implicitly deine z(x ) in terms of Θ:

Θ and the attacked malicious instance z satisfy f (Θ,z,λ, µ,η) = 0. The Implicit Function Theorem [31] states that if f (Θ,z,λ, µ,η) is continuous and diferentiable and the Jacobian matrix

has full rank, there is a unique implicit function

Moreover, the derivative of ∂I ∂Θ is:

∂f ∂z is the Jacobian matrix of f (Θ,z,λ, µ,η) with respect to z, and so on. ∂z ∂Θ ∈ R n×N is the irst n rows of ∂I ∂Θ , where ∂z ∂Θ l can be column-wise indexed by the nodes at layer l.

(b) can be similarly expanded as we had done for (a), except that the attacker does not modify benign content, so that x ∈ D -is no longer a function of Θ:

The full projected gradient descent approach is given by Algorithm 1.

Algorithm 1 Find Defense Strategy 1: Input: agent j 2: Initialize:

5: end for 6: return Θ (k+1)

So far, we had assumed that the network node being attacked is ixed. However, the ultimate goal is to allow the attacker to choose both the node s, and the modiication of the malicious content z. We begin our generalization by irst allowing the attacker to optimize these jointly. The full attacker algorithm which results is described in Algorithm 2.

x (i) ← Solve (5) 5:

Ûa (i) ← Optimal objective value of (5) 6:

i,z(i,x ), Ûa (i) appended to ret 7: end for 8: z,s ← OptimalTuple(ret) 9: return z,s

Recall that the tree structure of a propagation is dependent on the agent being attacked, which makes the objective function of (5) a function of the agent being attacked. Thus, for a given ixed Θ, the attacker iterates through each agent i and solves the problem (5), assuming the propagation starts from i, resulting in associated utility Ûa (i) and an attacked instance z(i,x ). Then i, z(i,x ), and Ûa (i) are appended into a list of a 3-tuples (the sixth step in Algorithm 2). When the iteration completes the attacker picks the optimal 3-tuple in terms of utility (eighth step in Algorithm 2, where the function OptimalTuple(ret) inds the optimal 3-tuple from the list ret). The node s and the corresponding attack instance z in this optimal 3-tuple become the optimal attack.

Now we take the inal step, relaxing the assumption that the attacker chooses a ixed node to attack which is known to the defender prior to choosing Θ. Our main observation is that ixing s in the defender's algorithm above allows us to ind a collection of heterogeneous detector parameters Θ, and we can evaluate the actual utility of the associated defense (i.e., if the attacker optimally chooses both s and z in response) by using Algorithm 2. We use this insight to devise a simple heuristic: iterate over all potential nodes s that can be attacked, compute the associated defense Θ(s) (using the optimistic deinition of defender's utility in which s is assumed ixed), then ind the actual optimal attack in response for each x ∈ D + . Finally, choose the Θ(s) which has the best actual defender utility. This heuristic algorithm is described in Algorithm 3. The ifth Ûd (j) ← DefenderUtility(Θ j , (s,z(x )))

6: end for 7: j ← arg max j Ûd (j) 8: return Θ j step in the algorithm includes the function DefenderUtility, which evaluates the defender's utility Ûd (j). Note that the input argument s of this function is used to determine the tree structure of the propagation started from s.

Recall that Algorithm 1 solves (10), which depends on the speciic detection model to compute the relevant gradients. Therefore, in what follows, we present a concrete example of how to solve (10) where detection models are logistic regressions. Speciically, we illustrate how to derive the two terms, ∂1[θ j (z )=0] ∂Θ and ∂c l,j ∂Θ l that depend on particular details of the detection model.

We consider the logistic regression model used for detection at individual nodes to illustrate the ideas developed above. For a node i, its detection model has two components: the logistic regression 1 1+e -ϕ T x , where ϕ is the weight vector of the logistic regression and x the instance propagated to i, and a detection threshold θ i (which is the parameter the defender will optimize). An instance is classiied as benign if 1 1+e -ϕ T x ≤ θ i . Thus (slightly abusing notation as before), θ i (x ) 0 (x is classiied as malicious) if

∂Θ is a N -dimension vector with the jth element equal to 1 θ j -θ 2 j . The c l vector then becomes:

and ∂c l ∂Θ l becomes a N l × N l diagonal matrix:

With equations ( 12)-( 16), ∂c l ∂Θ l and ∂1[θ j (x )=0] ∂Θ

, we can now calculate ∇ Θ Fd . Since the thresholds θ i ∈ [0, 1], the defender's action space is [0, 1] N . When updating Θ by (11) we therefore project it back to [0, 1] N in each iteration.

In this section we experimentally evaluate our proposed approach. We used the Spam dataset [22] from UCI machine learning repository as the training dataset for the logistic regression model. The Spam dataset contains 4601 emails, where each email is represented a 57-dimension feature vector. We divided the dataset into three disjoint subsets: D ′ used to learn the logistic regression (tuning the weight vectors with thresholds setting to 0.5) as well as other models to which we compare, D train used in Algorithm 3 to ind the optimal defense strategy, and D test to test the performance of

We address the problem of adversarial detection of malicious content spreading through social networks. Traditional approaches use with a homogeneous detector or a personalized iltering approach. Both ignore (and thus fail to exploit knowledge of) the network topology, and most iltering approaches in prior literature ignore the presence of an adversary. We present a combination of modeling and algorithmic advances to systematically address this problem. On the modeling side, we extend difusion modeling to allow for dependence on the content propagating through the network, model the attacker as choosing both the malicious content, and initial target on the social network, and allow the defender to choose heterogeneous detectors over the network to block malicious content while allowing benign difusion. On the algorithmic side, we solve the resulting Stackelberg game by irst representing it as a bilevel program, then collapsing this program into a single-level program by exploiting the problem structure and applying KKT conditions, and inally deriving a projected gradient descent algorithm using explicit and implicit gradient information. Our experiments show that our approach dramatically outperforms, homogeneous classiication, adversarial learning, and heterogeneous but non-adversarial alternatives.