$\theta\mapsto\Theta(\theta)\overset{\rm def}{=}\sum_{n\geq
2}P_{n,m}\sin(nm\theta)\in L^{2}(\mathbb{T})\subset L^{1}(\mathbb{T}).$

Accordingly, we deduce that

$\sum_{n\geq
2}P_{n,m}(\Omega_{m}^{\pm})\begin{pmatrix}g_{nm,1}\vspace{0.1cm}\\\
g_{nm,2}\end{pmatrix}\sin(nm\theta)=\Theta*\begin{pmatrix}g_{1}\vspace{0.1cm}\\\
g_{2}\end{pmatrix}(\theta)\in C^{\alpha}(\mathbb{T})\times
C^{\alpha}(\mathbb{T}),$

where the convolution above is written in a vectorial format. This completes
the proof of (4.36).

Finally, we are left with the proof of the transversality condition. To that
end, we first write, by differentiating (4.31) with respect to $\Omega$, that

$\partial_{\Omega}d_{r}\mathcal{F}(\Omega,0)\begin{pmatrix}{\rho}_{1}\vspace{0.1cm}\\\
{\rho}_{2}\end{pmatrix}=-\sum_{n\geq
1}n\begin{pmatrix}c_{n,1}\vspace{0.1cm}\\\ c_{n,2}\end{pmatrix}\sin(n\theta),$

for any $\Omega\in\mathbb{R}$. Therefore, we obtain that

$\partial_{\Omega}d_{r}\mathcal{F}(\Omega_{m}^{\pm},0)\begin{pmatrix}\Omega_{m}^{\pm}+\frac{B_{m}}{\delta+1}\vspace{3mm}\\\
-\frac{\delta}{\delta+1}\gamma_{m}\end{pmatrix}\cos(m\theta)=-m\begin{pmatrix}\Omega_{m}^{\pm}+\frac{B_{m}}{\delta+1}\vspace{3mm}\\\
-\frac{\delta}{\delta+1}\gamma_{m}\end{pmatrix}\sin(m\theta).$

Hence, in view of (4.34), it follows that

$\partial_{\Omega}d_{r}\mathcal{F}(\Omega_{m}^{\pm},0)\begin{pmatrix}\Omega_{m}^{\pm}+\frac{B_{m}}{\delta+1}\vspace{3mm}\\\
-\frac{\delta}{\delta+1}\gamma_{m}\end{pmatrix}\cos(m\theta)\in{\rm
R}\big{(}d_{r}\mathcal{F}(\Omega_{m}^{\pm},0)\big{)}$

if and only if there exist two real numbers $c_{m,1}$ and $c_{m,2}$ such that

$M_{m}(\Omega_{m}^{\pm})\begin{pmatrix}c_{m,1}\vspace{0.1cm}\\\
c_{m,2}\end{pmatrix}=\begin{pmatrix}\Omega_{m}^{\pm}+\frac{B_{m}}{\delta+1}\vspace{3mm}\\\
-\frac{\delta}{\delta+1}\gamma_{m}\end{pmatrix}.$

Since $\Omega_{m}^{\pm}+\frac{B_{m}}{\delta+1}\neq 0$, the latter identity is
equivalent to finding two real numbers, still denoted by $c_{m,1}$ and
$c_{m,2}$ for simplicity, such that

(4.38) $M_{m}(\Omega_{m}^{\pm})\begin{pmatrix}c_{m,1}\vspace{0.1cm}\\\
c_{m,2}\end{pmatrix}=\begin{pmatrix}1\\\ \sigma_{m}\end{pmatrix},$

where we set

$\sigma_{m}\overset{\rm
def}{=}\frac{-\frac{\delta}{\delta+1}\gamma_{m}}{\Omega_{m}^{\pm}+\frac{B_{m}}{\delta+1}}$

and we emphasize that

$\begin{pmatrix}1\\\
\sigma_{m}\end{pmatrix}\in\text{Ker}\big{(}M_{m}(\Omega_{m}^{\pm})\big{)}.$

The validity of the identity (4.38) is violated by means of basic linear
algebra arguments, for $M_{m}(\Omega_{m}^{\pm})$ is non-invertible and the
vector $(1,\sigma_{m})$ is a non trivial zero of that matrix, with
$\sigma_{m}\neq 0$. More precisely, this is a consequence of the following
simple lemma

######  Lemma 4.9.

Let $M$ be a real two-dimensional matrix with a non trivial kernel. Assume
further that there is $s\in\mathbb{R}\setminus\\{0\\}$ such that

$\begin{pmatrix}1\\\ s\end{pmatrix}\in\text{Ker}(M)\cap\text{R}(M).$

Then, $M$ is trace-free, i.e., it holds that

$\text{Tr}(M)=0.$

Let us admit Lemma 4.9 for a moment and first continue the proof of the
transversality condition. We get back to the proof of that lemma thereafter.

According to Lemma 4.9, in order to prove the non validity of (4.38) for any
real numbers $c_{m,1},c_{m,2}$, it is enough for us to check that
$\text{Tr}(M_{m}(\Omega_{m}^{\pm}))\neq 0$. To that end, we compute that

$\text{Tr}(M_{m}(\Omega_{m}^{\pm}))=2\Omega_{m}^{\pm}+\frac{A_{m}+B_{m}}{1+\delta}.$

Hence, in view of the definition of $\Omega_{m}^{\pm}$, given in (4.26), we
find that

$\text{Tr}(M_{m}(\Omega_{m}^{\pm}))=\pm(\Omega_{m}^{+}-\Omega_{m}^{-})\neq 0,$

thereby deducing that (4.38) cannot hold true for any real numbers $c_{m,1}$
and $c_{m,2}$. This justifies the transversality condition.

Let us now prove Lemma 4.9. Generally speaking, a given two-dimensional matrix
$M$ is non-invertible if and only if

$M=\begin{pmatrix}a&\eta a\vspace{0.1cm}\\\ b&\eta
b\end{pmatrix},\quad\text{for some}\quad a,b,\eta\in\mathbb{R}.$

Note that, without loss of generality, we can assume that $a$ and $b$ are both
not trivial, otherwise we emphasize that there will be noting left to prove.
Therefore, if $(1,s)$ is in the kernel of $M$ and satisfies

$M\begin{pmatrix}c_{1}\vspace{0.1cm}\\\
c_{2}\end{pmatrix}=\begin{pmatrix}1\vspace{0.1cm}\\\ s\end{pmatrix},$

for some $s\in\mathbb{R}^{*}$ and some two real numbers $c_{1}$ and $c_{2}$,
then one can easily check that $M$ should have the format

$M=\begin{pmatrix}a&-\frac{a^{2}}{b}\vspace{0.1cm}\\\ b&-a\end{pmatrix}.$

In particular, one deduces from all of this that $Tr(M)=0.$ This proves Lemma
4.9 and concludes the proof of the proposition. ∎

#### Proof of Theorem 4.1

The proof of Theorem 2.1 is now achieved as direct application of
Crandall–Rabinowitz’s Theorem 2.6, whose hypothesis are fully fulfilled due to
Proposition 4.8, above.

##  5\. Endnote

In this paper, it is shown that the multy-layer quasi–geostrophic system
(QS2L) admits a unique global weak—Lagrangian—solution as soon as the initial
vorticities are Lebesgue-integrable and bounded. In light of that, any couple
of initial vortex-patches is transported by the flow of the system and the
vortex structure remains unchanged as time goes forward. Moreover, it is also
shown here that there are time-periodic patches, close to stationary states
(discs), characterized by their rotational movement around their centers of
mass with the same angular velocity.

Although the first result—existence of global weak solutions of (QS2L)—is
shown to hold in the full range of parameters $\lambda>0$ and $\delta>0$, the
elements of proof of the second result—existence of rotating solutions—does
not cover the whole previous range of parameters. Specifically, technically
speaking, it turns out that the spectral analysis of the contour dynamics can
be affected by the choice of these parameters and this is shown to also depend
on the choice of the radii $b_{1}$ and $b_{2}$ of the initial discs. Note that
this phenomenon is not observable in the Euler equations by virtue of their
invariance by dilatation; it is, however, a property that comes from the
contribution of the kernel associated with the shallow-water equations.

Our spectral analysis of the linearized operator around a steady state (two
discs) shows that its kernel has a bi-dimensional structure. Moreover, the
sequence of the associated eigenvalues
$(\Omega_{m}^{\pm})_{m\in\mathbb{N}^{*}}$ for which this operator is not
invertible is, in some sense, a combination of a semblable sequence of
eigenvalues from Euler and shallow-water equations. This is well observed in
the case $\delta=1$, see (4.29). Although we are able to show that the
linearized operator is not invertible at any value of angular velocities
$\Omega_{m}^{\pm}$, for any given symmetry $m\in\mathbb{N}^{*}$, it turns out
that there are cases (depending on the choice of parameters $\lambda$,
$\delta$, $b_{1}$ and $b_{2}$) where spectral collisions surely occur and the
Crandall-Rabinowitz theorem does not directly apply to construct time-periodic
solutions in such situations. Here, it is a remarkable observation that the
non-invertibility of the linearized operator at $\Omega_{m}^{\pm}$, for any
given symmetry $m\in\mathbb{N}^{*}$, stems from the coupling of Euler and
shallow-water kernels. This description for small number of symmetries is
satisfactory when compared to the doubly connected case of shallow-water
equations [47], which, as previously emphasized, shares several aspects of
similarity in terms of the two-dimensional structure of the V-states.

In conclusion, the present work opens the gate for more interesting questions
to be discussed about (QS2L), such as properties of the branches of
bifurcation, description of stationary solutions, existence of doubly
connected V-states and quasi-time-periodic solutions.

## Acknowledgement

The authors would like to thank Taoufik Hmidi for introducing the multy-layer
quasi–geostrophic system (QS2L) as well as for several helpful discussions and
remarks.

The work of Zineb Hassainia has been supported by Tamkeen under the NYU Abu
Dhabi Research Institute grant of the center SITE.

