# Interpreting Graph Inference with Skyline Explanations

arXiv: https://arxiv.org/abs/2505.07635 · HTML: https://mlsanity.com/paper/2505.07635/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 31 of its 84 references that are in the map.
- First posted on arXiv 12 May 2025.

## Builds on (most cited first, 30 of 31)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [Pitfalls of Graph Neural Network Evaluation](https://mlsanity.com/paper/1811.05868/) (2018)
- [GNNExplainer: Generating Explanations for Graph Neural Networks](https://mlsanity.com/paper/1903.03894/) (2019)
- [Graph Neural Networks for Social Recommendation](https://mlsanity.com/paper/1902.07243/) (2019)
- [Explaining Machine Learning Classifiers through Diverse Counterfactual Explanations](https://mlsanity.com/paper/1905.07697/) (2019)
- [Multi-scale Attributed Node Embedding](https://mlsanity.com/paper/1909.13021/) (2019)
- [Parameterized Explainer for Graph Neural Network](https://mlsanity.com/paper/2011.04573/) (2020)
- [Explainability in Graph Neural Networks: A Taxonomic Survey](https://mlsanity.com/paper/2012.15445/) (2020)
- [Graph Convolutional Policy Network for Goal-Directed Molecular Graph Generation](https://mlsanity.com/paper/1806.02473/) (2018)
- [On Explainability of Graph Neural Networks via Subgraph Explorations](https://mlsanity.com/paper/2102.05152/) (2021)
- [Interpretable and Generalizable Graph Learning via Stochastic Attention Mechanism](https://mlsanity.com/paper/2201.12987/) (2022)
- [Interpreting Graph Neural Networks for NLP With Differentiable Edge Masking](https://mlsanity.com/paper/2010.00577/) (2020)
- [CF-GNNExplainer: Counterfactual Explanations for Graph Neural Networks](https://mlsanity.com/paper/2102.03322/) (2021)
- [Scalable Graph Neural Networks via Bidirectional Propagation](https://mlsanity.com/paper/2010.15421/) (2020)
- [Learning and Evaluating Graph Neural Network Explanations based on Counterfactual and Factual Reasoning](https://mlsanity.com/paper/2202.08816/) (2022)
- [Diversity in Machine Learning](https://mlsanity.com/paper/1807.01477/) (2018)
- [GStarX: Explaining Graph Neural Networks with Structure-Aware Cooperative Games](https://mlsanity.com/paper/2201.12380/) (2022)
- [Multi-agent Dynamic Algorithm Configuration](https://mlsanity.com/paper/2210.06835/) (2022)
- [A survey on multi-objective hyperparameter optimization algorithms for Machine Learning](https://mlsanity.com/paper/2111.13755/) (2021)
- [Interpretable Prototype-based Graph Information Bottleneck](https://mlsanity.com/paper/2310.19906/) (2023)
- [Demystifying Fraudulent Transactions and Illicit Nodes in the Bitcoin Network for Financial Forensics](https://mlsanity.com/paper/2306.06108/) (2023)
- [Illuminati: Towards Explaining Graph Neural Networks for Cybersecurity Analysis](https://mlsanity.com/paper/2303.14836/) (2023)
- [Multi-objective Explanations of GNN Predictions](https://mlsanity.com/paper/2111.14651/) (2021)
- [View-based Explanations for Graph Neural Networks](https://mlsanity.com/paper/2401.02086/) (2024)
- [The Shape of Money Laundering: Subgraph Representation Learning on the Blockchain with the Elliptic2 Dataset](https://mlsanity.com/paper/2404.19109/) (2024)
- [Evolve Path Tracer: Early Detection of Malicious Addresses in Cryptocurrency](https://mlsanity.com/paper/2301.05412/) (2023)

## Abstract (arXiv)

Inference queries have been routinely issued to graph machine learning models such as graph neural networks (GNNs) for various network analytical tasks. Nevertheless, GNN outputs are often hard to interpret comprehensively. Existing methods typically conform to individual pre-defined explainability measures (such as fidelity), which often leads to biased, ``one-side'' interpretations. This paper introduces skyline explanation, a new paradigm that interprets GNN outputs 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.