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.
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.
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