Generating Skyline Explanations for Graph Neural Networks

Dazhuo Qiu, Haolai Che, Arijit Khan, Yinghui Wu

Abstract

Inference queries have been routinely issued to graph machine learning models such as graph neural networks (GNNs) for various network analytical tasks. Nevertheless, GNNs outputs are often hard to interpret comprehensively. Existing methods typically compromise to individual pre-defined explainability measures (such as fidelity), which often leads to biased, “one-sided” interpretations. This paper introduces skyline explanation, a new paradigm that interprets GNN output by simultaneously optimizing multiple explainability measures of users' interests. (1) We propose skyline explanations as a Pareto set of explanatory subgraphs that dominate others over multiple explanatory measures. We formulate skyline explanation as a multi-criteria optimization problem, and establish its hardness results. (2) We design efficient algorithms with an onion-peeling approach, which strategically prioritizes nodes and removes unpromising edges to incrementally assemble skyline explanations. (3) We also develop an algorithm to diversify the skyline explanations to enrich the comprehensive interpretation. (4) We introduce efficient parallel algorithms with load-balancing strategies to scale skyline explanation for large-scale GNN-based inference. Using real-world and synthetic graphs, we experimentally verify our algorithms' effectiveness and scalability.

Introduction

Graph Neural Networks (GNNs) have become essential for complex network analysis tasks, such as detecting financial fraud or predicting molecular properties. However, their internal logic remains opaque. When a GNN classifies a Bitcoin transaction as "illicit," human analysts require a clear explanation of why that decision was made. Traditionally, explainability methods have focused on finding a single "best" subgraph that optimizes a specific metric, such as conciseness or fidelity.

The Problem with One-Sided Explanations

Existing GNN explainers typically optimize for a single pre-defined metric. For instance, one might look for the smallest possible subgraph that preserves the model's prediction (conciseness), while another looks for the edges whose removal would most change the prediction (counterfactuality).

The challenge is that these metrics often conflict. A highly concise explanation might omit critical context, while a highly faithful one might be too complex for human interpretation. By forcing an optimization toward a single goal, current methods provide biased, "one-sided" interpretations. The authors argue that users shouldn't have to choose a single metric upfront; instead, they should see the "Skyline"—the set of all explanations that aren't strictly worse than any other across multiple criteria.

Comparison of single-objective explanations versus the multi-objective Skyline approach.

As illustrated above, optimizing for a single objective like "Factuality" or "Counterfactuality" yields different subgraphs. The Skyline Explanation paradigm instead identifies a set of Pareto-optimal subgraphs where no explanation is strictly dominated by another across all chosen criteria.

Methodology: Multi-Criteria Optimization

The authors frame GNN explanation as a multi-criteria optimization problem. Given the NP-hard nature of finding the exact Skyline, they introduce several algorithmic innovations:

  • Skyline Explanatory Query (SXQ): A framework that returns a set of subgraphs dominating others across user-defined measures like fidelity+, fidelity-, and conciseness.
  • Onion Peeling (ASX-OP): A top-down approach that starts with the full local neighborhood and strategically "peels" away edges. This is particularly effective for identifying counterfactual explanations.
  • Edge Growing (ASX-I): A bottom-up alternative that starts with the target node and adds edges, ideal for finding factual evidence quickly.
  • Diversified Skyline (DSX): An algorithm designed to ensure the returned set of explanations is not redundant, offering a broader variety of insights.
  • ParaSX: A parallelized version for massive workloads, utilizing workload clustering and influential node prioritization to scale to graphs with billions of edges.

Experimental Evaluation

The researchers evaluated their methods on seven datasets, including citation networks (Cora, PubMed, OGBN_arxiv), social/product networks (FacebookPage, AmazonComputer), and synthetic benchmarks (BA_Shapes, Tree_Cycles).

Key Results

  • Superior Quality: Using the Integrated Preference Function (IPF), the ASX-OP method outperformed state-of-the-art explainers like GNNExplainer and PGExplainer by up to 2.8x on the Cora dataset.
  • Comprehensive Coverage: Qualitative analysis demonstrated that Skyline explanations span the interpretable space, offering diverse reasons for a prediction (e.g., identifying an illicit Bitcoin user based on both transaction frequency and high-value neighbors).
  • Scalability: The ParaSX algorithm achieved an 8.2x speedup over baseline explainers on the million-edge OGBN_arxiv graph and successfully processed a synthetic graph with 6 billion edges.

Conclusion and Future Work

The Skyline paradigm represents a shift from finding a single "correct" explanation to providing a holistic view of GNN logic. While the framework is powerful, it currently requires users to select relevant metrics and relies on approximation algorithms due to the problem's complexity. Future research may explore "global" explanations for entire models and more complex graph editing operations beyond edge removal.

Summary updated

Abstract

Inference queries have been routinely issued to graph machine learning models such as graph neural networks (GNNs) for various network analytical tasks. Nevertheless, GNNs outputs are often hard to interpret comprehensively. Existing methods typically compromise to individual pre-defined explainability measures (such as fidelity), which often leads to biased, ``one-sided'' interpretations. This paper introduces skyline explanation, a new paradigm that interprets GNN output by simultaneously optimizing multiple explainability measures of users' interests. (1) We propose skyline explanations as a Pareto set of explanatory subgraphs that dominate others over multiple explanatory measures. We formulate skyline explanation as a multi-criteria optimization problem, and establish its hardness results. (2) We design efficient algorithms with an onion-peeling approach, which strategically prioritizes nodes and removes unpromising edges to incrementally assemble skyline explanations. (3) We also develop an algorithm to diversify the skyline explanations to enrich the comprehensive interpretation. (4) We introduce efficient parallel algorithms with load-balancing strategies to scale skyline explanation for large-scale GNN-based inference. Using real-world and synthetic graphs, we experimentally verify our algorithms' effectiveness and scalability.
BibTeX
@misc{qiu2025generating,
  author = {Dazhuo Qiu and Haolai Che and Arijit Khan and Yinghui Wu},
  title = {{Generating Skyline Explanations for Graph Neural Networks}},
  year = {2025},
  eprint = {2505.07635},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2505.07635},
}
Figure