{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T23:40:03Z","timestamp":1755906003050,"version":"3.44.0"},"reference-count":56,"publisher":"Association for Computing Machinery (ACM)","issue":"2","funder":[{"DOI":"10.13039\/501100006374","name":"Agencia Nacional de Investigaci\u00f3n y Desarrollo","doi-asserted-by":"publisher","award":["FB210017","FB210005","1221460","1250060","ICN17002"],"award-info":[{"award-number":["FB210017","FB210005","1221460","1250060","ICN17002"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100006374","name":"NSF","doi-asserted-by":"publisher","award":["DMS-2434625"],"award-info":[{"award-number":["DMS-2434625"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,6,9]]},"abstract":"<jats:p>\n            Despite the wide use of\n            <jats:italic toggle=\"yes\">k<\/jats:italic>\n            -Nearest Neighbors as classification models, their explainability properties remain poorly understood from a theoretical perspective. While nearest neighbors classifiers offer interpretability from a ''data perspective'', in which the classification of an input vector x is explained by identifying the vectors v\n            <jats:sub>1<\/jats:sub>\n            , ..., v\n            <jats:sub>k<\/jats:sub>\n            in the training set that determine the classification of x, we argue that such explanations can be impractical in high-dimensional applications, where each vector has hundreds or thousands of features and it is not clear what their relative importance is. Hence, we focus on understanding nearest neighbor classifications through a ''feature perspective'', in which the goal is to identify how the values of the features in x affect its classification. Concretely, we study abductive explanations such as ''minimum sufficient reasons'', which correspond to sets of features in x that are enough to guarantee its classification, and counterfactual explanations based on the minimum distance feature changes one would have to perform in x to change its classification. We present a detailed landscape of positive and negative complexity results for counterfactual and abductive explanations, distinguishing between discrete and continuous feature spaces, and considering the impact of the choice of distance function involved. Finally, we show that despite some negative complexity results, Integer Quadratic Programming and SAT solving allow for computing explanations in practice.\n          <\/jats:p>","DOI":"10.1145\/3725234","type":"journal-article","created":{"date-parts":[[2025,6,9]],"date-time":"2025-06-09T15:20:31Z","timestamp":1749482431000},"page":"1-26","source":"Crossref","is-referenced-by-count":0,"title":["Explaining\n            <i>k<\/i>\n            -Nearest Neighbors: Abductive and Counterfactual Explanations"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2293-2653","authenticated-orcid":false,"given":"Pablo","family":"Barcel\u00f3","sequence":"first","affiliation":[{"name":"Pontifical Catholic University of Chile, Santiago, Chile"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9956-9023","authenticated-orcid":false,"given":"Alexander","family":"Kozachinskiy","sequence":"additional","affiliation":[{"name":"CENIA, Santiago, Chile"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2615-6455","authenticated-orcid":false,"given":"Miguel","family":"Romero","sequence":"additional","affiliation":[{"name":"Pontifical Catholic University of Chile, Santiago, Chile"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2295-1299","authenticated-orcid":false,"given":"Bernardo","family":"Subsercaseaux","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2049-6467","authenticated-orcid":false,"given":"Jos\u00e9","family":"Verschae","sequence":"additional","affiliation":[{"name":"Pontifical Catholic University of Chile, Santiago, Chile"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,6,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"Pankaj K. Agarwal Boris Aronov Sariel Har-Peled Jeff M. Phillips Ke Yi and Wuzhou Zhang. 2013. Nearest neighbor searching under uncertainty II. In PODS. ACM 115--126.","DOI":"10.1145\/2463664.2465219"},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Pankaj K. Agarwal Alon Efrat Swaminathan Sankararaman and Wuzhou Zhang. 2012. Nearest-neighbor searching under uncertainty. In PODS. ACM 225--236.","DOI":"10.1145\/2213556.2213588"},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"Pankaj K. Agarwal Kyle Fox Kamesh Munagala and Abhinandan Nath. 2016. Parallel Algorithms for Constructing Range and Nearest-Neighbor Searching Data Structures. In PODS. ACM 429--440.","DOI":"10.1145\/2902251.2902303"},{"key":"e_1_2_1_4_1","unstructured":"Marcelo Arenas Pablo Barcel\u00f3 Miguel A. Romero Orth and Bernardo Subercaseaux. 2022. On Computing Probabilistic Explanations for Decision Trees. In NeurIPS."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.inffus.2019.12.012"},{"key":"e_1_2_1_6_1","volume-title":"On the computation of counterfactual explanations--A survey. arXiv preprint arXiv:1911.07749","author":"Artelt Andr\u00e9","year":"2019","unstructured":"Andr\u00e9 Artelt and Barbara Hammer. 2019. On the computation of counterfactual explanations--A survey. arXiv preprint arXiv:1911.07749 (2019)."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.datak.2022.102088"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Gilles Audemard Jean-Marie Lagniez and Pierre Marquis. 2024. On the Computation of Contrastive Explanations for Boosted Regression Trees. In ECAI. 1083--1091.","DOI":"10.3233\/FAIA240600"},{"key":"e_1_2_1_9_1","unstructured":"Pablo Barcel\u00f3 Mika\u00ebl Monet Jorge P\u00e9rez and Bernardo Subercaseaux. 2020. Model Interpretability through the lens of Computational Complexity. In NeurIPS. 15487--15498."},{"key":"e_1_2_1_10_1","unstructured":"Shahaf Bassan Guy Amir and Guy Katz. 2024. Local vs. Global Interpretability: A Computational Complexity Perspective. arxiv: 2406.02981 [cs.LG] https:\/\/arxiv.org\/abs\/2406.02981"},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","unstructured":"Kevin S. Beyer Jonathan Goldstein Raghu Ramakrishnan and Uri Shaft. 1999. When Is ''Nearest Neighbor'' Meaningful?. In ICDT. 217--235.","DOI":"10.1007\/3-540-49257-7_15"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3--319--25388--6"},{"key":"e_1_2_1_13_1","unstructured":"Guy Blanc Jane Lange and Li-Yang Tan. 2021. Provably efficient succinct and precise explanations. In NeurIPS A. Beygelzimer Y. Dauphin P. Liang and J. Wortman Vaughan (Eds.)."},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","unstructured":"Claudio Contardo Ricardo Fukasawa Louis-Martin Rousseau and Thibaut Vidal. 2024. Optimal Counterfactual Explanations for k-Nearest Neighbors Using Mathematical Optimization and Constraint Programming. In ISCO. 318--331.","DOI":"10.1007\/978-3-031-60924-4_24"},{"volume-title":"Logic for Explainable AI","author":"Darwiche Adnan","key":"e_1_2_1_15_1","unstructured":"Adnan Darwiche. 2023. Logic for Explainable AI. In LICS. IEEE, 1--11."},{"key":"e_1_2_1_16_1","volume-title":"On The Reasons Behind Decisions. CoRR","author":"Darwiche Adnan","year":"2020","unstructured":"Adnan Darwiche and Auguste Hirth. 2020. On The Reasons Behind Decisions. CoRR, Vol. abs\/2002.09284 (2020). https:\/\/arxiv.org\/abs\/2002.09284"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/MSP.2012.2211477"},{"key":"e_1_2_1_18_1","unstructured":"Matthijs Douze Alexandr Guzhva Chengqi Deng Jeff Johnson Gergely Szilvasy Pierre-Emmanuel Mazar\u00e9 Maria Lomeli Lucas Hosseini and Herv\u00e9 J\u00e9gou. 2024. The Faiss library. (2024). arxiv: 2401.08281 [cs.LG]"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977066.6"},{"key":"e_1_2_1_20_1","first-page":"1","article-title":"Certifiable Robustness for Nearest Neighbor Classifiers","volume":"6","author":"Fan Austen Z.","year":"2022","unstructured":"Austen Z. Fan and Paraschos Koutris. 2022. Certifiable Robustness for Nearest Neighbor Classifiers. In ICDT (LIPIcs). 6:1--6:20.","journal-title":"ICDT (LIPIcs)."},{"key":"e_1_2_1_21_1","volume-title":"Improved search of relevant points for nearest-neighbor classification. arXiv preprint arXiv:2203.03567","author":"Flores-Velazco Alejandro","year":"2022","unstructured":"Alejandro Flores-Velazco. 2022. Improved search of relevant points for nearest-neighbor classification. arXiv preprint arXiv:2203.03567 (2022)."},{"key":"e_1_2_1_22_1","volume-title":"ICML","volume":"202","author":"Forel Alexandre","year":"2023","unstructured":"Alexandre Forel, Axel Parmentier, and Thibaut Vidal. 2023. Explainable Data-Driven Optimization: From Context to Decision and Back Again. In ICML, Vol. 202. PMLR, 10170--10187."},{"key":"e_1_2_1_23_1","first-page":"1770","article-title":"Counterfactual explanations and how to find them: literature review and benchmarking","volume":"36","author":"Guidotti Riccardo","year":"2022","unstructured":"Riccardo Guidotti. 2022. Counterfactual explanations and how to find them: literature review and benchmarking. Data Mining and Knowledge Discovery, Vol. 36, 5 (2022), 1770--182.","journal-title":"Data Mining and Knowledge Discovery"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3236009"},{"key":"e_1_2_1_25_1","unstructured":"Gurobi Optimization LLC. 2024. Gurobi Optimizer Reference Manual. https:\/\/www.gurobi.com"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.engappai.2023.107829"},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","unstructured":"Yunqiu Han Yizuo Chen and Adnan Darwiche. 2023. On the Complexity of Counterfactual Reasoning. In IJCAI. ijcai.org 5676--5684.","DOI":"10.24963\/ijcai.2023\/630"},{"key":"e_1_2_1_28_1","volume-title":"Keim","author":"Hinneburg Alexander","year":"2000","unstructured":"Alexander Hinneburg, Charu C. Aggarwal, and Daniel A. Keim. 2000. What Is the Nearest Neighbor in High Dimensional Spaces?. In VLDB. 506--515."},{"volume-title":"Fundamentals of Convex Analysis","author":"Hiriart-Urruty Jean-Baptiste","key":"e_1_2_1_29_1","unstructured":"Jean-Baptiste Hiriart-Urruty and Claude Lemar\u00e9chal. 2001. Fundamentals of Convex Analysis. Springer, Berlin, Heidelberg."},{"key":"e_1_2_1_30_1","doi-asserted-by":"crossref","unstructured":"Xuanxiang Huang Yacine Izza Alexey Ignatiev and Jo ao Marques-Silva. 2021. On Efficiently Explaining Graph-Based Classifiers. In KR. 356--367.","DOI":"10.24963\/kr.2021\/34"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3-030--80223--3_18"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3-030--77091--4_21"},{"key":"e_1_2_1_33_1","doi-asserted-by":"crossref","unstructured":"Alexey Ignatiev Nina Narodytska and Jo ao Marques-Silva. 2019. Abduction-Based Explanations for Machine Learning Models. In AAAI. 1511--1519.","DOI":"10.1609\/aaai.v33i01.33011511"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ijar.2023.108939"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1613\/jair.1.13575"},{"key":"e_1_2_1_36_1","unstructured":"Yacine Izza Alexey Ignatiev Nina Narodytska Martin C. Cooper and J. Marques-Silva. 2021. Efficient Explanations With Relevant Sets. ArXiv Vol. abs\/2106.00546 (2021)."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","unstructured":"Yacine Izza Alexey Ignatiev Nina Narodytska Martin C. Cooper and Joao Marques-Silva. 2022b. Provably Precise Succinct and Efficient Explanations for Decision Trees. https:\/\/doi.org\/10.48550\/ARXIV.2205.09569","DOI":"10.48550\/ARXIV.2205.09569"},{"key":"e_1_2_1_38_1","volume-title":"When Large Language Models Meet Vector Databases: A Survey. CoRR","volume":"2402","author":"Jing Zhi","year":"2024","unstructured":"Zhi Jing, Yongye Su, Yikun Han, Bo Yuan, Haiyun Xu, Chunjiang Liu, Kehai Chen, and Min Zhang. 2024. When Large Language Models Meet Vector Databases: A Survey. CoRR, Vol. abs\/2402.01763 (2024)."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/0041--5553(80)90098--1"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2024.06.004"},{"key":"e_1_2_1_41_1","unstructured":"Harry R Lewis and Christos H Papadimitriou. 1997. Elements of the Theory of Computation."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3236386.3241340"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","unstructured":"Marica Magagnini Emilio Carrizosa and Renato De Leone. 2025. Nearest Neighbors Counterfactuals. In Machine Learning Optimization and Data Science Giuseppe Nicosia Varun Ojha Sven Giesselbach M. Panos Pardalos and Renato Umeton (Eds.). Springer Nature Switzerland Cham 193--208. https:\/\/doi.org\/10.1007\/978--3-031--82481--4_14","DOI":"10.1007\/978--3-031--82481--4_14"},{"key":"e_1_2_1_44_1","unstructured":"Jo ao Marques-Silva Thomas Gerspacher Martin C. Cooper Alexey Ignatiev and Nina Narodytska. 2020. Explaining Naive Bayes and Other Linear Classifiers with Polynomial Time and Delay. In NeurIPS."},{"key":"e_1_2_1_45_1","unstructured":"Joao Marques-Silva Thomas Gerspacher Martin C Cooper Alexey Ignatiev and Nina Narodytska. 2021. Explanations for Monotonic Classifiers.. In ICML. 7469--7479."},{"key":"e_1_2_1_46_1","unstructured":"Jo ao Marques-Silva Thomas Gerspacher Martin C. Cooper Alexey Ignatiev and Nina Narodytska. 2021. Explanations for Monotonic Classifiers. In ICML. 7469--7479."},{"key":"e_1_2_1_47_1","doi-asserted-by":"crossref","unstructured":"Joao Marques-Silva and Alexey Ignatiev. 2022. Delivering Trustworthy AI through Formal XAI. In AAAI.","DOI":"10.1609\/aaai.v36i11.21499"},{"key":"e_1_2_1_48_1","unstructured":"Christoph Molnar. 2022. Interpretable Machine Learning (2 ed.). https:\/\/christophm.github.io\/interpretable-ml-book"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-65627-9_6"},{"key":"e_1_2_1_50_1","volume-title":"Anchors: High-Precision Model-Agnostic Explanations. In AAAI. 1527--1535.","author":"Ribeiro Marco T\u00falio","year":"2018","unstructured":"Marco T\u00falio Ribeiro, Sameer Singh, and Carlos Guestrin. 2018. Anchors: High-Precision Model-Agnostic Explanations. In AAAI. 1527--1535."},{"key":"e_1_2_1_51_1","volume-title":"Reducing Nearest Neighbor Training Sets Optimally and Exactly. arXiv preprint arXiv:2302.02132","author":"Rohrer Josiah","year":"2023","unstructured":"Josiah Rohrer and Simon Weber. 2023. Reducing Nearest Neighbor Training Sets Optimally and Exactly. arXiv preprint arXiv:2302.02132 (2023)."},{"volume-title":"Nearest Neighbor Queries","author":"Roussopoulos Nick","key":"e_1_2_1_52_1","unstructured":"Nick Roussopoulos, Stephen Kelley, and Fr\u00e9d\u00e9ic Vincent. 1995. Nearest Neighbor Queries. In SIGMOD. ACM Press, 71--79."},{"volume-title":"Theory of Linear and Integer Programming","author":"Schrijver Alexander","key":"e_1_2_1_53_1","unstructured":"Alexander Schrijver. 1998. Theory of Linear and Integer Programming. John Wiley & Sons, Chichester."},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.5555\/3304652.3304719"},{"key":"e_1_2_1_55_1","doi-asserted-by":"crossref","unstructured":"Yufei Tao Ke Yi Cheng Sheng and Panos Kalnis. 2009. Quality and efficiency in high dimensional nearest neighbor search. In SIGMOD. ACM 563--576.","DOI":"10.1145\/1559845.1559905"},{"key":"e_1_2_1_56_1","first-page":"351","article-title":"The Computational Complexity of Understanding Binary Classifier Decisions","volume":"70","author":"W\u00e4ldchen Stephan","year":"2021","unstructured":"Stephan W\u00e4ldchen, Jan MacDonald, Sascha Hauch, and Gitta Kutyniok. 2021. The Computational Complexity of Understanding Binary Classifier Decisions. J. Artif. Intell. Res., Vol. 70 (2021), 351--387.","journal-title":"J. Artif. Intell. Res."}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3725234","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T23:18:40Z","timestamp":1755904720000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3725234"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,9]]},"references-count":56,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,6,9]]}},"alternative-id":["10.1145\/3725234"],"URL":"https:\/\/doi.org\/10.1145\/3725234","relation":{},"ISSN":["2836-6573"],"issn-type":[{"type":"electronic","value":"2836-6573"}],"subject":[],"published":{"date-parts":[[2025,6,9]]}}}