Reconstructing Diffusion Networks from Incomplete Data

1 Introduction

The topology of a diffusion network provides an explicit view for the influence relationships between network nodes, and is crucial for revealing the intrinsic mechanisms of diffusion dynamics. In practice, diffusion network topologies are often not naturally accessible, and need to be reconstructed based on diffusion results observed from history [Gan et al., 2021].

To reconstruct the topology of a diffusion network, most existing approaches rely on the assumption that nodes infected sequentially within a short time interval are more likely to possess influence relationships. Therefore, these approaches demand not only the eventual infection statuses of nodes, but also the exact times (called cascades) when infections occur, and aim to find an optimal diffusion network topology that maximizes the likelihood of the cascades [Gomez-Rodriguez et al., 2010; Myers and Leskovec, 2010; Gomez-Rodriguez et al., 2011; Gomez-Rodriguez and Sch¨olkopf, 2012; Du et al., 2012; Gomez-Rodriguez et al., 2013; Daneshmand et al., 2014; Wang et al., 2014; Pouget-Abadie and Horel, 2015;

Narasimhan et al., 2015; Rong et al., 2016; Kalimeris et al., 2018]. Nevertheless, in many real-world settings, such as the spread of epidemics and viral marketing campaigns, monitoring the entire diffusion process to obtain precise cascades is expensive and time consuming. A few existing approaches try to reconstruct diffusion networks with only the eventual infection statuses of nodes [Amin et al., 2014; Huang et al., 2019; Han et al., 2020; Huang et al., 2021], which are more easily accessible than cascades in most cases.

Whether the existing approaches use cascades or the eventual infection statuses of nodes, they usually assume that the observed data are complete. Unfortunately, this assumption often fails to hold in practice [Gan et al., 2021]. For example, it is difficult to collect infection situations of all individuals during the spread of epidemics because of population mobility and limited medical resources. It is also hard to guarantee that every respondent provides feedback in viral marketing campaigns. To deal with incomplete observed data, a simple and straightforward strategy is replacing each missing data with its corresponding expected value in the observed part [Sefer and Kingsford, 2015], under the assumption that the missing and observed data have the same probability distribution. However, this strategy has no accuracy guarantee, and may result in a severe bias for the estimate of missing data. To minimize bias, a few studies utilize constrained optimization to handle incomplete observed data, but most of them aim to learn either the strengths of influence relationships [Lokhov, 2016; Wilinski and Lokhov, 2020] or influence functions [He et al., 2016] when the topology of diffusion network is given. Only one work aims to reconstruct diffusion network topologies with incomplete observed data [Gan et al., 2021]. Nonetheless, this work tries to maximize a relaxed objective function rather than the original objective function, and thus can not guarantee to obtain the optimal solution or a local optimal solution of the original problem.

Aiming at an accurate solution for diffusion network reconstruction with incomplete observations of node infection statuses, we propose LIDO (Learning from Incomplete Diffusion Observations) algorithm. It consists of three iterative steps, i.e., (1) inferring the topology of target diffusion network based on the observed node infection statuses and estimated values for unobserved node infection statuses, (2) jointly learning the optimal infection propagation probabilities between adjacent nodes in current inferred topology and the corresponding probability distribution of each unobserved node infection status, that are most likely to generate the observed data, and (3) updating the estimate of unobserved infection statuses by sampling values from the latest learned probability distributions. LIDO repeats these three steps until the inferred topology converges to a stable solution.

The remainder of the paper is organized as follows. We first present our problem statement, and then introduce our proposed LIDO algorithm, followed by reporting experimental results and our findings before concluding the paper.

2 Problem Statement

A diffusion network is represented as a directed graph G = (V,E), where V = {v1, ..., vn} is the set of n nodes in the network, and E is the set of directed edges (i.e., influence relationship). A directed edge (vj, vi) ∈ E from a parent node vj ∈ V to a child node vi ∈ V indicates that when vj is infected and vi is uninfected, vj will infect vi with a certain probability pji, which is known as infection propagation probability. We assume that the diffusion processes on G follow the Independent Cascade (IC) model [Kempe et al., 2003], in which each infected parent node tries to infect each of its uninfected children with corresponding infection propagation probability independently. This assumption is commonly used in existing approaches, and we would like to point out that our proposed algorithm can be also extended to other propagation models such as the linear threshold model.

