Relative Keys: Putting Feature Explanation into Context

Summary: Relative keys offer context-aware explanations with bounded conformity, merging formal guarantees with fast, model-agnostic reasoning. CCE computes them without model access; finding most succinct relative keys is NP-complete; batch/online algorithms yield two orders of magnitude speedups on 9 datasets with 7 explainers. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h1257a22b9439f3bb
Venue: SIGMOD
Year: 2024
Pagerank: 4.9793485e-05
Overall Rank: 11,504 | 22.66%
DOI: 10.1145/3639263

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Shuai An (University of Edinburgh)
2. Yang Cao (University of Edinburgh)

BibTeX Citation

@inproceedings{an_sigmod24,
        title = {{Relative Keys: Putting Feature Explanation into Context}},
        author = {An, Shuai and Cao, Yang},
        series = {{SIGMOD} '24},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3639263},
        url = {https://dl.acm.org/doi/10.1145/3639263},
        year = {2024}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
11,515	Counterfactual Explanation at Will, with Zero Privacy Leakage	2024	SIGMOD	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
17	Provenance Semirings	2007	PODS	0.00059752575
134	Deep Entity Matching with Pre-Trained Language Models	2021	VLDB	0.00030043481
158	Deep Learning for Entity Matching: A Design Space Exploration	2018	SIGMOD	0.00028046388
189	Scorpion: Explaining Away Outliers in Aggregate Queries	2013	VLDB	0.00025840026
578	The Complexity of Causality and Responsibility for Query Answers and non-Answers	2011	VLDB	0.00016096504
670	A Formal Approach to Finding Explanations for Database Queries	2014	SIGMOD	0.00014954494
878	Interpretable and Informative Explanations of Outcomes	2015	VLDB	0.00013302631
2,222	Explaining Query Answers with Explanation-Ready Databases	2016	VLDB	8.8109051e-05
3,514	Sketching Linear Classifiers over Data Streams	2018	SIGMOD	7.2429609e-05
4,739	Going Beyond Provenance: Explaining Query Answers with Pattern-based Counterbalances	2019	SIGMOD	6.4441962e-05
9,491	Computing Rule-Based Explanations by Leveraging Counterfactuals	2023	VLDB	5.1708619e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,134	Regularizing Conjunctive Features for Classification	2019	PODS
2	878	Interpretable and Informative Explanations of Outcomes	2015	VLDB
3	11,515	Counterfactual Explanation at Will, with Zero Privacy Leakage	2024	SIGMOD
4	10,739	Database Views as Explanations for Relational Deep Learning	2026	VLDB
5	7,543	Determining the Relative Accuracy of Attributes	2013	SIGMOD
6	1,847	Nearest Neighbor Classifiers over Incomplete Information: From Certain Answers to Certain Predictions	2021	VLDB
7	4,548	Explaining Link Prediction Systems based on Knowledge Graph Embeddings	2022	SIGMOD
8	10,069	On Concise Set of Relative Candidate Keys	2014	VLDB
9	9,491	Computing Rule-Based Explanations by Leveraging Counterfactuals	2023	VLDB
10	10,101	Explaining k-Nearest Neighbors: Abductive and Counterfactual Explanations	2025	PODS