PaperlayerView exact revision on arXiv

Source-linked AI summary

Robust Influence Maximization

Wei Chen, Tian Lin, Zihan Tan, Mingfei Zhao, Xuren Zhou

arXiv:1601.06551v2cs.SIcs.LG

TL;DR

The paper addresses influence maximization when edge-probability estimates are uncertain. It formulates robust influence maximization, develops LUGreedy and sampling methods, and reports that uncertainty can substantially reduce robustness while information-cascade-based adaptive sampling improves it.

  • Problem

    Influence maximization typically assumes exact edge probabilities, although learned estimates have confidence intervals and their uncertainty may adversely affect performance.

  • Method

    The paper formulates robust influence maximization using a worst-case multiplicative ratio, provides LUGreedy with a solution-dependent bound, and studies uniform and adaptive sampling.

  • Results

    Empirical results show that robustness is sensitive to parameter uncertainty, while information-cascade-based adaptive sampling improves robustness and outperforms uniform and other baseline sampling methods.

  • Takeaways & Limitations

    Robust influence maximization may require tighter parameter estimates, and information-cascade-based sampling can effectively reduce uncertainty and increase robustness.

  • Takeaways & Limitations

    The reported α(Θ) and ¯α(Θ) results target LUGreedy, and better algorithms with higher robustness at the same uncertainty level may exist.

Abstract

from arXiv · show

In this paper, we address the important issue of uncertainty in the edge influence probability estimates for the well studied influence maximization problem --- the task of finding $k$ seed nodes in a social network to maximize the influence spread. We propose the problem of robust influence maximization, which maximizes the worst-case ratio between the influence spread of the chosen seed set and the optimal seed set, given the uncertainty of the parameter input. We design an algorithm that solves this problem with a solution-dependent bound. We further study uniform sampling and adaptive sampling methods to effectively reduce the uncertainty on parameters and improve the robustness of the influence maximization task. Our empirical results show that parameter uncertainty may greatly affect influence maximization performance and prior studies that learned influence probabilities could lead to poor performance in robust influence maximization due to relatively large uncertainty in parameter estimates, and information cascade based adaptive sampling method may be an effective way to improve the robustness of influence maximization.

1. INTRODUCTION

The paper studies influence maximization when edge-probability estimates are uncertain, formulates a worst-case robust objective, and develops algorithms and sampling methods to improve robustness.

  • Motivation: Prior influence-maximization studies generally assume that ground-truth edge influence probabilities are exactly known.Learning methods instead produce estimates with confidence intervals, leaving uncertainty that may adversely affect influence-maximization performance.
  • Problem formulation: Robust Influence Maximization maximizes the worst-case multiplicative ratio between a chosen seed set’s spread and the optimal spread over uncertain parameter settings.The uncertainty is represented by a parameter space of possible edge-probability values.
  • Algorithm: LUGreedy solves the robust influence-maximization task with a solution-dependent performance bound that can be verified after seed selection.When uncertainty disappears, the robust problem reduces to classical influence maximization.
  • Sampling: The paper studies uniform and information-cascade-based adaptive sampling to tighten the parameter space and improve robust influence maximization.Adaptive sampling biases effort toward important edges traversed by information cascades.
  • Empirical findings: Empirical evaluations find that robust ratio decreases rapidly as confidence intervals widen, while information-cascade-based adaptive sampling outperforms uniform and other baseline methods.Large confidence intervals from learned edge probabilities can therefore produce poor robust ratios.

2. MODEL AND PROBLEM DEFINITION

The model represents uncertain edge probabilities by intervals and seeks a fixed-size seed set with the best worst-case influence ratio, building on the independent cascade formulation.

  • Influence model: Under the independent cascade model, influence spread can be represented through stochastic diffusion or reachability in random live-edge graphs.Each directed edge is live independently according to its associated probability.
  • Classical problem: Classical influence maximization selects k vertices maximizing expected influence spread for a known edge-probability vector.The problem is NP-hard, while the spread function is non-negative, monotone, and submodular.
  • Uncertainty model: Uncertain edge probabilities are represented by intervals [l_e, r_e], whose Cartesian product forms the parameter space Θ containing the unknown true vector.The interval can be interpreted as a confidence range obtained from observations or an estimate with edge-specific perturbation.
  • Robust objective: Robust influence maximization chooses k seeds maximizing the worst-case ratio between their spread and the optimal spread under the unknown probability vector.This robust ratio compares a fixed seed set with the underlying optimal size-k solution for each possible parameter setting.
  • Sampling motivation: Limited cascade observations can leave the best attainable robust ratio too low, motivating additional edge sampling to narrow Θ.The sampling question asks how to improve worst-case performance efficiently from the given uncertainty region.

