betaFeedback

WorksComputer Science

Influence Estimation and Maximization via Neural Mean-Field Dynamics

Abstract

We propose a novel learning framework using neural mean-field (NMF) dynamics for inference and estimation problems on heterogeneous diffusion networks. Our new framework leverages the Mori-Zwanzig formalism to obtain an exact evolution equation of the individual node infection probabilities, which renders a delay differential equation with memory integral approximated by learnable time convolution operators. Directly using information diffusion cascade data, our framework can simultaneously learn the structure of the diffusion network and the evolution of node infection probabilities. Connections between parameter learning and optimal control are also established, leading to a rigorous and implementable algorithm for training NMF. Moreover, we show that the projected gradient descent method can be employed to solve the challenging influence maximization problem, where the gradient is computed extremely fast by integrating NMF forward in time just once in each iteration. Extensive empirical studies show that our approach is versatile and robust to variations of the underlying diffusion network models, and significantly outperform existing approaches in accuracy and efficiency on both synthetic and real-world data.

Introduction

Continuous-time information diffusion on heterogeneous networks is a prevalent phenomenon [2, 44, 48]. News spreading on social media [13, 15, 56], viral marketing [26, 27, 58], computer malware propagation, and epidemics of contagious diseases [1, 42, 48, 53] are all examples of diffusion on networks, among many others. For instance, a piece of information (such as a tweet) can be retweeted by users (nodes) with followee-follower relationships (edge) on the Twitter network. We call a user infected if she retweets, and her followers see her retweet and can also become infected if they retweet in turn, and so on. Such information diffusion mimics the epidemic spread where an infectious virus can spread to individuals (human, animal, or plant) and then to many others upon their close contact. The study of heterogeneous diffusion networks only emerged in the past decade and is considered very challenging, mainly because of the extremely large scale of modern networks, the heterogeneous inter-dependencies between the nodes, and the randomness exhibited in cascade data.

In the remainder of this section, we provide the mathematical formulations of the inference, influence estimation, and influence maximization problems on an arbitrary diffusion network. Throughout this paper, we use boldfaced lower (upper) letter to denote vector (matrix) or vector-valued (matrix-valued) function, and (⋅)k(\cdot)_k (or (⋅)ij(\cdot)_{ij}) for its kkth component (or (i,j)(i,j)-th entry). All vectors are column vectors unless otherwise

*Department of Mathematics and Statistics, Georgia State University, Atlanta, Georgia 30303, USA. ([email protected]).

†School of Data Science, Shenzhen Research Institute of Big Data, The Chinese University of Hong Kong, Shenzhen, Guangdong, China, 518172. ([email protected]).

‡Department of Mathematics and Statistics, Georgia State University, Atlanta, Georgia 30303, USA. ([email protected]). noted. We follow the Matlab syntax and use [x;y][\boldsymbol{x};\boldsymbol{y}] to denote the vector that stacks x\boldsymbol{x} and y\boldsymbol{y} vertically, and x⋅y\boldsymbol{x}\cdot\boldsymbol{y} or xTy\boldsymbol{x}^{\mathsf{T}}\boldsymbol{y} for the inner product. Time is denoted by tt in either continuous (t∈[0,T]t \in[0,T]) or discrete case (t=0,1,…,Tt = 0,1,\ldots,T) for some time horizon T∈R+T \in\mathbb{R}_{+} (N\mathbb{N} in discrete case). Derivative  ˙\dot{\ } is with respect to tt, and gradient ∇x\nabla_{\boldsymbol{x}} is with respect to x\boldsymbol{x}. Probability is denoted by Pr⁡(⋅)\Pr(\cdot), and expectation with respect to XX (or its distribution function pXp_X) is denoted by EX[⋅]\mathbb{E}_X[\cdot]. The nn-vectors 1n,0n∈Rn\boldsymbol{1}_n,\boldsymbol{0}_n \in\mathbb{R}^n stand for the vectors of ones and zeros respectively, and we often omit the subscript nn when their dimensions are obvious from the context.

Figure 1. Example of a sample cascade on a diffusion network. The cascade was originated from the source set S={1}S = \{1\} and gradually propagates to other nodes through their directed edge connections. The time line below the network shows the wall-clock time tit_i that each node ii was infected during the cascade with t1=0t_1 = 0. The orange edges indicate whom each node got infection from, and tij:=tj−tit_{ij} := t_j - t_i is the time that node ii took to infect node jj.

Diffusion network models

Consider a diffusion network model, which consists of a network (directed graph) G=(V,E)\mathcal{G} = (\mathcal{V},\mathcal{E}) with node set V=[n]:={1,…,n}\mathcal{V} = [n] := \{1,\ldots,n\} and edge set E⊂V×V\mathcal{E} \subset\mathcal{V} \times\mathcal{V}, and a diffusion model that describes the distribution p(t;αij)p(t;\alpha_{ij}) of the time tt that an infected node ii takes to infect her healthy neighbor j∈{j′:(i,j′)∈E}j \in\{j' : (i,j') \in\mathcal{E}\}. Here αij\alpha_{ij} is the infection rate of ii on jj which vary across different edges. That is, tijt_{ij} is a random variable following the density function p(t;αij)p(t;\alpha_{ij}) for each (i,j)∈E(i,j) \in\mathcal{E}. We assume that the infection is progressive, i.e., a node will not be infected again nor recover once infected, since generalization to the case with recovery is straightforward. Then, given a source set SS (a subset of V\mathcal{V}) of nodes that are infected at time 0, they will infect their healthy neighbors with random infection times described above; and the infected neighbors will then infect their healthy neighbors, and so on. As such, the infection initiated by SS at time 0 propagates to other nodes of the network. We call one course of such propagation a cascade. For simplicity, it is common to assume that the infection times across different edges are independent, known as the continuous-time independent cascade (CIC) model [13, 19, 21].

In Figure 1, we illustrate one such cascade originated from a singleton source set S={1}S = \{1\}, which spreads to other nodes during the propagation. The orange edges indicate whom a node got infection from, for example, node 4 succeeded in infecting node 6 before node 1 did. The time line below the network indicates the wall-clock time tit_i of each node ii got infected in this cascade. In particular, t1=0t_1 = 0. Moreover, tij:=tj−tit_{ij} := t_j - t_i is the time node ii took to infect node jj. Note that this is one sample cascade of S={1}S = \{1\}, and a different sample cascade of the same source SS may yield different infected nodes and infection times due to the randomness of tijt_{ij}.

The standard diffusion model with exponential distribution p(t;α)=αe−αtp(t;\alpha) = \alpha e^{-\alpha t} is mostly widely used in the literature. That is, tij∼p(t;αij)t_{ij} \sim p(t;\alpha_{ij}) for each (i,j)∈E(i,j) \in\mathcal{E}. Note that the parameter αij>0\alpha_{ij} > 0 in the exponential distribution indicates the strength of impact node ii has on jj—the expectation of tij∼p(t;αij)t_{ij} \sim p(t;\alpha_{ij}) is 1/αij1/\alpha_{ij}—and the larger αij\alpha_{ij} is, the sooner node jj will be infected by ii on expectation. We focus on the diffusion model with exponential distribution in this work. Other distributions, such as Rayleigh and general Weibull distributions, are also experimented in our empirical studies in this work.

Cascade data

Observation data D\mathcal{D} of a diffusion network are often in the form of sample cascades D:={Ck=(Sk,τk)∈V×R+n:k∈[K]}\mathcal{D} := \{C_k = (S_k, \tau_k) \in\mathcal{V} \times\mathbb{R}_{+}^{n} : k \in[K]\}, where the kkth cascade CkC_k records its source set Sk⊂VS_k \subset\mathcal{V} and the time (τk)i≥0(\tau_k)_i \ge0 which indicates when node ii was infected (if ii was not infected during CkC_k then (τk)i=∞(\tau_k)_i = \infty). See Figure 1 for one of such sample cascades, where we have τ={t1,…,t8,∞,…,∞}\tau= \{t_1, \ldots, t_8, \infty, \ldots, \infty\} if no other nodes were infected in this cascade. Cascade data are collected from historical events for training purposes.

Network inference and influence estimation

Suppose G=(V,E)\mathcal{G} = (\mathcal{V}, \mathcal{E}) is a diffusion network with transmission matrix A\mathbf{A}, where (A)ji=αij(\mathbf{A})_{ji} = \alpha_{ij} is the parameter of p(t;αij)p(t; \alpha_{ij}) for edge (i,j)(i,j). Then the goal of infection probability estimation (influence estimation, or influence prediction, for short) is to compute

x(t;χS)=[x1(t;χS),…,xn(t;χS)]T∈[0,1]n(1)\mathbf{x}(t; \chi_S) = [x_1(t; \chi_S), \ldots, x_n(t; \chi_S)]^{\mathsf{T}} \in[0,1]^n \tag*{(1)}

for all time t>0t > 0 and any given source set S⊂VS \subset\mathcal{V}. In (1), xi(t;χS)x_i(t; \chi_S) is the probability of node ii being infected at time tt given the source set SS, and χS∈{0,1}n\chi_S \in\{0,1\}^n indicates the identities of SS, i.e., (χS)i=1(\chi_S)_i = 1 if i∈Si \in S and 0 otherwise. Note that we use χS\chi_S and SS interchangeably hereafter. The probability x(t;χS)\mathbf{x}(t; \chi_S) can also be used to compute the influence function σ(t;χS):=1nTx(t;χS)\sigma(t; \chi_S) := \mathbf{1}_n^{\mathsf{T}}\mathbf{x}(t; \chi_S), the expected number of infected nodes at time tt. Our method can be readily applied to influence functions defined with uneven weights (rather than 1’s on all nodes) if the severity of infection varies at different nodes, but we focus on the even weight case for the sake of conciseness.

Most influence estimation problems do not assume knowledge of A\mathbf{A}. Instead, only cascade data D\mathcal{D} are available. In this case, network inference is often needed. Network inference refers to the problem of uncovering E\mathcal{E} and A\mathbf{A} from cascade data D\mathcal{D}, and is of independent research interests in the literature. Now influence estimation can be tackled by a two-stage approach, where a network inference is performed first to learn the network structure E\mathcal{E} and the diffusion model parameters A\mathbf{A}, and then an influence estimation is used to compute the influence of the source set SS. However, both influence estimation and network inference problems are very challenging, and the approximation errors and biases in the two stages will certainly accumulate. Alternatively, one can use a one-stage approach to directly estimate x(t;χS)\mathbf{x}(t; \chi_S) of any SS from the cascade data D\mathcal{D}, which is more versatile and less prone to diffusion model misspecification. Our method is a such kind of one-stage method. Additionally, it allows knowledge of E\mathcal{E} and/or A\mathbf{A}, if available, to be integrated for further performance improvement.

Influence maximization

Given a budget size n0∈{1,…,n−1}n_0 \in\{1,\ldots,n-1\}, the goal of influence maximization is to find the source set SS which generates the maximal influence σ(t;χS)\sigma(t; \chi_S) at a prescribed time tt among all source sets of size n0n_0. Influence maximization can be formulated as follows:

max⁡χS σ(t;χS),s.t.χS∈{0,1}n,1nTχS=n0.(2)\max_{\chi_S}\ \sigma(t; \chi_S), \quad\text{s.t.}\quad\chi_S \in\{0,1\}^n,\quad\mathbf{1}_n^{\mathsf{T}}\chi_S = n_0. \tag*{(2)}

There are two main ingredients of an influence maximization method for solving (2): an influence estimation subroutine that evaluates the influence σ(t;χS)\sigma(t; \chi_S) for any given source set SS, and an (approximate) combinatorial optimization solver to find the optimal set SS of (2) that repeatedly calls the subroutine. The combinatorial optimization problem is NP-hard and is often approximately solved by greedy algorithms with guaranteed sub-optimality when σ(t;χS)\sigma(t; \chi_S) is submodular in χS\chi_S. In this work, we propose a variational method based on the continuous relaxation of (2), and show that it can tackle this challenging problem very efficiently using our solution framework.

Summary of contribution

In this paper, we develop a comprehensive framework, called neural mean-field (NMF) dynamics, for simultaneous influence estimation and network inference from cascade data on a diffusion network. We substantially extend our preliminary work [25] which first proposed NMF for influence estimation and network influence with a discrete-time setting. The novelty and contribution of the present work in contrast to existing ones, including [25], are summarized as follows:

  1. We extend the NMF dynamics developed in [25] to the continuous-time setting which is more suitable for real-world applications of diffusion networks. We show that the continuous-time NMF dynamics can be naturally incorporated into the likelihood function of the corresponding point process, which in turn plays the role of loss function, whereas [25] directly uses cross-entropy of the observed discrete-time data as the loss function.

  1. We prove rigorously the connections between parameter learning in continuous-time NMF and optimal control, where the NMF parameter serves as the time invariant control. The derivations lead to a fast algorithm based on numerical ordinary differential equation (ODE) solver that is easy to implement. Unlike the standard deep residual network training used in [25], we prove rigorously that the gradients in continuous-time NMF training can be efficiently computed by solving the ODE defined by NMF forward in time and an augmented co-state ODE backward in time.

  1. Based on our continuous-time NMF framework, we develop a highly efficient algorithm for the very challenging influence maximization problem. In each iteration, our algorithm only requires solving one augmented ODE based on NMF dynamics forward in time and one quadratic program, both of which can be computed very efficiently.

All the theoretical and algorithm developments mentioned above are supported by extensive empirical studies in this work. The numerical results show that our approach is robust to the variation of the unknown underlying diffusion models, and it also significantly outperforms existing approaches on both synthetic and real-world diffusion networks.

Paper outline

The remainder of this paper is organized as follows. In Section 2, we develop the proposed neural mean-field dynamics for network inference and influence estimation on diffusion networks, as well as an optimal control formulation for parameter training. We show that our new solution framework leads to an efficient influence maximization algorithm in Section 3. We demonstrate the performance of the proposed method on influence estimation and maximization on a variety of synthetic and real-world networks in Section 4. A comprehensive review of related work in the literature is provided in Section 5. Section 6 concludes the paper.

Neural Mean-Field Dynamics

Modeling diffusion by stochastic jump processes

