一句话：提出图描述语言 GDL 和基于程序合成的可解释图学习模型 PL4XGL，用 GDL 程序解释分类结果。
图神经网络在图学习任务上表现优异，但可解释性不足，限制其在关键决策中的应用。现有后验解释方法虽能生成子图解释，却存在额外解释开销和解释正确性问题。本文提出基于编程语言技术的可解释图学习方法：设计图描述语言 GDL 解释分类结果，并构建基于 GDL 的可解释分类模型 PL4XGL 替代 GNN 模型。PL4XGL 由带标签和质量分数的候选 GDL 程序组成；给定图组件，它搜索最佳 GDL 程序，并以对应标签为分类结果、程序为解释。本文将数据学习建模为程序合成问题，提出自顶向下和自底向上算法从训练数据合成 GDL 程序。在常用数据集上，PL4XGL 的解释质量优于先进方法 SubgraphX，分类准确率与主流 GNN 相当。
In this article, we present a new, language-based approach to explainable graph learning. Though graph neural networks (GNNs) have shown impressive performance in various graph learning tasks, they have severe limitations in explainability, hindering their use in decision-critical applications. To address these limitations, several GNN explanation techniques have been proposed using a post-hoc explanation approach providing subgraphs as explanations for classification results. Unfortunately, however, they have two fundamental drawbacks in terms of 1) additional explanation costs and 2) the correctness of the explanations. This paper aims to address these problems by developing a new graph-learning method based on programming language techniques. Our key idea is two-fold: 1) designing a graph description language (GDL) to explain the classification results and 2) developing a new GDL-based interpretable classification model instead of GNN-based models. Our graph-learning model, called PL4XGL, consists of a set of candidate GDL programs with labels and quality scores. For a given graph component, it searches the best GDL program describing the component and provides the corresponding label as the classification result and the program as the explanation. In our approach, learning from data is formulated as a program-synthesis problem, and we present top-down and bottom-up algorithms for synthesizing GDL programs from training data. Evaluation using widely-used datasets demonstrates that PL4XGL produces high-quality explanations that outperform those produced by the state-of-the-art GNN explanation technique, S ubgraph X. We also show that PL4XGL achieves competitive classification accuracy comparable to popular GNN models.
@article{JeonPO24,
title = {PL4XGL: A Programming Language Approach to Explainable Graph Learning},
author = {Minseok Jeon and Jihyeok Park and Hakjoo Oh},
journal = {Proceedings of the ACM on Programming Languages},
volume = {8},
number = {PLDI},
year = {2024},
doi = {10.1145/3656464}
}