3. ALGORITHM AND ANALYSIS FOR RIM

RIM models uncertain edge probabilities as intervals and selects k seeds maximizing worst-case performance. LUGreedy provides a solution-dependent guarantee, but worst-case robust ratios can remain poor without informative parameter constraints.

  • Robust Influence Maximization: RIM treats each edge probability as an interval, forming parameter space Θ, and maximizes the worst-case ratio between a seed set’s spread and the optimal spread.When Θ collapses to one parameter vector, RIM reduces to classical influence maximization.
  • LUGreedy: LUGreedy applies greedy maximization at the lower and upper parameter vectors, then returns the better candidate seed set.Its performance is evaluated through a gap ratio α(Θ) based on the selected solution and the upper-bound greedy solution.
  • LUGreedy: LUGreedy’s solution-dependent bound can be checked after selecting the seed set and is stronger when α(Θ) is not too small.The bound indicates whether the selected set performs well under every parameter vector in Θ.
  • LUGreedy: In a constructed instance, α(Θ) equals both LUGreedy’s robust ratio and the best achievable robust ratio, namely (1+tl)/(1+tr).This occurs when many alternative seed sets have largely non-overlapping influence coverage.
  • Worst-case limits: Without strong assumptions on Θ, even the best robust ratio can be very small; with interval width δ=O(1/n), it can still be O(log n/n).Randomized seed selection can likewise have robust ratio as low as O(log n/√n).
  • Worst-case limits: If Θ provides no knowledge, such as Θ=×e∈E[0,1], a selected seed set may influence O(k) nodes while an optimal set influences Ω(n).These worst-case limits motivate sampling to narrow the parameter space.

4. SAMPLING FOR IMPROVING RIM

The paper narrows uncertain parameter intervals through uniform or adaptive sampling before applying LUGreedy. Uniform sampling has theoretical guarantees, while information-cascade sampling prioritizes edges relevant to influence propagation.

  • Sampling objective: Sampling for Improving RIM narrows Θ to Θ′ and then seeks a seed set with a large robust ratio under the refined parameter space.The true parameter vector remains in Θ′ with high probability.
  • Uniform sampling: US-RIM samples every edge equally, constructs confidence intervals, and applies LUGreedy; it supports additive and multiplicative interval settings.The algorithm returns both an output parameter space and a seed set.
  • Uniform sampling: The sampling analysis connects confidence-interval width to influence-spread stability through additive and multiplicative bounds.Shrinking intervals and then applying LUGreedy preserves the solution-dependent guarantee when Θ becomes sufficiently tight.
  • Uniform sampling: US-RIM’s guarantees hold with Pr[θ∈Θout]≥1−γ, and the additive setting provides a high-probability (1−1/e−ϵ)-approximation.The multiplicative setting can have better sample complexity when p′=Ω(k^2/m^2).
  • Adaptive sampling: ICS-RIM adaptively samples edges along information cascades, concentrating effort on edges that determine influence spread.Its iterative procedure updates confidence intervals, computes a lower-upper greedy set, and retains high-probability coverage of the true probabilities.
  • Adaptive sampling: Adaptive sampling uses an initial observation set and confidence intervals that accommodate edges with both large and small influence probabilities.The method dynamically increases sampling effort on critical edges as estimates improve.

5. EMPIRICAL EVALUATION

