acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Graph neural networks, graph classification, robust singular pooling, actor-critic network, graph subsampling

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_YL8pOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes a computationally efficient graph classification framework that combines the multi-order actor representations, singular pooling and subgraph training. It argues that the theoretical conditions for sampling to preserve the propagated feature Gram matrices and the generalization and prediction stability guarantees for graph representations. Furthermore, substantial reduction of the training time demonstrated in real world datasets.

Critical strengths

The paper addresses the practical challenge of reducing the training cost of GNN through the subgraph sampling while retaining the useful graph information. This is interesting since the higher order neighborhood aggregation can increase computational cost in large graphs.

In Theorem 3.2, the authors shows theoretical guarantees connecting Gram-matrix preservation to singular-pooling representation stability and consistent classification predictions under certain conditions. This helps explain how subgraph sampling affects the model's predictions.

The paper proves the conditional generalization guarantees for subgraph trained models and actor level stability bounds under feature perturbations. These findings support the theoretical analysis characterize the generalization for unseen full graphs and identifying conditions under which singular-pooling representations remain stable.

Critical weaknesses

In Theorem 3.1 qd_min≥12 log⁡(2m/η_d ) requires a sufficiently large minimum sampled degree. How applicable is this condition to real-world sparse graphs, and can the theoretical analysis be extended to graphs with low-degree nodes.

Theorem 3.3 establishes an O(n^(-1/2)) generalization rate by assuming that several error terms already decrease at this rate (G2-G4). However, the sampling discrepancy is not guaranteed to decrease with the number of training graphs at a fixed sampling ratio it is unclear whether these assumptions hold for the proposed SMaRS-GNN architecture and training procedure.

Empirical experiments accuracies of SMaRS_GNN for all the datasets do not outperform the MaRS baseline models like RS_GCN event if it achieves a reduction of training time. Therefore, the practical value of the computational cost reduction become less meaningful when the prediction accuracy declines considerably.

Experiments are conducted only on three real world datasets (Reddit-B, D&D, and PROTEINS), and D&D and PROTEINS contain protein-structure graphs. This make limited the diversity of the datasets and difficult to asses the generalizability and other measures claimed by the authors. More diverse graph classification datasets may strengthen the authors claims.

Questions for authors

Theorem 3.2 states the accuracy guarantee for the sampled and full graph with a fitted classifier. However, the experiments compare separately trained models. It is less clear how does this relate to the performance of the models trained on sampled subgraphs versus full graphs? For Other questions please see Weaknesses

Reviewer_v4vcOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper proposes SMaRS-GNN, a graph classification framework combining multi-order actor representations, singular-vector pooling, and induced-subgraph training.

Critical strengths

The authors develop a clear theoretical framework that proceeds from Gram-matrix perturbation analysis to singular-vector pooling stability, logit stability, prediction stability, and risk transfer. In particular, distinguishing the error caused by node subsampling from that introduced by recomputed message passing is a well-motivated aspect of the theoretical design.

Critical weaknesses
  1. The proposed method mainly combines the multi-order actor–critic framework from MaGNet, the singular-vector pooling mechanism from RS-Pool, and conventional subgraph sampling. Such a combination of existing techniques offers limited methodological novelty. The paper would benefit from emphasizing its theoretical analysis as the main contribution. Accordingly, the authors should substantially revise the motivation and overall organization of the paper to better highlight its theoretical contributions.

  2. The paper lacks a systematic ablation study that isolates the contributions of individual components within the same framework. For example, the authors could compare RS-Pool with Mean/Max Pooling while keeping the multi-order architecture and sampling strategy fixed, remove the multi-order actors and use only a single neighborhood order, or compare different sampling strategies under the same model configuration.

  3. On real-world datasets, although SMaRS-GNN reduces training time compared with MaRS-GNN, it also suffers from substantial drops in classification accuracy. The authors should further justify whether this trade-off between computational efficiency and predictive performance is practically meaningful.

Questions for authors

Could the authors clarify why the terms “Actor” and “Critic” are used in this paper? What similarities do these components share with the conventional definitions of actors and critics in RL? If there is no direct connection, what motivates the use of this terminology?

Reviewer_idAmOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This work introduces SMaRS‑GNN for graph classification, combining MaGNet and RS‑Pool and training on randomly sampled induced subgraphs. It provides finite‑sample theoretical bounds including a useful decomposition separating degree renormalisation and message‑sampling error. Experiments are conducted on synthetic and TU datasets evaluating clean, perturbed, PGD robustness and training speed. While parts of theory are solid, experiments suffer from missing external baselines, contradictory robustness results against internal full‑graph baseline, unexplained speedups and poor reproducibility reporting. I give a weak reject.

Critical strengths
  1. Proposition B.4 is a valuable technical contribution: it decomposes propagation error into degree‑renormalisation and message‑sampling components, an aspect mostly ignored in prior subgraph‑sampling theory.
  2. The paper properly clarifies limitations of its theoretical guarantees, distinguishes bounds for same‑model vs cross‑model comparison and avoids over‑claiming universal speedup. My rejection is based on empirical issues, not theoretical flaws.
Critical weaknesses
  1. No published external baselines (GraphSAINT, FastGCN etc. are cited but not run). PGD robustness results contradict the title: SMaRS‑GNN underperforms full‑graph MaRS and RS‑GCN on two out of three datasets. The D&D Av‑GCN PGD accuracy (7.3%) hints at a degenerate attack setting. The “robust” title needs explicit qualification.
  2. Reported speed‑up numbers cannot be justified by the given cost model. Training iterations/stopping criteria are missing; speed gains may come from early‑stopping rather than subgraph sampling. Timing only counts training cost, ignoring full‑graph inference at test time.
  3. Critical hyperparameters, seeds, hardware, standard deviations and statistical significance tests are missing, hurting reproducibility.
  4. Provenance concern: it is unclear whether experimental tables are regenerated for this submission.
Questions for authors
  1. Add at least one external subgraph‑sampling baseline and one robust‑GNN baseline. Document full PGD attack hyperparameters. Under what definition does the “robust” title hold given worse PGD performance on 2/3 datasets? Explain D&D Av‑GCN’s very low PGD accuracy.
  2. Report epochs/iterations, per‑epoch runtime and clarify whether timing accounts for full‑graph test‑time inference. State explicitly if speed‑up partially arises from early stopping.
  3. Complete missing hyper‑parameters, seeds, hardware. Provide std and significance tests for Tables 1‑2. Are small PGD improvements statistically meaningful?
  4. Confirm theoretical bounds are conditional and do not automatically hold for benchmark graphs. Is a fixed anchor used to satisfy Theorem 3.2’s sign convention?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.