acceptodds
Withdrawn from ICLR 2027

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

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

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.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Graph Neural Networks, Certified Robustness, Adversarial Robustness, Graph Certification, Adversarial Attacks, Robust Machine Learning

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_xUwkOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

This paper introduces SpecCert, a deterministic certified defense framework for Graph Neural Networks (GNNs) against bounded structural (edge insertion/deletion) and feature perturbations.

Critical strengths

Unlike standard cross-entropy training which is indifferent to the vote margin, MECT explicitly optimizes a differentiable surrogate of the vote margin consumed by the certificate. This design directly targets the training–certification objective mismatch present in existing defenses.

Critical weaknesses

Equation (5) combines standard cross-entropy, label smoothing, sub-view consistency regularization, and MECT. The paper does not thoroughly isolate the individual impacts of label smoothing and consistency regularization versus MECT alone on final clean and certified accuracy.

The datasets used are outdated, there are more recent benchmark and GNN architectures; eg, Long range benchmarks

Questions for authors

Since the confidence-weighted branch currently yields conservative bounds due to raw softmax confidence distributions, did you experiment with temperature scaling or conformal calibration techniques on the sub-views prior to certification? Could such calibration restore tightness to the weighted branch?

Reviewer_73GwOpenReview ↗
Rating
1
Confidence
4
Informativeness
2
Presentation
3
Soundness
1
Read review
Paper summary

This work proposes a new derandomized smoothing method for provably robust graph classification.