In the problem of diffusion network reconstruction, the node set V is given, while the topology (i.e., the directed edge set E) of target diffusion network is unknown, so are the infection propagation probabilities w.r.t. the topology. To reconstruct the diffusion network, a set S of diffusion results observed from a number of historical diffusion processes on the network is required. In this paper, we assume that the diffusion results contain only the final infection statuses of nodes in each diffusion process, i.e., S = {sℓi | i ∈ {1, ..., n}, ℓ ∈ {1, ..., β}}, where sℓi ∈ {0, 1} is the final infection status of node vi in the ℓ-th diffusion process, and β is the number of historical diffusion processes. Furthermore, we focus on a complex yet more realistic situation, i.e., partial data in S are unobserved. Let Sobs and Smis denote the observed part and unobserved part in S, respectively, then our problem statement can be formulated as follows.

Given: partial observations Sobs of node infection statuses observed on a diffusion network G at the end of β historical diffusion processes.

Infer: the unknown edge set E of diffusion network G.

3 The LIDOAlgorithm

To reconstruct the topology of G with partial observations Sobs , LIDO performs the following three steps iteratively, namely (1) inferring the topology with Sobs and estimated values ˆ Smis for Smis , (2) learning the optimal infection propagation probabilities and corresponding probability distributions of Smis w.r.t. the current inferred topology, and (3) updating ˆ Smis by sampling from the learned probability distribution. The details of these steps as well as a complexity analysis for LIDO are provided in what follows.

Topology inference. In general, the goal of diffusion network reconstruction with node infection statuses S is to find an optimal directed edge set E∗ that satisfies the following requirement.

Nonetheless, in our problem setting, the node infection statuses is incomplete, containing only partial observations Sobs . To estimate P(E | S) with less bias, we can repeatedly sample Smis to obtain a set of samples of unobserved data {ˆ Smis 1 , ..., ˆ Smis m }, where m is the number of sampling rounds. Then, we can obtain a set of samples of complete data {ˆ S1, ..., ˆ Sm}, in which the r-th sample ˆ Sr consists of Sobs and ˆ Smis r , i.e., ˆ Sr = (Sobs , ˆ Smis r ). If the sampling is sufficient and follows the underlying probability distributions of unobserved data, then

Let { ˆ S(t) 1 , ..., ˆ S(t) m } denote the sample set of complete data sampled by LIDO after the t-th iteration, then in the (t+1)-th iteration, the task of topology inference is to find a directed edge set E(t+1) that satisfies the following requirement.

Note that the problem in Eq. (3) is equivalent to reconstructing diffusion network topologies from only the complete data of final node infection statuses. Existing approaches to this problem, such as TENDS [Han et al., 2020], can be utilized to infer E(t+1) . Therefore, how to complete the data through sampling is essential for topology inference.

Learning probability distribution for sampling. After inferring E(t+1) with {ˆ S(t) 1 , ..., ˆ S(t) m }, the subsequent task is to find the optimal infection propagation probabilities {pji | (vj, vi) ∈ E(t+1) } and the corresponding probability distributions of unobserved data Smis that are most likely to generate the observed data Sobs . Then, by sampling Smis from the learned probability distributions, we can obtain an updated sample set of complete data { ˆ S(t+1) 1 , ..., ˆ S(t+1) m } for the next iteration of topology inference.

According to IC model, when the infection status sℓi of node vi in the ℓ-th diffusion process is observed and sℓi = 1, the likelihood that the infection of vi is caused by any of its parent nodes is 1- ∏vj∈Fi (1-pjisℓj ), where Fi refers to the set of parent nodes of vi; when sℓi is observed and sℓi = 0, the likelihood that none of the parent nodes of vi has successfully infected vi can be estimated as ∏vj∈Fi (1 - pjisℓj ).

When sℓi is unobserved, i.e., sℓi ∈ Smis , we regard sℓi with the probability that Xℓ i = 1, i.e., sℓi = P(Xℓ i = 1 | Sobs ), where Xℓ i ∈ {0, 1} is the infection status variable of vi in the ℓ-th diffusion process. In other words, we substitute the unknown sℓi with its expectation P(Xℓ i = 1 | Sobs ).

Then, the likelihood of the observed data Sobs can be written as ∏βℓ=1 ∏sℓi ∈Sobs P (Xℓ i = sℓi ) with constraints:

where F (t+1) i refers to the set of parent nodes of node vi in current inferred topology E(t+1) .

Then, we can learn the optimal {pji | (vj, vi) ∈ E(t+1) } and corresponding {sℓi ∈ Smis } by solving the following optimization problem.

