Social-Inverse: Inverse Decision-making of Social Contagion Management with Task Migrations
Authors: Guangmo Tong
Venue: NeurIPS 2022 Accept (2022)
Keywords: social computing
structured prediction
combinatorial optimization

Abstract: Considering two decision-making tasks $A$ and $B$, each of which wishes to compute an effective decision $Y$ for a given query $X$, can we solve task $B$ by using query-decision pairs $(X, Y)$ of $A$ without knowing the latent decision-making model? Such problems, called inverse decision-making with task migrations, are of interest in that the complex and stochastic nature of real-world applications often prevents the agent from completely knowing the underlying system. In this paper, we introduce such a new problem with formal formulations and present a generic framework for addressing decision-making tasks in social contagion management. On the theory side, we present a generalization analysis for justifying the learning performance of our framework. In empirical studies, we perform a sanity check and compare the presented method with other possible learning-based and graph-based methods. We have acquired promising experimental results, confirming for the first time that it is possible to solve one decision-making task by using the solutions associated with another one.

Social-Inverse: Inverse Decision-making of Social Contagion Management with Task Migrations
Guangmo Tong
Department of Computer and Information Sciences
University of Delaware
amotong@udel.co edu
Abstract
Considering two decision-making tasks A and B, each of which wishes to compute effective decision Y for given query X, decision pairs (X,Y) Y) of A without knowing the latent decision-making model? Such problems, called inverse decision-mann -making with task migrations, in that the complex and stochastic nature of real-world applications often prevents the agent from completely knowing the underlying system. In this paper, we introduce such a new problem with formal formulations and present a generic framework for addressing decision-making tasks in social contagion management. On the theory side, we present generalization analysis for justifying the learning performance of our framework. In empirical studies, perform sanity check and compare the presented method with other possible tearning-base and graph-based methods. We have acquired promising experimental results, confirming for the first time that it is possible to solve one decision decision-making task by using the solutions associated with another one.
solve task B by using query-
of interest
Introduction
Social contagion management. Social contagion, its most general sense, describes the diffusion process of one or more information cascades spreading between set of atomic entities through the underlying network [1, 2, 3, 4]. Prototypical applications of social contagion management include deploying advertising campaigns to maximize brand awareness [5, 6]. broadcasting debunking information to minimize the negative impact of online misinformation [7. 8, 9], HIV prevention for homeless youth [10, 11], and the prevention of youth obesity [12, 13]. In these applications, central problem is to launch new information cascades in response to certain input queries, with the goal of optimizing the agents' objectives [14, 15]. In principle, most of these tasks fall into either diffusion enhancement, which secks to maximize the influence of the to-be- be-generated cascade (c.g.. marketing campaign [5, 16, 17] and public service announcement [12, 18, 19]), diffusion containment, which aims to generate positive cascades to minimize the spread of negative cascades (e.g., misinformation [20, 21, 22] and violence- prommoing messages [23, 24]).
Inverse decision-making with task migrations. Traditional research on social contagion manage- ment often adopts classic operational diffusion models with known parameters, and focuses on algorithmic development in overcoming the NP-hardness [25, 17, 26, 27, 28). However, real-world contagions are often very complicated, and therefore, perfectly knowing the diffusion model is less realistic [29, 30, 31, 32, 33). When presented with management tasks defined over unknown diffusion models, one adopt the learn-and-optimize approach in which modeling methodologies and optimization schemes are designed separately; in such methods, the main issue is that the learning process is guided by model accuracy but not by the optimization effect [34, 35), suggesting that
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

the endeavors dedicated to model construction are neither necessary nor sufficient for successfully handling the downstream optimization problems. This motivates us explore unified frameworks that can shape the learning pipeline towards effective approximations. Recently, it has been shown that for contagion management tasks like diffusion containment, is possible to produce high-quality decisions for future queries by using query-decision pairs from the same management task without learning the diffusion model [36]. Such findings point out an interesting and fundamental question: with fixed latent diffusion model, can solve target management task by using query-decision pairs from a different management task? This is of interest because the agents often simultaneously deal with several management tasks while it is less likely that they always have the proper empirical evidence concerning the target task. For example, a network manager may need to work on a rumor blocking task, but they only have historical data collected in solving viral marketing tasks. We call such a setting as inverse decision-makinn with task migrations.
Contribution. This paper presents formal formulation of inverse decision making where the target task we wish to solve different from the source task that generates samples, with a particular focus on social contagion management tasks. Our main contribution is generic framework, called Social- Inverse, for handling migrations between tasks of diffusion enhancement and diffusion containment. For Social-Inverse we present theoretical analysis to obtain insights regarding how different contagion management tasks can be subtly correlated in order for samples from one task to help the optimization of another task. In empirical studies, we have observed encouraging results indicating that our method indeed works the way it is supposed to. Our main observations suggest that the task migrations practically manageable to satisfactory extent in many cases. In addition, we also explore the situations where the discrepancy between the target task and the source task is inherently essential, thereby making the samples from the source task less useful.
Roadmap. In Sec. 2, we first provide preliminaries regarding social contagion models, and then discuss how to formalize the considered problem. The proposed method together with its theoretical analysis is presented in Sec. 3. In Sec. 4, we present our empirical studies. We close our paper with discussion on limitations and future works (Sec. 5). The technical proofs, source code, pre-train models, data, and full experimental analysis can be found in the supplementary material. The data and source code is maintained online!
2 Preliminaries
2.1 Stochastic diffusion model
A social network is given by a directed graph G -V, E), with V and E respectively denoting the user set and the edge set. In modeling the contagion process, let us assume that there are L. E Z information cascades (= each of which is associated with seed set S; C V. Without loss of generality, we assume that S, SS = for i j. A diffusion model M is governed by two sets of
configurations: each node u E V is associated with a distribution N,, over 2%v,, where N₂ is the set of the in-neighbors of u; each edge (u, v) E E is associated with a distribution T (u.c) over (0, +o0) denoting the transmission time. During the diffusion process, node can be inactive Cs-active if activated by cascade C. Given the seed sets, the diffusson process unfolds as follows:
Initialization: Each node u samples subset A, S Nj following No. and each edge (u, v) samples a real number ((,,)) 2 0 following T (u.,))
Time O: The nodes in S; become actave at time 0, and other nodes are inactive.
Time l: When a node becomes C,-active at time I, for each inactive node v such that u is in Ag. e will be activated by and become Ci-active at time I ++ ((u,o)- Each node will be activated by the first in-neighbor attempting to activate them and never deactivated. When a node is activated by two more in-neighbors at the same time, v will be activated by the cascade with the smallest index.
The considered model is in general highly expressive because N,, and T (v.,)) can be flcxibly designed. For sample, it subsumes the classic independent cascade model [25] by making N,, sample each in in-neighbor independently. When there only one or two cascades, the above model generalizes a few popular diffusion models, including discrete-ting time independent cascade model [25].
Remark 1.
'nttps://githinn htt.aaab.oooncesaaaaaottonnr//na inverse

---