## References

  * [1] Explosive instability of geostrophic vortices. part 1: baroclinic instability.  Theoretical and Computational Fluid Dynamics, 24(1):125–130, 2010\.
  * [2] Milton Abramowitz and Irene A. Stegun.  Handbook of mathematical functions with formulas, graphs, and mathematical tables.  National Bureau of Standards Applied Mathematics Series, No. 55. U. S. Government Printing Office, Washington, D.C., 1964.
  * [3] Milton Abramowitz and Irene A Stegun.  Handbook of mathematical functions with formulas, graphs, and mathematical tables.  US Government printing office, 1968.
  * [4] Dallas Albritton, Elia Brué, Maria Colombo, Camillo De Lellis, Vikram Giri, Maximilian Janisch, and Hyunju Kwon.  Instability and nonuniqueness for the $2d$ euler equations in vorticity form, after M. Vishik.  https://arxiv.org/abs/2112.04943, 2021.
  * [5] Hajer Bahouri, Jean-Yves Chemin, and Raphaël Danchin.  Fourier analysis and nonlinear partial differential equations, volume 343.  Springer Science & Business Media, 2011.
  * [6] Árpád Baricz.  On a product of modified bessel functions.  Proceedings of the American Mathematical Society, 137(1):189–193, 2009.
  * [7] Massimiliano Berti, Zineb Hassainia, and Nader Masmoudi.  Invent. Math., (3):1279–1391.
  * [8] Elia Brué and Maria Colombo.  Nonuniqueness of solutions to the euler equations with vorticity in a Lorentz space.  https://arxiv.org/abs/2108.09469, 2021.
  * [9] Jacob Burbea.  Motions of vortex patches.  Letters in Mathematical Physics, 6(1):1–16, 1982.
  * [10] Xavier Carton, Thomas Meunier, Glenn R. Flierl, Xavier Perrot, and Mikhail A. Sokolovskiy.  Explosive instability of geostrophic vortices. part 2: parametric instability.  Theoretical and Computational Fluid Dynamics, 24(1):131–135, 2010\.
  * [11] Xavier J. Carton and Stéphanie M. Corréard.  Baroclinic tripolar geostrophic vortices.  pages 181–190, 1999.
  * [12] Angel Castro, Diego Córdoba, and Javier Gómez-Serrano.  Ann. PDE, (1):Art. 1, 34.
  * [13] Angel Castro, Diego Córdoba, and Javier Gómez-Serrano.  Uniformly rotating analytic global patch solutions for active scalars.  Annals of PDE, 2(1):Art. 1, 34, 2016.
  * [14] Jean-Yves Chemin.  Fluides parfaits incompressibles.  Astérisque, (230):177, 1995.
  * [15] Michael G. Crandall and Paul H. Rabinowitz.  Bifurcation from simple eigenvalues.  Journal of Functional Analysis, 8:321–340, 1971.
  * [16] Gianluca Crippa and Stefani Giorgio.  An elementary proof of existence and uniqueness for the euler flow in localized yudovich spaces.  arXiv:2110.15648v2, 2021.
  * [17] Francisco de la Hoz, Taoufik Hmidi, Joan Mateu, and Joan Verdera.  SIAM Journal on Mathematical Analysis, (3):1892–1928.
  * [18] Gary S. Deem and Norman J. Zabusky.  Vortex waves: Stationary “${V}$ states,” interactions, recurrence, and breaking.  Physical Review Letters, 40:859–862, Mar 1978.
  * [19] Ronald. J. DiPerna and Pierre-Lions. Lions.  Ordinary differential equations, transport theory and Sobolev spaces.  Invent. Math., 98(3):511–547, 1989.
  * [20] David Gerard Dritschel, Taoufik Hmidi, and Coralie Renault.  Imperfect bifurcation for the quasi-geostrophic shallow-water equations.  Arch. Ration. Mech. Anal., 231(3):1853–1915, 2019.
  * [21] Lawrence C. Evans.  Partial differential equations, volume 19 of Graduate Studies in Mathematics.  American Mathematical Society, Providence, RI, 1998.
  * [22] Glenn R. Flierl.  On the instability of geostrophic vortices.  Journal of Fluid Mechanics, 197:349–388, 1988.
  * [23] Claudia García.  Kármán vortex street in incompressible fluid models.  Nonlinearity, 33(4):1625–1676, 2020.
  * [24] Claudia García.  Vortex patches choreography for active scalar equations.  Journal of Nonlinear Science, 31(5):Paper No. 75, 31, 2021.
  * [25] Claudia García, Zineb Hassinia, and Emeric Roulley.  Dynamics of vortex cap solutions on the rotating unit sphere.  https://arxiv.org/abs/2306.00154, 2023.
  * [26] Javier Gómez Serrano, Alexandru D. Ionescu, and Jaemin Park.  Quasiperiodic solutions of the generalized SQG equation.  arXiv preprint arXiv:2303.03992., 2023.
  * [27] Javier Gómez-Serrano, Jaemin Park, and Jia Shi.  Existence of non-trivial non-concentrated compactly supported stationary solutions of the 2D Euler equation with finite energy.  arXiv preprint arXiv:2112.03821, 2021.
  * [28] Javier Gómez-Serrano, Jaemin Park, Jia Shi, and Yao Yao.  Symmetry in stationary and uniformly rotating solutions of active scalar equations.  Duke Mathematical Journal, 170(13):2957–3038, 2021.
  * [29] Zineb Hassainia and Taoufik Hmidi.  Steady asymmetric vortex pairs for euler equations.  Discrete and Continuous Dynamical Systems. Series A, 41(4):1939–1969, 2021.
  * [30] Zineb Hassainia, Taoufik Hmidi, and Nader Masmoudi.  Kam theory for active scalar equations.  arXiv preprint arXiv:2110.08615, Memoirs of the AMS (in press), 2021\.
  * [31] Zineb Hassainia, Taoufik Hmidi, and Emeric Roulley.  Invariant kam tori around annular vortex patches for 2D Euler equations.  arXiv preprint arXiv:2302.01311, 2023.
  * [32] Zineb Hassainia, Nader Masmoudi, and Miles H. Wheeler.  Global bifurcation of rotating vortex patches.  Communications on Pure and Applied Mathematics, 73(9):1933–1980, 2020.
  * [33] Zineb Hassainia and Emeric Roulley.  Boundary effects on the emergence of quasi-periodic solutions for euler equations.  arXiv preprint arXiv:2202.10053, 2022.
  * [34] Zineb Hassainia and Miles H. Wheeler.  Multipole vortex patch equilibria for active scalar equations.  SIAM Journal on Mathematical Analysis, 54(6):6054–6095, 2022.
  * [35] Taoufik Hmidi.  On the trivial solutions for the rotating patch model.  Journal of Evolution Equations, 15(4):801–816, 2015.
  * [36] Taoufik Hmidi and Joan Mateu.  Bifurcation of rotating patches from Kirchhoff vortices.  Discrete Contin. Dyn. Syst., (10):5401–5422.
  * [37] Taoufik Hmidi and Joan Mateu.  Existence of corotating and counter-rotating vortex pairs for active scalar equations.  Communications in Mathematical Physics, 350(2):699–747, 2017.
  * [38] Taoufik Hmidi, Joan Mateu, and Joan Verdera.  Boundary regularity of rotating vortex patches.  Archive for Rational Mechanics and Analysis, 209(1):171–208, 2013\.
  * [39] Taoufik Hmidi and Emeric Roulley.  Time quasi-periodic vortex patches for quasi-geostrophic shallow-water equations.  arXiv preprint arXiv:2110.13751, 2021.
  * [40] Taoufik Hmidi, Liutang Xue, and Zhilong Xue.  Emergence of time periodic solutions for the generalized surface quasi-geostrophic equation in the disc.  https://arxiv.org/abs/2210.08760v1, 2023.
  * [41] V. I. Judovič.  Non-stationary flows of an ideal incompressible fluid.  Ž. Vyčisl. Mat i Mat. Fiz., 3:1032–1066, 1963.
  * [42] Nikolai Nikolaevich Lebedev, Richard A Silverman, and Livhtenberg.  Special Functions and their applications.  American Institute of Physics, 1965.
  * [43] Francesco Mainardi.  Fractional calculus and waves in linear viscoelasticity.  Imperial College Press, London, 2010.  An introduction to mathematical models.
  * [44] L. M. Polvani.  Two-layer geostrophic vortex dynamics. part 2. alignment and two-layer v-states.  Journal of Fluid Mechanics, 225:241–270, 1991.
  * [45] L. M. Polvani, N. J. Zabusky, and G. R. Flierl.  Two-layer geostrophic vortex dynamics. I. Upper-layer $V$-states and merger.  J. Fluid Mech., 205:215–242, 1989.
  * [46] Emeric Roulley.  Periodic and quasi-periodic Euler-$\alpha$ flows close to Rankine vortices.  arXiv preprint arXiv:2208.13109, 2022.
  * [47] Emeric Roulley.  Vortex rigid motion in quasi-geostrophic shallow-water equations.  Asymptotic Analysis, pages 1–50, 2022.
  * [48] Javier Segura.  Bounds for ratios of modified bessel functions and associated turán-type inequalities.  Journal of Mathematical Analysis and Applications, 374(2), 2011\.
  * [49] Misha Vishik.  Incompressible flows of an ideal fluid with vorticity in borderline spaces of besov type.  In Annales scientifiques de l’Ecole normale supérieure, volume 32, pages 769–812, 1999.
  * [50] G. N. Watson.  A treatise on the theory of Bessel functions.  Cambridge Mathematical Library. Cambridge University Press, Cambridge, 1995.  Reprint of the second (1944) edition.
  * [51] V. I. Yudovich.  Uniqueness theorem for the basic nonstationary problem in the dynamics of an ideal incompressible fluid.  Math. Res. Lett, 2:27–38, 1995.


§ INTRODUCTION

Graph Neural Networks (GNNs) have become a cornerstone in modern machine learning, excelling in diverse domains such as social network analysis <cit.>, recommender systems <cit.> and bioinformatics <cit.>. However, the complexity of GNNs contributes to one of their principal shortcoming: a lack of human-interpretable predictions.
This opacity hinders their potential for practical, real-world impact, as practitioners often require interpretable models to inform decision-making, ensure trustworthiness, and comply with regulations <cit.>.
Current interpretability methods for GNN predictors aim to identify the most predictive subgraph from an original graph <cit.>.
In essence, interpretability in this context is closely tied to graph sparsity, implying the use of a minimal set of nodes and edges from the graph for prediction, rather than the entire graph $\Gcal$.

pipeline. Illustration of the pipeline of  using the synthetic   designed for binary graph classification. On the left, we present two examples of original graphs, denoted as $\Gcal$, corresponding to the positive class (top, cycle motif) and negative class (bottom, house motif). The policy $\phi$ of  takes $\Gcal$ and sparsifies it, resulting in the predictive subgraph $\Gcal_s$, which retains only the relevant information for the task, i.e., the motifs. Finally, the graph classifier $\theta$ takes $\Gcal_s$ as input and produces the prediction $y \in \{0, 1\}$.

This viewpoint of interpretability is exemplified in <ref> with the synthetic dataset <cit.>.
In this dataset, a binary classification task can be solved using only specific motifs of the graphs (the house or the cycle motifs, i.e., yellow nodes), while the original graphs contain additional irrelevant information for the task at hand, i.e., purple nodes.
A sparser graph reduces the volume of information used for making predictions, rendering it easier for humans to understand the GNN predictions. It is crucial to note that interpretability is achieved through sparsity only when the subgraph completely excludes information from the omitted nodes and edges since only then the subgraph, and thus, the explanation is faithful to the model prediction.
This situation does not arise, for example, if message passing  <cit.> is applied to obtain the node embeddings before finding the subgraph.

While most of explainability methods for GNNs are post-hoc, some existing approaches attempt to identify the predictive subgraph during training <cit.>.
These methods, however, exhibit two primary limitations:
i) they often still rely on the entire graph for predictions <cit.>, resulting in a lack of faithfulness to the model prediction (as described above), and/or
ii) they impose strong assumptions concerning the structure of the predictive subgraph, such as a pre-defined size.
In practical scenarios, relaxing assumptions on the subgraph structure is desirable.
For instance, in community detection within social networks <cit.>, it is crucial to only remove edges connecting users across distinct communities but the number of inter-community connections varies significantly and is unknown a priori.
Another relevant example is the prediction of mutagenic effects in compounds, where <cit.> observed that diverse “motifs” of chemical elements are predictive. We refer the reader to <ref> for a concrete example on the  dataset.

In this work, we introduce , a novel algorithm for training GNNs that addresses the two fundamental challenges simultaneously:
i) finding the informative subgraph $\Gcal_s$ by removing edges and/or nodes, without imposing assumptions on the subgraph's structure, and
ii) optimizing the performance of the graph classification task solely using the selected subgraph $\Gcal_s$, thereby enhancing the interpretability of the classifier.
To this end, we use a bi-level optimization approach.
The optimization for performance adheres to the conventional supervised problem paradigm.
We then apply reinforcement learning to identify the predictive subgraph, using a policy that allows edge and/or node removal modes.
Our carefully designed reward function allows us to introduce inductive biases toward either sparse or high-performing solutions and uses conformal predictions <cit.> to account for classifier uncertainty at each training epoch.

In summary, our work presents the following key contributions:
(i) A novel framework, , which enables graph-level classification using only predictive subgraphs as input,  leading to more interpretable solutions.
(ii) The flexibility to choose between achieving sparsity through node or edge removal, which removes assumptions on the structure of the predictive subgraph and broadens the range of application scenarios.
(iii) The design of a versatile reward function that takes into account the uncertainty of the classifier and allows to introduce inductive biases towards sparser or more high-performing solutions.
(iv) A comprehensive comparison across nine graph classification datasets, showing that  makes predictions using significantly sparser graphs while keeping competitive performance.

§ PRELIMINARIES

This section outlines necessary background information on the key building blocks of : reinforcement learning, message-passing graph neural networks, and conformal predictions. We begin by introducing the notation used throughout this work.

A graph is denoted as $\Gcal = (\Vcal, \Ecal)$ where $\Vcal \in \{1, \dots, n\} = [n]$ is the set of $n$ nodes and $\Ecal \subseteq \Vcal \times \Vcal$ is the set of edges.
The size of a set is represented as $\size{\Vcal}$.
A subgraph of $\Gcal$ is denoted as $\Gcal[s] = (\Vcal[s], \Ecal[s]) \subseteq \Gcal$ comprising subsets of nodes $\Vcal[s] \subseteq \Vcal$ and edges $\Ecal[s] \subset \Ecal$.
A labeled dataset is represented as $\Dcal = \{\Gcal_i, \yb_i \}_i$ where $\yb_i$ denotes the target of $\Gcal_i$. Here, without loss of generality, we focus on $K$ classes graph classification, hence $\yb_i \in \{1, \dots, K\} = [K]$.

§.§ Reinforcement learning

Reinforcement Learning (RL) is a learning paradigm in which an agent learns to optimize decisions by interacting with an environment <cit.>.
The objective is to find a policy $\pi$ that maximizes the expected cumulative reward.
An RL problem is typically modeled as a Markov Decision Process (MDP), defined by a tuple $(\mathcal{S}, \mathcal{A}, \mathcal{P}, \reward, \gamma)$, where $\mathcal{S}$ and $\mathcal{A}$ denote the state and action spaces, $\mathcal{P}$ the transition probability, $\reward$ the reward function, and $\gamma$ the discount factor.

Policy Gradient Methods
Policy gradient methods directly optimize the policy using gradient ascent on the expected cumulative reward <cit.>.
Proximal Policy Optimization (PPO) <cit.> is a policy gradient method that introduces an objective function fostering exploration while mitigating drastic policy updates. PPO aims to solve the optimization problem:

\begin{equation}
L^{CLIP}(\phi) = \mathbb{E}_{t}\left[\min\left(r_t(\phi)\hat{A}_t, clip(r_t(\phi), 1-\epsilon, 1+\epsilon)\hat{A}_t\right)\right]
\label{eq:ppo}
\end{equation}

where $r_t(\phi) = \frac{\pi_{\phi}(a_t|s_t)}{\pi_{\phi_{old}}(a_t|s_t)}$ is the probability ratio, $\hat{A}_t$ an estimator of the advantage function at time $t$, and $\epsilon$ a hyperparameter controlling the deviation from the old policy.

§.§ Graph neural networks

