{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,18]],"date-time":"2026-08-18T03:06:10Z","timestamp":1787022370998,"version":"build-2736575974"},"reference-count":72,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2023,7]]},"abstract":"<jats:p>Graph Neural Networks (GNNs) have significantly boosted the performance of many graph-based applications, yet they serve as black-box models. To understand how GNNs make decisions, explainability techniques have been extensively studied. While the majority of existing methods focus on local explainability, we propose DAG-Explainer in this work aiming for global explainability. Specifically, we observe three properties of superior explanations for a pretrained GNN: they should be highly recognized by the model, compliant with the data distribution and discriminative among all the classes. The first property entails an explanation to be faithful to the model, as the other two require the explanation to be convincing regarding the data distribution. Guided by these properties, we design metrics to quantify the quality of each single explanation and formulate the problem of finding data-aware global explanations for a pretrained GNN as an optimizing problem. We prove that the problem is NP-hard and adopt a randomized greedy algorithm to find a near optimal solution. Furthermore, we derive an improved bound of the approximation algorithm in our problem over the state-of-the-art (SOTA) best. Experimental results show that DAG-Explainer can efficiently produce meaningful and trustworthy explanations while preserving comparable quantitative evaluation results to the SOTA methods.<\/jats:p>","DOI":"10.14778\/3611479.3611538","type":"journal-article","created":{"date-parts":[[2023,8,24]],"date-time":"2023-08-24T22:08:08Z","timestamp":1692914888000},"page":"3447-3460","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["On Data-Aware Global Explainability of Graph Neural Networks"],"prefix":"10.14778","volume":"16","author":[{"given":"Ge","family":"Lv","sequence":"first","affiliation":[{"name":"HKUST"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lei","family":"Chen","sequence":"additional","affiliation":[{"name":"HKUST &amp; HKUST(GZ)"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,8,24]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"[n.d.]. Supplementary Materials. https:\/\/github.com\/Gori-LV\/DAG.  [n.d.]. Supplementary Materials. https:\/\/github.com\/Gori-LV\/DAG."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3477141"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2018.00059"},{"key":"e_1_2_1_4_1","volume-title":"Summarizing Provenance of Aggregate Query Results in Relational Databases. In 2021 IEEE 37th International Conference on Data Engineering (ICDE). IEEE","author":"AlOmeir Omar","year":"2021","unstructured":"Omar AlOmeir , Eugenie Yujing Lai , Mostafa Milani , and Rachel Pottinger . 2021 . Summarizing Provenance of Aggregate Query Results in Relational Databases. In 2021 IEEE 37th International Conference on Data Engineering (ICDE). IEEE , 1955--1960. Omar AlOmeir, Eugenie Yujing Lai, Mostafa Milani, and Rachel Pottinger. 2021. Summarizing Provenance of Aggregate Query Results in Relational Databases. In 2021 IEEE 37th International Conference on Data Engineering (ICDE). IEEE, 1955--1960."},{"key":"e_1_2_1_5_1","series-title":"Series B: Biological Sciences 359, 1447","volume-title":"transmission dynamics and control of SARS: the 2002--2003 epidemic. Philosophical Transactions of the Royal Society of London","author":"Anderson Roy M","year":"2004","unstructured":"Roy M Anderson , Christophe Fraser , Azra C Ghani , Christl A Donnelly , Steven Riley , Neil M Ferguson , Gabriel M Leung , Tai H Lam , and Anthony J Hedley . 2004. Epidemiology , transmission dynamics and control of SARS: the 2002--2003 epidemic. Philosophical Transactions of the Royal Society of London . Series B: Biological Sciences 359, 1447 ( 2004 ), 1091--1105. Roy M Anderson, Christophe Fraser, Azra C Ghani, Christl A Donnelly, Steven Riley, Neil M Ferguson, Gabriel M Leung, Tai H Lam, and Anthony J Hedley. 2004. Epidemiology, transmission dynamics and control of SARS: the 2002--2003 epidemic. Philosophical Transactions of the Royal Society of London. Series B: Biological Sciences 359, 1447 (2004), 1091--1105."},{"key":"e_1_2_1_6_1","volume-title":"Optimizing sentinel surveillance in temporal network epidemiology. Scientific reports 7, 1","author":"Bai Yuan","year":"2017","unstructured":"Yuan Bai , Bo Yang , Lijuan Lin , Jose L Herrera , Zhanwei Du , and Petter Holme . 2017. Optimizing sentinel surveillance in temporal network epidemiology. Scientific reports 7, 1 ( 2017 ), 1--10. Yuan Bai, Bo Yang, Lijuan Lin, Jose L Herrera, Zhanwei Du, and Petter Holme. 2017. Optimizing sentinel surveillance in temporal network epidemiology. Scientific reports 7, 1 (2017), 1--10."},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Peng Bao Weihui Hong and Xuanya Li. 2021. Predicting Paper Acceptance via Interpretable Decision Sets. In WWW (Companion Volume). ACM \/ IW3C2 461--467.  Peng Bao Weihui Hong and Xuanya Li. 2021. Predicting Paper Acceptance via Interpretable Decision Sets. In WWW (Companion Volume). ACM \/ IW3C2 461--467.","DOI":"10.1145\/3442442.3451370"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/2634074.2634180"},{"key":"e_1_2_1_9_1","volume-title":"Webb","author":"Bunimovich Leonid A.","year":"2018","unstructured":"Leonid A. Bunimovich , Chi-Jen Wang , Seokjoo Chae , and Benjamin Z . Webb . 2018 . Uncovering Hierarchical Structure in Social Networks Using Isospectral Reductions. In IEEE\/ACM 2018 International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2018. IEEE Computer Society , 1199--1206. Leonid A. Bunimovich, Chi-Jen Wang, Seokjoo Chae, and Benjamin Z. Webb. 2018. Uncovering Hierarchical Structure in Social Networks Using Isospectral Reductions. In IEEE\/ACM 2018 International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2018. IEEE Computer Society, 1199--1206."},{"key":"e_1_2_1_10_1","volume-title":"ParamE: Regarding Neural Network Parameters as Relation Embeddings for Knowledge Graph Completion","author":"Che Feihu","unstructured":"Feihu Che , Dawei Zhang , Jianhua Tao , Mingyue Niu , and Bocheng Zhao . 2020. ParamE: Regarding Neural Network Parameters as Relation Embeddings for Knowledge Graph Completion . In AAAI. AAAI Press , 2774--2781. Feihu Che, Dawei Zhang, Jianhua Tao, Mingyue Niu, and Bocheng Zhao. 2020. ParamE: Regarding Neural Network Parameters as Relation Embeddings for Knowledge Graph Completion. In AAAI. AAAI Press, 2774--2781."},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsm\u00e4ssan","volume":"80","author":"Chen Lin","year":"2018","unstructured":"Lin Chen , Moran Feldman , and Amin Karbasi . 2018 . Weakly Submodular Maximization Beyond Cardinality Constraints: Does Randomization Help Greedy? . In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsm\u00e4ssan , Stockholm, Sweden, July 10--15 , 2018 (Proceedings of Machine Learning Research), Vol. 80 . PMLR, 803--812. Lin Chen, Moran Feldman, and Amin Karbasi. 2018. Weakly Submodular Maximization Beyond Cardinality Constraints: Does Randomization Help Greedy?. In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsm\u00e4ssan, Stockholm, Sweden, July 10--15, 2018 (Proceedings of Machine Learning Research), Vol. 80. PMLR, 803--812."},{"key":"e_1_2_1_12_1","volume-title":"Mining graph data","author":"Cook Diane J","unstructured":"Diane J Cook and Lawrence B Holder . 2006. Mining graph data . John Wiley & Sons . Diane J Cook and Lawrence B Holder. 2006. Mining graph data. John Wiley & Sons."},{"key":"e_1_2_1_13_1","volume-title":"Carlo Sansone, and Mario Vento","author":"Cordella Luigi P","year":"2004","unstructured":"Luigi P Cordella , Pasquale Foggia , Carlo Sansone, and Mario Vento . 2004 . A (sub) graph isomorphism algorithm for matching large graphs. IEEE transactions on pattern analysis and machine intelligence 26, 10 (2004), 1367--1372. Luigi P Cordella, Pasquale Foggia, Carlo Sansone, and Mario Vento. 2004. A (sub) graph isomorphism algorithm for matching large graphs. IEEE transactions on pattern analysis and machine intelligence 26, 10 (2004), 1367--1372."},{"key":"e_1_2_1_14_1","volume-title":"Submodular meets spectral: Greedy algorithms for subset selection, sparse approximation and dictionary selection. arXiv preprint arXiv:1102.3975","author":"Das Abhimanyu","year":"2011","unstructured":"Abhimanyu Das and David Kempe . 2011. Submodular meets spectral: Greedy algorithms for subset selection, sparse approximation and dictionary selection. arXiv preprint arXiv:1102.3975 ( 2011 ). Abhimanyu Das and David Kempe. 2011. Submodular meets spectral: Greedy algorithms for subset selection, sparse approximation and dictionary selection. arXiv preprint arXiv:1102.3975 (2011)."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1021\/jm00106a046"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1021\/jm00106a046"},{"key":"e_1_2_1_17_1","unstructured":"Amit Dhurandhar Pin-Yu Chen Ronny Luss Chun-Chen Tu Pai-Shun Ting Karthikeyan Shanmugam and Payel Das. 2018. Explanations based on the Missing: Towards Contrastive Explanations with Pertinent Negatives. In NeurIPS. 590--601.  Amit Dhurandhar Pin-Yu Chen Ronny Luss Chun-Chen Tu Pai-Shun Ting Karthikeyan Shanmugam and Payel Das. 2018. Explanations based on the Missing: Towards Contrastive Explanations with Pertinent Negatives. In NeurIPS. 590--601."},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 37th Graph Representation Learning and Beyond Workshop at ICML 2020.","author":"Faber Lukas","year":"2020","unstructured":"Lukas Faber , Amin K. Moghaddam , and Roger Wattenhofer . 2020 . Contrastive Graph Neural Network Explanation . In Proceedings of the 37th Graph Representation Learning and Beyond Workshop at ICML 2020. Lukas Faber, Amin K. Moghaddam, and Roger Wattenhofer. 2020. Contrastive Graph Neural Network Explanation. In Proceedings of the 37th Graph Representation Learning and Beyond Workshop at ICML 2020."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/090750688"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/IJCNN.2005.1555942"},{"key":"e_1_2_1_21_1","volume-title":"Chemistry of the Elements","author":"Greenwood Norman Neill","unstructured":"Norman Neill Greenwood and Alan Earnshaw . 2012. Chemistry of the Elements . Elsevier . Norman Neill Greenwood and Alan Earnshaw. 2012. Chemistry of the Elements. Elsevier."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.knosys.2020.106622"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0269888912000331"},{"key":"e_1_2_1_24_1","unstructured":"Kristian Kersting Nils M. Kriege Christopher Morris Petra Mutzel and Marion Neumann. 2016. Benchmark Data Sets for Graph Kernels. http:\/\/graphkernels.cs.tu-dortmund.de  Kristian Kersting Nils M. Kriege Christopher Morris Petra Mutzel and Marion Neumann. 2016. Benchmark Data Sets for Graph Kernels. http:\/\/graphkernels.cs.tu-dortmund.de"},{"key":"e_1_2_1_25_1","volume-title":"Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980","author":"Kingma Diederik P","year":"2014","unstructured":"Diederik P Kingma and Jimmy Ba . 2014 . Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980 (2014). Diederik P Kingma and Jimmy Ba. 2014. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980 (2014)."},{"key":"e_1_2_1_26_1","volume-title":"Semi-Supervised Classification with Graph Convolutional Networks. In 5th International Conference on Learning Representations, ICLR","author":"Thomas","year":"2017","unstructured":"Thomas N. Kipf and Max Welling. 2017 . Semi-Supervised Classification with Graph Convolutional Networks. In 5th International Conference on Learning Representations, ICLR 2017 . OpenReview.net. Thomas N. Kipf and Max Welling. 2017. Semi-Supervised Classification with Graph Convolutional Networks. In 5th International Conference on Learning Representations, ICLR 2017. OpenReview.net."},{"key":"e_1_2_1_27_1","unstructured":"Himabindu Lakkaraju and Cynthia Rudin. 2017. Learning cost-effective and interpretable treatment regimes. In Artificial intelligence and statistics. PMLR 166--175.  Himabindu Lakkaraju and Cynthia Rudin. 2017. Learning cost-effective and interpretable treatment regimes. In Artificial intelligence and statistics. PMLR 166--175."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(95)00205-7"},{"key":"e_1_2_1_29_1","volume-title":"ICML (Proceedings of Machine Learning Research)","volume":"139","author":"Lin Wanyu","year":"2021","unstructured":"Wanyu Lin , Hao Lan , and Baochun Li . 2021 . Generative Causal Explanations for Graph Neural Networks . In ICML (Proceedings of Machine Learning Research) , Vol. 139 . PMLR, 6666--6679. Wanyu Lin, Hao Lan, and Baochun Li. 2021. Generative Causal Explanations for Graph Neural Networks. In ICML (Proceedings of Machine Learning Research), Vol. 139. PMLR, 6666--6679."},{"key":"e_1_2_1_30_1","volume-title":"Local Community Detection in Multiple Networks. In KDD '20: The 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining","author":"Luo Dongsheng","year":"2020","unstructured":"Dongsheng Luo , Yuchen Bian , Yaowei Yan , Xiao Liu , Jun Huan , and Xiang Zhang . 2020 . Local Community Detection in Multiple Networks. In KDD '20: The 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining , Virtual Event , 2020. ACM, 266--274. Dongsheng Luo, Yuchen Bian, Yaowei Yan, Xiao Liu, Jun Huan, and Xiang Zhang. 2020. Local Community Detection in Multiple Networks. In KDD '20: The 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Virtual Event, 2020. ACM, 266--274."},{"key":"e_1_2_1_31_1","volume-title":"Parameterized Explainer for Graph Neural Network. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems","author":"Luo Dongsheng","year":"2020","unstructured":"Dongsheng Luo , Wei Cheng , Dongkuan Xu , Wenchao Yu , BoZong, Haifeng Chen , and Xiang Zhang . 2020 . Parameterized Explainer for Graph Neural Network. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020. Dongsheng Luo, Wei Cheng, Dongkuan Xu, Wenchao Yu, BoZong, Haifeng Chen, and Xiang Zhang. 2020. Parameterized Explainer for Graph Neural Network. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020."},{"key":"e_1_2_1_32_1","volume-title":"DASFAA (1) (Lecture Notes in Computer Science)","author":"Lv Ge","unstructured":"Ge Lv , Lei Chen , and Caleb Chen Cao . 2022. On Glocal Explainability of Graph Neural Networks . In DASFAA (1) (Lecture Notes in Computer Science) , Vol. 13245 . Springer , 648--664. Ge Lv, Lei Chen, and Caleb Chen Cao. 2022. On Glocal Explainability of Graph Neural Networks. In DASFAA (1) (Lecture Notes in Computer Science), Vol. 13245. Springer, 648--664."},{"key":"e_1_2_1_33_1","volume-title":"The complexity of causality and responsibility for query answers and non-answers. arXiv preprint arXiv:1009.2021","author":"Meliou Alexandra","year":"2010","unstructured":"Alexandra Meliou , Wolfgang Gatterbauer , Katherine F Moore , and Dan Suciu . 2010. The complexity of causality and responsibility for query answers and non-answers. arXiv preprint arXiv:1009.2021 ( 2010 ). Alexandra Meliou, Wolfgang Gatterbauer, Katherine F Moore, and Dan Suciu. 2010. The complexity of causality and responsibility for query answers and non-answers. arXiv preprint arXiv:1009.2021 (2010)."},{"key":"e_1_2_1_34_1","volume-title":"Flexible Query Answering Systems 2015: Proceedings of the 11th International Conference FQAS","author":"Moreau Aur\u00e9lien","year":"2015","unstructured":"Aur\u00e9lien Moreau , Olivier Pivert , and Gr\u00e9gory Smits . 2016. A clustering-based approach to the explanation of database query answers . In Flexible Query Answering Systems 2015: Proceedings of the 11th International Conference FQAS 2015 , Cracow, Poland, October 26--28, 2015. Springer , 307--319. Aur\u00e9lien Moreau, Olivier Pivert, and Gr\u00e9gory Smits. 2016. A clustering-based approach to the explanation of database query answers. In Flexible Query Answering Systems 2015: Proceedings of the 11th International Conference FQAS 2015, Cracow, Poland, October 26--28, 2015. Springer, 307--319."},{"key":"e_1_2_1_35_1","volume-title":"TUDataset: A collection of benchmark datasets for learning with graphs. CoRR abs\/2007.08663","author":"Morris Christopher","year":"2020","unstructured":"Christopher Morris , Nils M. Kriege , Franka Bause , Kristian Kersting , Petra Mutzel , and Marion Neumann . 2020. TUDataset: A collection of benchmark datasets for learning with graphs. CoRR abs\/2007.08663 ( 2020 ). arXiv:2007.08663 Christopher Morris, Nils M. Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. 2020. TUDataset: A collection of benchmark datasets for learning with graphs. CoRR abs\/2007.08663 (2020). arXiv:2007.08663"},{"key":"e_1_2_1_36_1","doi-asserted-by":"crossref","unstructured":"Kazuya Nakagawa Shinya Suzumura Masayuki Karasuyama Koji Tsuda and Ichiro Takeuchi. 2016. Safe Pattern Pruning: An Efficient Approach for Predictive Pattern Mining. In KDD. ACM 1785--1794.  Kazuya Nakagawa Shinya Suzumura Masayuki Karasuyama Koji Tsuda and Ichiro Takeuchi. 2016. Safe Pattern Pruning: An Efficient Approach for Predictive Pattern Mining. In KDD. ACM 1785--1794.","DOI":"10.1145\/2939672.2939844"},{"key":"e_1_2_1_37_1","volume-title":"Plug & Play Generative Networks: Conditional Iterative Generation of Images in Latent Space. In 2017 IEEE Conference on Computer Vision and Pattern Recognition, CVPR","author":"Nguyen Anh","year":"2017","unstructured":"Anh Nguyen , Jeff Clune , Yoshua Bengio , Alexey Dosovitskiy , and Jason Yosinski . 2017 . Plug & Play Generative Networks: Conditional Iterative Generation of Images in Latent Space. In 2017 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2017. IEEE Computer Society, 3510--3520. Anh Nguyen, Jeff Clune, Yoshua Bengio, Alexey Dosovitskiy, and Jason Yosinski. 2017. Plug & Play Generative Networks: Conditional Iterative Generation of Images in Latent Space. In 2017 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2017. IEEE Computer Society, 3510--3520."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2015.7298640"},{"key":"e_1_2_1_39_1","volume-title":"Temporal Graph Kernels for Classifying Dissemination Processes","author":"Oettershagen Lutz","unstructured":"Lutz Oettershagen , Nils M. Kriege , Christopher Morris , and Petra Mutzel . 2020. Temporal Graph Kernels for Classifying Dissemination Processes . In SDM. SIAM , 496--504. Lutz Oettershagen, Nils M. Kriege, Christopher Morris, and Petra Mutzel. 2020. Temporal Graph Kernels for Classifying Dissemination Processes. In SDM. SIAM, 496--504."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.23915\/distill.00007"},{"key":"e_1_2_1_41_1","first-page":"320","article-title":"The power of Student's t-test","volume":"60","author":"Owen Donald B","year":"1965","unstructured":"Donald B Owen . 1965 . The power of Student's t-test . J. Amer. Statist. Assoc. 60 , 309 (1965), 320 -- 333 . Donald B Owen. 1965. The power of Student's t-test. J. Amer. Statist. Assoc. 60, 309 (1965), 320--333.","journal-title":"J. Amer. Statist. Assoc."},{"key":"e_1_2_1_42_1","unstructured":"Adam Paszke Sam Gross Soumith Chintala Gregory Chanan Edward Yang Zachary DeVito Zeming Lin Alban Desmaison Luca Antiga and Adam Lerer. 2017. Automatic differentiation in pytorch. (2017).  Adam Paszke Sam Gross Soumith Chintala Gregory Chanan Edward Yang Zachary DeVito Zeming Lin Alban Desmaison Luca Antiga and Adam Lerer. 2017. Automatic differentiation in pytorch. (2017)."},{"key":"e_1_2_1_43_1","volume-title":"Explainability Methods for Graph Convolutional Neural Networks. In IEEE Conference on Computer Vision and Pattern Recognition, CVPR","author":"Pope Phillip E.","year":"2019","unstructured":"Phillip E. Pope , Soheil Kolouri , Mohammad Rostami , Charles E. Martin , and Heiko Hoffmann . 2019 . Explainability Methods for Graph Convolutional Neural Networks. In IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2019. Computer Vision Foundation \/ IEEE, 10772--10781. Phillip E. Pope, Soheil Kolouri, Mohammad Rostami, Charles E. Martin, and Heiko Hoffmann. 2019. Explainability Methods for Graph Convolutional Neural Networks. In IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2019. Computer Vision Foundation \/ IEEE, 10772--10781."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517886"},{"key":"e_1_2_1_45_1","volume-title":"Singh","author":"Ranu Sayan","year":"2009","unstructured":"Sayan Ranu and Ambuj K . Singh . 2009 . GraphSig: A Scalable Approach to Mining Significant Subgraphs in Large Graph Databases. In ICDE. IEEE Computer Society , 844--855. Sayan Ranu and Ambuj K. Singh. 2009. GraphSig: A Scalable Approach to Mining Significant Subgraphs in Large Graph Databases. In ICDE. IEEE Computer Society, 844--855."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.14778\/3554821.3554902"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.14778\/2856318.2856329"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-008-5089-z"},{"key":"e_1_2_1_49_1","first-page":"1","article-title":"Weakly Submodular Function Maximization Using Local Submodularity Ratio. In ISAAC (LIPIcs), Vol. 181","volume":"64","author":"Santiago Richard","year":"2020","unstructured":"Richard Santiago and Yuichi Yoshida . 2020 . Weakly Submodular Function Maximization Using Local Submodularity Ratio. In ISAAC (LIPIcs), Vol. 181 . Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik , 64 : 1 -- 64 :17. Richard Santiago and Yuichi Yoshida. 2020. Weakly Submodular Function Maximization Using Local Submodularity Ratio. In ISAAC (LIPIcs), Vol. 181. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 64:1--64:17.","journal-title":"Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNN.2008.2005605"},{"key":"e_1_2_1_51_1","volume-title":"An introduction to data structures and algorithms","author":"Storer James Andrew","unstructured":"James Andrew Storer . 2012. An introduction to data structures and algorithms . Springer Science & Business Media . James Andrew Storer. 2012. An introduction to data structures and algorithms. Springer Science & Business Media."},{"key":"e_1_2_1_52_1","unstructured":"Juntao Tan Shijie Geng Zuohui Fu Yingqiang Ge Shuyuan Xu Yunqi Li and Yongfeng Zhang. 2022. Learning and Evaluating Graph Neural Network Explanations based on Counterfactual and Factual Reasoning. In WWW. ACM 1018--1027.  Juntao Tan Shijie Geng Zuohui Fu Yingqiang Ge Shuyuan Xu Yunqi Li and Yongfeng Zhang. 2022. Learning and Evaluating Graph Neural Network Explanations based on Counterfactual and Factual Reasoning. In WWW. ACM 1018--1027."},{"key":"e_1_2_1_53_1","volume-title":"Graph Attention Networks. In 6th International Conference on Learning Representations, ICLR","author":"Velickovic Petar","year":"2018","unstructured":"Petar Velickovic , Guillem Cucurull , Arantxa Casanova , Adriana Romero , Pietro Li\u00f2 , and Yoshua Bengio . 2018 . Graph Attention Networks. In 6th International Conference on Learning Representations, ICLR 2018. OpenReview.net. Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Li\u00f2, and Yoshua Bengio. 2018. Graph Attention Networks. In 6th International Conference on Learning Representations, ICLR 2018. OpenReview.net."},{"key":"e_1_2_1_54_1","volume-title":"PGM-Explainer: Probabilistic Graphical Model Explanations for Graph Neural Networks. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems","author":"Minh","year":"2020","unstructured":"Minh N. Vu and My T. Thai. 2020 . PGM-Explainer: Probabilistic Graphical Model Explanations for Graph Neural Networks. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020 . Minh N. Vu and My T. Thai. 2020. PGM-Explainer: Probabilistic Graphical Model Explanations for Graph Neural Networks. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020."},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218127413500958"},{"key":"e_1_2_1_56_1","unstructured":"Xiang Wang Ying-Xin Wu An Zhang Xiangnan He and Tat-Seng Chua. 2021. Towards Multi-Grained Explainability for Graph Neural Networks. In NeurIPS. 18446--18458.  Xiang Wang Ying-Xin Wu An Zhang Xiangnan He and Tat-Seng Chua. 2021. Towards Multi-Grained Explainability for Graph Neural Networks. In NeurIPS. 18446--18458."},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1021\/ci00057a005"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.compbiomed.2005.12.002"},{"key":"e_1_2_1_59_1","volume-title":"Jingyuan Wang, and Dayan Pan.","author":"Wu Ning","year":"2020","unstructured":"Ning Wu , Wayne Xin Zhao , Jingyuan Wang, and Dayan Pan. 2020 . Learning Effective Road Network Representation with Hierarchical Graph Neural Networks. In KDD. ACM , 6--14. Ning Wu, Wayne Xin Zhao, Jingyuan Wang, and Dayan Pan. 2020. Learning Effective Road Network Representation with Hierarchical Graph Neural Networks. In KDD. ACM, 6--14."},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNNLS.2020.2978386"},{"key":"e_1_2_1_61_1","unstructured":"Keyulu Xu Weihua Hu Jure Leskovec and Stefanie Jegelka. 2019. How Powerful are Graph Neural Networks?. In ICLR.  Keyulu Xu Weihua Hu Jure Leskovec and Stefanie Jegelka. 2019. How Powerful are Graph Neural Networks?. In ICLR."},{"key":"e_1_2_1_62_1","volume-title":"Proceedings of the 2002 IEEE International Conference on Data Mining. IEEE Computer Society, 721--724","author":"Yan Xifeng","year":"2002","unstructured":"Xifeng Yan and Jiawei Han . 2002 . gSpan: Graph-Based Substructure Pattern Mining . In Proceedings of the 2002 IEEE International Conference on Data Mining. IEEE Computer Society, 721--724 . Xifeng Yan and Jiawei Han. 2002. gSpan: Graph-Based Substructure Pattern Mining. In Proceedings of the 2002 IEEE International Conference on Data Mining. IEEE Computer Society, 721--724."},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956784"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3520251"},{"key":"e_1_2_1_65_1","volume-title":"GNNExplainer: Generating Explanations for Graph Neural Networks. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019","author":"Ying Zhitao","year":"2019","unstructured":"Zhitao Ying , Dylan Bourgeois , Jiaxuan You , Marinka Zitnik , and Jure Leskovec . 2019 . GNNExplainer: Generating Explanations for Graph Neural Networks. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019 , NeurIPS 2019. Zhitao Ying, Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, and Jure Leskovec. 2019. GNNExplainer: Generating Explanations for Graph Neural Networks. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019."},{"key":"e_1_2_1_66_1","volume-title":"XGNN: Towards Model-Level Explanations of Graph Neural Networks. InKDD '20: The 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining","author":"Yuan Hao","year":"2020","unstructured":"Hao Yuan , Jiliang Tang , Xia Hu , and Shuiwang Ji . 2020 . XGNN: Towards Model-Level Explanations of Graph Neural Networks. InKDD '20: The 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining , Virtual Event , 2020. ACM, 430--438. Hao Yuan, Jiliang Tang, Xia Hu, and Shuiwang Ji. 2020. XGNN: Towards Model-Level Explanations of Graph Neural Networks. InKDD '20: The 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Virtual Event, 2020. ACM, 430--438."},{"key":"e_1_2_1_67_1","volume-title":"Explainability in Graph Neural Networks: A Taxonomic Survey. CoRR abs\/2012.15445","author":"Yuan Hao","year":"2020","unstructured":"Hao Yuan , Haiyang Yu , Shurui Gui , and Shuiwang Ji. 2020. Explainability in Graph Neural Networks: A Taxonomic Survey. CoRR abs\/2012.15445 ( 2020 ). arXiv:2012.15445 Hao Yuan, Haiyang Yu, Shurui Gui, and Shuiwang Ji. 2020. Explainability in Graph Neural Networks: A Taxonomic Survey. CoRR abs\/2012.15445 (2020). arXiv:2012.15445"},{"key":"e_1_2_1_68_1","unstructured":"Hao Yuan Haiyang Yu Jie Wang Kang Li and Shuiwang Ji. 2020. On Explainability of Graph Neural Networks via Subgraph Explorations. In ICML (Proceedings of Machine Learning Research).  Hao Yuan Haiyang Yu Jie Wang Kang Li and Shuiwang Ji. 2020. On Explainability of Graph Neural Networks via Subgraph Explorations. In ICML (Proceedings of Machine Learning Research)."},{"key":"e_1_2_1_69_1","volume-title":"RelEx: A Model-Agnostic Relational Model Explainer. CoRR abs\/2006.00305","author":"Zhang Yue","year":"2020","unstructured":"Yue Zhang , David DeFazio , and Arti Ramesh . 2020. RelEx: A Model-Agnostic Relational Model Explainer. CoRR abs\/2006.00305 ( 2020 ). arXiv:2006.00305 Yue Zhang, David DeFazio, and Arti Ramesh. 2020. RelEx: A Model-Agnostic Relational Model Explainer. CoRR abs\/2006.00305 (2020). arXiv:2006.00305"},{"key":"e_1_2_1_70_1","volume-title":"Relational Graph Neural Network with Hierarchical Attention for Knowledge Graph Completion","author":"Zhang Zhao","unstructured":"Zhao Zhang , Fuzhen Zhuang , Hengshu Zhu , Zhi-Ping Shi , Hui Xiong , and Qing He. 2020. Relational Graph Neural Network with Hierarchical Attention for Knowledge Graph Completion . In AAAI. AAAI Press , 9612--9619. Zhao Zhang, Fuzhen Zhuang, Hengshu Zhu, Zhi-Ping Shi, Hui Xiong, and Qing He. 2020. Relational Graph Neural Network with Hierarchical Attention for Knowledge Graph Completion. In AAAI. AAAI Press, 9612--9619."},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/bty294"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2020\/456"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3611479.3611538","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,23]],"date-time":"2023-09-23T18:13:09Z","timestamp":1695492789000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3611479.3611538"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7]]},"references-count":72,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2023,7]]}},"alternative-id":["10.14778\/3611479.3611538"],"URL":"https:\/\/doi.org\/10.14778\/3611479.3611538","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2023,7]]},"assertion":[{"value":"2023-08-24","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}