Provably Robust Explainable Graph Neural Networks against Graph Perturbation Attacks

Binghui Wang; Jiate Li; Jinyuan Jia; Meng Pang; Yun Dong

REVIEW 2 major objections 5 minor 1 cited by

Provably Robust Explainable Graph Neural Networks against Graph Perturbation Attacks

T0 review · 2 major / 5 minor · reviewed 2026-08-08 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read XGNNCert claims the first deterministic certificate for GNN explanations: bounded edge perturbations cannot change the majority-vote prediction or wipe out the top-k explanation.

desk verdict First certified defense for GNN explainers, with a real gap between the formal threat model and the proof; fix Definition 1 and the paper holds up. read the letter →

arxiv 2502.04224 v1 pith:UX3DG6TD submitted 2025-02-06 cs.CR

Jiate Li , Meng Pang , Yun Dong , Jinyuan Jia , Binghui Wang This is my paper · ORCID

classification cs.CR MSC 68T0768R10

keywords certifiedrobustnessgraphneuralnetworksGNNexplainabilityperturbationattacksmajorityvotinghash-basedsubgraphpartitionadversarialXGNNCert

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

XGNNCert establishes the first provable robustness guarantee for an explainable graph neural network. For any graph perturbation attack that changes at most $M_\lambda$ edges, it certifies that the majority-vote GNN prediction is unchanged and that the voting explainer still returns at least $\lambda$ of the $k$ explanatory edges found on the clean graph. The certificate is deterministic, not probabilistic, and is computed from vote margins on a hash-based partition of the graph into hybrid subgraphs. This matters because existing certified defenses protect GNN classifiers but not their explanations, and empirical explanation defenses have been broken by stronger attacks; safety-critical users of GNN explanations would gain an a-priori bound on how much tampering an explanation can survive.

What carries the argument

The load-bearing object is hybrid subgraph generation via a hash function $h$ that maps each edge $(u,v)$ to a bucket $h[\mathrm{str}(u)+\mathrm{str}(v)] \bmod T + 1$, which is deterministic and independent of the graph structure. Each subgraph $G^i_H$ contains the original edges in bucket $i$ plus a random fraction $p$ of the complete-graph subgraphs in other buckets; because the complete graph is fixed, $M$ edge perturbations corrupt at most $M$ hybrid subgraphs. The voting explainer $\bar{g}_\gamma$ then counts, for every edge in the complete graph, how many winning-class hybrid subgraphs give it an importance score in the top $\gamma$ fraction, and the output is $E.\mathrm{topk}(n^\gamma)$. The vote margins $n_y - n_b$ and $n^\gamma_l - n^\gamma_{h_M}$ are what make the certificate computable from a single clean forward pass.

What would settle it

Run XGNNCert on a graph whose ground-truth explanation is a single edge, then delete exactly that explanatory edge (budget $M=1$). The perturbed graph lacks the edge, so no top-$k$ output can contain it, and any certificate with $\lambda \ge 1$ is contradicted; this test isolates whether the formal claim includes explanatory-edge deletions.

Watch

Extended reading notes

Core claim

The central discovery is a way to convert any stable edge-scoring explainer into a certified explainer without changing its training objective. The graph's edges are hashed into $T$ buckets, and each bucket becomes a hybrid subgraph containing the original edges in that bucket plus a random fraction $p$ of the complete graph's edges from other buckets; the complete-graph part is what lets non-existent edges compete for explanation votes. A voting classifier runs the base GNN on every hybrid subgraph, and a voting explainer counts, over hybrid subgraphs that predicted the winning class, how often each edge's importance score reaches the top $\gamma$ fraction, then outputs the top-$k$ counts. The paper proves that $M$ edge perturbations change at most $M$ hybrid subgraphs (Theorem 2), and derives the certified budget $M_\lambda \le \min(\lfloor (n_y - n_b + I(y<b) - 1)/2 \rfloor, M_h)$, where the first term keeps the prediction stable and $M_h$ is the largest budget satisfying $n^\gamma_l - n^\gamma_{h_M} + I(l<h_M) > 2M$ so that at least $\lambda$ explanation edges survive (Theorem 3).

Load-bearing premise

The whole certificate depends on the attacker never deleting an explanatory edge, since a deleted edge is absent from the graph and can never appear in the output explanation; the paper states this informal restriction but the formal definition and abstract say 'any' perturbation.

