Learnability of Competitive Threshold Models

1 Introduction

Social contagion phenomena, such as the propagation of behavior patterns or the adoption of new technologies, have attracted huge research interests in various fields (e.g., sociology, psychology, epidemiology, and network science [Cozzo et al., 2013; Goldstone and Janssen, 2005; Camacho et al., 2020]). Formal methods for modeling social contagion are crucial to many applications, for example, the recommendation and advertising in viral marketing [Kempe et al., 2003; Tong et al., 2018] and misinformation detection [Budak et al., 2011; Tong, 2020]. Given the operational diffusion models, there is a fundamental question regarding the learnability of the models: to which extent can we learn such models from data?. In this paper, we study the classic threshold models in which the core hypothesis is that the total influence from active friends determines the contagion per a threshold. We seek to derive its PAC learnability and sample complexity by which efficient learning algorithms are possible.

Motivation andRelatedWorks. Learning contagionmodels from data has been a central topic in social computing. One research branch focuses on estimating the total influence resulting from an initial status [Li et al., 2017;

Gomez-Rodriguez et al., 2016; Tang et al., 2009]; in contrast, our learning task attempts to predict the diffusion status for each node. For node status prediction, it has been proved that deep learning methods are promising when rich features are available (e.g., [Qiu et al., 2018; Leung et al., 2019]), but their generalization performance in theory is often unclear. Recent works have demonstrated the sample complexity of influence learning for single-cascade models [He et al., 2016; Du et al., 2014], where certain technical conditions are required and the approach therein is different from ours in a substantial way. Our research is inspired by the recent works that show the possibility of simulating single-cascade contagion models through neural networks [Narasimhan et al., 2015; Adiga et al., 2019]. Departing from the common surrogate modeling methods where the learned mappings are less transparent, the pursued idea seeks to design neural networks with their layer structures mimicking real networks. In this paper, we take a step towards the case of general threshold models, without limiting the number of cascades. Comparing to the single-cascade case where threshold layers are sufficient, multi-cascade diffusion requires more sophisticated designs in order to properly propagate influence summation between layers without losing the information of cascade identity.

Contribution. Our work can be summarized as follows.

• Model Design. For a finite-precision system, we present elementary designs showing that the general threshold model can be simulated explicitly by neural networks with piecewise polynomial activation functions.
• Theoretical Analysis. Based on our hypothesis design, we prove that the general threshold model is PAC learnable, and design efficient empirical risk minimization schemes with a provable sample complexity.
• Empirical Studies. We experimentally examine the proposed methods over synthetic and real datasets. The results suggest that methods based on explicit simulation outperform off-the-shelf learning methods by an evidence margin. They also verify that our methods work in the way it supposed to.

The proofs, full experimental results, and source code are provided in the supplementary material 1 .

1 https://github.com/cdslabamotong/LTInfLearning

2 Preliminaries

2.1 Competitive Linear ThresholdModel

We follow the standard competitive linear threshold (CLT) model [Borodin et al., 2010], which has been widely adopted in the formal study of social contagions [He et al., 2012; Tzoumas et al., 2012; Bozorgi et al., 2017]. A social network is represented as a directed graph G = (V,E), where V = {v1, ..., vN} is the set of nodes and E is the set of edges, with N = |V | and M = |E| being the numbers of nodes and edges, respectively. For each node v ∈ V , we denote by N(v) ⊆ V the set of its in-neighbors.

We consider the scenario where there are S ∈ Z+ information cascades, each of which starts to spread from their seed set ψs 0 ⊆ V for s ∈ [S]. Associated with each node vi and each cascade s, there is a threshold θs i ∈ [0, 1]; associated with each edge (vi, vj) ∈ E and each cascade s, there is a weight ws i,j ∈ [0, 1]. Without loss of generality, we assume that the seed sets are disjoint and the weights are normalized such that ∑vj∈N(vi) ws (j,i) ≤ 1 for each node vi ∈ V and cascade s. The nodes are initially inactive and can be s-active if activated by cascade s. In particular, the diffusion process unfolds step by step as follows:

• Step 0: For each cascade s ∈ [S], nodes in ψs 0 become s-active.
• Step t > 0: Let ψs t-1 ⊆ V be the set of s-active nodes after t - 1 step. There are two phases in step t.
• Phase 1: For an inactive node vi ∈ V , let ζ s i be the summation of the weights from its s-active inneighbors:

The node vi is activated by cascade s if and only if ζ s i ≥ θs i . After phase 1, it is possible that a node can be activated by more than one cascades.

• Phase 2: For each node vi, it will be finally activated by the cascade s∗ with the largest weight summation:

For tie-breaking, cascades with small indices are preferred.

Clearly, there are at most n diffusion steps, and without loss of generality, we may assume that there are always n diffusion steps. An illustration is given in Figure 1. The following notations are useful for formal discussions.

