Neural Probabilistic Relational Games (N-PRG): Learning Influence Coalitions from Cascade Data via Gradient Descent

Abstract

Influence maximisation traditionally assumes that each activated neighbour contributes independently to the likelihood of a user adopting information, ignoring conjunctive synergies where a set of users must be active simultaneously to trigger another. Relational games provide a formal language for such coalitional dependencies, but the necessary influence hypergraph must be hand-crafted by domain experts, making them infeasible for large, dynamic social networks. We introduce the Neural Probabilistic Relational Game (N-PRG), a data-driven framework that automatically learns a probabilistic hypergraph of influence coalitions from cascade traces. A feed-forward neural network, trained via gradient descent to predict user activation, is interpreted using Deep SHAP to extract important set-level triggers. These are calibrated into a stochastic cascade model, the Probabilistic Relational Game (PRG), which generalises the Independent Cascade to set-based activation. We define the Minimal Reliable Seed Set problem, prove its NP-hardness even in the deterministic case, and establish that the expected influence function is monotone. We further demonstrate that, unlike the Independent Cascade model, the influence function under conjunctive (AND-type) hyperedges is in general not submodular, which precludes constant-factor approximation guarantees and motivates the use of greedy heuristics. Extensive experiments on synthetic data confirm that N-PRG successfully identifies coalitional interactions of size greater than one and achieves targeted out-of-sample coverage. Semi-synthetic experiments on Digg and Twitter network topologies demonstrate that N-PRG discovers seed sets up to 45% smaller than Independent Cascade baselines, while providing interpretable coalition pathways invisible to black-box methods. N-PRG thus unites the flexibility of gradient-descent learning with the structural rigour of relational games for influence analysis.