Editorial extensions

If this is right

A deployer who knows the clean vote margins can publish a certificate $(M_\lambda, \lambda)$ before any attack happens, and the certificate holds against worst-case edge additions and deletions up to budget $M_\lambda$.
The same voting wrapper can be applied to any GNN classifier and any GNN explainer that outputs edge importance scores, so the method is not tied to one explanation algorithm.
Choosing more hybrid subgraphs $T$ tends to enlarge the certified perturbation size, but at the cost of clean explanation accuracy and $T$-fold computation; the paper reports a tradeoff rather than a free win.
Without the complete-graph information ($p=0$), the certified perturbation size collapses to zero, so the hybrid subgraphs are the load-bearing part of the guarantee.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

My inference: because the hash function keys on node indices, the certificate is node-order dependent; in deployment one would fix a canonical ordering, and anyone choosing the ordering after seeing the graph could alter the vote margins.
My inference: the hybrid-subgraph trick should transfer to node-level explanations if a division keeps the target node in every subgraph; the paper notes this adaptation is open, and the key check would be whether the 'at most $M$ corrupted subgraphs' bound survives.
My inference: the margin formula turns explanation robustness into a quantity one can inspect before attack: graphs whose explanation votes are concentrated on a few edges will tolerate larger budgets, which could serve as a cheap screening test during model selection.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Here's my read on XGNNCert.

The core claim is genuinely new: this is the first certified robustness guarantee for a GNN explainer, as opposed to a GNN classifier. The hybrid subgraph construction—mixing the original graph's subgraphs with subgraphs from the complete graph—is a clever way to make partition-and-vote work for edge explanations, and the deterministic certificate is a clean margin argument. The appendix proofs are standard and, under the intended threat model, correct. The paper also ships code and evaluates across several datasets and explainers.

The soft spot is the threat model. Definition 1 says 'any graph perturbation attack,' but the proof and the output operation E.topk require that no explanatory edge be deleted. If an attacker deletes an edge in Ek, that edge cannot appear in the perturbed output, so the λ-overlap guarantee fails for λ ≥ 1. Section 2 does informally restrict the attacker to not deleting explanatory edges (for stealthiness), but the formal definition, abstract, and evaluation language drop that restriction. This is an overclaim, not a fatal flaw: the fix is to state the non-deletion condition explicitly in Definition 1 and in all summary claims.

There is a secondary overclaim in the evaluation. Section 4.1 defines certified explanation accuracy as λ edges 'from the groundtruth,' but Theorem 3 only certifies overlap with the clean explanation Ek. Since clean explanation accuracy is moderate (e.g., 0.74 on SG+House with PGExplainer), the end-to-end guarantee is weaker than the text suggests. Again, correctable by rewording.

The node-order variance issue is acknowledged and empirically shown to be stable, which I find acceptable for a first result. The complexity of enumerating complete-graph edges is high for large graphs, but the paper is honest about the tradeoff.

Overall, this paper is for researchers in explainable GNNs and adversarial robustness. The central idea survives the critique; the flaws are in the presentation of the guarantee, not in the math. I would send it to a serious referee and expect a revision rather than a rejection. It would also be a good reading-group paper, because the mismatch between the formal threat model and the proof is a useful lesson in how to specify attack models.

Referee Report

2 major / 5 minor

Summary. The paper proposes XGNNCert, a defense that gives deterministic certified robustness guarantees for GNN explainers against bounded structural perturbations. The construction hashes edges into T groups, builds T hybrid subgraphs by combining each original-edge group with a p-fraction of subgraphs of the complete graph (Eq. 2), and aggregates base classifier predictions and base explainer importance scores through majority voting (Eqs. 3-6). The central result, Theorem 3, certifies a perturbation size M* as the minimum of a classification margin term and an explanation margin term, so that the majority-vote prediction is unchanged and at least lambda edges of the clean top-k explanation survive in the perturbed top-k output. Experiments on three synthetic and two real datasets with PGExplainer, ReFine, and GSAT report clean accuracy close to the base models, certified M* versus lambda curves, hyperparameter studies, and improved empirical robustness over V-InfoR against the authors' prior black-box explanation attack (Li et al., 2024). Section 4.2.4 analyzes the T-fold computational and O(pT|V|^2) memory overhead.

