From Abductive Explanations to Global Logical Rules for Node Classification in SGCs

• Bryan Lima Cavalcante IFCE
• Thiago Alves Rocha IFCE

DOI: https://doi.org/10.5753/eniac.2026.31456

Resumo

Graph Neural Networks (GNNs) have achieved remarkable performance in node classification tasks, motivating growing interest in methods capable of explaining their predictions. Recent logic-based approaches, such as LogicXGNN, derive global logical rules for Graph Neural Networks (GNNs) from collections of explanatory subgraphs. While informative, these subgraphs may contain redundant structural information that is specific to individual nodes, potentially limiting the generality of the extracted rules. In this work, we propose a logic-based framework for node classification in Simple Graph Convolution (SGC) networks that uses minimal abductive explanations as an intermediate representation for rule extraction. For each node, we compute a minimal set of node-feature pairs sufficient to preserve the predicted class. These explanations are then used to train decision trees from which global logical rules are extracted. Experiments on benchmark datasets show that the proposed framework produces compact global rules while maintaining high fidelity to the original SGC model.

Referências

Armgaan, B., Dalmia, M., Medya, S., and Ranu, S. (2024). GraphTrail: Translating GNN predictions into human-interpretable logical rules. In Advances in Neural Information Processing Systems 38 (NeurIPS 2024).

Azzolin, S., Longa, A., Barbiero, P., Lio, P., and Passerini, A. (2023). Global explainability of GNNs via logic combination of learned concepts. In 11th ICLR.

Geng, C., Zhao, Z., Wang, Z., Ye, H., Jiang, Y., and Si, X. (2026). LogicXGNN: Grounded logical rules for explaining graph neural networks. In 14th ICLR.

Hu, W., Fey, M., Zitnik, M., Dong, Y., Ren, H., Liu, B., Catasta, M., and Leskovec, J. (2020). Open graph benchmark: Datasets for machine learning on graphs. In Advances in Neural Information Processing Systems (NeurIPS), volume 33, pages 22118–22133.

Ignatiev, A., Narodytska, N., and Marques-Silva, J. (2019). Abduction-Based Explanations for Machine Learning Models. In AAAI, volume 33, pages 1511–1519.

Izza, Y., Huang, X., Morgado, A., Planes, J., Ignatiev, A., and Marques-Silva, J. (2024). Distance-restricted explanations: Theoretical underpinnings & efficient implementation. arXiv preprint arXiv:2405.08297.

Ju, W., Fang, Z., Gu, Y., Liu, Z., Long, Q., Qiao, Z., Qin, Y., Shen, J., Sun, F., Xiao, Z., Yang, J., Yuan, J., Zhao, Y., Wang, Y., Luo, X., and Zhang, M. (2024). A comprehensive survey on deep graph representation learning. Neural Networks, 173:106207.

La Malfa, E., Michelmore, R., Zbrzezny, A. M., Paoletti, N., and Kwiatkowska, M. (2021). On guaranteed optimal robust explanations for NLP models. In IJCAI-21.

Marques-Silva, J., Gerspacher, T., Cooper, M. C., Ignatiev, A., and Narodytska, N. (2020). Explaining naive Bayes and other linear classifiers with polynomial time and delay. In Advances in Neural Information Processing Systems 33 (NeurIPS 2020).

Marques-Silva, J. and Ignatiev, A. (2022). Delivering trustworthy AI through formal XAI. Proceedings of the AAAI Conference on Artificial Intelligence, 36(11):12342–12350. Senior Member Presentation Track.

Pereira, T., Nascimento, E., Resck, L. E., Mesquita, D., and Souza, A. (2023). Distill n’ explain: Explaining graph neural networks using simple surrogates. In 26th AISTATS.

Wu, F., Souza, A., Zhang, T., Fifty, C., Yu, T., and Weinberger, K. Q. (2019). Simplifying graph convolutional networks. In 36th ICML, pages 6861–6871.

Yuan, H., Yu, H., Gui, S., and Ji, S. (2023). Explainability in graph neural networks: A taxonomic survey. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(5):5782–5799.