SpecCert: Deterministic Joint Certification and Margin-Explicit Training for Graph Neural Networks

Graph neural networks deliver state-of-the-art accuracy in graph classification and support many real-world applications, including drug discovery, fraud detection, and malware classification. However, they remain vulnerable to adversarial perturbations on both graph structure and node features, posing serious challenges for security-critical applications. Although existing certified methods provide formal robustness guarantees through smoothing or ensemble voting, they suffer from fundamental limitations: count-based certification bounds discard confidence information, training objectives are not explicitly matched to certification margins, and topology-dependent partitioning can incur substantial overhead. In this paper, we propose SpecCert, a deterministic certification framework for graph neural networks with margin-explicit training and a confidence-weighted extension of count-based certification. Specifically, we introduce a topology-independent hash partitioning scheme that decomposes graphs into sub-views where each perturbation affects a bounded number of views. We then develop Margin-Explicit Certification Training (MECT), a differentiable surrogate objective designed to encourage larger certification-relevant margins. Finally, we derive a confidence-weighted certificate and combine it with the count-based certificate through a logically sound OR rule. SpecCert provides formal robustness guarantees under simultaneous bounded structure and node-feature perturbations. Experiments on eight benchmark datasets show that the deterministic framework provides competitive certified accuracy and substantially lower certification cost than the evaluated smoothing baselines. The confidence-weighted branch is formally valid but its empirical tightness depends on the distribution of sub-view confidences.