Message passing Graph Neural Networks (GNNs) are designed for graph-structured data processing. Each node $v \in \Vcal$ has a feature vector $\hb$, and the GNN transforms these features using neighborhood information.
Formally, a GNN performs $L$ update rounds, updating each node's feature vector $\hb_i^{(l)}$ at step $l \geq 1$:

\begin{equation}
\hb_i^{(l)} = \frm_{\theta_u} \left( \bigoplus_{j \in \Ncal_i } \mrm_{\theta_m} ( \hb_i^{(l-1)}, \hb_j^{(l-1)}) \right).
\end{equation}

Here, $ \frm_{\theta_u}$ and $\mrm_{\theta_m}$ are differentiable, parameterized functions, $\Ncal_i$ represents node $i$'s neighbors, and $\bigoplus$ denotes permutation invariant operations, i.e., sum, mean, or max. After $L$ steps, we obtain the final node representations ${\hb_i^{(L)}} \forall i \in \Vcal$. These representations are used for tasks like graph-level prediction, employing a permutation-invariant readout function $\hat{\yb} = \grm\left(\left\{\hb_i^{(L)}: i \in \Vcal\right\}\right)$ that ensures the output is node order independent.

§.§ Conformal Prediction

Conformal prediction <cit.> is a framework that rigorously quantifies uncertainty in machine learning predictions.
Given a labeled dataset $\{x_i, y_i\}_{i=1}^N$, a heuristic measure of uncertainty of our predictor (e.g., softmax values from a classifier $\frm_\theta$), and a scoring function $s(x, y) \in \mathbb{R}$ that reflects prediction uncertainty, conformal prediction generates a prediction set for a new input $x_{\text{test}}$ as follows:

\begin{equation}
\mathcal{C}\left(x_{\text{test}} \right)=\left\{y: s\left(x_{\text{test}}, y\right) \leq \hat{q}\right\} \subseteq [K].
\label{eq:prediction_set}
\end{equation}

Here, $\hat{q}$ represents the $\frac{\lceil(n+1)(1-\alpha)\rceil}{n}$ quantile of the calibration scores $\{s_i\}_n$, where $\alpha$ is a predefined error rate.
In the context of classification tasks, one commonly used conformal procedure is Adaptive Prediction Sets (APS) <cit.>, which defines the scoring function as:

\begin{equation}
s(x, y)=\sum_{j=1}^k \frm_\theta(x)_{\pi_j(x)} \text {, where } y=\pi_k(x)
\label{eq:aps_score}
\end{equation}

Here, $\pi(x)$ represents the permutation of $[K]$ that arranges the softmax values $\frm_\theta(x)$ from most likely to least likely.

§ RELATED WORK

GNNs extend deep learning models to incorporate graph-structured data <cit.>. Numerous architecture proposals have emerged, tailored for node, link, and graph prediction tasks <cit.>.
However, these approaches rely on the complete graph data and often disregard interpretability, which is the focus of our work.
More recently, some works aim for sparsification <cit.>.
However, these methods typically make strong assumptions on the predictive subgraph. Moreover, they often focus on tasks other than graph prediction.

Here, we explore relevant sparsification techniques that specifically target supervised problems, which are the main focus of our paper.
We categorize these works into two categories: those employing soft information removal, where the predictive subgraph retains information from the complete graph, and thus may not be faithful to the model predictions; and those adopting hard information removal, which closely aligns with our approach.

Soft removal of information
Several architectures <cit.> assign varying importance to network edges, simulating soft edge removal whilst maintaining information flow across nodes.
<cit.> hierarchically removes parts of the original graph, distilling the graph's representation into a single vector used for prediction.
<cit.>, uses a GNN to update node features and subsequently selects the top $k$ most relevant nodes based on their features. It is worth noting that even though part of the network is dropped, the remaining subgraph contains information from the entire network. In contrast, in our framework, the graph predictor does not have access to the dropped information.

Hard removal of information
<cit.> selects the top $k$ nodes based solely on their information. However, the number of nodes is fixed and cannot dynamically change for different graphs.
<cit.> takes a different approach by identifying discriminative subgraphs. It introduces a reinforcement pooling module trained with Q-learning <cit.> to adaptively select a pooling ratio when recombining subgraphs for classification.
SUGAR also imposes a predefined size for the subgraphs.
In contrast,  does not make any assumptions about the structure of the subgraph, uses policy gradient methods to capture uncertainty in the sparsity process, and allows for different modes of removal.

Finally, there is extensive literature that aims to understand which subgraph of the input graph is most relevant for making predictions in GNNs <cit.>.
However, it is important to note that these methods primarily focus on explaining a GNN predictor trained using the original graphs. In contrast, our objective is to train a GNN that inherently utilizes a minimal portion of the original graph.
While these methods may complement our approach by providing further insights of the predictions, they operate in a post-hoc manner.

§ : CONFORMAL-BASED REINFORCEMENT LEARNING FOR GRAPH SPARSIFICATION

In this section, we present , a novel training procedure for GNNs leveraging reinforcement learning with conformal-based rewards to achieve graph sparsification.
Given a labeled dataset $\Dcal$, the main goal of  is to identify a compact predictive subgraph $\Gcal[s] \subseteq \Gcal$ that maintains high performance for a graph classification task.
Next, we provide a detailed description of the different parts comprising .

§.§ Optimizing for sparsity and performance

Firstly, we aim to learn a function $\policy_\phi: \Gcal \mapsto \Gcal[s]$ with parameters $\phi$ responsible for identifying the predictive subgraph. This function corresponds to the policy of the reinforcement learning component of .
Secondly, we want to train a graph classifier $\frm_\theta: \Gcal[s] \rightarrow \hat{\yb}$ with parameters $\theta$ that takes the identified predictive subgraph as input and generates predictions.
The pipeline of our approach is illustrated with the synthetic  dataset in <ref>.
To tackle this challenge we introduce a bi-level iterative optimization approach:

\begin{align}
\phi^{*} &= \myargmin{\phi}{\Lcals}{\theta^{\star}(\phi), \phi, \Dcal[val] }  \label{eq:outer} \\
& \text { s.t. } \theta^\star(\phi) = \myargmin{\theta}{\Lcalp}{\theta, \phi, \Dcal[tr] }  \label{eq:inner}
\end{align}

The nested structure of the problem implies that achieving an optimal predictive subgraph requires a high-performing graph classifier.
We employ gradient descent for both optimizations, with a larger learning rate for the inner optimization  <cit.>.
Also, notice that we use the training $\Dcal[tr]$ and validation $\Dcal[val]$ sets to solve the inner and outer procedures respectively, which avoids overfitting.
<ref> summarizes the training procedure.

Performance optimization
This objective corresponds to <ref> which represents a standard graph-supervised problem. Here, the objective is to minimize a loss function $\Lcalp$, e.g., the cross-entropy loss. Thus the goal is to learn a function $\frm_\theta: \Gcal[s] \rightarrow \hat{\yb}$ with parameters $\theta$ that minimizes the prediction loss.

Training of .

[1]
Input: Training $\Dcal[tr]$ and validation $\Dcal[val]$ sets; Initial graph classifier parameters $\theta$ and policy parameters $\phi$; Empty buffer $\Bcal$; Learning rates $\alpha$ and $\beta$; Number of PPO updates $K$
not convergence
$\{\yb, \Gcal\} \in \Dcal[tr]$  Get a (batch of) sample(s) from the training set
$\policy_\phi: \Gcal \mapsto \Gcal[s]$ Get the subgraph using the policy
$\hat{\yb}_s = \frm_{\theta}(\Gcal_s)$ Get the prediction
$\theta \leftarrow \theta - \alpha \nabla_\theta \Lcalp(\theta, \phi)$ Update the parameters of the graph classifier
$\{\yb, \Gcal \} \in \Dcal[val]$  Get a (batch of) sample(s) from the validation set
$\policy_\phi: \Gcal \mapsto \Gcal[s]$  Use the $\policy$ to sample a sparse graph
$\yhat_s = \frm (\Gcal[s])$ Get the prediction of the sparse graph
Add tuple $\{\yb, \Gcal, \yhat, \Gcal[s] \}$ to the buffer $\Bcal$
Compute the quantile $\hat{q}$ using the calibration scores obtained with $\Dcal[tr]$
Compute rewards and prepare mini-batches from buffer $\Bcal$ for PPO updates
i = $\{1, 2, \dots, K\}$ Update PPO K times
$\{\yb, \Gcal, \yhat, \Gcal[s], r\} \sim \Bcal$Sample a batch of tuples from the buffer
Compute advantage estimates $\hat{A}$
$\phi \leftarrow \phi - \beta \nabla_\phi \Lcals(\theta, \phi)$ Update policy by maximizing  <ref>
Check for convergence, update convergence flag
Output: Optimal policy parameters $\phi$ and graph classifier parameters $\theta$

Sparsity optimization
This optimization task corresponds <ref>.
It presents a considerable challenge due to the combinatorial nature of the node and edge removal process.
Specifically, we must determine both which edges ($(u, v) \in \Ecal$) and/or nodes  ($v \in \Vcal$) and how many of them, should be removed.
Drawing inspiration from SparRL <cit.>, we formulate the sparsification task as a Markov Decision Process (MDP) and address it through the framework of graph reinforcement learning <cit.>: we parameterize the policy $\policy_\phi$ using a GNN.
In contrast to prior approaches that rely on value-based methods like Deep Q-Learning <cit.>, we opt for the policy gradient method Proximal Policy Optimization (PPO) <cit.> to capture the inherent uncertainty in the sparsification process.
We denote the objective of sparsity optimization as $\Lcals$, which corresponds to solving the PPO objective in <ref>.
The outcome of this task is a policy $\policy_\phi$ that finds the predictive subgraph $\Gcal[s]$, subsequently employed as input for the graph classification task.
Next, we provide more details on the sparsity optimization.

§.§ Unpacking the sparsity optimization

In this subsection, we provide a detailed description of the components of the PPO method we designed to identify the predictive subgraph.
In RL problems, agents usually make sequential decisions over multiple time steps, and the rewards they receive at each step may depend on the whole trajectory taken so far.
This challenge, known as the “delayed reward”  problem, is a central challenge in RL <cit.>.
Our objective shifts towards identifying the predictive subgraph in a single step, rather than considering a trajectory as in traditional RL.
This approach aims to find a strategy that maximizes the reward across the dataset graphs.
This simplified scenario resembles the Multi-Armed Bandit Problem <cit.>.
As our experiments in <ref> empirically show, this simplified scenario effectively achieves high-performance relying on significantly sparser graphs.
Below, we focus on describing two key components: the policy responsible for the removal process and the design of the reward function that guides the policy in finding the optimal predictive subgraph.

§.§.§ Policy formulation for graph sparsification via node or edge removal

We propose a policy $\policy[\ab | \Gcal; \phi]$ we model using a GNN with parameters $\phi$.
Given an input graph $\Gcal$, the policy produces an action $\ab$, where each element determines whether to keep ($a_i = 0$) or remove ($a_i = 1$) a specific node or edge in $\Vcal$ or $\Ecal$, respectively.
This action results in a subgraph $\Gcal[s] \subseteq \Gcal$.
Recognizing the inherent uncertainty in real-world scenarios where the importance of a node/edge may not be clear, we design the policy as a probability distribution.
We establish two operational modes depending on the removal objective:

* Node Removal Policy: $\policyn[\ab | \Gcal; \phi]$, where $\ab \in \{0, 1\}^{\size{\Vcal}}$. In this scenario, the resulting subgraph $\Gcal[s]$, used as input for the downstream task , satisfies $\Vcal[s] = \{v \in \Vcal | a_v = 0 \}$ and $\Ecal[s] = \{(u, v) \in \Ecal | a_u = 0 \land a_v=0 \}$.

* Edge Removal Policy: $\policye[\ab | \Gcal; \phi]$, where $\ab \in \{0, 1\}^{\size{\Ecal}}$. Here, the subgraph $\Gcal[s]$, used as input for the downstream task, has $\Vcal[s] = \Vcal$ and $\Ecal[s] = \{(u, v) \in \Ecal | a_{uv}=0 \}$.

Note that node removal implies the removal of all edges connected to the node.
In contrast, the edge removal policy retains all nodes, making it suitable for node classification, which is a direction for future work.
In either case, determining $\Gcal[s]$ poses an NP-hard problem for both removal modes.
The number of potential subgraphs increases exponentially with the number of nodes/edges in the original graph.
Specifically, the number of possible actions for $\policyn$ is $\sum_{i=1}^{\size{\Vcal}-1} \binom{\size{\Vcal}}{i}$, while for $\policye$, it is $\sum_{i=1}^{\size{\Ecal}} \binom{\size{\Ecal}}{i}$.
RL can be helpful to solve combinatorial problems, particularly when the reward function effectively guides the optimization process <cit.>.

§.§.§ Reward formulation

The reward function $\reward$ plays a pivotal role in shaping the policy's behavior.
It should provide positive rewards for predictive and sparse subgraphs while penalizing those that negatively impact the performance of the graph classifier.
It is also important to consider that the classifier makes errors, i.e., it does not achieve perfect performance.
Consequently, there are instances where a subgraph may be genuinely predictive, but the classifier produces an incorrect prediction.
Our reward design accounts for this inherent uncertainty through the use of conformal predictions, as described in a subsequent section. It consists of two primary components: one aimed at enhancing performance and the other dedicated to promoting sparsity.

