Abstract
Multiplex influence maximization (MIM) asks us to identify a set of seed users such as to maximize the expected number of influenced users in a multiplex network. MIM has been one of central research topics, especially in nowadays social networking landscape where users participate in multiple online social networks (OSNs) and their influences can propagate among several OSNs simultaneously. Although there exist a couple combinatorial algorithms to MIM, learning-based solutions have been desired due to its generalization ability to heterogeneous networks and their diversified propagation characteristics. In this paper, we introduce MIM-Reasoner, coupling reinforcement learning with probabilistic graphical model, which effectively captures the complex propagation process within and between layers of a given multiplex network, thereby tackling the most challenging problem in MIM. We establish a theoretical guarantee for MIM-Reasoner as well as conduct extensive analyses on both synthetic and real-world datasets to validate our MIM-Reasoner’s performance.
Introduction
Influence Maximization (IM) is the classic problem of identifying a small set of "seed" users to trigger the largest possible cascade of information in a network. While well-studied for single networks, real-world influence happens across multiplex networks—layered systems where the same users interact on multiple platforms (e.g., Twitter, Facebook, and Instagram) simultaneously.
The MIM problem is significantly harder than standard IM due to three primary factors:
- Scalability: Multiplex networks are massive, and the search space grows exponentially with the number of layers.
- Heterogeneity: Different platforms follow different rules for how information spreads (e.g., Independent Cascade vs. Linear Threshold models).
- Redundancy: Activating a user on one layer might automatically activate them on others. Traditional methods often waste "budget" by re-activating users who would have been influenced anyway through cross-layer overlaps.
Methodology: The MIM-Reasoner Framework
The authors introduce MIM-Reasoner, which tackles the problem in two distinct phases by combining deep reinforcement learning (RL) with Probabilistic Graphical Models (PGMs).
Phase 1: Budget Allocation
Instead of treating the multiplex network as one giant graph, the framework decomposes it into individual layers. It uses a Graph Attention Network (GAT) to identify a "candidate set" of high-potential nodes, drastically reducing the search space. Then, it solves a Multiple Choice Knapsack Problem (MCKP) to decide how many seed nodes to allocate to each layer to maximize the initial estimated spread.
Phase 2: Relation RL Optimization
This is the "reasoning" core. An RL agent learns a policy to select specific seed nodes for each layer. To account for cross-layer effects, the system integrates a Probabilistic Graphical Model (PGM)—specifically a Bayesian Network—trained on node activation data. The PGM provides a "reward signal" to the RL agent, penalizing it for selecting nodes that are already likely to be activated by other layers.
Crucially, the authors prove that their method maintains a theoretical approximation ratio of $\frac{(1-\epsilon)(1-1/e)}{(o+1)k}$ in the worst case (where $k$ is the number of layers and $o$ is the number of overlapping nodes), providing a safety net that most deep-learning approaches lack.
Experiments and Results
The framework was evaluated on both synthetic and real-world datasets, including biological networks (Celegans, Drosophila) and massive social networks like the Pope-Election dataset, which contains over 2.06 million nodes.
Key Findings
- Superior Spread: As shown in Figure 5, MIM-Reasoner consistently matched or outperformed state-of-the-art combinatorial (ISF, KSN) and deep learning (DeepIM, ToupleGDD) methods in terms of total influenced users.
- Massive Speedups: On the Pope-Election dataset, traditional combinatorial methods failed due to memory errors (OOM). MIM-Reasoner not only solved it but did so with an inference time of just 2.27 seconds.
- Efficiency through Sparsity: The model is remarkably lightweight, using only ~64,000 parameters compared to nearly 10 million in competing models like DeepIM. This makes it much faster to train and less prone to overfitting.
Conclusion
MIM-Reasoner bridges the gap between classical probability and modern RL. By using a Bayesian Network to "reason" about redundancy, the agent understands that a node's value is its marginal influence given what is happening on other platforms. While current guarantees are tied to submodular propagation models, future work could explore dynamic multiplex networks where inter-layer connections change over time.
Summary updated