where

Lagrange multiplier method can be used to solve the above problem, and the corresponding Lagrangian is as follows.

where λℓi is the Lagrange multiplier corresponding to constraint cℓi = 0 (sℓi ∈ Smis ).

Given this Lagrangian L, its derivative w.r.t. pji is

and the derivative of L w.r.t. sℓj ∈ Smis is

Then, solving the optimization problem in Eq. (5) can be transformed into solving the following equations.

Specifically, starting with randomly initialized pji ∈ (0, 1), Eq. (10) can be solved by the following three iterative steps:

Step 1. Substituting current pji into Eq. (6), we have a system of equations w.r.t. sℓi ∈ Smis :

As each historical diffusion process is independent to each other, for each ℓ ∈ {1, ..., β}, we have a system of equations:

To solve Eq. (12), if the condition that for each vj ∈ F (t+1) i , sℓj is observed or has been calculated already, holds for node vi in the ℓ-th diffusion process, then the corresponding sℓi ∈ Smis can be calculated as

We repeatedly find which nodes in the ℓ-th diffusion process satisfy the above condition, and calculate corresponding sℓi by Eq. (13), until no node can be found. If there are still some unobserved sℓi left that cannot be directly calculated by Eq. (13), it indicates that there exist cyclic dependencies among the calculation of these unobserved sℓi . Without loss of generality, let sℓ1 , ..., sℓk be this kind of unobserved infection statuses, then we can calculate their values jointly by solving the following equations.

The above Eq. (14) is a polynomial system of equations w.r.t. sℓ1 , ..., sℓk , of which the numerical solution can be efficiently obtained by existing tools, such as the fsolve and root functions in SciPy package for Python.

Step 2. Substituting current pji and sℓj into equations

∂L ∂sℓj = 0 (sℓj ∈ Smis ), we have a system of equations w.r.t. the Lagrange multipliers λℓi . According to Eq. (9), this system of

equations is linear and can be solved directly.

Step 3. Substituting current pji, sℓj and λℓi into Eq. (8), we have the latest gradient ∂L ∂pji of the Lagrangian L w.r.t. pji, then we update pji with the latest gradient as follows.

where θ(τ) > 0 is the updating step size used in the τ-th iteration of Steps 1-3.

Note that using variable step sizes helps strike a trade-off between convergence guarantee and speed. Large step sizes are first adopted to quickly reach the neighborhood of the optimum; then, small steps are adopted to avoid overshooting. If the optimum is static, the gradient descent approach is guaranteed to converge to a stationary point when the step sizes satisfy the relationship below [Kushner and Yin, 2003].

Inspired by this, we set θ(τ) = θ0 √τ , where θ0 = 0.001 works as the initial step size.

After learning the optimal {pji | (vj, vi) ∈ E(t+1) } and corresponding {sℓi ∈ Smis }, LIDO executes sampling based on the learned {sℓi ∈ Smis }, which describes the probability distribution of unobserved data.

Complexity analysis. In topology inference, performing TENDS algorithm on complete data sampled by LIDO takes about O(mβn2 ) time, where n is the number of nodes in target diffusion network, β is the number of the historical diffusion processes, and m is the number of sampling rounds for unobserved data.

To learn probability distribution for sampling, the most computationally expensive process is solving the equations Eq. (10) by our proposed three steps. The time complexities of the three steps are all bounded by O(βn3 ), and thus learning probability distribution takes about O(τβn3 ) time, where τ is the iteration number of the three steps.

In brief, the time complexity of LIDO is O(tmβn2 + tτβn3 ), where t refers to the number of iterations of LIDO.

4 Experimental Evaluation

In this section, we first introduce experimental setup, and then evaluate LIDO on synthetic and real-world networks with simulated infection data by investigating the effects of network size, network's average degree, unobserved data ratio, the amount of diffusion processes, and the iterations of LIDO on the accuracy and running time performance of LIDO. Furthermore, we also carry out a case study on a realworld network with real infection data. All algorithms in the experiments are implemented in Python, running on a desktop PC with Intel Core i3-6100 CPU at 3.70GHz and 8GB RAM.

Experimental setup. (1) Network: We adopt LFR benchmark graphs [Lancichinetti et al., 2008] as the synthetic networks, and generate two series of LFR benchmark graphs with properties summarized in Table 1. In addition, we adopt two commonly used real-world networks: NetSci [Newman, 2006], a co-authorship network containing 379 scientists and 1602 co-authorships, and DUNF [Wang et al., 2014], a microblogging network containing 750 users and 2974 following relationships.