Experiments on Flixster and NetHEPT show that uncertainty and sampling strategy materially affect robust influence maximization. Information-cascade sampling improves robustness more than uniform sampling, while repeatedly sampling only seed out-edges performs poorly.

  • Experimental setup: Experiments use Flixster and NetHEPT graphs to evaluate uniform sampling, information-cascade sampling, and out-edge sampling.Flixster includes Topic 8 and Mixed graphs; the methods are compared using a common parameter-space estimation procedure.
  • Predetermined intervals: As confidence intervals widen, both α(Θ) and ¯α(Θ) decrease, indicating lower robustness under greater parameter uncertainty.The decrease in α(Θ) is sharp for W ∈ [0, 0.1] and slows afterward; ¯α(Θ) also decreases more slowly after W = 0.2.
  • Predetermined intervals: With 318 samples per Flixster edge, α(Θ) is approximately 0.04 for Topic 8 and 0.08 for Mixed, while ¯α(Θ) is approximately 0.12 and 0.2.These values correspond to average interval widths of 0.293 and 0.265, respectively.
  • Sampling results: α(Θ) and ¯α(Θ) increase with sample count, and their consistent trends support using α(Θ) to compare LUGreedy robustness across algorithms.The lower and upper quantities may remain separated, so neither bound is necessarily tight.
  • Sampling results: Both US-RIM and ICS-RIM improve robust ratios, with ICS-RIM outperforming US-RIM as sample size increases; OES-RIM performs significantly worse.OES-RIM repeatedly samples a small set of seed out-edges, leaving other potentially important edges inaccurately estimated.
  • Sampling results: Information-cascade sampling is a competitive adaptive strategy, while predetermined uniform sampling can perform reasonably well when adaptive sampling is unavailable.The empirical comparison suggests that sampling should cover both critical edges and other edges potentially reached by cascades.

6. CONCLUSION

The paper studies robust influence maximization under uncertain edge probabilities, proposes LUGreedy and sampling methods, and finds that robustness is sensitive to parameter uncertainty.

  • The paper proposes robust influence maximization to address uncertainty in learned edge probability estimates.
  • LUGreedy provides a solution-dependent performance bound for robust influence maximization.
  • Information cascade based adaptive sampling reduces uncertainty and increases the robustness of LUGreedy.
  • Robustness may be sensitive to parameter-space uncertainty, and accurate robust influence maximization may require more learning data.
  • The paper identifies unresolved questions about the best attainable robust ratio and improved sampling, learning, and optimization methods.

A. PROOF OF THEOREM 3

The proof establishes unfavorable robust-ratio behavior through three graph constructions, including instances where uncertainty makes a selected seed set much worse than the optimum.

  • For two disjoint dense subgraphs, choosing a seed in the lower-probability subgraph yields spread O(log n), versus Θ(n) for an optimal seed in the other subgraph.
  • The second construction uses intervals [p−ϵ, p+ϵ] covering the critical Erdős-Rényi interval for n/2-node subgraphs.
  • A construction with √n disjoint subgraphs shows that randomized seed selection can also face a worst-case parameter setting targeting the least-selected subgraph.

B. PROOF OF LEMMAS

The lemmas analyze robust influence ratios by reducing parameter cases and graph structure, while connecting path activation probabilities to bounds used in the algorithmic analysis.

  • Because influence spread is monotone in edge probabilities, the analysis can restrict attention to parameter settings with coordinated interval endpoints.
  • The influence spread is represented through live-edge graphs and reachable sets, providing a linear form for subsequent analysis.
  • For fixed edges, conditional live-edge probabilities are separated according to whether each edge is present or absent.
  • The proof reduces extremal interval settings to edges with endpoint probabilities and deletes zero-probability edges before removing cycles.
  • After cycle removal, the graph becomes a DAG decomposable into connected DAG components for component-wise analysis.
  • For a path of length l in a connected DAG, the activation probability under θ− is β^l, supporting the lemma’s ratio analysis.
  • The remaining proof steps derive sampling-related probability bounds using Chernoff bounds and union bounds.

C. PROOF OF THEOREM 6

The theorem proof uses concentration bounds to show that sufficient edge sampling places the true probabilities inside the constructed uncertainty intervals, enabling a robust-ratio guarantee.

  • The proof first bounds sampling deviations for every edge using Chernoff-Hoeffding inequalities.
  • With probability at least 1 −γ, the sampled observations satisfy the interval constraints defining Θ.
  • The proof then applies the earlier lemma and Theorem 2 to transfer interval accuracy into a robust influence guarantee.
  • A union bound combines the per-edge deviation probabilities into a simultaneous guarantee over all edges.
  • The constructed interval endpoints are set multiplicatively around each edge probability as re = (1 + a)pe and le = (1 −a)pe.
Loading 1601.06551v2…