DeepSN: A Sheaf Neural Framework for Influence Maximization

Asela Hevapathige, Qing Wang, Ahad N. Zehmakan

Abstract

Influence Maximization (IM) is a critical task in network analysis, aiming to identify a small set of nodes that maximize information spread. Traditional methods struggle with non-linear dynamics and computational complexity. We present DeepSN, a novel framework that leverages cellular sheaves and reaction-diffusion dynamics to model complex node interactions. By partitioning the network into dynamics-aware subgraphs, DeepSN efficiently identifies optimal seed sets. Our evaluation across diverse datasets demonstrates that DeepSN significantly outperforms state-of-the-art methods, particularly in non-progressive scenarios like disease spread.

Introduction

Influence Maximization (IM) involves finding a small set of "seed" nodes in a network that, when activated, trigger the largest possible spread of information or behavior. This has massive implications for viral marketing, public health (disease control), and social media management.

Existing approaches face two major hurdles. First, modeling complexity: traditional Graph Neural Networks (GNNs) often assume homophily (neighbors are similar) and suffer from over-smoothing, making them poor at modeling the dynamic, non-linear nature of real-world influence. Second, combinatorial explosion: finding the absolute best seed set is NP-hard. As networks scale to millions of nodes, searching for the optimal combination becomes computationally prohibitive without advanced heuristics.

Methodology

DeepSN introduces a two-phase approach: Learning to Estimate Influence and Optimizing Seed Selection.

1. Sheaf Reaction-Diffusion

Unlike standard GNNs that use a single feature space for the whole graph, DeepSN utilizes Cellular Sheaves. In this framework, every node and edge can have its own vector space, connected by transformation maps. This allows the model to learn specific trust or confidence levels between individual pairs of nodes, effectively breaking the homogeneity assumption of standard GNNs.

To capture dynamic behaviors, the model implements a Reaction-Diffusion process:

  • Diffusion: Models the spread of information across the network structure.
  • Pointwise Dynamics: Models internal node changes (e.g., a person changing their mind independently).
  • Coupled Dynamics: Models the combined impact of having both activated and susceptible neighbors.
DeepSN Architecture: (a) Sheaf Diffusion-Reaction modeling and (b) Subgraph-based optimization.

2. Subgraph-Based Optimization

To solve the seed selection problem, DeepSN creates a weighted graph based on the learned sheaf coefficients. It then uses the Louvain algorithm to partition this graph into communities (subgraphs). By selecting seeds proportionally from these distinct communities, the model avoids "overlapping influence"—where two seeds wastefully target the same group—and drastically reduces the search space.

Experimental Evaluation

The framework was evaluated on six diverse datasets, including social networks (Jazz, Digg), citation networks (Cora-ML), infrastructure (Power Grid), and large-scale synthetic graphs. These range from small networks of 198 nodes to systems with over 279,000 nodes.

Key Results

DeepSN consistently outperformed baselines like IMM, OPIM, and DeepIM across Independent Cascade (IC) and Linear Threshold (LT) models. A standout result was observed in the non-progressive SIS model (Susceptible-Infected-Susceptible), where nodes can recover and become susceptible again. DeepSN showed a substantial improvement over all baselines, proving its superior ability to model complex, recurring dynamics.

Comparison of Mean Absolute Error (MAE) for influence estimation across various datasets and models (LT and SIS). DeepSN consistently achieves the lowest error.

Furthermore, experimental results confirmed that the sheaf-based approach maintains feature separability even as the network depth increases, whereas traditional GNNs (GCN, GAT) saw performance drops due to over-smoothing. The sparse variant, DeepSN-SP, maintained high accuracy while significantly reducing computational overhead on large graphs like Digg.

Conclusion

DeepSN represents a significant step forward in influence maximization by moving beyond simple topological connectivity to dynamics-aware partitioning. By using sheaf theory, the model can represent heterophily—situations where a node might actively resist the influence of a specific neighbor. While currently limited to two-state diffusion models (e.g., Active vs. Inactive), future work will focus on extending the framework to handle multi-state dynamics like S-I-R models and more complex topological structures.

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