TIPTOP: Shattering the (1-1/e) Barrier in Viral Marketing at Billion-Scale

TL;DR

For over a decade, the Influence Maximization (IM) field has been "stuck" at the $(1-1/e)$ approximation ratio—a theoretical ceiling for greedy algorithms. TIPTOP (Tiny Integer Program with Theoretically OPtimal results) breaks this barrier by proving that we can reach nearly exact $(1-ϵ)$ optimality even on billion-edge networks by cleverly combining Integer Programming with a massive reduction in sampling complexity.

Background: Why "Good Enough" Isn't Enough Anymore

Influence Maximization (IM) and its generalized cousin, Cost-aware Targeted Viral Marketing (CTVM), are the "holy grails" of social media advertising. The goal is to pick $k$ users who spark the largest cascade of product adoption.

The problem? IM is NP-hard. Since 2003, researchers have relied on the Greedy algorithm because it offers a $(1-1/e\approx 63\%)$ guarantee. While state-of-the-art methods like SSA and IMM have made this process incredibly fast, no one knew how much influence they were actually leaving on the table. TIPTOP changes the narrative from "how fast can we approximate" to "how close can we get to the real optimum."

The Core Insight: Quality Over Quantity

The traditional two-stage Stochastic Programming (SP) approach fails in social networks because it tries to model the entire graph for every possible "realization" of edge activations. TIPTOP bypasses this by using Reverse Influence Sampling (RIS) but with a twist.

Instead of using a greedy approach to cover as many RR sets as possible, TIPTOP uses an Integer Linear Program (ILP).

How TIPTOP remains scalable:

1. Sample Reduction: TIPTOP identifies that ILP solvers can find the absolute optimum if the number of RR sets is small. It uses a factor of $1000imes$ fewer samples than greedy methods.
2. Dynamic Verification: It starts with a tiny pool of samples, finds a candidate solution, and then uses a separate "Verify" procedure to check if the solution is truly $(1-ϵ)$ optimal.
3. Adaptive Growth: If the candidate fails the test, it increases samples just enough to bridge the gap.

The proof map above illustrates how TIPTOP maintains its approximation guarantee while minimizing the search space.

Methodology: The "Tiny" Integer Program

The mathematical formulation of TIPTOP is surprisingly compact. By embedding node benefits into the sampling process (BSA algorithm), the ILP focuses purely on coverage:

$extmaximize\sum (1-y_j)$ Subject to: ${\sum }_{v\in V}{s}_v\le k$ ${\sum }_{v\in R_j}{s}_v+y_j\ge 1\forall R_j\in \mathcal{R}$

Here, $s_v$ selects the seed, and $y_j$ tracks if an RR set is "missed." Because TIPTOP uses so few $R_j$ sets, the ILP is solved in seconds rather than hours.

Experiments: Benchmarking the Giants

The authors tested TIPTOP on the Twitter dataset (1.5 Billion edges).

Key Findings:

• Speed: TIPTOP provides a $98\%$ optimal solution in under 3 hours on Twitter.
• Sample Efficiency: As shown in the table below, TIPTOP requires orders of magnitude fewer samples for its coverage stage compared to IMM or SSA.

• The "Greedy Gap": The benchmarking results show that while greedy algorithms often perform well, their performance can degrade significantly when costs are randomized or when targeting specific sub-communities (CTVM). In some scenarios, the gap between greedy and TIPTOP's $(1-ϵ)$ result is substantial.

Performance plots show that TIPTOP's runtime is competitive with SOTA greedy handles like SSA, even while providing much higher quality results.

Conclusion & Perspective

TIPTOP is more than just a new algorithm; it’s a benchmarking tool. For the first time, researchers can calculate exactly how much "money" they are leaving on the table when using greedy approximations in billion-scale networks.

Limitations: The runtime of the ILP can be less predictable than the linear-time greedy methods, as ILP solving is inherently exponential in the worst case. however, TIPTOP's sampling reduction is so effective that this worst-case scenario is rarely encountered in social network topologies.

Future Work: This framework could potentially be adapted to more complex influence models, such as competitive viral marketing or time-constrained cascades, where greedy algorithms struggle even more than in the standard IM setting.