Cited By
View all- Liu XMa YChen DLiu L(2024)Toward Embedding Ambiguity-Sensitive Graph Neural Network ExplainabilityIEEE Transactions on Fuzzy Systems10.1109/TFUZZ.2024.345791432:12(6951-6964)Online publication date: Dec-2024
Game-theoretic Counterfactual Explanation for Graph Neural Networks
Authors: 
Chirag Chhablani, Sarthak Jain, Akshay Channesh, Ian A. Kash, Sourav MedyaAuthors Info & Claims
Chirag Chhablani, Sarthak Jain, Akshay Channesh, Ian A. Kash, Sourav MedyaAuthors Info & ClaimsPages 503 - 514
Abstract
Graph Neural Networks (GNNs) have been a powerful tool for node classification tasks in complex networks. However, their decision-making processes remain a black-box to users, making it challenging to understand the reasoning behind their predictions. Counterfactual explanations (CFE) have shown promise in enhancing the interpretability of machine learning models. Prior approaches to compute CFE for GNNS often are learning-based approaches that require training additional graphs. In this paper, we propose a semivalue-based, non-learning approach to generate CFE for node classification tasks, eliminating the need for any additional training. Our results reveals that computing Banzhaf values requires lower sample complexity in identifying the counterfactual explanations compared to other popular methods such as computing Shapley values. Our empirical evidence indicates computing Banzhaf values can achieve up to a fourfold speed up compared to Shapley values. We also design a thresholding method for computing Banzhaf values and show theoretical and empirical results on its robustness in noisy environments, making it superior to Shapley values. Furthermore, the thresholded Banzhaf values are shown to enhance efficiency without compromising the quality (i.e., fidelity) in the explanations in three popular graph datasets.
Supplemental Material
MP4 File
Supplemental video
- Download
- 119.45 MB
References
[1]
Yoram Bachrach, Evangelos Markakis, Ezra Resnick, Ariel D Procaccia, Jeffrey S Rosenschein, and Amin Saberi. 2010. Approximating power indices: theoretical and empirical analysis. Autonomous Agents and Multi-Agent Systems 20 (2010), 105--122.
[2]
Mohit Bajaj, Lingyang Chu, Zi Yu Xue, Jian Pei, LanjunWang, Peter Cho-Ho Lam, and Yong Zhang. 2021. Robust Counterfactual Explanations on Graph Neural Networks. In Advances in Neural Information Processing Systems, M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (Eds.), Vol. 34. Curran Associates, Inc., 5644--5655. https://proceedings.neurips.cc/paper_files/ paper/2021/file/2c8c3a57383c63caef6724343eb62257-Paper.pdf
[3]
Federico Baldassarre and Hossein Azizpour. 2019. Explainability Techniques for Graph Convolutional Networks. arXiv:1905.13686 [cs.LG]
[4]
John F Banzhaf III. 1965. Weighted voting doesn't work: A mathematical analysis. Rutgers L. Rev. 19 (1965), 317.
[5]
Javier Castro, Daniel Gómez, and Juan Tejada. 2009. Polynomial Calculation of the Shapley Value Based on Sampling. Computers & Operations Research 36, 5 (May 2009), 1726--1730.
[6]
Amnon Catav, Boyang Fu, Yazeed Zoabi, Ahuva Libi Weiss Meilik, Noam Shomron, Jason Ernst, Sriram Sankararaman, and Ran Gilad-Bachrach. 2021. Marginal contribution feature importance-an axiomatic approach for explaining data. In International Conference on Machine Learning. PMLR, 1324--1335.
[7]
Daphne Cornelisse, Thomas Rood, Yoram Bachrach, Mateusz Malinowski, and Tal Kachman. 2022. Neural Payoff Machines: Predicting Fair and Stable Payoff Allocations Among Team Members. In Advances in Neural Information Processing Systems, S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh (Eds.), Vol. 35. Curran Associates, Inc., 25491--25503. https://proceedings.neurips.cc/paper_files/paper/2022/file/ a38df2dd882bf7059a1914dd5547af87-Paper-Conference.pdf
[8]
Pradeep Dubey and Lloyd S Shapley. 1979. Mathematical properties of the Banzhaf power index. Mathematics of Operations Research 4, 2 (1979), 99--131.
[9]
Alexandre Duval and Fragkiskos D Malliaros. 2021. Graphsvx: Shapley value explanations for graph neural networks. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases. Springer, 302--318.
[10]
David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alán Aspuru-Guzik, and Ryan P Adams. 2015. Convolutional networks on graphs for learning molecular fingerprints. In Advances in neural information processing systems. 2224--2232.
[11]
Evan N Feinberg, Harsh Suratia, and Amir Saffari. 2018. PotentialNet for molecular property prediction. Journal of chemical information and modeling 58, 6 (2018), 1194--1201.
[12]
Amirata Ghorbani and James Zou. 2019. Data Shapley: Equitable Valuation of Data for Machine Learning. In International Conference on Machine Learning. PMLR, 2242--2251.
[13]
William L. Hamilton, Rex Ying, and Jure Leskovec. 2017. Inductive Representation Learning on Large Graphs. In Proceedings of the 31st International Conference on Neural Information Processing Systems (Long Beach, California, USA) (NIPS'17). Curran Associates Inc., 1025--1035.
[14]
Zexi Huang, Mert Kosan, Sourav Medya, Sayan Ranu, and Ambuj Singh. 2023. Global Counterfactual Explainer for Graph Neural Networks. In Proceedings of the Sixteenth ACM International Conference onWeb Search and Data Mining. 141--149.
[15]
Ruoxi Jia, David Dao, Boxin Wang, Frances Ann Hubis, Nezihe Merve Gurel, Bo Li, Ce Zhang, Costas Spanos, and Dawn Song. 2019. Efficient Task-Specific Data Valuation for Nearest Neighbor Algorithms. Proceedings of the VLDB Endowment 12, 11 (July 2019), 1610--1623.
[16]
Jaykumar Kakkad, Jaspal Jannu, Kartik Sharma, Charu Aggarwal, and Sourav Medya. 2023. A Survey on Explainability of Graph Neural Networks. arXiv:2306.01958 [cs.LG]
[17]
Adam Karczmarz, Anish Mukherjee, Piotr Sankowski, and Piotr Wygocki. 2021. Improved Feature Importance Computations for Tree Models: Shapley vs. Banzhaf. arXiv preprint arXiv:2108.04126 (2021).
[18]
Thomas N Kipf and MaxWelling. 2016. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907 (2016).
[19]
Mert Kosan, Samidha Verma, Burouj Armgaan, Khushbu Pahwa, Ambuj Singh, Sourav Medya, and Sayan Ranu. 2023. GNNX-BENCH: Unravelling the Utility of Perturbation-based GNN Explainers through In-depth Benchmarking. arXiv preprint arXiv:2310.01794 (2023).
[20]
I Elizabeth Kumar, Suresh Venkatasubramanian, Carlos Scheidegger, and Sorelle Friedler. 2020. Problems with Shapley-value-based explanations as feature importance measures. In International Conference on Machine Learning. PMLR, 5491--5500.
[21]
Yongchan Kwon and James Zou. 2022. Beta Shapley: A Unified and Noise- Reduced Data Valuation Framework for Machine Learning. In Proceedings of the 25th International Conference on Artificial Intelligence and Statistics (AISTATS), Vol. 151. PMLR, Valencia, Spain, 1234--1245.
[22]
Yongchan Kwon and James Zou. 2022. Data-OOB: Out-of-Bag Estimate as a Simple and Efficient Data Value. In Proceedings of the 40th International Conference on Machine Learning (ICML).
[23]
Yongchan Kwon and James Y Zou. 2022.WeightedSHAP: analyzing and improving Shapley based feature attributions. Advances in Neural Information Processing Systems 35 (2022), 34363--34376.
[24]
Wenqian Li, Yinchuan Li, Zhigang Li, Jianye HAO, and Yan Pang. 2023. DAG Matters! GFlowNets Enhanced Explainer for Graph Neural Networks. In The Eleventh International Conference on Learning Representations. https://openreview.net/ forum?id=jgmuRzM-sb6
[25]
Wanyu Lin, Hao Lan, and Baochun Li. 2021. Generative Causal Explanations for Graph Neural Networks. In Proceedings of the 38th International Conference on Machine Learning (Proceedings of Machine Learning Research, Vol. 139), Marina Meila and Tong Zhang (Eds.). PMLR, 6666--6679. https://proceedings.mlr.press/ v139/lin21d.html
[26]
Ana Lucic, Maartje A Ter Hoeve, Gabriele Tolomei, Maarten De Rijke, and Fabrizio Silvestri. 2022. Cf-gnnexplainer: Counterfactual explanations for graph neural networks. In International Conference on Artificial Intelligence and Statistics. PMLR, 4499--4511.
[27]
Scott M Lundberg and Su-In Lee. 2017. A unified approach to interpreting model predictions. Advances in neural information processing systems 30 (2017).
[28]
Dongsheng Luo,Wei Cheng, Dongkuan Xu,Wenchao Yu, Bo Zong, Haifeng Chen, and Xiang Zhang. 2020. Parameterized Explainer for Graph Neural Network. In Advances in Neural Information Processing Systems, H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (Eds.), Vol. 33. Curran Associates, Inc., 19620--19631. https://proceedings.neurips.cc/paper_files/paper/2020/file/ e37b08dd3015330dcbb5d6663667b8b8-Paper.pdf
[29]
Jing Ma, Ruocheng Guo, Saumitra Mishra, Aidong Zhang, and Jundong Li. 2022. CLEAR: Generative Counterfactual Explanations on Graphs. arXiv preprint arXiv:2210.08443 (2022).
[30]
Sahil Manchanda, Akash Mittal, Anuj Dhawan, Sourav Medya, Sayan Ranu, and Ambuj Singh. 2020. Gcomb: Learning budget-constrained combinatorial algorithms over billion-sized graphs. Advances in Neural Information Processing Systems 33 (2020), 20000--20011.
[31]
Sourav Medya, Tiyani Ma, Arlei Silva, and Ambuj Singh. 2020. K-Core Minimization: A Game Theoretic Approach. arXiv:1901.02166 [cs.SI]
[32]
Danilo Numeroso and Davide Bacciu. 2021. MEG: Generating Molecular Counterfactual Explanations for Deep Graph Networks. arXiv:2104.08060 [cs.LG]
[33]
Ramin Okhrati and Aldo Lipani. 2021. A Multilinear Sampling Algorithm to Estimate Shapley Values. In 25th International Conference on Pattern Recognition (ICPR 2020). IEEE, 7992--7999.
[34]
Roma Patel, Marta Garnelo, Ian Gemp, Chris Dyer, and Yoram Bachrach. 2021. Game-theoretic Vocabulary Selection via the Shapley Value and Banzhaf Index. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies. Association for Computational Linguistics, Online, 2789--2798. https://doi.org/10.18653/v1/ 2021.naacl-main.223
[35]
Tamara Pereira, Erik Nascimento, Lucas E. Resck, Diego Mesquita, and Amauri Souza. 2023. Distill n' Explain: explaining graph neural networks using simple surrogates. In Proceedings of The 26th International Conference on Artificial Intelligence and Statistics (Proceedings of Machine Learning Research, Vol. 206), Francisco Ruiz, Jennifer Dy, and Jan-Willem van de Meent (Eds.). PMLR, 6199-- 6214. https://proceedings.mlr.press/v206/pereira23a.html
[36]
Phillip E. Pope, Soheil Kolouri, Mohammad Rostami, Charles E. Martin, and Heiko Hoffmann. 2019. Explainability Methods for Graph Convolutional Neural Networks. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR).
[37]
Michael Schlichtkrull, Thomas N. Kipf, Peter Bloem, Rianne van den Berg, Ivan Titov, and Max Welling. 2017. Modeling Relational Data with Graph Convolutional Networks. arXiv:1703.06103 [stat.ML]
[38]
Michael Sejr Schlichtkrull, Nicola De Cao, and Ivan Titov. 2022. Interpreting Graph Neural Networks for NLP With Differentiable Edge Masking. arXiv:2010.00577 [cs.CL]
[39]
Lloyd S Shapley. 1953. A value for n-person games. Contributions to the Theory of Games 2, 28 (1953), 307--317.
[40]
Hao Tian, Sourav Medya, and Wei Ye. 2023. COMBHelper: A Neural Approach to Reduce Search Space for Graph Combinatorial Problems. arXiv preprint arXiv:2312.09086 (2023).
[41]
Stelios Triantafyllou, Adish Singla, and Goran Radanovic. 2021. On Blame Attribution for Accountable Multi-Agent Sequential Decision Making. Advances in Neural Information Processing Systems 34 (2021), 15774--15786.
[42]
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. 2018. Graph Attention Networks. In International Conference on Learning Representations. https://openreview.net/forum?id=rJXMpikCZ
[43]
Samidha Verma, Burouj Armgaan, Sourav Medya, and Sayan Ranu. 2023. Empowering Counterfactual Reasoning over Graph Neural Networks through Inductivity. arXiv preprint arXiv:2306.04835 (2023).
[44]
Jiachen TWang and Ruoxi Jia. 2023. Data banzhaf: A robust data valuation framework for machine learning. In International Conference on Artificial Intelligence and Statistics. PMLR, 6388--6421.
[45]
XibinWang, Liang Jiang, Sujian Liu, Zhihua Cui, and Shuming Yang. 2019. Graph convolutional networks for sentiment classification. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics. 1431--1441.
[46]
Xiaoqi Wang and Han-Wei Shen. 2023. GNNInterpreter: A Probabilistic Generative Model-Level Explanation for Graph Neural Networks. arXiv:2209.07924 [cs.LG]
[47]
Geemi P.Wellawatte, Aditi Seshadri, and Andrew D. White. 2022. Model agnostic generation of counterfactual explanations for molecules. Chem. Sci. 13 (2022), 3697--3705. Issue 13. https://doi.org/10.1039/D1SC05259D
[48]
Zongda Wu, Shirui Pan, Guodong Long, Jing Jiang, Xiaojun Chang, and Chengqi Zhang. 2020. Graph adversarial networks: Protecting information against adversarial attacks. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 34. 12721--12729.
[49]
Tom Yan and Ariel D Procaccia. 2021. If you like shapley then you'll love the core. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 35. 5751--5759.
[50]
Liang Yao, Chengsheng Mao, Yuan Luo, Yansong Huang, Zhiyuan Li, Xiaoyong Dong, and Jie Zhou. 2019. Graph convolutional networks for text classification. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 33. 7370--7377.
[51]
Zhitao Ying, Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, and Jure Leskovec. 2020. Gnnexplainer: Generating explanations for graph neural networks. In Proceedings of the 35th International Conference on Machine Learning. 6214--6223.
[52]
Muhan Zhang, Zhiwei Cui, Marion Neumann, and Yixin Chen. 2019. Graph convolutional networks: A comprehensive review. In Proceedings of the IEEE, Vol. 107. 1656--1683.
[53]
Shichang Zhang, Yozen Liu, Neil Shah, and Yizhou Sun. 2022. Gstarx: Explaining graph neural networks with structure-aware cooperative games. Advances in Neural Information Processing Systems 35 (2022), 19810--19823.
[54]
Yue Zhang, David Defazio, and Arti Ramesh. 2021. RelEx: A Model-Agnostic Relational Model Explainer. In Proceedings of the 2021 AAAI/ACM Conference on AI, Ethics, and Society (Virtual Event, USA) (AIES '21). Association for Computing Machinery, New York, NY, USA, 1042--1049. https://doi.org/10.1145/3461702.3462562
[55]
Jie Zhou, Ganqu Cui, Zhengyan Zhang, and Cheng Yang. 2018. Graph Neural Networks: A Reviewof Methods and Applications. arXiv preprint arXiv:1812.08434 (2018).
[56]
Michael Zuckerman, Piotr Faliszewski, Yoram Bachrach, and Edith Elkind. 2008. Manipulating the Quota in Weighted Voting Games. In AAAI, Vol. 8. 215--220.
Index Terms
- Game-theoretic Counterfactual Explanation for Graph Neural Networks
Recommendations
Global Counterfactual Explainer for Graph Neural Networks
WSDM '23: Proceedings of the Sixteenth ACM International Conference on Web Search and Data MiningGraph neural networks (GNNs) find applications in various domains such as computational biology, natural language processing, and computer security. Owing to their popularity, there is an increasing need to explain GNN predictions since GNNs are black-...
Causal generative explainers using counterfactual inference: a case study on the Morpho-MNIST dataset
AbstractIn this paper, we propose leveraging causal generative learning as an interpretable tool for explaining image classifiers. Specifically, we present a generative counterfactual inference approach to study the influence of visual features (pixels) ...
Learning and Evaluating Graph Neural Network Explanations based on Counterfactual and Factual Reasoning
WWW '22: Proceedings of the ACM Web Conference 2022Structural data well exists in Web applications, such as social networks in social media, citation networks in academic websites, and threads data in online forums. Due to the complex topology, it is difficult to process and make use of the rich ...
Comments
Information & Contributors
Information
Published In
May 2024
4826 pages
ISBN:9798400701719
DOI:10.1145/3589334
- General Chairs:
- Tat-Seng Chua,
- Chong-Wah Ngo,
- Proceedings Chair:
- Roy Ka-Wei Lee,
- Program Chairs:
- Ravi Kumar,
- Hady W. Lauw
Copyright © 2024 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 13 May 2024
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
Conference
WWW '24
Sponsor:
Acceptance Rates
Overall Acceptance Rate 1,899 of 8,196 submissions, 23%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 198Total Downloads
- Downloads (Last 12 months)198
- Downloads (Last 6 weeks)28
Reflects downloads up to 22 Dec 2024
Other Metrics
Citations
Cited By
View all- Liu XMa YChen DLiu L(2024)Toward Embedding Ambiguity-Sensitive Graph Neural Network ExplainabilityIEEE Transactions on Fuzzy Systems10.1109/TFUZZ.2024.345791432:12(6951-6964)Online publication date: Dec-2024
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in