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: 6879
Venue: SIGMOD
Year: 2024
Pagerank: 5.093636e-05
Overall Rank: 11,157 | 23.46%
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,170	Counterfactual Explanation at Will, with Zero Privacy Leakage	2024	SIGMOD	5.093636e-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.00059843817
141	Deep Entity Matching with Pre-Trained Language Models	2021	VLDB	0.0002964847
176	Deep Learning for Entity Matching: A Design Space Exploration	2018	SIGMOD	0.00027191081
191	Scorpion: Explaining Away Outliers in Aggregate Queries	2013	VLDB	0.00026096009
605	The Complexity of Causality and Responsibility for Query Answers and non-Answers	2011	VLDB	0.00015839628
663	A Formal Approach to Finding Explanations for Database Queries	2014	SIGMOD	0.00015174751
858	Interpretable and Informative Explanations of Outcomes	2015	VLDB	0.0001356511
2,195	Explaining Query Answers with Explanation-Ready Databases	2016	VLDB	8.9713779e-05
3,445	Sketching Linear Classifiers over Data Streams	2018	SIGMOD	7.4089141e-05
4,638	Going Beyond Provenance: Explaining Query Answers with Pattern-based Counterbalances	2019	SIGMOD	6.5919801e-05
9,313	Computing Rule-Based Explanations by Leveraging Counterfactuals	2023	VLDB	5.289545e-05

Semantically Similar Papers

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