MIM-Reasoner: Learning with Theoretical Guarantees for Multiplex Influence Maximization

Nguyen Do, Tanmoy Chowdhury, Chen Ling, Liang Zhao, My T. Thai

Abstract

Multiplex Influence Maximization (MIM) involves identifying a set of seed users to maximize information spread across multiple interconnected social networks. Current approaches often fail to scale to massive networks or lack theoretical performance guarantees. This paper introduces MIM-Reasoner, a novel framework that integrates Reinforcement Learning (RL) with Probabilistic Graphical Models (PGMs). By decomposing the MIM problem into budget allocation and relation-aware RL optimization, the framework achieves state-of-the-art influence spread while maintaining high efficiency and providing theoretical approximation ratios.

Introduction

In the contemporary digital landscape, users typically maintain presence across multiple social platforms, such as Twitter, Instagram, and TikTok. This interconnectedness forms a Multiplex Network, where influence can propagate not only within a single platform but also across layers via linked accounts. For instance, activating a user on one platform may automatically trigger their activation on another.

The Multiplex Influence Maximization (MIM) problem seeks to select a limited budget of seed nodes to maximize total influence across all layers. This task presents three primary challenges:

  1. Scalability: Real-world networks often encompass millions of nodes and edges.
  2. Heterogeneity: Information diffusion dynamics vary significantly between different platforms.
  3. Redundancy: Overlapping user bases mean that targeting a user on multiple platforms can be inefficient if cross-layer activation is likely.

Methodology: The MIM-Reasoner Framework

MIM-Reasoner addresses these challenges through a two-phase decomposition strategy.

Phase 1: Budget Allocation

Rather than treating the multiplex network as a monolithic graph, the system first determines how to distribute the total seed budget across individual layers. It employs a Graph Attention Network (GAT) to evaluate node potential and subsequently solves a "Multiple Choice Knapsack Problem" to optimize the number of seeds assigned to each layer.

Phase 2: Relation RL Optimization

The core of the framework is an RL agent trained to select specific nodes within each layer. To account for cross-layer dependencies and avoid redundancy, the authors integrate a Probabilistic Graphical Model (PGM), specifically a Bayesian Network. The PGM models the causal relationships between layers, providing a refined "reward signal" to the RL agent. This signal discourages the selection of nodes that are highly likely to be activated through inter-layer influence, ensuring a more diverse and effective seed set.

MIM-Reasoner workflow architecture

Critically, MIM-Reasoner is not a purely empirical "black-box" model; the authors provide theoretical guarantees for solution quality, establishing approximation ratios for various scenarios.

Experimental Evaluation

The model was rigorously tested against several baselines, including DeepIM and ToupleGDD, across diverse datasets:

  • Synthetic Graphs: 5,000 nodes with varying overlap rates (30% to 70%) and 3 to 9 layers.
  • Biological Networks: Celegans and Drosophila multiplex networks.
  • Large-Scale Social Networks: The Twitter-Foursquare network (~93k nodes, 18M edges) and the Pope Election dataset (over 2 million nodes, 6M edges).

Key Results

MIM-Reasoner consistently matched or exceeded the influence spread of state-of-the-art methods. Notably, its parallelized architecture allows training time to remain stable or even decrease as the number of layers increases, as individual layer sub-problems are simpler to solve than the full multiplex structure.

Influence spread and running time performance

On the massive 2-million-node Pope Election dataset, traditional combinatorial algorithms failed due to memory constraints. In contrast, MIM-Reasoner completed inference in just 2.27 seconds, demonstrating exceptional scalability.

Conclusion and Future Work

MIM-Reasoner successfully bridges the gap between mathematically grounded combinatorial optimization and the scalability of deep learning. By using PGMs to "reason" about global network states, it avoids the pitfalls of redundant targeting in multiplex environments.

Future research directions include relaxing the submodularity assumption to accommodate "tipping point" influence models, improving PGM structure learning beyond tree-based dependencies, and extending the framework to dynamic networks where the graph topology evolves over time.

Summary updated

BibTeX
@inproceedings{do2024mim,
  author = {Nguyen Do and Tanmoy Chowdhury and Chen Ling and Liang Zhao and My T. Thai},
  title = {{MIM-Reasoner: Learning with Theoretical Guarantees for Multiplex Influence Maximization}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2024},
  url = {https://openreview.net/forum?id=4gjy9YPFUM},
}
Figure