Definition 1. We use a binary matrix I0 ∈ {0, 1}N×S to denote the initial status, where I0,i,s = 1 if and only if node vi is in the seed set ψs 0 of cascade s. For a time step t > 0, the diffusion status is denoted by a binary tensor It ∈ {0, 1}N×S×2 , where, for a cascade s, It,i,s,p = 1 if and only if node vi is s-active after phase p ∈ {1, 2} in time step t.

We are interested in the learnability of the influence function of CLT models.

Definition 2. Given a CLT model, the influence function F : {0, 1}N×S ↦→ {0, 1}N×S maps from the initial status I0 to the final status IN,:,:,2.

2.2 Learning Settings

Assuming that the social graph G is unknown to us, we seek to learn the influence function using a collection D of K ∈ Z+ pairs of initial status and corresponding diffusion statuses:

where Ik1:N,:,:,1:2 denotes the diffusion status after each phase in each diffusion step:

We use the zero-one loss ℓ0-1 to measure the difference between the prediction ˆIN,:,:,2 and the ground truth IN,:,:,2, which is defined as

For a distribution D over the input I0 and a CLT model generating the training data D, we wish to leverage D to learn a mapping ˆ F : {0, 1}N×S ↦→ {0, 1}N×S such that the generalization loss can be minimized:

3 Learnability Analysis

In this section, we present a PAC learnability analysis for the influence function. The following assumptions will be made throughout the analysis.

Assumption 1. Following the conventions regarding finite precision system [Holi and Hwang, 1993; Weiss et al., 2018; Dembo et al., 1989], we assume that the diffusion model is a decimal system of a finite precision: for the involved parameters (i.e., ws i,j and θs i ), number of their decimal places is upper bounded by a constant Q ∈ Z+.

Assumption 2. The cascade number S = 2Z is a power of 2 for some constant Z ∈ Z+.

The overall idea is to design a realizable hypothesis with a finite VC dimension by which the PAC learnability can be established. In order to obtain a realizable hypothesis space, we seek to explicitly simulate the diffusion function through neural networks. While the universal approximation theory ensures that such neural networks exist, we wish for elementary designs of a polynomial size so as to admit efficient learning algorithms. To this end, we first demonstrate how to simulate the one-step diffusion under the CLT model, which can be used repeatedly to simulate the entire diffusion.

3.1 Realizable Hypothesis Space

For the one-step diffusion, its simulation is done through two groups of layers that are used in turn to simulate phase 1 and phase 2. As illustrated in Figure 2, the simulation starts by receiving the diffusion status H1 ∈ {0, 1}N·S after the last step, where for i ∈ [N] and s ∈ [S], H1(i-1)·S+s = 1 if and only if node vi is s-active. After 2Z + 4 layers of transformations, it ends by outputting a vector H2Z+6 ∈ {0, 1}N·S , which corresponds exactly to the diffusion status after one diffusion step under the CLT model. The layer transformations all follow the canonical form:

with Wl being the weight matrix and σl being a collection of activation functions over the elements of WlHl . In the rest of this subsection, we will present our designs of the weight matrices and the activation functions that can fulfill the goal of simulation.

Phase 1

The single-cascade activation can be simulated by

where for each i, j ∈ [N] and s1, s2 ∈ [S], we have

and for each i ∈ [N] and s ∈ [S], we have

For each i ∈ [N] and s ∈ [S], the resulting H2(i-1)·S+s is equal to the influence summation of cascade s at node vi if vi is activated by cascade s, and otherwise zero.

Phase 2

In simulating phase 2, the general goal is to figure out among the candidate cascades which one wins the competition. Intuitively, this can be implemented through a hierarchy of pairwise comparisons. One technical challenge is that comparison made directly by linear functions tells only the difference between the summations, while we need to keep the summation for future comparisons; we observe that this problem can be solved by using two consecutive layers of piecewise linear functions. A more serious problem is that simply passing the largest influence summation to subsequent layers incurs the loss of the information about the cascade identity (i.e., index), making it impossible to identify the node status - which is required as the input to simulating the next diffusion step. We propose to address such a challenge by appending the cascade identity to the weight summation as the lowest bits. The total shifted bits are determined by the system precision (Assumption 1). Doing so does not affect the comparison result while allowing us to retrieve the cascade identity by the scale and modulo operations. In particular, two groups of transformations are employed to achieve the pairwise comparison and status recovery.

Pairwise Comparison. With the input H2 from phase 1, we encode the cascade identity through

where for each i ∈ [N · S] and j ∈ [N · S], we have

and for each i ∈ [N] and s ∈ [S], we have

The design of W2 ensures that sufficient bits are available at the low side, and the activation function σ2 then writes the cascade identity into the empty bits (Comment 1 in Figure 2).