Performance Reward ($\rewardp$) Our approach to rewarding performance is straightforward. We simply use the softmax score assigned by the graph classifier to the correct class $y$, i.e., $\rewardp=\frm_\theta(\Gcal_s)_{y} \in [0, 1]$.

Evolution of the sparsity reward $\rewards$ over the node/edge ratio for different values of the maximum desired nodes/edges ratio $d$.

Sparsity Reward ($\rewards$)
To incentivize a minimal predictive subgraph, we introduce a component that penalizes the nodes ratio $\PR[n]=\frac{\size{\Vcal[s]}}{\size{\Vcal}}$ or the edges ratio $\PR[e]=\frac{\size{\Ecal[s]}}{\size{\Ecal}}$ kept from the original graph, depending on the policy mode.
To control the desired sparsity level, we introduce a parameter $d \in [0,1]$ representing the maximum desired nodes/edges ratio.
Then, we define the sparsity reward as $\rewards(\Gcal[s]) = 1 - \PR^{\tilde{d}}$, where $\tilde{d}$ is a transformation of $d$ such that $\rewards=0.95$ when $\PR=d$.
The variation of $\rewards$ with respect to $\PR$ for different $d$ values is depicted in the inline figure.
Each vertical line represents a unique $d$ value, extending upwards until $\rewards = 0.95$ for all instances.

To seek sparsity, a smaller $d$ value (e.g., blue or yellow curves) is preferred.
This leads to a slower increase in $\rewards$ with node/edge removal, rewarding substantial removal.
Conversely, when $d$ approaches 1 (e.g., pink curve), $\rewards$ close to 1 are awarded even for keeping most nodes/edges.

Note that both reward components fall within the range $[0,1]$, facilitating comparison.
Now, we proceed to define the reward function used in :

\begin{equation}
\reward =
\begin{cases}
\lambda \rewardp +  (1 - \lambda)\rewards(\Gcal_s)  & \text{if } y  \in \cset[\Gcal_s]  \land \size{\cset[\Gcal_s]} = 1, \\
\frac{\rewardp}{\size{\cset[\Gcal_s]}}  & \text{if } y  \in \cset[\Gcal_s] \land \size{\cset[\Gcal_s]} > 1, \\
- \rewards(\Gcal_s) & \text{if } y \not\in \cset[\Gcal_s].
\label{eq:reward}
\end{cases}
\end{equation}

There are two key aspects to highlight.
Firstly, we compute the quantile $\hat{q}$ used to obtain the prediction set $\cset$ using the scoring function introduced in <ref>.
Secondly, it involves three different cases based on whether the true label $y$ is within the prediction set and the size of the prediction set.

The top scenario corresponds to cases in which the predictive subgraph leads to a highly certain and correct prediction.
Here, a parameter $\lambda \in [0, 1]$ allows practitioners to emphasize either performance ($\lambda = 1$) or sparsity ($\lambda = 0$).
In this scenario, the reward is in the range $\Rrm \in [0, 1]$.
The middle scenario addresses instances in which the subgraph leads to the classifier being uncertain about the prediction, i.e., $\size{\cset[\Gcal_s]} > 1$.
In such cases, we aim to provide a positive but smaller reward within the range $(0, 0.5)$.
This reward encourages to increase the probability of the true label and to reduce the size of the prediction set, that is moving to the top scenario. Intuitively, this scenario arises with challenging examples.
The bottom scenario refers to cases in which the predictive subgraph results in an incorrect prediction, falling outside the prediction set $\cset$.
As this behavior is undesirable, the rewards $\Rrm$ fall within the range $[-1, 0]$, encouraging to reduce sparsity. In this scenario, the reward reaches 0 only when we recover the original graph.

The use of conformal prediction in the reward function is essential to guide the policy toward discovering a good predictive subgraph. If the task is challenging and the classifier exhibits uncertainty, the focus should initially be on performance. Only when the classifier is confident about the prediction should we encourage sparsity.
In the following section, we present empirical evidence supporting the reward function's design, and more generally our approach , for achieving both performance and compact predictive subgraphs.

§ EXPERIMENTS

In this section, we present a comprehensive set of experiments to assess the performance of .
First, we conduct an ablation study to show the impact of different values of $\lambda$ and maximum desired ratio ($d$) on performance, as well as the effect of the choice of base GNN architecture.
Then, we compare  with relevant baselines.

Proposed approaches We evaluate the two information removal modes of the proposed framework, described in <ref>. We denote the model with the policy that removes nodes as [N] and the model with the policy that exclusively removes edges as [E].

In this study, we used seven Bioinformatics datasets, which include  <cit.>,  <cit.>,  <cit.>,  <cit.>,  <cit.>,  <cit.>, and  <cit.>. Additionally, we incorporated two chemical compound datasets,  <cit.> and  <cit.>. <ref> shows the statistics of the datasets.

Statistics of the datasets.

Dataset     # Graphs     # Features     # Edge Features     # Classes     Undirected     # Nodes     # Edges

BZR     405     10     0     2     Yes     35.75 $\pm$ 7.26     76.72 $\pm$ 15.39

COX2     467     10     0     2     Yes     41.22 $\pm$ 4.03     86.89 $\pm$ 8.53

DD     1178     20     0     2     Yes     284.32 $\pm$ 272.00     1431.32 $\pm$ 1387.81

ENZYMES     600     21     0     6     Yes     32.63 $\pm$ 15.28     124.27 $\pm$ 51.00

MUTAG     135     7     4     2     Yes     18.85 $\pm$ 4.49     41.67 $\pm$ 11.13

NCI1     4110     7     0     2     Yes     29.87 $\pm$ 13.56     64.60 $\pm$ 29.87

NCI109     4127     8     0     2     Yes     29.68 $\pm$ 13.57     64.26 $\pm$ 29.92

PROTEINS     1113     4     0     2     Yes     39.06 $\pm$ 45.76     145.63 $\pm$ 169.20

PTC     349     8     4     2     Yes     14.11 $\pm$ 8.44     28.97 $\pm$ 18.88

Experimental setup
Aiming for computational efficiency, we conducted cross-validation on the hyperparameters of the vanilla GNN classifier, i.e., the GNN architecture (e.g., ) trained with stochastic gradient descent. We selected the optimal configuration of hyperparameters based on the validation set and used it to train the remaining models.  We performed 5-fold cross-validation and reported standard deviation values on the test set at the last epoch. All experiments were conducted on a single CPU with 8GB of RAM.
Here, we present results obtained using the  architecture.
Additional results using other well-known architectures, namely  and , are provided in <ref>. For a comprehensive overview of the best configuration hyperparameters obtained for each model, architecture and dataset, please refer to <ref>.
We implemented the baselines using the Torch Geometric package <cit.> whenever it was available. Furthermore, we provide the implementation of , along with the necessary scripts to replicate the experiments, at <https://github.com/psanch21/CORES>.

§.§ Ablation study

In this section, we provide an ablation study on the proposed framework analyzing the effects of key hyperparameters and different choices for the base GNN architecture.

$d$ versus accuracy

$d$ versus sparsity

Sparsity versus accuracy

Ablation study on the maximum desired ratio $d$. We use the  architecture and run each experiment for 5 different folds.

$\lambda$ versus accuracy

$\lambda$ versus sparsity

Sparsity versus accuracy

Ablation study on $\lambda$. We use the  architecture and run each experiment for 5 different folds.

Analysis of the impact of $\lambda$ and $d$
The reward function, presented in <ref>, leverages two hyperparameters: the maximum desired nodes/edges ratio ($\desired$)  and the balancing parameter ($\lambda$) to prioritize performance or sparsity.
For the nine datasets under study, we present the effect of varying $\desired$ and $\lambda$ in <ref> and <ref>, respectively, for both [N] (solid lines) and [E] (dashed lines). For this ablation study, we use  as the base GNN architecture. The results are color-coded for each dataset.
The figures in the top row contain the performance analysis, while the middle row shows the sparsity, specifically the node ratio ($\frac{\size{\Vcal_s}}{\size{\Vcal}}$) for [N] and the edge ratio ($\frac{\size{\Ecal_s}}{\size{\Ecal}}$) for [E].
The bottom row shows performance versus sparsity in the vertical and horizontal axes respectively.

In <ref>, we fix $\lambda=0.0$ (only rewarding sparsity) while varying $\desired$ within the range $[0.2, 0.9]$.
Regarding performance (top row), we observe that generally, the value of  $\desired$ does not have an impact.
The middle row, which focuses on sparsity, reveals interesting variations among datasets.
For instance, for the  dataset,  finds a predictive subgraph that utilizes as little as 20% of the original nodes/edges with $\desired=0.2$.
In contrast, for the  dataset, we keep approximately 80% of the original nodes in [N] and 60% of the original edges in [E], even with low $\desired$ values.
The bottom figures highlight that for certain datasets, e.g., ,  can maintain comparable accuracy regardless of sparsity levels. Conversely, for other datasets, decreasing sparsity tends to enhance performance, such as the case with the  dataset and [N].
These findings suggest that some datasets exhibit rapid performance degradation when information is removed.
Examining the different reward scenarios in our reward definition (refer to <ref>), it is intuitive to deduce that  will prioritize reducing sparsity if the prediction is not within the prediction set (bottom scenario) or enhancing performance when the classifier exhibits uncertainty (middle scenario).

In <ref>, we fix $\desired=0.1$ (favoring high levels of sparsity) and we vary $\lambda$ within the range $[0.0, 1.0]$.
We observe a similar behavior as in <ref>.
The top row consistently shows that varying $\lambda$ has a minimal impact on accuracy, and only sometimes leads to increased accuracy as $\lambda$ increases (e.g.,  dataset).
Importantly, for none of the datasets does performance degrade with higher $\lambda$ values.
This behavior aligns with our objective, as higher values of $\lambda$ correspond to a greater emphasis on rewarding performance.
The middle row reveals two distinct patterns: i) a high correlation between $\lambda$ and the number of nodes/edges kept, particularly evident in datasets like , and ii) minimal sensitivity, as observed with the  dataset.
The bottom row reveals similar patterns: positive correlation between the node/edge ratio and accuracy. It is also worth noting that varying $\lambda$ results in a wide range of sparsity levels for some datasets, such as 20-90% for , and a narrower range for others, like 40-70% for .

In summary, we observe that varying $\desired$ or $\lambda$ leads to one of two scenarios, depending on the dataset:
i) A minimal change in performance and low sparsity, which suggests that information removal significantly degrades performance for these datasets.
ii) A small positive correlation between the hyperparameters and performance and a high negative correlation between the hyperparameters and sparsity.
Based on these insights, we recommend that practitioners use $\desired$ to fine-tune sparsity levels and consider $\lambda=1.0$ when prioritizing performance over sparsity. <ref> contains the results for the rest of the datasets under study.

Ablation study on GNN architecture. We compare the performance (accuracy) and sparsity (node/edge ratio) of  with the  approach for the  (left) and (right) architectures.  We show the mean over 5 independent runs and the standard deviation as the subindex. All metrics are shown in percentages.

2*Dataset     2*Metric     3c     3c

CORES$_N$     CORES$_E$          CORES$_N$     CORES$_E$

3*BZR     Accuracy     86.83$_{4.08}$     82.44$_{4.69}$     80.98$_{5.29}$     80.98$_{4.36}$     83.90$_{4.43}$     81.46$_{4.08}$

Node Ratio     -     76.98$_{6.06}$     100.00$_{0.00}$     -     37.99$_{10.27}$     100.00$_{0.00}$

Edge Ratio     -     61.17$_{11.31}$     46.16$_{5.68}$     -     29.92$_{8.83}$     57.26$_{21.50}$

3*COX2     Accuracy     79.15$_{4.85}$     80.85$_{3.01}$     81.70$_{4.90}$     82.13$_{4.15}$     81.70$_{4.41}$     80.85$_{2.61}$

Node Ratio     -     72.49$_{4.24}$     100.00$_{0.00}$     -     77.91$_{2.29}$     100.00$_{0.00}$

Edge Ratio     -     53.19$_{8.07}$     31.27$_{23.60}$     -     62.62$_{3.24}$     66.18$_{0.38}$

3*DD     Accuracy     78.47$_{3.47}$     79.32$_{2.58}$     75.76$_{4.05}$     76.10$_{3.02}$     75.42$_{4.19}$     76.44$_{2.19}$

Node Ratio     -     56.44$_{2.50}$     100.00$_{0.00}$     -     75.16$_{1.39}$     100.00$_{0.00}$

Edge Ratio     -     32.01$_{2.89}$     51.39$_{1.90}$     -     56.42$_{2.16}$     58.62$_{2.51}$

3*ENZYMES     Accuracy     66.00$_{5.35}$     58.31$_{8.47}$     57.02$_{11.62}$     71.33$_{10.63}$     69.84$_{4.43}$     67.54$_{12.23}$

Node Ratio     -     77.17$_{7.28}$     100.00$_{0.00}$     -     80.26$_{1.03}$     100.00$_{0.00}$

Edge Ratio     -     62.33$_{9.26}$     74.20$_{35.99}$     -     65.92$_{1.80}$     61.60$_{9.06}$

