LISA: Scaling the Social Influence Spectrum for Multi-Budget Decisions

TL;DR

Quantifying social influence typically involves solving for a specific number of "seeds" ($k$). But what if your budget is flexible? This paper introduces LISA, the first algorithm capable of computing the Influence Spectrum—finding near-optimal seed sets for all budgets from $k_{lower}$ to $k_{upper}$ simultaneously. It processes billion-edge graphs in minutes, offering a $1-1/e-ϵ$ guarantee while being 100x faster than previous kings of the hill like IMM.

Background: The Price of Flexibility

The Influence Maximization (InfMax) problem is a staple of viral marketing: find $k$ nodes to maximize the expected reach. However, in the real world, decision-makers don't just ask "Who are the best 100 people?" They ask "What is the ROI if I pick 50, 100, or 500?"

Until now, answering this meant rerunning expensive algorithms for every single value of $k$. Existing SOTA methods like IMM and SSA scale poorly when you need a wide range of results because their sampling logic is optimized for a single, fixed $k$.

The Core Insight: The Influence Spectrum (InfSpec)

The authors propose InfSpec, the maximum influence at every possible seed set size within a range.

The technical hurdle? The number of required samples (hyperedges) in Reverse Influence Sampling (RIS) is governed by $OPT(k)$, which changes non-monotonically with $k$. LISA solves this by utilizing a "Stop-and-Stare" philosophy simplified through a global threshold $\Lambda$.

LISA's Methodology

Instead of estimating $OPT(k)$ for each $k$, LISA uses a martingale-based stopping rule. It generates a stream of hyperedges and checks a simple condition: Is the coverage of the current candidate seed set for the smallest budget high enough?

The algorithm iterates by doubling the sample count until the degree of the seed set in the hypergraph exceeds the theoretical threshold $(\Lambda )$. Because the Greedy Max-Coverage solution for a large $k$ contains the solutions for smaller $k$ as prefixes, a single "spectrum" is generated in one pass.

Experimental Results: Billion-Scale Domination

The paper puts LISA to the test on the massive Twitter dataset (1.5 billion edges).

1. Speed

LISA is the clear winner. While other methods take hours to compute solutions for a range of 100 different $k$ values, LISA finishes the entire spectrum in roughly 15 minutes.

2. Efficiency

The memory footprint is a critical bottleneck for InfMax. LISA manages to keep memory consumption nearly half that of TIM+ and IMM on the largest datasets because it avoids the redundant sample storage needed by point-solution reruns.

Critical Analysis & Conclusion

Takeaway

LISA proves that the "computational cost" of being flexible with your budget is negligible. By deriving a global stopping condition, we can "kill all birds with one stone"—obtaining the entire influence-to-cost curve rather than just a single point.

Limitations

While LISA is near-optimal for standard IC and LT models, its performance on more "expensive" diffusion models (like continuous-time models) remains an open question. Additionally, the algorithm assumes submodularity; if the influence function lacks this property (e.g., in some competitive settings), the greedy prefix approach would fail.

Future Outlook

This work sets a new bar for industrial viral marketing. The ability to provide an interactive "Spectrum" allows marketers to perform cost-benefit analyses in real-time on massive graphs, moving the field from theoretical optimization to practical decision science.