{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T19:02:30Z","timestamp":1774983750475,"version":"3.50.1"},"reference-count":75,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2025,2,10]],"date-time":"2025-02-10T00:00:00Z","timestamp":1739145600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"BSF","award":["2022279"],"award-info":[{"award-number":["2022279"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,2,10]]},"abstract":"<jats:p>Association rules are an important technique for gaining insights over large relational datasets consisting of tuples of elements (i.e. attribute-value pairs). However, it is difficult to explain the relative importance of data elements with respect to the rules in which they appear. This paper develops a measure of an element's contribution to a set of association rules based on Shapley values, denoted SHARQ (ShApley Rules Quantification). As is the case with many Shapely-based computations, the cost of a naive calculation of the score is exponential in the number of elements. To that end, we present an efficient framework for computing the exact SHARQ value of a single element whose running time is practically linear in the number of rules. Going one step further, we develop an efficient multi-element SHARQ algorithm which amortizes the cost of the single element SHARQ calculation over a set of elements. Based on the definition of SHARQ for elements we describe two additional use-cases for association rules explainability: rule importance and attribute importance. Extensive experiments over a novel benchmark dataset containing 67 instances of mined rule sets show the effectiveness of our approach.<\/jats:p>","DOI":"10.1145\/3709726","type":"journal-article","created":{"date-parts":[[2025,2,11]],"date-time":"2025-02-11T15:45:06Z","timestamp":1739288706000},"page":"1-25","source":"Crossref","is-referenced-by-count":1,"title":["SHARQ: Explainability Framework for Association Rules on Relational Data"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0009-0006-8135-6835","authenticated-orcid":false,"given":"Hadar","family":"Ben-Efraim","sequence":"first","affiliation":[{"name":"Bar-Ilan University, Ramat Gan, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-9259-9662","authenticated-orcid":false,"given":"Susan B.","family":"Davidson","sequence":"additional","affiliation":[{"name":"University of Pennsylvania, Philadelphia, PA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2314-6542","authenticated-orcid":false,"given":"Amit","family":"Somech","sequence":"additional","affiliation":[{"name":"Bar-Ilan University, Ramat Gan, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,2,11]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Adults Income Dataset (UCI). 2024. https:\/\/archive.ics.uci.edu\/ml\/datasets\/Adult\/. (2024)."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/170035.170072"},{"key":"e_1_2_1_3_1","volume-title":"Proc. 20th int. conf. very large data bases, VLDB","volume":"1215","author":"Agrawal Rakesh","year":"1994","unstructured":"Rakesh Agrawal, Ramakrishnan Srikant, et al. 1994. Fast algorithms for mining association rules. In Proc. 20th int. conf. very large data bases, VLDB, Vol. 1215. Citeseer, 487--499."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.imu.2019.100204"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989284.1989302"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2735361"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/312129.312219"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3615952.3615954"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.14778\/3007263.3007301"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/253260.253327"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/253260.253325"},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"P. Buneman S. Khanna and W.C. Tan. 2001. Why and Where: A Characterization of Data Provenance. In ICDT. 316--330.","DOI":"10.1007\/3-540-44503-X_20"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-006-0039-1"},{"key":"e_1_2_1_14_1","first-page":"S119","article-title":"Knowledge-Based Error Detection in External Beam Physician Orders Using Association Rules. International Journal of Radiation Oncology, Biology","volume":"102","author":"Chang X","year":"2018","unstructured":"X Chang, H Li, Y Fu, and D Yang. 2018. Knowledge-Based Error Detection in External Beam Physician Orders Using Association Rules. International Journal of Radiation Oncology, Biology, Physics, Vol. 102, 3 (2018), S119--S120.","journal-title":"Physics"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559901"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/19.1.79"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3520172"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3520172"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3459637.3482341"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.14778\/3415478.3415508"},{"key":"e_1_2_1_21_1","volume-title":"A survey on the use of association rules mining techniques in textual social media. Artificial Intelligence Review","author":"Diaz-Garcia Jose A","year":"2022","unstructured":"Jose A Diaz-Garcia, M Dolores Ruiz, and Maria J Martin-Bautista. 2022. A survey on the use of association rules mining techniques in textual social media. Artificial Intelligence Review (2022), 1--26."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s40747-021-00607-3"},{"key":"e_1_2_1_23_1","volume-title":"Towards a rigorous science of interpretable machine learning. arXiv preprint arXiv:1702.08608","author":"Doshi-Velez Finale","year":"2017","unstructured":"Finale Doshi-Velez and Been Kim. 2017. Towards a rigorous science of interpretable machine learning. arXiv preprint arXiv:1702.08608 (2017)."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0094799"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132960.1132963"},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","unstructured":"T.J. Green G. Karvounarakis and V. Tannen. 2007. Provenance semirings. In PODS. 31--40.","DOI":"10.1145\/1265530.1265535"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11573-016-0822-8"},{"key":"e_1_2_1_28_1","volume-title":"Mining frequent patterns without candidate generation. ACM sigmod record","author":"Han Jiawei","year":"2000","unstructured":"Jiawei Han, Jian Pei, and Yiwen Yin. 2000. Mining frequent patterns without candidate generation. ACM sigmod record, Vol. 29, 2 (2000), 1--12."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-3283-2"},{"key":"e_1_2_1_30_1","first-page":"1761","article-title":"LERI: Local Exploration for Rare-Category Identification","volume":"32","author":"Huang Hao","year":"2019","unstructured":"Hao Huang, Qian Yan, Wei Lu, Huaizhong Lin, Yunjun Gao, and Lei Chen. 2019. LERI: Local Exploration for Rare-Category Identification. IEEE Transactions on Knowledge and Data Engineering, Vol. 32, 9 (2019), 1761--1772.","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of ASBBS","volume":"16","author":"Huebner Richard A","year":"2009","unstructured":"Richard A Huebner. 2009. Diversity-based interestingness measures for association rule mining. Proceedings of ASBBS, Vol. 16, 1 (2009)."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3306618.3314230"},{"key":"e_1_2_1_33_1","unstructured":"ISOLET Dataset (UCI). 2024. https:\/\/archive.ics.uci.edu\/dataset\/54\/isolet. (2024)."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-47887-6_13"},{"key":"e_1_2_1_35_1","volume-title":"FastSHAP: Real-Time Shapley Value Estimation. In International Conference on Learning Representations.","author":"Jethani Neil","year":"2021","unstructured":"Neil Jethani, Mukund Sudarshan, Ian Connick Covert, Su-In Lee, and Rajesh Ranganath. 2021. FastSHAP: Real-Time Shapley Value Estimation. In International Conference on Learning Representations."},{"key":"e_1_2_1_36_1","unstructured":"COVID-19 Symptoms (Kaggle). 2020. https:\/\/www.kaggle.com\/datasets\/iamhungundji\/covid19-symptoms-checker. (2020)."},{"key":"e_1_2_1_37_1","unstructured":"Spotify Dataset (Kaggle). 2024. https:\/\/www.kaggle.com\/mrmorj\/dataset-of-songs-in-spotify. (2024)."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41598-021-96912-5"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.1997.581756"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.3389\/fpsyg.2020.582480"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.5555\/1148928.1700950"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.3390\/e23010018"},{"key":"e_1_2_1_43_1","volume-title":"The Shapley value of tuples in query answering. arXiv preprint arXiv:1904.08679","author":"Livshits Ester","year":"2019","unstructured":"Ester Livshits, Leopoldo Bertossi, Benny Kimelfeld, and Moshe Sebag. 2019. The Shapley value of tuples in query answering. arXiv preprint arXiv:1904.08679 (2019)."},{"key":"e_1_2_1_44_1","volume-title":"From local explanations to global understanding with explainable AI for trees. Nature machine intelligence","author":"Lundberg Scott M","year":"2020","unstructured":"Scott M Lundberg, Gabriel Erion, Hugh Chen, Alex DeGrave, Jordan M Prutkin, Bala Nair, Ronit Katz, Jonathan Himmelfarb, Nisha Bansal, and Su-In Lee. 2020. From local explanations to global understanding with explainable AI for trees. Nature machine intelligence, Vol. 2, 1 (2020), 56--67."},{"key":"e_1_2_1_45_1","first-page":"I","article-title":"A Unified Approach to Interpreting Model Predictions","volume":"30","author":"Lundberg Scott M","year":"2017","unstructured":"Scott M Lundberg and Su-In Lee. 2017a. A Unified Approach to Interpreting Model Predictions. Advances in Neural Information Processing Systems 30, I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (Eds.). Curran Associates, Inc., 4765--4774. http:\/\/papers.nips.cc\/paper\/7062-a-unified-approach-to-interpreting-model-predictions.pdf","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_2_1_46_1","unstructured":"Scott M Lundberg and Su-In Lee. 2017b. A Unified Approach to Interpreting Model Predictions. Advances in Neural Information Processing Systems 30. 4765--4774."},{"key":"e_1_2_1_47_1","doi-asserted-by":"crossref","unstructured":"Yuyu Luo Xuedi Qin Nan Tang and Guoliang Li. 2018. DeepEye: Towards Automatic Data Visualization. ICDE.","DOI":"10.1109\/ICDE.2018.00019"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.25080\/Majora-92bf1922-00a"},{"key":"e_1_2_1_49_1","first-page":"1","article-title":"Sampling permutations for shapley value estimation","volume":"23","author":"Mitchell Rory","year":"2022","unstructured":"Rory Mitchell, Joshua Cooper, Eibe Frank, and Geoffrey Holmes. 2022. Sampling permutations for shapley value estimation. Journal of Machine Learning Research, Vol. 23, 43 (2022), 1--46.","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_2_1_50_1","unstructured":"United States Department of Transportation. 2015. 2015 Flight Delays and Cancellations. https:\/\/www.kaggle.com\/usdot\/flight-delays. (2015)."},{"key":"e_1_2_1_51_1","doi-asserted-by":"crossref","unstructured":"Judea Pearl et al. 2009. Causal inference in statistics: An overview. Statistics surveys Vol. 3 (2009) 96--146.","DOI":"10.1214\/09-SS057"},{"key":"e_1_2_1_52_1","unstructured":"SHARQ Github Repository. 2024. https:\/\/anonymous.4open.science\/r\/SHARQ-0EC4. (2024)."},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939778"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v32i1.11491"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.5555\/3463952.3463962"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1007\/s42452-021-04148-9"},{"key":"e_1_2_1_57_1","volume-title":"Petia Radeva, Steffen E Petersen, Karim Lekadir, and Gloria Menegaz.","author":"Salih Ahmed M","year":"2024","unstructured":"Ahmed M Salih, Zahra Raisi-Estabragh, Ilaria Boscolo Galazzo, Petia Radeva, Steffen E Petersen, Karim Lekadir, and Gloria Menegaz. 2024. A Perspective on Explainable Artificial Intelligence Methods: SHAP and LIME. Advanced Intelligent Systems (2024), 2400304."},{"key":"e_1_2_1_58_1","volume-title":"A value for n-person games. Contributions to the Theory of Games 28","author":"LS SHAPLEY.","year":"1953","unstructured":"LS SHAPLEY. 1953. A value for n-person games. Contributions to the Theory of Games 28 (1953), 307--317."},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1515\/9781400881970-018"},{"key":"e_1_2_1_60_1","volume-title":"International Conference on Machine Learning. PMLR, 3145--3153","author":"Shrikumar Avanti","year":"2017","unstructured":"Avanti Shrikumar, Peyton Greenside, and Anshul Kundaje. 2017. Learning important features through propagating activation differences. In International Conference on Machine Learning. PMLR, 3145--3153."},{"key":"e_1_2_1_61_1","volume-title":"DBExplorer: Exploratory Search in Databases. EDBT","author":"Singh Manish","year":"2016","unstructured":"Manish Singh, Michael J Cafarella, and HV Jagadish. 2016. DBExplorer: Exploratory Search in Databases. EDBT (2016)."},{"key":"e_1_2_1_62_1","volume-title":"Future Gener. Comput. Syst.","volume":"13","author":"Srikant R.","year":"1997","unstructured":"R. Srikant and R. Agrawal. 1997. Mining generalized association rules. Future Gener. Comput. Syst., Vol. 13, 2 (1997)."},{"key":"e_1_2_1_63_1","volume-title":"Augmenting visualizations with interactive data facts to facilitate interpretation and communication","author":"Srinivasan Arjun","year":"2018","unstructured":"Arjun Srinivasan, Steven M Drucker, Alex Endert, and John Stasko. 2018. Augmenting visualizations with interactive data facts to facilitate interpretation and communication. IEEE transactions on visualization and computer graphics, Vol. 25, 1 (2018), 672--681."},{"key":"e_1_2_1_64_1","volume-title":"Explaining prediction models and individual predictions with feature contributions. Knowledge and information systems","author":"\u0160trumbelj Erik","year":"2014","unstructured":"Erik \u0160trumbelj and Igor Kononenko. 2014. Explaining prediction models and individual predictions with feature contributions. Knowledge and information systems, Vol. 41, 3 (2014), 647--665."},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10257-016-0329-4"},{"key":"e_1_2_1_66_1","volume-title":"International Conference on Machine Learning. PMLR, 3319--3328","author":"Sundararajan Mukund","year":"2017","unstructured":"Mukund Sundararajan, Ankur Taly, and Qiqi Yan. 2017. Axiomatic attribution for deep networks. In International Conference on Machine Learning. PMLR, 3319--3328."},{"key":"e_1_2_1_67_1","unstructured":"Pang-Ning Tan and Vipin Kumar. 2000. Interestingness measures for association patterns: A perspective. (2000)."},{"key":"e_1_2_1_68_1","volume-title":"Discovering symptom patterns of COVID-19 patients using association rule mining. Computers in biology and medicine","author":"Tandan Meera","year":"2021","unstructured":"Meera Tandan, Yogesh Acharya, Suresh Pokharel, and Mohan Timilsina. 2021. Discovering symptom patterns of COVID-19 patients using association rule mining. Computers in biology and medicine, Vol. 131 (2021), 104249."},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3035922"},{"key":"e_1_2_1_70_1","unstructured":"U.S. Census Bureau. 2024. Annual Social and Economic Supplements. https:\/\/www.census.gov\/data\/datasets\/time-series\/demo\/cps\/cps-asec.html. (2024)."},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFVIS.1999.801866"},{"key":"e_1_2_1_72_1","volume-title":"Voyager: Exploratory analysis via faceted browsing of visualization recommendations. TVCG","author":"Wongsuphasawat Kanit","year":"2016","unstructured":"Kanit Wongsuphasawat, Dominik Moritz, Anushka Anand, Jock Mackinlay, Bill Howe, and Jeffrey Heer. 2016. Voyager: Exploratory analysis via faceted browsing of visualization recommendations. TVCG (2016)."},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536354.2536356"},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1109\/BIFE.2009.110"},{"key":"e_1_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04174-7_45"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3709726","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3709726","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T18:22:51Z","timestamp":1774981371000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3709726"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2,10]]},"references-count":75,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,2,10]]}},"alternative-id":["10.1145\/3709726"],"URL":"https:\/\/doi.org\/10.1145\/3709726","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,2,10]]}}}