Scalable Influence Estimation Without Sampling
- URL: http://arxiv.org/abs/1912.12749v1
- Date: Sun, 29 Dec 2019 22:15:58 GMT
- Title: Scalable Influence Estimation Without Sampling
- Authors: Andrey Y. Lokhov, David Saad
- Abstract summary: In a diffusion process on a network, how many nodes are expected to be influenced by a set of initial spreaders?
Here, we suggest an algorithm for estimating the influence function in popular independent model based on a scalable dynamic message-passing approach.
We also provide dynamic message-passing equations for a version of the linear threshold model.
- Score: 9.873635079670091
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In a diffusion process on a network, how many nodes are expected to be
influenced by a set of initial spreaders? This natural problem, often referred
to as influence estimation, boils down to computing the marginal probability
that a given node is active at a given time when the process starts from
specified initial condition. Among many other applications, this task is
crucial for a well-studied problem of influence maximization: finding optimal
spreaders in a social network that maximize the influence spread by a certain
time horizon. Indeed, influence estimation needs to be called multiple times
for comparing candidate seed sets. Unfortunately, in many models of interest an
exact computation of marginals is #P-hard. In practice, influence is often
estimated using Monte-Carlo sampling methods that require a large number of
runs for obtaining a high-fidelity prediction, especially at large times. It is
thus desirable to develop analytic techniques as an alternative to sampling
methods. Here, we suggest an algorithm for estimating the influence function in
popular independent cascade model based on a scalable dynamic message-passing
approach. This method has a computational complexity of a single Monte-Carlo
simulation and provides an upper bound on the expected spread on a general
graph, yielding exact answer for treelike networks. We also provide dynamic
message-passing equations for a stochastic version of the linear threshold
model. The resulting saving of a potentially large sampling factor in the
running time compared to simulation-based techniques hence makes it possible to
address large-scale problem instances.
Related papers
- Deep Ensembles Meets Quantile Regression: Uncertainty-aware Imputation
for Time Series [49.992908221544624]
Time series data often exhibit numerous missing values, which is the time series imputation task.
Previous deep learning methods have been shown to be effective for time series imputation.
We propose a non-generative time series imputation method that produces accurate imputations with inherent uncertainty.
arXiv Detail & Related papers (2023-12-03T05:52:30Z) - Probabilistic Unrolling: Scalable, Inverse-Free Maximum Likelihood
Estimation for Latent Gaussian Models [69.22568644711113]
We introduce probabilistic unrolling, a method that combines Monte Carlo sampling with iterative linear solvers to circumvent matrix inversions.
Our theoretical analyses reveal that unrolling and backpropagation through the iterations of the solver can accelerate gradient estimation for maximum likelihood estimation.
In experiments on simulated and real data, we demonstrate that probabilistic unrolling learns latent Gaussian models up to an order of magnitude faster than gradient EM, with minimal losses in model performance.
arXiv Detail & Related papers (2023-06-05T21:08:34Z) - Efficient distributed representations beyond negative sampling [4.5687771576879594]
This article describes an efficient method to learn distributed representations, also known as embeddings.
We show that the sotfmax normalization constants can be estimated in linear time, allowing us to design an efficient optimization strategy.
arXiv Detail & Related papers (2023-03-30T15:48:26Z) - Approximate Gibbs Sampler for Efficient Inference of Hierarchical Bayesian Models for Grouped Count Data [0.0]
This research develops an approximate Gibbs sampler (AGS) to efficiently learn the HBPRMs while maintaining the inference accuracy.
Numerical experiments using real and synthetic datasets with small and large counts demonstrate the superior performance of AGS.
arXiv Detail & Related papers (2022-11-28T21:00:55Z) - FaDIn: Fast Discretized Inference for Hawkes Processes with General
Parametric Kernels [82.53569355337586]
This work offers an efficient solution to temporal point processes inference using general parametric kernels with finite support.
The method's effectiveness is evaluated by modeling the occurrence of stimuli-induced patterns from brain signals recorded with magnetoencephalography (MEG)
Results show that the proposed approach leads to an improved estimation of pattern latency than the state-of-the-art.
arXiv Detail & Related papers (2022-10-10T12:35:02Z) - Sampling Approximately Low-Rank Ising Models: MCMC meets Variational
Methods [35.24886589614034]
We consider quadratic definite Ising models on the hypercube with a general interaction $J$.
Our general result implies the first time sampling algorithms for low-rank Ising models.
arXiv Detail & Related papers (2022-02-17T21:43:50Z) - Scaling Structured Inference with Randomization [64.18063627155128]
We propose a family of dynamic programming (RDP) randomized for scaling structured models to tens of thousands of latent states.
Our method is widely applicable to classical DP-based inference.
It is also compatible with automatic differentiation so can be integrated with neural networks seamlessly.
arXiv Detail & Related papers (2021-12-07T11:26:41Z) - Fast Bayesian Estimation of Spatial Count Data Models [0.0]
We introduce Variational Bayes (VB) as an optimisation problem instead of a simulation problem.
A VB method is derived for posterior inference in negative binomial models with unobserved parameter and spatial dependence.
The VB approach is around 45 to 50 times faster than MCMC on a regular eight-core processor in a simulation and an empirical study.
arXiv Detail & Related papers (2020-07-07T10:24:45Z) - Slice Sampling for General Completely Random Measures [74.24975039689893]
We present a novel Markov chain Monte Carlo algorithm for posterior inference that adaptively sets the truncation level using auxiliary slice variables.
The efficacy of the proposed algorithm is evaluated on several popular nonparametric models.
arXiv Detail & Related papers (2020-06-24T17:53:53Z) - Efficiently Sampling Functions from Gaussian Process Posteriors [76.94808614373609]
We propose an easy-to-use and general-purpose approach for fast posterior sampling.
We demonstrate how decoupled sample paths accurately represent Gaussian process posteriors at a fraction of the usual cost.
arXiv Detail & Related papers (2020-02-21T14:03:16Z) - A Deep Learning Algorithm for High-Dimensional Exploratory Item Factor
Analysis [0.0]
We investigate a deep learning-based VI algorithm for exploratory item factor analysis (IFA) that is computationally fast even in large data sets with many latent factors.
The proposed approach applies a deep artificial neural network model called an importance-weighted autoencoder (IWAE) for exploratory IFA.
We show that the IWAE yields more accurate estimates as either the sample size or the number of IW samples increases.
arXiv Detail & Related papers (2020-01-22T03:02:34Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.