Gnnx Bench Eval

gnnx-bench-eval

GNNX-BENCH: Unravelling the Utility of Perturbation-based GNN Explainers through In-depth Benchmarking — Kosan et al. (2023) (arXiv:2310.01794, 2023)

What this evaluates

Evaluates the quality, robustness, and feasibility of perturbation-based GNN explainers. It probes whether generated subgraphs (factual or counterfactual) reliably preserve or flip model predictions, remain stable under topological or architectural perturbations, and satisfy domain-specific structural constraints.

Datasets

• Mutagenicity — total 4337; splits: test (-1)
• Proteins — total 1113; splits: test (-1)
• IMDB-B — total 1000; splits: test (-1)
• AIDS — total 2000; splits: test (-1)
• MUTAG — total 188; splits: test (-1)
• NCI1 — total 4110; splits: test (-1)
• Graph-SST2 — total 70042; splits: test (-1)
• DD — total 1178; splits: test (-1)
• REDDIT-B — total 2000; splits: test (-1)
• ogbg-molhiv — total 41127; splits: test (-1)
• Tree-Cycles — total 1; splits: test (-1)
• Tree-Grid — total 1; splits: test (-1)
• BA-Shapes — total 1; splits: test (-1)

Metrics

• Sufficiency (primary) — range: [0, 1]
  • Ratio of graphs where the prediction from the explanation subgraph matches the prediction from the complete graph. Value spans [0, 1]. Higher is better for factual explanations; lower is better for counterfactual explanations (objective is to flip the class label).
• Stability — range: [0, 1]
  • Jaccard similarity between the set of edges in the original explanation and the set of edges after introducing variations (topological perturbations, different random seeds, or architecture changes). Value spans [0, 1].
• Necessity — range: [0, 1]
  • Accuracy of the model when the explanation subgraph is removed from the original graph, measuring whether the label flips to the counterfactual class.
• Reproducibility+ — range: [0, 1]
  • Accuracy of a GNN retrained exclusively on the explanation subgraphs, measuring if the original predictions can be retained.
• Reproducibility- — range: [0, 1]
  • Accuracy of a GNN retrained on the residual graph (original graph minus the explanation), measuring if the class label is preserved.
• Feasibility — range: [0, 1]
  • Binary or percentage metric indicating whether the generated counterfactual explanation adheres to domain-specific topological constraints (e.g., valid molecular structures, consistently connected graphs).
• Explanation Size — range: other
  • Count of edges or nodes in the generated explanation subgraph. Used alongside sufficiency to quantify performance trade-offs.

Input / output format

Input: Graph structures (nodes, edges, node features) and the trained GNN model to be explained.

Output: A subgraph (set of edges/nodes) representing the explanation, or a counterfactual graph modification that flips the prediction.

Scoring recipe

def compute_sufficiency(explanation_edges, original_graph, gnn_model):
    pred_full = gnn_model(original_graph)
    pred_expl = gnn_model(subgraph(original_graph, explanation_edges))
    return (pred_full == pred_expl).mean()

def compute_stability(orig_edges, perturbed_edges):
    intersection = len(set(orig_edges) & set(perturbed_edges))
    union = len(set(orig_edges) | set(perturbed_edges))
    return intersection / union if union > 0 else 0.0

def compute_necessity(explanation_edges, original_graph, gnn_model):
    residual_graph = remove_subgraph(original_graph, explanation_edges)
    return (gnn_model(residual_graph) != gnn_model(original_graph)).mean()

Common pitfalls

• Confusing the directionality of Sufficiency: higher values indicate better performance for factual explanations, but lower values are better for counterfactual explanations since the goal is to flip the class label.
• Ignoring domain-specific topological constraints when evaluating Feasibility, leading to counterfactuals that are structurally invalid for the target domain (e.g., invalid molecules or disconnected graphs).
• Overlooking stochasticity from random seeds when measuring Stability, as perturbation-based explainers optimize non-convex loss functions and can produce dissimilar explanations across runs on the same model.

Evidence (verbatim from paper)

The performance is quantified using explanation size and sufficiency. Sufficiency encodes the ratio of graphs for which the prediction derived from the explanation matches the prediction obtained from the complete graph. Its value spans between 0 and 1. For factual explanations, higher values indicate superior performance, while in counterfactual lower is better since the objective is to flip the class label. Stability is quantified by taking the Jaccard similarity between the set of edges in the original explanation vs. those obtained after introducing the variation.

Citation

@misc{kosan2023gnnxbench,
  title={GNNX-BENCH: Unravelling the Utility of Perturbation-based GNN Explainers through In-depth Benchmarking},
  author={Kosan et al. (2023)},
  year={2023},
  note={arXiv:2310.01794}
}

• arXiv: 2310.01794