Abstract: Graph Neural Networks (GNNs) have achieved state-of-the-art performance in solving graph classification tasks. However, most GNN architectures aggregate information from all nodes and edges in a graph, regardless of their relevance to the task at hand, thus hindering the interpretability of their predictions. In contrast to prior work, in this paper we propose a GNN training approach that jointly i) finds the most predictive subgraph by removing edges and/or nodes — without making assumptions about the subgraph structure — while ii) optimizing the performance of the graph classification task. To that end, we rely on reinforcement learning to solve the resulting bi-level optimization with a reward function based on conformal predictions to account for the current in-training uncertainty of the classifier. Our empirical results on nine different graph classification datasets show that our method competes in performance with baselines while relying on significantly sparser subgraphs, leading to more interpretable GNN-based predictions.
Introduction
Graph Neural Networks (GNNs) are the gold standard for analyzing everything from social networks to molecular structures. However, they suffer from a "black box" problem: because they aggregate information from every node and edge in a graph, it’s nearly impossible for a human to tell which specific features actually drove a prediction.
The core challenge in GNN interpretability is faithfulness. Many existing methods are "post-hoc," meaning they try to explain a pre-trained model's behavior. However, if a model was trained on a full graph, a post-hoc explanation highlighting a small subgraph might not actually represent how the model made its decision. Furthermore, existing "hard removal" methods often make rigid assumptions, such as requiring the resulting subgraph to be a specific size. This doesn't work well in the real world, where the "important" part of a molecule or social network varies in size and structure. The authors aim to find the most predictive subgraph without these restrictive priors.
Methodology: The CORES Framework
The authors propose CORES (Conformal-based reinforcement learning for graph sparsification), which uses a bi-level iterative optimization approach to jointly optimize accuracy and sparsity.
- Inner Loop (Performance): Trains a graph classifier ($\theta$) to minimize prediction loss using only the subgraphs provided by the policy.
- Outer Loop (Sparsity): Trains a sparsification policy ($\phi$) using Proximal Policy Optimization (PPO). This policy decides which nodes or edges to remove.
Conformal Rewards
The most innovative part of CORES is its reward function. Instead of a simple "correct/incorrect" reward, it uses Conformal Prediction to quantify the classifier's uncertainty. The reward function ($R$) is split into three scenarios:
- Correct & Certain: If the model is right and confident (prediction set size = 1), it gets a high reward for being both accurate and sparse.
- Correct but Uncertain: If the model is right but hesitant (prediction set size > 1), the reward is reduced to encourage the model to find a more "certain" subgraph.
- Incorrect: If the model is wrong, it receives a negative reward proportional to how much it pruned, effectively telling the RL agent: "You pruned too much; go back and look at the original graph."
Experimental Results
The researchers evaluated CORES across nine diverse graph classification datasets, primarily from the bioinformatics and chemical domains (e.g., MUTAG, ENZYMES, BZR, PTC).
CORES demonstrates that you don't have to sacrifice much accuracy to get a massive boost in interpretability:
- Competitive Accuracy: Across most datasets, CORES achieved competitive accuracy, often outperforming other "sparse" baselines like SUGAR or GPool and staying within a few percentage points of "full" GNN models.
- Massive Sparsity: In the MUTAG dataset (predicting mutagenicity), CORES found predictive subgraphs using as little as 20% of the original nodes/edges.
- Uncertainty-Aware Pruning: Using conformal prediction allows the RL agent to adapt its pruning strategy based on the classifier's current state of learning. It prunes only when it doesn't hurt the model's confidence.
- Qualitative Success: On MUTAG, the model successfully identified known chemical motifs (like $NO_2$ groups) as the primary drivers for mutagenic predictions, aligning perfectly with established chemical knowledge.
Conclusion and Future Work
The primary drawback of CORES is computational overhead. Because it relies on Reinforcement Learning and bi-level optimization, training and inference are significantly slower than standard GNNs—sometimes up to 10x slower during inference compared to "full" models.
Future directions suggested by the authors include improving the efficiency of the RL component, modifying the reward function to penalize specific undesirable structures (like creating isolated nodes), and expanding the framework to handle graph regression tasks and node-level classification.
Summary updated