Gradient Method for Continuous Influence Maximization with Budget-Saving Considerations

Wei Chen, Weizhong Zhang, Haoyu Zhao

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:

  1. ProxGrad-RIS: A proximal gradient method that achieves a $(1/2 - \epsilon)$-approximation for the general CIM-BS problem.
  2. 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).

Figure 2: Performance comparison of various algorithms in the Personalized Marketing scenario across different budget constraints (k) and balance parameters (λ).

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.

Figure 5: Performance comparison in the Segment Marketing scenario, demonstrating the robustness of the proposed methods across different cost functions and parameters.

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

Abstract

Continuous influence maximization (CIM) generalizes the original influence maximization by incorporating general marketing strategies: a marketing strategy mix is a vector x = (x1, …, xd) such that for each node v in a social network, v could be activated as a seed of diffusion with probability hv(x), where hv is a strategy activation function satisfying DR-submodularity. CIM is the task of selecting a strategy mix x with constraint ∑ixi ≤ k where k is a budget constraint, such that the total number of activated nodes after the diffusion process, called influence spread and denoted as g(x), is maximized. In this paper, we extend CIM to consider budget saving, that is, each strategy mix x has a cost c(x) where c is a convex cost function, and we want to maximize the balanced sum g(x) + λ(k − c(x)) where λ is a balance parameter, subject to the constraint of c(x) ≤ k. We denote this problem as CIM-BS. The objective function of CIM-BS is neither monotone, nor DR-submodular or concave, and thus neither the greedy algorithm nor the standard result on gradient method could be directly applied. Our key innovation is the combination of the gradient method with reverse influence sampling to design algorithms that solve CIM-BS: For the general case, we give an algorithm that achieves (½ − ε)-approximation, and for the case of independent strategy activations, we present an algorithm that achieves (1 − 1/e − ε) approximation.
BibTeX
@inproceedings{chen2020gradient,
  author = {Wei Chen and Weizhong Zhang and Haoyu Zhao},
  title = {{Gradient Method for Continuous Influence Maximization with Budget-Saving Considerations}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.1609/aaai.v34i01.5332},
}
Figure