Beyond Greedy: Maximizing Social Influence with Conjugate Learning Automata

TL;DR

The traditional "Greedy" approach to Influence Maximization (IM)—picking the best node one at a time—is mathematically elegant but can be tricked by specific network structures. This paper proposes Conjugate Learning Automata (CLA), a reinforcement learning framework where multiple agents cooperate to select a set of seed nodes simultaneously. This approach not only escapes "greedy traps" but also rivals the efficiency of state-of-the-art methods like CELF.

The Problem: The "Greedy Pitfall"

Influence Maximization is the art of selecting $K$ "seed" nodes in a social network to maximize the eventual spread of information. Since Kempe's seminal work in 2003, the Greedy Algorithm has been the gold standard because it guarantees at least $(1-1/e)$ of the optimal performance.

However, "Greedy" has a fundamental flaw: it is myopic. It assumes the best set of 2 nodes must include the single best individual node. As shown in the figure below, clever network constructions (adversary pitfalls) can make the best pair consist of two nodes that, individually, look mediocre.

In this toy example, a greedy method selects $v_1$ first, then $v_4$, missing the globally optimal pair $\{v_2,v_3\}$.

Methodology: Coordination through Conjugation

The authors propose a system of Conjugate Learning Automata (CLA). Instead of one algorithm making $K$ decisions, they deploy $K$ independent LAs that "play a game" to reach a Nash Equilibrium.

1. The Architecture

Each LA represents one seed to be selected. They interact with a "stochastic environment" (the social network).

• Action: Choosing a node from the network.
• Feedback: The total influence spread ($\sigma$) resulting from the combination of all $K$ actions.

2. The "Adiabatic" Training Strategy

To prevent the LAs from converging too quickly to local optima (which would just replicate the greedy result), the authors use a temporary threshold ($\delta$).

• The threshold starts low, allowing all agents to explore.
• Only one LA updates at a time to keep the environment "stationary" for that specific agent.
• As $\delta$ increases toward the convergence threshold $T$, the agents refine their choices collectively.

Experimental Battleground: Synthetic and Real-World

The researchers tested CLA against CELF, the standard-bearer for efficient greedy IM.

Breaking the Pitfalls

In synthetic environments specifically designed to trap greedy algorithms, the probability vectors of the CLA agents (Figures 4b and 4c) successfully shifted away from the "greedy bait" ($v_1$) to settle on the true optimal nodes ($v_2$ and $v_3$).

Visualizing how the probability distribution shifts across iterations (left to right) to identify the optimal nodes.

Real-World Efficiency

When tested on datasets like Arxiv GrQc and HEP-PH, CLA achieved parity with CELF in spread range but often required fewer simulations to reach convergence. This proves that CLA is not just a theoretical "trick" for small graphs but a scalable alternative for real social networks.

Critical Insight & Summary

The brilliance of this work lies in how it frames Influence Maximization as a Cooperative Game. While greedy algorithms are limited by their sequential nature, the "conjugate" nature of this approach treats the seed set as a holistic unit.

Key Takeaways:

• Smarter than Greedy: CLA can solve specific network configurations that are mathematically designed to fail under greedy logic.
• Competitive Speed: By using the eDGPA algorithm, the convergence is fast enough for practical use.
• Graceful Degradation: By tuning the hyper-parameters (${\delta }_0$), the model can actually mimic a greedy search, making it a flexible generalization of previous work.

Limitation: The method's performance depends heavily on the step-size ($\Delta \delta$). If the threshold increases too quickly, the "cooperation" benefit disappears, and the model reverts to greedy-like behavior.