(2) Infection data: The infection status results S or cascades can be obtained by simulating β times of diffusion processes on each network with randomly selected initially infected nodes in each simulation (the ratio of initially infected nodes is 15%). In each diffusion process, each infected node tries to infect its uninfected child nodes with an infection propagation probability that follows a Gaussian distribution with mean of 0.3 and standard deviation of 0.05, to make about 95% of infection propagation probabilities within a range from 0.2 to 0.4 [Gan et al., 2021]. We randomly remove partial data from S as the unobserved data Smis (γ denotes the unobserved data ratio), and use the remaining observation data Sobs for diffusion network reconstruction.

(3) Performance criterion: To evaluate the accuracy performance of LIDO algorithm, we report the F-score (the harmonic mean of precision and recall) of its inferred directed edges, which is computed as F-score = 2·Precision·Recall Precision+Recall , where Precision = NTP NTP+NFP , Recall = NTP NTP+NFN , NTP is the number of the true edges that are correctly inferred by the algorithm; NFP is the number of the wrong inferred edges that are not in the real network; and NFN is the number of the true edges that are not correctly inferred by the algorithm.

(4) Benchmark algorithms: We compare LIDO with a classical cascade-based approach MulTree [Gomez-Rodriguez and Sch¨olkopf, 2012], a high-performance infection statusbased approach TENDS [Han et al., 2020], and POIND [Gan et al., 2021] which is the only existing approach to diffusion network reconstruction with incomplete data. In LIDO, the number m of sampling round is set to 6, the maximum number t of iterations is set to 5, and the stop condition for updating pji in each iteration is that the variation of each pji is less than 0.01. As TENDS requires complete data, we complete the Sobs with the following ad-hoc method for them: we estimate the average infection probability of each node in Sobs , and sample for the unobserved data 6 times based on the average infection probabilities.

Effect of diffusion network size. To study the effect of diffusion network size, we adopt five synthetic networks, LFR1-5, whose sizes vary from 100 to 300. We simulate 200 times of diffusion processes on each network (β = 200), and randomly remove 15% of infection status observations as unobserved data (γ = 0.15).

Fig. 1 illustrates the F-score and running time of each algorithm, from which we can have the following observations:

(1) LIDO outperforms the three benchmark algorithms in terms of accuracy. (2) A larger diffusion network size tends to degrade the accuracy of MulTree, while the accuracy of LIDO, TENDS, and POIND are reasonably insensitive to the size of diffusion network. TENDS's insensitivity to diffusion network size has also been verified in existing study [Han et al., 2020]. This is one of the reasons for why LIDO adopts TENDS for topology inference with completed data. (3) The running time of each tested algorithm tends to increase with the growth of diffusion network size, and TENDS is faster than LIDO as there is no iteration in TENDS.

Effect of average degree of diffusion network. To study the effect of the average degree of diffusion network, we test the algorithms on five synthetic networks, LFR6-10, whose average degree of each node varies from 2 to 6. We simulate 200 times of diffusion processes on each network (β = 200), and randomly remove 15% of infection status observations as unobserved data (γ = 0.15).

Fig. 2 illustrates the F-score and running time of each algorithm, from which we can have the following observations: (1) Among the tested algorithms, LIDO has the best accuracy. (2) With the increase of the average degree, the accuracy of LIDO decreases slightly. This is because a greater average degree often brings more complicated influence relationships between nodes, and thus adds complexity to diffusion network reconstruction. (3) The running time of each tested algorithm increases with the growth of average degree.

Effect of unobserved data ratio. To study the effect of the ratio of unobserved data, we test the algorithms on two realworld networks, NetSci and DUNF, with β = 200, varying unobserved data ratio γ from 0 to 0.2.

Fig. 3 illustrates the F-score and running time of each algorithm, from which we can have the following observations: (1) Compared with MulTree and POIND, LIDO often achieves higher accuracy. (2) LIDO and TENDS have the same accuracy in the setting of γ = 0; when there is more unobserved data, LIDO shows a greater advantage on accuracy than TENDS. (3) The increase of unobserved data ratio has a rather mild effect on the running time of MulTree and TENDS, but results in significantly longer running time for LIDO and POIND. This is because LIDO and POIND require longer running time to infer more unobserved data, while MulTree and TENDS use completed data directly.