Using the information in H3 , for a node vi ∈ V , the largest influence summation can be determined by the sub-array

through pairwise comparisons. For the comparison between two cascades s1 and s2 at node vi (s1 < s2), as illustrated in Comment 2 in Figure 2, the difference

is first fed into a ReLu function of which the result is then added by H3(i-1)·S+s2 . We can verify that this returns exactly

Therefore, two layers are used to eliminate a half of the candidate cascades, thereby resulting in 2Z layers in total. The output of this part is H2Z+3 ∈ RN in which we have

for each i ∈ [N].

Notably, the lowest Q bits in H2Z+3 stores the cascade index, which can be recovered by

where W2Z+3 is the identity matrix and we have

which is shown in Comment 3 in Figure 2.

Finally, the cascade indices in H2Z+4 are converted to binary indicators through two layers. The first layer transforms H2Z+4 into a binary vector in {0, 1}N·S by

where for each i, j ∈ [N] and s ∈ [S], we have

and

This ensures that in each group

H2Z+5 (i-1)·S+s is 1 if and only if s is no larger than the index of the cascade that activates vi. Finally, H2Z+5 is transformed into the form that matches exactly the diffusion status after ones-step diffusion, which can be achieved through

where for each i, j ∈ [N] and s1, s2 ∈ [S], we have

and

The last two layers are illustrated in Comment 4 in Figure 2.

Lemma 1. One-step diffusion in a CLT model can be simulated by a feed-forward neural network composed of O(Z) layers, with O(S(N +M)) adjustable weights and O(N · S) piecewise linear computation units each of which with O(2Q) pieces.

Definition 3 (Hypothesis Space). Repeating such one-step simulations for N steps, the CLT model can be explicitly simulated. Taking the weights ws i,j and the thresholds θs i as parameters, we denote by F the hypothesis space formed by such neural networks.

One important property is that the entire neural network is composed of piecewise polynomial activation functions, which will be used in deriving its sample complexity.

3.2 Efficient ERM

Theorem 1 suggests that for any sample set D, there always exists a perfect hypothesis in F. In what follows, we show that such an empirical risk minimization solution can be efficiently computed. It is sufficient to find the parameters that can ensure the output of each activation function coincides with the diffusion result. Since the activation functions are all pairwise linear functions, the searching process can be done by linear programming with a polynomial number of constraints. Formally, we have the following statement.

Lemma 2. For a CLT model and each sample set D, there exists a hypothesis in F with zero training error, and it can be computed in polynomial time in terms of N,M, S, and |D|.

3.3 Generalization Performance

To establish the learnability of class F, we first analyze the VC dimension of the binary-valued function class Fi,j that is obtained by restricting the output of to the diffusion status of node vi regarding cascade s in the last layer of the neural network. That is,

Lemma 3. For each i ∈ [N] and s ∈ [S], the VC dimension of class Fi,s is VC(Fi,s) = ˜O(S · Q · (N +M)).

proof sketch. The proof is obtained by first showing that the functions in Fi,s have a manageable VC dimension when restricted to the one-step simulation. Given the fact that repeating such one-step simulations does not increase the model capacity in terms of shattering points, the VC dimension of the entire class Fi,s can be derived immediately.

Remark 1. The above suggests that the VC dimension is linear in the network size, the number of cascades, and the coding size of the numerical values. When there is only one cascade, pairwise comparisons and status recovery are no longer needed, and therefore, the size of the neural network does not depend on the system precision (i.e., Q). This gives a VC dimension of ˜O(N +M), which recovers the results in [Narasimhan et al., 2015]. Interestingly, similar results apply to the case of S = 2 but not to larger S. We provide more details in Appendix B.

With Lemmas 2 and 3, the generalization bound of the ERM scheme for predicting the status of one node regarding one cascade can be derived through the class result of statistical learning theory, and the sample complexity of F follows from the union bound over all the nodes and cascades.

Theorem 1. The influence function class F is PAC learnable and the sample complexity for achieving a generalization error no larger than ϵ with probability at least 1 - δ is O( VC(Fi,s) log(1/ϵ)+log(NS/δ) ϵ ).

4 Experiment

In this section, we present empirical studies for experimentally examining the practical utility of the proposed method.

4.1 Experimental Settings

Graphs. We adopt two classic graph structures (Kronecker [Leskovec et al., 2010] and power-law) and one real graph Higgs, which was built after monitoring the spreading process of the messages posted between 1st and 7th July 2012 regarding the discovery of a new particle with the features of the elusive Higgs boson [De Domenico et al., 2013]. The graph statistics are provided in the supplementary material.