discrete-time linear threshold model [25], continuous- independent cascade model [37], and independent multi-cascade model [38, 36].
Definition 1 (Realization). Notice that the initialization phase essentially samples weighted subgraph, and the diffusion process becomes deterministic after the initialization phase. For an abstraction, we call each of such weighted subgraph a realization. and use Rg to denote the space of weighted subgraphs of G. With the concept of realization, we may abstract a concrete stochastic diffusion model M as a collection of density functions, i.c., M {N
E V} {7 (u.e) (u, E}. Slightly abusing the notation, also use M Rr + [o, 1] to denote the distribution over Ra induced by the density functions specified by M. On top of a diffusion model M. the distribution of the diffusion outcome depends on the seed sets of the cascades. An example for illustrating the diffusion process is given in Appendix A.
2.2 Social contagion management tasks
In this paper, we focus on the following two classes of social contagion management tasks.
Problem 1 (Diffusion Enhancement (DE)). Given diffusion model M and set of target users (X. Y) be the expected number users in X who are activated by cascade from seed set Y C V. We would like to find seed set with at most k E & nodes such that the total influence on X can be maximized, i.e.,
X S V. we consider the single-cascade case and let fM (DF
arg max fM (X.
(I)
Problem 2 (Diffusion Containment (DC)). Given diffusion model M, now consider the situation of competitive diffusion where there is a negative cascade C1 with a seed set X S V and a positive cascade C2 with seed Y C V. Let (X, (X,Y) be the expected number of users who are not activated by the negative cascade. Given the diffusion model . and the seed set X of the negative cascade, we would like find seed set Y for the positive cascade with most k E Z nodes such that the impact of the negative cascade can be maximally limited, i.e.,
arg max LM YX, YSKINTK
Contagion management tasks like Problems and might be viewed as decision- making problems aiming to infer an effective decision Y in response to a query X In such a sense, we may abstract such problems in the following way:
Problem 3 (Abstract Contagion Management Tasks). Given a diffusion model M, abstract management task T is specified by an objective function (X, 2 x 2 + R. a candidate space X' S 2V of the queries, and a candidate space VT C 2 of the decisions, where we wish to compute
MM,,, == arg max SM (X,)) YEYr
for each input query X E Xr. We assume that Xy and Vr are matroids over V, subsuming common constraints such the cardinality constraint or k-partition [39]. Since such optimization problems are often NP-hard, their approximate solutions are frequently used, and we denote by YM,,, an a-approximation to Equation 3.
Definition 2 (Linearity over Kernel Functions). In addressing the above management tasks, it is worth noting that the objective function calculated over the possible diffusion outcomes, which are determined in the initialization phase. Specifically, denoting by f (X, Y) the objective value projected to a single realization r E Rg. the objective function can be expressed as
- [ M(r) FF(XX
BMXXY)-
JIERO
The function f:T (X, is called kernel, in the sense that it transforms set structures into real numbers. For example, (PE(X)Y) Y)) denotes the number of users in who are activated by a cascade generated from Y in a single realization fPC(X Y) denotes the number of users in G who are not activated by the negative cascade (generated from X) in realization r when the positive cascade spreads from Y.
3

---

where ā E (0, 1] is introduced to measure the optimality of the sample decisions. For the purpose of theoretical analysis, the ratio ã may be interpreted as the best approximation ratio that can be achieved by polynomial-tima algorithm under common complexity assumptions (e.g., NP + P). For DE and DC, we have the best ratio as 1 1/c due the well-known fact that their objective 2.3 Inverse pocision-making of contagion management with task migrations
Supposing that the diffusion model .M is given, DE and DC are purely combinatorial optimization problems, which have been extensively studied [25, 20]. In the case that the diffusion model is unknown, inverse decision-making is potential solution, which seeks to solve contagion management tasks by directly learning from query-decision pairs [40]. In particular, with respect to a certain management task J&4 associated with an unknown diffusion model M, the agent receives collection of pairs (X,, Y3) where Y; is the optimal/suboptimal solution to maximizing f'M Y). Such empirical evidence can be mathematically characterized as
MM (X., V.T...)) fX,, M.T.X.)) 2 a- max
(,,,, m YEJT
(5)
functions are submodular [25, 20 Leveraging such empirical evidence, we wish to solve the same or different management task for future queries:
Problem 4 (Inverse Decision- Decision-making with Task Migrations). Suppose that there is an underlying diffusion model Mirue. Consider two management tasks To and T' defined in Problem 3, where
Sa To is the source task and To is the target task. With a collection MMrrseiTo m of samples concerning the source task Tø for some ratio T E (0, 1]. we aim to build a framework A Xro - Vro that can make a prediction A(X) for each future query X of the target task To. Let be a loss function 1(X,Y) XTo x X.To + [0, 1] that measures the desirability of Ý with respect to X. We seek to minimize the generalization error & with respect to an unknown distribution D over Nro:
[(A, = EXDD A(X))
Since Morue and m are fixed, we denote S the case where the source task and the target task are selected from DE and DC.
M To .m as ST for conciseness. We will focus on
Remark 2. In general, the above problem appears to be challenging because the query query-decision pairs of one optimization problem do not necessarily shed any clues on effectively solving another optimization problem. What makes our problem tractable is that the source task and the target task share the same underlying diffusion model Marve- With the hope that the query-decision pairs of the source task can identify MMrrue to a certain extent, we may solve the target task with statistical significance, as evidenced in experiments. In such a sense, our setting is called inverse as it implicitly infers the structure of the underlying model from solutions, in contrast to the forward decision-making pipeline that seeks solutions based on given models.
3 Social-Inverse
In this section, we present a learning framework called Social-Inverse for solving Problem 4. Our method is inspired by the classic structured prediction [41] coupled with randomized kernels [40], which may be ultimately credited to the idea of Random Kitchen Sink [42]. Social-Inverse starts by selecting an empirical distribution Mem over RG and a hyperparameter K Z, and then proceeds with the following steps:
Hypothesis design. Sample K iid realizations Rx (rI,...,TK) S RG following Mem E RK) where
and obtain the hypothesis space F Rxx HH
Rx Rx, (X,Y): :
H Ho fg. is the affine combination of TTo over the realizations in Rx:
K
H 1 RK (X,Y)
= Σ w To (X,
1=1
T Training, Compute a prior vector w using the training set S (Sec. 3.2), and sample the final parameter w from an isotropic Gaussian Q(7 w, I) with mean of w scaled by y- The selection of will be discussed in Sec. 3.1.

---

Inference. Given a future query X E ATo of the target task To. the prediction is made by solving the inference problem over the hypothesis in FRx associated with final weight w:
arg max H w (X,Y). YEVTO
It is often NP-hard to solve the above inference problem in optimal, and therefore, assume that an ag approxiixxiino Equation 8 denoted by Y RR..W.X w. is employed for some K E (0, Notice that the ratio og herein represents the inference hardness, while the ratio & associated with the training set measures the hardness of the source task.
In completing the above procedure, it is left to determine a) the prior distribution Mem b) the hyperparameter K, c) the scale factor y, d) the training method for computing the prior vector w, and e) the inference algorithm for computing Rig w..x what follows, we will first discuss how they may influence the generalization performance theory, and then present methods for their selections. For the convenience of reading, the notations are summarized in Table in Appendix B.
y
3.1 Generalization analysis
For Social-Inverse, given the fact the generation of w is randomized, the generalization error is further expressed as
[(Social-Inverse D,1)= =Dxxxx, [[X. y m
In deriving an upper bound with respect to the prior vector w, let notice that the empirical risk is yo0 given by ((,,, yag Rx,,w,x)). which randomized by w ~ Q( I)). Thus, the prediction Rx w. associated with a training input X; is most likely one of those centered around yu Rx. W. W. and we will measure such concentration by their difference in terms fraction of the empirical risk associated with w. More specifically, controlled by hyperparameter 3 E (0, a for an input query X,, the potential predictions are those within the margin:
10
(10)
Ri W.B.B
Y Vo: āo H1x
(Xi,
yo w.x)
Rx. (X,,)) S Rx w (Xi, yão
The empirical risk is therefore given via the above margin:
Lem RR.
The ST
1)
max 1(X,, Y). 11 1g YEVO
vr X,. (Y),
(11)
where (x) E 1) is the indicator function: 1s(x) 1 + x E S. With the above progressions, we have the following result concerning the generalization error.
Theorem 1. For each (W1. Wk), RK Ro. B E (0, az), and 8 0, with probability at least 8, we have
2
2 /2 + In (m//))
S(Social-Inverse D,I) S Lem (W, RK. S 5a 1) +
+
m
2(m 1)
provided that
0g +
2mk |w|]
7 minp Wp B 20
2 In
(12)
The proof follows from the standard analysis of the PAC-Baycsian framework [43] coupled with the approximate inference [44] based multiplicative margin [40]; the extra caution we need to handle is that our margin (Equation 10) is parameterized by B. Notice that when 3 decreases, the regularization term becomes larger, while the margin set Rx w.x..9 becomes smaller - implying low empirical risk (Equation 11). In this regard, Theorem presents an intuitive trade-off between the estimation error and the approximation error controlled by B.
5

---

Having seen the result for a general loss, we now seek to understand the best possible generalization performance in terms of the approximation loss lapproxi
Meru (X,Y) Merue (X,Y)
lapprox X, 8- m
E [0, 1].
(13)
Such questions essentially explore the realizability of the hypothesis space J Rxx which is determined by the empirical distribution Mem and the number of random realizations used to construct Fax- We will shortly how these factors may impact the generalization performance. By Theorem 1, when infinite samples are available, the empirical risk approaches to
Ex~D
max lapprox (X2Y) YEVro
1
(Y) Rg x.
(14)
The next result provides analytical relationship between the complexity of the hypothesis space and the best possible generalization performance in terms of lapprox.
Theorem 2. Let A sup,
Merse()) MMm(r) min f- (X-Y) measure the divergence between Marue and
To (X.Y)
Mem scaled by the range of the kernel function. For each e > 0, 61 > 0,62 > 0, and Mens when K is O (1 22.3 (In) Pre | + In )), with probability at least 1 - 81 over the selection of RR, there exists a desired weight w such that
(Y) S ao (āo B) (1- (1+
Pr X
lapprox (xpprox(XX (X YEYTO
max
1
21 11-22 82. (15)
Rg. 8.8
Remark 3. The above result has the implication that the best possible ratio in generalization is essentially bounded by O (ao B)) On the other hand, one easily that the target task (Equation 3) and the inference problem (Equation 8) suffer the same approximation hardness, and therefore, one would wish for a true approximation error that is better than ag; ; in this regard, the result in Theorem 2 is not very loose.
The results in this section demonstrate how the selections of K, Mem w, and may affect the gener- alization performance in theory. Since the true model Manue is unknown, the prior distribution Mem can be selected be uniform Gaussian distribution. K and B can be taken as hyperparameters determining the model complexity. In addition, since the true loss lapprox is not accessible, one can take general loss functions. Given the fact that we are concerned with set structures rather than real numbers. we employ the zero-one loss, which is adopted also for the convenience of optimization. Therefore, remains figure out how to compute the prior vector w from training samples as well as how to solve the inference problem (Equation 8), which will be discussed in the next part.
3.2 Training method
In computing the prior vector w. the main challenge caused by the task migration is that the target task on which we performance inference is different from the source task that generates training samples. Theorem suggests that, ignoring the low-order terms,
may find the prior vector
by minimizing the regularized empirical risk Lem (w, Rx. ST I) + [il Directly minimizing such a quantity would be notoriously hard because the optimization problem is bilevel: optimizing
over involves the term y w.x; which is obtained by solving another optimization problem you
depending on (Equations 10 and 11). Notably, since HD Rx,, (X,, "Rx w...) is lower bounded by 2 Rx. w (X,, MMrr replacing Rx W, with YMeseiTo would allow for us to optimize an upper bound of the empirical risk. Seeking a large-margin formulation, this amounts to solving the following mathematical program under the zero-one loss [4], 45]:
yoo
m
min
|w| 2
+
&/m
1=1
s.t. āolāo - B) H !
Rx. w (Xi, Moma.To.)) - 11 Rg. (X,Y)) E, ViE [m], V E Vo
0
(16)

---

where &, is the slack variable and C' hyperparameter [46]. However, our dataset concerns only about the source task T without informing MM....To. or its approximation. In order to see where we could feed the training samples into the training process, let us notice that the constraints in Equation 16 have an intuitive meaning: with respect to the target the task To. desired weight H W should lead to a score function Rggw w that can assign highest scores to the optimal solutions
Y MMerueTTy... Similar arguments also apply to the source task To. as the weight w implicitly estimates the true model Myrue. which is independent of the management tasks. This enables us to reformulate the optimization problem with respect to the source task To by using the following constraints:
ao O 3).H% (X,, T
Mirne To. H w (X, Ei, Vi E [m], AY E eoo (17)
where Hi (X W. TO (X,Y) is the score function corresponding to the source task To- As desired, pairs of (Xi, Y XX, are the exactly the information we have in the training data ST One remaining issue is that the acquired program (Equation 17) has an exponential number of constrains [45]. which can be reduced to linear (in sample size) if the following optimization problem can be solved for each w and X;:
max H YEVO RK (),
(18)
Provided that the above problem be addressed, the entire program be solved by several classic algorithms, such as the cutting plane algorithm [47] and the online subgradient algorithm [48]. Therefore, in completing the entire framework, it remains to solve Equations 8 and 18. For tasks of DE and DC, we delightedly have the following results.
Theorem 3. When Te, and To are selected from DE and DC, Equations 8 and 18 are both NP-hard to solve in optimal, but both can be approximated within a ratio of 1/e in polynomial time.
A concrete example of using Social-Inverse solve Problem 4 is provided in Appendix C.
4 Empirical studies
Although some theoretical properties of our framework can be justified (Sec. 3.1), it remains open whether or not the proposed method is practically effective, especially given the fact that no prior work has attempted to solve one optimization problem by using the solutions to another one. this section, we present our empirical studies.
4.1 Experimental settings
We herein present the key logic of our experimental settings and provide details in Appendix E.
The latent model Merue and samples (Appendix E.1.)). To generate a latent diffusion model Mtrue. first determine the graph structure and then fix the distributions Nr, and T (u.,)) by generating random parameters. We adopt four graphs: a Kronecker graph [49], an Erdōs-Rén Ménds-Rééíi graph [50], Higgs graph [51]. and Hep graph [52]). Given the underlying diffusion model Merues for each of DE and DC, we generate pool of query-decision pairs (X,, Y)) for training and testing, where X, is selected randomly from V and Y; is the approximate solution associated with X; (Theorem 3). As for Problem 4, there are four possible target-source pairs: DE-DE, DC-DE, DE-DC, and DC-DC.
Sovirl-Inverse (Appendix F.1.2). With K and / being hyperparameters, to set up Social-Inverse, we need to specify the empirical distribution Mem- We construct the empirical distribution by building three diffusion models M, with Mtrue- In addition, we construct an empirical distribution Ma which is totally random and not close to Mtrue anywhere. For each empirical distribution, generate pool of realizations.
(0.1, 1}. where a smaller q implics that M, is closer to
Competitors (Appendix E.1.3). Given the fact that Problem may be treated as supervised learning problem with the ignorance of task migration, we have implemented Naive Bayes (NB) [53]. graph neural networks (GNN) [54], and a deep set prediction network (DSPN) [55]. addition, we consider the High-Degree (HD) method, which is a popular heuristic believing that selecting the high-degree users as the seed nodes can decently solve DE and DC. random (Random) method also used the bascline.
7

---

Table Results on Kronecker (Kro) and Erdös-Rényi (ER), Each cell shows the mean of perfor- mance ratio with std. For Jocial-Inverse under each empirical distribution, the table shows the results with K E (15, 30, 60) and 3 = 1. The training size is 270, and the testing size is 540..
K= 15 K = 30 K 60
K 15
K 30
K = 60
Ma
0,541 (004)) 0.567 (0:100 0.584 (8.000
Mi
0.748 (0.022)
0.794 (am1)) 0,811 (0.01)
DC
Ma.5
0.767 (0078) 0.837 (0:44) 0.851 (0.004)
Mo.1
0.770 (0025)
0.850 (.01)) 0.853 (0.040)
I
DE
NB:
0.64 (0.0))
GNN: 0.51 (0:05)
DSPN: 0.46 (0.34)
HD:
0.59 (0.01)
Random: 0.15 (0.01)
Kro
Moo
0.846 (0.005) 0.913 (0:005) 0.985 (0.014)
Mi
0.796 (0.55))
0.845 (0.000 0.899 (0.000)
DE
Ma.5
0.850 (.00)) 0.937 (0:05)) 1.021 (0,44)
Mo.1 0.862 (0.013)
0.953 (..18) 1.041 (0.026)
I
DC
NB: 0.88 (001)
GNN: 0.76 (0:05)
DSPN: 0.57 (0.4)
HD: 0.89 (0.01)
Random: 0.26 (0.01)
Ma
0.541 (0.00) 0.585 (aa1s) 0.577 (0.00))
Mi
0.744 (0.005)
0.752 (0:00)) 0.754 (0.000)
DC
Ma.s
0.825 (0.05)) 0.830 (0:05) 0.830 (0005)
Mo. 0.829 (0.002)
0.833 (0:004) 0.833 (0.004)
I
DE
NB: 0.78 (o01)
GNN: 0.05 (0.02)
DSPN: 0.06 (000)
HD: 0.32 (0.01)
Random: 0.06 (0.01)
ER
Ma0
0.526 (0.20))
0.677 (0:16)
0.750 (0.100)
Mi
0.773 (0.016)
0.796 (0.010) 0.800 (0.009)
DE
Ma.5
0.879 (0.02)) 0.900 (0:002) 0.892 (0.002)
Mo. 0.886 (0.005)
0,902 (0.00)) 0.895 (0.000)
I
DC
NB: 0.04 (0.0))
GNN: 0.05 (0.02)
DSPN: 0.04 (001)
HD: 0.09 (0.01)
Random: 0.04 (0.01)
Training, festing, and evaluation (Appendix E.1.4) The testing size is 540, and the training size m is selected from [90, 270, 1350]. Given the training size and the testing size, the samples are randomly selected from the pool we generate; similarly, given K, the realizations used in Social- Inverse are also randomly selected from the pool we generate. For each method, the entire process is repeated five times, and we report the average performance ratio together with the standard deviation. The performance ratio is computed by comparing the predictions with the decisions in testing samples; larger is better.
4.2 Main observations
The main results on the Kronecker graph and the Erdós-Rényí graph are provided in Table 1. According to Table 1, it is clear that Social-Inverse performs better when K becomes larger or when the discrepancy between Mem and Merue becomes smaller (i.e., g is small), which suggests that Social-Invers. indeed works the way is supposed to. In addition, while all the methods are non-trivially better than Random, one can also observe that Docial-Inverse easily outperforms other methods by an evident margin as long as sufficient realizations are provided. We also see that learning-basee based methods do not perform well in many cases; this is not very surprising because the effectiveness of learning-bai based methods hinges on the assumption that different tasks share similar decisions for the same query, which however may not be the case especially on the Erdös-Rén graph. Furthermore, Social-Inverse appears to be more robust than other methods in terms of standard deviation. Finally, the performance of standard learning methods (e.g., NB and GNN) sensitive to graph structures; they are relatively good on the Kronecker graph but less satisfactory on the Erdös- Rendi- graph, while Social-
consistently effective on all datasets.
4.3
An in-depth investigation on task migration
Notably, the effectiveness of Social-Inverse depends not only on the training samples Sg (for tuning the weight w) but also on the expressiveness of the hypothesis space (determined by Mem and K). Therefore, with solely the results in Table 1, we are not ready to conclude that samples of DE (resp., DC) are really useful for solving DC (resp.. DE). In fact, when Mem is identical to Mtrue no samples are needed because setting w 1 can allow for us to perfectly recover the best decisions as long as K is sufficiently large. As a result, the usefulness of the samples should be assessed by examining how much they can help in delivering high-quality w. To this end, for each testing query, we report the quality of two predictions made based, respectively, on the initial weight (before optimization) and on the final weight (after optimization).
Such results for DC-DE on the Kronecker graph are provided in Figure 1. As seen from Figure 1b, the efficacy of DC samples in solving DE is statistically significant under Mo.1. which might be the first
8

