{"id":"2bd5c580-2614-4b0e-b48a-312c34d34382","arxiv_id":"2502.04224","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"XGNNCert certifies that a GNN explanation keeps at least lambda edges under any graph perturbation of bounded size, using majority voting over hash-partitioned hybrid subgraphs.","lead":"Researchers built XGNNCert, a defense that makes graph neural network explanations provably stable when an attacker changes a limited number of edges. The system votes over many random subgraphs, and it certifies a minimum number of explanation edges that survive any attack within a budget.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Definition 1 overclaims: the λ-overlap guarantee fails if an attacker deletes an explanatory edge; the proof assumes this never happens, and the evaluation's groundtruth claims exceed Theorem 3.","rationale":"The technical machinery is sound under Section 2's intended threat model: Theorem 2's key claim that a single added or deleted edge only corrupts the hybrid subgraph with the same hash index is correct because the complete subgraph with index i is excluded from hybrid subgraph i, and the margin argument in Theorem 3 correctly bounds vote changes by the number of corrupted subgraphs. The load-bearing problem is that the formal definition, abstract, and evaluation overstate the attacked set: they say 'any graph perturbation attack,' while the proof silently assumes explanatory edges are never deleted. This gap changes the meaning of the central claim and must be fixed before the claim is accepted as stated; it is a correctable overclaim rather than a fatal flaw. The groundtruth-labelling issue is a real secondary overclaim in the evaluation section. The reader's CONDITIONAL verdict remains appropriate, so no verdict change is recommended.","tokens_in":20495,"tokens_out":13493,"duration_ms":146415,"concrete_test":"Take any test graph for which the certificate reports Mλ ≥ 1 and λ ≥ 1, and construct the attack that deletes exactly one edge e ∈ Ek; this is allowed by Definition 1 as written. Recompute the voting explainer on the perturbed graph. Since its output is E.topk(n^γ) over the perturbed edge set, e cannot be in the output, so the λ-overlap guarantee fails. This pins the missing assumption; amending Definition 1 to explicitly forbid deleting explanatory edges would make the theorem consistent with Section 2.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Definition 1 states that for any graph perturbation attack with at most Mλ perturbed edges, at least λ edges of Ek survive in the new explanation. Under this wording, the guarantee is false: the voting explainer outputs E.topk(n^γ) (Eq. 6), selecting only from edges present in the perturbed graph. If an attacker deletes one explanatory edge e ∈ Ek, then e is absent from the perturbed edge set and cannot appear in the output, so no λ ≥ 1 overlap is possible. Section 2 does informally restrict the attacker to not delete explanatory edges, and Appendix A.2's proof relies on that restriction by assuming explanatory-edge votes only decrease by at most M rather than being removed from the candidate set. However, Definition 1, the abstract, and the evaluation language ('arbitrarily perturbed edges') omit this restriction, so the stated central claim is stronger than the proof supports. The fix is to make non-deletion of explanatory edges an explicit condition in Definition 1 and in every abstract/introduction claim. A secondary but related overclaim: Section 4.1 defines certified explanation accuracy as λ edges 'from the groundtruth,' yet Theorem 3 only certifies overlap with the clean explanation Ek. Since clean explanation accuracy is only about 0.74 on SG+House (Table 1), groundtruth overlap is not actually certified.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":20668,"tokens_out":10468,"duration_ms":106867,"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":[{"comment":"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":"Definition 1; Section 2; Appendix A.2"},{"comment":"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.","section":"Section 4.1; Introduction"}],"minor_comments":[{"comment":"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":"Theorem 2"},{"comment":"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.","section":"Section 4.1"},{"comment":"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.","section":"Table 5; Section 4.2.2"},{"comment":"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.","section":"Eq. (2); Algorithm 1"},{"comment":"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.","section":"Figures 3-5, 7, 8; Table 7"}],"recommendation":"major_revision","confidential_remarks":"The empirical attack evaluation in Section 4.2.3 uses the authors' own prior attack (Li et al., 2024) to compare XGNNCert with V-InfoR; an independent re-implementation of the attack or a third-party adversarial explainer attack would strengthen confidence in the empirical comparison. The manuscript is the camera-ready version of an ICLR 2025 paper, and it does not state its prior publication status; the editor may wish to consider the journal-scope and incremental-contribution questions. The 'first provably robust XGNN' claim appears accurate relative to the cited literature, since existing certified defenses for explainable non-graph models are probabilistic while this certificate is deterministic."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my read on XGNNCert.\n\nThe 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.\n\nThe 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.\n\nThere 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.\n\nThe 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.\n\nOverall, 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.","headline":"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.","tokens_in":21262,"tokens_out":4978,"would_cite":true,"duration_ms":47010,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68T07","68R10"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["certified robustness","graph neural networks","GNN explainability","graph perturbation attacks","majority voting","hash-based subgraph partition","adversarial robustness","XGNNCert"],"falsifier":"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.","tokens_in":20209,"feed_emoji":"🛡️","tokens_out":11255,"duration_ms":99903,"temperature":0.7,"pith_summary":"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.","feed_headline":"First certificate keeps GNN explanations safe from edge attacks","feed_subtitle":"Hash-based voting keeps prediction and explanation stable, so users know how much graph tampering an explanation can survive.","key_machinery":"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.","core_discovery":"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).","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the divide-and-aggregate certification template that XGNNCert adapts from image patches to graph edges.","marker":"Levine & Feizi, 2020b"},{"why":"Establishes the deterministic majority-vote certification machinery behind the voting classifier and voting explainer.","marker":"Jia et al., 2022"},{"why":"Provides the hash-based graph division and deterministic certification approach for GNN classifiers that XGNNCert extends.","marker":"Xia et al., 2024"},{"why":"Another deterministic graph certification defense whose subgraph-voting design is adapted for explanation robustness.","marker":"Yang et al., 2024"},{"why":"Directly preceding deterministic certification for GNNs under arbitrary perturbations, cited as the template for bounded-subgraph-corruption arguments.","marker":"Li & Wang, 2025"},{"why":"Defines the explanation-fragility attack, including the stealthy keep-prediction variant, that XGNNCert is designed to defend against.","marker":"Li et al., 2024"},{"why":"V-InfoR, the empirical explanation defense used as the comparison baseline; the paper reports XGNNCert outperforms it under the attack.","marker":"Wang et al., 2023c"},{"why":"PGExplainer, one of the stable base explainers used to instantiate the voting explainer.","marker":"Luo et al., 2020"},{"why":"GSAT, another stable base explainer used in the evaluation of XGNNCert.","marker":"Miao et al., 2022"},{"why":"Supplies the datasets with ground-truth explanations used to measure clean and certified explanation accuracy.","marker":"Agarwal et al., 2023"}],"fun_headline_variants":["Certified robust GNN explanations against edge attacks","Provably stable GNN explanations under graph perturbation","First certifiable explanation method for GNNs under attacks","Certified explanation robustness for graph neural networks","Guaranteeing GNN explanation stability despite edge perturbations"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Certified robust GNN explanations against edge attacks","Provably stable GNN explanations under graph perturbation","First certifiable explanation method for GNNs under attacks","Certified explanation robustness for graph neural networks","Guaranteeing GNN explanation stability despite edge perturbations"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000488,"raw_usage":{"total_tokens":2423,"prompt_tokens":984,"completion_tokens":1439,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":600,"completion_tokens_details":{"reasoning_tokens":1365}},"tokens_in":600,"tokens_out":1439,"duration_ms":10729,"temperature":1.0,"reasoning_tokens":1365,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-08T23:07:41.228233+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}