Significance. The paper addresses a genuinely open problem—certified robustness for GNN explainers rather than classifiers—and, if the claims are properly scoped, delivers the first deterministic certificate of this kind. The hybrid-subgraph construction (Eq. 2) is a clever adaptation of partition aggregation to edge-sparse explanations: the Theorem 2 bound that at most M of the T hybrid subgraphs change under M edge perturbations is what makes a deterministic vote-margin certificate possible, and the certificate is computed directly from the trained model's own margins, with no sampling and probability 1. The evaluation is broad (five datasets, three explainers, three GNN classifiers), source code is provided, and the reported clean accuracy of the voting pipeline is close to the base explainers, which is a necessary sanity check. The main caveats are that the headline guarantees need restating under an explicit non-deletion-of-explanation-edge assumption, and the evaluation language that equates certified clean-explanation overlap with ground-truth overlap is stronger than Theorem 3.

major comments (2)

[Definition 1; Section 2; Appendix A.2] Definition 1 states that for any graph perturbation attack with at most M_lambda perturbed edges, at least lambda edges of the clean explanation E_k survive in the perturbed explanation. This is false under the stated wording: the voting explainer outputs E.topk(n_gamma) over the edge set of the perturbed graph (Eq. 6), so an attacker who deletes one explanatory edge e in E_k removes e from the candidate set entirely, and no lambda >= 1 overlap is possible. The proof in Appendix A.2 only bounds vote changes by +/-M and does not account for removal of explanatory edges from the candidate set; it implicitly relies on the informal stealthiness restriction in Section 2 that the attacker does not delete edges in E_k. Because the abstract, Definition 1, and the introduction's 'any graph perturbation attack' phrasing omit this restriction, the stated central claim is stronger than the proof supports. The Definition 1 remark that lambda = k implies hat(E)_k = E_k is likewise only meaningful under the non-deletion restriction. The fix is to make non-deletion of explanatory edges an explicit condition in Definition 1 and in every abstract, introduction, and evaluation claim, and to state explicitly how added and deleted non-explanatory edges are handled.
[Section 4.1; Introduction] Section 4.1 defines the metric 'Certified Perturbation Size M* at Certified Explanation Accuracy' as guaranteeing that lambda explanatory edges on the perturbed testing graph are from the groundtruth, and the introduction reports 'at least 2 edges are from the 5 groundtruth explanatory edges' on SG+House. However, Theorem 3 certifies overlap with the clean explanation E_k of the voting explainer, not with the groundtruth explanation. Since clean explanation accuracy is only about 0.74 on SG+House (Table 1) and lower on other datasets, a certified edge from E_k need not be a groundtruth edge; the groundtruth phrasing is not supported by the theorem. The metric should be renamed and redefined as 'certified overlap with the clean explanation,' with groundtruth accuracy reported separately (as in Table 1), and all headline numbers, including the abstract's claim about '5 groundtruth explanatory edges,' should be restated accordingly.

minor comments (5)

[Theorem 2] The statement of Theorem 2 uses the condition |E \ hat(E)| = M, which reads as the number of deleted edges only, but the proof and the use in Theorem 3 require the symmetric difference (deletions plus additions) to be bounded by M; the statement should be corrected to |E Δ hat(E)| <= M.
[Section 4.1] Section 4.1 averages M* over all testing graphs even though the meaningfulness premise in Section 3.3 assumes the voting classifier has an accurate label prediction on the clean graph; Table 2 reports prediction accuracies as low as 0.62 (FC with GSAGE), so the reported averages mix graphs for which the certificate's premise holds with graphs for which it does not, and the numbers should be recomputed on the correctly-classified subset or reported with the conditioning made explicit.
[Table 5; Section 4.2.2] There is an inconsistency in the groundtruth size for SG+House: Table 5 reports |E_GT|avg = 6 and k = 6, while the introduction and Section 4.2.2 state k = 5 groundtruth edges for SG+House; the correct value should be determined and used consistently.
[Eq. (2); Algorithm 1] Equation (2) constructs hybrid subgraphs by selecting exactly floor(pT) complement-graph subgraphs, whereas Algorithm 1 (lines 13-21) includes each complement subgraph independently with probability p; the text and pseudocode should be aligned, since Theorem 2 holds for both variants but the two procedures can produce different vote counts in practice.
[Figures 3-5, 7, 8; Table 7] Several typos should be corrected: 'Beneze' appears in the captions of Figures 3-5, 7, and 8, and the caption of Table 7 spells the hash function as 'MDS' instead of MD5.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the certificate is a direct margin argument over the model's own votes; the main issues (deletion of explanatory edges, groundtruth-vs-clean overclaim) are correctness gaps, not circular reasoning.