---

after optimization
before optimization
19-
15.
2
0.30-
0.5-
0.0
67-
4.5.
0.8
08-
08-
47.
(a) IDC-DE, Ma.1, m 901
(b) IDC-DE, Ma.1, 2701
(c) IDC-DE, Ma.1. m 13501
1
058
134-
333
058
053
139
357-
3.50-
0:51
(d) [DC-DE, Mas, m = 90]
(e) [DC-DE, M.s. m71 270]
(1) [DC-DE, Ma. m = 1350]
Figure 1: Each subgraph shows the results of 50 testing queries on the Kronecker graph with K 30. For each query, we report the quality (i.e. performance ratio) of the predictions made based on the initial weight (before optimization) and final weight (after optimization).
piece of experimental evidence confirming that is indeed possible to solve one decision-making task by using the query-decision pairs of another one. addition, according to Figures la, 1b, and Ic, the efficacy of the samples is limited when the sample size is too small, and it does not increase too much after sufficient samples are provided. On the other hand, with Figure le, we also see that the samples of DC are not very useful when the empirical distribution (e.g.. Max) deviates too much from the true model, and in such a case, providing more samples can even cause performance degeneration (Figure If), which is an interesting observation calling for further investigations.
The full experimental study can be found in Appendix E.2, E.3 and E.4, including the results on Higgs and Hep, results with more realizations, results of DE-DE and DC-DC, results of GNN under different seeds, discussion on the impact of and a discussion of training efficiency.
5 Further discussion
We close our paper with a discussion on the limitations and future directions of the presented work, with the related works being discussed in Appendix F.
Future directions. Following the discussion on Figure 1, one immediate direction is to systemically investigate the necessary or sufficient condition in which the task migrations between DE and DC are manageable. In addition, settings in Problem 4 can be carried over to other contagion management tasks beyond DE and DC, such as effector detection [56] and diffusion-basee community detection [57]. Finally, in its most general sense, the problem of inverse decision meriiinnnmmking with task migrations can be conceptually defined over any two stochastic combinatorial optimization problems [40] sharing the same underlying model (e.g., graph distribution). For instance, considering the stochastic shortest path problem [58] and the minimum Steiner tree problem [59], with the information showing the shortest paths between some pairs of nodes, can we infer the minimum Steiner tree of a certain group of nodes with respect to the same graph distribution? Such problems are interesting and fundamental to many complex decision-making applications [60, 61].
Limitations. While our method offers promising performance in experiments, it is possible that deep architectures can be designed in a sophisticated manner so as to achieve improved results. In addition, while we believe that similar observations also hold for graphs that are not considered in our experiment, more experimental studies are required to support the universal superiority of Social-Inverse another issue, the assumption that the training set contains approximation solutions is the minimal one for the purpose of theoretical analysis, but in practice, such guarantees may never be known. Therefore, experimenting with samples of heuristic query-decision pairs needed to further justify the practical utility of our method. Finally, we have not experimented with graphs of extreme scales (e.g., over I IM nodes) due to the limit in memory. We wish to explore the above issues in future work.

