Multistage Campaigning in Social Networks
We consider the problem of how to optimize multi-stage campaigning over social networks. The dynamic programming framework is employed to balance the high present reward and large penalty on low future outcome in the presence of extensive uncertainties. In particular, we establish theoretical foundations of optimal campaigning over social networks where the user activities are modeled as a multivariate Hawkes process, and we derive a time dependent linear relation between the intensity of exogenous events and several commonly used objective functions of campaigning. We further develop a convex dynamic programming framework for determining the optimal intervention policy that prescribes the required level of external drive at each stage for the desired campaigning result. Experiments on both synthetic data and the real-world MemeTracker dataset show that our algorithm can steer the user activities for optimal campaigning much more accurately than baselines.
The paper builds on existing work in shaping social activity on social networks modeled as multivariate Hawkes processes (developed in citation [8] for constant-in-time control schemes). The paper characterizes a relationship between time-dependent exogenous activity and average activity rate in the network for exponential kernels, and uses this to derive an approximate dynamic programming control algorithm for driving activity using piecewise-constant control signals. The paper compares the performance of their control algorithm to baselines on synthetic networks with simulations, as well as real-data (using a custom performance metric) and shows promising although somewhat difficult to interpret results.
The theoretical contributions (relationship between time-dependent exogenous intensity to average activity) appear significant, and the use of this result to derive a closed-form control algorithm appears to be a contribution to the field of shaping activities in social (and other) networks modeled as multivariate Hawkes processes.  Regarding the clarity of this paper:  The paper does not frame itself relative to prior work clearly. Clearly indicating where and how this work is a generalization of prior work [8] would improve clarity of the paper, and highlight the core contribution of handling *time-dependent* exogenous events. Stating that the paper "establishes theoretical foundations of optimal campaigning over social networks where user activities are modeled as multivariate Hawkes processes" does not properly localize the work relative to [8]. This could be improved in part by mentioning [8] in the introduction, and specifically stating that prior work has done optimal control with constant exogenous control, and that this paper addresses multi-stage exogenous intensity. Similarly, in section 3 “From Intensity to Average Activity”, it should be made clear that this is an extension of a previous analogous result for constant-time activity. Finally, the three objective functions of section 4 appear to mirror the three objective functions from [8], but the text does not reveal this when it states “In what follows, we introduce several instances of the objective function...”. These changes may help the reader focus on the core and cohesive technical contribution.  The description of the closed-loop approximate dynamic programming control algorithm requires more precise language. For example, Lines 241-252 are unclear: The excerpt “By observing the counting process in previous stages summarized in a sequence of x_m) and taking future uncertainty into account, the control problem is…” needs to be more explicit (using mathematical variables) about what specific data is given to the control algorithm, and what are the specific random variables causing the "future uncertainty". For example, in Line 257: “However, when control policy \pi_m is to be implemented, only x_m is observed and there are still uncertainties in future..” Why is this a problem? Assuming “implemented” means that the policy was already determined, then isn’t implementing the policy a matter of evaluating the function \pi_m on input x_m?. Being more clear about the *computation* represented by Equation 19 and the *computation* representing Equation 18 would make it more clear how Algorithm 1 is derived in a stage-wise process (e.g. on Line 268: “Solving for .. is analytically intractable [due to ...]").  How significant is the choice of exponential kernel? It seems it may be critical to the control algorithm. If this is indeed a critical requirement, it deserves some more discussion besides just calling it “standard”.  Based on the text, in Figure 1 the error bars seem to represent standard deviation and not a form of confidence intervals, but this could be made more explicit in the figure caption.  Only the acronyms of the baselines used in Figure 1 and Figure 2 were given in the main text. The identity of these baselines could be briefly stated in the caption of Figure 1 (with citations).  Regarding the potential impact of the work:  The experimental results on synthetic data did not seem as significant of an improvement over open-loop one-time optimization over all stages as might be expected given that the closed-loop algorithm has access to significantly greater information. A demonstration for network parameter settings that better highlight the novel algorithm's strengths relative to baselines, paired with a demonstration of network parameter settings for which the distinction is less striking, would make the potential impact of the technique more clear. A discussion of in which contexts the proposed algorithm is likely to significantly improve performance would also strengthen the clarity as well as make it easier to assess impact.  The experimental results on real-world data are based on a performance metric of “predicting which cascade will reach the objective function better. They should be able to answer this by measuring how similar their prescription is to the real exogenous intensity...” This metric needs a clearer and more mathematically precise definition---the results of Figure 2 seem promising, but are hard to interpret based on the lack of clarity in the prose description of this key metric.