Joint Certification for Attributed Graphs: Beyond Topology-Only Robustness

Graph neural networks for bot and fraud detection operate on attributed graphs, where adversaries can jointly modify local edges and continuous node features. We study node-level certification under a localized mixed threat model with up to $d$ edge flips in the target message-passing neighborhood and an ${\ell }_2$ Frobenius feature budget $ϵ$. We instantiate hybrid randomized smoothing for this graph setting and derive two graph-specific certificates: a sound Sequential NP composition baseline for the joint topology–continuous-feature threat model, and a Hybrid NP certificate whose homogeneous edge-smoothing structure reduces the adversarial adjacency search to an $O(d^2)$ optimization over edge-deletion and edge-addition counts. Across PubMed, Amazon Fraud, YelpChi, and MGTAB, the Hybrid NP certificate yields non-trivial certified regions under joint perturbations. We also construct adaptive joint attacks and show failure cases on PubMed, Amazon Fraud, MGTAB and YelpChi for topology-only certified nodes, demonstrating that topology-only guarantees can overestimate robustness when continuous feature perturbations are allowed. The results support joint discrete–continuous certification as the appropriate robustness notion for attributed graphs with continuous features.