---

Acknowledgments and Disclosure of Funding
We thank the reviewers for their time and insightful comments. This work supported in part by a) National Science Foundation under Award IIS-21 244255 and b) the University of Delaware.
References
[1] N. A. Christakis and J. H. Fowler, "Social contagion theory: examining dynamic social networks and human behavior," Statistics in medicine, vol. 32, no. 4, pp. 556-577,,011
[2] R. S. Burt, "Social contagion and innovation: Cohesion versus structural equivalence," American journal of Sociology, vol. 92, no. 6, pp. 1287-1335, 1987.
[3] N. O. Hodas and K. Lerman, "The simple rules of social contagion." Scientific reports, vol. 4,
no. 1, pp. 2014.
[4] I. lacopini, G. Petri, A. Barrat, and V. Latora, "Simplicial models of social contagion," " Nature communications, vol. 10, 1, pp. 1-9, 2019.
[5] A. De Bruyn and G. L. Lilien, "A multi-stage model of word-of-mouth influence through viral marketing," International journal of research in marketing, vol. 25, no. 3, pp. 151-163, 2008.
[6] M. R. Subramani and B. Rajagopalan, "Knowledge-sharins and influence in online social networks via viral marketing." Communications of the ACM, vol. 46, no. 12, pp. 300-307, 2003.
[7] G. Tong, W. Wu, L. Guo, D. Li, C. Liu, B. Liu, and D.-Z. Du, "An efficient randomized algorithm for rumor blocking in online social networks," IEEE Transactions on Nenwork Science and Engineering. vol. 7, no. 2, pp. 845-854,20 2017.
[8] R. Yan, Y. Li, W. Wu, Li, and Wang. "Rumor blocking through online link deletion on social networks," ACM Transactions on Knowledge Discovery from Data (TKDD), vol. 13,
no. 2. pp. 1-26, 2019.
[9] M. Del Vicario, Bessi, Zollo, F. Petroni, Scala, G. Caldarelli, H. Stanley, and W. Quattrociocchi, "The spreading of misinformation online," Proceedings of the National Academy of Sciences, vol. 113, no. 3, pp. 184-559,22 2016.
[10] A. Yadav, B. Wilder, E. Rice, R. Petering, J. Craddock, A. Yoshioka-Maxwell, M. Hemler, L. Onasch- M. Tambe, and D. Woo, "Bridging the gap between theory and practice in influence maximization: Raising awareness about hiv among homeless youth." in IJCAI, 2018, pp. 5399-5503,
[11] L. E. Young, J. Mayaud, S.-C. Suen, M. Tambe, and E. Rice, "Modeling the dynamism of hiv information diffusion in multiplex networks homeless youth," " Social Networks, vol. 63, pp. 112-121. 2020.
[12] M. H. Oostenbrock, M. J. van der Leij, Q. A. Meertens, C. G. Diks, and H. M. Wortelboer, "Link-based influence maximization in networks of health promotion professionals." PloS one, vol. 16, no. 8, p. e0256604, 2021.
[13] E. Rice, B. Wilder, I. Onasch- Vera, C. Hill, A. Yadav, S.-J. Lee, and M. Tambe, "A peer- led, artificial intelligence-aggmente social network intervention to prevent hiy among youth experiencing homelessness."
[14] S. Aral, "Commentary-iddntee social contagion in new product diffusion," Marketing Science, vol. 30, no. 2, pp. 217-223, 2011.
social influence: A comment on opinion leadership and
[15] S. Aral and D. Walker, "Creating social contagion through viral product design: A randomized trial of peer influence in networks," Management science, vol. 57, no. 9, pp. 1623-1639, 2011
[16] C. I. Dăniasä, V. Tomijä, D. Stuparu, and M. Stanciu, "The mechanisms of the influence of viral marketing in social media," Economics, Management Financial Markets, vol. no. 3, pp. 278-282. 2010.
[17] W. Chen, C. Wang, and Y. Wang. "Scalable influence maximization for prevalent viral market- ing in large-scale social networks," in Proceedings of the 16th ACM SIGKDD international conference Knowledge discovery and data mining, 2010, pp. 1029-1038.
10

