Scapin: Scalable Graph Structure Perturbation by Augmented Influence Maximization

Summary: Scapin reframes perturbation for GNNs as influence-maximization, enabling scalable edge edits. Proposes edge-influence model with decomposed, submodular objectives and a submodularity-based edge addition algorithm, yielding runtime/memory efficiency. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 6649
Venue: SIGMOD
Year: 2023
Pagerank: 4.3967784e-05
Overall Rank: 9,098 | 36.71%
DOI: 10.1145/3589291

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,741	Efficient Approximation Algorithms for Minimum Cost Seed Selection with Probabilistic Coverage Guarantee	2024	SIGMOD	4.456315e-05
10,936	NPA: Improving Large-scale Graph Neural Networks with Non-parametric Attention	2024	SIGMOD	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
180	Influence Maximization: Near-Optimal Time Complexity Meets Practical Efficiency	2014	SIGMOD	0.00037135181
337	Influence Maximization in Near-Linear Time: A Martingale Approach	2015	SIGMOD	0.00027011645
2,664	Influence Maximization Revisited: Efficient Reverse Reachable Set Generation with Bound Tightened	2020	SIGMOD	8.3512717e-05
4,110	Learning to Validate the Predictions of Black Box Classifiers on Unseen Data	2020	SIGMOD	6.4428544e-05
4,165	Grain: Improving Data Efficiency of Graph Neural Networks via Diversified Influence Maximization	2021	VLDB	6.3921956e-05
4,220	Revisiting the Stop-and-Stare Algorithms for Influence Maximization	2017	VLDB	6.3493792e-05
6,158	The Solution Distribution of Influence Maximization: A High-level Experimental Study on Three Algorithmic Approaches	2020	SIGMOD	5.1800945e-05
6,526	Data Collection and Quality Challenges for Deep Learning	2020	VLDB	5.0267429e-05
6,566	Reliable Data Distillation on Graph Convolutional Network	2020	SIGMOD	5.0074274e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
3,101	Injecting Uncertainty in Graphs for Identity Obfuscation	2012	VLDB	7.5598015e-05
777	Local Graph Sparsification for Scalable Clustering	2011	SIGMOD	0.0001679862
6,153	On Data-Aware Global Explainability of Graph Neural Networks	2023	VLDB	5.1829258e-05
7,849	Demystifying Graph Sparsification Algorithms in Graph Properties Preservation	2024	VLDB	4.6362484e-05
3,087	Scalable and Efficient Full-Graph GNN Training for Large Graphs	2023	SIGMOD	7.5939896e-05
7,904	Coarsening Massive Influence Networks for Scalable Diffusion Analysis	2017	SIGMOD	4.6214923e-05
11,080	Fast and Space-Efficient Parallel Algorithms for Influence Maximization	2024	VLDB	4.1945683e-05
10,936	NPA: Improving Large-scale Graph Neural Networks with Non-parametric Attention	2024	SIGMOD	4.1945683e-05
13,174	Topology-preserving Graph Coarsening: An Elementary Collapse-based Approach	2024	VLDB	-
5,420	SCARA: Scalable Graph Neural Networks with Feature-Oriented Optimization	2022	VLDB	5.5157743e-05