3*MUTAG     Accuracy     81.43$_{3.91}$     81.43$_{10.83}$     87.14$_{6.56}$     81.43$_{6.39}$     80.00$_{5.98}$     81.43$_{6.02}$

Node Ratio     -     79.94$_{2.79}$     100.00$_{0.00}$     -     75.72$_{4.04}$     100.00$_{0.00}$

Edge Ratio     -     63.52$_{4.23}$     32.66$_{8.79}$     -     58.74$_{6.05}$     55.25$_{14.77}$

3*NCI1     Accuracy     77.33$_{2.09}$     66.45$_{7.71}$     65.94$_{6.31}$     79.42$_{1.34}$     73.43$_{2.67}$     75.38$_{1.22}$

Node Ratio     -     76.47$_{17.88}$     100.00$_{0.00}$     -     63.49$_{3.58}$     100.00$_{0.00}$

Edge Ratio     -     64.02$_{18.84}$     37.98$_{14.34}$     -     53.33$_{2.81}$     88.68$_{6.67}$

3*NCI109     Accuracy     79.32$_{1.57}$     76.08$_{2.71}$     77.14$_{2.02}$     76.90$_{1.34}$     74.72$_{2.25}$     72.78$_{2.29}$

Node Ratio     -     78.78$_{4.15}$     100.00$_{0.00}$     -     71.55$_{11.30}$     100.00$_{0.00}$

Edge Ratio     -     67.08$_{4.42}$     92.02$_{1.93}$     -     62.37$_{12.96}$     62.37$_{13.13}$

3*PROTEINS     Accuracy     72.86$_{1.02}$     73.21$_{2.45}$     75.89$_{1.94}$     75.36$_{3.00}$     73.39$_{3.86}$     73.57$_{1.62}$

Node Ratio     -     74.66$_{6.10}$     100.00$_{0.00}$     -     67.94$_{2.97}$     100.00$_{0.00}$

Edge Ratio     -     56.12$_{9.77}$     64.73$_{0.98}$     -     46.56$_{4.27}$     52.82$_{1.86}$

3*PTC     Accuracy     57.78$_{7.71}$     62.86$_{2.86}$     63.43$_{3.13}$     64.00$_{4.33}$     62.96$_{4.17}$     59.43$_{4.69}$

Node Ratio     -     64.10$_{4.19}$     100.00$_{0.00}$     -     45.61$_{6.00}$     100.00$_{0.00}$

Edge Ratio     -     40.21$_{6.93}$     44.47$_{5.29}$     -     21.24$_{6.53}$     76.36$_{14.75}$

Ablation on the base GNN architecture
Now, we analyze how switching the base architecture affects the performance of .
<ref> summarizes the results for two base architectures:  and .
We observe that even when the base architecture changes, both [N] and [E] achieve competitive accuracy compared to the respective  approach that simply trains the GNN architecture using all the information from the original graph. We refer the reader to <ref> for the complete results.

§.§ Performance comparison

In this section, we conduct a comprehensive evaluation of  by comparing it with baselines and competing methods across nine datasets.

We assess the performance on the test set using three key metrics: accuracy (the larger the better $\uparrow$), as well as the percentage of nodes (for [N]) or edges (for [E]) kept in the subgraph (the lower the better $\downarrow$).
Decreasing these percentages increases graph sparsity, enhancing model interpretability.

Model comparison results. We show the mean over 5 independent runs and the standard deviation as the subindex. All metrics are shown in percentage. The last rows include the average ranking of the model across datasets. Best performing models on average are indicated in bold.

2*Dataset     2*Metric     3cFull Models     4cSparse Models

(lr)3-5 (lr)6-9
SAGPool     DiffPool     SUGAR     GPool     CORES$_N$     CORES$_E$

3*BZR     Accuracy     82.44$_{5.00}$     85.85$_{2.67}$     70.24$_{5.95}$     -     80.98$_{4.01}$     84.88$_{4.01}$     81.95$_{5.62}$

Node Ratio     -     -     -     -     96.46$_{0.19}$     15.91$_{5.30}$     100.00$_{0.00}$

Edge Ratio     -     -     -     -     96.40$_{0.45}$     10.84$_{5.80}$     76.03$_{3.72}$

3*COX2     Accuracy     82.13$_{5.12}$     80.43$_{3.16}$     65.83$_{6.65}$     -     80.43$_{3.50}$     82.98$_{3.36}$     85.11$_{3.01}$

Node Ratio     -     -     -     -     91.15$_{0.14}$     86.44$_{3.48}$     100.00$_{0.00}$

Edge Ratio     -     -     -     -     89.20$_{1.08}$     77.63$_{6.60}$     58.30$_{28.00}$

3*DD     Accuracy     78.81$_{3.44}$     74.07$_{4.09}$     -     -     77.46$_{3.31}$     75.42$_{5.22}$     75.25$_{2.77}$

Node Ratio     -     -     -     -     40.23$_{0.03}$     47.53$_{15.04}$     100.00$_{0.00}$

Edge Ratio     -     -     -     -     15.41$_{0.26}$     25.88$_{14.79}$     51.55$_{2.42}$

3*ENZYMES     Accuracy     61.67$_{8.50}$     45.90$_{5.18}$     31.00$_{6.66}$     16.67$_{23.57}$     62.62$_{5.36}$     62.33$_{6.08}$     64.92$_{3.40}$

Node Ratio     -     -     -     -     96.67$_{0.14}$     80.67$_{1.16}$     100.00$_{0.00}$

Edge Ratio     -     -     -     -     93.37$_{0.14}$     66.90$_{1.66}$     72.71$_{1.00}$

3*MUTAG     Accuracy     85.71$_{8.75}$     78.57$_{5.05}$     69.00$_{12.21}$     76.34$_{3.80}$     81.43$_{3.91}$     82.86$_{6.39}$     82.14$_{5.98}$

Node Ratio     -     -     -     -     51.38$_{0.12}$     52.38$_{7.67}$     100.00$_{0.00}$

Edge Ratio     -     -     -     -     36.56$_{9.20}$     36.31$_{11.32}$     61.09$_{12.39}$

3*NCI1     Accuracy     76.89$_{2.03}$     69.29$_{2.12}$     69.93$_{3.24}$     49.95$_{35.58}$     77.77$_{1.93}$     73.34$_{6.30}$     74.34$_{7.53}$

Node Ratio     -     -     -     -     96.89$_{0.08}$     89.13$_{13.88}$     100.00$_{0.00}$

Edge Ratio     -     -     -     -     94.47$_{0.28}$     86.61$_{20.20}$     84.06$_{27.86}$

3*NCI109     Accuracy     78.64$_{2.69}$     74.14$_{0.85}$     67.49$_{2.60}$     49.65$_{35.71}$     75.45$_{3.30}$     73.03$_{1.90}$     75.74$_{2.04}$

Node Ratio     -     -     -     -     96.79$_{0.04}$     66.31$_{5.69}$     100.00$_{0.00}$

Edge Ratio     -     -     -     -     93.65$_{0.22}$     61.26$_{7.22}$     71.34$_{7.62}$

3*PROTEINS     Accuracy     75.18$_{2.04}$     70.54$_{3.63}$     66.42$_{7.19}$     59.57$_{43.01}$     72.68$_{1.85}$     73.75$_{4.02}$     74.11$_{2.82}$

Node Ratio     -     -     -     -     41.92$_{0.30}$     87.01$_{20.04}$     100.00$_{0.00}$

Edge Ratio     -     -     -     -     19.42$_{0.64}$     78.55$_{32.05}$     83.31$_{37.32}$

3*PTC     Accuracy     63.43$_{1.28}$     61.14$_{8.23}$     54.44$_{11.10}$     56.14$_{8.95}$     59.43$_{3.73}$     64.00$_{3.26}$     63.43$_{1.28}$

Node Ratio     -     -     -     -     43.52$_{0.67}$     96.02$_{8.80}$     100.00$_{0.00}$

Edge Ratio     -     -     -     -     24.80$_{3.48}$     93.19$_{15.13}$     88.61$_{15.64}$

3*Avg. Rank     Accuracy     2.11     4.44     6.12     6.67     3.44     2.67     2.67

Node Ratio     -     -     -     -     1.56     1.44     -

Edge Ratio     -     -     -     -     2.22     1.67     2.11

We divided the baselines into two categories: Full model (use complete graph information) and Sparse (use part of the graph information) model approaches.
In the Full model category, we compare with the following approaches:
approach representing training the  base GNN architecture without any sparsity consideration,
<cit.>, and
<cit.>—which uses node embeddings coming from a GNN to select the top $k$ nodes, thus incorporating global information.
For the Sparse models, we compare with:
<cit.> [We use the official implementation of  to extract the results on the above datasets. We believe our evaluation of a held-out test set may explain the disparity between the results we report and those in <cit.>. Instead, the available implementation of  evaluates on the same validation set used to select the best model. ] (for the datasets that their code can run) and
<cit.>— where the node embeddings used to select the top $k$ come from a multi-layer perceptron, hence the subgraph does not contain global information.
Here, we present the results using  <cit.> as the base GNN architecture. Refer to <ref> for the results using  and .

Quantitative results
<ref> summarizes the results.
In terms of accuracy, we observe that while  consistently achieves the highest accuracy on most datasets, [E] and [N] secure the second and third-best positions, outperforming all other Full models and all Sparse models, which highlights the competitive performance of the proposed approach.
On the other hand,  consistently underperforms across all datasets, and its results exhibit high variance.
Regarding interpretability (understood as sparsity), we perform a node and edge ratio analysis on the three best-performing Sparse models in terms of accuracy: [N], [E], and .
It is important to note that [E] consistently maintains a node ratio of 100%, due to its edge removal strategy that preserves all nodes.
Among these models, [N] achieves the highest rankings in both node and edge ratios, indicating its effectiveness in removing a larger number of nodes from the original graph.
Consequently, the graph classifier operates on a reduced, and thus more interpretable, subgraph.
Finally, we find it interesting to analyze the results for the  dataset (bottom row). We observe that  , in both removal modes, achieves the worst sparsity results but at the same time the best performance among all models.
In terms of sparsity, [N] keeps 96.02% of the nodes, while [E] keeps 88.61% of the edges.
In terms of accuracy, all the models achieve less than  65%, which is notably low for a binary classification problem.
This indicates that the classifier makes a substantial number of errors.
This observation is important considering the design of the proposed reward function of  (see <ref>).
For this dataset, the reward function places  in a scenario where it seeks to enhance performance, corresponding to the middle case, or penalize sparsity, corresponding to the bottom case of the reward function.
In essence,  behaves in accordance with the reward function.

Illustration of the predictive subgraph obtained by [N] for a mutagenic (top) and non-mutagenic (bottom) graph of the  dataset.

Qualitative results
<ref> presents two examples of the predictive subgraphs discovered by [N] for the  dataset, showcasing positive (top) and negative (bottom) instances.
In this dataset, the positive class ($y=1$) represents mutagenic molecules, while the negative class ($y=0$) corresponds to non-mutagenic molecules. The left side of the figure shows the original graphs, while the center illustrates the predictive subgraphs identified by [N].
We observe that for the mutagenic graph (top), [N] keeps $N0_2$ nitrogen dioxide compounds and some carbon atoms, while for the non-mutagenic graph (bottom), it captures chlorine carbon atoms as relevant for the classification task.
These findings align with prior in the chemical domain <cit.>.

Time complexity
Training and inference are significantly faster in methods that employ a straightforward forward pass compared to RL-based methods like  and . Notably, our findings indicate that  is at least as fast as  during training and can be up to 10 times faster during inference. For comprehensive quantitative results across all datasets, please refer to <ref>.

§ CONCLUSIONS

Graph Neural Networks (GNNs) have demonstrated exceptional performance in graph-level tasks,  but suffer from interpretability issues due to their complexity.
Existing interpretability research in GNNs mainly focuses on post-hoc explanations.
Approaches that aim to introduce sparsity during training often provide predictive subgraphs that are not faithful with the classifier predictions.
Also, these methods often rely on complete graph information and/or make strong assumptions about the sparser graphs.
In this work, we introduced , a novel GNN training approach that simultaneously identifies predictive subgraphs by removing edges and/or nodes, without imposing assumptions about subgraph structures; and optimizes the performance of the graph classification task.
The optimization for performance refers to the conventional supervised problem paradigm.
We then leverage reinforcement learning to identify predictive subgraphs, using a policy that allows both edge and node removal modes.
One key aspect of  is the design of the reward function. This function allows the practitioner to introduce inductive biases towards either sparse or high-performing predictive subgraphs and it incorporates conformal predictions <cit.> to account for classifier uncertainty.
Our empirical evaluation, conducted on nine graph classification datasets, provides evidence that our approach not only competes in performance with the baselines that use the complete graph information but also relies on significantly sparser subgraphs.
Consequently, the resulting GNN-based predictions are more interpretable, addressing the primary motivation behind our work.

Practical limitations
The main limitation of our proposed approach lies in the significantly increased training and inference time, introduced by the reinforcement learning component,  compared to the baselines that do not use reinforcement learning.

Future work
Future research could focus on improving the efficiency of the reinforcement learning component to accelerate the training process of .
Another interesting avenue for future work could involve modifying the current reward function to penalize specific types of errors or undesirable structures, such as isolated nodes.
Additionally, it could also be interesting to explore the application of  to graph regression tasks and [E] to node classification tasks.

§ ACKNOWLEDGEMENTS

Pablo Sánchez Martín thanks the German Research Foundation through the Cluster of Excellence “Machine Learning – New Perspectives for Science”, EXC 2064/1, project number 390727645 for generous funding support.
The authors thank the International Max Planck Research School for Intelligent Systems (IMPRS-IS) for supporting Pablo Sánchez Martín.

§ TRAINING DETAILS

In this section, we provide further details of the experimental setup used to obtain our results.
For all experiments, we train the models using a fixed seed of 0, and the reported results represent the mean and standard deviation over five different dataset splits.
We run the models up to  1000 epochs, doing early stopping if the accuracy does not improve for 500 epochs. All experiments were conducted on a single CPU with 8GB of RAM.
We carry out hyperparameter tuning using random sampling. We explored 20 different configurations for each model, data, and GNN architecture. Complete details regarding the cross-validated hyperparameters can be found in our GitHub repository at <https://github.com/psanch21/CORES>.
<ref> presents the best configurations achieved for each dataset and architecture for the  GNN baselines. These configurations were subsequently used for training . The best configuration for [N] is detailed in <ref>, while for [E], it can be found in <ref>.
The best configurations for  and  are outlined in <ref> and <ref>, respectively.

Best configuration for the  GNN. Split sizes ($\#$0), Batch size ($\#$1), Dropout rate ($\#$2), Batch normalizing ($\#$3), Dimension of hidden layers ($\#$4), Number of GNN layers ($\#$5), Global pooling type ($\#$6), Classifier scheduler factor ($\#$7), Classifier learning rate ($\#$8), $\epsilon$ ($\#$9), Trainable $\epsilon$ ($\#$10), Number of heads ($\#$11).

2*Param     2*Archi     9cDatasets

BZR     COX2     DD     ENZYMES     MUTAG     NCI1     NCI109     PROTEINS     PTC

3* $\#$0     GIN     [0.6, 0.3, 0.1]     [0.4, 0.5, 0.1]     [0.6, 0.3, 0.1]     [0.5, 0.4, 0.1]     [0.4, 0.5, 0.1]     [0.5, 0.4, 0.1]     [0.4, 0.5, 0.1]     [0.4, 0.5, 0.1]     [0.6, 0.3, 0.1]

GAT     [0.6, 0.3, 0.1]     [0.5, 0.4, 0.1]     [0.5, 0.4, 0.1]     [0.5, 0.4, 0.1]     [0.5, 0.4, 0.1]     [0.6, 0.3, 0.1]     [0.6, 0.3, 0.1]     [0.4, 0.5, 0.1]     [0.5, 0.4, 0.1]

GCN     [0.6, 0.3, 0.1]     [0.5, 0.4, 0.1]     [0.6, 0.3, 0.1]     [0.5, 0.4, 0.1]     [0.5, 0.4, 0.1]     [0.6, 0.3, 0.1]     [0.6, 0.3, 0.1]     [0.4, 0.5, 0.1]     [0.4, 0.5, 0.1]

3* $\#$1     GIN     16     16     32     16     16     16     32     16     32

GAT     32     16     32     16     16     32     32     16     16

GCN     16     16     32     16     32     32     16     32     32

3* $\#$2     GIN     0.0     0.2     0.5     0.2     0.0     0.0     0.1     0.1     0.4

GAT     0.1     0.2     0.3     0.4     0.3     0.2     0.1     0.1     0.5

GCN     0.3     0.1     0.3     0.0     0.4     0.0     0.1     0.4     0.5

3* $\#$3     GIN     True     False     True     True     True     True     True     False     False

GAT     True     True     False     True     True     True     False     False     True

GCN     True     False     False     True     False     True     True     False     False

3* $\#$4     GIN     128     64     32     64     16     128     128     128     16

GAT     16     128     16     128     32     128     128     16     16

GCN     64     128     32     128     16     64     128     32     32

3* $\#$5     GIN     3     1     1     1     3     1     3     1     3

GAT     1     2     1     4     4     4     3     2     4

GCN     1     4     3     3     4     3     4     1     1

3* $\#$6     GIN     ['mean', 'add']     ['add']     ['mean', 'add']     ['mean']     ['mean', 'add']     ['mean']     ['mean']     ['add']     ['mean']

GAT     ['add']     ['mean']     ['mean', 'add']     ['mean']     ['mean', 'add']     ['add']     ['mean', 'add']     ['add']     ['mean', 'add']

GCN     ['mean']     ['mean', 'add']     ['mean', 'add']     ['mean']     ['mean', 'add']     ['mean', 'add']     ['add']     ['add']     ['mean']

3* $\#$7     GIN     0.95     0.99     0.99     0.9     0.95     0.9     0.99     0.9     0.99

GAT     0.95     0.95     0.99     0.95     0.99     0.95     0.99     0.95     0.9

GCN     0.99     0.99     0.99     0.95     0.99     0.99     0.9     0.99     0.99

3* $\#$8     GIN     0.0001     0.001     0.005     0.0001     0.001     0.01     0.001     0.0005     0.005

GAT     0.01     0.0001     0.0001     0.001     0.005     0.005     0.001     0.005     0.01

GCN     0.01     0.0001     0.001     0.01     0.005     0.005     0.001     0.001     0.01

3* $\#$9     GIN     0.3     0.2     0.3     0.0     0.2     0.2     0.2     0.0     0.2

GAT     -     -     -     -     -     -     -     -     -

GCN     -     -     -     -     -     -     -     -     -

3* $\#$10     GIN     False     True     True     True     True     False     True     False     False

GAT     -     -     -     -     -     -     -     -     -

GCN     -     -     -     -     -     -     -     -     -

3* $\#$11     GIN     -     -     -     -     -     -     -     -     -

GAT     2.0     4.0     4.0     2.0     2.0     4.0     4.0     2.0     4.0

GCN     -     -     -     -     -     -     -     -     -

Best configuration for . Split sizes ($\#$0), Batch size ($\#$1), Early stopping clf. patience ($\#$2), Dropout rate ($\#$3), Batch normalizing ($\#$4), Dimension of hidden layers ($\#$5), Number of GNN layers ($\#$6), Global pooling type ($\#$7), Classifier scheduler factor ($\#$8), Classifier learning rate ($\#$9), TopK multiplier ($\#$10), TopK ratio ($\#$11), Number of heads ($\#$12), $\epsilon$ ($\#$13), Trainble $\epsilon$ ($\#$14)

2*Param     2*Archi     9cDatasets

BZR     COX2     DD     ENZYMES     MUTAG     NCI1     NCI109     PROTEINS     PTC

3* $\#$0     GCN     [0.5, 0.4, 0.1]     [0.5, 0.4, 0.1]     [0.4, 0.5, 0.1]     [0.5, 0.4, 0.1]     [0.5, 0.4, 0.1]     [0.5, 0.4, 0.1]     [0.5, 0.4, 0.1]     [0.4, 0.5, 0.1]     [0.6, 0.3, 0.1]

GAT     [0.4, 0.5, 0.1]     [0.4, 0.5, 0.1]     [0.4, 0.5, 0.1]     [0.5, 0.4, 0.1]     [0.4, 0.5, 0.1]     [0.6, 0.3, 0.1]     [0.5, 0.4, 0.1]     [0.4, 0.5, 0.1]     [0.4, 0.5, 0.1]

GIN     [0.5, 0.4, 0.1]     [0.5, 0.4, 0.1]     [0.5, 0.4, 0.1]     [0.6, 0.3, 0.1]     [0.5, 0.4, 0.1]     [0.5, 0.4, 0.1]     [0.6, 0.3, 0.1]     [0.6, 0.3, 0.1]     [0.5, 0.4, 0.1]

3* $\#$1     GCN     16     16     16     16     32     16     16     16     32

GAT     16     16     16     16     16     16     32     16     16

GIN     16     16     16     32     32     16     32     32     16

3* $\#$2     GCN     800     650     500     650     500     650     650     500     650

GAT     800     800     500     800     800     650     500     800     800

GIN     800     500     650     500     800     800     500     500     650

3* $\#$3     GCN     0.4     0.0     0.5     0.1     0.4     0.0     0.1     0.5     0.4

GAT     0.3     0.3     0.1     0.1     0.4     0.1     0.4     0.3     0.3

GIN     0.2     0.3     0.5     0.0     0.4     0.2     0.0     0.0     0.5

3* $\#$4     GCN     True     False     False     True     True     False     True     False     False

GAT     False     False     False     False     True     True     False     False     False

GIN     True     False     False     True     False     True     True     True     False

3* $\#$5     GCN     128     32     32     128     32     32     128     32     64

GAT     16     16     64     128     16     32     16     16     16

GIN     32     128     128     64     16     32     64     64     128

3* $\#$6     GCN     4     1     4     4     1     1     4     4     3

GAT     1     1     2     2     2     3     2     1     1

GIN     4     4     3     1     2     4     1     1     3

3* $\#$7     GCN     ['add']     ['mean', 'add']     ['add']     ['mean']     ['mean', 'add']     ['mean', 'add']     ['mean']     ['add']     ['mean']

GAT     ['mean', 'add']     ['mean', 'add']     ['mean', 'add']     ['mean', 'add']     ['mean', 'add']     ['mean']     ['mean', 'add']     ['mean', 'add']     ['mean', 'add']

GIN     ['mean']     ['mean']     ['mean']     ['add']     ['mean', 'add']     ['mean']     ['add']     ['add']     ['mean']

3* $\#$8     GCN     0.99     0.95     0.99     0.95     0.9     0.95     0.95     0.99     0.9

GAT     0.9     0.9     0.9     0.99     0.99     0.95     0.99     0.9     0.9

GIN     0.9     0.99     0.95     0.95     0.99     0.9     0.95     0.95     0.95

3* $\#$9     GCN     0.01     0.005     0.0005     0.0001     0.01     0.005     0.0001     0.0005     0.0001

GAT     0.01     0.01     0.01     0.005     0.005     0.0001     0.005     0.01     0.01

GIN     0.001     0.0005     0.0005     0.001     0.005     0.001     0.001     0.001     0.0005

3* $\#$10     GCN     0.5     2.0     0.5     1.5     1.0     2.0     1.5     0.5     0.5

GAT     1.0     1.0     2.0     1.0     1.5     1.5     0.5     1.0     1.0

GIN     1.5     2.0     0.5     0.5     0.5     1.5     0.5     0.5     0.5

3* $\#$11     GCN     0.95     0.95     0.9     0.3     0.3     0.95     0.3     0.9     0.2

GAT     0.9     0.9     0.5     0.9     0.2     0.6     0.8     0.9     0.9

GIN     0.3     0.4     0.8     0.3     0.8     0.3     0.3     0.3     0.8

3* $\#$12     GCN     -     -     -     -     -     -     -     -     -

GAT     1.0     1.0     1.0     1.0     1.0     1.0     4.0     1.0     1.0

GIN     -     -     -     -     -     -     -     -     -

3* $\#$13     GCN     -     -     -     -     -     -     -     -     -

GAT     -     -     -     -     -     -     -     -     -

GIN     0.4     0.2     0.4     0.4     0.3     0.4     0.4     0.4     0.4

3* $\#$14     GCN     -     -     -     -     -     -     -     -     -

GAT     -     -     -     -     -     -     -     -     -

GIN     False     True     True     True     False     False     True     True     True

Best configuration for the . Split sizes ($\#$0), Batch size ($\#$1), Early stopping clf. patience ($\#$2), Dropout rate ($\#$3), Batch normalizing ($\#$4), Dimension of hidden layers ($\#$5), Number of GNN layers ($\#$6), Global pooling type ($\#$7), Classifier scheduler factor ($\#$8), Classifier learning rate ($\#$9), TopK multiplier ($\#$10), TopK ratio ($\#$11), Number of heads ($\#$12), $\epsilon$ ($\#$13), Trainble $\epsilon$ ($\#$14).

2*Param     2*Archi     9cDatasets

BZR     COX2     DD     ENZYMES     MUTAG     NCI1     NCI109     PROTEINS     PTC

3* $\#$0     GAT     [0.5, 0.4, 0.1]     [0.6, 0.3, 0.1]     [0.6, 0.3, 0.1]     [0.4, 0.5, 0.1]     [0.4, 0.5, 0.1]     [0.4, 0.5, 0.1]     [0.4, 0.5, 0.1]     [0.4, 0.5, 0.1]     [0.4, 0.5, 0.1]

GIN     [0.4, 0.5, 0.1]     [0.4, 0.5, 0.1]     [0.4, 0.5, 0.1]     [0.4, 0.5, 0.1]     [0.5, 0.4, 0.1]     [0.4, 0.5, 0.1]     [0.4, 0.5, 0.1]     [0.4, 0.5, 0.1]     [0.5, 0.4, 0.1]

GCN     [0.4, 0.5, 0.1]     [0.4, 0.5, 0.1]     [0.4, 0.5, 0.1]     [0.4, 0.5, 0.1]     [0.5, 0.4, 0.1]     [0.4, 0.5, 0.1]     [0.4, 0.5, 0.1]     [0.4, 0.5, 0.1]     [0.6, 0.3, 0.1]

3* $\#$1     GAT     16     16     16     32     32     32     32     32     32

GIN     32     16     16     32     16     32     32     16     32

GCN     16     16     32     32     16     32     32     32     16

3* $\#$2     GAT     500     650     800     500     500     500     500     650     800

GIN     500     800     800     500     800     500     500     800     800

GCN     650     650     500     500     650     500     500     800     650

3* $\#$3     GAT     0.0     0.3     0.5     0.1     0.1     0.1     0.1     0.1     0.3

GIN     0.1     0.0     0.5     0.1     0.4     0.1     0.1     0.5     0.2

GCN     0.0     0.0     0.4     0.1     0.0     0.3     0.1     0.5     0.1

3* $\#$4     GAT     True     True     False     True     True     True     True     False     False

GIN     True     True     False     True     False     True     True     False     False

GCN     True     True     False     True     True     True     True     True     False

3* $\#$5     GAT     16     64     16     64     64     64     64     16     64

GIN     64     32     16     64     32     64     64     16     128

GCN     128     128     128     64     32     128     64     16     16

3* $\#$6     GAT     2     4     1     2     2     2     2     1     3

GIN     2     1     1     2     1     2     2     1     4

GCN     2     2     2     2     4     3     2     3     3

3* $\#$7     GAT     ['mean', 'add']     ['mean']     ['mean', 'add']     ['mean']     ['mean']     ['mean']     ['mean']     ['add']     ['add']

GIN     ['mean']     ['mean']     ['mean', 'add']     ['mean']     ['mean', 'add']     ['mean']     ['mean']     ['mean', 'add']     ['add']

GCN     ['mean']     ['mean']     ['add']     ['mean']     ['mean', 'add']     ['mean', 'add']     ['mean']     ['mean', 'add']     ['mean']

3* $\#$8     GAT     0.9     0.95     0.9     0.9     0.9     0.9     0.9     0.95     0.99

GIN     0.9     0.9     0.9     0.9     0.9     0.9     0.9     0.9     0.9

GCN     0.95     0.95     0.99     0.9     0.99     0.9     0.9     0.99     0.95

3* $\#$9     GAT     0.005     0.0005     0.001     0.01     0.01     0.01     0.01     0.001     0.0005

GIN     0.01     0.0001     0.001     0.01     0.01     0.01     0.01     0.001     0.0001

GCN     0.0001     0.0001     0.01     0.01     0.01     0.001     0.01     0.001     0.005

3* $\#$10     GAT     2.0     0.5     1.5     2.0     2.0     2.0     2.0     1.5     0.5

GIN     2.0     2.0     1.5     2.0     1.0     2.0     2.0     1.5     0.5

GCN     1.0     1.0     1.5     2.0     0.5     1.0     2.0     0.5     1.5

3* $\#$11     GAT     0.4     0.5     0.4     0.95     0.95     0.95     0.95     0.5     0.5

GIN     0.95     0.9     0.4     0.95     0.5     0.95     0.95     0.4     0.4

GCN     0.95     0.95     0.4     0.95     0.7     0.95     0.95     0.5     0.8

3* $\#$12     GAT     4.0     1.0     1.0     1.0     1.0     1.0     1.0     1.0     1.0

GIN     -     -     -     -     -     -     -     -     -

GCN     -     -     -     -     -     -     -     -     -

3* $\#$13     GAT     -     -     -     -     -     -     -     -     -

GIN     0.0     0.4     0.1     0.0     0.1     0.0     0.0     0.1     0.2

GCN     -     -     -     -     -     -     -     -     -

3* $\#$14     GAT     -     -     -     -     -     -     -     -     -

GIN     True     True     False     True     True     True     True     False     True

GCN     -     -     -     -     -     -     -     -     -

Best configuration for [N]. Early stopping PPO patience ($\#$0), Number of environment steps ($\#$1), Number of PPO epochs ($\#$2), Environment penalty size ($\#$3), RL scheduler factor ($\#$4), Ratio of the critic learning rate ($\#$5), PPO entropy coefficient ($\#$6), PPO MSE coefficient ($\#$7), PPO clip value $\epsilon$ ($\#$8), Conformal error rate $\alpha$ ($\#$9), $d$ ($\#$10), $\lambda$ ($\#$11).

2*Param     2*Archi     9cDatasets

BZR     COX2     DD     ENZYMES     MUTAG     NCI1     NCI109     PROTEINS     PTC

3* $\#$0     GIN     15     5     5     10     10     5     15     5     5

GCN     10     5     5     15     5     15     10     15     15

GAT     15     5     5     10     15     15     10     10     5

3* $\#$1     GIN     128     128     128     128     128     128     64     64     64

GCN     32     64     64     128     64     32     32     32     128

GAT     64     32     32     32     128     64     32     32     64

3* $\#$2     GIN     10     15     15     5     15     15     10     5     15

GCN     10     15     15     5     15     3     10     5     5

GAT     10     15     15     10     5     10     10     5     5

3* $\#$3     GIN     0.5     0.5     0.5     0.5     0.5     0.5     1.5     1.5     1.0

GCN     0.5     0.5     0.5     1.0     0.5     0.5     0.5     1.5     1.5

GAT     1.5     0.5     1.5     0.5     1.5     1.5     0.5     1.0     1.5

3* $\#$4     GIN     0.99     0.95     0.95     0.99     0.9     0.95     0.9     0.9     0.95

GCN     0.99     0.95     0.95     0.99     0.95     0.99     0.99     0.9     0.9

GAT     0.9     0.95     0.99     0.99     0.9     0.9     0.99     0.95     0.9

3* $\#$5     GIN     3.0     2.5     2.5     1.0     3.0     2.5     2.5     1.0     3.0

GCN     2.5     1.5     1.5     2.0     1.5     3.0     2.5     2.5     1.5

GAT     2.5     2.0     2.5     2.5     1.5     2.5     2.5     1.0     1.0

3* $\#$6     GIN     0.001     0.0001     0.0001     0.01     0.001     0.0001     0.0001     0.001     0.0001

GCN     0.0001     0.01     0.01     0.0001     0.01     0.01     0.0001     0.01     0.001

GAT     0.0001     0.001     0.001     0.0001     0.001     0.0001     0.0001     0.001     0.001

3* $\#$7     GIN     0.5     5.0     5.0     2.0     1.0     5.0     2.0     3.0     0.5

GCN     1.0     0.5     0.5     0.1     0.5     1.0     1.0     5.0     3.0

GAT     2.0     1.0     3.0     1.0     3.0     2.0     1.0     0.1     3.0

3* $\#$8     GIN     0.2     0.4     0.4     0.1     0.2     0.4     0.2     0.1     0.4

GCN     0.4     0.3     0.3     0.3     0.3     0.1     0.4     0.3     0.1

GAT     0.2     0.2     0.4     0.4     0.1     0.2     0.4     0.4     0.1

3* $\#$9     GIN     0.2     0.05     0.05     0.1     0.2     0.05     0.2     0.05     0.05

GCN     0.05     0.2     0.2     0.05     0.2     0.1     0.05     0.2     0.05

GAT     0.2     0.2     0.2     0.05     0.05     0.2     0.05     0.05     0.05

3* $\#$10     GIN     0.2     0.3     0.3     0.7     0.7     0.3     0.4     0.2     0.5

GCN     0.9     0.8     0.8     0.6     0.8     0.4     0.9     0.5     0.2

GAT     0.4     0.6     0.6     0.9     0.2     0.4     0.9     0.6     0.2

3* $\#$11     GIN     0.2     1.0     1.0     0.9     0.1     1.0     0.4     0.0     0.4

GCN     0.2     0.7     0.7     1.0     0.7     0.8     0.2     0.8     0.7

GAT     0.4     0.3     0.8     0.2     0.7     0.4     0.2     0.5     0.0

Best configuration for [E]. Early stopping PPO patience ($\#$0), Number of environment steps ($\#$1), Number of PPO epochs ($\#$2), Environment penalty size ($\#$3), RL scheduler factor ($\#$4), Ratio of the critic learning rate ($\#$5), PPO entropy coefficient ($\#$6), PPO MSE coefficient ($\#$7), PPO clip value $\epsilon$ ($\#$8), Conformal error rate $\alpha$ ($\#$9), $d$ ($\#$10), $\lambda$ ($\#$11).

2*Param     2*Archi     9cDatasets

BZR     COX2     DD     ENZYMES     MUTAG     NCI1     NCI109     PROTEINS     PTC

3* $\#$0     GIN     15     5     5     10     10     5     15     5     5

GCN     10     5     5     15     5     15     10     15     15

GAT     15     5     5     10     15     15     10     10     5

3* $\#$1     GIN     128     128     128     128     128     128     64     64     64

GCN     32     64     64     128     64     32     32     32     128

GAT     64     32     32     32     128     64     32     32     64

3* $\#$2     GIN     10     15     15     5     15     15     10     5     15

GCN     10     15     15     5     15     3     10     5     5

GAT     10     15     15     10     5     10     10     5     5

3* $\#$3     GIN     0.5     0.5     0.5     0.5     0.5     0.5     1.5     1.5     1.0

GCN     0.5     0.5     0.5     1.0     0.5     0.5     0.5     1.5     1.5

GAT     1.5     0.5     1.5     0.5     1.5     1.5     0.5     1.0     1.5

3* $\#$4     GIN     0.99     0.95     0.95     0.99     0.9     0.95     0.9     0.9     0.95

GCN     0.99     0.95     0.95     0.99     0.95     0.99     0.99     0.9     0.9

GAT     0.9     0.95     0.99     0.99     0.9     0.9     0.99     0.95     0.9

3* $\#$5     GIN     3.0     2.5     2.5     1.0     3.0     2.5     2.5     1.0     3.0

GCN     2.5     1.5     1.5     2.0     1.5     3.0     2.5     2.5     1.5

GAT     2.5     2.0     2.5     2.5     1.5     2.5     2.5     1.0     1.0

3* $\#$6     GIN     0.001     0.0001     0.0001     0.01     0.001     0.0001     0.0001     0.001     0.0001

GCN     0.0001     0.01     0.01     0.0001     0.01     0.01     0.0001     0.01     0.001

GAT     0.0001     0.001     0.001     0.0001     0.001     0.0001     0.0001     0.001     0.001

3* $\#$7     GIN     0.5     5.0     5.0     2.0     1.0     5.0     2.0     3.0     0.5

GCN     1.0     0.5     0.5     0.1     0.5     1.0     1.0     5.0     3.0

GAT     2.0     1.0     3.0     1.0     3.0     2.0     1.0     0.1     3.0

3* $\#$8     GIN     0.2     0.4     0.4     0.1     0.2     0.4     0.2     0.1     0.4

GCN     0.4     0.3     0.3     0.3     0.3     0.1     0.4     0.3     0.1

GAT     0.2     0.2     0.4     0.4     0.1     0.2     0.4     0.4     0.1

3* $\#$9     GIN     0.2     0.05     0.05     0.1     0.2     0.05     0.2     0.05     0.05

GCN     0.05     0.2     0.2     0.05     0.2     0.1     0.05     0.2     0.05

GAT     0.2     0.2     0.2     0.05     0.05     0.2     0.05     0.05     0.05

3* $\#$10     GIN     0.2     0.3     0.3     0.7     0.7     0.3     0.4     0.2     0.5

GCN     0.9     0.8     0.8     0.6     0.8     0.4     0.9     0.5     0.2

GAT     0.4     0.6     0.6     0.9     0.2     0.4     0.9     0.6     0.2

3* $\#$11     GIN     0.2     1.0     1.0     0.9     0.1     1.0     0.4     0.0     0.4

GCN     0.2     0.7     0.7     1.0     0.7     0.8     0.2     0.8     0.7

GAT     0.4     0.3     0.8     0.2     0.7     0.4     0.2     0.5     0.0

§ EXTRA RESULTS IMPACT OF HYPERPARAMETERS

In this section, we present an ablation study on the impact of two key hyperparameters of , namely $d$ and $\lambda$, for the datasets not included in the main manuscript: , , , , and .
<ref> illustrates the results of the ablation study for parameter $d$, while the results for parameter $\lambda$ are shown in <ref>.

The findings from this ablation study are consistent with those reported in the main manuscript.
In the top row figures, we observe that the accuracy remains relatively stable when varying either $d$ or $\lambda$, improving only as the values increase for certain datasets, such as or .
In the middle row figures, we find a positive correlation between both parameters and the node/edge ratio for most of the datasets, and no correlation for others. Remarkably, the correlation is never negative.
Finally, the bottom row figures reveal a positive correlation between the node/edge ratio and accuracy for the majority of the datasets.
This pattern holds except for the  dataset, which present a negative correlation. Interestingly this dataset presents the most significant disparities in terms of the number of nodes and edges compared to the other datasets (see Table <ref>).

$d$ versus accuracy

$d$ versus sparsity

Sparsity versus accuracy

Ablation study on the maximum desired ratio $d$ for 5 different runs for the  architecture.

$\lambda$ versus accuracy

$\lambda$ versus sparsity

Sparsity versus accuracy

Ablation study on $\lambda$ for 5 different runs for the  architecture.

§ EXTRA COMPARISON RESULTS

Here, we analyze the results of how switching the base model affects the performance. <ref>  and <ref> summarizes the results for two base architectures  and . It can be observed that even when the base architecture changes our models [N] and [E] achieve competitive accuracy compared to the respective baseline and achieve top rankings in terms of node/edge ratio.

Model comparison results with  architecture. We show the mean over 5 independent runs and the standard deviation as the subindex. All metrics are shown in percentage. The last rows include the average ranking of the model across datasets.
2*Dataset     2*Metric     5cModels

GNN     SAGPool     GPool     CORES$_N$     CORES$_E$

3*BZR     Accuracy     80.98$_{4.36}$     83.90$_{3.27}$     79.51$_{6.12}$     83.90$_{4.43}$     81.46$_{4.08}$

Node Ratio     -     -     41.11$_{0.11}$     37.99$_{10.27}$     100.00$_{0.00}$

Edge Ratio     -     -     20.93$_{0.70}$     29.92$_{8.83}$     57.26$_{21.50}$

3*COX2     Accuracy     82.13$_{4.15}$     80.00$_{4.41}$     77.87$_{3.87}$     81.70$_{4.41}$     80.85$_{2.61}$

Node Ratio     -     -     50.62$_{0.09}$     77.91$_{2.29}$     100.00$_{0.00}$

Edge Ratio     -     -     20.75$_{0.51}$     62.62$_{3.24}$     66.18$_{0.38}$

3*DD     Accuracy     76.10$_{3.02}$     75.76$_{3.72}$     77.80$_{1.84}$     75.42$_{4.19}$     76.44$_{2.19}$

Node Ratio     -     -     40.24$_{0.03}$     75.16$_{1.39}$     100.00$_{0.00}$

Edge Ratio     -     -     15.63$_{0.29}$     56.42$_{2.16}$     58.62$_{2.51}$

3*ENZYMES     Accuracy     71.33$_{10.63}$     45.00$_{7.64}$     63.93$_{6.35}$     69.84$_{4.43}$     67.54$_{12.23}$

Node Ratio     -     -     96.67$_{0.14}$     80.26$_{1.03}$     100.00$_{0.00}$

Edge Ratio     -     -     93.27$_{0.23}$     65.92$_{1.80}$     61.60$_{9.06}$

3*MUTAG     Accuracy     81.43$_{6.39}$     88.57$_{3.91}$     78.57$_{7.14}$     80.00$_{5.98}$     81.43$_{6.02}$

Node Ratio     -     -     97.81$_{0.36}$     75.72$_{4.04}$     100.00$_{0.00}$

Edge Ratio     -     -     95.65$_{2.50}$     58.74$_{6.05}$     55.25$_{14.77}$

3*NCI1     Accuracy     79.42$_{1.34}$     68.93$_{1.37}$     72.43$_{2.11}$     73.43$_{2.67}$     75.38$_{1.22}$

Node Ratio     -     -     96.89$_{0.08}$     63.49$_{3.58}$     100.00$_{0.00}$

Edge Ratio     -     -     94.07$_{0.34}$     53.33$_{2.81}$     88.68$_{6.67}$

3*NCI109     Accuracy     76.90$_{1.34}$     67.46$_{4.31}$     67.22$_{3.25}$     74.72$_{2.25}$     72.78$_{2.29}$

Node Ratio     -     -     96.79$_{0.04}$     71.55$_{11.30}$     100.00$_{0.00}$

Edge Ratio     -     -     94.70$_{0.98}$     62.37$_{12.96}$     61.37$_{13.13}$

3*PROTEINS     Accuracy     75.36$_{3.00}$     72.68$_{3.26}$     73.21$_{3.22}$     73.39$_{3.86}$     73.57$_{1.62}$

Node Ratio     -     -     51.15$_{0.17}$     67.94$_{2.97}$     100.00$_{0.00}$

Edge Ratio     -     -     28.39$_{0.42}$     46.56$_{4.27}$     52.82$_{1.86}$

3*PTC     Accuracy     64.00$_{4.33}$     65.00$_{6.39}$     62.44$_{4.12}$     62.96$_{4.17}$     59.43$_{4.69}$

Node Ratio     -     -     52.46$_{0.41}$     45.61$_{6.00}$     100.00$_{0.00}$

Edge Ratio     -     -     36.58$_{3.53}$     21.24$_{6.53}$     76.36$_{14.75}$

3*Avg. Rank     Accuracy     1.89     3.33     3.89     3.00     2.89

Node Ratio     -     -     1.67     1.33     -

Edge Ratio     -     -     2.33     1.56     2.11

Model comparison results with  architecture We show the mean over 5 independent runs and the standard deviation as the subindex. All metrics are shown in percentage. The last rows include the average ranking of the model across datasets.

2*Dataset     2*Metric     5cModels

GNN     SAGPool     GPool     CORES$_N$     CORES$_E$

3*BZR     Accuracy     86.83$_{4.08}$     83.41$_{4.69}$     84.39$_{4.08}$     82.44$_{4.69}$     80.98$_{5.29}$

Node Ratio     -     -     96.46$_{0.19}$     76.98$_{6.06}$     100.00$_{0.00}$

Edge Ratio     -     -     92.87$_{0.58}$     61.17$_{11.31}$     46.16$_{5.68}$

3*COX2     Accuracy     79.15$_{4.85}$     80.43$_{3.81}$     80.00$_{1.90}$     80.85$_{3.01}$     81.70$_{4.90}$

Node Ratio     -     -     96.14$_{0.18}$     72.49$_{4.24}$     100.00$_{0.00}$

Edge Ratio     -     -     92.67$_{0.71}$     53.19$_{8.07}$     31.27$_{23.60}$

3*DD     Accuracy     78.47$_{3.47}$     75.93$_{4.39}$     76.10$_{5.06}$     79.32$_{2.58}$     75.76$_{4.05}$

Node Ratio     -     -     40.23$_{0.03}$     56.44$_{2.50}$     100.00$_{0.00}$

Edge Ratio     -     -     16.48$_{0.13}$     32.01$_{2.89}$     51.39$_{1.90}$

3*ENZYMES     Accuracy     66.00$_{5.35}$     52.00$_{5.70}$     64.59$_{4.86}$     58.31$_{8.47}$     57.02$_{11.62}$

Node Ratio     -     -     96.67$_{0.14}$     77.17$_{7.28}$     100.00$_{0.00}$

Edge Ratio     -     -     93.39$_{0.35}$     62.33$_{9.26}$     74.20$_{35.99}$

3*MUTAG     Accuracy     81.43$_{3.91}$     80.00$_{3.19}$     78.57$_{5.05}$     81.43$_{10.83}$     87.14$_{6.56}$

Node Ratio     -     -     73.13$_{0.55}$     79.94$_{2.79}$     100.00$_{0.00}$

Edge Ratio     -     -     68.22$_{2.47}$     63.52$_{4.23}$     32.66$_{8.79}$

3*NCI1     Accuracy     77.33$_{2.09}$     73.58$_{1.64}$     72.14$_{2.64}$      66.45$_{7.71}$     65.94$_{6.31}$

Node Ratio     -     -     96.89$_{0.08}$     76.47$_{17.88}$     100.00$_{0.00}$

Edge Ratio     -     -     96.06$_{0.20}$     64.02$_{18.84}$     37.98$_{14.34}$

3*NCI109     Accuracy     79.32$_{1.57}$     71.19$_{2.03}$     71.53$_{2.12}$     76.08$_{2.71}$     77.14$_{2.02}$

Node Ratio     -     -     96.79$_{0.04}$     78.78$_{4.15}$     100.00$_{0.00}$

Edge Ratio     -     -     95.82$_{0.11}$     67.08$_{4.42}$     92.02$_{1.93}$

3*PROTEINS     Accuracy     72.86$_{1.02}$     72.86$_{3.13}$     75.18$_{2.75}$     73.21$_{2.45}$     75.89$_{1.94}$

Node Ratio     -     -     51.15$_{0.17}$     74.66$_{6.10}$     100.00$_{0.00}$

Edge Ratio     -     -     28.15$_{0.67}$     56.12$_{9.77}$     64.73$_{0.98}$

3*PTC     Accuracy     57.78$_{7.71}$     64.57$_{3.83}$     63.43$_{1.28}$     62.86$_{2.86}$     63.43$_{3.13}$

Node Ratio     -     -     83.80$_{0.74}$     64.10$_{4.19}$     100.00$_{0.00}$

Edge Ratio     -     -     78.21$_{3.76}$     40.21$_{6.93}$     44.47$_{5.29}$

3*Avg. Rank     Accuracy     1.89     3.33     3.89     3.00     2.89

Node Ratio     -     -     1.67     1.33     -

Edge Ratio     -     -      2.56     1.67     1.78

§ TIME COMPLEXITY

We analyze the training and inference times of all models on each dataset. We run each model on every dataset for a single epoch, utilizing a batch size of one. To ensure statistical significance and reliability in our measurements, we repeat each experiment ten times. This repetition enables us to calculate the average training and inference times accurately. Such a meticulous approach guarantees robust and precise performance assessment for our models across the diverse set of datasets under examination.

<ref> and <ref> show the complete results for the training and inferences times, respectively.
If we focus on <ref>, we observe the models that only rely on a single forward pass are two orders of magnitude faster than the models that rely on a reinforcement learning-based approach. Still, we observe that  achieves comparable speed as , and sometimes it is faster, e.g., with  or .
In terms of inference time, in <ref>, we can observe that even though  is still one order of magnitude slower than the Full Models, it is considerably faster than .

Training time comparison. We show the average training time in seconds along with the standard deviation of each model on each dataset for one epoch with a batch size of one. We use the  GNN architecture.

Dataset     2cFull Models     4cSparse Models

(lr)2 - 3 (lr)4 - 7
[N]       [E]

2.64 $_{0.18}$     4.23 $_{0.12}$     -     3.44 $_{0.27}$     186.96 $_{61.70}$     121.94 $_{2.00}$

3.07 $_{0.15}$     4.83 $_{0.17}$     -     10.00 $_{2.70}$     411.93 $_{85.97}$     203.93 $_{1.86}$

6.13 $_{0.13}$     -     -     33.31 $_{4.90}$     1848.21 $_{1.12}$     1857.59 $_{1.13}$

2.40 $_{0.04}$     6.26 $_{0.31}$     132.86 $_{3.77}$     6.08 $_{0.30}$     233.78 $_{6.65}$     287.95 $_{2.20}$

1.09 $_{0.03}$     1.63 $_{0.04}$     47.82 $_{3.45}$     1.71 $_{0.19}$     24.97 $_{1.55}$     22.94 $_{0.30}$

15.44 $_{0.19}$     41.74 $_{3.03}$     1143.85 $_{45.27}$     48.05 $_{8.12}$     1596.95 $_{107.83}$     1826.41 $_{51.06}$

16.68 $_{1.15}$     43.73 $_{0.44}$     1195.10 $_{47.42}$     43.46 $_{3.09}$     1533.59 $_{15.51}$     1756.84 $_{37.12}$

5.80 $_{0.23}$     11.79 $_{1.19}$     511.21 $_{22.63}$     13.58 $_{2.58}$     484.97 $_{14.74}$     505.89 $_{2.70}$

1.68 $_{0.16}$     3.00 $_{0.07}$     95.78 $_{1.47}$     3.28 $_{0.18}$     64.60 $_{1.23}$     67.19 $_{0.32}$

Inference time comparison. We show the average inference time in seconds along with the standard deviation of each model on each dataset. We use the  GNN architecture.

Dataset     2cFull Models     4cSparse Models

(lr)2 - 3 (lr)4 - 7
[N]       [E]

0.0025 $_{0.0001}$     0.1447 $_{0.0048}$     -     0.0045 $_{0.0003}$     0.0540 $_{0.0257}$     0.0425 $_{0.0011}$

0.0026 $_{0.0001}$     0.1550 $_{0.0093}$     -     0.0062 $_{0.0008}$     0.1031 $_{0.0349}$     0.0526 $_{0.0014}$

0.0028 $_{0.0004}$     -     -     0.0085 $_{0.0006}$     0.2262 $_{0.0842}$     0.1206 $_{0.0016}$

0.0024 $_{0.0000}$     0.1992 $_{0.0080}$     0.1399 $_{0.0094}$     0.0063 $_{0.0007}$     0.0496 $_{0.0014}$     0.0625 $_{0.0019}$

0.0029 $_{0.0001}$     0.0596 $_{0.0034}$     0.0135 $_{0.0036}$     0.0065 $_{0.0017}$     0.0448 $_{0.0056}$     0.0415 $_{0.0012}$

0.0022 $_{0.0001}$     1.3756 $_{0.1246}$     1.0187 $_{0.1040}$     0.0058 $_{0.0004}$     0.0530 $_{0.0026}$     0.1301 $_{0.0602}$

0.0023 $_{0.0001}$     1.3685 $_{0.0988}$     0.9477 $_{0.0132}$     0.0055 $_{0.0002}$     0.0500 $_{0.0006}$     0.0563 $_{0.0009}$

0.0025 $_{0.0001}$     0.3835 $_{0.0619}$     3.9375 $_{0.0347}$     0.0058 $_{0.0007}$     0.0437 $_{0.0016}$     0.0439 $_{0.0008}$

0.0028 $_{0.0001}$     0.1076 $_{0.0050}$     0.0398 $_{0.0099}$     0.0058 $_{0.0005}$     0.0395 $_{0.0013}$     0.0418 $_{0.0005}$