---

[18] J. Seymour, "The impact of public health awareness campaigns on the awareness and quality of palliative care." Journal of Palliative Medicine, vol. 21, no. SI, pp. S-30, 2018.
[19] T. W. Valente and P. Pumpuang, "Identifying opinion leaders to promote behavior change." Health education & behavior, vol. 34, no. 6, pp. 881-896, 2007.
[20] C. Budak, D. Agrawal, and A. El Abbadi, "Limiting the spread of misinformation in social networks," in Proceedings of the 20th international conference on World wide web, 2011 I, pp. 665-674.
[21] M. Farajtabar, J. Yang. X. Ye, H. Xu, R. Trivedi, E. Khalil, S. Li, L. Song, and H. Zha, FFake news mitigation via point process based intervention," in International Conference on Machine Learning. PMLR, 2017, pp. 1097-1106.
[22] X. He, G. Song, W. Chen, and Q. Jiang, "Influence blocking maximization in social networks under the competitive linear threshold model," in Proceedings of the 2012 siam international conference on data mining. SIAM, 2012, pp. 463-474.
[23] J. Fagan, D. L. Wilkinson, and G. Davies, "Social contagion of violence." in Urban Seminar Series on Children's 's Health and Safety, John P. Kennedy School of Government, Harvard Univer- sity, Cambridge, MA, US; An earlier version of this paper was presented at the aforementioned seminar. Cambridge University Press, 2007.
[24] W. A. Knight and T. Narozhna, "Social contagion and the female face of terror: New trends in the culture of political violence," " Canadian Foreign Policy Journal, vol. 12, no. 1, pp. 141-166, 2005.
[25] D. Kempe, J. Kleinberg, and É. Tardos, "Maximizing the spread of influence through a social network," " in Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, 2003, pp. 137-146.
[26] W. Chen, Y. Wang, and S. Yang. "Efficient influence maximization in social networks," " in Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, 2009, pp. 199-208.
[27] A. Goyal, W. Lu, and L. V. Lakshmanan, "Celf++ optimizing the greedy algorithm for influ- ence maximization in social networks," in Proceedings of the 20th international conference companion on World wide web, 2011, I, pp. 47-48.
[28] Y. Tang. X. Xiao, and Y. Shi, "Influence maximization: Near-optimal time complexity meets practical efficiency." in Proceedings of the 2014 ACM SIGMOD international conference on Management of data, 2014, pp. 75-86.
[29] N. Du, Y. Liang, M. Balcan, and L.. Song, "Influence function learning in information diffusion networks," " in International Conference on Machine Learning. PMLR, 2014, pp. 2016-2024
[30] X. He, K. Xu, D. Kempe, and Y. Liu, "Learning influence functions from incomplete observa- tions," arXiv preprint arXiv: 161 1.02305, 2016.
[31] A. Goyal, Bonchi, and I.. Lakshmanan, "Learning influence probabilities in social net- works," in Proceedings of the third ACM international conference on Web search and data mining, 2010, pp. 241 241-250.
[32] D. Kalimeris, Y. Singer, K. Subbian, and U. Weinsberg, "Learning diffusion using hyperparam- eters," in International Conference on Machine Learning. PMLR, 2018, pp. 2420-2428..
[33] M. Gomez- Rodriguz, L.. Song, N. Du, H. Zha, and Schölkopf, "Influence estimation and maximization in continuous-time diffusion networks," ACM Transactions Information Systems (TOIS), vol. 34, no. 2. pp. 1 1-33, 2016.
[34] H. Li, M. Xu, S. S. Bhowmick, C. Sun, 7. Jiang, and J. Cui, "Disco: Influence maximization meets network embedding and deep learning," arXiv preprint arXiv: 2019.
[35] Ko, K. Lee, K. Shin, and Park, "Monstor: an inductive approach for estimating and maximizing influence over unseen networks." in 2020 JEFF/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM). IEEE, 2020, pp. 204-211.
[36] G. Tong, "Stratlearner: Learning strategy for misinformation prevention in social networks," Advances in Neural Information Processing Systems, vol. 33, 2020.
[37] N. Du, I.. Song, M. Gomez Rodriguez, and H. Zha, "Scalable influence estimation in continuous- time diffusion networks," Advances in neural information processing systems, vol. 26, 2013.
11

