Beyond Node Influence: Activating Nested Subgraphs in Propagation Networks

We investigate a practical yet underexplored variant of the influence maximization problem, in which the goal is to activate a given sequence of nested subgraphs as far outward as possible. A subgraph is considered activated if either it reaches a prescribed influence threshold within itself, or a larger subgraph containing it in the nested sequence is activated. We formally define this problem as Structure-Aware Influence Maximization (SAIM) , and show that it is NP-hard and its objective function is non-submodular. To tackle SAIM, we propose a decomposition framework that reduces it to a sequence of subproblems, each called Target Subgraph Activation Probability Maximization (TSAPM) . For TSAPM, we propose two oracles: a Sandwich Approximation (SA) framework with data-dependent guarantees, and a heuristic algorithm tailored to the TSAPM objective. Combined with the SA-based oracle, the overall decomposition framework provides a solution-dependent approximation guarantee for the SAIM problem. Extensive experiments on six real-world datasets validate the effectiveness and efficiency of our proposed methods.