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.