SMaRS-GNN: A Scalable and Robust Graph Neural Network Integrating Higher-Order Information

Growing concerns about the computational and energy demands of artificial intelligence motivate more efficient learning methods. For graph classification, the challenge is to reduce computational cost while retaining information across higher-order neighborhoods and maintaining robustness to perturbations. In this paper, we introduce a new method called SMaRS-GNN to address this problem. Under this method, a graph representation is constructed for each actor from the dominant right singular vector of its node embedding matrix, and a critic model provides weights that combine these representations for classification. The training step uses randomly sampled subgraphs instead of the full graph, which leads to computational scalability. We establish finite sample bounds on the perturbations in normalized feature Gram matrices caused by subsampling, accounting for node sampling and recomputed message passing. Under standard regularity conditions, we establish theoretical bounds that yield stability guarantees for pooled representations and predicted labels. We further prove a risk transfer bound that preserves generalization guarantees up to explicit subsampling and optimization terms, as well as a bound that establishes actor-level robustness to feature perturbations. Experiments on simulated and benchmark datasets demonstrate substantial reductions in runtime and characterize the tradeoffs among computational efficiency, predictive accuracy, and robustness across various model settings and algorithmic hyperparameters.