DeepSN: A Sheaf Neural Framework for Influence Maximization
Asela Hevapathige, Qing Wang, Ahad N. Zehmakan · 2024
Read DeepSN: A Sheaf Neural Framework for Influence Maximization by Asela Hevapathige, Qing Wang, Ahad N. Zehmakan (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-12416.txt.
Introduction
Asela Hevapathige, Qing Wang, and Ahad Zehmakan pick the best seed users to spread a message through a social network, in a 2024 paper. This influence maximization problem drives viral marketing and network analysis. Learning-based methods promise to adapt to each network's own spread patterns. Two gaps persist: standard graph networks miss the tangled dynamics of diffusion, and choosing seeds faces a combinatorial explosion.
Their framework, DeepSN, learns spread with sheaf neural diffusion, which separates influence patterns more sharply. A new optimization step accounts for overlap between users' spheres of influence, shrinking the search for the seed set. Tests on synthetic and real networks show the framework finds effective seeds efficiently. The authors present it as end-to-end learning for a classic hard problem.
Catalog record
| CREATOR | Asela Hevapathige, Qing Wang, Ahad N. Zehmakan |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 53 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-12416
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
DeepSN: A Sheaf Neural Framework for Influence Maximization Asela Hevapathige, Qing Wang, Ahad N. Zehmakan Abstract Influence maximization is key topic in data mining, with broad applications in social network analysis and viral marketing. In recent years, researchers have increasingly turned to machine learning techniques to address this problem. They have developed methods to learn the underlying diffusion processes in a data-driven manner, which enhances the generalizability of the solution, and have designed optimization objectives to identify the optimal seed set. Nonetheless, two fundamental gaps remain unsolved: (1) Graph Neural Networks (GNNs) are increasingly used to learn diffusion models, but in their traditional form, they often fail to capture the complex dynamics of influence diffusion, (2) Designing optimization objectives is challenging due to combinatorial explosion when solving this problem. To address these challenges, we propose a novel framework, DeepSN. Our framework employs sheaf neural diffusion to learn diverse influence patterns in a data-driven, end-to-end manner, providing enhanced separability in capturing diffusion characteristics. We also propose an optimization technique that accounts for overlapping influence between vertices, which helps to reduce the search space and identify the optimal seed set effectively and efficiently. Finally, we conduct extensive experiments on both synthetic and real-world datasets to demonstrate the effectiveness of our framework. Introduction Influence maximization (IM) is a challenging network science problem that involves identifying a set of vertices which, when activated, maximize the spread of influence across the network. IM has significant real-world applications including viral marketing ( Li, Lai, and Lin 2009 ; Kempe, Kleinberg, and Tardos 2003 ) , disease control ( Marquetoux et al. 2016 ) , social media content management ( Hosseini-Pozveh, Zamanifar, and Naghsh-Nilchi 2017 ) , and crisis communication ( Fan, Jiang, and Mostafavi 2021 ) . Despite decades of research, IM still remains challenging primarily due its exponentially large search space and the complex nature of the influence diffusion processes. A plethora of traditional methods have been proposed to obtain optimal or near-optimal solutions for IM ( Kempe, Kleinberg, and Tardos 2003 ; Leskovec et al. 2007 ; Wang et al. 2010 ; Tang, Shi, and Xiao 2015 ; Li et al. 2019 ) . These methods vary in strategy and effectiveness: some offer theoretical performance guarantees, while others use heuristics to enhance scalability. A common trait among these traditional approaches is their reliance on the explicit specification of the influence diffusion model as input. Recently, researchers have turned to learning-based methods focusing on their ability to automatically identify the diffusion model from the ground truth and accommodate multiple diffusion models, thereby achieving broader applicability ( Li et al. 2023 ) . Learning-based approaches for IM encounter two key challenges. (1) Effectively modeling the underlying diffusion model from ground truth: There is a growing interest in leveraging Graph Neural Networks (GNNs) for modeling influence propagation, due to their ability to capture structural insights in networks ( Kumar et al. 2022 ; Ling et al. 2023 ; Panagopoulos et al. 2023 ) . However, existing work relies on traditional GNN techniques like attention ( Lee et al. 2019 ) and convolution ( Zhang et al. 2019 ) . While these traditional GNNs excel in tasks with a static nature such as vertex classification and graph regression, their inductive bias and inherent assumptions limit their ability to model the dynamic behaviors of influence diffusion. They also suffer from issues like over-smoothing ( Chen et al. 2020 ) which hampers their capacity to capture global information and long-range dependencies crucial for influence diffusion ( Xia et al. 2021 ) . (2) Identifying the optimal subset of vertices with maximal Influence: Designing an optimization objective to select the optimal seed set is arduous due to the vast search space, especially in large networks. Existing learning-based approaches often use deep reinforcement learning ( Li et al. 2022 ; Chen et al. 2023 ) and ranking-based methods ( Kumar et al. 2022 ; Panagopoulos, Malliaros, and Vazirgianis 2020 ) to approximate the optimal seed set. However, these methods often incur significant computational costs and suffer from a lack of interpretability. Our work addresses the limitations of existing approaches by leveraging sheaf theory ( Tennison 1975 ; Bredon 2012 ) , an algebraic-topological framework that captures the topological and geometric properties of complex networks, essential for understanding dynamic processes. Current sheaf diffusion GNNs ( Hansen and Gebhart 2020 ; Bodnar et al. 2022 ; Barbero et al. 2022 ) are limited by their homogeneous diffusion behaviors and inability to handle the evolving dynamics crucial for influence propagation. To tackle this, we propose DeepSN , a novel sheaf GNN framework designed to address the influence maximization problem. Our architecture effectively estimates diverse influence propagation processes by learning adaptive structural relationships between vertices, enabling effective identification of influence patterns in the network. Building on this, we design a seed set inference mechanism that uses subgraphs to efficiently reduce the search space in influence maximization. Our contributions are summarized as follows. • Influence Diffusion: We redefine influence propagation as a sheaf diffusion-reaction process, capturing the intricate dynamics found in real-world diffusion models. • GNN Architecture: We propose a novel GNN architecture rooted in sheaf theory, designed to capture the unique nuances of influence propagation. • Seed Selection: We use a subgraph-based strategy leveraging the structural insights from our sheaf GNN to minimize overlapping influence among seed vertices, thereby reducing the search space for influence maximization. • Experiments: We rigorously evaluate our framework on both real-world and synthetic datasets, demonstrating superior performance and generalizability over state-of-the-art methods. Related Work Influence Maximization Methods IM methods generally fall into two main categories: traditional and learning-based. Traditional approaches include simulation-based, proxy-based, and sketch-based methods ( Li et al. 2018 ) . Simulation-based methods rely on Monte Carlo simulations for stochastic evaluation with theoretical guarantees, while proxy-based methods use heuristics for efficient seed set approximation. Sketch-based methods combine both simulation and proxy methods, balancing theoretical guarantees and computational efficiency. For detailed discussions on these traditional methods, see the surveys by Li et al. 2018 and Banerjee, Jenamani, and Pratihar 2020 . Contrary to traditional methods that require a specific diffusion model as input, learning-based models excel in generalizability, adapting to multiple diffusion models. Several studies have leveraged deep reinforcement learning for this problem ( Li et al. 2022 ; Ma et al. 2022 ; Wang et al. 2021 ; Chen et al. 2023 ) , and some works explored the use of GNNs in this context ( Xia et al. 2021 ; Kumar et al. 2022 ; Ling et al. 2023 ; Panagopoulos et al. 2023 ) .However, reinforcement learning methods often face scalability challenges due to exploration complexity, limiting their application in large-scale networks. Meanwhile, GNNs typically rely on traditional architectures that struggle to capture dynamic diffusion phenomena and mainly focus on progressive models, limiting their adaptability to non-progressive scenarios. Our work breaks from these limitations by incorporating an inductive bias guided by diffusion-reaction processes, which is capable of modeling both information diffusion and intrinsic transformations that occur during the diffusion process. This allows us to effectively model complex propagation patterns in both progressive and non-progressive spread dynamics. Diffusion GNNs A diffusion process typically refers to the spread of