Effect of amount of diffusion processes. To study the effect of the amount β of diffusion processes, we test the algorithms on NetSci and DUNF with different β, which varies from 100 to 300. In the diffusion result obtained with each β, we randomly remove 15% of infection status observations as unobserved data (γ = 0.15).

Fig. 4 illustrates the F-score and running time of each algorithm, from which we can have the following observations: (1) With more diffusion processes, the tested algorithms obtain more accurate results, and LIDO leads its competitors in accuracy. (2) To analyze the cascades observed frommore diffusion processes, MulTree requires more running time, while a greater amount of diffusion processes does not always increase the running time of LIDO, TENDS and POIND.

Effect of iterations of LIDO. To study the effect of the iterations of LIDO, we test LIDO on NetSci and DUNF with β = 200 and γ = 0.15, and report the accuracy and accumulated running time of LIDO at the end of each iteration.

Fig. 5(a) & (b) illustrate the testing result, from which we can observe that (1) LIDO shows a fast convergence property; (2) more iterations result in longer running time for LIDO.

The main reason behind the fast convergence property is that LIDO can accurately estimate the values of unobserved data. To verify this point, Fig. 5(c) illustrates the accuracy (i.e., the rate of correct estimated values) of LIDO's estimated values for unobserved data Smis in each iteration, from which we can observe that the accuracy of estimated values increases and converges to a stable level quickly. Another important reason is due to the effectiveness of LIDO on revealing the underlying infection propagation probabilities, which helps LIDO to estimate the probability distribution and the values of of unobserved data in turn. To demonstrate this effectiveness, Fig. 5(d) illustrates the MAE (Mean Absolute Error) of infection propagation probabilities {pji | (vj, vi) ∈ E(t+1) } learned in the first iteration of LIDO (i.e., t = 1). A lower MAE indicates a higher accuracy. From Fig. 5(d), we can observe that the accuracy of learned pji is significantly improved by iteratively performing our proposed learning approach. Similar results can be observed when t > 1.

Case study on real infection data. To verify the effectiveness of LIDO in real scenarios, we adopt a commonly used real-world data set MemeTracker (http://memetracker.org), which contains more than 96 million news articles and blogs from 1 million sources over a period of nine months from August 1 2008 till April 31 2009.

As the ground truth of network topology is unknown on MemeTracker data set, we generate a MemeTracker network having 1000 media sites and blogs with 4000 directed hyperlinks as follows. We first extract the top 1000 media sites and blogs with the largest number of documents as 1000 network nodes, and then add directed edge (vi, vj) if a post on network node vi linked to a post on a network node vj. Hyperlinks between blog posts can be used to trace diffusion processes [Leskovec et al., 2007]. When a blog publishes a piece of information and uses hyperlinks to refer to posts published by other blogs, we consider this kind of activities as events of information propagation. By tracing these information propagation events between the nodes of our generated MemeTracker network, we identify 13000 infection results S and cascades of corresponding diffusion processes. Furthermore, to create incomplete data, we randomly remove partial data from S as the unobserved data Smis (the unobserved data ratio γ varies from 0 to 0.2), and use the remaining observation data Sobs for diffusion network reconstruction.

Fig. 6 illustrates the F-score and running time of each tested algorithm, from which we can have the following observations: (1) A greater unobserved data ratio often degrades the accuracy of each tested algorithm, while LIDO leads its competitors in accuracy. (2) The increase of unobserved data ratio results in longer running time for LIDO, TENDS and POIND, while having a rather mild effect on the running time of MulTree. (3) MulTree tends to be relatively more efficient than the other tested algorithm. This is because most of the diffusion processes identified from the MemeTracker data set start from a single media or blog site, with tree-shape propagation paths, which are more applicable to MulTree.

5 Conclusion

In this paper, we have investigated the problem of how to reconstruct the topology of a diffusion network with incomplete observations of node infection statuses, and presented an effective approach called LIDO to solve this problem in an iterative way. In each iteration, LIDO infers the topology of target diffusion network based on observed data and estimated values of unobserved data, and learns the optimal infection propagation probabilities and corresponding probability distributions of unobserved data w.r.t. the inferred topology. The learned probability distributions are used by LIDO to update the estimate of unobserved data for the next iteration of topology inference. Extensive experimental results on both synthetic and real-world networks show that LIDO can properly handle incomplete observation data and reconstruct diffusion network topologies accurately.

Acknowledgments

This work was supported in part by NSFC Grants 61976163 and 61902284. Ting Gan is the corresponding author.