full rationale

The derivation chain is self-contained. Theorem 2 ('for any two graphs ... at most M different graphs') is proved directly from the hash partition: each perturbed edge changes only the subgraph with its hash index, and the complete-graph subgraphs are fixed. Theorem 3 is then a standard vote-margin certificate: with at most M affected subgraphs, each edge's vote can change by at most M (Eq. 5), so the conditions ny − nb + I(y<b) > 2M and nγ_l − nγ_hM + I(l<hM) > 2M (Eqs. 7-8) force the same majority label and the survival of λ clean top-k edges. No equation in the proof assumes the target robustness; the certificate is evaluated on the clean graph's own votes. The cited prior work (Li et al. 2024; Xia et al. 2024; Li & Wang 2025) supplies motivation and the partition idea, but the hybrid-subgraph construction and the explanation margin argument are new and self-contained, so there is no load-bearing self-citation and no uniqueness theorem imported from the authors. Two non-circular overclaims should be noted. (1) Definition 1 says 'for any graph perturbation attack' and requires λ same edges in Ek and ˆEk, but the voting explainer outputs from the perturbed edge set only (Eq. 6 and Section 2's ˆEk = ˆE.topk(...)). If an attacker deletes an explanatory edge e ∈ Ek, e cannot appear in ˆEk regardless of its vote, and the proof A.2's implication 'then at least λ edges in Ek are still in ˆEk' silently assumes e is still in ˆE. Section 2 does informally exclude deleting explanatory edges ('the attacker does not delete edges in the explanatory edges Ek'), but that restriction is not in Definition 1 or the abstract, so the stated central claim is stronger than the proof supports. (2) Section 4.1 defines the metric as 'λ explanatory edges on the perturbed testing graph are from the groundtruth', and Section 4.2.2 reports 'at least λ = 2 edges are from the k = 5 groundtruth explanatory edges', but Theorem 3 certifies overlap with the clean explanation Ek, not with the groundtruth. Given clean explanation accuracies around 0.74 on SG+House (Table 1), the groundtruth claim is stronger than the theorem. These are correctness/fidelity issues, not circular reductions, so they do not raise the circularity score.

Assumptions & free parameters 3 free parameters · 5 assumptions · 0 invented entities

The central certificate rests on the hash partition property, the non-deletion-of-explanatory-edges assumption, and the standard worst-case vote-margin argument. The hyperparameters p, T, and gamma are tuned and affect the certificate size but are not fitted to force the theorem. The ground-truth interpretation of the certificate adds an unproven accuracy assumption.

free parameters (3)

p = 0.3 (default)
Fraction of complete-graph subgraphs combined into each hybrid subgraph. Tuned on validation (Table 3); p=0 gives certified perturbation size 0, so the non-zero certificate depends on p>0.
T = 70 (default)
Number of hash buckets and hybrid subgraphs. Tuned per dataset; trades clean explanation accuracy against certified perturbation size (Figures 3 and 6-8).
gamma = 0.3 (default)
Top-fraction threshold for counting an edge as high-importance in a subgraph. Tuned on validation (Table 3); results are stable in the range 0.2 to 0.4.

assumptions (5)

domain assumption Deterministic, graph-structure-independent hash mapping assigns each edge to exactly one subgraph.
Theorem 2 relies on each perturbed edge affecting only the subgraph of its own hash group. If the hash were graph-dependent or reversible in a way the attacker could exploit, the bounded-different-subgraphs property could break.
domain assumption The attacker never deletes edges in the clean explanatory edge set E_k.
A deleted explanatory edge is absent from the perturbed graph and cannot be emitted by E.topk, so the lambda-overlap certificate fails under unrestricted deletion. Section 2 states this restriction informally, but Definition 1 omits it.
standard math Subgraphs built from the complete graph are fixed and unaffected by edge perturbations.
The complete graph over a fixed node set does not depend on which edges are present in G, so perturbing an edge does not change the complete-graph subgraphs.
standard math The base GNN explainer, when applied to a changed hybrid subgraph, can change its importance scores arbitrarily; vote counts therefore change by at most one per changed subgraph.
This is the worst-case assumption used in the Appendix A.2 proof of Theorem 3 to bound loss and gain of votes by M.
ad hoc to paper The clean voting explainer's output is an accurate explanation of the ground truth.
The theorem certifies overlap with the clean explanation, not with ground truth. The evaluation metric that reports certified edges 'from the groundtruth' requires this additional accuracy assumption, which the paper does not prove or certify.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Provably Robust Explainable Graph Neural Networks against Graph Perturbation Attacks." pith.science (2026). https://pith.science/paper/UX3DG6TD

@misc{pith2026250204224,
  author       = {Pith},
  title        = {Pith review of: Provably Robust Explainable Graph Neural Networks against Graph Perturbation Attacks},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/UX3DG6TD}},
  note         = {Machine review of arXiv:2502.04224}
}