---

[38] G. Tong, R. Wang, and Z. Dong. "On castae influence maximization: Model, hardness and algorithmic framework," " IEEE Transactions on Network Science and Engineering, vol. no. 2, pp. 1600-1613, 2021.
[39] J. G. Oxley, Matroid theory. Oxford University Press, USA, 2006, vol. 3.
[40] G. Tong, "Usco-solver: Solving undetermined stochastic combinatorial optimization problems." Advances in Neural Information Processing Systems, vol. 34, 2021.
[41] I. Tsochantaridis, T. Joachims, T. Hofmann, Y. Altun, and Y. Singer, "Large margin methods for structured and interdependent output variables." Journal of machine learning research, vol. 9, 2005.
[42] A. Rahimi and B. Recht, "Weighted sums of random kitchen sinks: Replacing minimization with randomization in learning," Advances in neural information processing systems, vol. 21, 2008.
[43] D. McAllester, "Simplified pac-bayesian margin bounds," in Learning theory and Kernel machines. Springer, 2003, pp. 203-215,
[44] Y. Wu, M. Lan, S. Sun, Q. Zhang, and X. Huang, "A learning enror analysis for structured prediction with approximate inference," in Proceedings of the 3 International Conference on Neural Information Processing Systems, 2017, pp. 6131-6141.
[45] B. Taskar, V. Chatalbashev, D. Koller, and C. Guestrin, "Learning structured prediction models:
A large margin approach," in Proceedings of the 22nd international conference on Machine learning, 2005, pp. 896-903.
[46] A. C. Müller and S. Behnke, "Pystruct: learning structured prediction in python." " J. Mach. Learn. Res., vol. 15, no. 1, pp. 2055-2060, 2014.
[47] E. Kelley, Jr, "The cutting-plane method for solving convex programs," Journal of the society for Industrial and Applied Mathematics, vol. 8, no. 4, pp. 703-712, 1960.
[48] A. Lucchi, Y. Li, and P. Fua, "Learning for structured prediction using approximate subgradient descent with working sets," in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2013, pp. 1987-1994.
[49] J. Leskovee, D. Chakrabarti, J. Kleinberg, C. Faloutsos, and Z. Ghahramani, "Kronecker graphs: an approach to modeling networks." Journal of Machine Learning Research, vol. 11, no. 2, 2010.
[50] A. Hagberg, Swart, and D. S Chult, "Exploring network structure, dynamics, and function using networkx," " Los Alamos National Lab((LAN)), Los Alamos, NM (United States), Tech. Rep., 2008
[51] M. De Domenico, A. Lima, P. Mougel, and M. Musolesi, "The anatomy of scientific rumor," Scientific reports, vol. 3, no. 1, pp. 1-9, 2013.
[52] J. Leskovec, J. Kleinberg, and C. Faloutsos, "Graph evolution: Densification and shrinking diameters." ACM transactions on Knowledge Discovery frrcveeyyfrom Data (TKDD), vol. 1, no. 1, pp. 2-es, 2007.
[53] I. Rish et al., "An empirical study of the naive bayes classifier." in IJCAI 2001 workshop on empirical methods in artificial intelligence, vol. 3, no. 22, 2001, pp. 41-46.
[54] T. N. Kipf and M. Welling, "Semi-supervised classification with graph convolutional networks," arXiv preprini arXiv: 1609002907, 2016.
[55] Y. Zhang, J. Hare, and A. Prugel-Bennete "Deep set prediction networks," in NeurlPS, 2019,
pp. 3207-3217.
[56] T. Lappas, E. Terzi, D. Gunopulos, and H. Mannila, "Finding effectors in social networks," in Proceedings the 16th ACM SIGKDD international conference on Knowledge discovery and data mining, 2010, pp. 1059-1068.
[57] M. Ramezani, A. Khodadadi, and H. R. Rabice, "Community detection using diffuusion informa- tion," ACM Transactions Knowledge Discovery from Data (TKDD), vol. 12, no. 2, pp. 1-22, 2018.
[58] D. Bertsekas and J. Tsitsiklis, "An analysis of stochastic shortest path problems," Mathe- matics of Operations Research, vol. 16, no. 3. pp. 580-595, 1991.
12

---

[59] A. Gupta and M. Pál, "Stochastic steiner trees without root," in International Colloquium on Automata, Languages, and Programming. Springer, 2005, pp. 1051-1063.
[60] R. Ramanathan, "Stochastic decision making using multiplicative ahp." " European Journal of Operational Research, vol. 97, no. 3, pp. 543-549, 1997.
[61] E. Celik, M. Gul, M. Yucesan, and S. Mete, "Stochastic multi-criteria dociision-makngg an overview to methods and applications," Beni-Suef University Journal of Basic and Applied Sciences, vol. 8, no. 1, pp. 1-11, 2019.
[62] S. Fujishige, Submodular functioonn and optimization. Elsevier, 2005.
[63] G. Calinescu, C. Chekuri, M. Pal, and J. Vondrák, "Maximizing a monotone submodular function subject to matroid constraint," SIAM Journal on Computing, vol. 40, no. pp.
1740-1766, 2011.
[64] G. L.. Nemhauser, L. A. Wolsey, and M. L.. Fisher, "An analysis of approximations for maxi- mizing submodular set functions Mathematical programming, vol. 14, no. 1, pp. 265-294, 1978.
[65] C. Seshadhri, A. Pinar, and T. G. Kolda, "An in-depth study of stochastic kronecker graphs," in 2011 IEEE 11th International Conference on Data Mining. IEEE, 2011, pp. 587-596.
[66] E. Bodine-Baron, B. Hassibi, and A. Wierman, "Distance-dependent kronecker graphs for modeling social networks," " IEEE Journal of Selected Topics in Signal Processing, vol. 4, no. 4, pp. 718-731, 2010.
[67] C. Seshadhri, T. G. Kolda, and A. Pinar, "Community structure and scale-free collections of erdös-rényí graphs," Physical Review E, vol. 85, no. 5, p. 056109, 2012.
[68] T. Hong and Q. Liu, "Seeds selection for spreading in weighted cascade model," Physica A: Statistical Mechanics and its Applications, vol. 526, p. 120943, 2019.
[69] T. Joachims, T. Finley, and C.-N. J. Yu, "Cutting-plane training of structural svms," Machine learning, vol. 77,
pp. 27-59, 2009.
[70] Q. E. Dawkins, T. Li, and H. Xu, "Diffusion source identification on networks with statistical confidence," in International Conference on Machine Learning. PMLR, 2021, pp. 2500-2509,
[71] W. Dong, W. Zhang, and C. W. Tan, "Rooting out the rumor culprit from suspects." in 2013 IEEE International Symposium on Information Theory. IEEE, 2013, pp. 2671-2675
[72] D. Shah and T. Zaman, "Rumors in network: Who's the culprit?" IEEE Transactions on information theory, vol. 57, no. 8. pp. 5163-5181, 2011.
[73] P.-D. Yu, C. W. Tan, and H.-L. Fu, "Rumor source detection in finite graphs with boundary effects by ppessage-passingg algorithms," in IEEE/ACM International Conference Advances in Social Networks Analysis and Mining. Springer, 2018, pp. 175-192.
[74] C. Borgs, M. Brautbar, J. Chayes, and B. Lucier, "Maximizing social influence in nearly optimal time." in Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms. SIAM, 2014, pp. 946 957..
[75] X. Fang, P. J. Hu, Z. Li, and W. Tsai, "Predicting adoption probabilities in social networks." Information Systems Research, vol. 24, no. 1, pp. 128-145, 2013.
[76] K. Saito, M. Kimura, K. Ohara, and H. Motoda, "Selecting information diffusion models over social networks for behavioral analysis." in Joint European Conference on Machine Learning and Knowledge Discovery in Databases. Springer. 2010, pp. 180-195.
[77] F. Bonchi, "Influence propagation in social networks: A data mining perspective." " IEEE Intell. Informatics Bull., vol. 12, no. 1, pp. 8-16, 2011.
[78] H. Wang, H. Xie, L. Qiu, Y. R. Yang, Y. Zhang, and A. Greenberg, "Cope: Traffic engineering in dynamic networks," " in Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications, 2006, pp. 99-110.
[79] F. Fang, T. H. Nguyen, R. Pickles, W. Y. Lam, G. R. Clements, B. An, A. Singh, M. Tambe, and Lemieux, "Deploying paws: Field optimization of the protection assistant for wildlife security." in eighty- IAAI conference, 2016.
13

