Statistical Test for Saliency Maps of Graph Neural Networks via Selective Inference
Authors: Shuichi Nishino
Tomohiro Shiraishi
Teruyuki Katsuoka
Ichiro Takeuchi
Venue: Accepted by TMLR ()

Abstract: Graph Neural Networks (GNNs) have gained prominence for their ability to process graph-structured data across various domains. However, interpreting GNN decisions remains a significant challenge, leading to the adoption of saliency maps for identifying salient subgraphs composed of influential nodes and edges. Despite their utility, the reliability of GNN saliency maps has been questioned, particularly in terms of their robustness to input noise. In this study, we propose a statistical testing framework to rigorously evaluate the significance of saliency maps. Our main contribution lies in addressing the inflation of the Type I error rate caused by double-dipping of data, leveraging the framework of Selective Inference. Our method provides statistically valid $p$-values while controlling the Type I error rate, ensuring that identified salient subgraphs contain meaningful information rather than random artifacts. The method is applicable to a variety of saliency methods with piecewise linearity (e.g., Class Activation Mapping). We validate our method on synthetic and real-world datasets, demonstrating its capability in assessing the reliability of GNN interpretations.

Published in Transactions on Machine Learning Research (09/2025)
Statistical Test for Saliency Maps of Graph Neural Networks via Selective Inference
Shuichi Nishino
mehiio..hhickk..ooyym@eddd.d
Nagoya University
RIKEN
Tomohiro Shiraishi
Nagoya University
RIKEN
Teruyuki Katsuoka
Nagoya University
Ichiro Takeuchi
takeuchi, mukeruhh..chhrr...dd3...a.aaa
Nagoya University
RIKEN
Reviewed OpenReview: https: openreview. net/ forum? id= 5N
Abstract
Graph Neural Networks (GNNs) have gained prominence for their ability to process graph- structured data across various domains. However, interpreting GNN decisions remains significant challenge, lcading to the adoption of saliency maps for identifying salient sub- graphs composed of influential nodes and edges. Despite their utility, the reliability of GNN saliency maps has been questionod, particularly in terms their robustness to input noisc. In this study, we propose a statistical lesting framework to rigorously evaluate the signisi- cance saliency maps. Our main contribution lies in addressing the inflation of the Type I error rate caused by double-dipping of data, leveraging the framework of Selective Inference. Our method provides statistically valid p-values while controlling the Type error rate, suring that identified salient subgraphs contain meaningful information rather than random artifacts. The method is applicable to variety of saliency methods with piecewise linear- ity (c.g., Class Activation Mapping). We validate our method on synthotic and real-world datasets, demonstrating its capability in assessing the reliability of GNN interpretations.
1 Introduction
Graph Neural Networks (GNNs) have gained considerable attention as a powerful approach for analyzing data with an inherent graph structure. Graph structures, defined by nodes and edges, appear in various types of data, including social networks, molecular structures, 3D scans, and spatiotemporal data. The flexibility of graph representation enables the utilization of rich structural information, which is difficult process using conventional vector-based representations. As a result, GNNs have achieved notable success in applications ranging from social network analysis to climate forecasting and bioinformatics.
A significant challenge in applying GNNs is to interpret their decision-making processes. To ensure inter- pretability, it essential to identify and visualize which parts of the input graph such as specific nodes or subgraphs contribute most significantly to the model's prediction. A well-known approach to this problem extends saliency-based techniques originally developed for computer vision, such as Class Activation Map- ping (CAM) (Simonyan et al., 2013) and Grad- CAM (Selvaraju et al. [007]) the graph domain (Pope) all 2019 These methods produce saliency maps that highlight influential components of graph; from

---

Published in Transactions on Machine Learning Research (09/2025)
these, one can extract salient subgraphs that may reflect characteristic structure in the imput data. However, several studies have raised concerns about their reliability, making it crucial to quantify the reliability (Li et all 2024baa a). This is especially important in mission-critical applications (e.g,, medical diagnosis) and scientific discovery (e.g., neuroscience).
In this study, we propose a novel statistical test for evaluating the reliability of saliency maps of GNNs. We focus on discovering characteristic structures hidden in the input data using saliency maps. Instead of blindly trusting the values of saliency maps, treat them Our method quantifies the reliability in the form of p-values. P-values indicate the statistical significance of saliency map, allowing us to assess whether the observed patterns are meaningful or occur merely by chance. In other words, it enables us to control the Type error rate (i.e., false positive rate) at a predefined significance level.
hypotheses and assess their statistical significance.
In this paper, as a proof of concept, we consider simple GNN for clectronncehhalograply (EEG) data. EEG signals are recorded as spatiotemporal vollage changes across the scalp and have recently been increasingly analyzed using GNNs (Demir et al.) 2021 Lin et al. 2023 Klepl et al. 2024). In particular, we identify the spatiotemporal locations where stimulus-induu
voltage shifts occur, known as Event-Related Potentials (ERPs] I in neuroscience. Specifically, when GNN is trained to classify stimulus types from EEG data, it can reveal characteristic spatiotemporal patterns in brain activity by extracting the salient subgraph that underlies its classification decision. Figure Segure[[ilustraan illlustaates the workflow of our method as applied to EEG data. First, we transform the multidimensional time-series data into a graph representation. Next, we apply a trained GNN and use a saliency map to extract the salient subgraph. Finally, we evaluate the statistical significance of the extracted salient subgraph and quantify its reliability through p-values. Our proposed statistical testing framework enables a rigorous assessment of whether the observed voltage shift constitutes a statistically significant change, thereby identifying the regions and time periods where meaningful differences occur.
(a) Features
(c) Saliency map
Prediction
pretrsined
GNN
CAM
Sersors
Time segments
Thresholding
(b) Graph structure
(d) Salient subgraph
Non-salient subgraph
Time
tel, t=2, 1s3
Salient Salient subgraph
p-value: 0.000 0.05
Figure 1: The analysis workflow for computing a saliency map from graph data and assessing its statistical significance. (a) The time-series data from each sensor are segmented along the temporal axis, forming nodes with features extracted from the resulting segments (sensor count number of time segments). (b) A graph structure is constructed by defining edges based on the spatial adjacency of sensors and the temporal continuity of the segments. (c) A trained GNN, combined with saliency estimation method (e.g., CAM), is applied to compute the saliency of each node. (d) By applying two different thresholds upper and lower to the resulting saliency map, we oblain a salient subgraph (red) and a non-salient subgraph (blue), while the remaining nodes are shown in gray. In this example, certain spatial regions become salient at two different time steps. Finally, we perform statistical hypothesis testing and compute p-valuc. In this example, p 0.05 indicates statistical significance.
ERR is well-known class of stimulus-induedd voltage shifts, widely used in ncuroscience and cognitive science study brain responses, cognitive processing, and sensory perception. They offer key insights into neural dynamics and have applications in clinical diagnostics, brain-computer interfaces, and cognitive neuroscience.
2

---

Published in Transactions on Machine Learning Research (09/2025)
To the best of our knowledge, this study is the first to propose rigorous statistical testing framework for assessing the reliability of GNN saliency maps. A fundamental challenge in conducting such statistical tests is that the same dataset is used both to select the salient subgraph and to perform the test itself. This practice violates the standard statistical assumption that the hypothesis should be specified independently of the data used for testing. This issue is widely known as double-dipping in the statistical literature (Breiman 1992: Kriegeskorte et al., 2009; Benjamini 2020). When EEG signals contain noise, the saliency map tends to highlight and extract false salient subgraphs that are affected by the noise and are not truly important. If we then test these subgraphs using the same EEG data (i..., the data that contains the same noise), we risk accepting patterns that are in fact artifacts of the noise. In other words, the Type I error rate is inflated, a phenomenon often referred to as selection bias, and the results of statistical tests become unreliable. Note that this double-dipping problem is unavoidable, as saliency maps are designed to explain the model's 's prediction for a specific input instance, which prevents the use of separate datasets for estimation and testing, Therefore, we are inevitably required to test a data-driuen hypothesis the salient subgraph-usingg the same data that was used to select it.
We address this challenge by employing Selective Inference (SI), a statistical testing framework that has attracted significant attention over the past decade for testing data-driven hypotheses (Fithian et al. 2014 Loftus & Taylor 2014; Lee et al., 2016). The fundamental principle of SI is to perform statistical testing while accounting for the data-driven selection of hypotheses. By incorporating the selection process into the analysis, SI effectively mitigates the inflation of Type I error caused by data-driven selection. In this work, we analyze the selection mechanism underlying GNN saliency maps and incorporate it into statistical testing via the ST framework. The proposed statistical test yields valid p-vauues and enables reliable evaluation of the saliency maps and properly controll the Type I error rate at the nominal significance level.
As a proof of concept for statistical testing on GNN saliency maps, we focus on a standard GNN architecture with CAM, a fundamental method for saliency computation. However, the proposed framework is applicable to a wide range of GNN architecturos and saliency mothods that satisfy piecewise lincarity. Piccewise linearity is a property that arises in various graph architectures, such as Graph Convolutional Networks (GCNs) and Graph Isomorphism Networks (GINs) (Xu et al. 2019) with ReLU activation, as well as in gradient-based saliency methods, including Grad-CAM, applied to these architectures. We also assume that the imput graphs are attributed graphs, where each node is associated with continuous feature vectors, in the EEG example described above. A more detailed discussion of limitations and scopes is provided in Section 5
Related work. Interpretable machine learning has received increasing attention in GNNs Yuan et al. 2022). Among various approaches, saliency-based approaches have emerged as a prominent category. Saliency- methods that infer importance for input features are known as feature- based methods, with Class Activation Mapping (CAM) and Grad-CAM being the most well-known examples. These methods were first introduced in the context of Convolutional Neural Networks to identify important input regions (Simonyan et al., 2013; Selvaraju et al., 2017). CAM for GNNs (Pope et al. 2019) extends CAM to graph data by using node feature activations to identify influential nodes and edges. Its extension, Grad-CAM for GNNs (Pope et al. 2019), incorporates gradient information to make it applicable to a broader range of
GNN models. Other feature-based saliency map methods include GraphLIME (Huang et al., 2022), which
uses local surrogate models for feature-level explanations, and GraphSVX (Dvval & Malliaros) 2021 which
applies Shapley value approximations to quantify node and edge contributions. In these methods, sets of highly influential nodes can often be interpreted as salient subgraphs. Alternatively, subgraph- based meth- ods, including GNNExplainer (Ying et al.] 2019) and SubgraphX (Yuan et al., 2021). , directly infer such structures. However, several studies (Li el al. 2024blal a) have highlighted the fragility of interpretability methods for GNNs, since small perturbations to the input graph can significantly alter saliency, thus reduc- ing their reliability. To our knowledge, this is the first study to propose principled statistical framework for asscssing the reliability of GNN saliency maps. Statistical significance alone is not sufficient for inter- pretability However, it enables us to use saliency maps to discover underlying patterns in the input data while controlling the Type I crror rate.
2Qur method can be viewed as a complementary metric of interpretability; see Section
3

