Beyond Unit Costs: Scaling Budgeted Influence Maximization via Belief Propagation

TL;DR

Social influence maximization is no longer just about the number of people; it's about the "price" of influence. This paper tackles the Budgeted Influence Maximization (BIM) problem by introducing an improved greedy algorithm with a $1-1/\sqrt{e}$ approximation ratio. By converting social graphs into Directed Acyclic Graphs (DAGs) and applying Belief Propagation, the authors achieve SOTA influence spread with a fraction of the computational cost of traditional Monte Carlo methods.

Problem & Motivation: The Cost of a "Like"

In viral marketing, not all seeds are created equal. Influential users often demand higher incentives, yet most classic research treats every node with a "unit cost." When budgets are finite and nodes have arbitrary costs, the standard greedy approach fails—potentially picking "cheap" but isolated nodes over "expensive" but high-impact ones.

The technical hurdle is twofold:

1. Optimization: The budgeted version of IM is NP-hard and the naive greedy ratio is unbounded.
2. Estimation: Calculating the "Influence Spread" (the expected number of influenced nodes) is #P-complete. Traditional Monte-Carlo simulations require tens of thousands of runs per iteration, which doesn't scale to millions of edges.

Methodology: From Social Graphs to Bayesian Networks

The authors' core "aha!" moment is identifying the linkage between Information Diffusion and Bayesian Inference.

1. The Strategy: Improved Greedy

Instead of just picking the best ROI (Spread/Cost), the "Improved Greedy" algorithm compares the result of a cost-effective greedy selection against the single most influential node. This simple shift secures a constant approximation ratio of $(1-1/\sqrt{e})$.

2. The Engine: DAGs and Belief Propagation

To solve the #P-complete estimation problem, the authors propose reducing the complex, loopy social graph into a Directed Acyclic Graph (DAG). They define the Maximum Influence Path (MIP) to retain only the most likely edges of transmission.

Once a DAG is formed, the influence spread becomes a marginal probability problem in a Bayesian Network. The authors implement:

• LBP (Loopy Belief Propagation): High accuracy for multi-connected graphs.
• SPBP (Single-Pass BP): Optimized for speed, treating the graph as "singly-connected."

Figure: The framework of the proposed BIM algorithm, from DAG construction to BP-based estimation.

Experiments & Results: Efficiency Gains

The authors tested their approach on datasets ranging from small lab email networks to the massive Amazon product co-purchasing graph (262k nodes).

Key Findings:

• Accuracy: The proposed DAG1-LBP combination tracks the performance of the "Gold Standard" Greedy algorithm (10,000 simulations) almost perfectly.
• Scalability: On the p2p-Gnutella dataset, the proposed methods were orders of magnitude faster than CELF (the leading baseline for budgeted problems).
• Density Resilience: Traditional heuristics like PMIA fail as networks get denser. The DAG+BP approach remains robust, capturing complex "word-of-mouth" paths that simple degree-based methods miss.

Figure: Influence spread results on Email and P2P networks show the proposed BP methods matching Monte-Carlo Greedy performance.

Critical Analysis & Conclusion

This paper provides a rigorous bridge between Graph Theory and Probabilistic Inference. The shift from simulation to message-passing (BP) reflects a broader trend in AI toward more structured, analytical estimators.

Takeaway: If you are dealing with large-scale influence problems (e.g., fraud detection or viral marketing), don't just simulate—prune and infer.

Limitations: While the DAG construction is efficient, very dense graphs with many cycles still pose a challenge for the "Maximum Influence Path" assumption, as influence might aggregate through many weak paths rather than one strong one. Future work might explore Graph Neural Networks (GNNs) to learn these influence kernels directly from data.