---

[80] A. Mukhopadhyay and Y. Vorobeychik, "Prioritized allocation of emergency responders based on a continuous-time time incident prediction model," in International Conference on Autonomous A gents and MultiAgent Systems, 2017.
[81] Y. Xue, I. Davies, D. Fink, C. Wood, and C. P. Gomes, "Avicaching: A two stage game for bias reduction in citizen science," in Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems, 2016, pp. 776-785.
[82] A. Beygelzimer and J. Langford, "The offset tree for learning with partial labels," in Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, 2009, pp. 129-138.
[83] B. Ford, T. Nguyen, M. Tambe, N. Sintov, and Delle Fave, "Beware the soothsayer: From at- tack prediction accuracy to predictive reliability in security games," in International Conference on Decision and Game Theory for Security. Springer, 2015. pp. 35-56.
[84] P. L.. Donti, B. Amos, and 7. Kolter, "Task-based end-to-end model learning in stochastic optimization." arXiv preprint arXiv: 1 700.00459, 2017.
[85] B. Wilder, B. Dilkina, and M. Tambe, "Melding the data-decision pipeline: secision-focuse learning for combinatorial optimization." in Proceedings of the AAAI Conference Artificial Intelligence, vol. 33, no. 01, 2019, pp. 1658-1665.
[86] D. Bertsimas and N. Kallus, "From predictive prescriptive analytics," Management Science, vol. 66, no. 3, pp. 1044-1044, 2020.
[87] Y. Bengio, "Using a financial training criterion rather than a prediction criterion," " International journal of neural systems, vol. 8, 04, pp. 433 443, 1997.
[88] J. Roland, Y. De Smet, and J. R. Figueira, "Inverse multi-objective combinatorial optimization," Discrete applied mathematics, vol. 161, no. 16-17, pp. 2764 2771, 2013.
[89] Zhang and Z. Ma, "Solution structure of some inverse combinatorial optimization problems." Journal of Combinatorial Optimization, vol. 3, no. 1, pp. 127-139, 1999.
[90] C. Chan, R. Mahmood, and I. Y. Zhu, "Inverse optimization: Theory and applications," arXiv preprint arXiv:2109. 200.09009903900 2021.
[91] Y. Tan, D. Terekhov, and A. Delong, "Learning linear programs from optimal decisions," Advances Neural Information Processing Systems, vol. 33, pp. 738-19749) 2020.
[92] 7. Shahmoradi and T. Lee, "Quantile inverse optimization: Improving stability in inverse linear programming." Operations Research, 2021.
[93] Ahmadi, F. Ganjkhanloo, and K. Ghobadi, "Inverse learning: A data-driven framework to infer optimizations models," arXiv preprint wwXiv:22111030333 2020.
[94] C. Dong and B. Zeng, "Wasserstein distributionally robust inverse multiobjective optimization." " arXiv preprint arXiv:2009. 14550, 2020.
[95] C. Dong, Y. Chen, and B. Zeng, "Generalized inverse optimization through online learning," Advances in Neural Information Processing Systems, vol. 31, 2018.
Checklist
The checklist follows the references. Please read the checklist guidelines carefully for information on how to answer these questions. For each question, change the default [TODO] to [Yes], [No], ; or [N/A]. You are strongly encouraged include justification your answer, either by referencing the appropriate section of your paper or providing a brief inline description. For example:
Did you include the license the code and datasets? [Yes] See Section ??.
Did you include the license the code and datasets? [No] The code and the data proprietary.
Did you include the license to the code and datasets? [N/A]
Please do not modify the questions and only use the provided macros for your answers. Note that the Checklist section does not count towards the page limit. In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/answers below.
14

---

