Learnability of Competitive Threshold Models

We follow the standard competitive linear threshold (CLT) model ?, which has been widely adopted in the formal study of social contagions ?. A social network is represented as a directed graph $G=(V,E)$, where $V=\{v_{1},...,v_{N}\}$ 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\in V$, we denote by $N(v)\subseteq V$ the set of its in-neighbors.

We consider the scenario where there are $S\in\mathbb{Z}^{+}$ information cascades, each of which starts to spread from their seed set $\psi_{0}^{s}\subseteq V$ for $s\in[S]$. Associated with each node $v_{i}$ and each cascade $s$, there is a threshold $\theta_{i}^{s}\in[0,1]$; associated with each edge $(v_{i},v_{j})\in E$ and each cascade $s$, there is a weight $w_{i,j}^{s}\in[0,1]$. Without loss of generality, we assume that the seed sets are disjoint and the weights are normalized such that $\sum_{v_{j}\in N(v_{i})}w_{(j,i)}^{s}\leq 1$ for each node $v_{i}\in 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 $\mathbf{0}$: For each cascade $s\in[S]$, nodes in $\psi_{0}^{s}$ become $s$-active.

• •

  Step $\mathbf{t>0}$: Let $\psi_{t-1}^{s}\subseteq 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 $v_{i}\in V$, let $\zeta^{s}_{i}$ be the summation of the weights from its $s$-active in-neighbors:

    $\displaystyle\zeta^{s}_{i}=\sum_{v_{j}\in N(v_{i})\bigcap\psi^{s}_{t-1}}w_{(j,i)}^{s}.$

    (1)

    The node $v_{i}$ is activated by cascade $s$ if and only if $\zeta_{i}^{s}\geq\theta_{i}^{s}$. After phase 1, it is possible that a node can be activated by more than one cascades.

  • –

    Phase 2: For each node $v_{i}$, it will be finally activated by the cascade $s^{*}$ with the largest weight summation:

    $\displaystyle s^{*}=\operatorname*{arg\,max}_{s:\zeta^{i}_{s}\geq\theta^{i}_{s}}\zeta_{i}^{s}.$

    (2)

    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.

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

Assuming that the social graph $G$ is unknown to us, we seek to learn the influence function using a collection $D$ of $K\in\mathbb{Z}^{+}$ pairs of initial status and resulted the statuses:

where $\mathbf{I}_{1:N,:,:,1:2}^{k}$ denotes the diffusion status after each phase in each diffusion step:

We use the zero-one loss $\operatorname{\mathcal{\ell}_{0-1}}$ to measure the difference between the prediction $\hat{\mathbf{I}}_{N,:,:,2}$ and the ground truth $\mathbf{I}_{N,:,:,2}$, which is defined as

For a distribution $\mathcal{D}$ over the input $\mathbf{I}_{0}$ and a CLT model generating the training data $D$, we wish to leverage $D$ to learn a mapping $\hat{F}:\{0,1\}^{N\times S}\mapsto\{0,1\}^{N\times S}$ such that the generalization loss can be minimized:

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 explicitly 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 used repeatedly to simulate an arbitrary number of diffusion steps.

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 illustrate is in Figure 2, the simulation starts by receiving the diffusion status $\mathbf{H}^{1}\in\{0,1\}^{N\cdot S}$ after the last step, where for $i\in[N]$ and $s\in[S]$, $\mathbf{H}^{1}_{(i-1)\cdot S+s}=1$ if and only if node $v_{i}$ is $s$-active. After $2Z+4$ layers of transformations, it ends by outputting a vector $\mathbf{H}^{2Z+5}\in\{0,1\}^{N\cdot 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 $\mathbf{W}^{l}$ being the weight matrix and $\sigma^{l}$ being a collection of activation functions over the elements of $\mathbf{W}^{l}\mathbf{H}^{l}$. 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.

Taking the weights $w_{i,j}^{s}$ and the thresholds $\theta_{i}^{s}$ as parameters, the neural networks designed in the last subsection form a hypothesis space denoted by $\operatorname{\mathcal{F}}$. Theorem 1 suggests that for any sample set $D$, there always exists a perfect hypothesis in $\operatorname{\mathcal{F}}$. In what follows, we show that such an empirical risk minimization solution can be efficiently computed. It is sufficient to find the parameters than 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 a linear programming with polynomial number of constraints. Formally, we have the following statement.

The learnability of class $\operatorname{\mathcal{F}}$ is enabled by the analysis of its VC dimension.

Together with Lemma 2, the following result summarizes our theoretical findings.

(Pleas organize the appendix so that we have proofs only to Theorem 1, lemma 1, lemma 2 corollary 1.)

In this section we list our main results in three table. Additional experiments results on power-law graph are in ?.