ESSM: Solving the Multiple Benefit Thresholds Problem with Unprecedented Efficiency

TL;DR

Viral marketing in Online Social Networks (OSNs) isn't just about maximizing reach; it's about hitting specific ROI targets (Benefit Thresholds) under a strict budget. This paper introduces the Multiple Benefit Thresholds (MBT) problem and the ESSM algorithm, which optimizes for multiple targets simultaneously by incrementally reusing computation. The results are staggering: it's up to 4600x faster and 13,000x more memory-efficient than adapted SOTA baselines.

Motivation: Why One Threshold is Never Enough

In the real world, marketing strategies are fluid. A company might want to know the cheapest way to generate $10kin"influencevalue,"buttheyalsoneedtoknowthecostfor$20k or $50k to align with varying quarterly budgets.

Existing models like Influence Maximization (IM) focus on a fixed budget $k$, while Influence Threshold (IT) models look for a minimal set to reach a specific number of nodes. Both have two fatal flaws:

1. Uniformity Bias: They treat all users as equal, ignoring that a "high-net-worth" user provides more benefit than a casual browser.
2. Isolation: Running a single-threshold algorithm $k$ times for $k$ different targets is computationally wasteful.

Methodology: The ESSM Framework

The researchers proposed ESSM (Efficient Sampling for Selecting Multiple seed sets). Its central "Aha!" moment is the transition from greedy selection in a vacuum to Incremental Refinement.

1. Benefit Sampling & Martingale Bounds

The algorithm uses Benefit Samples (BS)—a variation of Reverse Reachable sets—to estimate the expected benefit $B(S)$. Instead of expensive Monte Carlo simulations, it uses Martingale theory to determine the minimum number of samples required to guarantee an $(ϵ,\delta )$-approximation.

2. The Incremental Loop

Unlike traditional methods that start from an empty set for every new threshold, ESSM follows a "nesting" logic:

• Seed Reuse: To reach threshold $T_i$, it starts with the seed set $S_{i-1}$ already computed for $T_{i-1}$.
• Sample Inheritance: It carries over random samples used for lower thresholds, only adding new samples when the statistical requirements for a higher threshold (which is harder to estimate) demand them.

The core mathematical bound for sample complexity used in ESSM.

Experimental Showdown

The authors tested ESSM on the Net-Phy and Net-Hept datasets. They compared it against BCT' (an adapted Cost-aware model), AT (standard IT solver), and DEGREE (a heuristic baseline).

Performance Metrics

• Cost Efficiency: ESSM consistently found seed sets with the lowest costs. Specifically, it was 1875x cheaper than BCT'.
• Speed & Memory: Because of the inheritance mechanism, ESSM's runtime was nearly flat compared to the exponential growth seen in AT. It processed datasets in seconds that took AT hours.

Fig 1: Net-Phy dataset performance comparison showing ESSM's dominance in runtime and memory.

Critical Insight & Conclusion

The Multiple Benefit Thresholds problem is NP-hard and its objective function is #P-hard to compute. ESSM bypasses these hurdles by treating the problem as a submodular set cover challenge with a stochastic oracle.

The Takeaway: If you are building a recommendation or marketing engine, don't optimize for single points. Scaling through computation reuse and martingale-based sample bounding is the only way to handle multi-threshold objectives in billion-scale networks.

Limitations

While ESSM is revolutionary in speed, it currently operates under the Independent Cascade (IC) model. Future work could benefit from extending this incremental logic to the Linear Threshold (LT) model or competitive/multi-product diffusion scenarios.