1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Sec. 5
(c) Did you discuss any potential negative societal impacts of your work? [No] This work focuses on learning and algorthimic foundations of social contagion management, without being tied to specific applications
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] They can be found in the appendix.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed reproduce the main ex- perimental results (either in the supplemental material or as a URL)? [Yes] They are provided in the supplemental material. Due the 100M limitation, we only provide partial data at the submission time and will release the complete dataset (> 6GB) after the review period.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] The details are provided in Appendix E.
(c) Did you report
bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes] Yes, we report standard deviations.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Appendix F.2.
4. If you using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either in the supplemental material or as a URL? [Yes]
(d) Did you discuss whether and how consent was obtained from people whose data you'l 're using/curating? [Yes] We use public dataset and source code following their licenses. (e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [No] Our dataset is purely numerical and does not have any personally identifiable information offensive content.
5. If you used crowdsoureing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "zE_Cw3hc8NP", "reviewer": "Reviewer_iB7C", "summary": "The paper considers a semi-opaque-box influence network and the cumulative impacts from information dissemination at a few seed nodes. The network is semi-opaque in the sense that we know the general connectivity of the nodes, but not the actual realization of the influence, which is sampled from an unknown distribution with support by the observed connections. To make up for the observability gap, the paper suggests to use previous examples of information diffusion, collected in the form of which targets to reach (queries) and which seeds would maximize the coverage of the targets after diffusion (decisions). It then proposes to use random samples of possible realizations to solve a max-margin (SVM) optimization problem to find out the most likely linear combination of the realizations. The paper finally uses the learned weighted combination of realizations to decide for optimal solutions in new information diffusion tasks. Theoretical and empirical studies were included.", "questions": "* Line 172. Why do you introduce a Gaussian distribution after you learned the optimal combinations of realizations? Doesn't this introduce pure noise?\n* Line 185. Related, the generalization error considers the mean of the sample you use for inference, yet in the algorithm description, you use only one point in the sample for inference. Does this generalization error cover the full risk?\n* Line 191. I do not understand the use of beta. Also, why do you analyze a binary loss when your objective contains an optimization sub-problem?\n* Table 1. Can you elaborate on Naive Bayes? It seems to be the second-best in the considered baselines, just below High Degree.", "limitations": "Overall, I can get some inspirations from the proposed method and empirical studies, but some key aspects in the algorithm were left unexplained, namely eta and the extra step of Gaussian sampling. The theory presentation does not meet the expectation of the NeurIPS community, perhaps because too many new concepts were introduced without good explanations.\n\nThough the paper is purely methodological, I flagged it for ethics reviews due to some word choices, such as information containment, which may lead to a limitation of people's access to opportunities. The authors should be also be advised on the creation of an ethics discussion section.", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n* Quality: The paper is nicely presented with thorough empirical studies.\n* Originality: The paper solves an essentially \"graph-kernel\" problem using inspirations from random kitchen sink. This sounds like a reasonable idea.\n\nWeaknesses:\n* Theory: The presentation is not entirely clear and I have some questions about some unexplained terms in the key algorithm and theoretical analysis.\n* Significance: We have to accept the assumption that the training data is presented as query-decision pairs, instead of the more commonly used decision-impact pairs, that is, the actual coverage caused by the seed nodes.\n* Ethics: The paper is missing ethics discussions on a potentially sensitive topic.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["Inappropriate Potential Applications & Impact  (e.g., human rights concerns)"]}, "extra_text": {}}, {"review_id": "unOKGH_oOhl", "reviewer": "Reviewer_egd8", "summary": "The authors consider the problem of task migration for decision making tasks in social networks for the purpose of managing contagion events. The authors begin by formally defining a social network (and associated social contagions) as a directed graph of users, where a set of seed users initiate a social contagion, with contagions spreading through edges at a rate defined by a distribution on each edge.\n\nThe authors then define four different contagion management problems, the last of which is the task migration problem. In this setting, we have two contagion management tasks (source and target) on the same social network and have samples from the source task. The goal is to minimize a loss with respect to the target task using those source task samples.\n\nThe authors propose an algorithm for this task migration problem which they dub social-inverse. They bound the generalization error of social inverse and compare their algorithm in simulated experiments to supervised learning algorithms and a heuristic that selects high-degree users as seed nodes.", "questions": "How closely do the assumptions of this work mirror real-world practices in social contagion management?\nFor example, the introduction states that \"For example, a network manager may need to work on a rumor blocking task, but they only have historical data collected in solving viral marketing tasks.\" are there any existing cases where such a network manager would employ any methods that are remotely similar to social-inverse instead of just proceeding based on intuition/industry best practices for their interventions?", "limitations": "Limitations were well addressed by the author.", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 1, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper addresses an important problem (task migration) in a very general setting that can be applied to many different instances (contagion management in social networks). Unfortunately I am unable to leave an educated review since this paper seems to be targeted at a highly technical research sub-community which I have had no prior exposure to.\n\nMy primary concern is that this paper might not be accessible to most of Neurips' audience and thus might be better received at more theoretical conferences like STOC or COLT. However, I do not feel as though this should be a disqualifying factor for acceptance, especially if there is a large enough community at Neurips that would find this paper useful.\n\nGoing through the theoretical results, the assumptions seem reasonable and I can't see any glaring red flags in their resulting theorems.\n\nI do not feel like I have enough context to critically interpret the significance of the improvements in the experimental results. \n\nOverall this paper seems sound to me, but I have concerns about the accessibility of the paper. Hence I recommend a borderline accept with very low confidence. I think the authors could significantly improve the paper if they spent some time providing more intuition in the first few sections and also added some concrete examples to aid the interpretation of their definitions.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "padG3XRFMr", "reviewer": "Reviewer_8vwD", "summary": "This paper studies an inverse decision-making problem for task migrations on contagion management. Specifically, it investigates how prior decision-making on diffusion containment can be migrated to diffusion enhancement; and vice versa. It provides a theoretical analysis of how different diffusion management tasks can be correlated such that samples from one task can be useful for another task. It performs empirical analysis on four graphs, comparing with several benchmarks (used for supervised learning) to evaluate the performance. ", "questions": "\n(1) In remark 1, the paper mentioned that the model generalizes popular diffusion models, including the linear threshold model, which requires a percentage or number of neighbors to adopt before the users adopt. However, in lines 79—80 on P2, the paper mentions that the node will only be activated by \"first in-attempting neighbors\" or activated by the cascade with the smallest index. These two scenarios both conflict with the linear threshold model. Why can't a node be activated by two or more cascades? In reality, a user only observes his/her neighbor's decisions, rather than which cascade resulted in the neighbors' decision. \n\n(2) L88–89, why is the subgraph weighted? From the description in Line 71—72, I think the subgraph is attributed instead of weighted? \n\n(3) There are two decision-making problems in the paper, one is the decision-making of users, and the other is the decision-making of the central planner (I believe referred to as agent by the paper). Given that both are important concepts yet are entirely different, I suggest distinguishing the two concepts to avoid confusing the readers, e.g., user decision-marking vs. planner decision-making). \n\n(4) \\beta is an important parameter that controls the trade-off between estimation and approximation errors. How can it be tuned? It seems that the experiment section directly uses beta = 1. If it cannot be systematically tuned, it might also help to show the robustness of the method w.r.t. different beta \n\n(5) Regarding the experiment, I think it will help add a benchmark, which assumes either a linear threshold model or an independent cascade. The parameters in these models can be learned based on different realizations. That is, since there is rich research on the diffusion model in sociology, it seems sensible to use them directly in such a migration task. \n\n(6) I wonder how realistic in practice do we assume the platform has information about all DC but no DE, or all DE but no DC? It seems more reasonable to observe a mix of both. Can you provide some insights on how the method performs (especially compared with the benchmarks) if this is the case? \n\n(7) Any insights on why the benchmarks perform this badly on ER? \n\n(8) Minor: There is a typo on line 84, \"For sample\" —> \"For example\"\n", "limitations": "NA", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \nI find the idea of task migration on contagion management novel and important (although I have some concerns about the detailed setup (see weakness 1). The paper provides rigorous theoretical analysis and shows empirical effectiveness on four datasets. \n\nWeaknesses:\n(1) I think the setup that the platform only observes one type of task (either diffusion containment or enhancement) does not seem realistic. It is more likely that the platform will observe a combination of both. I think this is a crucial question: How realistic is the task migration problem proposed in this paper? \n\n(2)  Given that many models have been proposed in the diffusion literature (also cited by the paper), designing benchmarks w.r.t. based on these models is important to show the effectiveness of the methods, rather than other ML methods that do not know the underlying diffusion process.  ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "7KI2qgB2ds", "reviewer": "Reviewer_HDGT", "summary": "The paper presents a framework for task migration in the context of contagion management in social networks, in which, a target decision-making task is solved using the historical data collected from another task. The authors define a generic problem formulation that covers the tasks of diffusion enhancement as well as diffusion containment, and further derive a reformulated optimization problem that can be coupled with several classic algorithms to provide an approximated solution in a polynomial time.", "questions": "- How the concepts of \"task migration\" relate to \"transfer learning\"?\n\n- It is not completely clear what the authors mean by learning-based methods. Isn't your approach a learning framework?\n\n", "limitations": "No discussion is provided in that regard. However, given the nature of the work, which is related to the social network analysis, a discussion about societal impact of the approach would be interesting. ", "rating": 5, "confidence": 3, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n+ Originality: The paper develops a novel framework for task migration between two classes of social management tasks with a generic problem definition and (re-)formulation of the objectives.\n\n+ Quality: The authors theoretically analyze the generalization ability of their approach across tasks and show that the generalization error is bounded. Subsequently, they identify potential conditions on the design choices that can affect the generalizability, and thus, some aspects/parameters are chosen accordingly. In addition, they conduct considerable empirical study evaluating the performance of their method in various setups and compared to several baselines.\n\nWeaknesses:\n\n- Significance: The proposed approach is not well located within the literature, and the discussion of the related work seems to be limited. Additionally, in terms of approaches, it is mentioned that the ideas are closely related to structure prediction methods (refs. 40-42), but the  connection to those work is not clarified; what are the similarities/differences with those methods? in what sense the framework is novel compared to them? Moreover, the generalization of the approach to other domains and problems and the applicability of the work on real network data is not clear. As a result, the outcomes only impact a narrow scope which leads to limited significance.\n\n- Clarity: The paper is well written, but it is a bit hard to follow. The writeup could be improved in terms of structure and choice of content, Some details about the background information and algorithmic characteristic can be expanded.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept