{"id":"588f6397-c85e-4e8f-9223-2a09d4a4ed41","arxiv_id":"2506.12558","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":7,"one_line_summary":"RAW-Explainer combines parameterized edge-mask learning with random-walk connectivity and a distance-biased robust evaluator to efficiently produce connected subgraph explanations for knowledge-graph link prediction.","lead":"A new method, RAW-Explainer, generates small connected subgraphs that explain why a graph neural network predicts a given link in a knowledge graph, and it runs faster than existing path-based explainers. It also introduces a distance-based evaluator to cope with the mismatch between full graphs and tiny explanation subgraphs, a step toward trust in AI-curated knowledge bases.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Robust evaluator is validated only on random edge-drop/ego-network shifts, not on the mask-optimized subgraphs RAW-Explainer actually produces, so its surrogate validity for the backbone is unestablished.","rationale":"The reader's weakest assumption is essentially the same issue: Phi_dist_eval is assumed to approximate the true distribution of explanatory subgraphs well enough that maximizing its masked prediction yields subgraphs informative for the backbone. I sharpen the concern by pointing out that the empirical support (Figs. 2-3) covers random edge-drop and ego-network perturbations, not the mask-optimized subgraphs the explainer actually produces, so the transfer is untested. This is load-bearing because the robust evaluator is the method's main novelty; without it, RAW-Explainer reduces to PG-Explainer with a PPR connectivity regularizer. The concern does not refute the paper's empirical results, but it identifies a missing validation that is necessary for the central claim. Since the paper is already CONDITIONAL due to missing code, error bars, and hyperparameters, the verdict remains CONDITIONAL (UNCHANGED). The proposed ablation would directly test whether the surrogate evaluator is the reason for any observed improvement.","tokens_in":12704,"tokens_out":5624,"duration_ms":65443,"concrete_test":"Run an ablation on WN18RR: train the mask learner with (a) the backbone Phi, (b) Phi_unif_eval, and (c) Phi_dist_eval as the evaluator, all other components fixed. For each variant, generate explanation subgraphs and measure the fine-tuned backbone MRR under the protocol of Sec. 4.5. Also compute the rank correlation between Phi and Phi_dist_eval scores over a sample of candidate subgraphs produced by the mask learner. If variant (c) does not outperform (a) and (b) by a clear margin, or if the rank correlation is low (<0.5), the robust evaluator's benefit and surrogate validity are not supported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"RAW-Explainer's objective (Eq. 5) replaces the backbone Phi with the distance-biased evaluator Phi_dist_eval when optimizing the edge mask Omega. The paper's justification is that Phi_dist_eval is more robust to OOD subgraphs, supported by Figs. 2-3. However, those experiments only test random edge deletions and ego-network slices; they never test the distribution of subgraphs that the mask learner actually selects. Mask-optimized subgraphs are sparse, concentrated, and chosen to maximize Phi_dist_eval's score, so they may exploit idiosyncrasies of the evaluator's distance-biased training rather than reflect true informativeness for the backbone. Because the final explanations are judged by fine-tuning the backbone Phi (Sec. 4.5), a mismatch between what Phi_dist_eval rewards and what Phi needs would directly undermine the headline claim. No experiment measures the agreement between Phi and Phi_dist_eval on the explainer's own output subgraphs.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"RAW-Explainer generates post-hoc subgraph explanations for knowledge graph link prediction. It parameterizes edge-mask learning with an MLP, regularizes masks through a Personalized PageRank random-walk objective to encourage connectivity, and replaces the backbone GNN with a distance-biased robust evaluator (Φdist_eval) when optimizing the mask. Explanations are evaluated by fine-tuning the backbone NBFNet on the extracted subgraphs and reporting MRR on test subgraphs, comparing against GNN-Explainer, PG-Explainer, PaGE-Link, and Power-Link on WN18RR and FB15k-237. The paper reports that RAW-Explainer outperforms KG-specific path baselines, is competitive with or behind PG-Explainer, and is substantially faster than instance-based methods.","tokens_in":12983,"tokens_out":5974,"duration_ms":63604,"significance":"The proposed downstream fine-tuning protocol (Section 4.5) is a practical way to compare explainers when ground truth is absent, and the parameterized, inductive mask learner is a sensible design for scalability. The efficiency gains are concrete and large (e.g., 17 minutes vs. 109–172 minutes on WN18RR). If the robustness of Φdist_eval to the explainer's own subgraph distribution were established, the method would offer a solid balance between efficiency, connectivity, and informativeness. However, the current evidence does not yet substantiate the surrogate-evaluator mechanism or the connectivity guarantee, and the reported point estimates are not accompanied by variance information. The contributions are promising but not fully established.","major_comments":[{"comment":"The robust evaluator Φdist_eval is validated only on random edge-drop and ego-network perturbations, not on the distribution of subgraphs actually produced by the mask learner. Since the mask learner optimizes Eq. (5) against Φdist_eval, a systematic disagreement between Φdist_eval and the backbone Φ on those optimized subgraphs would undermine the factual-fidelity interpretation of the explanations, yet no experiment compares Φ and Φdist_eval on RAW-Explainer's output subgraphs. Please add a direct agreement or transfer experiment (e.g., correlation of masked predictions, or downstream MRR of masks trained with Φ vs. Φdist_eval) to support the claim that Φdist_eval 'generalizes to the subgraph distribution.'","section":"§4.2, §5.2–5.3"},{"comment":"All MRR results are reported as single point estimates with no standard deviations, confidence intervals, or significance tests. The evaluation protocol involves stochastic mask learning and GNN fine-tuning, and several margins are narrow (e.g., WN18RR, k=25: RAW-Explainer 0.482 vs. Power-Link 0.473). Without repeated runs and variance reporting, the comparative claims are not statistically assessable.","section":"Tables 3–4"},{"comment":"The manuscript does not report the values or tuning ranges of the free parameters introduced in the method, including α, the top-m predicted tails, top-l PPR entities, β_in/β_out, the Gumbel-Softmax temperature, the sparsity and entropy regularization weights, and the distance-decay rate for Φdist_eval. Section 5.4 states that hyperparameters are selected on the validation set, but without these details the results are not reproducible and the sensitivity of the method to key choices is unknown. A hyperparameter table and a sensitivity analysis for at least α and the β weights should be provided.","section":"§5.1, §5.4"},{"comment":"The paper claims that the random-walk objective 'ensures the connectivity of the output explanations,' and the FB15k-237 discussion states that RAW-Explainer 'returns a single connected component by design.' The described procedure—selecting top-l PPR nodes and then edges with both endpoints in that set—does not mathematically guarantee a connected induced subgraph, since two high-PPR nodes may be connected only through a node outside the top-l set. No connectivity metric is reported for the generated subgraphs (only PG-Explainer's average components is mentioned). Please prove the guarantee or report empirical connectivity statistics for all methods.","section":"§4.3, §5.4"},{"comment":"The introduction claims RAW-Explainer 'yields better explanatory subgraphs under limited edge budgets,' but Table 4 shows that PG-Explainer achieves the highest MRR at every budget on FB15k-237, with RAW-Explainer second. The discussion attributes PG-Explainer's advantage to disconnected subgraphs, but the claim as written is contradicted by the table. The claim should be qualified to 'better than path-based KG-specific baselines' or reworded to explicitly describe the trade-off between connectivity/interpretability and downstream MRR.","section":"Introduction, Table 4"}],"minor_comments":[{"comment":"The teleportation matrix τ is described as binary but is combined with σ(Ω′) via a softmax; please clarify the normalization and the role of τ in the stochastic matrix construction.","section":"Eq. (7)"},{"comment":"The entry 'RA W-Exp' appears with an awkward line break; it should read 'RAW-Exp' for consistency with the rest of the paper.","section":"Table 1"},{"comment":"There is a typo, 'due to to the increased complexity,' which should be corrected to 'due to the increased complexity.'","section":"§5.4, Results Discussion"},{"comment":"The caption says 'on different size of ego networks'; the grammar should be 'on different sizes of ego networks.'","section":"Figure 3 caption"},{"comment":"The notation for the evaluator is inconsistent: Section 4.1 uses Φeval, while Section 4.2 introduces Φdist_eval and Φunif_eval; please standardize the notation throughout.","section":"§4.1–4.2"}],"recommendation":"major_revision","confidential_remarks":"The paper is within scope for a machine learning venue and the evaluation protocol is a useful contribution, but the missing variance estimates and hyperparameter reporting may be significant at a journal that requires reproducibility. The major revision should focus on the evaluator-validation experiment and the connectivity guarantee, as these are central to the paper's claims."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nRAW-Explainer is a serious attempt at filling a real gap: post-hoc explanations for link prediction on knowledge graphs. It combines three known pieces—parameterized edge masks (PG-Explainer style), a robust evaluator trained with distance-biased edge dropping (a twist on XG-Explainer), and a PPR-based connectivity loss—and adds a downstream fine-tuning evaluation protocol that is genuinely useful for comparing explainers when ground truth is absent. The genuinely new part is the distance-biased robust evaluator for KG link prediction, and the paper shows it holds up better than the backbone or a uniform-drop evaluator on random edge-deletion and ego-network tests. That part is convincing enough.\n\nThe evaluation protocol is a good contribution on its own: fine-tune the backbone GNN on the extracted subgraphs and measure MRR. It gives an external yardstick, and it is why the result is not purely self-referential. The method is also efficient and produces connected subgraphs, which matters for interpretability.\n\nThe soft spots are real but not fatal. No error bars anywhere; tables report single runs, and with budgets across six sizes and two datasets, that is thin. Hyperparameters are mostly unspecified, and no code is shipped, so reproducibility is weak. On FB15k-237, PG-Explainer actually beats RAW-Explainer on MRR for every budget; the paper defends itself by saying PG-Explainer's subgraphs are disconnected, which is fair, but the abstract's claim of 'better explanatory subgraphs' is overstated.\n\nThe bigger concern, which I think is legitimate, is that the robust evaluator's validity is only tested on random edge drops and ego-network slices, not on the mask-optimized subgraphs the explainer actually produces. Those subgraphs are sparse, concentrated, and selected to score well on the evaluator, so it could be rewarding idiosyncrasies. The final fine-tuning benchmark catches some of this, but the paper never measures how closely the evaluator tracks the backbone on the explainer's own outputs. That would be the decisive experiment. If the agreement is high on those subgraphs, the central claim is solid; if not, the mask training is optimizing against the wrong oracle.\n\nOverall, I'd accept this for peer review with a request for major revisions: add error bars, specify hyperparameters, and run that agreement check. As it stands, the central idea is plausible and the framework is coherent, but the evidence is not yet airtight.","headline":"A plausible and coherent explainer for KG link prediction, but the robustness story needs an experiment on the explainer's own subgraphs before I'd trust it.","tokens_in":13451,"tokens_out":3038,"would_cite":true,"duration_ms":30062,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Connected subgraph explanations beat path-based KG rivals","keywords":["graph neural network explainability","knowledge graph completion","link prediction","subgraph explanations","random walk","distribution shift","robust evaluator","fine-tuning evaluation"],"falsifier":"Run a controlled study on synthetic KGs with planted ground-truth rule patterns. If RAW-Explainer's extracted subgraphs fail to cover the planted pattern at a high rate, or if the MRR of a backbone fine-tuned on its subgraphs does not exceed that of a random connected subgraph of the same budget, the method's central claim would be refuted.","tokens_in":12534,"feed_emoji":"🔗","tokens_out":5908,"duration_ms":65851,"temperature":0.7,"pith_summary":"RAW-Explainer claims that the right way to explain a knowledge-graph link prediction is a small connected subgraph, and that existing explainers fail at this because they either ignore heterogeneous structure, do not guarantee connectivity, or evaluate subgraphs with a model that was never trained on anything that small. The paper's method learns a soft edge mask from entity and relation embeddings with a small neural network, then runs a personalized random walk to force the selected edges into one connected component around the query. To score candidate masks correctly, it trains a robust evaluator that drops edges with probability increasing with distance from the query head, so the evaluator stays accurate on subgraph-scale inputs. On FB15k-237 and WN18RR, fine-tuning the backbone on RAW-Explainer's explanations gives higher MRR than PaGE-Link and Power-Link and is competitive with PG-Explainer, while producing a single connected subgraph orders of magnitude faster.","feed_headline":"Connected subgraph explanations beat path-based KG rivals","feed_subtitle":"Distance-biased evaluator plus random walks yields higher MRR after fine-tuning, in minutes.","key_machinery":"The central object is the pair ($\\Phi_{\\mathrm{dist}}^{eval}$, $\\mathcal{L}_{PPR}$). $\\Phi_{\\mathrm{dist}}^{eval}$ is a GNN link predictor trained with distance-proportional edge dropping, so its predictions remain reliable on small subgraphs; it supplies the training signal for the mask. $\\mathcal{L}_{PPR}$ converts the learned soft mask into a stochastic transition matrix with teleportation to query-relevant entities, runs a personalized random walk to convergence, then penalizes mask weight on edges whose endpoints are not both in the top-ranked entity set, enforcing that the final subgraph is connected around the query head and its likely tails.","core_discovery":"The paper's central claim is that explanation quality for KG link prediction hinges on three design choices working together: a heterogeneous, parameterized mask learner; a personalized random walk that enforces connectivity; and a distance-biased robust evaluator. The evaluator is trained by removing each edge with probability that grows with its hop distance from the query head, which mimics the small, local subgraphs that explanations actually are. The mask learner maximizes the evaluator's masked prediction while the random-walk loss rewards edges inside the query's reachable core and penalizes edges outside it, yielding a concise connected subgraph at any budget. The authors then assess explanations by downstream utility: they fine-tune the original backbone GNN on the extracted subgraphs and measure MRR, finding that RAW-Explainer outperforms the path-based KG baselines and matches a graph-wide explainer while guaranteeing connectivity and cutting inference time from hours to minutes.","pith_inferences":["The evaluation protocol suggests a data-augmentation loop the authors did not run: fine-tuning the backbone on its own high-utility explanations could improve the link predictor itself, closing the explain-then-train circle.","Making the edge-drop probability depend on relation type as well as distance may sharpen the robust evaluator further, since informative edge patterns in KGs are relation-specific.","The connectivity guarantee is only as strong as the random walk's top-$\\ell$ entity set; if an important edge lies outside that set, the loss actively penalizes it, so the method favors well-connected queries over scattered-but-important ones.","Re-running the PG-Explainer comparison with a connectivity penalty or post-hoc path extraction would isolate whether its higher MRR on FB15k-237 comes from genuinely better subgraphs or from exploiting disconnected latent structure."],"forward_implications":["Every KG link prediction can be explained by one connected subgraph at any user-chosen edge budget, making explanations readable as a small graph or path.","Replacing uniform edge dropping with distance-biased dropping improves any perturbation-based evaluator on heterogeneous graphs, not just this explainer.","The downstream fine-tuning protocol gives KG explainability a task-based metric, so methods can be compared without ground-truth explanations.","Parameterized mask learning makes collective explanation generation inductive and time-efficient: minutes instead of hours."],"supporting_citations":[{"why":"Provides the backbone GNN used throughout and the query-dependent message passing being explained.","marker":"[21]"},{"why":"Introduces the robust-evaluator concept that RAW-Explainer adapts to KGs with distance bias.","marker":"[9]"},{"why":"Supplies the parameterized global explainer design for inductive mask prediction.","marker":"[10]"},{"why":"Is the main heterogeneous path-based baseline and source of the synthetic ground-truth evaluation.","marker":"[18]"},{"why":"Power-Link, another baseline for path extraction speed.","marker":"[5]"},{"why":"GNN-Explainer, instance-based baseline and mutual-information approach.","marker":"[15]"},{"why":"Defines the personalized random walk that the connectivity loss is built on.","marker":"[11]"},{"why":"Motivates freezing the evaluator so masks do not encode shortcuts.","marker":"[7]"},{"why":"Supplies the FB15k-237 dataset used in the real-world experiments.","marker":"[13]"},{"why":"Supplies the WN18RR dataset used in the real-world experiments.","marker":"[6]"}],"fun_headline_variants":["Connected subgraph KG explanations: minutes, not hours","Random walks yield fast, connected link explanations","RAWE: subgraph explanations that keep quality and speed","Robust evaluator makes KG explanations quick and connected","From hours to minutes for connected KG link explainability"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole method rests on the assumption that the distance-biased evaluator, trained on synthetic edge-dropped graphs, approximates the real distribution of explanatory subgraphs well enough that maximizing its masked prediction yields subgraphs the true backbone finds informative; the paper supports this only with the curves in Figure 3.","fun_headline_variants_meta":{"raw":{"variants":["Connected subgraph KG explanations: minutes, not hours","Random walks yield fast, connected link explanations","RAWE: subgraph explanations that keep quality and speed","Robust evaluator makes KG explanations quick and connected","From hours to minutes for connected KG link explainability"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000208,"raw_usage":{"total_tokens":1388,"prompt_tokens":917,"completion_tokens":471,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":533,"completion_tokens_details":{"reasoning_tokens":396}},"tokens_in":533,"tokens_out":471,"duration_ms":6578,"temperature":1.0,"reasoning_tokens":396,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T00:45:45.194851+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run a controlled study on synthetic KGs with planted ground-truth rule patterns. If RAW-Explainer's extracted subgraphs fail to cover the planted pattern at a high rate, or if the MRR of a backbone fine-tuned on its subgraphs does not exceed that of a random connected subgraph of the same budget, the method's central claim would be refuted.","supporting_citations":[{"cited_title":"In: NeurIPS","cited_arxiv_id":null,"evidence_quote":"Provides the backbone GNN used throughout and the query-dependent message passing being explained."},{"cited_title":"In: Proceedings of the 2024 SIAM International Confer- ence on Data Mining (SDM)","cited_arxiv_id":null,"evidence_quote":"Introduces the robust-evaluator concept that RAW-Explainer adapts to KGs with distance bias."},{"cited_title":"In: NeurIPS (2020)","cited_arxiv_id":null,"evidence_quote":"Supplies the parameterized global explainer design for inductive mask prediction."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Is the main heterogeneous path-based baseline and source of the synthetic ground-truth evaluation."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Power-Link, another baseline for path extraction speed."},{"cited_title":"In: NeurIPS","cited_arxiv_id":null,"evidence_quote":"GNN-Explainer, instance-based baseline and mutual-information approach."},{"cited_title":"Technical Report 1999-66, Stanford InfoLab (November 1999)","cited_arxiv_id":null,"evidence_quote":"Defines the personalized random walk that the connectivity loss is built on."},{"cited_title":"In: AISTATS","cited_arxiv_id":null,"evidence_quote":"Motivates freezing the evaluator so masks do not encode shortcuts."},{"cited_title":"In: CVSC","cited_arxiv_id":null,"evidence_quote":"Supplies the FB15k-237 dataset used in the real-world experiments."},{"cited_title":"In: AAAI","cited_arxiv_id":null,"evidence_quote":"Supplies the WN18RR dataset used in the real-world experiments."}],"review_version":1}