Open Problems

Graph Neural Networks & Node Classification

Architecture-Agnostic Black-Box Explanation for Graph Neural Networks

Barrier to removePartly addressed
Possible candidate · 2/5 runs3 papers report this0% from 2025+

Generated automatically from the limitations stated in 3 papers (NeurIPS, ICML), listed under Evidence. It is not a paper, and it does not come from papers submitted to CSPaper.

The problem

Many current GNN explainers require differentiable access to intermediate node embeddings, meaning they cannot operate under true black-box conditions such as inference-only APIs or proprietary model deployments. Because these methods are tied to specific encoder representations, their explanations fail to generalize across diverse GNN architectures and degrade when underlying embeddings are noisy or poorly calibrated. Practitioners with black-box access to graph classification services are currently blocked from generating post-hoc explanations without access to internal model parameters and activations.

Why it matters

Enables trustworthy post-hoc explanations for closed-source, proprietary, or heterogeneous GNN prediction pipelines where internal embeddings and gradients are strictly unavailable.

Ways to approach it

Prior-work checks are free with an account. Results someone already ran are shown to everyone.

  1. 1

    Conduct a cross-architecture benchmark evaluating existing perturbation- and search-based explainers strictly through input-output queries (without intermediate embedding access) across multiple GNN backbones (e.g., GCN, GAT, GIN, GraphSAGE), measuring explanation fidelity, sparsity, and query complexity.

  2. 2

    Develop a black-box subgraph attribution method driven purely by output prediction probabilities via discrete sampling or zeroth-order optimization, measuring its stability and explanation accuracy against white-box baselines across diverse node classification tasks.

Have a different approach?

Describe how you would tackle this problem and we'll look for papers that already do it. Free; your text stays private.

Free · 3 checks per day

Why it might fail

The query sample complexity required to obtain high-fidelity subgraph explanations without gradient guidance could be prohibitively high for large-scale graphs, rendering strictly black-box approaches computationally intractable in practice.

Evidence

Each paper's own statement of the limitation, verbatim.

Nearest existing work

Generated automatically, not curated by hand. Automated prior-work checks catch about a third of existing work, so treat this problem as a lead to investigate.