Diffusion Model. We simulate the case with the number of cascades S selected from {2, 3, 4}. The thresholds θs i are generated uniformly at random from [0, 1]. We consider two settings for weight generation, following the weighted cascade setting [Borodin et al., 2010], the weights on Kronecker and Power-law are set as ws i,j = 1 |N(vj)|+s/7 for each pair (vi, vj) ∈ E and each s ∈ [S]. On Twitter, the weights are sampled uniformly at random from [0, 1] and then normalized such that ∑vi∈N(vj) ws i,j = 1 for each vj ∈ V . The parameters are set to be numbers with three decimal places.

Samples. To generate one sample of (I10 , I11:N,:,:,2 ), the total number of seed nodes | ⋃Ss=1 ψs 0 | is generated from [0.1N, 0.5N] uniformly at random, and then a subset of | ⋃Ss=1 ψs 0 | nodes are randomly selected from V . For each selected node, it is assigned to one cascade uniformly at random. Given the initial status, the ground truth is generated following the diffusion model. For each graph, we generate a pool of 2,000 samples among which the average diffusion step is four and the average number of total active nodes is 254.

Methods. Given the samples, the parameters of our model are computed by the linear programming solver Cplex [Cplex, 2009]. Alternatively, one can use off-the-shelf supervised learning methods to train a one-step diffusion model on each node, and make predictions by repeatedly simulating the onestep diffusion process. Given the nature of binary classification, we implement three methods, logistic regression (LR), support vector machine (SVM), and multilayer perceptron (MLP), using scikit-learn [Pedregosa et al., 2011]. For such baselines, the number of repetitions for testing is selected from {1, 2, 3, 4, 5}. We also implement the random method that makes a random prediction.

Training and Testing. The size of the training set is selected from {50, 100, 500} and the testing size is 500. In each run, the training and testing samples are randomly selected from the sample pool, and we evaluate the performance of each method in terms of F1 score, precision, and accuracy. The entire process is repeated for five times, and we report the average performance together with the standard deviation.

4.2 Results

Major Observations

The main results are given in Table 1. We see from the table that all the prediction results are statistically robust per the standard deviation. The main observation is that our method outperforms other methods in a significant manner in terms of any of the measurements. MLP is better than LR and SVM, but still produces low-quality predictions on the power-law graph. In addition, for classic learning methods, the Kronecker graph is relatively easy to handle, while the predictions on the power-law graph are consistently less satisfactory, which suggests that they are sensitive to graph structures.

Minor Observations

Hidden Layers Meeting Diffusion Status. From the standpoint of surrogate modeling, it may be interesting to notice that the hidden features of the proposed neural networks meet exactly the node status during the diffusion process, which somehow makes our model explainable and more transparent.

While the original goal is to predict the final diffusion status, we seek to examine to what extent the hidden features are semantically meaningful. To this end, we compare the hidden features with the node status in the corresponding steps, and the results are given in Figure 3. For our method, we in general observe that the one-step prediction is very accurate, while the match becomes less perfect with more steps. Therefore, given the fact that most of the samples contain no more than six diffusion steps, our method is overall effective.

Imbalance Class Distribution. Imbalance class distribution is an inherent issue in predicting the node status in that the majority of the nodes tend to be inactive, and therefore high accuracy does not necessarily imply good prediction performance. According to the results in Table 1, the standard methods often simply predict all the nodes as inactive, which gives a decent accuracy but low F1 score and precision. In such a sense, our method is more robust and effective.

Impact of Testing Iterations. For LR and MLP, one can see that repeating the single-step prediction does not help increase prediction quality. One plausible reason is that the single-step prediction is not sufficiently good and its error is amplified by the repetitions. For MLP, the results suggest that the prediction almost converges after the first single-step prediction.

Impact of the Number of Training Samples. Tables 5 and 6 in Appendix C presents the full results on Kronecker and power-law using different training sizes. We see that the performance increases very slightly when more samples are provided, suggesting that training size is not the main bottleneck.

Impact of the Number of Cascades. As our work focuses on the CLT model, we are interested in the performance under different numbers of cascades, and the results of this part can be found in Tables 3 and 4 in Appendix C. Our method exhibits a stable performance, while for other methods, the task becomes more challenging in the presence of more cascades. The above tables also present the running time of each method, which confirms that our proposed linear programming can be easily handled by standard software packages.

5 Further Discussions

In this paper, we demonstrate the possibility of design methods for simulating social contagions by using neural networks that directly mimic the diffusion pattern. We present a learnability study for the competitive threshold models as well as an efficient learning algorithm with a provable sample complexity. While our method outperforms classic supervised learning methods, it does not rule out the possibility that advanced representation techniques can achieve better learning performance with sufficient samples, which is one direction of our future work. In addition, there exist other classic operational models, such as the independent cascade model and voter model, and it remains unknown how to explicitly simulate them through neural networks, or more generally, graphical models. Given the encouraging experimental results we acquire in this paper, we believe it is worth investigating more models beyond the single-cascade case.