We begin with the jump process formulation of network diffusion. Given a source set XS\mathcal{X}_{\mathcal{S}}, let Xi(t;XS)X_i(t;\mathcal{X}_{\mathcal{S}}) denote the infection status of the node ii at time tt. Namely, Xi(t)=1X_i(t)=1 if node ii is infected by time tt, and 00 otherwise. Then {Xi(t):i∈[n]}\{X_i(t):i\in[n]\} are a set of nn coupled jump processes, such that Xi(t;XS)X_i(t;\mathcal{X}_{\mathcal{S}}) jumps from 00 to 11 when the node ii is infected at tt. Let λi∗(t)\lambda_i^*(t) be the conditional intensity of Xi(t;XS)X_i(t;\mathcal{X}_{\mathcal{S}}) given history H(t)={Xi(s;XS):s≤t, i∈[n]}\mathcal{H}(t)=\{X_i(s;\mathcal{X}_{\mathcal{S}}):s\leq t,\ i\in[n]\}, i.e.,

λi∗(t):=lim⁡τ→0+E[Xi(t+τ;XS)−Xi(t;XS)∣H(t)]τ.(3)\lambda_i^*(t):=\lim_{\tau\to0^+}\frac{\mathbb{E}[X_i(t+\tau;\mathcal{X}_{\mathcal{S}})-X_i(t;\mathcal{X}_{\mathcal{S}})\mid\mathcal{H}(t)]}{\tau}. \tag*{(3)}

In influence estimation, our goal is to compute the probability x(t;XS)=[xi(t;XS)]\mathbf{x}(t;\mathcal{X}_{\mathcal{S}})=[x_i(t;\mathcal{X}_{\mathcal{S}})] in (1), which is the expectation of Xi(t;XS)X_i(t;\mathcal{X}_{\mathcal{S}}) conditioning on H(t)\mathcal{H}(t):

xi(t;XS)=EH(t)[Xi(t;XS)∣H(t)].(4)x_i(t;\mathcal{X}_{\mathcal{S}})=\mathbb{E}_{\mathcal{H}(t)}[X_i(t;\mathcal{X}_{\mathcal{S}})\mid\mathcal{H}(t)]. \tag*{(4)}

To this end, we adopt the following notations (for notation simplicity we temporarily drop χS\chi_S in this subsection as the source set SS is arbitrary but fixed):

xI(t)=EH(t)[∏i∈IXi(t;χS)|H(t)],yI(t)=∏i∈Ixi(t),eI(t)=xI(t)−yI(t)(5)x_I(t)=\mathbb{E}_{\mathcal{H}(t)}\left[\prod_{i\in I}X_i(t;\chi_S)\middle|\mathcal{H}(t)\right],\quad y_I(t)=\prod_{i\in I}x_i(t),\quad e_I(t)=x_I(t)-y_I(t) \tag*{(5)}

for all I⊂[n]I\subset[n] and ∣I∣≥2|I|\ge2. Then we can derive the evolution of z:=[x;e]z:=[x;e]. Here x(t)∈[0,1]nx(t)\in[0,1]^n is the resolved variable whose value is of interests and samples can be observed in cascade data D\mathcal{D}, and e(t)=[⋯ ;eI(t);⋯ ]∈R2n−n−1e(t)=[\cdots;e_I(t);\cdots]\in\mathbb{R}^{2^n-n-1} is the unresolved variable. The evolution of zz is given by the following theorem, and the proof is provided in Section A.1.

Theorem 1. The evolution of z(t)=[x(t);e(t)]z(t)=[x(t);e(t)] follows the nonlinear differential equation:

z′=fˉ(z),where fˉ(z)=fˉ(x,e)=[f(x;A)−(A∘E)1;⋯ ;fI(x,e);⋯ ],(6)z'=\bar{f}(z),\qquad\text{where }\bar{f}(z)=\bar{f}(x,e)=\left[f(x;A)-(A\circ E)\mathbf{1};\cdots;f_I(x,e);\cdots\right], \tag*{(6)}

with initial value z0=[χS;0]z_0=[\chi_S;0], E=[eij]∈Rn×nE=[e_{ij}]\in\mathbb{R}^{n\times n}, and

f(x;A)=Ax−diag⁡(x)Ax,(7)f(x;A)=Ax-\operatorname{diag}(x)Ax, \tag*{(7)}
fI(x,e)=∑i∈I∑j∉Iαji(yI−yI∪{j}+eI−eI∪{j})−∑i∈IyI∖{i}∑j≠iαji(xj−yij−eij).(8)f_I(x,e)=\sum_{i\in I}\sum_{j\notin I}\alpha_{ji}(y_I-y_{I\cup\{j\}}+e_I-e_{I\cup\{j\}})-\sum_{i\in I}y_{I\setminus\{i\}}\sum_{j\ne i}\alpha_{ji}(x_j-y_{ij}-e_{ij}). \tag*{(8)}

We remark that the dimension of zz is 2n−12^n-1 which grows exponentially fast in nn and hence renders the computation infeasible in practice. To overcome this issue, we employ the Mori-Zwanzig formalism [6] to derive a reduced-order model of xx that has dimensionality nn only, as shown in the next subsection.

Mori-Zwanzig memory closure

We employ the Mori-Zwanzig (MZ) formalism [6] that allows to introduce a generalized Langevin equation (GLE) of the xx part of the dynamics. The GLE of xx is derived from the original equation (6) describing the evolution of z=[x;e]z=[x;e], while maintaining the effect of the unresolved part ee. This is particularly useful in our case, as we only need xx for infection probability and influence estimation.

Define the Liouville operator L\mathcal{L} such that L[g](z):=fˉ(z)⋅∇zg(z)\mathcal{L}[g](z):=\bar{f}(z)\cdot\nabla_zg(z) for any real-valued function gg of zz. Let etLe^{t\mathcal{L}} be the Koopman operator associated with L\mathcal{L} such that etLg(z(0))=g(z(s))e^{t\mathcal{L}}g(z(0))=g(z(s)) where z(t)z(t) solves (6). Then L\mathcal{L} is known to satisfy the semi-group property for all gg, i.e., etLg(z)=g(etLz)e^{t\mathcal{L}}g(z)=g(e^{t\mathcal{L}}z). Now consider the projection operator P\mathcal{P} as the truncation such that (Pg)(z)=(Pg)(x,e)=g(x,0)(\mathcal{P}g)(z)=(\mathcal{P}g)(x,e)=g(x,0) for any z=(x,e)z=(x,e), and its orthogonal complement as Q=I−P\mathcal{Q}=I-\mathcal{P} where II is the identity operator. The following theorem describes the exact evolution of x(t)x(t), and the proof is given in Section A.2.

Theorem 2. The evolution of xx specified in (6) can also be described by the following GLE:

x′=f(x;A)+∫0tk(t−s,x(s)) ds,(9)x'=f(x;A)+\int_0^t k(t-s,x(s))\,\mathrm{d}s, \tag*{(9)}

where ff is given in (7), and k(t,x):=PLetQLQLxk(t,x):=\mathcal{P}\mathcal{L}e^{t\mathcal{Q}\mathcal{L}}\mathcal{Q}\mathcal{L}x.

Note that (9) is not an approximation—it is an exact representation of the xx part of the original problem (6). The equation (9) can be interpreted as a mean-field equation, where the two terms on the right hand side are called the streaming term (corresponding to the mean-field dynamics) and memory term, respectively. The mean-field dynamics provide the main drift of the evolution, and the memory term in a convolution form is for vital adjustment. This inspires us to approximate the memory term as a time convolution on xx, which naturally yields a delay differential equation reduced a continuous-time neural network, as shown in the next subsection.

Memory approximation and delay differential equation

To compute the evolution (9) of xx, we consider an approximation of the Mori-Zwanzig memory term by a neural network ϵ\epsilon with time convolution of xx as follows,

∫0tk(t−s,x(s)) ds≈ϵ(x(t),h(t);η)whereh(t)=∫0tK(t−s;w)x(s) ds.(10)\int_0^t k(t-s,x(s))\,\mathrm{d}s\approx\epsilon(x(t),h(t);\eta)\quad\text{where}\quad h(t)=\int_0^t K(t-s;w)x(s)\,\mathrm{d}s. \tag*{(10)}

In (10), K(⋅;w)\mathbf{K}(\cdot;\mathbf{w}) is a convolutional operator with parameter w\mathbf{w}, and ε(x,h;η)\boldsymbol{\varepsilon}(\mathbf{x},h;\boldsymbol{\eta}) is a deep neural network with (x,h)(\mathbf{x},h) as input and η\boldsymbol{\eta} as parameter. Both w\mathbf{w} and η\boldsymbol{\eta} are to be trained by the cascade data D\mathcal{D}. Hence, (9) reduces to the delay differential equation which involves a time integral h(t)h(t) of past x\mathbf{x}:

x′=f~(x,h;θ):=f(x;A)+ε(x,h;η).(11)\mathbf{x}'=\widetilde{f}(\mathbf{x},h;\boldsymbol{\theta}):=f(\mathbf{x};\mathbf{A})+\boldsymbol{\varepsilon}(\mathbf{x},h;\boldsymbol{\eta}). \tag*{(11)}

The initial condition of (11) with source set S\mathcal{S} is given by

x(0)=χS,h(0)=0,andx(t)=h(t)=0,∀t<0.(12)\mathbf{x}(0)=\chi_{\mathcal{S}},\quad h(0)=0,\quad\text{and}\quad\mathbf{x}(t)=h(t)=0,\quad\forall t<0. \tag*{(12)}

We call the system (11) with initial (12) the neural mean-field (NMF) dynamics.

The delay differential equation (11) is equivalent to a coupled system of (x,h)(\mathbf{x},h) which is shown in the following theorem, whose proof is provided in Section A.3.

Proposition 2.1. The delay differential equation (11) is equivalent to the following coupled system of (x,h)(\mathbf{x},h):

x′(t)=f~(x(t),h(t);A,η)=f(x(t);A)+ε(x(t),h(t);η)(13)\mathbf{x}'(t)=\widetilde{f}(\mathbf{x}(t),h(t);\mathbf{A},\boldsymbol{\eta})=f(\mathbf{x}(t);\mathbf{A})+\boldsymbol{\varepsilon}(\mathbf{x}(t),h(t);\boldsymbol{\eta}) \tag*{(13)}
h′(t)=∫0tK(t−s;w)f~(x(s),h(s);A,η) ds(14)h'(t)=\int_{0}^{t}\mathbf{K}(t-s;\mathbf{w})\widetilde{f}(\mathbf{x}(s),h(s);\mathbf{A},\boldsymbol{\eta})\,\mathrm{d}s \tag*{(14)}

with initial condition (12). In particular, if K(t;w)=∑l=1LBle−Clt\mathbf{K}(t;\mathbf{w})=\sum_{l=1}^{L}\mathbf{B}_{l}e^{-\mathbf{C}_{l}t} for some L∈N∗with∗L\in\mathbb{N} *with*\mathbf{w}={(\mathbf{B}_{l},\mathbf{C}_{l})_{l}:\mathbf{B}_{l}\mathbf{C}_{l}=\mathbf{C}_{l}\mathbf{B}_{l},\ \forall l\in[L]}$, then (13) can be solved by a non-delay system of (x,h)(\mathbf{x},h) with (13a) and h′=∑l=1L(Blx−Clh)h'=\sum_{l=1}^{L}(\mathbf{B}_{l}\mathbf{x}-\mathbf{C}_{l}h).

In the remainder of this paper, we only consider the linear kernel K(t;w)=Be−Ct\mathbf{K}(t;\mathbf{w})=\mathbf{B}e^{-\mathbf{C}t} where B\mathbf{B} and C\mathbf{C} commute for simplicity. As shown in Proposition 2.1, NMF (11) reduces to a non-deday ODE system of (x,h)(\mathbf{x},h) with (13a) and h′=Bx−Chh'=\mathbf{B}\mathbf{x}-\mathbf{C}h. Solving such a system for the optimal parameter θ=(A,w,η)\boldsymbol{\theta}=(\mathbf{A},\mathbf{w},\boldsymbol{\eta}) has been cast as the so-called neural ODE (NODE) in [5]. In the following subsection, we establish a direction connection between mathematical optimal control and NODE, and provide a rigorous proof that NODE exactly evaluates the gradient of the target payoff function (likelihood function in our case) during optimization from the optimal control point of view. Compared to [5], our proof is based on calculus of variation which is more mathematically rigorous. Moreover, we show how to incorporate the running payoff (or loss) function at scattered observation times through a rigorous derivation, as needed in continuous-time NMF training.

Note that, once the optimal θ\boldsymbol{\theta} is obtained, we can extract A\mathbf{A} for network inference. Moreover, we can compute x(t)\mathbf{x}(t) for all tt using (11) with any given source set S\mathcal{S}, which solves the influence estimation problem. Therefore, the network inference and influence estimation problems can be tackled simultaneously by the parameter training of NMF.

Parameter training and optimal control

To obtain explicit form of NMF (11) for influence estimation and network inference, we need to know the network parameters θ=(A,η,w)\boldsymbol{\theta}=(\mathbf{A},\boldsymbol{\eta},\mathbf{w}). Let [0,T][0,T] be the time horizon of the cascade data D={Ck=(Sk,τk):k∈[K]}\mathcal{D}=\{\mathcal{C}_{k}=(\mathcal{S}_{k},\tau_{k}):k\in[K]\}, i.e., recorded up to time TT. Given any particular C=(S,τ)∈D\mathcal{C}=(\mathcal{S},\tau)\in\mathcal{D} where τ={ti∈[0,T]∪{∞}:i∈[n]}\tau=\{t_{i}\in[0,T]\cup\{\infty\}:i\in[n]\}, it suffices to derive the negative log-likelihood function of the infection probabilities x\mathbf{x} given (11) with parameter θ\boldsymbol{\theta} for this cascade C\mathcal{C}. The total negative log-likelihood function is thus the sum of such function over all the KK cascades in D\mathcal{D}.

Recall from Section 2.1 that X(t)\mathbf{X}(t) is the jump stochastic process describing the infection state of the nodes and x(t)\mathbf{x}(t) is the infection probabilities. Therefore, x′(t)\mathbf{x}'(t) is essentially the (non-conditional) intensity of X(t)\mathbf{X}(t). In other words, X(t)\mathbf{X}(t) is identical to a non-homogeneous Poisson process with intensity function x′(t)\mathbf{x}'(t) for tt almost everywhere. Due to the relation between the intensity function and the likelihood function of a point process [23], the negative log-likelihood function of x′(t)\mathbf{x}'(t) given the cascade C=(S,τ)\mathcal{C}=(\mathcal{S},\tau) can be easily obtained, and it is also the “loss function” ℓ\ell we need to minimize:

ℓ(x;C)=∑i=1n(−log⁡xi′(ti)+xi(T))=∫0Tr(x(t),θ) dt+1Tx(T),(15)\ell(\mathbf{x};\mathcal{C})=\sum_{i=1}^{n}\left(-\log x_i'(t_i)+x_i(T)\right)=\int_{0}^{T}\mathbf{r}(\mathbf{x}(t),\boldsymbol{\theta})\,\mathrm{d}t+\mathbf{1}^{\mathsf{T}}\mathbf{x}(T), \tag*{(15)}

where the running loss function is defined by

r(x(t),θ)=∑i=1n−δ(t−ti)log⁡xi′(t)=∑i=1n−δ(t−ti)log⁡(f~(x,h;θ))i.(16)r(x(t),\theta)=\sum_{i=1}^{n}-\delta(t-t_i)\log x_i'(t)=\sum_{i=1}^{n}-\delta(t-t_i)\log(\tilde{f}(x,h;\theta))_i. \tag*{(16)}

and δ(⋅)\delta(\cdot) is the Dirac delta function. The running loss takes into account the changes of x(t)x(t) at intermediate times during [0,T][0,T].

We can further add regularization or incorporate prior information to (15). In particular, if E\mathcal{E} is given, we know that AA must be supported on E\mathcal{E}, which serves as the constraint of AA. If we know the network has low density (sparse edges), then we can enforce a sparsity regularization such as ∥A∥1\lVert A\rVert_1 (the ℓ1\ell_1 norm of the vectorized A∈Rn2A\in\mathbb{R}^{n^2}). In general, AA can be interpreted as the convolution to be learned from a graph convolution network (GCN) [29, 59]. The support and magnitude of AA implies the network structure and strength of interaction between pairs of nodes, respectively. We will provide more details of our choice of regularization and its parameter setting in § 4.

To summarize, the optimal parameter θ\theta of (11) can be obtained by minimizing the loss function in (15) for the given cascade C\mathcal{C}:

min⁡θ ℓ(θ;C):=∫0Tr(x(t),θ) dt+1Tx(T),(17)\min_{\theta}\ \ell(\theta;\mathcal{C}):=\int_{0}^{T}r(x(t),\theta)\,\mathrm{d}t+\mathbf{1}^{\mathsf{T}}x(T), \tag*{(17)}
s.t.m′(t)=g(m(t);θ),m(0)=[χSk;0],t∈[0,T],(18)\text{s.t.}\quad m'(t)=g(m(t);\theta),\quad m(0)=[\chi_{\mathcal{S}_k};0],\quad t\in[0,T], \tag*{(18)}

where m(t)=[x(t);h(t)]∈R2nm(t)=[x(t);h(t)]\in\mathbb{R}^{2n} and

g(m;θ)=(Ax−diag⁡(x)Ax+ε(x,h;η)Bx−Ch).(19)g(m;\theta)=\begin{pmatrix} Ax-\operatorname{diag}(x)Ax+\varepsilon(x,h;\eta)\\ Bx-Ch \end{pmatrix}. \tag*{(19)}

This is the parameter training problem given one cascade C\mathcal{C}, and can be trivially extended to the case D\mathcal{D} which consists of KK cascades. In what follows, we drop the notation C\mathcal{C} for conciseness.

In (19), g(m;θ)g(m;\theta) is the NMF dynamics derived in (13) with parameter θ=(A,w,η)\theta=(A,w,\eta) and w=(B,C)w=(B,C). In particular, η\eta stands for the network parameters of the deep neural network ε\varepsilon that wraps the augmented state mm to approximate the MZ memory term (9). It is worth noting that, the so-called control variable θ\theta is constant and time-invariant in NODE [5] as well as in NMF. Therefore, it is considerably easier to handle than that in classical optimal control θ\theta. Specifically, we can develop an algorithm for solving θ\theta in (16) which is easy to implement. Moreover, we can derive rigorous proof of the relation between the gradient of the loss function and the solution of the augmented dynamics.

As we can see, to find the optimal θ\theta of (16), the key is to compute ∇θℓ(θ)\nabla_\theta\ell(\theta) for any θ\theta. To this end, we recall that the Hamiltonian function associated with the control problem (16) is

H(m(t),p(t);θ)=p(t)⋅g(m(t);θ)+r(m(t),θ),(20)H(m(t),p(t);\theta)=p(t)\cdot g(m(t);\theta)+r(m(t),\theta), \tag*{(20)}

where p(t)∈R2np(t)\in\mathbb{R}^{2n} is the co-state variable (also known as the adjoint variable) associated with m(t)m(t). Here, p(t)p(t) plays the role of Lagrange multiplier for the ODE constraint (16b). The standard optimal control theory states that the co-state p(t)p(t) follows the ODE backward in time as follows:

{p′(t)=−∇mg(m(t);θ)p(t)−∇mr(m(t),θ),T≥t≥0,p(T)=[1;0].(21)\begin{cases} p'(t)=-\nabla_m g(m(t);\theta)p(t)-\nabla_m r(m(t),\theta), & T\ge t\ge0,\\ p(T)=[1;0]. \tag*{(21)} \end{cases}

The terminal condition p(T)=[1;0]p(T)=[1;0] has this simple form because the “terminal loss” in (16) is given by [1;0]⋅m(T)=1⋅x(T)[1;0]\cdot m(T)=1\cdot x(T).

Now we show that ∇θℓ\nabla_\theta\ell can be obtained by solving the ODE (16b) forward in time and an augmented ODE backward in time. To this end, we need the following theorem, whose proof is given in Appendix A.4.

Theorem 3. The gradient ∇θℓ(θ)\nabla_\theta\ell(\theta) of the loss function ℓ\ell defined in (16) for any parameter θ\theta and cascade data C\mathcal{C} is given by

∇θℓ(θ)=∫0T(∇θg(m(t);θ)p(t)+∇θr(m(t),θ)) dt.(22)\nabla_\theta\ell(\theta)=\int_{0}^{T}\left(\nabla_\theta g(m(t);\theta)p(t)+\nabla_\theta r(m(t),\theta)\right)\,\mathrm{d}t. \tag*{(22)}

Moreover, if m∗m^* is the solution of (16b) using the optimal solution θ∗\theta^* to (16), and p∗p^* is the co-state determined by (19) with m∗m^* and θ∗\theta^*, then ∫0T∇θH(m∗(t),p∗(t);θ) dt=0\int_{0}^{T}\nabla_\theta H(m^*(t),p^*(t);\theta)\,\mathrm{d}t=0.

The formula (22) in Theorem 3 suggests that we can compute ∇θℓ\nabla_\theta\ell by tracking an auxiliary variable q\mathbf{q} that follows the backward differential equation and terminal condition:

{q′(t)=−∇θg(m(t),θ)Tp(t)−∇θr(θ,m(t)),T≥t≥0,q(T)=0.(23)\begin{cases} \mathbf{q}'(t)=-\nabla_\theta\mathbf{g}(\mathbf{m}(t),\theta)^{\mathsf{T}}\mathbf{p}(t)-\nabla_\theta r(\theta,\mathbf{m}(t)), & T\ge t\ge0,\\ \mathbf{q}(T)=\mathbf{0}. \tag*{(23)} \end{cases}

Then (20) implies that ∇θℓ(θ)=q(T)−∫0Tq′(t) dt=q(0)\nabla_\theta\ell(\theta)=\mathbf{q}(T)-\int_0^T\mathbf{q}'(t)\,\mathrm{d}t=\mathbf{q}(0).

Before closing this section, we need to clarify one implementation issue with the running loss rr. Suppose that the infection times in the cascade C\mathcal{C} can be sorted 0<t(1)<t(2)<⋯<t(m)<t(m+1):=T0<t^{(1)}<t^{(2)}<\cdots<t^{(m)}<t^{(m+1)}:=T. That is, there are mm infections (excluding the infections at the source nodes) during the cascade C\mathcal{C}. (Note that any two infection times coincide with probability 0 since the point process is simple.) For notation simplicity, suppose that at time t(i)t^{(i)}, the new infected node is ii.

Then the integral of the running loss reduces to

∫0T∇θr(θ,m) dt=∑i=0m∇θ(−log⁡gi(m(t(i));θ)),(24)\int_0^T\nabla_\theta r(\theta,\mathbf{m})\,\mathrm{d}t=\sum_{i=0}^{m}\nabla_\theta\left(-\log g_i(\mathbf{m}(t^{(i)});\theta)\right), \tag*{(24)}

where gi(m(t),θ)g_i(\mathbf{m}(t),\theta) is the iith component of g(m(t),θ)\mathbf{g}(\mathbf{m}(t),\theta). Hence, we need to compute q(0)\mathbf{q}(0) by solving the ODE (21) backward in each time interval as

q(t(i−1))=q(t(i))−∫t(i)t(i−1)∇θg(m(t),θ)Tp(t) dt−∇θlog⁡gi−1(m(t(i−1));θ).(25)\mathbf{q}(t^{(i-1)})=\mathbf{q}(t^{(i)})-\int_{t^{(i)}}^{t^{(i-1)}}\nabla_\theta\mathbf{g}(\mathbf{m}(t),\theta)^{\mathsf{T}}\mathbf{p}(t)\,\mathrm{d}t-\nabla_\theta\log g_{i-1}(\mathbf{m}(t^{(i-1)});\theta). \tag*{(25)}

Similarly, we have

p(t(i−1))=p(t(i))−∫t(i)t(i−1)∇mg(m(t),θ)Tp(t) dt−∇mlog⁡gi−1(m(t(i−1));θ).(26)\mathbf{p}(t^{(i-1)})=\mathbf{p}(t^{(i)})-\int_{t^{(i)}}^{t^{(i-1)}}\nabla_{\mathbf{m}}\mathbf{g}(\mathbf{m}(t),\theta)^{\mathsf{T}}\mathbf{p}(t)\,\mathrm{d}t-\nabla_{\mathbf{m}}\log g_{i-1}(\mathbf{m}(t^{(i-1)});\theta). \tag*{(26)}

The ODE of m(t)\mathbf{m}(t) remains the same as in (18) since it does not involve the running loss rr.

To summarize, in order to compute ∇θℓ(θ)\nabla_\theta\ell(\theta) for any given θ\theta, we need to first solve the ODE (18) of m(t)\mathbf{m}(t) forward in time from 0 to TT; Then we need to solve the ODE system (18), (21), and (23) of (m(t),p(t),q(t))(\mathbf{m}(t),\mathbf{p}(t),\mathbf{q}(t)) backward in time from TT to 0. In particular, we need to solve the backward ODE such that the last term (24) and (23) are added for p(t)\mathbf{p}(t) and q(t)\mathbf{q}(t) in each time interval (t(i−1),t(i)](t^{(i-1)},t^{(i)}]. Finally, we obtain ∇θℓ(θ)=q(0)\nabla_\theta\ell(\theta)=\mathbf{q}(0). The complete training process is summarized in Algorithm 1, where mini-batches of cascades are used to compute the stochastic gradient in searching the (local) minimizer θ\theta. We did not include the gradient of the regularization of θ\theta, but its computation is standard and can be easily added to ∇θℓ(θ)\nabla_\theta\ell(\theta).

Influence Maximization with Learned NMF

In this section, we show how the proposed NMF can be used to tackle an important but very challenging problem known as the influence maximization. Suppose we have trained an NMF with parameters θ\theta in Algorithm 1, such that we can estimate x(t)\mathbf{x}(t) for any t∈[0,T]t\in[0,T] and any given source node set χS\chi_S. Then the goal of influence maximization is to identify χS∈{0,1}n\chi_S\in\{0,1\}^n such that its influence at the prescribed time TT (or any other prescribed t∈(0,T)t\in(0,T)) is maximized. Namely, our goal is to solve the following optimization problem

max⁡χS σ(T;χS):=1nTx(T;χS),s.t.χS∈{0,1}n,1nTχS=n0,(27)\max_{\chi_S}\ \sigma(T;\chi_S):=\mathbf{1}_n^{\mathsf{T}}\mathbf{x}(T;\chi_S),\qquad\text{s.t.}\quad\chi_S\in\{0,1\}^n,\quad\mathbf{1}_n^{\mathsf{T}}\chi_S=n_0, \tag*{(27)}

where n0∈Nn_0\in\mathbb{N} is the given budget size. Note that x(T;χS)\mathbf{x}(T;\chi_S) is the first nn components of m(T)\mathbf{m}(T) computed by forward NMF dynamics with initial value m(0)=[χS;0]\mathbf{m}(0)=[\chi_S;0]. However, (25) is an NP-hard combinatorial optimization problem [18], we propose to relax the binary-valued decision vector χS\chi_S to u∈[0,1]n\mathbf{u}\in[0,1]^n in the continuous hypercube [0,1]n[0,1]^n as

min⁡u∈U L(u):=R(u)−1nTx(T;u),whereU:={u∈[0,1]n:1nTu=n0},(28)\min_{\mathbf{u}\in\mathcal{U}}\ L(\mathbf{u}):=\mathcal{R}(\mathbf{u})-\mathbf{1}_n^{\mathsf{T}}\mathbf{x}(T;\mathbf{u}),\qquad\text{where}\quad\mathcal{U}:=\{\mathbf{u}\in[0,1]^n:\mathbf{1}_n^{\mathsf{T}}\mathbf{u}=n_0\}, \tag*{(28)}
Algorithm 1 Neural mean-field (NMF) dynamics

Figure 1 (PDF p. 9).

and R(u)\mathcal{R}(\boldsymbol{u}) is a regularizer that encourages all components of u\boldsymbol{u} to take values close to either 0 or 1. In our experiments, we simply set R(u)=∑i=1nui(1−ui)\mathcal{R}(\boldsymbol{u}) = \sum_{i=1}^{n} u_i(1-u_i). Then we employ the projected gradient descent (PGD) method to solve (26):

ul+1=ΠU(ul−γl∇uL(ul)):=arg⁡min⁡u∈U∥u−(ul−γl∇uL(ul))∥2,(29)\boldsymbol{u}_{l+1} = \Pi_{\mathcal{U}}(\boldsymbol{u}_l-\gamma_l\nabla_{\boldsymbol{u}}L(\boldsymbol{u}_l)) := \underset{\boldsymbol{u}\in\mathcal{U}}{\arg\min}\left\lVert\boldsymbol{u}-(\boldsymbol{u}_l-\gamma_l\nabla_{\boldsymbol{u}}L(\boldsymbol{u}_l))\right\rVert^2, \tag*{(29)}

where ll is the iteration counter of PGD, τl>0\tau_l>0 is the step size, and ΠU\Pi_{\mathcal{U}} denotes the orthogonal projection onto U\mathcal{U}. If ∇uL(ul)\nabla_{\boldsymbol{u}}L(\boldsymbol{u}_l) is known, then (27) is a standard quadratic program (QP) and can be solved efficiently by off-the-shelf solvers. Therefore, the only remaining question is to compute ∇uL(u)\nabla_{\boldsymbol{u}}L(\boldsymbol{u}) for any given u\boldsymbol{u}. The following theorem states that this quantity can be computed very efficiently using the proposed NMF dynamics. The proof is provided in Appendix § 7.§ 5.

Theorem 4. Let [m(t);s(t)][\boldsymbol{m}(t);\boldsymbol{s}(t)] be the solution of the augmented NMF system:

(m′(t)s′(t))=(g(m(t);θ)∇xgx(m;θ)Ts(t))(30)\begin{pmatrix} \boldsymbol{m}'(t)\\ \boldsymbol{s}'(t) \end{pmatrix} = \begin{pmatrix} \boldsymbol{g}(\boldsymbol{m}(t);\boldsymbol{\theta})\\ \nabla_{\boldsymbol{x}}g_{\boldsymbol{x}}(\boldsymbol{m};\boldsymbol{\theta})^{\mathsf{T}}\boldsymbol{s}(t) \tag*{(30)} \end{pmatrix}

with initial value [m(0);s(0)]=[[u;0];1][\boldsymbol{m}(0);\boldsymbol{s}(0)] = [[\boldsymbol{u};0];1] forward in time [0,T][0,T], where gxg_{\boldsymbol{x}} is the first nn components of g\boldsymbol{g}. Then ∇uL(u)=∇uR(u)−s(T)\nabla_{\boldsymbol{u}}L(\boldsymbol{u}) = \nabla_{\boldsymbol{u}}\mathcal{R}(\boldsymbol{u})-\boldsymbol{s}(T).

Theorem 4 implies that ∇uL(u)\nabla_{\boldsymbol{u}}L(\boldsymbol{u}) can be easily computed by solving NMF augmented by an auxiliary variable s(t)\boldsymbol{s}(t) forward in time [0,T][0,T] as in (28). Note that the computation complexity of (28) is linear in the network size nn and standard numerical ODE integrators can quickly solve the ODE to high accuracy. We summarize the steps for solving (26) in Algorithm 2. Note that the output u\boldsymbol{u} may not be binary, and thus we can set the largest n0n_0 components of u\boldsymbol{u} to 1 and the rest to 0 as the final source set selection.

Algorithm 2 Influence maximization via neural mean-field dynamics (NMF-InfMax)

  1. Input: Trained NMF with g(⋅;θ)g(\cdot;\theta) from Algorithm 1, budget n0∈{1,…,n−1}n_0 \in\{1,\ldots,n-1\}

  2. Initialization: u∈Uu \in\mathcal{U}.

  3. for l=1,…,MaxIterationsl=1,\ldots,\mathrm{MaxIterations} do

  4. Solve [m(T),s(T)][m(T),s(T)] from (30) forward in time with initial [[u;0];1][[u;0];1]. (Forward pass)

  5. Set u^←u−γ∇uL(u)\hat{u} \leftarrow u-\gamma\nabla_u L(u) where ∇uL(u)=s(T)\nabla_u L(u)=s(T).

  6. Solve a QP: u←arg minu∈U∥u−u^∥2u \leftarrow\mathop{\mathrm{arg\,min}}_{u\in\mathcal{U}}\|u-\hat{u}\|^2.

  7. end for

  8. Output: Source set selection uu.

Numerical Experiments

Implementation details

In our NMF implementation, the neural mean field dynamic g(⋅;θ)g(\cdot;\theta) derived from Proposition 2.1 is learned as Algorithm 1, where ε(x,h;η)\varepsilon(x,h;\eta) is a three-layer fully connected network. Specifically, the input layer size of ε\varepsilon is 2n2n, and both of the hidden and output layer sizes are nn. We use Exponential Linear Unit (ELU) as the activation function. The output is truncated into [0,1][0,1]. We use the ℓ0\ell_0-norm regularization approximated by log-sum introduced by [50]. The NMF networks are trained and tested in PyTorch [49] by Adam optimizer [28] with default parameters (lr=0.001, β1=0.9\beta_1=0.9, β2=0.999\beta_2=0.999, ϵ=1e−8\epsilon=1\mathrm{e}{-8}) on a Linux workstation with Intel i9 8-Core Turbo 5GHz CPU, 64GB of memory, and an Nvidia RTX 2080Ti GPU. InfluLearner and NetRate are both trained by the Matlab code published by the original authors. All experiments are performed on the same machine. Given ground truth node infection probability x∗x^*, the Mean Absolute Error (MAE) of influence (Inf) and infection probability (Prob) of the estimated xx are defined by ∣1⋅(x(t)−x∗(t))∣|1\cdot(x(t)-x^*(t))| and ∥x(t)−x∗(t)∥1/n\|x(t)-x^*(t)\|_1/n for every tt, respectively. For all the experiments related on the influence estimation, we also use the scaled influence MAE ∣1⋅(x(t)−x∗(t))∣/n|1\cdot(x(t)-x^*(t))|/n as an evaluation metric.

Infection probability and influence function estimation

We first apply the proposed NMF to synthetic diffusion networks where ground truth node infection probabilities are available for quantitative evaluation.

Networks We use three types of network models [31] to generate these synthetic networks: hierarchical (Hier) network [8], core-periphery (Core) network [33] and Random (Rand) network with parameter matrices [0.9,0.1;0.1,0.9][0.9,0.1;0.1,0.9], [0.9,0.5;0.5,0.3][0.9,0.5;0.5,0.3], and [0.5,0.5;0.5,0.5][0.5,0.5;0.5,0.5], respectively.

For each of these three types of networks, we randomly generate 5 networks of (n,d)=(128,4)(n,d)=(128,4) and another 5 networks of (n,d)=(1024,4)(n,d)=(1024,4), where nn is the total number of nodes on the network and dd is the average out-degree per node.

Diffusion models and parameters We simulate the diffusion on these networks such that the infection time are modeled by exponential distribution (Exp), Rayleigh distribution (Ray), and general Weibull distribution (Wbl).

Note that our theoretical results in this work are based on diffusion models using exponential distribution, however, we still conduct experiments on other distributions to test the performance of NMF empirically. In particular, we draw the parameters αji\alpha_{ji} from Unif⁡[0.1,1]\operatorname{Unif}[0.1,1] to simulate the heterogeneous interactions between nodes for exponential and Rayleigh distributions. We generate both of the shape and scale parameters of Weibull distribution from Unif⁡[1,10]\operatorname{Unif}[1,10] randomly.

Training and testing data We randomly generate 900 source node sets of size varying between 1 and 10, and simulate 10 diffusion cascades for each source set for training. Thus the training data consists of K=9,000K=9{,}000 cascades, all of which are truncated into time window [0,T][0,T] with T=20T=20.

We generate 100 additional source sets in a similar way, and then split them as 50%-validation and 50%-test with ground truth of infection probability and influence estimated by simulating 10,000 cascades for each source set. This setting on validation and test data will be used for all the experiments related to influence estimation and all networks and cascades are generated using the SNAP package [34].

Algorithm and parameter settings In the training of NMF, the batch size of cascade data is set to 300 and the number of epochs is 50. The coefficients of the regularization term on AA and weight decay in Adam optimizer are set to (0.01,1)(0.01,1) and (0.001,0)(0.001,0) for network of size 128 and 1024, respectively. We use Runge-Kutta 4th order (rk4) method with 40 time steps to solve the ODEs numerically.

Comparison algorithm For comparison, we use InfluLearner [12], which is a state-of-the-art method that can estimate individual node infection probability directly from cascade data in the CIC setting as our method.

InfluLearner draws a set of random binary features from certain distribution for each node jj indicating the reachabilities of jj by other nodes, and then uses a convex combination of random basis function to parameterize the conditional infection probability of the node given a source set over these binary vectors. To estimate the reachability distribution, InfluLearner calculates the mean frequency of node jj being influenced by a source node ss, average over all cascades in the training dataset with the source ss.

In our test, we set the number of random features to 200 as suggested in [12].

It is worth noting that InfluLearner requires additionally the source identity for each infection to estimate the coverage functions. That is, InfluLearner also needs to know the original source node in the source set for each and every new infection occurred in the cascade in the training data. This additional information is provided in our simulated data in favor of InfluLearner. However, it is often unavailable in real-world applications such as epidemic spreads. The proposed NMF method does not have such restriction.

Moreover, to quantify estimation error, we compute the MAE of node infection probability and influence at tl=lt_l = l for l=1,…,20l = 1,\ldots,20, and average each over the 50 test source sets. Since InfluLearner needs to learn the coverage function for a prescribed time tt, we have to run it for each of the 20 time points one by one. In contrast, the proposed NMF is more advantageous since it can directly estimate the entire evolution of infection probabilities during [0,T][0,T], which is more computationally efficient.

Comparison results We show the numerical results of InfluLearner and NMF for influence estimation on the three aforementioned synthetic diffusion networks (i.e., Hier, Core, and Rand) in Figure 2. For each of these three networks, we simulate three types of diffusion times (i.e., Exp, Ray, and Wbl). Therefore, we have 9 network/diffusion combinations in total. For each of these 9 combinations, we show the scaled influence MAE (top) and probability MAE (bottom) of InfluLearner and NMF on networks of size 128 and 1024 as explained above. In each plot of Figure 2, we show the mean (center line) and standard deviation (shade) averaged over 5 instances.

Figure 2. MAE of scaled influence (top) and node infection probability (bottom) by InfluLearner [12] and NMF on each of the 9 different combinations of Core-periphery (Core), Random (Rand) and Hierarchical (Hier) networks, and exponential (Exp), Rayleigh (Ray) and Weibull (Wbl) diffusion models. Mean (centerline) and standard deviation (shade) over 50 test source sets are shown. Each network has two configurations of (n,d)(n, d): (128,4)(128, 4) and (1024,4)(1024, 4), where nn is the number of nodes in the diffusion network, and dd is the average out-degree per node.

As we can observe in Figure 2, the error of NMF is much smaller than that of InfluLearner for almost all times, except at some early stages and on Hierarchical network with Weibull distribution. This demonstrates that NMF is a much more accurate method in influence estimation.

Network structure inference

In addition to influence estimation, the proposed NMF can also learn the network structure and the transmission rate matrix AA as a byproduct during training. In this test, we examine the quality of the learned AA. We set the recovered adjacency matrix E\mathcal{E} to the binary indicator matrix A⊤≥ϵA^{\top} \ge\epsilon. More precisely, once we learned AA in NMF training, we set the edge E\mathcal{E} as Eij=1\mathcal{E}_{ij}=1 if αij=(A)ij≥0.01\alpha_{ij}=(A)_{ij}\ge0.01 and 0 otherwise. We set the threshold ϵ=0.01\epsilon=0.01 because all the transmission rates are between [0.01,1][0.01,1].

Evaluation criteria To evaluate the quality of E\mathcal{E} and A\mathbf{A}, we use four metrics: precision (Prc), recall (Rcl), accuracy (Acc), and correlation (Cor), defined as follows,

Prc⁡(E,E∗)=∣E∩E∗∣∣E∗∣,Rcl⁡(E,E∗)=∣E∩E∗∣∣E∣,\operatorname{Prc}(\mathcal{E},\mathcal{E}^{*})=\frac{|\mathcal{E}\cap\mathcal{E}^{*}|}{|\mathcal{E}^{*}|},\qquad\operatorname{Rcl}(\mathcal{E},\mathcal{E}^{*})=\frac{|\mathcal{E}\cap\mathcal{E}^{*}|}{|\mathcal{E}|},
Acc⁡(E,E∗)=1−∣E−E∗∣∣E∣+∣E∗∣,Cor⁡(A,A∗)=∣tr⁡(ATA∗)∣∥A∥F∥A∗∥F.\operatorname{Acc}(\mathcal{E},\mathcal{E}^{*})=1-\frac{|\mathcal{E}-\mathcal{E}^{*}|}{|\mathcal{E}|+|\mathcal{E}^{*}|},\qquad\operatorname{Cor}(\mathbf{A},\mathbf{A}^{*})=\frac{|\operatorname{tr}(\mathbf{A}^{\mathsf{T}}\mathbf{A}^{*})|}{\|\mathbf{A}\|_{F}\|\mathbf{A}^{*}\|_{F}}.

where ∣E∣|\mathcal{E}| counts the number of nonzero entries in E\mathcal{E}, and the E∗\mathcal{E}^{*} and A∗\mathbf{A}^{*} are the ground truths, respectively. In Cor, ∥A∥F2=tr⁡(ATA)\|\mathbf{A}\|_{F}^{2}=\operatorname{tr}(\mathbf{A}^{\mathsf{T}}\mathbf{A}) is the Frobenius norm of the matrix A\mathbf{A}. Prc is the ratio of edges in E∗\mathcal{E}^{*} that are recovered in E\mathcal{E}. Rcl is the ratio of correctly recovered edges in E\mathcal{E}. Acc indicates the ratio of the number of common edges shared by E\mathcal{E} and E∗\mathcal{E}^{*} against the total number of edges in them. Cor measures similarity between A\mathbf{A} and A∗\mathbf{A}^{*} by taking their values into consideration. All metrics are bounded between [0,1][0,1], and higher value indicates better accuracy.

Comparison algorithm For comparison purpose, we also applied NetRate [16], a state-of-the-art algorithm that uncovers the network structure and transmission rates from cascade data. It is worth noting that NetRate requires the knowledge of the specific diffusion model (e.g., Exp, Ray, or Wbl), so that the likelihood function can be explicitly expressed. Moreover, NetRate can only estimate A\mathbf{A} of diffusion networks, but not the influence. In contrast, NMF tackles both network inference and influence estimation simultaneously. In terms of computation efficiency, we observed that the implementation of NetRate provided in [16] runs very slowly for large networks. Therefore, we only perform comparisons on networks of size n=128n=128 in this experiment.

Comparison results We compared the estimated E\mathcal{E} and A\mathbf{A} using NetRate and NMF using the four criteria mentioned above in Table 1 for three types of networks (Random, Hierarchical, and Core-periphery) and two diffusion models (Exponential and Rayleigh). In all of these tests, NMF consistently outperforms NetRate in all accuracy metrics. We also draw A\mathbf{A} inferred by NetRate and NMF for a visual comparison in Figure 3. In Figure 3, we show the ground truth A∗\mathbf{A}^{*} (left), the matrix A\mathbf{A} inferred by NetRate (middle), and A\mathbf{A} learned by NMF (right). The values of αij\alpha_{ij} are indicated by the color—the darker the red is, the higher the value of αij\alpha_{ij}—and the white pixels represent where αij\alpha_{ij} is zero. As we can see, A\mathbf{A} learned by NMF is much more faithful to A∗\mathbf{A}^{*} than that by NetRate. This result shows that NMF is very versatile and robust in learning network structure from cascade data.

Figure 3. Ground truth A∗\mathbf{A}^{*} (left) and A\mathbf{A} inferred by NetRate (middle) and NMF (right) in same color scale using cascades from a Hierarchical network consisting of 128 nodes and 512 edges with exponential diffusion model. Darker pixel indicates larger value of an entry of A\mathbf{A}.

DiffusionNetworkMethodPrcRclAccCor
ExponentialRandomNetRate0.4570.8210.5150.438
ExponentialRandomNMF0.4590.9970.6220.910
ExponentialHierarchicalNetRate0.3950.7480.5150.739
ExponentialHierarchicalNMF0.5950.9970.7450.928
ExponentialCore-peripheryNetRate0.2770.6110.2640.264
ExponentialCore-peripheryNMF0.2920.9970.4500.839
RayleighRandomNetRate0.4810.3990.4340.465
RayleighRandomNMF0.8830.9050.8940.909
RayleighHierarchicalNetRate0.6590.4290.5190.464
RayleighHierarchicalNMF0.8890.9360.9110.913
RayleighCore-peripheryNetRate0.1500.2200.1780.143
RayleighCore-peripheryNMF0.6490.8200.7240.820

Table 1. Performance of network structure inference using NetRate [16] and the proposed NMF on Random, Hierarchical, and Core-periphery networks consisting of 128 nodes and 512 edges with Exponential and Rayleigh as diffusion distribution on edges. Quality of the learned edge set E\mathcal{E} and distribution parameter AA are measured by precision (Prc), recall (Rcl), accuracy (Acc), and correlation (Cor). Larger value indicates higher accuracy.

Since NetRate code [16] was implemented in MATLAB and is executed on CPU in our experiment, the computation times of NetRate and NMF cannot be directly compared. However, we notice that NetRate takes approximately 10+ hours on average to infer each network structure A\mathbf{A} in Table 1, whereas NMF only requires about 300 seconds on average to return both more accurate A\mathbf{A} and an influence estimation mechanism.

Scalability to network size and density

In this test, we will demonstrate the robustness of NMF in influence estimation when the network size nn and density dd vary. Recall that dd stands for the average out-degree per node. The larger and/or denser the network is, the more challenging the estimation becomes. In all the experiments, we use training data consisting of 9,000 cascades generated from Hierarchical network and exponential diffusion model and set the batch size to 300.

Network size Recall that we have showed in Figure 2 that NMF consistently outperforms than InfluLearner when the network size is set to 128 and 1024. To show the scability of NMF, we further test NMF on increasing network size nn from 128 to 2048 (with density d=4d = 4). To test the training time of NMF, we terminate the computation when the average MAE of infection probability on validation data over 20 timepoints tℓ=ℓt_\ell= \ell (ℓ=1,2,…,20\ell= 1, 2, \ldots, 20) is below 0.07. Euler method with 40 steps is employed as the ODE solver and the learning rate of the Adam optimizer is set to 0.0001 for network with 2048 nodes. The training time of NMF is shown in Figure 4d, which demonstrate that NMF is scalable for large network size nn.

Four plots comparing probability MAE, influence MAE, and training time

Figure 4. (a)–(b) MAE of infection probability and influence obtained by InfluLearner [12] and NMF on Hierarchical networks of size n=128n = 128 and increasing dd from 4 to 6. (c) Training time (in seconds) of NMF versus density (average out-degree per node) dd. (d) Training time (in seconds) versus network size nn.

Network density We also test the performance of NMF for varying network density dd. We compare the infection probability and influence MAE of InfluLearner and NMF for varying edge density dd set to 4, 5, and 6 on a Hierarchical network on exponential diffusion model with 128 nodes. Figure 4a and Figure 4b show that the MAE of infection probability and influence estimation obtained by InfluLearner and NMF. These two plots show that NMF is very robust when the density of the network increases by consistently generating estimates of low MAE. Figure 4c shows the training time of NMF versus network density dd while n=128n = 128 is fixed. In this plot, the computation time is recorded when the training MAE at time tht_h is below 0.04, where tht_h is the time when on average half of the nodes on the network are infected as indicated by the ground truth. Here, rk4 method with 40 steps is employed as the ODE solver. Similarly, Figure 4d shows the training time versus network size nn while d=4d = 4 is fixed. From Figure 4c and Figure 4d, we can see that the computational cost of NMF grows approximately quadratic in density dd and linear in size nn.

Figure 5. (a) Influence generated the source sets selected by NMF-InfMax trained using increasing number of cascades on Hierarchical networks with 1,024 nodes and 4,096 edges. (b) Influence generated by the source sets selected by IMINFECTOR and NMF-InfMax on the MemeTracker dataset at T=10T = 10 hours.

Influence maximization

This part of the experiment is dedicated to performance evaluation in influence maximization. Specifically, we use the trained NMF to find the optimal source set with limited budget for maximal influence by following Algorithm 2 which is referred to as NMF-InfMax.

Comparison algorithms For comparison purpose, we also test the following methods for influence maximization.

  • IMINFECTOR [46]: IMINFECTOR represents the cascade data into two datasets consisting of seed-cascade length pairs and seed-influenced node pairs to approximate the influence spread and infection probability of each node by a regression model and a probability classifier, respectively. The outputs are used to reduce the number of candidate seeds and reformulate the computation of the influence spread in a greedy solution to influence maximization. Like our method, IMINFECTOR only uses cascade data as inputs, with embedding size 50 and sampling percentage 120, trained for 50 epochs with a learning rate of 0.1. The reduction percentage PP is set to 100 to keep full information of

cascades.

  • IMM [54]: IMM is a reverse reachable (RR) sketch based method which applies the standard greedy algorithm for maximum coverage to derive a budget size node set that covers a large number of RR sets sampled from the given network. We consider the case when IMM return (1−1/e−ε)(1 - 1/e - \varepsilon)-approximate solution with ε=0.1\varepsilon= 0.1 and parameter ℓ=1\ell= 1, following the experiments in [54].

  • InfluMax [19, 21]: InfluMax speed up the greedy influence maximization algorithm by exploiting submodularity. We incorporate it with the influence estimation algorithm ConTinEst [13]. For ContinEst, we draw 10,000 random samples, each of which has 5 random labels for each node.

Since IMM and InfluMax both require the knowledge of the transmission matrix AA, we apply NetRate method to learn AA from cascade data first, then feed AA to these two methods. We remark that NetRate and IMINFECTOR are both in favor of training data consisting of cascades with the source sets of size 1 (i.e., only one source node). In contrary, NMF-InfMax does not have this restriction and thus is more flexible. However, for comparison purpose, we only feed cascade data with single source node to all methods in this experiment.

Experiment setting We again use three types of Kronecker graph models: Hierarchical (Hier), Core-periphery (Core) and Random (Rand) networks, and simulate the diffusion processes using exponential distribution with transmission rates randomly sampled from Unif[0.1,1]. For each type of network model, we generate two networks of size n=1,024n = 1,024 with d=2d = 2 and d=4d = 4, respectively. We sample 100 source nodes, and for each source node we simulate 10 cascades. Hence we have a total of K=1,000K=1,000 cascades for training. To train NMF, we set the batch size to 300 and the number of epochs to 50. The coefficients of the regularization term on AA is set to 0.001, and the rk4 method with 40 time steps is employed as the ODE solver. To train NMF-InfMax, we set the step size to constant 0.01, and terminate PGD if either the iteration number reaches 500 or the computed influence does not change for 10 consecutive iterations. In fig:5a, we show the accuracy of NMF-InfMax when the number of training cascades increases from 1,000 to 5,000 for each fixed source set of size from 1 to 10. As we can observe, the accuracy increases significantly when the number of cascades grows from 1,000 to 2,000 but then improvements become insignificant. This suggests that 2,000 cascades is necessary to obtain more accurate influence maximization results for NMF-InfMax. However, due to the limited scalability of NetRate which performs extremely slowly when the number of cascades is over 1,000 and average out-degree is over 4. We also tested IMINFECTOR with larger training data set, but unlike our method, the accuracy of IMINFECTOR does not improve over 1,000. Hence we still only feed 1,000 cascades to all the compared methods despite that this choice is only in favor of three existing methods.

It is also important to note that both InfluMax and IMM require the knowledge of diffusion model given by the shape and scale parameters of edges for the computation of NetRate and their own. Thus, they are more vulnerable to model mis-specification. In this test, we assume they know the ground truth diffusion model, so they can attain their highest accuracy. However, it is worth noting that the network inference by NetRate can be very expensive computationally. For example, it took NetRate up to 160 hours to infer the network structure from 1,000 cascades of a core-periphery network of n=1,024n = 1,024 and d=4d = 4 in fig:6c. In contrast, the computational cost of IMINFECTOR is very low, but IMINFECTOR is more restrictive on data because it requires that the training cascades contain the nodes to be selected. This may not be feasible in practice. Moreover, the influence maximization results obtained by IMINFECTOR also appear to be worse than that by NMF, as shown below.

Comparison results The influence maximization results obtained by the aforementioned algorithms and NMF are shown in Figure 6. As we can see, NMF-InfMax consistently returns more influential source sets with all budget n0n_0 for all varying network structure, density, and budget.

Figure 6. Influence of the source sets selected by the compared methods on three different types of networks: (a) Hierarchical, (b) Random, and (c) Core-periphery, with exponential diffusion model at T=10T = 10 and varying source sizes n0n_0 from 1 to 10. Each network consists of 1024 nodes and 2048 edges (top) or 4096 edges(bottoms).

Real data We extract diffusion cascades from the MemeTracker dataset [30] which includes 300 million blog posts and articles collected from 5,000 active media sites between March 2011 and February 2012. Following [12], we select the group of cascades with the keyword ”apple and jobs” and then split them as 60%-train and 40%-validation for the influence maximization models. As the diffusion model of real-world cascade data is unknown, we only test IMINFECTOR and NMF-InfMax. We follow the setting in [12] to compute the influence of any selected source set: we uniformly sample one cascade from the data for each node in the set and take the union of all sampled cascades as the set of infected nodes. We repeat this process for 1,000 times and take the average as the true influence of the selected set. fig:5b shows the result of influence maximization results. In fig:5b, we set T=10T = 10 and the source size n0=10,20,⋯ ,60n_0 = 10, 20, \cdots, 60, and plot the influence of the source sets selected by IMINFECTOR and NMF-InfMax. As we can see, NMF-InfMax consistently selected more influential combination of nodes that generate greater influence than those selected by IMINFECTOR do.

Related Work

In this section, we conduct a comprehensive review of the literature related to the present work. There are several topics involved in the proposed method, namely, influence estimation, network inference, and influence maximization, which just emerged within the past decade. These topics are considered independently, and the methods developed are mostly heuristic or sample-demanding. In what follows, we discuss these topics and their related work in order.

Influence estimation

Sampling-based influence estimation methods have been considered for discrete-time and continuous-time diffusion models. Discrete-time models assume node infections only occur at discrete time points. Under this setting, the independent cascade (IC) and linear threshold (LT) models are considered and the propagation spread of a source set SS is simply estimated by the expected reachable set size of SS taken over the randomness of the influence propagation process in [26]. To improve the efficiency of Monte Carlo simulations used in influence estimation, a method with provable performance guarantee is developed which iterates over a sequence of guesses on the true influence until the verifier accepts in [39]. In [39], the verifier estimates the influence on multiple sampled graphs using a standard Riemann sum of the influence function, and accepts if this value is close to the guesses. In [3], the reverse reachable (RR) sets of nodes are adopted which proved the expected spread equals nn times the fraction of sampled RR sets covered by the source set. The sample size is controlled by a given threshold [3], a pre-calculated parameter [55], or some stop conditions [54] to achieve a balance between efficiency and accuracy. Instead of using the full network structure as the methods above, sketch-based approaches only characterize propagation instances for influence computation, such as the method in [10], which considers per-node summary structures defined by the bottom-kk min-bash [9] sketch of the combined reachability set. In contrast to discrete-time models, continuous-time diffusion models allow arbitrary event occurrence times and hence are more accurate in modeling real-world diffusion processes. In continuous-time independent cascade (CIC) models, influence estimation can be reformulated as the problem of finding the least label list which contains information about the distance to the smallest reachable labels from the source [13, 21]. Compared to methods using a fixed number of samples, a more scalable approximation scheme with a built-in block is developed to minimize the number of samples needed for the desired accuracy [45]. Inspired by [54], algorithms proposed in [3, 54, 55] can be extended from the IC model to other discrete-time models and CIC models by generalizing the definition of RR sets. In [25], a neural mean-field dynamics approach is proposed, which employs the Mori-Zwanzig (MZ) formalism to derive the node infection probabilities in discrete-time setting. The influence function can also be approximated by solving a jump stochastic differential equation [60] or a deterministic differential equation that governs the evolution of the influence counter [7].

The aforementioned methods require knowledge of cascade traces [10] or the diffusion networks, such as node connectivity and node-to-node infection rates, as well as various assumptions on the diffusion of interests. However, such knowledge about the diffusion networks may not be available in practice, and the assumptions on the propagation or data formation are often application-specific and do not hold in most other problems. InfluLearner [12] is a state-of-the-art method that does not require knowledge of the underlying diffusion network. InfluLearner estimates the influence directly from cascades data in the CIC models by learning the influence function with a parameterization of the coverage functions using random basis functions. However, the estimation of random basis function suggested by [12] requires knowledge of the original source node for every infection, which can be difficult or impossible to be tracked in real-world applications, such as epidemic spreads.

In recent years, deep learning techniques have been employed to improve the scalability of influence estimation on large networks. In particular, convolutional neural networks (CNNs) and attention mechanism are incorporated with both network structures and user specific features to learn users’ latent feature representation in [51]. By piping represented cascade graphs through a gated recurrent unit (GRU), the future incremental influence of a cascade can be predicted [36]. RNNs and CNNs are also applied to capture the temporal relationships on the user-generated contents networks (e.g., views, likes, comments, reposts) and extract more powerful features in [61]. In methods based on graph structures, graph neural networks (GNNs) and graph convolution networks (GCNs) are widely applied. In particular, two coupled GNNs are used to capture the interplay between node activation states and the influence spread [4], while GCNs integrated with teleport probability from the domain of page rank in [35] enhanced the performance of method in [51]. However, these methods depend critically on the structure or content features of cascades which is not available in many real-world applications.

Network structure inference

Inference of diffusion network structure is an important problem closely related to influence estimation. In particular, if the network structure and infections rates are unknown, one often needs to first infer such information from a training dataset of sampled cascades, each of which tracks a series of infection times and locations on the network. Existing methods have been proposed to infer network connectivity [14, 17, 20, 38] and also the infection rates between nodes [16, 18, 43]. Submodular optimization is applied to infer network connectivity [17, 20, 38] by considering the most probable [17] or all [20, 38] directed trees supported by each cascade. One of the early works that incorporate spatio-temporal factors into network inference is introduced in [38]. Utilizing convex optimization, transmission functions [14], the prior probability [43], and the transmission rate [16] over edges are inferred from cascades. In addition to static networks, the infection rates are considered but also in the unobserved dynamic network changing over time [18]. Besides cascades, other features of dynamical processes on networks have been used to infer the diffusion network structures. To avoid using predefined transmission models, the statistical difference of the infection time intervals between nodes in the same cascade versus those not in any cascade was considered in [52]. A given time series of the epidemic prevalence, i.e., the average fraction of infected nodes was applied to discover the underlying network. The recurrent cascading behavior is also explained by integrating a feature vector describing the additional features [57]. A graph signal processing (GSP) approach is developed to infer graph structure from dynamics on networks [11, 41].

Influence maximization

Influence maximization is an important but very challenging problem in real-world applications of diffusion networks, such as commercial advertising and epidemic controls. Influence maximization is shown to be an NP-hard problem under most of diffusion models [37] (e.g., LT, IC, CIC). It was first formulated in [26] as a combinatorial optimization problem. Under certain assumptions, the influence function σ(⋅)\sigma(\cdot) is a non-negative monotone submodular function, and a standard greedy method [21, 26] can be applied to obtain provable sub-optimal solution. Specifically, the greedy method starts from an empty set SS and gradually add one node ii that maximizes the marginal gain σ(S∪{i})−σ(S)\sigma(S \cup\{i\}) - \sigma(S) to SS. Note that this requires repeatedly evaluation of influences σ(S)\sigma(S) which affects the result of influence maximization significantly.

Instead of searching all the nodes in the greedy iterations, a GCN is trained by a probabilistic greedy mechanism, such that it selects a node with probability proportional to its marginal gain to identify noise and predict the node quality for the propagation spread [40]. The computations on the reward for adding the node to set SS is performed in another Q-learning network. The importance of nodes can also be measured by exploiting the submodularity [22, 32] or only considering one-hop and two-hoop spread benefit measures on nodes in [24]. The influence maximization problem is also modeled as the maximum coverage problem of selecting the budget number of nodes to cover the maximum number of sampled RR sets in [3, 54, 55]. For instances without the information of network structure, the influence relationships between nodes are representation learned from cascade date initiated by a single node to derive a greedy solution in [46, 47].

Conclusion

We propose a novel framework using neural mean-field dynamics for inference and estimation on diffusion networks. Our new framework is derived from the Mori-Zwanzig formalism to obtain exact evolution of node infection probabilities. The Mori-Zwanzig memory can be approximated by convolutions, which renders the system as a delay differential equation for highly interpretable parameterization. Directly using information diffusion cascade data, our framework outperforms many state-of-the-art methods in network structure inference and influence estimation. Our framework can also effectively tackle influence maximization on networks, which is known to be a challenging NP-hard problem. Extensive numerical experiments were conducted to show the promising accuracy and efficiency of the proposed framework on both synthetic and real-world data sets. We expect that the proposed framework can be applied to many other optimization and control problems arising from diffusion network applications, such as optimal campaigning, propagation control, and source identification, which will also be investigated in our future work.

Proofs

Proof of Theorem 1

Proof. Let λi∗(t)\lambda_i^*(t) be the conditional intensity of node ii at time tt, i.e., E[dXi(t)∣H(t)]=λi∗(t) dt\mathbb{E}[\mathrm{d}X_i(t) \mid\mathcal{H}(t)] = \lambda_i^*(t)\,\mathrm{d}t. In the standard diffusion model, the conditional intensity λi∗(t)\lambda_i^*(t) of a healthy node ii (i.e., Xi(t)=0X_i(t) = 0) is determined by the total infection rate of its infected neighbors jj (i.e., Xj(t)=1X_j(t) = 1). That is,

λi∗(t)=∑jαjiXj(t)(1−Xi(t)).(31)\lambda_i^*(t) = \sum_j \alpha_{ji}X_j(t)(1-X_i(t)). \tag*{(31)}

By taking expectation EH(t)[⋅]\mathbb{E}_{\mathcal{H}(t)}[\cdot] on both sides of (31), we obtain

λi(t):=EH(t)[λi∗(t)]=EH(t)[αjiXj(t)(1−Xi(t))∣H(t)]=∑jαji(xj−xij)=∑jαji(xj−yij−eij).(32)\lambda_i(t) := \mathbb{E}_{\mathcal{H}(t)}[\lambda_i^*(t)] = \mathbb{E}_{\mathcal{H}(t)}\left[\alpha_{ji}X_j(t)(1-X_i(t))\mid\mathcal{H}(t)\right] = \sum_j \alpha_{ji}(x_j-x_{ij}) = \sum_j \alpha_{ji}(x_j-y_{ij}-e_{ij}). \tag*{(32)}

On the other hand, there is

λi(t) dt=EH(t)[λi∗(t)] dt=EH(t)[dXi(t)∣H(t)]=dEH(t)[Xi(t)∣H(t)]=dxi.(33)\lambda_i(t)\,\mathrm{d}t = \mathbb{E}_{\mathcal{H}(t)}[\lambda_i^*(t)]\,\mathrm{d}t = \mathbb{E}_{\mathcal{H}(t)}[\mathrm{d}X_i(t)\mid\mathcal{H}(t)] = \mathrm{d}\mathbb{E}_{\mathcal{H}(t)}[X_i(t)\mid\mathcal{H}(t)] = \mathrm{d}x_i. \tag*{(33)}

Combining (32) and (33) yields

xi′=dxi(t)dt=∑jαji(xj−yij−eij)=(Ax)i−(diag⁡(x)Ax)i−∑jαjieijx_i' = \frac{\mathrm{d}x_i(t)}{\mathrm{d}t} = \sum_j \alpha_{ji}(x_j-y_{ij}-e_{ij}) = (Ax)_i - (\operatorname{diag}(x)Ax)_i - \sum_j \alpha_{ji}e_{ij}

for every i∈[n]i\in[n], which verifies the xx part of (6). Similarly, we can obtain

xI′=∑i∈I∑j∉Iαji(xI−xI∪{j})=∑i∈I∑j∉Iαji(yI+eI−yI∪{j}−eI∪{j}).(34)x_I' = \sum_{i\in I}\sum_{j\notin I}\alpha_{ji}(x_I-x_{I\cup\{j\}}) = \sum_{i\in I}\sum_{j\notin I}\alpha_{ji}(y_I+e_I-y_{I\cup\{j\}}-e_{I\cup\{j\}}). \tag*{(34)}

Moreover, by taking derivative on both sides of xI(t)=yI(t)+eI(t)x_I(t)=y_I(t)+e_I(t), we obtain

xI′=∑i∈IyI∖{i}xi′+eI′=∑i∈IyI∖{i}∑j≠iαji(xj−xixj−eij)+eI′.(35)x_I' = \sum_{i\in I}y_{I\setminus\{i\}}x_i' + e_I' = \sum_{i\in I}y_{I\setminus\{i\}}\sum_{j\ne i}\alpha_{ji}(x_j-x_ix_j-e_{ij})+e_I'. \tag*{(35)}

Combining (34) and (35) yields the ee part of (6).

It is clear that x0=χSx_0=\chi_S. For every II, at time t=0t=0, there is xI(0)=∏i∈IXi(0)=1x_I(0)=\prod_{i\in I}X_i(0)=1 if I⊂SI\subset S and 0 otherwise; and the same for yI(0)y_I(0). Hence eI(0)=xI(0)−yI(0)=0e_I(0)=x_I(0)-y_I(0)=0 for all II. Hence z0=[x0;e0]=[χS;0]z_0=[x_0;e_0]=[\chi_S;0], which verifies the initial condition of (6).

Proof of Theorem 2

Proof. Consider the system (6) over a finite time horizon [0,T][0,T], which evolves on a smooth manifold r⊂RNr\subset\mathbb{R}^N. For any real-valued phase (observable) space function g:r→Rg:r\to\mathbb{R}, the nonlinear system (6) is equivalent to the linear partial differential equation, known as the Liouville equation:

{∂tu(t,z)=L[u](t,z),u(0,z)=g(z),(36)\begin{cases} \partial_t u(t,z)=\mathcal{L}[u](t,z),\\ u(0,z)=g(z), \tag*{(36)} \end{cases}

where the Liouville operator L[u]:=fˉ(z)⋅∇zu\mathcal{L}[u]:=\bar{f}(z)\cdot\nabla_z u. The equivalency is in the sense that the solution of (36) satisfies u(t,z0)=g(z(t;z0))u(t,z_0)=g(z(t;z_0)), where z(t;z0)z(t;z_0) is the solution to (6) with initial value z0z_0.

Denote etLe^{t\mathcal{L}} the Koopman operator associated with L\mathcal{L} such that etLg(z0)=g(z(t))e^{t\mathcal{L}}g(z_0)=g(z(t)) where z(t)z(t) is the solution of (6). Then etLe^{t\mathcal{L}} satisfies the semi-group property, i.e.,

etLg(z)=g(etLz)(37)e^{t\mathcal{L}}g(z)=g(e^{t\mathcal{L}}z) \tag*{(37)}

for all gg. On the right hand side of (37), zz can be interpreted as z=ι(z)=[ι1(z),…,ιN(z)]z=\iota(z)=[\iota_1(z),\ldots,\iota_N(z)] where ιj(z)=zj\iota_j(z)=z_j for all jj.

Now consider the projection operator P\mathcal{P} as the truncation such that Pg(z)=Pg(x,e)=g(x,0)\mathcal{P}g(z)=\mathcal{P}g(x,e)=g(x,0) for any z=(x,e)z=(x,e), and its orthogonal complement as Q=I−P\mathcal{Q}=I-\mathcal{P} where II is the identity operator. Note that z′(t)=dz(t)dt=∂∂tetLz0z'(t)=\frac{\mathrm{d}z(t)}{\mathrm{d}t}=\frac{\partial}{\partial t}e^{t\mathcal{L}}z_0, and fˉ(z(t))=etLfˉ(z0)=etLLz0\bar{f}(z(t))=e^{t\mathcal{L}}\bar{f}(z_0)=e^{t\mathcal{L}}\mathcal{L}z_0 since Lιj(z)=fj(z)\mathcal{L}\iota_j(z)=f_j(z) for all zz and jj. Therefore (6) implies that

∂∂tetLz0=etLLz0=etLPLz0+etLQLz0.(38)\frac{\partial}{\partial t}e^{t\mathcal{L}}z_0=e^{t\mathcal{L}}\mathcal{L}z_0=e^{t\mathcal{L}}\mathcal{P}\mathcal{L}z_0+e^{t\mathcal{L}}\mathcal{Q}\mathcal{L}z_0. \tag*{(38)}

Note that the first term on the right hand side of (36) is

etLPLz0=PLetLz0=PLz(t).(39)e^{t\mathcal{L}}\mathcal{P}\mathcal{L}z_0=\mathcal{P}\mathcal{L}e^{t\mathcal{L}}z_0=\mathcal{P}\mathcal{L}z(t). \tag*{(39)}

For the second term in (36), we recall that the well-known Dyson’s identity for the Koopman operator L\mathcal{L} is given by

etL=etQL+∫0tesLPLe(t−s)QL ds.(40)e^{t\mathcal{L}}=e^{t\mathcal{Q}\mathcal{L}}+\int_{0}^{t}e^{s\mathcal{L}}\mathcal{P}\mathcal{L}e^{(t-s)\mathcal{Q}\mathcal{L}}\,\mathrm{d}s. \tag*{(40)}

Applying (38) to QLz0\mathcal{Q}\mathcal{L}z_0 yields

etLQLz0=etQLQLz0+∫0tesLPLe(t−s)QLQLz0 ds=etQLQLz0+∫0tPLe(t−s)QLQLesLz0 ds=etQLQLz0+∫0tPLe(t−s)QLQLz(s) ds.(41)\begin{aligned} e^{t\mathcal{L}}\mathcal{Q}\mathcal{L}z_0=e^{t\mathcal{Q}\mathcal{L}}\mathcal{Q}\mathcal{L}z_0+\int_{0}^{t}e^{s\mathcal{L}}\mathcal{P}\mathcal{L}e^{(t-s)\mathcal{Q}\mathcal{L}}\mathcal{Q}\mathcal{L}z_0\,\mathrm{d}s \\ &=e^{t\mathcal{Q}\mathcal{L}}\mathcal{Q}\mathcal{L}z_0+\int_{0}^{t}\mathcal{P}\mathcal{L}e^{(t-s)\mathcal{Q}\mathcal{L}}\mathcal{Q}\mathcal{L}e^{s\mathcal{L}}z_0\,\mathrm{d}s \\ &=e^{t\mathcal{Q}\mathcal{L}}\mathcal{Q}\mathcal{L}z_0+\int_{0}^{t}\mathcal{P}\mathcal{L}e^{(t-s)\mathcal{Q}\mathcal{L}}\mathcal{Q}\mathcal{L}z(s)\,\mathrm{d}s. \tag*{(41)} \end{aligned}

Substituting (37) and (39) into (36), we obtain

∂∂tetLz0=PLz(t)+etQLQLz0+∫0tPLe(t−s)QLQLz(s) ds,(42)\frac{\partial}{\partial t}e^{t\mathcal{L}}z_0=\mathcal{P}\mathcal{L}z(t)+e^{t\mathcal{Q}\mathcal{L}}\mathcal{Q}\mathcal{L}z_0+\int_{0}^{t}\mathcal{P}\mathcal{L}e^{(t-s)\mathcal{Q}\mathcal{L}}\mathcal{Q}\mathcal{L}z(s)\,\mathrm{d}s, \tag*{(42)}

where we used the fact that etLPLz0=PLetLz0=PLz(t)e^{t\mathcal{L}}\mathcal{P}\mathcal{L}z_0=\mathcal{P}\mathcal{L}e^{t\mathcal{L}}z_0=\mathcal{P}\mathcal{L}z(t). Denote ϕ(t,z):=etLQLz\phi(t,z):=e^{t\mathcal{L}}\mathcal{Q}\mathcal{L}z, then we simplify (40) into

∂∂tetLz0=PLz(t)+ϕ(t,z0)+∫0tk(t−s,z(s)) ds,(43)\frac{\partial}{\partial t}e^{t\mathcal{L}}z_0=\mathcal{P}\mathcal{L}z(t)+\phi(t,z_0)+\int_{0}^{t}k(t-s,z(s))\,\mathrm{d}s, \tag*{(43)}

where k(t,z):=PLϕ(t,z)=PLetLQLzk(t,z):=\mathcal{P}\mathcal{L}\phi(t,z)=\mathcal{P}\mathcal{L}e^{t\mathcal{L}}\mathcal{Q}\mathcal{L}z.

Now consider the evolution of ϕ(t,z)\phi(t,z), which is given by

∂tϕ(t,z0)=QLϕ(t,z0),(44)\partial_t\phi(t,z_0)=\mathcal{Q}\mathcal{L}\phi(t,z_0), \tag*{(44)}

with initial condition ϕ(0,z0)=QLz0=Lz0−PLz0=f~(x0,e0)−f~(x0,0)=0\phi(0,z_0)=\mathcal{Q}\mathcal{L}z_0=\mathcal{L}z_0-\mathcal{P}\mathcal{L}z_0=\tilde{f}(x_0,e_0)-\tilde{f}(x_0,0)=0 since e0=0e_0=0. Applying P\mathcal{P} on both sides of (42) yields

∂tPϕ(t,z0)=PQLϕ(t,z0)=0,\partial_t\mathcal{P}\phi(t,z_0)=\mathcal{P}\mathcal{Q}\mathcal{L}\phi(t,z_0)=0,

with initial Pϕ(0,z0)=0\mathcal{P}\phi(0,z_0)=0. This implies that Pϕ(t,z0)=0\mathcal{P}\phi(t,z_0)=0 for all tt. Hence, applying P\mathcal{P} to both sides of (40) yields

∂∂tPz(t)=∂∂tPetLz0=PLz(t)+∫0tPk(t−s,z(s)) ds.(45)\frac{\partial}{\partial t}\mathcal{P}z(t)=\frac{\partial}{\partial t}\mathcal{P}e^{t\mathcal{L}}z_0=\mathcal{P}\mathcal{L}z(t)+\int_{0}^{t}\mathcal{P}k(t-s,z(s))\,\mathrm{d}s. \tag*{(45)}

Restricting to the first nn components, Pz(t)\mathcal{P}z(t) reduces to x(t)x(t) and Pk(t−s,z(s))\mathcal{P}k(t-s,z(s)) reduces to k(t−s,x(s))k(t-s,x(s)). Recalling that PLz(t)=Pf~(z(t))=f~(x(t),0)=f(x(t))\mathcal{P}\mathcal{L}z(t)=\mathcal{P}\tilde{f}(z(t))=\tilde{f}(x(t),0)=f(x(t)) completes the proof.

Proof of Proposition 2.1

Proof. From the definition of h(t)h(t) in (44), we obtain

h(t)=∫0tK(t−s;w)x(s) ds=∫−∞tK(t−s;w)x(s) ds=∫0∞K(s;w)x(t−s) ds(46)h(t)=\int_{0}^{t}K(t-s;w)x(s)\,\mathrm{d}s=\int_{-\infty}^{t}K(t-s;w)x(s)\,\mathrm{d}s=\int_{0}^{\infty}K(s;w)x(t-s)\,\mathrm{d}s \tag*{(46)}

where we used the fact that x(t)=0x(t)=0 for t<0t<0. Taking derivative on both sides of (44) yields

h′(t)=∫0∞K(s;w)x′(t−s) ds=∫0∞K(s;w)f~(x(t−s),h(t−s);A,η) ds=∫−∞tK(t−s;w)f~(x(s),h(s);A,η) ds=∫0tK(t−s;w)f~(x(s),h(s);A,η) ds,\begin{aligned} h'(t)=\int_{0}^{\infty}K(s;w)x'(t-s)\,\mathrm{d}s=\int_{0}^{\infty}K(s;w)\tilde{f}(x(t-s),h(t-s);A,\eta)\,\mathrm{d}s \\ &=\int_{-\infty}^{t}K(t-s;w)\tilde{f}(x(s),h(s);A,\eta)\,\mathrm{d}s=\int_{0}^{t}K(t-s;w)\tilde{f}(x(s),h(s);A,\eta)\,\mathrm{d}s, \end{aligned}

where we used the fact that x′(t)=f~(x(t),h(t);A,η)=0x'(t)=\tilde{f}(x(t),h(t);A,\eta)=0 for t<0t<0 in the last equality.

If K(t;w)=∑l=1LBle−CltK(t;w)=\sum_{l=1}^{L}B_l e^{-C_l t}, then we can take derivative of (44) and readily deduce that

h′=∑l=1L(Blx−Clh).h'=\sum_{l=1}^{L}(B_lx-C_lh).

Proof of Theorem 3

Proof. Let ζ∈Rm\zeta\in\mathbb{R}^{m} and ε≥0\varepsilon\ge0 be arbitrary. Consider the variation of any control θ\theta given by θε:=θ+εζ\theta_{\varepsilon} := \theta+ \varepsilon\zeta and denote mε(t)m_{\varepsilon}(t) the state process following (16b) with θε\theta_{\varepsilon}. Then we have

mε(t)=m(t)+εy(t)+o(ε),0≤t≤T,m_{\varepsilon}(t) = m(t) + \varepsilon y(t) + o(\varepsilon), \qquad0 \le t \le T,

where the first-order perturbation y(t)y(t) satisfies

{y′(t)=∇mg(m(t);θ)y(t)+∇θg(m(t);θ)ζ,0≤t≤T,y(0)=0.\begin{cases} y'(t) = \nabla_m g(m(t);\theta)y(t) + \nabla_\theta g(m(t);\theta)\zeta, & 0 \le t \le T,\\ y(0) = 0. \end{cases}

Therefore, the directional derivative of ℓ\ell defined in (16a) at θ\theta along the direction ζ\zeta is

ddεℓ(θε)∣ε=0=∫0T(∇mr(m(t),θ)y(t)+∇θr(m(t),θ)ζ) dt+p(T)y(T).(47)\left.\frac{\mathrm{d}}{\mathrm{d}\varepsilon}\ell(\theta_{\varepsilon})\right|_{\varepsilon=0} = \int_0^T \left(\nabla_m r(m(t),\theta)y(t) + \nabla_\theta r(m(t),\theta)\zeta\right)\,\mathrm{d}t + p(T)y(T). \tag*{(47)}

On the other hand, we have

(p⋅y)′=p′⋅y+p⋅y′=−(∇mg(m(t);θ)p(t)+∇mr(m(t),θ))⋅y+p⋅(∇mg(m(t);θ)Ty(t)+∇θg(m(t);θ)Tζ)=−∇mr(m(t),θ)Ty(t)+p(t)T∇θg(m(t);θ)ζ.\begin{aligned} (p\cdot y)' = p'\cdot y + p\cdot y' = -\left(\nabla_m g(m(t);\theta)p(t) + \nabla_m r(m(t),\theta)\right)\cdot y + p\cdot\left(\nabla_m g(m(t);\theta)^\mathsf{T}y(t) + \nabla_\theta g(m(t);\theta)^\mathsf{T}\zeta\right) \\ &= -\nabla_m r(m(t),\theta)^\mathsf{T}y(t) + p(t)^\mathsf{T}\nabla_\theta g(m(t);\theta)\zeta. \end{aligned}

Since y(0)=0y(0) = 0, we know

p(T)⋅y(T)=∫0T(−∇mr(θ,m(t))Ty(t)+p(t)T∇θg(m(t);θ)ζ) dt.(48)p(T)\cdot y(T) = \int_0^T \left(-\nabla_m r(\theta,m(t))^\mathsf{T}y(t) + p(t)^\mathsf{T}\nabla_\theta g(m(t);\theta)\zeta\right)\,\mathrm{d}t. \tag*{(48)}

Substituting (46) into (45) yields

ddεℓ(θε)∣ε=0={∫0T(∇θg(m(t);θ)Tp(t)+∇θr(θ,m(t))) dt}⋅ζ.\left.\frac{\mathrm{d}}{\mathrm{d}\varepsilon}\ell(\theta_{\varepsilon})\right|_{\varepsilon=0} = \left\{\int_0^T \left(\nabla_\theta g(m(t);\theta)^\mathsf{T}p(t) + \nabla_\theta r(\theta,m(t))\right)\,\mathrm{d}t\right\}\cdot\zeta.

As ζ\zeta is arbitrary, we know that the gradient ∇θℓ(θ)\nabla_\theta\ell(\theta) is as claimed in (20). Note that the integrand in (20) is

(∇θr(θ,m(t))+∇θg(m(t);θ)Tp(t))=∇θH(m(t),p(t);θ).\left(\nabla_\theta r(\theta,m(t))+\nabla_\theta g(m(t);\theta)^\mathsf{T}p(t)\right)=\nabla_\theta H(m(t),p(t);\theta).

Hence, at the optimal θ∗\theta^* of ℓ\ell, we have

ddεℓ(θε∗)∣ε=0=(∫0T∇θH(m∗(t),p∗(t);θ∗) dt)⋅ζ≥0,(49)\left.\frac{\mathrm{d}}{\mathrm{d}\varepsilon}\ell(\theta^*_{\varepsilon})\right|_{\varepsilon=0} = \left(\int_0^T \nabla_\theta H(m^*(t),p^*(t);\theta^*)\,\mathrm{d}t\right)\cdot\zeta\ge0, \tag*{(49)}

for all ζ∈Rm\zeta\in\mathbb{R}^{m}, from which we readily deduce the identity regarding HH at θ∗\theta^*.

Proof of Theorem 4

Proof. Let v∈Rnv \in\mathbb{R}^{n} be arbitrary and consider the variation uε:=u+εv+o(ε)u_{\varepsilon} := u+\varepsilon v+o(\varepsilon) of uu with ε>0\varepsilon>0. Let xε(t)x_{\varepsilon}(t) be the xx-part of the solution mε(t)m_{\varepsilon}(t) to (16b) with initial [uε;0][u_{\varepsilon};0]. Suppose xε(t)=x(t)+εw(t)+o(ε)x_{\varepsilon}(t)=x(t)+\varepsilon w(t)+o(\varepsilon) for all t∈[0,T]t\in[0,T] as ε→0\varepsilon\to0, then w(t)w(t) solves

{w′(t)=∇xgx(m(t);θ)w(t),0≤t≤T,w(0)=v.(50)\begin{cases} w'(t)=\nabla_x g_x(m(t);\theta)w(t), & 0\le t\le T,\\ w(0)=v. \tag*{(50)} \end{cases}

Note that (48) is a linear ODE of ww and thus has an analytic solution as follows:

w(T)=e∫0T∇xgx(m(t);θ) dtv.w(T)=e^{\int_0^T \nabla_x g_x(m(t);\theta)\,\mathrm{d}t}v.

Next, we compute the directional derivative of LL defined in (28) at u\mathbf{u} along direction v\mathbf{v}:

ddϵL(uϵ)∣ϵ=0=ddϵ(R(uϵ)−1⋅xϵ(T))∣ϵ=0=∇uR(u)⋅v−1⋅w(T)=(∇uR(u)−e∫0T∇xgx(x(t);θ)Tdt1)⋅v.\begin{aligned} \left.\frac{\mathrm{d}}{\mathrm{d}\epsilon}L(\mathbf{u}_{\epsilon})\right|_{\epsilon=0} &=\left.\frac{\mathrm{d}}{\mathrm{d}\epsilon}\left(\mathcal{R}(\mathbf{u}_{\epsilon})-\mathbf{1}\cdot\mathbf{x}_{\epsilon}(T)\right)\right|_{\epsilon=0}\\ &=\nabla_{\mathbf{u}}\mathcal{R}(\mathbf{u})\cdot\mathbf{v}-\mathbf{1}\cdot\mathbf{w}(T)\\ &=\left(\nabla_{\mathbf{u}}\mathcal{R}(\mathbf{u})-e^{\int_{0}^{T}\nabla_{\mathbf{x}}g_{\mathbf{x}}(\mathbf{x}(t);\theta)^{\mathsf{T}}\mathrm{d}t}\mathbf{1}\right)\cdot\mathbf{v}. \end{aligned}

As v\mathbf{v} is arbitrary, we know the gradient ∇uL(u)\nabla_{\mathbf{u}}L(\mathbf{u}) is

∇uL(u)=∇uR(u)−e∫0T∇xgx(x(t);θ)Tdt1.(51)\nabla_{\mathbf{u}}L(\mathbf{u})=\nabla_{\mathbf{u}}\mathcal{R}(\mathbf{u})-e^{\int_{0}^{T}\nabla_{\mathbf{x}}g_{\mathbf{x}}(\mathbf{x}(t);\theta)^{\mathsf{T}}\mathrm{d}t}\mathbf{1}. \tag*{(51)}

It is clear that the second term on the right hand side of (51) is s(T)\mathbf{s}(T) solved from

{s′(t)=∇xgx(x(t);θ)Ts(t),0≤t≤T,s(0)=1.(52)\begin{cases} \mathbf{s}'(t)=\nabla_{\mathbf{x}}g_{\mathbf{x}}(\mathbf{x}(t);\theta)^{\mathsf{T}}\mathbf{s}(t), \quad0\leq t\leq T,\\ \mathbf{s}(0)=\mathbf{1}. \tag*{(52)} \end{cases}

This completes the proof.

References

  1. [1]Á. Bodó, G. Y. Katona, and P. L. Simon. SIS epidemic propagation on hypergraphs. Bulletin of mathematical biology, 78(4):713–735, 2016.DOI
  2. [2]M. Boguñá and R. Pastor-Satorras. Epidemic spreading in correlated complex networks. Physical Review E, 66(4):047104, 2002.DOI
  3. [3]C. Borgs, M. Brautbar, J. Chayes, and B. Lucier. Maximizing social influence in nearly optimal time. Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, Dec 2013.arxiv.org/abs/1212.0884
  4. [4]Q. Cao, H. Shen, J. Gao, B. Wei, and X. Cheng. Popularity prediction on social platforms with coupled graph neural networks. In Proceedings of the 13th International Conference on Web Search and Data Mining, WSDM ’20, pages 70–78, New York, NY, USA, 2020. Association for Computing Machinery.arxiv.org/abs/1906.09032
  5. [5]R. T. Q. Chen, Y. Rubanova, J. Bettencourt, and D. Duvenaud. Neural ordinary differential equations. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems 31, pages 6571–6583. Curran Associates, Inc., 2018.arxiv.org/abs/1806.07366
  6. [6]A. J. Chorin, O. H. Hald, and R. Kupferman. Optimal prediction and the mori–zwanzig representation of irreversible processes. Proceedings of the National Academy of Sciences, 97(7):2968–2973, 2000.pubmed.ncbi.nlm.nih.gov/10737778
  7. [7]S.-N. Chow, X. Ye, H. Zha, and H. Zhou. Influence prediction for continuous-time information propagation on networks. Networks and Heterogeneous Media, 13(4):567–583, 2018.arxiv.org/abs/1512.05417
  8. [8]A. Clauset, C. Moore, and M. E. J. Newman. Hierarchical structure and the prediction of missing links in networks. Nature, 453(7191):98–101, May 2008.DOI
  9. [9]E. Cohen. Size-estimation framework with applications to transitive closure and reachability. Journal of Computer and System Sciences, 55(3):441–453, 1997.DOI
  10. [10]E. Cohen, D. Delling, T. Pajor, and R. F. Werneck. Sketch-based influence maximization and computation: Scaling up with guarantees. In Proceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Management, CIKM ’14, pages 629–638, New York, NY, USA, 2014. Association for Computing Machinery.
  11. [11]X. Dong, D. Thanou, M. Rabbat, and P. Frossard. Learning graphs from data: A signal representation perspective. IEEE Signal Processing Magazine, 36(3):44–63, 2019.DOI
  12. [12]N. Du, Y. Liang, M.-F. Balcan, and L. Song. Influence function learning in information diffusion networks. In Proceedings of the 31st International Conference on International Conference on Machine Learning - Volume 32, ICML’14, pages II–2016–II–2024. JMLR.org, 2014.pubmed.ncbi.nlm.nih.gov/25973445
  13. [13]N. Du, L. Song, M. Gomez-Rodriguez, and H. Zha. Scalable influence estimation in continuous-time diffusion networks. In Advances in Neural Information Processing Systems, pages 3147–3155, 2013.
  14. [14]N. Du, L. Song, M. Yuan, and A. J. Smola. Learning networks of heterogeneous influence. In F. Pereira, C. J. C. Burges, L. Bottou, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems 25, pages 2780–2788. Curran Associates, Inc., 2012.
  15. [15]M. Farajtabar, X. Ye, S. Harati, L. Song, and H. Zha. Multistage campaigning in social networks. In Advances in Neural Information Processing Systems, pages 4718–4726, 2016.arxiv.org/abs/1606.03816
  16. [16]M. Gomez-Rodriguez, D. Balduzzi, and B. Schölkopf. Uncovering the temporal dynamics of diffusion networks. In Proceedings of the 28th International Conference on International Conference on Machine Learning, ICML’11, pages 561–568, Madison, WI, USA, 2011. Omnipress.arxiv.org/abs/1105.0697
  17. [17]M. Gomez-Rodriguez, J. Leskovec, and A. Krause. Inferring networks of diffusion and influence. ACM Transactions on Knowledge Discovery from Data (TKDD), 5(4):21, 2012.
  18. [18]M. Gomez-Rodriguez, J. Leskovec, and B. Schölkopf. Structure and dynamics of information pathways in online media. CoRR, abs/1212.1464, 2012.arxiv.org/abs/1212.1464
  19. [19]M. Gomez Rodriguez and B. Schölkopf. Influence maximization in continuous time diffusion networks. In 29th International Conference on Machine Learning (ICML 2012), pages 1–8. International Machine Learning Society, 2012.arxiv.org/abs/1205.1682
  20. [20]M. Gomez-Rodriguez and B. Schölkopf. Submodular inference of diffusion networks from multiple trees. In ICML, 2012.arxiv.org/abs/1205.1671
  21. [21]M. Gomez-Rodriguez, L. Song, N. Du, H. Zha, and B. Schölkopf. Influence estimation and maximization in continuous-time diffusion networks. ACM Transactions on Information Systems (TOIS), 34(2):1–33, 2016.
  22. [22]A. Goyal, W. Lu, and L. V. Lakshmanan. Cell+: Optimizing the greedy algorithm for influence maximization in social networks. In Proceedings of the 20th International Conference Companion on World Wide Web, WWW ’11, pages 47–48, New York, NY, USA, 2011. Association for Computing Machinery.
  23. [23]J. Guldahl Rasmussen. Lecture Notes: Temporal Point Processes and the Conditional Intensity Function. arXiv e-prints, page arXiv:1806.00221, June 2018.arxiv.org/abs/1806.00221
  24. [24]Q. He, X. Wang, Z. Lei, M. Huang, Y. Cai, and L. Ma. Tifim: A two-stage iterative framework for influence maximization in social networks. Applied Mathematics and Computation, 354:338–352, 2019.DOI
  25. [25]S. He, H. Zha, and X. Ye. Network diffusions via neural mean-field dynamics. In Advances in Neural Information Processing Systems 33, 2020.arxiv.org/abs/2006.09449
  26. [26]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, pages 137–146. ACM, 2003.
  27. [27]D. Kempe, J. Kleinberg, and É. Tardos. Influential nodes in a diffusion model for social networks. In Automata, languages and programming, pages 1127–1138. Springer, 2005.DOI
  28. [28]D. Kingma and J. Ba. Adam: A method for stochastic optimization. International Conference on Learning Representations, Dec 2014.arxiv.org/abs/1412.6980
  29. [29]T. N. Kipf and M. Welling. Semi-supervised classification with graph convolutional networks. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24–26, 2017, Conference Track Proceedings. OpenReview.net, 2017.arxiv.org/abs/1609.02907
  30. [30]J. Leskovec, L. Backstrom, and J. Kleinberg. Meme-tracking and the dynamics of the news cycle. In Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’09, pages 497–506, New York, NY, USA, 2009. Association for Computing Machinery.DOI
  31. [31]J. Leskovec, D. Chakrabarti, J. Kleinberg, C. Faloutsos, and Z. Ghahramani. Kronecker graphs: An approach to modeling networks. The Journal of Machine Learning Research, 11:985–1042, 2010.
  32. [32]J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. VanBriesen, and N. Glance. Cost-effective outbreak detection in networks. In Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’07, pages 420–429, New York, NY, USA, 2007. Association for Computing Machinery.DOI
  33. [33]J. Leskovec, K. J. Lang, A. Dasgupta, and M. W. Mahoney. Statistical properties of community structure in large social and information networks. In Proceedings of the 17th International Conference on World Wide Web, WWW ’08, pages 695–704, New York, NY, USA, 2008. Association for Computing Machinery.
  34. [34]J. Leskovec and R. Sosič. Snap: A general-purpose network analysis and graph-mining library. ACM Transactions on Intelligent Systems and Technology (TIST), 8(1):1, 2016.arxiv.org/abs/1606.07550
  35. [35]C. K. Leung, A. Cuzzocrea, J. J. Mai, D. Deng, and F. Jiang. Personalized deepinf: Enhanced social influence prediction with deep learning and transfer learning. In 2019 IEEE International Conference on Big Data (Big Data), pages 2871–2880, 2019.
  36. [36]C. Li, J. Ma, X. Guo, and Q. Mei. Deepcas: An end-to-end predictor of information cascades. In Proceedings of the 26th international conference on World Wide Web, pages 577–586, 2017.
  37. [37]Y. Li, J. Fan, Y. Wang, and K.-L. Tan. Influence maximization on social graphs: A survey. IEEE Transactions on Knowledge and Data Engineering, 30(10):1852–1872, 2018.
  38. [38]Y. Liang, Z. Jiang, and Y. Zheng. Inferring traffic cascading patterns. In Proceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, SIGSPATIAL ’17, New York, NY, USA, 2017. Association for Computing Machinery.DOI
  39. [39]B. Lucier, J. Oren, and Y. Singer. Influence at scale: Distributed computation of complex contagion in networks. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’15, pages 735–744, New York, NY, USA, 2015. Association for Computing Machinery.
  40. [40]S. Manchanda, A. MITTAL, A. Dhawan, S. Medya, S. Ranu, and A. Singh. Gcomb: Learning budget-constrained combinatorial algorithms over billion-sized graphs. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 20000–20011. Curran Associates, Inc., 2020.
  41. [41]G. Mateos, S. Segarra, A. G. Marques, and A. Ribeiro. Connecting the dots: Identifying network structure via graph signal processing. IEEE Signal Processing Magazine, 36(3):16–43, May 2019.
  42. [42]J. C. Miller and I. Z. Kiss. Epidemic spread in networks: Existing methods and current challenges. Mathematical modelling of natural phenomena, 9(2):4, 2014.arxiv.org/abs/1403.1957
  43. [43]S. A. Myers and J. Leskovec. On the convexity of latent social network inference. In Proceedings of the 23rd International Conference on Neural Information Processing Systems - Volume 2, NIPS’10, pages 1741–1749, Red Hook, NY, USA, 2010. Curran Associates Inc.arxiv.org/abs/1010.5504
  44. [44]M. Newman. Networks: an introduction. Oxford University Press, 2010.DOI
  45. [45]H. T. Nguyen, T. P. Nguyen, T. N. Vu, and T. N. Dinh. Outward influence and cascade size estimation in billion-scale networks. Proc. ACM Meas. Anal. Comput. Syst., 1(1), June 2017.
  46. [46]G. Panagopoulos, F. Malliaros, and M. Vazirgiannis. Multi-task learning for influence estimation and maximization. IEEE Transactions on Knowledge and Data Engineering, pages 1–1, 2020.arxiv.org/abs/1904.08804
  47. [47]G. Panagopoulos, F. D. Malliaros, and M. Vazirgiannis. Influence maximization using influence and susceptibility embeddings. Proceedings of the International AAAI Conference on Web and Social Media, 14(1):511–521, May 2020.
  48. [48]R. Pastor-Satorras, C. Castellano, P. Van Mieghem, and A. Vespignani. Epidemic processes in complex networks. Reviews of modern physics, 87(3):925, 2015.
  49. [49]A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, A. Desmaison, A. Kopp, E. Yang, Z. DeVito, M. Raison, A. Tejani, S. Chilamkurthy, B. Steiner, L. Fang, J. Bai, and S. Chintala. PyTorch: An imperative style, high-performance deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d’Alché Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 8024–8035. Curran Associates, Inc., 2019.arxiv.org/abs/1912.01703
  50. [50]C. Qiao, Y. Shi, Y.-X. Diao, V. D. Calhoun, and Y.-P. Wang. Log-sum enhanced sparse deep neural network. Neurocomputing, 407:206–220, 2020.DOI
  51. [51]J. Qiu, J. Tang, H. Ma, Y. Dong, K. Wang, and J. Tang. Deepinf: Social influence prediction with deep learning. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 2110–2119, 2018.
  52. [52]Y. Rong, Q. Zhu, and H. Cheng. A model-free approach to infer the diffusion network from event cascade. In Proceedings of the 25th ACM International on Conference on Information and Knowledge Management, CIKM ’16, pages 1653–1662, New York, NY, USA, 2016. Association for Computing Machinery.DOI
  53. [53]F. D. Sahneh and C. Scoglio. Epidemic spread in human networks. In Decision and Control and European Control Conference (CDC-ECC), 2011 50th IEEE Conference on, pages 3008–3013. IEEE, 2011.arxiv.org/abs/1107.2464
  54. [54]Y. Tang, Y. Shi, and X. Xiao. Influence maximization in near-linear time: A martingale approach. In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, pages 1539–1554. ACM, 2015.DOI
  55. [55]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, SIGMOD ’14, pages 75–86, New York, NY, USA, 2014. Association for Computing Machinery.arxiv.org/abs/1404.0900
  56. [56]M. Vergeer, L. Hermans, and S. Sams. Online social networks and micro-blogging in political campaigning the exploration of a new campaign tool and a new campaign style. Party Politics, 19(3):477–501, 2013.
  57. [57]L. Wang, S. Ermon, and J. E. Hopcroft. Feature-enhanced probabilistic models for diffusion network inference. In Machine Learning and Knowledge Discovery in Databases, pages 499–514. Springer, 2012.DOI
  58. [58]J. Wortman. Viral marketing and the diffusion of trends on social networks. Technical Reports (CIS), page 880, 2008.
  59. [59]Z. Wu, S. Pan, F. Chen, G. Long, C. Zhang, and P. S. Yu. A comprehensive survey on graph neural networks. IEEE Transactions on Neural Networks and Learning Systems, pages 1–21, 2020.DOI
  60. [60]Y. Zang, G. Bao, X. Ye, H. Zha, and H. Zhou. A jump stochastic differential equation approach for influence prediction on heterogeneous networks. Communications in Mathematical Sciences, 18(8):2341–2359, 2020.
  61. [61]Y. Zhu, J. Xie, and Z. Chen. Predicting the popularity of micro-videos with multimodal variational encoder-decoder framework. arXiv preprint arXiv:2003.12724, 2020.DOI

Paper details

vlnc:W_tsgev8su
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents