Graph Neural Networks (GNNs) are powerful, but like many deep learning models, they often operate as "black boxes." To trust them in critical fields like drug discovery or social network analysis, we need explainers—tools that identify the specific subgraph most responsible for a model's prediction.
However, real-world data is rarely perfect. Graphs often contain "structural corruption," such as random noise or malicious adversarial attacks. A new paper introduces V-InFoR, a robust GNN explainer designed to provide reliable insights even when the input graphs are structurally compromised.
TL;DR
V-InFoR is a novel GNN explanation framework that remains accurate even when graphs are noisy or under adversarial attack. It combines variational inference to filter out minor structural noise with a Graph Information Bottleneck (GIB) approach to adaptively identify irregular, severe corruptions that change model predictions.
What Problem Does This Paper Address?
Existing GNN explainers (like GNNExplainer or PGExplainer) have a "fragility" problem. They typically assume the input graph is clean. When a graph is structurally corrupted—meaning edges are added or removed—these explainers often fail for two main reasons:
- Overfitting to Noise: They rely on raw features or latent representations that are easily swayed by "minor" corruptions (noise that doesn't change the final prediction).
- Rigid Constraints: Many explainers use strict rules, such as forcing the explanation to be a specific size or a single connected component. However, "severe" corruptions (attacks that actually change the model's prediction) are often irregular and disconnected, making these rigid rules counterproductive.
The authors argue that a robust explainer must filter out minor noise while identifying severe corruption as a key part of the explanation, since that severe corruption is the reason the model's output changed.
Methods
V-InFoR tackles these challenges through two main modules designed to handle both minor and severe graph corruptions.
1. Robust Graph Representation Extractor
Instead of looking at a single, potentially corrupted graph representation, V-InFoR uses Variational Inference. It treats graph representations as samples from a latent distribution (defined by a mean and standard deviation). By modeling the statistical characteristics shared across many graphs, the model can "smooth out" minor, random structural noise. This ensures the downstream explainer receives a cleaner, more generalized signal.
2. Adaptive Explanation Generator
To handle the irregular nature of severe corruptions, the authors move away from rigid structural constraints. Instead, they formulate the search for an explanation as a Graph Information Bottleneck (GIB) optimization problem.
- The Goal: Find a subgraph that is "minimal" (discards redundant info) but "sufficient" (retains enough info to explain the prediction).
- The Technique: They use a continuous relaxation of the discrete graph structure (via the Concrete distribution) to make this bottleneck objective differentiable and easy to optimize.
Datasets and Key Results
The researchers evaluated V-InFoR against six state-of-the-art baselines using both synthetic and real-world benchmarks, including BA-3Motifs (synthetic motifs), Mutag (molecules), Ogbg-molhiv, and Ogbg-ppa. To test robustness, they injected 20% random structural noise and performed adversarial attacks using the GRABNEL algorithm.
V-InFoR consistently outperformed all baselines in terms of the $F_{NS}$ score (a metric balancing how "sufficient" and "necessary" an explanation is).
- Noise Robustness: On the Mutag dataset with 20% random noise, V-InFoR improved the explanation performance by 29.23% over the best baseline.
- Attack Robustness: Under a 10% adversarial attack budget on the BA-3Motifs dataset, V-InFoR achieved a performance gain of 13.96%.
- Qualitative Success: Visualizations showed that while other explainers got "distracted" by noisy edges, V-InFoR successfully ignored them and highlighted the true underlying motifs (like "house" or "cycle" structures).
Key Insights and Future Work
- Minor vs. Severe Corruption: The paper provides a useful framework for thinking about noise. If the GNN's prediction stays the same, the noise is "minor" and should be ignored. If the prediction changes, the corruption is "severe" and must be part of the explanation.
- Information Bottleneck > Rigid Rules: By optimizing for information flow rather than subgraph size or connectivity, the explainer can adapt to the weird, disconnected shapes that adversarial attacks often take.
While V-InFoR is a major step forward for structural robustness, the authors note a few areas for improvement. The current model focuses on structural (edge) corruption and does not yet account for noise on node features. Furthermore, extending V-InFoR from graph classification to node classification and link prediction tasks remains a necessary next step.
Summary updated