Evolutionary Hypergraph Learning: A Multi-Objective Influence Maximization Approach Considering Seed Selection Costs

Influence maximization (IM) has been extensively studied due to its wide range of applications in scenarios such as transportation networks. In existing studies, the IM problem is primarily modeled by graphs, aiming to maximize influence spread only. However, graph-based modeling struggles to capture higher-order relationships between nodes. This becomes even more serious if seed selection costs are limited. Due to the strong coupling of high-order relationships between nodes and the complexity of propagation dynamics in a hypergraph, balancing the trade-off between the influence spread and seed selection costs remains a significant challenge. In this paper, we propose an evolutionary multi-objective approach to handling this challenge. The IM problem is formulated as a multi-objective optimization problem, where a low-complexity objective function is designed to optimize the influence spread, effectively leveraging the structural information of two-hop neighboring nodes to approximate the collective influence of the seed set. A novel population initialization method and mutation operator are proposed to accelerate the convergence speed while maintaining population diversity to prevent solutions from being trapped in local optima. Experiments on both synthetic and real-world hypergraphs demonstrate that the proposed method can obtain widely distributed non-dominated solutions, offering diverse options to balance the influence spread and seed selection costs.