Seeded MOEAs: Accelerating Social Influence Maximization via Heuristic Initialization

TL;DR

Social Influence Maximization (IM) is the art of picking the best "influencers" to trigger a viral cascade. While Evolutionary Algorithms (EAs) are great at finding the sweet spot between budget (number of seeds) and impact (total reach), they are notoriously slow. This paper introduces a seeding mechanism that jump-starts a Multi-Objective EA with results from traditional heuristics, achieving better results with 100x fewer evaluations than prior evolutionary methods.

Background & Motivation: The Pareto Trade-off

In marketing or public health, you rarely have an infinite budget. You face a dual-objective problem:

1. Minimize Cost: Use as few seed nodes as possible.
2. Maximize Spread: Reach as many people as possible.

Most existing solutions are "single-objective" greedy heuristics that require you to pick a fixed budget $k$ beforehand. Multi-Objective Evolutionary Algorithms (MOEAs) like NSGA-II can find the entire Pareto Front—a curve of optimal solutions for every budget—in a single run. However, starting an EA from a random population is like searching for a needle in a haystack; it takes millions of simulations of the "Independent Cascade" (IC) model to converge.

The "Seeding" Methodology: Best of Both Worlds

The authors propose a hybrid pipeline. Instead of starting with a random set of nodes, they initialize the MOEA population using solutions from five classical heuristics:

• HIGHDEG: Picks nodes with the most connections.
• SDISC: A discounted degree approach that accounts for overlapping influence.
• GDD: A refined version of degree discount looking two steps ahead.
• CELF: A "lazy forward" greedy algorithm that is more efficient than standard hill-climbing but still slow on large graphs.

By injecting these "good enough" solutions into the first generation, the MOEA doesn't waste time exploring obviously bad parts of the search space. It uses genetic operators (Add, Remove, Replace mutation; unique-node crossover) to refine these heuristic seeds into truly optimal configurations.

The Independent Cascade (IC) model used as the fitness function to simulate how influence flows from seeds to neighbors.

Experimental Results: Faster and Better

The study evaluated three real-world datasets, ranging from Facebook social circles to the Epinions consumer network.

1. Efficiency Gains

In previous work, it took roughly 1,000,000 evaluations to beat basic heuristics. With the new seeding approach, the MOEA found superior solutions in just 10,000 evaluations. On the ca-GrQc network, the algorithm immediatey began optimizing from a high-quality baseline provided by Generalized Degree Discount (GDD).

2. Overcoming Heuristic Limits

Heuristics like CELF are mathematically grounded but computationally "heavy" on large graphs. On the soc-ePinions1 graph (75k nodes), CELF was too slow to even complete. The seeded MOEA, however, was able to leverage simpler heuristics (like SDISC) and then evolve them into high-performing seed sets that the baseline heuristics couldn't reach.

Influence vs. Seed Set Size: The MOEA (red line) consistently pushes the boundary further than any individual heuristic (dots).

Critical Insight & Future Outlook

The primary takeaway is that Inductive Bias matters. By acknowledging that we already have "decades of heuristic wisdom," we haven't cheated the EA; we've given it a map of the neighborhood.

Limitations: While the number of evaluations dropped, each evaluation still requires a stochastic simulation of the Independent Cascade model. On massive billion-node graphs, even 10,000 simulations might be too much.

Future Work: The authors suggest moving toward Surrogate Models—using Machine Learning to predict how much a seed set will spread without actually running the expensive simulation. This could be the final step in making evolutionary influence maximization applicable to the scale of the modern web.

Summary Table