read the original abstract

Explaining Graph Neural Network (XGNN) has gained growing attention to facilitate the trust of using GNNs, which is the mainstream method to learn graph data. Despite their growing attention, Existing XGNNs focus on improving the explanation performance, and its robustness under attacks is largely unexplored. We noticed that an adversary can slightly perturb the graph structure such that the explanation result of XGNNs is largely changed. Such vulnerability of XGNNs could cause serious issues particularly in safety/security-critical applications. In this paper, we take the first step to study the robustness of XGNN against graph perturbation attacks, and propose XGNNCert, the first provably robust XGNN. Particularly, our XGNNCert can provably ensure the explanation result for a graph under the worst-case graph perturbation attack is close to that without the attack, while not affecting the GNN prediction, when the number of perturbed edges is bounded. Evaluation results on multiple graph datasets and GNN explainers show the effectiveness of XGNNCert.

Figures

Figures reproduced from arXiv: 2502.04224 by the authors.

**Figure 2.** Overview of the proposed three-step certifiably robust XGNN. [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗

**Figure 3.** Certified perturbation size over all testing graphs vs. [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗

Figures from the paper (9 more)

**Figure 4.** Figure 4: Certified perturbation size over all testing graphs vs. [PITH_FULL_IMAGE:figures/full_fig_p008_4.png]

**Figure 5.** Figure 5: Certified perturbation size over all testing graphs vs. [PITH_FULL_IMAGE:figures/full_fig_p008_5.png]

**Figure 6.** Figure 6: Certified perturbation size over all testing graphs vs. [PITH_FULL_IMAGE:figures/full_fig_p018_6.png]

**Figure 7.** Figure 7: Certified perturbation size over all testing graphs vs. [PITH_FULL_IMAGE:figures/full_fig_p018_7.png]

**Figure 8.** Figure 8: Maximal certified perturbation size over all testing graphs vs. [PITH_FULL_IMAGE:figures/full_fig_p018_8.png]

**Figure 9.** Figure 9: Certified perturbation size over all testing graphs vs. [PITH_FULL_IMAGE:figures/full_fig_p019_9.png]

**Figure 10.** Figure 10: Certified perturbation size over all testing graphs vs. [PITH_FULL_IMAGE:figures/full_fig_p019_10.png]

**Figure 11.** Figure 11: Certified perturbation size over all testing graphs vs. [PITH_FULL_IMAGE:figures/full_fig_p019_11.png]

**Figure 12.** Figure 12: Examples of how an explanatory subgraph outputted by PGExplainer changes when GNN [PITH_FULL_IMAGE:figures/full_fig_p020_12.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Inside the Unfair Judge: A Mechanistic Interpretability Account of LLM-as-Judge Bias
cs.LG 2026-07 conditional novelty 6.5 of 10

LLM-as-judge scoring biases concentrate in low-dimensional, type-specific activation subspaces that support bidirectional causal steering and cross-domain failure prediction.

Reference graph

Works this paper leans on

14 extracted references · 13 canonical work pages · cited by 1 Pith paper

[1]

C E XPERIMENTAL SETUP AND MORE RESULTS C.1 D ETAILED EXPERIMENTAL SETUP Dataset statistics: Table 5 shows the statistics of the used datasets. 15 Published as a conference paper at ICLR 2025 Algorithm 1 XGNNCert: Classification, Explanation, and Certified Perturbation Size Input: Graph G = (V, E) with k explanation edges, base classifier f, base explainer...

work page 2025
[2]

For Refine, we set its gamma parameter as 1, beta parameter as 1 and tau parameter as 0.1

For GSAT, we set its final rate as 0.7, decay interval as 10 and decay rate as 0.1. For Refine, we set its gamma parameter as 1, beta parameter as 1 and tau parameter as 0.1. Training the GNN classifier and GNN explainer: Traditionally, we only use the training graphs (with their labels) to train a GNN classifier, which is used to predict the testing grap...

work page 2025
[3]

Certified robustness of graph convolution networks for graph classification under topological attacks

11 Published as a conference paper at ICLR 2025 Hongwei Jin, Zhan Shi, Venkata Jaya Shankar Ashish Peruri, and Xinhua Zhang. Certified robustness of graph convolution networks for graph classification under topological attacks. In NeurIPS,

work page 2025
[5]

Certifiably Robust Interpretation in Deep Learning

Alexander Levine and Soheil Feizi. Deep partition aggregation: Provable defenses against general poisoning attacks. In ICLR, 2020a. Alexander Levine and Soheil Feizi. (de) randomized smoothing for certifiable defense against patch attacks. In NeurIPS, 2020b. Alexander Levine and Soheil Feizi. Robustness certificates for sparse adversarial attacks by rando...

work page Pith review arXiv 1905
[6]

Explainability methods for graph convolutional neural networks

12 Published as a conference paper at ICLR 2025 Phillip E Pope, Soheil Kolouri, Mohammad Rostami, Charles E Martin, and Heiko Hoffmann. Explainability methods for graph convolutional neural networks. In CVPR,

work page 2025
[7]

Reinforcement learning enhanced explainer for graph neural networks

Caihua Shan, Yifei Shen, Yao Zhang, Xiang Li, and Dongsheng Li. Reinforcement learning enhanced explainer for graph neural networks. In NeurIPS 2021, December

work page 2021
[8]

Chemistry-intuitive explanation of graph neural networks for molecular property prediction with substructure masking

13 Published as a conference paper at ICLR 2025 Zhenxing Wu, Jike Wang, Hongyan Du, Dejun Jiang, Yu Kang, Dan Li, Peichen Pan, Yafeng Deng, Dongsheng Cao, Chang-Yu Hsieh, et al. Chemistry-intuitive explanation of graph neural networks for molecular property prediction with substructure masking. Nature Communications, 14(1):2585,

work page 2025
[11]

the classifier: Mf = ⌊ ny −nb+I(y<b)−1 2 ⌋

17: if ˜p ≤ p then 18: Add the j-th complete subgraph into i-th hybrid subgraph by E i H ∪ = E i C 19: end if 20: end for 21: end for 22: for Gi C , i∈ [1, T] do 23: Predict Gi C’s label via the base classifier: c = f (Gi C ) 24: Add to the classification vote by 1: nc+ = 1 25: end for 26: Find the class with the most votes: y = arg max c∈C nc 27: Find th...

work page 2025

Show all 14 references

[13]

Std” is the Standard Deviation of the explanation accuracy on test data across the 5 runs, and “Change Rate

to show its unstable explanation results. Particularly, we run it 5 times and show the explanation results in Table 8, where “Std” is the Standard Deviation of the explanation accuracy on test data across the 5 runs, and “Change Rate” is the average fraction of different expla...

2025
[14]

This ranges from the classic GSAGE with LSTM to modern graph transformers (Kreuzer et al., 2021; Zhu et al., 2023)

show node-order variant GNNs can produce better expressivity. This ranges from the classic GSAGE with LSTM to modern graph transformers (Kreuzer et al., 2021; Zhu et al., 2023). Our GNN voting classifier is node-order variant due to the property of hash function. To further ex...

2021
[2018]

Note that the complete graph GC is fixed and all subgraphs built from it are never affected

14 Published as a conference paper at ICLR 2025 A P ROOFS A.1 P ROOF OF THEOREM 2 When an edge e is added to or deleted from G, only the subgraph Gie = (V, Eie) is corrupted after hash mapping, and all the other subgraphs {Gj}j̸=ie are unaffected. Note that the complete graph ...

2025
[2019]

Certified adversarial robustness via randomized smoothing

Jeremy M Cohen, Elan Rosenfeld, and J Zico Kolter. Certified adversarial robustness via randomized smoothing. arXiv preprint arXiv:1902.02918,

1902 arXiv
[2021]

Certified robustness to adversarial examples with differential privacy

Mathias Lecuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. Certified robustness to adversarial examples with differential privacy. In 2019 IEEE Symposium on Security and Privacy (SP), pp. 656–672. IEEE,

2019
[2022]

Certified robustness of commu- nity detection against adversarial structural perturbation via randomized smoothing

Jinyuan Jia, Binghui Wang, Xiaoyu Cao, and Neil Zhenqiang Gong. Certified robustness of commu- nity detection against adversarial structural perturbation via randomized smoothing. InProceedings of The Web Conference 2020,

2020

Pith tools

Reviewed August 8, 2026 · model on record in the stance chip above.

[1] [1]

C E XPERIMENTAL SETUP AND MORE RESULTS C.1 D ETAILED EXPERIMENTAL SETUP Dataset statistics: Table 5 shows the statistics of the used datasets. 15 Published as a conference paper at ICLR 2025 Algorithm 1 XGNNCert: Classification, Explanation, and Certified Perturbation Size Input: Graph G = (V, E) with k explanation edges, base classifier f, base explainer...

work page 2025

[2] [2]

For Refine, we set its gamma parameter as 1, beta parameter as 1 and tau parameter as 0.1

For GSAT, we set its final rate as 0.7, decay interval as 10 and decay rate as 0.1. For Refine, we set its gamma parameter as 1, beta parameter as 1 and tau parameter as 0.1. Training the GNN classifier and GNN explainer: Traditionally, we only use the training graphs (with their labels) to train a GNN classifier, which is used to predict the testing grap...

work page 2025

[3] [3]

Certified robustness of graph convolution networks for graph classification under topological attacks

11 Published as a conference paper at ICLR 2025 Hongwei Jin, Zhan Shi, Venkata Jaya Shankar Ashish Peruri, and Xinhua Zhang. Certified robustness of graph convolution networks for graph classification under topological attacks. In NeurIPS,

work page 2025

[4] [5]

Certifiably Robust Interpretation in Deep Learning

Alexander Levine and Soheil Feizi. Deep partition aggregation: Provable defenses against general poisoning attacks. In ICLR, 2020a. Alexander Levine and Soheil Feizi. (de) randomized smoothing for certifiable defense against patch attacks. In NeurIPS, 2020b. Alexander Levine and Soheil Feizi. Robustness certificates for sparse adversarial attacks by rando...

work page Pith review arXiv 1905

[5] [6]

Explainability methods for graph convolutional neural networks

12 Published as a conference paper at ICLR 2025 Phillip E Pope, Soheil Kolouri, Mohammad Rostami, Charles E Martin, and Heiko Hoffmann. Explainability methods for graph convolutional neural networks. In CVPR,

work page 2025

[6] [7]

Reinforcement learning enhanced explainer for graph neural networks

Caihua Shan, Yifei Shen, Yao Zhang, Xiang Li, and Dongsheng Li. Reinforcement learning enhanced explainer for graph neural networks. In NeurIPS 2021, December

work page 2021

[7] [8]

Chemistry-intuitive explanation of graph neural networks for molecular property prediction with substructure masking

13 Published as a conference paper at ICLR 2025 Zhenxing Wu, Jike Wang, Hongyan Du, Dejun Jiang, Yu Kang, Dan Li, Peichen Pan, Yafeng Deng, Dongsheng Cao, Chang-Yu Hsieh, et al. Chemistry-intuitive explanation of graph neural networks for molecular property prediction with substructure masking. Nature Communications, 14(1):2585,

work page 2025

[8] [11]

the classifier: Mf = ⌊ ny −nb+I(y<b)−1 2 ⌋

17: if ˜p ≤ p then 18: Add the j-th complete subgraph into i-th hybrid subgraph by E i H ∪ = E i C 19: end if 20: end for 21: end for 22: for Gi C , i∈ [1, T] do 23: Predict Gi C’s label via the base classifier: c = f (Gi C ) 24: Add to the classification vote by 1: nc+ = 1 25: end for 26: Find the class with the most votes: y = arg max c∈C nc 27: Find th...

work page 2025