DeepSN: A Sheaf Neural Framework for Influence Maximization

Asela Hevapathige, Qing Wang, Ahad N. Zehmakan

Abstract

Influence Maximization (IM) is a fundamental problem in network science, focused on identifying a subset of nodes (seeds) to maximize information or disease spread. Traditional Graph Neural Networks (GNNs) often struggle with non-progressive diffusion models and the combinatorial complexity of seed selection. We propose DeepSN, a framework that utilizes cellular sheaves to model influence as a reaction-diffusion process. This approach captures complex, non-linear spread patterns and heterophilic relationships that standard GNNs overlook. By combining sheaf-based dynamics with a subgraph-based optimization strategy, DeepSN achieves state-of-the-art performance across various datasets, particularly in non-progressive Susceptible-Infected-Susceptible (SIS) scenarios.

Introduction

The Influence Maximization problem asks: if you can activate $k$ individuals in a network, which $k$ will trigger the largest cascade? This task is central to viral marketing, public health, and crisis management. However, current AI-based approaches face two primary hurdles:

  1. Modeling Complexity: Standard GNNs assume uniform diffusion and often suffer from "oversmoothing," making them ill-suited for non-progressive models where nodes can return to a susceptible state.
  2. Combinatorial Explosion: The search space for optimal seed sets in large networks is prohibitively large, rendering many reinforcement learning or ranking methods inefficient.

Methodology

DeepSN addresses these challenges through a two-phase architecture: Influence Estimation and Seed Selection.

Sheaf Reaction-Diffusion

Unlike standard graph convolutions, DeepSN employs Cellular Sheaves. In this framework, each node and edge is assigned a vector space, with "transformation maps" defining the relationships between them. This allows the model to learn distinct diffusion rules for different types of interactions, effectively handling heterophily. The dynamics are governed by a Reaction-Diffusion Partial Differential Equation (PDE) consisting of:

  • Diffusion: The spread of state information across the network topology.
  • Pointwise Dynamics: Internal node behaviors, such as spontaneous recovery.
  • Coupled Dynamics: Interactions between the specific states of neighboring nodes.
Overview of the DeepSN framework, illustrating the transition from the initial graph $G$ to sheaf-based dynamics and final seed selection.

Subgraph-Based Optimization

To mitigate the computational cost of seed selection, DeepSN partitions the graph into communities using the Louvain algorithm on a weighted graph $G^w$, where weights represent learned influence strengths. A neural network then selects seeds proportionally from these subgraphs, significantly reducing the search space while maintaining high influence coverage.

Experimental Evaluation

The framework was evaluated on real-world networks (Jazz, Network Science, Cora-ML, Power Grid, Digg) and synthetic benchmarks. Diffusion models included Independent Cascade (IC), Linear Threshold (LT), and the non-progressive Susceptible-Infected-Susceptible (SIS) model.

Results and Discussion

DeepSN demonstrates significant improvements over traditional and learning-based baselines.

Performance in Non-Progressive Models

The most notable gains were observed in the SIS model. As shown in the performance comparison, DeepSN consistently achieves higher total influence across various seed set percentages. For instance, on the Jazz dataset with a 20% seed set, DeepSN reached ~85.8% influence, substantially outperforming the DeepIM baseline (~74.1%).

Comparison of total influence (%) across different datasets and seed set percentages under the SIS model.

Robustness and Sparsity

  • Depth Stability: Unlike standard GNNs that degrade with depth, DeepSN's performance improves with more layers (up to 10), allowing it to capture long-range dependencies without oversmoothing.
  • DeepSN$_{SP}$: A sparsified variant, DeepSN$_{SP}$, often outperforms the full model by filtering out noisy connections. This is evident in datasets like Cora-ML, where DeepSN$_{SP}$ achieves the highest influence at all seed percentages.

Conclusion

DeepSN provides a mathematically grounded and computationally efficient framework for Influence Maximization. By leveraging cellular sheaves and reaction-diffusion dynamics, it overcomes the limitations of traditional GNNs in modeling complex spread patterns. Future work will explore extending this framework to multi-state models and more intricate epidemic dynamics.

Summary updated

BibTeX
@inproceedings{hevapathige2025deepsn,
  author = {Asela Hevapathige and Qing Wang and Ahad N. Zehmakan},
  title = {{DeepSN: A Sheaf Neural Framework for Influence Maximization}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i16.33888},
}
Figure