---

Published in Transactions on Machine Learning Research (09/2025)
Over the past decade, SI has been actively studied to offer statistical tests for data-driven hypothesis selection. ST was initially developed to evaluate the reliability of feature selection in linear models (Fithian et al. 2014
Tibshirani et al.] 2016; Loftus& & Taylor
2014 Suzumura et al. 2017 Le Duy & Takeuchi] 2021
Sugiyama
ct a..
2021 Duy & Takouchi 2022 and later extended to other problem scttings (Lee et al., 2015 Choi 8L al.
2017 Neufeld et al.) 2022 Shiraishi et al. 2024a Matsukawa et al. 2024). In the context of deep
lcarning, ST was first introduced by Duy et al.
(2022) and later expanded for CNNs (Miwa. et al. 2023 Katsuoka et al., 2024; 2025), transformers (Shiraishi et al. (0224a) and RNNs (Shiraishi et al. 2024b).
2024
Despite growing interest in explainability for GNNs, rigorous statistical testing for GNN interpretations
remains open challenge. In this study, we propose novel statistical test for GNN saliency maps, which performs statistical test conditioned on the selected salient subgraph using the SI framework.
Contributions. Our contributions can be summarized as follows:
We propose framework to quantify the statistical significance of GNN saliency within the con- text of statistical testing. This framework enables the quantitative evaluation of the reliability of GNN saliency in the form of p-values. In our framework, we extract a salient subgraph and non- salient subgraph from the saliency map and perform a statistical test to evaluate its difference (see Section 3
We propose an SI-based approach to obtain statistically valid p-values for the aforementioned sta- listical test. Our method is an exact (non-asymplotic) inference method that works well even with a small sample size. We leverage the piecewise linear structure of GNN to compute the p-values efficiently (sce Section
We conducted experiments on synthetic and real-world datasels, through which we show that our proposed method can control the Type I error rate and provides good results in practical applications. Our code available at https:///itthu www.oiissm//aaaeeeeeaceceeeeeeee for gnn (see Section 6
2
Problem Setup
In this section, we briefly explain the GNN, its saliency map method and the extraction of salient subgraphs.
2.1 GNNs and Saliency Maps
First, we define the graph data as follows:
Baxd is the accumulated feature vector of all Gx = A),
where A E {0, 1) is the adjacency matrix with n nodes, and Ai 1 if there is an edge between nodes and j, and A; 0 otherwise. X (.,,,,,,,, nodes in the graph, where T, Rd is the feature vector of node i. In the case of EEG data in Section [ represents segment of the time series, and the adjacency matrix A is constructed based on the spatial adjacency of sensors and the temporal continuity of the segments.
As a proof concept for statistical testing on GNN saliency maps, we focus on a standard GNN architecture with CAM, a fundamental method for saliency computation. Figure 2 illustrates standard architecture of a GNN equipped with CAM (Pope et al. 2019). CAM a widely used technique for interpreting neural network decisions by identifying input regions most influential to the output. In the context of GNNs, we adopt dual-branch architecture that enables both graph-level prediction and node-wise saliency computation. Specifically, a stack of GCN layers first encodes the input graph into node embeddings. These embeddings are then processed through two distinct paths: one aggregates node features using global average pooling followed by a linear classifier; the other applies CAM. The CAM layer computes node-wise scores by applying the transposed classifier weights to the node embeddings. The approach of CAM enables efficient saliency estimation without additional training overhead. We show the details of the GCN layer and CAM layer in Appendix A
4

---

Published in Transactions on Machine Learning Research (09/2025)
GCN Layer
GCN Layer
GCN Layer
Input features
GAP
Linear
Class
X of
y
W1 x
X1
Wa da
X
W2 de-1 x
X
x
score
de
de
Adjacency matrix
CAM
Saliency
map
Figure 2: Architecture of GNN equipped with CAM. The input consists of node feature matrix X and adjacency matrix A. Multiple GCN layers perform neighborhood aggregation and feature transformation. The resulting node embeddings are processed in two parallel branches: one for graph-level classification via global average pooling and a linear layer, and the other for saliency computation using CAM. The CAM branch computes class-wise node relevance scores by applying the transposed classifier weights to the node embeddings.
2.2 Salient Subgraphs
Our goal is to evaluate the reliability of saliency maps generated by GNNs. As the output of the CAM layer, we obtain a saliency map S(Gx) [0, 1j" where each node is assigned a contribution score S,GGx) [0. 1]. representing its importance in the model's prediction. To evaluate the reliability of 8(Gx), we define the salient subgraph and non-salient subgraph and investigate whether they have statistically significant differences. From S(Gx), we identify the set of nodes V contributing to the GNN classification. This set can be determined as follows with an arbitrary threshold E [0, 1]:
V {ii [n] S(Gx)) TuF 2lml.
(1)
We refer to the subgraph induced by V as the salient subgraph, as it contains the most influential nodes in the model's prediction. Similarly, the non-salient subgraph is defined using the threshold t E [0, 1] for n. Tu:
= [n] ((G))) S n) 2
(2)
For simplicity, we denote the set of salient and non-salient subgraphs as
Vx = (²}
Our goal is to quantify the statistical significance of graph saliency by evaluating the feature-wise differences between the salient node sets v and the non-salient node sets Vx as p-values. A statistically significant difference indicates that the observed saliency region has some mcaningful interpretation. In contrast, lack of statistical significance suggests that the observed saliency region may simply be due to noise and could be meaningless.
3 A Statistical Testing Framework for GNN Saliency
In this section, we present our first contribution: a framework for quantifying the statistical significance of GNN saliency within the context of statistical testing. This framework allows for the quantitative assessment of GNN saliency reliability through p-values.
3.1 Assumptions
We formulate a statistical test to quantify the reliability of saliency maps generated by GNNs. For simplicity,
we introduce the accumulated feature vector of all nodes in the graph as (xI, ...,,?, T e Rnd To formulate the problem a statistical test, we assume that feature vector X a random voctor drawn from the following statistical model:
X 1 + e, (O,,E),
5

---

Published in Transactions on Machine Learning Research (09/2025)
where j (MI pa ..... -.) pT) Rad is the unknown true signal and Rad is the Gaussian noise with co- variance matrix - The model in (4) above is general in that it makes no prior structural assumptions about the signal in the feature vectors, while assuming normality for the noise (see Appendix E.1 for experiments verifying the robustness against violations the normality assumption).
Given a trained GNN model, we can obtain a saliency map S(Gx) E [0, 1) and salient subgraph V and non-salient subgraph Vx by and
3.2 Statistical Test
To assess the significance of the salient subgraph, we formulate the problem as hypothesis test to compare the mean feature values between the salient subgraph V and the non-salient subgraph Vx. Specifically, we consider the following null hypothesis is Hn and the alternative hypothesis is H1:
Ho
He,s
Pa.j
V
DE KE|d
uEV.JElO
vs.
(5)
H1
Σ
Hug +
Σ
Pa.j.
[V NEV
V
JE
where Mv is the i-th element of vector pe. which denotes the true signal of the i-th feature of node e. The mull hypothesis Hg assumes that there is no difference in the mean feature values between the two subgraphs, implying that the selection of salient nodes does not correspond to any meaningful distinction in feature space. The alternative hypothesis H1 indicates that the saliency map captures meaningful char- acteristics of the graph. Note that both Ho and Н₃ are dependent on data X, iee. they are data-driven hypotheses. Unlike traditional hypothesis testing, where hypotheses are fixed in advance, these hypotheses behave probabilistiaall data-driven hypotheses.
Section 3.4 we introduce the SI framework as a valid testing approach for such
A natural way to define the test statistic, which quantifies the difference stated in
5 is as follows:
T(X)
Tu,i
Σ
Fu.j.
(6)
V
The test statistic of 6 measures the discrepancy between the mean feature values of the salient subgraph and the non-salient subgraph. Note that the test statistic can be rewritten as T(X) = 17 X, where n Rnd is weight vector (see Appendix B for the detailed definition). For convenience, we a normalized version of this statistic without loss of generality:
7
X
T(X)=
(7)
1) En
To perform the hypothesis test, first determine the sampling distribution of the test statistic T(X) under the null hypothesis Ho, and then compute the p-value as the probability of obtaining the observed statistic (or a more extreme onc) under this distribution. the p-value less than the significance level a E (0, 1) (e.g,; 0.05), we reject Hg and conclude that the salient subgraph significantly different from the non-salient subgraph. Our goal to compute the p-value which satisfies
(8) The property in means that the Type I error rate is controlled at any significance level a E (0, 1), and the test is said to be valid. A statistical test is said to be valid if the p-values obtained by the test satistifics the property in (
PHo (p S a) a, Va E (0,
We assume that the covariance matrix known for simplicity and discuss the scenario when use sample estimate of the covariance matrix in Appendix F.2

---

Published in Transactions on Machine Learning Research (09/2025)
3.3 Challenges in Computing Valid P-Values
A key challenge in performing this test lies in the fact that the hypothesis is data-driven- is, the mull hypothesis Ho depends the data X. To compute the p-value, which quantifies the extremeness of the observed value under Ho, we need to fix Hg in some principled way.
Here, we describe a method referred to as the naive method. Although this method is not valid as a statistical test, it serves as a useful contrast to motivate our proposed approach. In the naive method, the randomness of Hy is ignored. It does not account for the fact that the salient subgraph is selected based on the data. Therefore, it assumes that the null distribution of the test statistic T(X) follows the standard normal distribution. Using this null distribution, the p-value for given observed value X is defined as
Pnaive = PHo (((()) [T(X
(9)
However, in reality, treating Ho as non-random is not valid, so the naive method does not guarantee the required property in (8), leading to an inflated Type error rate. Intuitively, this means that the saliency map may be overly emphasized, and the naive method may incorrectly judge it as statistically significant. As a result, the test statistic, which is defined based on difference between the two subgraphs, more likely be large, loading to an increased rejection rate of the null hypothesis. This issuc is known as selection bias in the SI literature (Lee et al. 2016). As shown in Section our experimental results demonstrate that selection bias leads to inflated Type error rate, exceeding the specified significance level. Our main contribution is to propose a statistical test that resolve this issue based on the SI framework.
3.4 Concept of Selective Inference
We introduce the framework of SI, also known as post-sclection inference, to compute valid p-values. The key idea behind SI is to perform conditional hypothesis testing, where the inference is conditioned on the selection event that the hypothesis Ho selected based on the data. In our setting, this corresponds conditioning on the selected subgraphs:
T(X) (Vx = Vx
(10)
The conditioning in 110 means that we only consider the X whose subgraph Vx is the same as the observed one Vx Conditioning the selection event allows to treat Ho fixed. The selective p-value computed under this conditional framework represents the probability that the observed test statistic T(X could have ariscn by chance, given that the selection event has occurred and the mull hypothesis holds. By quantifying graph saliency based on the selective p-value, we can control the Type error at a desired significance level.
4 Selective P-Values for Graph Saliency
In this section, present second contribution: method for computing valid selective p-values that appropriately quantify the statistical significance of graph saliency in the context of the statistical testing problem introduced in the previous section.
4.1 Definition of Selective P-Values
The parameters conditional sampling distribution 11) contain not only the parameter of interest, which is related the test statistic, but also the muisance parameter. We can eliminate the nuisance parameter by conditioning on its sufficient statistic, which defined as
Emm 2x = -1- En
X.
(11)
7

---

Published in Transactions on Machine Learning Research (09/2025)
The elimination of muisance parameters by conditioning is standard approach in statistics for deriving the
conditional sampling distribution (Lehmann et al. 1986) Existing studies on ST have also conditioned by the
same sufficient statistic Qx in [1] (Fithian et al. 2014
Lee et al. 2016). So, the conditional test statistic
for computing the selective p-value is defined as
T(X) (Vx Vx Qx = 2xoom
(12)
Finally, the selective p-value is defined as
Pselective PHo ((T(X) > [x(xxb)]] X x
(13)
where the conditional data space X' is defined as
X = x E Rnd
Vx = Vx Qx = 2xxobb }.
(14)
4.2 Property of Selective P-Values
The selective p-value 13 satisfies the following theorem.
Theorem 1. Under the rull hypothesis Ho in for any a (0, the selective p-value in satisfies the propery in 18 i.e.,
13
Pno (Peclective 5a) = a.
This is well-known property of the v-value derived through S1. The proof of Theorem | in our setting is given in Appendix C.2 This theorem means that test procedure based on the selective p-value in (13) controls the Type I error rate at any significance level a E (0, 1). Note that this theorem do not require asymptotic discussions to guarantee the validity of the selective p-valuc. In Section 0 we experimentally demonstrate that the selective p-value can control the Type error rale even when the sample size (i.e., the number of nodes and the number of features d) is finite. Furthermore, we emphasize that we make assumptions the training data training process of the GNN. Our method guarantecs control of the Type error rate even when the GNN is trained on ill-conditioned data, such datasets containing substantial number of false positive examples.
4.3 Computation of Selective P-Values
To compute the selective p-value in 13 must characterize the conditional data space X' in which corresponds to all feature vectors X that yield the same selected subgraph Vx the observed one V obe.. This requirement can be viewed as an inverse problem for GNN, and is particularly challenging due to the complexity the GNNs forward computation and decision process. We address this challenge based on the following two key insights. First, the computation of CAM scores can be formulated as a piecewise linear function for a broad class of GNN architectures (sce Lemma D.. Sccond, loveraging this piccewise lincarity, the selective p-value can be computed exactly by reducing the problem to one-dimensional search (see
Lemma 2 which is solvable using techniques called parametric programming (Duy & Takeuchi 2022
Piecewise linearity of GNN saliency maps. The first key observation is that the saliency map com- puted by CAM is a piecewise linear function of the input features. This structure enables us to analytically characterize the conditional data space X' in terms of linear constraints.
Lemma 1. For the network architecture defined in Figure 2 with ReLU activation function, the saliency map S(Gx) is a piecewise linear function of X. That is, the inpul space Rnd can be parlitioned into a finile {
set of convex polytopes {Ra T==1 for some K E N such that in each region Re, S(Gx) is an offine function of X:
VX E RR, Vi E [m], S(Gx)) =
ck (k)) X + +((0)
where ((k)) E RRaxnd and (100 RR. are region-specific coefficients.
8

---

Published in Transactions on Machine Learning Research (09/2025)
The proof is omitted since it follows from standard results In fact, many standard neural network components-sude as linear layers, convolutional layers, and max-pooling operations are also piecewise linear. Therefore, the piecewise linearity of the CAM output holds not only for GCNs but also for a wide range of GNN architectures. This implics that our proposed framework can be readily extended to various types of GNNs beyond those explicitly considered in this paper as a proof of concept.
One-dimensional search. The conditional data space X' consists of a union of convex polytopes, due to the piecewise linearily of the saliency map with respect to the input X E R However, directly characterizing or sampling from X' is computationally difficult because of the high dimensionality of X. To overcome this, we leverage the structure the conditional data space to roduce the problem to a one- dimensional search along a carefully chosen linear path in the input space.
Lemma 2. The set X defined in 14 can be rewritten using a scalor parameter 2 T(X) E R
X = (2) E Rnd
X()) = -a- aa+ta bz, 2 ZE
where
2x E Rnnd
b b= En/ vn 22n E R
and the truncation intervals 2 is given by
2 (2 Va+b= Vx
The proof of Lemma 2 is provided in Appendix C.1 This lemma shows that the conditional data space X lies entirely on a one-dimensional subspace of Rnd parameterized by the scalar paramcter 2. In our setting, X' is the subset of graph data that generates the same salient subgraphs as those of the observed data. Consequently, it suffices to restrict our attention to a one-dimensional subset, which enables efficient. and exact computation of the selective p-value. The remaining challenge is to identify Z.
Parametric programming, To identify the truncation intervals Z, we employ a divide-and-conquer strategy. Specifically, we assume that we have a procedure to compute the interval [L,, Us] for any E R which satisfics: for any r E [L,, U2), the subgraphs Va+br and Va+bz are the same, i.c.,
E U2), Vater Vatbz.
Then the truncation intervals 2 can be obtained as the union of the intervals [Tzz, U2] as
Z =
U
Uz.
(15)
ZER S.R.V..
Vxobo
The aggregation procedure in 15 is known as parametric programmingg originally introduced to S1 field by Duy & Takeuchi (2022). Building on the concept of parametric programming, the problem of identification of 2 is divided into subproblems on how to compute the interval [T.2, U=].
Each subproblem is tractable due to the piecewise linearity of the saliency map. From Lemma | and 2 it follows that (())())) is a piecewise linear function of z. Consequently, the thresholding operations used to define the salient and non-salient subgraphs (1] and (2) can be expressed as system of linear inequalities with respect to z. The explicit formulation of these inequalities is provided in Appendix D.I. In more practical cases, we may want to perform filtering or normalization on the saliency map S())(=)) before thresholding. Many filters (e.g., Gaussian filters) preserve linearity, so the same formulation can be applied. When applying a threshold to saliency map normalized to the range [0, 1]. slightly different formulation is required (see Appendix D.2p. We emphasize that our framework conducts selective inference with consideration of the thresholding process and ensures control of the Type I error rate for any specified threshold.
By solving these linear inequality systems, we can identify each interval [L,, Uz]. and by aggregating them using (15,, we obtain the full truncation set Z. The complete procedure for computing the selective p-value via parametric programming is sunmarized as Algorithm I provided in Appendix D.3
"hhe composition of piccewise linear functions is also piecewisc lincar. Therefore, it suffices verify that cach layer in the GNN (e.g., linear, convolutional, pooling, ReLU) piecewise linear to conclude that the overall CAM computation piecewise linear.
9

---

Published in Transactions on Machine Learning Research (09/2025)
5 Limitation and Scope
In this section, we discuss the scope of the framework and its current limitations from several aspects.
GNN architectures and saliency methods. In this study, as proof of concept, we employed a standard GCN architecture along with the conventional saliency method, CAM. However, our framework is not limited to this specific network architecture or saliency method. As discussed in Section 4 the proposed met hod is applicable when the operations within a NN can be expressed as piecewise linear functions. Although this requirement may appear restrictive at first glance, most operations commonly employed in GCNs are either inherently linear or can be represented by piecewise linear functions. A notable exception arises when nonlinear activation functions, such as the sigmoid function, are used; however, since sigmoid functions can be approximated with arbitrary precision by piecewise linear segments, selective p-values can still be computed with high accuracy. This property similarly holds for GINs. When applying CAM, Grad-CAM, Grad & GradInput (Shrikumar et al. 2017) to these networks, the resulting saliency maps also satisfy the piecewise linearity property, making the proposed method applicable. In the experiments in Section G we applied the proposed method to the GCN with CAM and confirmed that it controlled the Type error rate. In addition, we applied Grad-CAM, Grad, and GradInput to both GCNs and GINs and obtained similar results, which are reported in Appendix G In contrast, architectures such Graph Transformer Networks (Yun et al., 2019) and Graph Attention Networks (Veličkovié et al.] 2018), or saliency methods such GNNExplainer or GraphLIME, contain components that cannot be readily expressed or approximated as piecewise linear functions. Some gradient-base based methods, such as Integrated Gradients (IG) (Sundararajan et al. 2017). are also not piecewise lincar, posing challenges for the direct application of the proposed framework.
Noise distribution. Our data generation model in 4 is general in the sense that no assumptions are made regarding the true signal features μ. On the other hand, our SI framework builds on the normality of the noise, as is the case in other existing SI studies. We experimentally investigated the robustness when the noise deviates from the normal distribution (see Appendix E.1 and found that the type I error can be controlled almost at the nominal significance level. From theoretical perspective, one possible direction to address this issue is to introduce an asymptotic theory (Tian & Taylor 2018 2017 Markovic et al.) 2017). However, the computation of selective p- p-values based on asymptotic theory becomes much more complex, and the computational methods introduced in Section 4 of this paper cannot be directly applied.
Computational complexity. The computational cost of selective p-value calculation using the algorithm proposed in Section 4 depends on the complexity of the GNN architecture and the size of the data. As the GNN architecture becomes more complex, the number of segments in the piecewise linear function increases. Similarly, as the data. size (i.e., the number of samples and features) grows, the event associated with the selection of the saliency region becomes more intricate, resulting in a larger number of segments. An increase in the number of segments leads to more iterations in the while loop of Algorithm| [ thereby proportionally increasing the computational cost. Although the computational cost did not pose a bottleneck in the GNNs and datasets used in our numerical experiments, computational strategics such as parallelization may nood to be considered for larger networks and datasets.
Choice of test statistic. In this paper, we quantified the statistical significance of the GNN saliency by considering the null and alternative hypotheses defined in 5 and employing the test statistic presented in 6 However, our proposed framework is not limited to this specific test statistic. As detailed in Section 3.2
the framework is applicable as long the test statistic can be expressed as linear function r7' X, where n E Rnd is a vector that depends on the data X. Although we believe the test statistic adopted in this study is reasonable, depending on the perspective from which graph saliency is evaluated, it may be worthwhile to consider alternative test statistics that better capture different aspects of saliency.
Thresholding strategy. In this paper, we proposed a framework that controls the Type I error rate for any fixed threshold. Our method also applicable when the range of saliency values normalized before applying the threshold, for cases where the range of the saliency distribution varies depending on the data. In contrast, when adaptively adjusting the threshold according to the characteristics of the saliency distribution,
10

---

Published in Transactions on Machine Learning Research (09/2025)
it is necessary to perform SI that accounts for this process. One promising direction is to introduce new conditioning scheme, inspired by existing studies on selective inference for image segmentation (Tanizaki et al. 2020), which discuss conditioning on thresholding processes that consider the distribution of pixel intensities in image data.
Interpretability. Here, we further extend the discussion to consider the application of selective p-values to a comprchensive ovaluation of interpretability. From one perspective, the proposed method can be re- garded as a statistical means to check plausibility of an obtained saliency map-that is, the degree to which it conforms to expert knowledge. Since the data-generating model in (4) and the null and alternative hy- potheses in (5) can be viewed as a mathematical model such domain knowledge, the proposed method quantifies the plausibility of the explanation in the form of p-values with respect to this model. However, the interpretability of machine learning models is a multifaceted concept. Several evaluation criteria, such fidelity, consistency, and completeness, explicitly focus whether the explanation accurately reproduces the model's behavior. Moreover, criteria such as simplicily assess human readability. Since the proposed method does not directly assess these aspects, challenges remain in employing selective p-values as part of a comprchensive evaluation of interpretability. One possible direction to address this challenge is to use the proposed test as a complementary evaluation metric, in conjunction with existing evaluation metrics for interpretabillty, such as the entropy-based sparsity score of GNN saliency distributions (Funke et al., 2022). Even when a generated explanation lacks interpretability, our testby Theorem [oorectly controls the Type crror rate. Thus, the p-value serves complementary indicator to existing interpretability metrics, helping to guarantee the reliability of the saliency map. The optimal way to integrate the proposed test with existing metrics remains topic for future work. For example, gating strategy could be usedbefore proceeding to interpretability evaluation, apply our test to admit only statistically significant subgraphs as candidate explanations, thereby filtering out false positives due to incidental noise in advance. Weighted ag- gregation of metrics is another possibility. Complementary use with existing metrics expected enhance the robustness and credibility of interpretability assessments.
6 Numerical Experiments
In this section, we compare the proposed method with other methods and demonstrate that the proposed method exhibits high power (true positive rate) while controlling the Type error rate (false positive rate) below the significance level compared to other methods. First, experiments are conducted on synthetic datasets, followed by similar experiments on EEG datasets. The architecture of the GNN and the saliency map used in the experiments are shown in Figure 2 We set the number of GCN layers L 3 and the number of hidden units di 10 for I E [L]. We normalized the saliency map to the range [0, before applying thresholds, which were set to 0.3 and Ta 0.7. All experiments were conducted with significance level of a = 0.05.
6.1 Methods for Comparison
In our experiments, we compare the proposed method (proposed) with three other methods: naive, w/o-pp, and Bonferroni.
naive: This method uses classical z-test without conditioning: that is, we compute the naive p-value as described in Equation 9
This is method to control the Type error rate by using the Bonferroni correction. There are 3 ways to choose the subgraphs Vx. We then compute the Bonferroni-correcte p- vavuue as Pbonferroni = min(1,3' Puaiiee.
Bonferroni:
w/o-pp: An ablation study that excludes the parametric programming technique described in 15
11

---

Published in Transactions on Machine Learning Research (09/2025)
6.2 Synthetic Data Experiments
Setup. To evaluate the Type I error rale, we varied the number of features (d E (5, 10, 15, 20}) and the number of nodes (n E {32, 64, 128, 256)). If not specified, we used d = 5 and n = 256. For each setting, we statistically tested 1,000 graphs Gx = (X, which are generated using the following procedure. The adjacency matrix A E R generated by randomly adding edges such that the average degree of each node is 3. We also generated a null feature vector ~ (0, E); where the covariance matrix Σ R is defined as the Kronecker product > Espace Mieature. We considered two types of covariance matrices:
Independence: Espace In and Eicature Ld-
Correlation: Espace is defined by (Espace)is 0.1 where di is the shortest path length between nodes i and] in a graph, and Ereature is defined by (Eienture)s kt = 0.1
To evaluate the power, we varied the signal strength (6 (1.0, 1.5, 2.0, 2.5]). For each sctting, we iterated 1,000 experiments. In each iteration, we generated a feature vector X ~ (H, E), where is obtained by flipping each element of the 0 E Rnd to ó with probability 0.1. The adjacency matrix is generated in the same way as in the Type error rate experiments. The covariance matrix Σ follows the same two settings as in the Type I error rate experiments.
Results. The results shown in Figure 3 The proposed, w/o-pp, and Bonferroni methods successfully control the Type error rate at the nominal significance level, even under finite sample sizes, whereas the naive method fails due to selection bias. Since naive failed to control the Type error rale, we excluded it from the power analysis. Among the remaining methods, proposed achieves the highest power across varying signal strengths. Soe Appendix E. for results under non-Gaussian scttings, and Appendix E22 for results using estimated covariance matrices. We also confirmed that proposed method can control the Type error rate for any combinations of thresholds n. and Tu (see Appendix F)
proposed
proposed
proposed
0.8
naive
0.8
naive
0.8
Bonferroni
Type Error Rate
Bonferroni
Type Error Rate
Benferrori
w/o-pp
w/o-pp
w/o-pp
0.6
a=0.05
0.6
a=0.05
0.6
0.4
0.2
0.0
0.0
0.0
15
256
1.0
2.0
Number of Features
Number Nodes
Signal
(a) Independence
proposed
proposed
propesed
0.8
naive
0.8
naive
Bonferroni w/c-pp
Type Error Rate
Sonferragi
Type Error Rate
Bonferrori
wlo-pp
w/o-pp
0.6
0500.
0.6
a=0.05
0.6
0.4
0.4
0.4
0.0
0.0
0.0
15
256
1.0
2.0
Number of Features
Number of Nodes
Signal
(b) Correlation
Figure 3: Results on syuthetic data. The left and middle columns show the Type I error rates with varying numbers of features and nodes, respectively. The proposed and w/o-pp methods successfully control the Type I error rate at the a 0.05 level, with nearly overlapping curves, while the naive method fails do so. The results of Bonferroni column show the power with varying signal strength. The proposed method has the highest power.
almost zero, because it is too conservative. The figures in the right
12

---

Published in Transactions on Machine Learning Research (09/2025)
6.3 Real Data Experiments
Setup. We evaluated the effectiveness of our proposed method in detecting spatiotemporal characteristics in multi-dimensional time-series data using a dataset which contains known characteristics. We used the EEG Dataset provided by [Wo et al. (2022). which contains EEG signals recorded during the well-known Rapid Serial Visual Presentation (RSVP) task in neuroscience. This dataset contains two categories of EEG signals: positive and negative. Fach sample corresponds to one-second segments of multidimensional EEG signals recorded after the presentation of visual stimuli. The positive data are known to contain stimulus-induced positive potential shift, whercas the negative data are known to show little to no such shift. To demonstrate the effect iveness of the proposed framework, we applied it to the task of identifying the spatiotemporal characteristics of the evoked EEG response, specifically discovering the sensor locations and latencies at which the potential shift occurs. The positive potential observed in the positive data is referred to as the P300, which typically emerges approximately 300 to 600 milliseconds after stimulus presentation. It well-cstablished that the P300 manifests predominantly over parictal and frontal scalp regions. In this experiment, we investigated whether our proposed method yields results consistent with these established findings.
The dataset contains 55 participants, each with 40 positive and 560 negative samples, resulting in total of 33,000 EEG samples. Each sample consists of recordings from 28 EEG sensors capturing the scalp-wide potential distribution, with each sensor measuring 50 time points corresponding to the first second after stimulus onset. To represent the data as a graph, each time series was segmented into non-overlapping windows of length 5, resulting in total of 28 x 10 segments. Each segment was treated as a node in the graph representation of the EEG data, where each node encapsulates temporal features from specific EEG sensor. Edges between nodes were defined based on spatial temporal adjacency: an edge was added if two nodes originated from the same sensor in consecutive time windows, or from adjacent sensors at the same time step. For further details on the dataset and preprocessing steps, see Appendix H.T For training the GNN model, we used EEG data from 15 participants. For the remaining 40 participants, we utilized 520 negative samples per participant for covariance estimation, and used the remaining samples as test data.
The results of proposed and naive are shown in Figure and In the positive example, the saliency method successfully identifies the salient subgraph, which corresponds to the P300 component of the EEG signal. The p-values obtained from naive tend to be small even for the negative class EEG signals, indicating that they are not suitable for quantifying the reliability of salient subgraphs. In contrast, the p-values of proposed are generally large for positive data and small for negative data. This result suggests that proposed can effectively detect true positive cases while avoiding false positive detections. For more examples, see Appendix H.2 We also conducted experiments with modified real datasets, demonstrating that proposed can control the Type I error rate when the real dataset modified to follow the null hypothesis
Results.
assumptions; see Appendix H.3
7 Conclusion
In this study, proposed novel statistical testing framework for assessing the reliability of GNN saliency maps by leveraging S1. Our framework computes statistically valid p-values, ensuring that extracted salient subgraphs reflect meaningful contributions rather than arising by chance. Through extensive experiments on synthetic and real-world datasets, we demonstrated that our method effectively mitigates Type I errors. As explainability in GNNs continues to be a crucial research area, our approach provides a rigorous statistical foundation for evaluating model interpretations, paving the way for more reliable and trustworthy GNN- basod decision-making systems.
Broader Impact
The selective inference framework proposed in this study mathematically underpins the reliability of GNN saliency explanations by rigorously controlling the Type I crror rate at any chosen threshold. This enables safer and more transparent operation of decision-making systems based on GNNs-for example, in health- care (such as F.G. analysis and other biomedical data), weather and environmental modeling, or industrial
13

---

Published in Transactions on Machine Learning Research (09/2025)
Saliency map
Salient subgraph
Most salient time-series
Ampiltude (eV]
selective 000iiiv0e_p0000,,,, naive soive_p=0.000
Figure 4: Positive example. The left figure shows the saliency map, where brighter nodes indicate higher importance. In this figure, the x-axis corresponds to the anterior direction the scalp, while the y-axis corresponds to the rightward direction, providing a spatial interpretation of the saliency distribution. The middle figure shows the obtained subgraphs, where the red nodes are selected as salient subgraph and the blue nodes are selected non-salient, subgraph. The right figure shows the EEG signals of the most salient channel and its salient and non-salient segments (red and blue, respectively). CAM successfully identifies the segments of EEG signals that exhibit a potential shift. Notably, the identified salient segments correspond to iositive deflections occurring approximately 300600 milliseconds post-stimulus, predominantly over parietal and frontal scalp regionscharacteristiis consistent with the well-documented features the P300 component. Furehermore, the waveform morphology of the salient segment shown in the right figure closely resembles the pattern reported in Figure Won al. (2022), further supporting the neurophysiological plausibility of the identified explanation. Below the example, we report the corresponding p-values, demonstrating that the proposed method correctly detects the positive sample.
Saliency map
Salient subgraph
Most salient time-series
Amplituae (μv)
Time [ms]
Silectiveep=0.6111 naive_p=0.000
Figure Nogative example. See Figure for the interpretation. Our selective p-value is sufficiently large, indicating correct exclusion of spurious salieney, whereas the naive p-value is misleadingly small.
anomaly detection by mitigating decisions based on spurious or overly optimistic interpretations. par- ticular, noisy biomedical signals are known carry the risk of false positive saliency leading diagnostic errors, and our method helps extract only statistically significant patterns, providing clinicians, researchers, and engincers with trustworthy grounds for interpretation and supporting reliable explanations.
Acknowledgments
This work partially supported by JST CREST (JPMJCR21D3, JPMJCR22N2), JST Moonshot R&D (JPMJMS2033-05), and RIKEN Center for Advanced Intelligence Project and RIKEN Junior Research Associate Program.
References
Yoav Benjamini. Selective inference: The silent killer of replicability. 2020.
Leo Breiman. The little bootstrap and other methods for dimensionality selection in regression: X-fixed prediction error. Journal of the American Statistical Association, 87(419):738 -54, 1992.
Yunjin Choi, Jonathan Taylor, and Robert Tibshirani. Selecting the number of principal components: Estimation of the true rank of noisy matrix. The Annals of Slatisties, 45(6):2590 2617, 2017.
14

---

Published in Transactions on Machine Learning Research (09/2025)
Andac Demir, Toshiaki Koike- Akino, Ye Wang, Masaki Haruna, and Deniz Erdogmus. Eeg-gun: Graph neural networks for classification of electroencephalogramn (veg) signals. In 2021 1 49rd Annual International Conference of the IEEE Engineering in Medicine & Biology Society (EMBC), pp. 1061-1067. LEEE, 2021.
Alexandre Duval and Fragkiskos D Malliaros. Graphsvx: Shapley value explanations for graph neural networks. In Machine Learning and Knowledge Discovery in Databases. Research Track: European Con- ference, ECML PKDD 2021, Bilbao, Spoin, Seplember 13 17, 2021, Proceedings, Part II 21, pp. 302 318. Springer, 2021.
Vo Nguyen Le Duy and Ichiro Takeuchi. More powerful conditional selective inference for generalized lasso by parametric programming. The Journal of Machine Learning Research, 23(1):1354441335) 2022.
Vo Nguyen Le Duy, Shogo Iwazaki, and Ichiro Takeuchi. Quantifying statistical significance of neural network- based image segmentation by selective inference. Advonces in Newral Information Processing Systems, 35: 31627-31639, 2022.
William Fithian, Dennis Sun, and Jonathan Taylor. Optimal inference after model selection. arXiv preprint 14Xiv:1410.220 140.225411. 2597,, 2014.
Thorben Funke, Megha Khosla, Mandeep Rathee, and Avishek Anand. Zorro: Valid, sparse, and stable explanations in graph neural networks. IEEE Transactions on Knowledge and Data Engineering, 35(8): 8687-8698, 2022.
Qiang Huang, Makoto Yamada, Yuan Tian, Dinesh Singh, and Yi Chang. Graphlime: Local interprctable model explanations for graph neural networks. IEEE Transactions on Knowledge and Data Engineering, 35(7):6968-699) 6972, 2022.
Teruyuki Katsuoka, Tomohiro Shiraishi, Daiki Miwa, Vo Nguyen Le Duy, and Ichiro Takenchi. Statistical test on diffusion model-based anomaly detection by selective inference. arXiv preprint arXiv:2402.0 11789,
2024.
Teruyuki Katsuoka, Tomohiro Shiraishi, Daiki Miwa, Shuichi Nishino, and Tchiro Takeuchi. si4onnx: A python package for selective inference in deep learning models. arXiv preprint arXiv:2501.14415 2025.
Dominik Klepl, Min Wu, and Fei He. Graph neural network- based eeg classification: A survey. IEEE Transactions on Neural Systems and Rehabilitation Engincering, 02:493-503, 2024.
Nikolaus Kriegeskorte, W Kyle Simmons, Patrick SF Bellgowan, and Chris T Baker. Circular analysis in systems neuroscience: the dangers of double dipping. Nature neuroscience, 12(5):535, 2009.
Vo Nguyen Le Duy and Ichiro Takeuchi. Parametric programming approach for more powerful and general lasso selective inference. In International conference on artificial intelligence and statistics, pp. 901-909. PMLR, 2021.
Jason D Lee, Yuckai Sun, and Jonathan E Taylor. Evaluating the statistical significance of biclusters. Advances in neural information processing systems, 28, 2015.
Jason D Lee, Dennis L Sun, Yuekai Sun, and Jonathan E Taylor. Exact post-selection inference, with application to the lasso. The Annols of Statistics, 44(3):907 927, 2016.
Erich Leo Lehmann, Joseph P Romano, et al. Testing statistical hypotheses, volume 3. Springer, 1986.
Jiate Li, Meng Pang, Yun Dong, Jinyuan Jia, and Binghui Wang. Graph neural network explanations are fragile. arXiv preprint arXiv:2406.0911 03199, 2024a.
Zhong Li, Simon Geisler, Yuhang Wang, Stephan Günnemann, and Matthijs van Locuwen. Explainable graph neural networks under fire. arXie preprint +xXiv2446.06417, 2024b.
Xuefen Lin, Jielin Chen, Weifeng Ma, Wei Tang, and Yuchen Wang. Ecg emotion recognition using improved graph neural network with channel selection. Computer Methods and Programs in Biomedicine, 231:107380, 2023.
15

---

Published in Transactions on Machine Learning Research (09/2025)
Joshua R Loftus and Jonathan E Taylor. A significance test for forward stepwise model selection. arXiv preprint Xrx:::4055.3000 2014.
Jelena Markovic, Lucy Xia, and Jonathan Taylor. Unifying approach to selective inference with applications vross-validation. arXiv preprint Xrxi::1703 110097059555 2017.
Tatsuya Matsukawa, Tomohiro Shiraishi, Shuichi Nishino, Teruyuki Katsuoka, and Ichiro Takeuchi. Statis- tical test for auto feature engineering by selective inference. arXiv preprint ar 10..11..1111. 19768, 2024.
Daiki Miwa, Duy Vo Nguyen Le, and Ichiro Takeuchi. Valid p-value for deep learning- driven salient region. Proceedings of the 11th International Conference on Learning Representation, 2023.
Daiki Miwa, Tomohiro Shiraishi, Vo Nguyen Le Duy, Teruyuki Katsuoka, and Ichiro Takeuchi. Statistical test for anomaly detections by variational auto-encoders. arXiv preprint arXiv:2402.0372 2024.
Anna C Neufeld, Lucy T. Gao, and Daniela M Witten. Tree-values: selective inference for regression trees.
Journal of Machine Learning Research, 23(305):1-43, 2022.
Phillip E Pope, Soheil Kolouri, Mohammad Rostami, Charles E Martin, and Heiko Hoffmann. Explainability methods for graph convolutional neural networks. In Proceedings of the IEEE/CVV conference computer vision and pattern recognition, pp. 10772-10781, 2019.
Ramprasaath R Selvaraju, Michael Cogswell, Abhishek Das, Ramakrishna Vedantam, Devi Parikh, and Dhruv Batra. Grad-cam: Visual explanations from deep networks via gradient-based localization. Proceedings of the IEEE international conference on computer vision, pp. 618-626, 2017.
Tomohiro Shiraishi, Tatsuya Matsukawa, Shuichi Nishino, and Ichiro Takeuchi. Statistical test for feature selection pipelines by selective inference. ar preprind or arXi::2406. 1001661199900 18902, 2024a.
Tomohiro Shiraishi, Daiki Miwa, Teruyuki Katsuoka, Vo Nguyen Le Duy, Kouichi Taji, and Ichiro Takeuchi.
Statistical test for attention maps in vision transformers. In Forty-first International Conference on Machine Learning, 2024b. URL https: http::/wwww.ttttooootoeeoooooooo
Avanti Shrikumar, Peyton Greenside, and Anshul Kundaje. Learning important features through propagating activation differences. In International conference on machine learning, pp. 3143-3152 PMIR, 2017.
Karen Simonyan, Andrea Vedaldi, and Andrew Zisserman. Deep inside convolutional networks: Visualising image classification models and saliency maps. arXiv preprint 1xXi:1312.60334 2013.
Kazuya Sugiyama, Vo Nguyen Le Duy, and Ichiro Takeuchi. More powerful and general selective inference for stepwise feature selection using homotopy method. In International Conference on Machine Learning, pp. 9891-9901. PMLR, 2021.
Mukund Sundararajan, Ankur Taly, and Qiqi Yan. Axiomatic altribution for deep networks. In International conference on machine learning, pp. 3319 3328. PMLR, 2017.
Shinya Suzumura, Kazuya Nakagawa, Yuta Umezu, Koji Tsuda, and Ichiro Takeuchi. Selective inference for sparse high-order interaction models. In Proceedings of the 34th International Conference on Machine Learning-Voon Volume 70, pp. 3338 3347. JMLR. org, 2017.
Kosuke Tanizaki, Noriaki Hashimoto, Yu Inatsu, Hidekata Hontani, and Ichiro Takeuchi. Computing valid p-values for image segmentation by selective inference. In Proceedings of the IEEE/CVE conference on computer vision and pattern recognition, pp. 0553-9562. 2020.
Xisoying Tian and Jonathan Taylor. Asymptotics of selective inference. Scandinavion Journal of Statistics, 44(2):480-499, 2017.
Xiaoying Tian and Jonathan Taylor. Selective inference with a randomized response. The Annols of Statistics, 46(2):669-770) 2018.
16

---

Published in Transactions on Machine Learning Research (09/2025)
Ryan J Tibshirani, Jonathan Taylor, Richard Lockhart, and Robert Tibshirani. Exact post-sclection inference for sequential regression procedures. Journal of the American Stalistical Associalion, 111(614):600-628 -2000 2016.
Petar Velićković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio.
Graph Attention Networks. International Conference Learning Representations, 2018. URL https: accepted as poster.
Kyungho Won, Moonyoung Kwon, Minkyu Ahn, and Sung Chan Jun. Eeg dataset for rsvp and p300 speller brain-computer interfaces. Scientific Data, 9(1):388, 2022.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? International Conference on Learning Representations, 2019. URL httphhtt/ppeneerriiii http://ppemrrriieeeneeeeoottttt net/forum?id-
ryUs61A5KM.
Zhitao Ying, Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, and Jure Leskovec. Gnnexplainer: Generating explanations for graph neural networks. Advonces in neural information processing systems, 32, 2019.
Hao Yuan, Haiyang Yu, Jie Wang, Kang Li, and Shuiwang Ji. On explainability of graph neural networks via subgraph explorations. In International conference machine learning, pp. 12241 12252. PMLR, 2021.
Hao Yuan, Haiyang Yu, Shurui Gui, and Shuiwang Ji. Explainability in graph neural networks: taxonomic survey. IEEE transactions on pattern analysis and machine intelligence, 45(5):5782255)) 5799,, 2022.
Seongjun Yun, Minbyul Jeong, Raehyun Kim, Jaewoo Kang, and Hyunwoo J Kim. Graph transformer networks. Advances in neural information processing systems, 32, 2019.
17

---

Published in Transactions on Machine Learning Research (09/2025)
A Graph Neural Network Architecture
GCN layer. The GCN layer is layer that computes the output of the GNN by aggregating the information of the neighbors of each node. The GCN layer is defined as
X₁ (A
where 1 E [T.] is the layer index, Xi-1 E Raxd-1 is the input of the layer, X Baxd is the output of the layer, and W E [Rd-1xxd xd: is the weight matrix. is the activation function, which is typically a nonlinear function such as ReLU. A E Raxx is the normalized adjacency matrix which is defined as D-1/22211 A3//2D-114 1/2 where = (A) E Nax" the degree matrix.
CAM layer. The CAM layer is a layer that computes the saliency map, which the contribution of each node to the decision of the GCN-based GNN. The use of the CAM layer assumes that the class score of the GNN uses the output of the GAP layer. The GAP layer is defined as
-X- 1
Y2
where X₁ E 1R is the output of the GCN layer just before the GAP layer, and E Rdi is the output vector of the GAP layer, which is the aggregation of the features of the entire graph for each feature dimension. The classification score of class e is defined as
= = Wes
Wey
where we Rd is the weight vector of class c. The CAM layer utilizes we and the output of the GCN layer just before the GAP layer X₁ to compute the class saliency map, wchich is defined
(Xrws) R"
where the activation function o is the ReLU function.
B Detailed Definition of the Test Statistic
The weighted vector 17 RRnd in the test statistic T(X) = .7) X in is defined as follows:
n n= (x) (x)) E Rndd
with component-wise definition:
1 Rd
if V
[V
(X)
1ER Rd
i
Vxl
0 Rd
otherwise.
18

---

Published in Transactions on Machine Learning Research (09/2025)
C
Proof of Theorem
C.1 Proof of Lemma 2
According to the conditioning on Qx = Qxobe we have
Qx 2x = ( (In
Erm
X = 2xota - X = =a bz,
En TEEn
Then, we have
{x E R Vx = Vx 2x = 2x
= {X E R Vx = Vx X = a + bz, R}
{a + ba E R"
Vatb: = Vx E IR}
{a+ be R 2)
C.2 Proof of Theorem
Based on intervals set in Lemma 2 we can derive the null distribution of the test statistic in 12 as a truncated normal distribution. Specifically, under the null hypothesis Ho in (5), the conditional test statistic in [2) follows the truncated standard normal distribution TN 1, 2) with mean 0 and standard deviation 1, where Z is the truncation intervals defined in Lemina 2 Thus, by probability integral transformation, we have
Psclective
(Vx Vxobe, Qx = xx ) ~ Unif(0, 1),
which leads to
IP Ho (Peelective a Vx Vx Qx 2xxos)=== =a, a, Va (0, 1).
For any (0, 1), by marginalizing muisance parameters, have
P PHo (Pselective a Vx = Vxxa.)) = / IP (Peelective a Vx Vx 2x =
x PHo (2x = =xxom Vx Vx (xxox)d2xx. xQ
PHO (ex Qx 1/x Vxobe Xob
a.
Therefore, we also obtain
F (Peelective 5 5a) =
Σ PHO (Vx PP (Peolective a Vx Vx
V Vaass
PHo (V (X
a
Vxobe
a.
19

---

Published in Transactions on Machine Learning Research (09/2025)
D Details of Algorithm
D.1 How to Identify the Interval of
From Lemma about the piecewise linearity of the GNN saliency map and Lemma 2 we can see that the saliency map (z)) is a piecewise linear function of 2, i... Vr E [L,, U2), Vi E [n], S, (Gx)) = = p,r.
If we have the interval [T/2, Ug]: we can compute the interval [T.z, U2] by the following formula:
[2,U - [ [:]
(16)
where [ they are defined as
U and
are the intervals Va+bz is same and Va+oz is same, respectively. Specifically,
[L
n ()) ie(n]
max (L's, Iumei UU!
if (3: > OAiE V=+ V (3. <0ii & Vz (17)
(1) (1)
L'z, min (U/, Tumei
if (3. < OAAi OAiEVa.. (++be) V (3, 0 & V Vo-oo);
[2200-] = n
L1_ U2),
sE|n]
max (L'z) =im U3
if (B. > 00004 V V V <B<<oniV (18)
(1) (1)
T/4 min (U2. I-
(8, < 00Ai $ V Va+b2) (8, > -Aiie Vo+b..
D.2 Normalization of Saliency Map
In Appendix D.I] we consider the case where the saliency map is not normalized. Here, we consider the case where we want to normalize the saliency map before applying a threshold. With a slight abuse of notation, we denote the saliency of i-th node (Gx)) as S, The normalized saliency Sporm is then defined as:
S. min(S))
Shorm
(max(S:) min
provided that max St + min S.. Then subgraphs V and Vx are defined
V = {i E [n] Suorm > >u).
VX = {i E [n] Sporm <T}.
In this case, the interval [4 [U+] in 17 and [ Ug] in 18 are modified as follows:
| n (1). (1) (i),
sE[n]
[max f((,))
(3 8 AiEV 14bb) V < V v4bb2)
Ai
min (((T))
if (3 < 8 AiE v. vo+b.) V (8 8* Ai V+ V++bb):
[,,05]] n [L_ (1) (i).
sE(n]
[max (L's, f((m)) U3] [L', (U% f(())]] if (8, < 8 ^i $ Vo+b=) (3,> 8" AiE V
( (8, 3* Ai 3i Vo+be) ( V Vo+ba)
(1) (i))
where 8"= =B, + (1 - B,, for p arg (S:) and q arg maxmmxx)) (S;), and fi is defined as
f((T) TCp (1 T C) C2
B - 3*
20

---

Published in Transactions on Machine Learning Research (09/2025)
D.3 Algorithm for Computing the Selective p-value
Algorithm 1: Computation of the selective p-value
Input: ox
Output: Pselective
2 + 0;
Obtain Vx from ox by
3
Compute a, by Lemma 2
Initialize z to sufficiently small value;
while is not sufficiently large do Compute [Lg Uz] and Vx(=) by 16 for ;
if Vx(=) Vx then
L Z - 2 U [T,,
+ U2 + y, where 0 0<7 < 1;
Compute Psclective by return Pselective
13
21

---

Published in Transactions on Machine Learning Research (09/2025)
E Evaluation of Robustness
In this experiment, we confirmed the robustness of the proposed method to two factors that may affect the Type error rate control. First, we evaluate the robustness to non-Gaussian noise. Second, we evaluate the robustness to estimated variance.
E.1 Robustness to Non-Gaussian Noise
In this experiment, we confirmed the proposed method can control the Type I error rate when the data is generated from a non-Gaussian distribution. As non-Gaussian noise, we considered the following five distribution families:
skewnorm: Skew normal distribution family.
exponorm: Exponentially modified normal distribution family.
gennormsteep: Generalized normal distribution family (where the shape parameter B is con- strained to be steeper than that of the normal distribution, i.e., 3 < 2).
gennormflat: Generalized normal distribution family (where the shape parameter B is constrained to be flatter than that of the normal distribution, ie.,, B > 2).
Students t-distribution family.
Note that all of these distribution families include the Gaussian distribution and were standardized in the experiment.
To conduct the experiment, we first obtained a distribution such that the 1-Wasserstein distance from \(O0, 1) was A for each distribution family, with A E {0.01, 0.05, 0.1, 0.15). Other settings were the same the default settings in the Type error rate evaluation in Section 6.2 The results shown in Figure ? demonstrating that our proposed method can effectively control the Type I error rate for non-Gaussien noise.
1.0
skewnorm
exponnorm
0.8
Type Error Rate
gennormsteep gennormflat
0.6
0.05
0.4
0.2
0.0
0.01
0.05
0.1
0.15
1-Wasserstein Distance
Figure 6: Type error rate for non- nan-aassiaan noise.
22

---

Published in Transactions on Machine Learning Research (09/2025)
E.2 Robustness to Estimated Variance
In this experiment, we confirmed that the proposed method can control the Type error rate when the variance is estimated as sample variance from the same data. We varied the number of nodes n E (32, 64, 128, 256) and evaluated the Type crror rate at three significance levels: a = 0.01, 0.05, 0. 10. Other settings were the same as the Type error rate evaluation in Section 6.2 The results are shown Figure 7 demonstrating that our proposed method can effectively control the Type I error rate.
0.200
0.05
0.01
Type Error Rate
0.150
0.10
0.125
0.100
0.075
0.050
0.025
0,000
64
128
256
Number of Nodes
Figure 7: Type error rate for estimated variance.
23

---

Published in Transactions on Machine Learning Research (09/2025)
F Sensitivity of the Threshold Parameters
In this experiment, we confirmed that the proposed method can control the Type I error rate when the threshold in [ and 7 in (2) are varied. We varied the threshold pair (7. over 0.3, 0.5, 0.7] x {0.2, 0.4, 0.6, 0.8} such that 72 < Tu- Other settings were the same as the Type error rate evaluation
Section 6.2 The results are shown in Figure S demonstrating that our proposed method can effectively control the Type I error rate the a 0.05 level for all combinations of 77 and Tu.
T 0.2
Tu 0.4
T
T,
0.10
T= 0.1
0.05
0.00
0.10
0.3
0.05
0.00
0.10
0.5
0.05
0.00
0,7
0.05
0.00
Figure 8: Type I error rate when varying the threshold parameters and Tu.
24

---

Published in Transactions on Machine Learning Research (09/2025)
G Evaluation with Various GNN Architectures and Saliency Map Methods
In this experiment, we confirmed that the proposed method can control the Type I error rate across various combinations of GNN architectures and saliency map methods, which satisfy the assumptions of piecewise linearity. We compared the following four methods:
This setting is the same in Section 6 where the GNN architecture is GCN and the saliency map method is CAM.
GCN+CAM:
GGN+GradCAM: The GNN architecture GCN and the saliency map method is Grad-CAM
We used the same 3-layer GCN as in Section t and applied Grad-CAM to the output of the second layer.
The GNN architecture GIN (Graph Isomorphism Network) and the saliency map method is Grad (Shrikumar et al., 2017). In this setting, we implemented GIN based on the standard formulation (Xu et al. 2019)) where v-th node features h. X,, at 1-th layer updated as follows in the GINLayer:
GrN+Grad:
h(+1) MLP + c)h, EuEN(o)
The MLP consisted of two layers with 64 hidden units and 64-dimensional output, and used ReLU as the activation function. The parameter was learned. After three GINLayers, the node features were aggregated via global add pooling to obtain graph-level representation, which was then passed through fully connected layer to compute the logits for two classes.
Gradlnuu: The GNN architecture is GIN and the saliency map method is GradIn- put (Shrikumar et al. 2017). The GIN architecture is the same in the GIN+Grad method.
All methods satisfied the assumptions of piecewise linearity. All saliency maps were normalized the range [0, 1] before applying thresholds to extract salient and non-salient subgraphs.
Other settings were the same the Type I error rate evaluation in Section 6.2 2
The results are shown
in Figure g demonstrating that our proposed method can effectively control the Type error rate at the a 0.05 level for all settings.
25

---

Published in Transactions on Machine Learning Research (09/2025)
GCN+CAM
GCN+CAM
GCN+Gra
GAM
0.8-
GIN+ Grad
0.8
GIN+Grad
GIN+ Gradinutt
Typp Error Rate
GIN+Gradinput
Signlficance (g=0.05)
Significance D.05)
1ype
0.4-
0.4
0.2-
0.2
5
10
15
20
32
64
128
256
Number of features
Number of nodes
Independence
1.0
GCN+CAM
GCN+CAM
GCN+GradCAM
GCN-GradCAM
0.8-
GIN+ Grad
0.8-
GIN+Grad
1yp Rate
GIN+ Gradinput
Type Error Rate
GIN+Grad nput
Significance (d-0.05)
Significance
0.4-
0.4
5
10
15
20
32
64
128
256
Number of features d
Number of nodes
(b) Correlation
Figure Type I error rate for various GNN architectures and saliency map methods.
26

---

Published in Transactions on Machine Learning Research (09/2025)
H Experiments on EEG Dataset
H.1 Detail of Dataset
The EEG dataset provided by Won et al. (0222) consists of high-rosolution brain activity recordings obtained from 55 participants performing the Rapid Serial Visual Presentation (RSVP) lask. In this dataset, each trial comprises a sequence of visual stimuli presented at rapid rate, with participants required to identify target stimuli among distractors. The EEG signals are labeled based on whether a stimulus was target (positive category) or non-target (negalive calegory). The event-related potential (ERP) component. of interest in this study is the P300 response, well-establiseed neural marker for target detection in RSVP paradigms.
The dataset includes signals collected from 32 electrodes positioned according to the international 10-20 system, sampled at 512 Hz. The original recordings spanned from -200 to 1000 ms relative to stimulus onset, capturing both pre-stimulus baseline and post-stimulus neural activity. Each participant's 's dataset consists of 40 positive and 560 negative samples.
The preprocessing and filtering steps adhered to standard EEG signal processing practices; for further details, refer to Won et al. (2022). However, specific modifications were made in this study to enhance data quality, To miligate the influence of eye movement artifacts, four sensors near the eyes were excluded from analysis, leaving 28 sensors for further processing, Only the post-stimulus interval (0 to 1,000 ms) was analyzed, as the primary interest lics in stimulus-cvoked activity rather than pro-stimulus baseline fluctuations. Each ,,000 ms segment was then downsampled from 512 to 50 Hz, reducing the time series to points while preserving the relevant frequency components associated with cognitive processing.
27

---

Published in Transactions on Machine Learning Research (09/2025)
H.2
Examples of Individual Results
Saliency map
Salient subgraph
Most salient time-series
Amplltudn (UV]
400
620
Time [ms]
selective_p=0.0000 naive_p=0.000
Saliency map
Salient subgraph
Most salient time-series
Amplitude (N))
Time [ms]
Delective_p=0.001 naive_p=0.000
Saliency map
Salient subgraph
Most salient time-series
Amplitude (W] i x
[ms]
Solective_p-0.032 Taive_p=0.00%
Saliency map
Salient subgraph
Most salient time-series
Ampiluude (MV]
200
400
630
100
Time [ms]
selective 00000 naive_p=0.000
Saliency map
Salient subgraph
Most salient time-series
Amplitudo lpv]
460 Time [ms]
selective 00000l0epp000,,,,, naive_ 2000e_p=0.000
Saliency map
Salient subgraph
Most salient time-series
Amplitune lnv]
selective -otittivve==.000,, naive -p=00000
Figure 10: Positive examples. See Figure for the interpretation of the visual elements. Below each example, we report the corresponding p-values, demonstrating that the proposed method correctly detects the positive samples.
28

---

Published in Transactions on Machine Learning Research (09/2025)
Saliency map
Salient subgraph
Most salient time-series
Ampllitud (μV]
Time
selective patiiiie___.28,,,..- naive seive_p=0.000
Saliency map
Salient subgraph
Most salient time-series
Amplitus (uV]
200
400
620
500
Time [ms]
selective_p=0.109 naive_p=0.00
Saliency map
Salient subgraph
Most salient time-series
Amplitude lMM]
400
600
Time [ms]
selective p00.il2,,pp0..,, naive_p=0.000
Saliency map
Salient subgraph
Most salient time-series
Ampiltude (UV]
Time [ms]
Delective_p=0.40 naive_p=0.o0m
Saliency map
Salient subgraph
Most salient time-series
Amplittdd (uV]
x
[ms]
selective p0tilleeep0.0.,,..-. naive_p- 00000000000000
Saliency map
Salient subgraph
Most salient time-series
Amplitude [MM]
700
400
620
sio
Time [ms]
0.1.44, naive_p=0.000
Figure 11: Negative examples. See Figure 4 for the interpretation of the visual clements. Below each example, report the p-values for both the proposed and naive methods. The selective p-values sufficiently large, indicating correct exclusion of spurious saliency, whereas the naive p-values are misleadingly small.
29

---

Published in Transactions on Machine Learning Research (09/2025)
H.3 Experiments Modified Datasets
In this experiment, we evaluated the proposed method using modified real datasets.
The primary objective of this study is to develop valid hypothesis testing framework under the assumption that the data follows the model presented in Section However, real-world data do not always adhere to these assumplions, making direct evaluation challenging. In Section we demonstrated several case studies illustrate our approach.
In this section, evaluate the Type error rate by modifying the real datasets used in Section G to better conform to the assumed model. For the experiment, we est imated the mean vector ftt from the positive class and the covariance matrix E from the negative class in the real dataset. To investigate the effect of covariance structures, we considered two different settings for Σ: (i) the sample covariance matrix, normalized so that its largest eigenvalue is one and then scaled by a factor y E R (denoted as full), and (ii) a diagonal covariance matrix set to 7 (denoted as eye). The scalar factor y was varied over {0.25, 0.5, 0.75, 1.0). Using these estimates, we generated 1,000 test samples following X NO Σ) for Type error rate evaluation and X NWt Σ) for power analysis.
The results are presented in Figure 12 The proposed method effectively controls the Type I error rate while achieving a detection rate above the significance level a.
1.0
1.0
proposed: eye
eye
proposed: full
full
0.8
0.8
Type EError Rate
naive: eye
a=0.05
I
naive: full
0.6
a=0.05
Power
0.6
0.4
0.4
T
I
0.0
0.0
0.75
0.75
(a) Type error rate
(b) Power
Figure 12: Results for modified real datasets
30


Reviews:
[{"review_id": "d29JzJQr5f", "reviewer": "Reviewer_jNsC", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength  \n1.\tThe paper addresses an under-explored problem, i.e., the robustness in GNN interpretability by explicitly modeling and correcting for selection bias through Selective Inference.  \n2.\tThe paper is well-written, i.e., the motivation and method are clear and easy to understand.  \n3.\tThe paper provides extensive empirical evidence, including synthetic and real EEG datasets, demonstrating that the proposed method uniquely avoids false positives in negative-class saliency and maintains higher statistical power.  \n\nWeaknesses  \n1.\tThe method fundamentally relies on the piecewise linearity of CAM and cannot be directly applied to attention-based architectures or black-box saliency methods like GNNExplainer or GraphMask. Why the proposed method can assess the robustness of general GNN explanations methods needs to be clarified.  \n2.\tThe choice of saliency thresholds seems to significantly influence the subgraph definition and test outcome, yet the paper does not examine how sensitive the method is to these hyperparameters.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper addresses the issue of assessing the reliability of GNN saliency maps, which are used to model the interpretability of GNNs. Specifically, the authors propose a principled statistical testing based on Selective Inference, which quantifies the statistical significance of saliency maps by computing p-values. The proposed method leverages the piecewise linearity of GNN saliency methods (e.g., CAM) and reduces the high-dimensional conditional inference problem to a one-dimensional search problem. Extensive experiments on both synthetic and real-world EEG datasets demonstrate that the proposed method outperforms naive and Bonferroni-corrected baselines by achieving better Type I error control and higher statistical power.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1.\tHow can the method be extended to handle soft attention weights or other non-linear saliency mechanisms?  \n2.\tHow sensitive are the selective p-values to the choice of thresholds? Would an adaptive thresholding strategy be possible?", "broader_impact_concerns": "The authors could discuss how their proposed method affects the reliability of GNN in decision-making, e.g., recommender system and healthcare (e.g., the EEG example in the paper).", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "BgwRrYPPzx", "reviewer": "Reviewer_uvL7", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:**\n1. Overall the idea of statistical testing of GNN explanations is useful and has not been considered very rigorously in the literature. So in that sense the paper is a good addition. \n\n**Weaknesses:**\n1. The hypothesis are defined based on input feature values for the nodes identified in salient and non-salient partitions of the graph. What happens if the input nodes come without features and are just one-hot encoded? Even if the nodes come with input features why should saliency be defined only in terms of input node features and not also the structure? For example, two nodes having the same feature values might be in different substructures of the graph. One of the substructures might be more important than the other.\n\n2. The connection to explainability/interpretability is missing. Once the statistical significance of salient subgraph is established how do we know that it is a reliable explanation in the sense that it is faithful to the model and the model actually used it to make the decision. In this regard I would suggest to the authors to relate their framework with existing explanation evaluation metrics.\n\n3. To the best of my understanding, the framework  is in itself not new but its application to GNNs is. But currently the framework is simply applied to GNNs without accounting for the role of graph structure that is unique to the graph data and models. For instance Lemma 1 and Lemma 2 do not take into account of the effect of the graph structure at all. \n\n4. It is also not clear how the threshold for obtaining the most salient subgraph are chosen. Imagine the case where all saliency values are very similar to each other. I think a very first test should be to check if the saliency values can be used to obtain a small salient subgraph for instance by checking the entropy of the the returned saliency distribution as proposed in https://ieeexplore.ieee.org/document/9866587 for evaluation sparsity of continuous explanations. A very high entropy would already mean that there is no real distinguishing information in the obtained salient masks . More details should be provided how the current thresholds are chosen.\n\n5. The presentation of the paper can be improved with a bit more details about the statistical testing framework as the general audience from Graph learning might not have background in statistical testing. Specifically Lemma 2 which is the core of this framework needs to be elaborated a bit more of what the conditional data space would mean for the given graph data.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes a statistical testing framework to evaluate the significance of saliency maps for explaining GNN decisions. The authors leverage the selective inference framework to overcome the issue of double dipping caused due to the use of the dataset for hypothesis generation and testing. The approach is limited to testing saliency maps from the CAM approach with a standard GNN architecture. Empirical evidence is provided to support the proposed approach.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please see the Weaknesses", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "ihyF1Evary", "reviewer": "Reviewer_DAiL", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This is a good paper and I thank the authors for their work. I see a lot of positive aspects in this work and have only 2 concerns.\n\n### Strengths:\n- A very well written paper which is very easy to follow. Important aspects of the work are well presented in the main section and supplementary material is deferred to the Appendix.\n- The contributions of the paper are very good. Statistical analysis of Explainable AI methods is well overdue since works like [1] emerged. Therein, the contributions of this work are very well positioned.\n- Evidence for all claims made in the paper are provided  (with an exception of the ablation mentioned in the Weaknesses section).\n- Strong related work section.\n- Figures and Results are clearly stated.\n- The theoretical results are clean and easy to follow (see my note).\n- The Appendix is well structured and organized. It contains a lot of good additional information like the Computation of the p-values and the additional empirical evaluations like the robustness tests.\n\n### Weaknesses:\n1. While the paper shows that their proposed statistical test can be applied to any model / saliency combinations which adheres to the assumptions mentioned in Section 5. This could have easily been validated and demonstrated by an ablation study in the empirical evaluation. Currently, only one kind of architecture is used; a traditional GCN. It would be worth showcasing how other architectures like Graph Attention Networks (GATs) [2] or Graph Isomorphism Networks (GINs) [3] influence the statistical test. The same holds true for the choice of saliency method. Currently only CAM is applied, which is already quite dated. Better representatives in my opinion would be Grad-CAM or even integrated gradients (IG) [4]. I acknowledge that the work tightly limits its scope by specifically mentioning this as its main limitation, which seems to be in line with the guidelines provided by TMLR. However, the paper could be of much higher impact if these simple checks would be presented, since the title of the work currently reads as \"Statistical Test for Saliency Maps of Graph Neural Networks via Selective Inference\" **and not** \"Statistical Test for _Class Activation Maps_ of Graph _Convolutional_ Neural Networks via Selective Inference\".\n2. The real-world experiment in section 6.3 falls a bit short without knowledge if the detected salient sets **actually are** salient sets, which are important. The plot with the most-salient time series might suggest that, but this is only a 1d view into the high-d time series. More evidence, that the test actually finds salient sets could be provided by maybe plotting not only the top-1 time series but maybe all dimensions in some meaningful manner or digging deeper into the application and assessing the results with domain experts or comparing the identified sets with other research from the medical domain.\n\n### Note\nI am not a statistician by trait and do not feel comfortable in judging the final correctness of all the theoretical results, since I might have overlooked an assumption which would be obvious to someone with more of a background in statistics.\n\n### References\n- [1] https://arxiv.org/abs/1810.03292\n- [2] https://arxiv.org/abs/1710.10903\n- [3] https://arxiv.org/abs/1810.00826\n- [4] https://arxiv.org/abs/1703.01365", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The work presents a novel method to conduct statistical tests on saliency maps retrieved for a graph neural network. The goal of the test is to identify _salient_ sets of features compared _non-salient_ sets of features with statistical guarantees (limiting the Type-1 error rate). The statistical test proposed in this work is based on the framework of selective inference. The proposed test is compared and evaluated on synthetic experiments and applied on a real-world example.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "### Ablation Study with different GNN architectures\nConduct an ablation study as described in the weakness section (item 1.) similar to the experiment in Section 6.2 but with different GNN architectures and different saliency map methods. I am unsure about which of the mentioned methods (GAT, GIN, Grad-CAM, IG) would work for your test. If a method does not work for your test, it would be very important to describe why it does not. The results could be presented similarly as Figure 3.\n\n### Better Plotting of Salient Time Series\nI don't know how exactly this can be achieved, but it would be good, if the \"evidence\" in Figure 3 would be reworked. It is not clear to me if the salient sets provided in Section 6.3 are actually meaningful or not from an application perspective. Some further investigation and presentation in the form of a case study would be very appreciated. For a bit more context please see the weaknesses section item 2.\n\n\n### Typos:\n- Typo I noticed in your caption of Figure 3: I think it should be \"The left and middle columns ...\" instead of \"The right and middle columns ...\".\n- Style: I do not like the \"§\" Symbol for cross-references inside the manuscript and would prefer writing \"Section\" or \"Appendix\".", "broader_impact_concerns": "No concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)