Neural Tangent Bayesian Optimization for Accurate and Efficient Influence Maximization

Influence Maximization (IM) is a critical area of research with widespread applications in viral marketing, social network recommendations, and disease containment. The primary objective of IM is to identify an optimal seed set that maximizes influence spread across networks. Traditional approaches to IM, including proxy-based, sketch-based, and simulation-based methods, each face specific limitations. Proxy-based methods often fail to capture complex seed interactions and are model-specific, sketch-based methods balance scalability with accuracy but can introduce errors, and simulation-based techniques, while accurate, are computationally intensive, particularly for large-scale graphs. Additionally, the relationship between seed set configurations and their resulting influence spreads remains largely a black box, posing significant challenges in modeling and prediction without extensive computational effort. To address these challenges, we introduce the Neural Tangent BOIM (NT-BOIM) framework, which utilizes Bayesian Optimization (BO) to reduce the number of required simulations significantly. This approach employs the Neural Tangent Kernel (NTK) as the kernel for the Gaussian Processes(GP) in our BO framework, enhancing our ability to model the complex, high-dimensional data typical of social networks. The NTK provides a robust framework to analyze and predict the training dynamics of neural networks, making it particularly effective for understanding and optimizing influence spread across different seed sets. Our NT-BOIM methodology not only enhances the performance of IM tasks but also expedites the optimization process, offering a computationally efficient alternative to traditional methods. Key innovations include designing a specialized NTK that accurately quantifies distances between seed sets in graph structures and implementing a stratified sampling technique, preceded by clustering, to ensure uniform sampling distribution within each BO iteration. Extensive empirical experiments demonstrate that our approach outperforms standard simulation methods in both effectiveness and computational speed, bridging the gap between computational efficiency and approximation accuracy. [Code] (https://github.com/XGraph-TeamlNT-BOIM).