RDS-Explainer: Random-Reference Dual Score for Size-Adaptive GNN Explanation

Understanding why a graph neural network (GNN) makes a prediction is important for trustworthy graph learning. Many post-hoc GNN explainers identify important nodes or edges, but isolated importance values do not reveal which elements together form the prediction-relevant structure. A concrete explanatory subgraph makes this structure explicit, but its size is difficult to determine: too small may omit important evidence, whereas too large may include irrelevant structure, and the appropriate size varies across graphs. To address this problem, we propose RDS-Explainer (Random-Reference Dual-Score Explainer), which evaluates candidate subgraphs against references constructed from random subgraphs of different sizes. The resulting support and dispensability scores form the Dual Score, which identifies just-sufficient explanations by encouraging sufficient predictive evidence within the candidate subgraph and suppressing residual evidence outside it, without requiring a predefined explanation size. To search the exponential edge-subset space, Cooperative Edge Pruning removes multiple edges per step and coordinates parallel node-level pruning decisions through graph-level feedback. Once trained, the pruning policy applies directly to unseen graphs without per-instance optimization, enabling millisecond-level explanation generation. Across four molecular benchmarks, RDS-Explainer achieves the highest Charact and GEA, even when six baselines receive privileged ground-truth size information. Code will be publicly available after acceptance.