Concretely, the authors propose a specialized partition-based procedure that incorporates both hard class labels and softmax scores. This method is intended to provide provable guarantees against modification of a bounded number of edge insertions/removals and node attribute vector substitutions. The inference procedure is composed of the following steps:

  • The original graph GG is partitioned into subgraphs {Gt}\{G_t\} using a hashing operation that is independent of graph topology or node attributes.
  • An arbitrary base classifier fθ:G→ΔC−1f_\theta:\mathcal{G} \rightarrow \Delta_{C-1} is applied to each partition GtG_t to obtain both hard class labels q(Gt)=argmaxfθ(Gt)q(G_t) = \mathrm{argmax} f_\theta(G_t) and associated softmax scores κ(Gt)=fθ(G′)[q(Gt)]\kappa(G_t) = f_\theta(G')[q(G_t)].
  • Then, two smoothed predictions are mode: The first one is a simple majority vote argmax∑GtI[q(Gt)=c]\mathrm{argmax} \sum_{G_t} I[q(G_t) = c]. The second, novel one is a confidence-weighted voted argmax∑GtI[q(Gt)=c]\mathrm{argmax} \sum_{G_t} I[q(G_t) = c].

For the standard majority vote, the authors propose to improve smoothed utility as follows: Instead of simply training fθf_\theta on different subgraphs GtG_t, they propose to directly train the smoothed classifier while maximizing certificate strength (margin between majority and runner-up class) via a new auxiliary loss ("MECT").

For their novel confidence-weighted voting scheme, the authors derive a robustness certificate. They further show how it can be combined with the standard majority voting certificate into a joint certificate ("SpecCert") via conjunction.

The overall method is evaluated on common graph classification datasets to two baselines using majority-voting and different smoothing distributions: Another hash-based derandomized smoothing method (GNNCert) and random edge insertion/removal (sparsity-aware smoothing).

The method compares favorably w.r.t. certified accuracy. Both the auxiliary loss (MECT) and enhanced certificate (SpecCert) are ablated and found to be beneficial.

Critical strengths

Potential impact beyond graphs

The novel confidence-weighted smoothing scheme is well-motivated and the corresponding certificate appears sound. While this particular work focuses on graph classification and graph partitions, it should be applicable to arbitrary domains and partitioning schemes. As such, it may be of broader interest, e.g., for proving poisoning robustness where partition-based smoothing is still the state of the art.

Well-founded paradigm for improving robustness-utility-tradeoff

In addition to deriving a new smoothing scheme and certificate, the authors also propose a general, well-motivated method for improving smoothed utility in traditional majority voting. As before, this contribution has potential impact across various domains and methods relying on partition-based certification.

Critical weaknesses

Main contribution is unsound

The intended main contribution is to combine majority voting and confidence weighted certificate "through a logically sound OR rule".
However, the overall certificate (Eq. 7) only shows that either the majority vote is robust or the confidence-based vote is robust (Lemma 3.3). In practice, however, it is not sufficient for our model to output two different labels and to certify that at least one of them is robust. Instead, the predictions of multiple smoothed models need to be reconciled into a single predicted label which must then be certified (see, e.g., Table 1 in [1]).

Beyond theoretical soundness, this issue also puts into question the validity of the experimental results, which use this "OR" construction that may incorrectly inflate the certified accuracy.

Treatment of prior work

The manuscript omits directly related work, overclaims novelty compared to prior work, and underclaims the capabilities of baselines.

Omission: "Certifying confidence via randomized smoothing" [2], which also uses confidence-based voting (albeit via the argmax of expected softmax scores) is the most obvious point of comparison but not cited or compared against.

Overclaimed novelty: Secondly, the proposed "topology-blind partitioning", which is listed as a main contribution, appears like a direct application of the methodology developed in GNNCert [3]. The main contribution there was that it is possible to define a data-independent (topology-blind) graph partitioning to enable derandomized smoothing. It appears like the authors simply instantiate this method with another hash function without correctly attributing it to prior work [3]. Furthermore, the choice of hash function is not motivated and the corresponding explanations are hard to follow.

Underclaiming baseline capabilities: The authors incorrectly state in both related work and experimental setup that certain baselines were not capable of simulatenously certifying robustness to attribute and adjacency perturbations, claiming this as a core contribution. However GNNCert [3] is explicitly designed to simultaneously certified both (see their Section 3.2). Sparsity-aware smoothing [4] can certify structure and feature perturbations via simultaneousy perturbation of the adjacency and attribute matrix (see their Section 6.1).


References:

[1] Nandi et al. Certified Adversarial Robustness Within Multiple Perturbation Bounds. CVPRw 2023.
[2] Kumar et al. Certifying Confidence via Randomized Smoothing. NeurIPS 2022
[3] Xia et al. GNNCert: Deterministic Certification of Graph Neural Networks against Adversarial Perturbations.
[4] Bojchevski et al. Efficient Robustness Certificates for Discrete Data: Sparsity-Aware Randomized Smoothing for Graphs, Images and More. ICML 2020.

Questions for authors
  • How do you combine the two smoothed predictions (majority vote and confidence-weighted) into a single prediction. How is it certified?
  • Assuming we only use majority voting and the standard LCEL_\mathrm{CE} objective. How is this work different from GNNCert beyond using a different hash function. If it's otherwise identical, why this specific hash function?
  • What is the benefit of using confidence-weighted voting over voting based on expected confidence[2]? Either theoretically or empirically.
  • Is the claim that GNNCert and sparsity-aware smoothing "certify only structure perturbations and cannot guarantee robustness against feature manipulations" (ll.57-58) actually correct?
Reviewer_8uCeOpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

SpecCert studies deterministic robustness certification for graph classification under edge and node-feature perturbations. It combines hash-based graph partitioning and majority voting with a margin-oriented training objective, MECT, and an additional confidence-weighted certificate. Experiments compare certified accuracy and computational cost against deterministic and randomized certification baselines.

Critical strengths

The framework provides explicit sufficient conditions for robustness under joint structure-feature perturbations.

The implementation reduces computational costs for certification, especially at the test stage.

The manuscript includes component ablations and acknowledges the limited empirical benefit of the confidence-weighted branch.

Critical weaknesses

The contribution beyond existing deterministic majority-vote certification appears limited. The central certification mechanism is already represented in existing work. The count-based certificate retains the same basic argument. The additional weighted certificate is individually sound, but does not establish a generally stronger bound, and Figure 10 shows that the OR combination largely coincides with the standard certificate. Consequently, this component does not demonstrate a substantive improvement in certification performance.

The empirical evidence does not establish training-certification mismatch as a major bottleneck. MECT is a reasonable differentiable surrogate, but cross-entropy already encourages correct and confident predictions, and increasing the surrogate does not guarantee an increase in the discrete certified margin.

The source of the overall gains over baselines is insufficiently isolated. The framework also includes label smoothing, an optional consistency regularizer, implementation optimizations, and optional multi-seed ensembling. Their individual contributions are not fully separated. A controlled comparison matching the training recipe, ensemble size, and computational budget is needed to identify the benefit attributable to the proposed components.

Questions for authors

Please see weaknesses

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

Related papers

Discussion (0)

Sign in to comment.