Learning Influence Functions from Incomplete Observations
We study the problem of learning influence functions under incomplete observations of node activations. Incomplete observations are a major concern as most (online and real-world) social networks are not fully observable. We establish both proper and improper PAC learnability of influence functions under randomly missing observations. Proper PAC learnability under the Discrete-Time Linear Threshold (DLT) and Discrete-Time Independent Cascade (DIC) models is established by reducing incomplete observations to complete observations in a modified graph. Our improper PAC learnability result applies for the DLT and DIC models as well as the Continuous-Time Independent Cascade (CIC) model. It is based on a parametrization in terms of reachability features, and also gives rise to an efficient and practical heuristic. Experiments on synthetic and real-world datasets demonstrate the ability of our method to compensate even for a fairly large fraction of missing observations.
1 r. Random observation loss naturally occurs when crawling data from social media, where rate restrictions are likely to affect all observations equally.
We establish both proper and improper PAC learnability of influence functions under incomplete observations for two popular diffusion models: the Discrete-Time Independent Cascade (DIC) and Discrete-Time Linear Threshold (DLT) models. In fact, randomly missing observations do not even significantly increase the required sample complexity. The result is proved by interpreting the incomplete observations as complete observations in a transformed graph, The PAC learnability result implies good sample complexity bounds for the DIC and DLT models. However, the PAC learnability result does not lead to an efficient algorithm, as it involves marginalizing a large number of hidden variables (one for each node not observed to be active).
Towards designing more practical algorithms and obtaining learnability under a broader class of diffusion models, we pursue improper learning approaches. Concretely, we use the parameterization of Du et al. [3] in terms of reachability basis functions, and optimize a modified loss function suggested by Natarajan et al. [17] to address incomplete observations. We prove that the algorithm ensures improper PAC learning for the DIC, DLT and Continuous-Time Independent Cascade (CIC) models. Experimental results on synthetic cascades generated from these diffusion models and real-world cascades in the MemeTracker dataset demonstrate the effectiveness of our approach. Our algorithm achieves nearly a 20% reduction in estimation error compared to the best baseline methods on the MemeTracker dataset.
Several recent works also aim to address the issue of missing observations in social network analysis, but with different emphases. For example, Chierichetti et al. [2] and Sadikov et al. [21] mainly focus on recovering the size of a diffusion process, while our task is to learn the influence functions from several incomplete cascades. Myers et al. [15] mainly aim to model unobserved external influence in diffusion. Duong et al. [6] examine learning diffusion models with missing links from complete observations, while we learn influence functions from incomplete cascades with missing activations. Most related to our work are papers by Wu et al. [23] and simultaneous work by Lokhov [13]. Both study the problem of network inference under incomplete observations. Lokhov proposes a dynamic message passing approach to marginalize all the missing activations, in order to infer diffusion model parameters using maximum likelihood estimation, while Wu et al. develop an EM algorithm. Notice that the goal of learning the model parameters differs from our goal of learning the influence functions directly. Both [13] and [23] provide empirical evaluation, but do not provide theoretical guarantees.
The authors consider the problem of PAC-learning the influence function in cascade models under a incomplete observation model. For each observed cascade, only the initial seeds and random subset of final active nodes are observed---specifically, each active node is observed as being active independently with probability 1-mu. The specific learning goal is to estimate the marginal probabilities of each node being activated given any source set S.  The paper considers both proper PAC learning (the estimated influence function corresponds to an actual diffusion model) and improper PAC learning (the estimated influence function is parameterized differently). For proper learning, they extend results of [14] to the case of incomplete observations. The main idea is to reduce (by a fairly straightforward reduction) the problem of learning with incomplete cascades to the problem of learning with complete observations in a modified graph (and with modified training cascades). They show that influence functions are PAC-learnable with a sample complexity that increases by a factor of 1/(1-mu)^4 over that of learning with complete cascades.   However, proper PAC learning is computationally intractable, so they instead consider improper learning.  For improper learning, they extend the results of [2] for "model-free" learning of influence functions to the case of incomplete observations. In particular, the influence function is estimated by approximating the reverse reachable sets of each node v as a mixture of sets sampled from some distribution q that approximates the true one. The results are parameterized in terms of how good an approximation q is. The sample complexity increases by a factor of 1/(1-mu)^2 compared with learning with complete cascades. They also improve the analysis of [2] to show a better dependence (logarithmic instead of polynomial) on the parameter C that quantifies how good an approximation q is.   Experiments compare with a number of different baselines to show that their model-free method performs much better with an increasing fraction of missing observations. 
In general, the paper is extremely well written and technically sound.  In terms of significance and impact, I appreciate the general line of work of directly estimating influence functions from pairs of seed and activation sets. This seems a lot more practically applicable than related problems of estimating true parameters or recovering the edges of an unobserved graph because it can be applied directly in a predictive setting.   The specific high-level problem tackled by this paper---of estimating influence functions when some fraction of observations are missing---is relevant but not obviously a problem of huge impact. However, the problem is addressed very nicely. Two previous results are extended to the new observation model (refs [2,14]), the latter using another relatively recent result about learning with noisy labels (ref [15]). Each of the two major results in this paper required careful adaptation (and not just reuse) of the previous results.   The experiments were thorough and showed improvements compared with a number of baselines.  A limitation of the paper are the assumptions that: (1) the missing probability mu is known and, (2) observations are missing at random. While this is a reasonable place to start, the paper would be stronger if the authors acknowledge and discuss these limitations (e.g. lines 39-41 argue in favor of the assumption but do not acknowledge limitations).  I also suggest that the tradeoffs in Section 4 be clarified. It is unclear leading up to Theorem 4 where the distribution q for generating features comes from, and whether the final choice (lines 264-265: "approximate \beta_T^* with the product of marginal distributions") carries any theoretical guarantee. The footnote suggests that C may be exponential in the number of nodes, but Theorem 4 asserts that on the order of C^2 features are required for the theoretical guarantee. How big is C in practice? Is it known? A better discussion of these issues is warranted.  Minor comments:  I believe these two references are also relevant. [1] estimates diffusion parameters with missing data. [2] recovers the edges of a graph from activation-only cascades.  [1] Parameter Learning for Latent Network Diffusion. Wu, Kumar, Sheldon, Zilberstein. IJCAI 2013.   [2] Learning form contagion (without timestamps). Amin, Heidari, Kearns, ICML 2014.   In Section 2.1, clarify whether G and {w_{uv}} are known or unknown.  In Theorems 1 and 2, it is somewhat confusing that the dependence of the sample complexity on delta is suppressed by the \tilde{O} notation. From the previous discussion, I expected to see delta in these expressions.  The assertion in Lines 180-181 seems redundant with the previous equation. Isn't this case (non-seed nodes) already included in the statement of Eq. (1)?  Line 195: I suggest saying the "computing the objective function" and not "writing down the objective function" is hard.  For the experiments, one other baseline to consider is a naive adjustment to the predictions of the parametric models (CIC, DIC, etc.) that multiplies the predicted influence by 1/(1-mu). This would correct for missingness in the prediction phase but not the training phase. Was this already considered?