Abstract
Continuous Influence Maximization with Budget Saving (CIM-BS) represents a realistic evolution of viral marketing models, where the objective is to maximize network influence while simultaneously minimizing marketing expenditures. Traditional greedy algorithms, which rely on the submodularity and monotonicity of influence functions, fail in this context because the budget-saving objective is neither monotone nor submodular. This paper introduces a novel framework that integrates gradient-based optimization with Reverse Influence Sampling (RIS). By leveraging RIS to create a deterministic estimator, the authors develop two algorithms—ProxGrad-RIS and UpperGrad-RIS—that provide strong theoretical approximation guarantees and achieve significant practical speedups over standard stochastic gradient methods.
Introduction
In social network analysis, Influence Maximization (IM) is the task of identifying a set of "seed" users to trigger the largest possible cascade of information or adoption. While classic IM treats user selection as a binary decision, Continuous Influence Maximization (CIM) allows for the allocation of continuous resources, such as varying discount levels or promotional intensity.
This research addresses a critical practical constraint: Budget Saving (CIM-BS). In real-world marketing, practitioners do not simply wish to exhaust a fixed budget; they seek to balance the reach of their campaign against the cost of the resources deployed. This creates a combined objective function: the expected influence spread plus the weighted value of the saved budget.
The Mathematical Challenge
The introduction of budget-saving considerations fundamentally alters the mathematical landscape of the problem. Influence spread is typically DR-submodular and monotone increasing—properties that allow greedy algorithms to find near-optimal solutions. However, the budget-saving term is concave and decreasing. Their sum results in a function that is neither monotone, nor DR-submodular, nor concave. Consequently, the theoretical guarantees of standard greedy hill-climbing algorithms vanish, necessitating a more sophisticated optimization approach.
Proposed Methodology
To navigate this complex objective, the authors propose moving away from discrete greedy steps toward gradient-based methods. The primary hurdle in this transition is that the exact gradient of influence spread is computationally expensive to calculate, and standard stochastic gradient descent (SGD) suffers from high variance due to the inherent randomness of network diffusion.
Integrating Reverse Influence Sampling (RIS)
The core innovation of this paper is the use of Reverse Influence Sampling (RIS) to facilitate gradient computation. RIS samples "reverse reachable" sets to estimate influence. By using these sets, the authors construct a deterministic estimator function, allowing for the calculation of an exact gradient of the estimate rather than a noisy stochastic gradient.
- ProxGrad-RIS (General Case): This algorithm utilizes a proximal gradient method designed to handle the mixture of DR-submodular and concave components. It achieves a guaranteed $(1/2 - \epsilon)$ approximation ratio.
- UpperGrad-RIS (Independent Activation): In scenarios where marketing strategies activate users independently, the objective function behaves like a "coverage function." The authors exploit this by constructing a tight concave upper bound and applying a projected subgradient method, improving the theoretical guarantee to a $(1 - 1/e - \epsilon)$ approximation.
Experimental Evaluation
The proposed methods were evaluated on two real-world academic networks:
- DM Network: A researcher collaboration network (679 nodes, 3,374 edges).
- NetHEPT: A larger high-energy physics theory collaboration network (15,233 nodes, 62,774 edges).
Key Results
- Efficiency Gains: The RIS-backed gradient methods demonstrated massive speedups, running 9 to 49 times faster than standard SGD applied to the original objective.
- Superior Optimization: Both
ProxGrad-RISandUpperGrad-RISconsistently outperformed greedy heuristics. This performance gap was most notable when the penalty for budget spending (the $\lambda$ parameter) was high, indicating that these algorithms are significantly better at balancing the trade-off between spread and cost. - Heuristic Acceleration: The authors introduced an early-stopping heuristic (
-HEU) based on the rate of change in the objective value. In practice, this reduced computation time by 5-7x (e.g., from 81 seconds down to 13 seconds on the DM dataset) without any measurable loss in the quality of the influence spread.
Conclusion and Future Work
This study marks a significant milestone in applying gradient methods to influence maximization, providing a robust theoretical and practical framework for non-monotone, non-submodular optimization. While the current theoretical time complexity (up to $O(n^4)$) suggests challenges for massive-scale networks, the practical performance of the heuristic variants is promising. Future research will focus on improving the scalability of these gradient methods and extending the RIS-gradient framework to other complex domains, such as competitive influence maximization where multiple entities vie for the same network nodes.
Summary updated