Introduction
Influence Maximization (IM) is a foundational problem in social network analysis, traditionally focused on selecting a discrete set of seed nodes to trigger a viral cascade. Continuous Influence Maximization (CIM) extends this by allowing continuous investment levels across various marketing strategies. However, existing CIM models often assume a fixed budget must be entirely spent. In practice, marketers seek to maximize the "net gain"—the total influence spread plus any unspent budget. This paper introduces the Continuous Influence Maximization with Budget-Saving (CIM-BS) framework to address this practical trade-off.
The Challenge of Non-Submodularity
Mathematically, CIM-BS is significantly more difficult than standard IM. While influence spread functions are typically monotone and DR-submodular, the inclusion of a budget-saving term (which is concave and decreasing) results in an objective function that lacks these properties. Consequently, the standard greedy algorithms that dominate IM literature fail to provide theoretical guarantees for this non-monotone, non-submodular problem.
The RIS-Gradient Framework
To overcome these challenges, the authors propose a framework that integrates Reverse Influence Sampling (RIS) with continuous optimization. RIS is traditionally used to speed up discrete IM by sampling "Reverse Reachable" (RR) sets to create an unbiased estimator of the influence function. This research demonstrates that RIS can be leveraged to compute the exact gradient of this estimator, providing a stable objective for gradient-based optimization and bypassing the noise inherent in traditional stochastic simulations.
The paper introduces two primary algorithms:
- ProxGrad-RIS: A proximal gradient method that achieves a $(1/2 - \epsilon)$-approximation for the general CIM-BS problem.
- UpperGrad-RIS: A specialized algorithm for independent strategy activations that utilizes a tight concave upper bound to reach a superior $(1 - 1/e - \epsilon)$-approximation.
Experimental Evaluation
The researchers evaluated their approach on the DM network, a real-world dataset of 679 data mining researchers and 3,374 edges. They tested two distinct marketing scenarios: Personalized Marketing (targeting specific individuals) and Segment Marketing (targeting groups).
Key Results and Efficiency
In both marketing scenarios, the proposed RIS-integrated gradient methods consistently outperformed baselines such as Greedy-RIS and standard stochastic gradient descent. UpperGrad-RIS, in particular, demonstrated the highest budget-balanced influence spread, especially as the balance parameter ($\lambda$) increased, indicating its effectiveness in identifying optimal stopping points for spending.
Beyond solution quality, the framework offers a massive efficiency gain. The RIS-integrated methods achieved a 30x speedup over standard stochastic gradient descent (ProxGrad-Org). This is attributed to the RIS estimator's faster convergence compared to raw diffusion simulations. Furthermore, the authors found that a heuristic early-stopping rule (terminating when the objective change is < 0.3) maintains high quality while significantly boosting practical speed.
Conclusion
The integration of RIS with gradient methods provides a powerful new toolkit for non-submodular influence maximization. By explicitly accounting for budget savings, this framework offers a more realistic and efficient approach for viral marketing. Future directions include scaling these methods to billion-node graphs and extending the framework to competitive influence maximization scenarios.
Summary updated