REVIEW 2 major objections 5 minor 1 cited by
Predicate-Conditional Conformalized Answer Sets for Knowledge Graph Embeddings
T0 review · 2 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read CondKGCP approximates predicate-conditional coverage for knowledge-graph link prediction by merging similar predicates and applying a dual score-and-rank calibration, keeping per-group coverage close to the target confidence while…
desk verdict CondKGCP's recipe is empirically promising, but its headline coverage bound is not proven because the rank cutoff is estimated from the same calibration data used for the score threshold. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The machinery is a dual calibration schema operating on merged predicate groups. First, Algorithm 1 partitions predicates: predicates with at least $\phi$ calibration triples seed groups, and low-data predicates are assigned to the group of the most similar predicate under negative Manhattan distance of their embedding vectors. Then the score threshold $\hat{s}_{\epsilon'(g)}(T_g)$ is computed by conformal quantile on group $g$, and the rank threshold $\hat{k}(g) = \min\{k : \epsilon^k_g < \epsilon\}$ filters to top-ranked entities before the score threshold is applied. The parameter $\gamma$ connects the two: $\epsilon'(g) = \epsilon - \gamma \epsilon^{\hat{k}(g)}_g$. What carries the size reduction is the observation that high-rank entities are disproportionately responsible for large sets, so cutting them before score thresholding keeps coverage while trimming size.
What would settle it
Hold out a separate set to choose the rank cutoff, keep the score threshold on the original calibration set, and measure per-group coverage; if coverage falls below the Proposition 1 lower bound, the shared calibration set is supporting the guarantee and the bound is not finite-sample valid as stated.
Extended reading notes
Core claim
CondKGCP claims that predicate-conditional coverage, not just marginal coverage, can be approximated for knowledge graph link prediction. For any merged predicate group $g$, the probability that the true answer lies in the prediction set satisfies the lower bound $p \geq 1 - \epsilon - (1-\gamma)\epsilon^{\hat{k}(g)}_g$ and, under a no-ties condition, the upper bound $p \leq 1 - \epsilon + \gamma\epsilon^{\hat{k}(g)}_g + \frac{1}{|T_g|+1}$. Here $\epsilon^{\hat{k}(g)}_g$ is the miscoverage probability of the top-$\hat{k}(g)$ rank set in group $g$, and $\gamma$ distributes allowed error between the rank and score calibrations. The dual calibration first keeps entities ranked within top $\hat{k}(g)$, then applies a score quantile threshold with adjusted level $\epsilon'(g) = \epsilon - \gamma\epsilon^{\hat{k}(g)}_g$. The paper further claims, via Corollary 2, that this rank cutoff reduces expected prediction-set size whenever the probability mass of entities passing both thresholds is no larger than the mass passing the score threshold alone, a condition it verifies empirically. With these two pieces, CondKGCP is claimed to deliver per-group coverage close to $1-\epsilon$ with sets much smaller than Mondrian-style per-predicate conformal prediction.
Load-bearing premise
The construction assumes calibration triples are exchangeable, that predicates with similar vector representations have similar score distributions, and that the rank-miscoverage rate estimated from the calibration set is the true rate even though the same data chooses the rank cutoff and the score threshold.
Editorial extensions
If this is right
- For each merged predicate group $g$, if the calibration assumptions hold, coverage falls within controlled bounds of the target $1-\epsilon$ rather than only on average over all queries.
- The rank cutoff $\hat{k}(g)$ chosen as the smallest $k$ with $\epsilon^k_g < \epsilon$, combined with the adjusted score threshold $\epsilon'(g) = \epsilon - \gamma\epsilon^{\hat{k}(g)}_g$, keeps prediction sets smaller than per-predicate MCP while achieving coverage-gap values near MCP's empirical lower bound.
- When the condition in Equation (13) holds, the dual calibration reduces expected prediction-set size relative to score-threshold-only subgroup conformal prediction.
- The same construction extends beyond predicates to other conditioning structures such as entity types and to embedding-based query answering, as the paper states in its discussion.
- At high confidence levels above $1-\epsilon = 0.95$, prediction sets grow sharply because base KGE models rarely rank true answers beyond their top-10 accuracy, so the method's advantage persists but accurate base models are needed.
Reading between the lines
- A natural safeguard, not tested in the paper, is to estimate $\epsilon^k_g$ on a separate holdout set or to use a union bound over candidate ranks; this would convert the heuristic double-calibration into a rigorously finite-sample valid procedure.
- The merging step's reliance on embedding-vector similarity is a testable design choice: using nonconformity-score quantile similarity instead of negative Manhattan distance could be compared directly to see which better preserves per-group coverage when calibration data is scarce.
- The same dual-calibration idea could be applied to other imbalanced subgroup structures in knowledge graphs, such as entity types or temporal intervals, wherever ranks are informative and group sizes are small.
- If the condition in Equation (13) fails for some groups, rank calibration can in principle enlarge rather than shrink sets, so monitoring $\sigma_g$ per group would be a useful deployment diagnostic.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes CondKGCP, a method for uncertainty quantification in knowledge graph embedding link prediction. CondKGCP merges predicates with similar vector representations to form larger calibration groups, then applies a dual calibration schema: a conformal score threshold and an additional rank threshold. The authors claim a group-conditional coverage guarantee (Proposition 1), a size-reduction guarantee under a verifiable condition (Corollary 1), and empirical improvements over KGCP, MCP, CLUSTERCP, APS, and RAPS on WN18 and FB15k across six KGE models. The abstract and introduction frame the contribution as approximating predicate-conditional coverage while maintaining compact prediction sets.
Significance. Conditional coverage guarantees for KGE link prediction would be valuable, and the paper's empirical study is broad: six KGE models, two datasets, ablations, hyperparameter analyses, and runtime comparisons. If Proposition 1 were a valid finite-sample coverage statement, the method would be a practically useful way to approximate predicate-level coverage with compact sets. However, the central theoretical guarantee is not established as written: the proof treats a rank miscoverage quantity estimated from the same calibration data as if it were a known constant. As a result, the advertised coverage guarantee and the size-reduction claim are not supported by the proof. The empirical CovGap results are suggestive but measure a different quantity than the guarantee that is proved.
major comments (2)
- [§4.2, Eq. (8)–(9); Appendix A, Eq. (18)–(23)] Proposition 1 is not a valid finite-sample coverage bound as stated. The proof treats the rank miscoverage probability eps^khat_g as the known true conditional probability P(rank > khat(g) | pred(q) in g), but khat(g) is selected in Eq. (9) from estimates of eps^k_g computed on T_g, and T_g is the same calibration set used to compute the score quantile s_hat_{eps'(g)}(T_g) in Eq. (7). Because khat(g) and eps^khat_g are random and data-dependent, substituting them into the decomposition in Appendix A is circular; a spuriously small empirical rank-miscoverage on a small part g would yield an over-optimistic adjusted level eps'(g) and an under-covering prediction set. No holdout, uniform bound over k, or high-confidence correction is provided. The Limitation section (Sec. 8) acknowledges the i.i.d. and similarity assumptions but does not mention this double-use problem.
- [§4.1, Algorithm 1; §6.2, Eq. (14)–(15)] There is a mismatch between the guarantee and the evaluation metric. Proposition 1 provides coverage conditional on the merged part g, not on individual predicates, while the headline claim of predicate-conditional coverage is measured by CovGap computed per predicate in Eq. (14)–(15). A group-level threshold can be dominated by the frequent predicates in the group, so per-predicate coverage is not controlled by the proposition. The paper should either state the guarantee as group-conditional and evaluate at the group level, or provide a bound on the per-predicate deviation; as written, the theoretical claim and the main empirical claim concern different objects.
minor comments (5)
- [§5 vs. Appendix A] The corollary is numbered Corollary 1 in the main text and Corollary 2 in Appendix A; renumber for consistency.
- [Appendix A, upper-bound proof] In the last line of the upper-bound proof, '|I_g|+1' should be '|T_g|+1'.
- [§6.1, Eq. (17) and Table 1] The metric is called Efficiency Rate (ER) in Eq. (17) but the tables report 'EF'; use one name consistently.
- [§6.2, Eq. (16)] The notation '1/T_test[{r}]' in Eq. (16) should be '1/|T_test[{r}]|', and the summation index and set should be made explicit.
- [§5, Corollary 1 and Appendix C, Table 3] The size-reduction result is conditional on Eq. (13), and Appendix C verifies the condition only empirically, with CSR below 100% in several configurations (e.g., 91.7% for TransE and DistMult on WN18); the main text should state this limitation more prominently rather than saying that rank calibration 'always reduces' the expected size.
Circularity Check
Proposition 1's coverage bound embeds the rank-miscoverage rate epsilon^{khat(g)}_g, fitted from the same calibration group T_g, into the conformal quantile guarantee as if it were a known population parameter.
-
fitted input called prediction
[Section 4.2 (Rank Calibration, Eqs. 8-9); Section 5 Proposition 1 (Eq. 10); Appendix A proof (Eqs. 20-23)]
"We define the miscoverage error of top-k prediction set ... epsilon^k_g = P(rank_{Mθ}(q,e) > k | pred(q) in g). ... we choose khat(g) = min{k : epsilon^k_g < epsilon}. ... Suppose that the rank threshold for part g is khat(g) and epsilon^{khat(g)}_g is its corresponding miscoverage error ... we set epsilon'(g) = epsilon - gamma * epsilon^{khat(g)}_g."
The rank threshold khat(g) is selected using the calibration group T_g, so khat(g) and the associated epsilon^{khat(g)}_g are data-dependent quantities estimated from the same triples used to compute the score threshold in Eq. (7). The proof of Proposition 1 then invokes the standard MCP quantile guarantee P(S <= s_{epsilon'(g)}(T_g)) >= 1 - epsilon'(g) with epsilon'(g) = epsilon - gamma * epsilon^{khat(g)}_g, treating this random, calibration-dependent error level as a fixed constant. Exchangeability-based conformal guarantees are valid for a pre-specified error level; they do not automatically hold when the error level is estimated from the calibration set itself. No holdout split, union bound over k, or bound on the estimation error of epsilon^k_g is provided.
full rationale
The central circular step is the proof of Proposition 1. The method chooses khat(g) = min{k : epsilon^k_g < epsilon} within each calibration group T_g (Section 4.2), so the realized khat(g) and the empirical rank-miscoverage rate are functions of the same T_g that produces the conformal score threshold in Eq. (7). The proof then applies the MCP guarantee with epsilon'(g) = epsilon - gamma * epsilon^{khat(g)}_g as if this were a fixed, pre-specified error level, but the standard exchangeability argument does not cover a data-dependent error level. This is a fitted input (the rank-miscoverage rate, plus the threshold derived from it) being presented as a theoretical coverage guarantee. The empirical comparisons against KGCP, MCP, CLUSTERCP, APS, and RAPS on WN18/FB15k provide external evidence that the construction can be practically useful, and self-citations to Zhu et al. (2025) are not the load-bearing issue here; the load-bearing issue is the unaccounted double use of T_g. Separately, the size-reduction result (Corollary 2) is conditional on Eq. (13), and Appendix C shows the condition is only empirically verified and fails for some groups (e.g., CSR 91.7% for TransE-WN18 and DistMult-WN18), so that result is not an unconditional guarantee either, though this is an empirically checked assumption rather than a circular reduction. Section 8's limitation discussion mentions i.i.d. data and the predicate-similarity assumption but does not acknowledge this double-use problem in the proof.
Assumptions & free parameters
free parameters (3)
- gamma =
0.01 or 0.1 (tuned from [0.01, 0.1, 0.5])
- phi =
20, 50, or 100 (tuned from [20, 50, 100, 200])
- khat(g) =
data-dependent per group
assumptions (3)
- standard math Exchangeability of calibration and test triples within each merged group
- domain assumption Similarity of predicate vector representations implies similarity of nonconformity score distributions
- ad hoc to paper The estimated rank miscoverage rate eps^khat_g equals the true conditional miscoverage probability
Cite this review
Pith. "Pith review of Predicate-Conditional Conformalized Answer Sets for Knowledge Graph Embeddings." pith.science (2026). https://pith.science/paper/JY3I3PED
@misc{pith2026250516877,
author = {Pith},
title = {Pith review of: Predicate-Conditional Conformalized Answer Sets for Knowledge Graph Embeddings},
year = {2026},
howpublished = {\url{https://pith.science/paper/JY3I3PED}},
note = {Machine review of arXiv:2505.16877}
}
read the original abstract
Uncertainty quantification in Knowledge Graph Embedding (KGE) methods is crucial for ensuring the reliability of downstream applications. A recent work applies conformal prediction to KGE methods, providing uncertainty estimates by generating a set of answers that is guaranteed to include the true answer with a predefined confidence level. However, existing methods provide probabilistic guarantees averaged over a reference set of queries and answers (marginal coverage guarantee). In high-stakes applications such as medical diagnosis, a stronger guarantee is often required: the predicted sets must provide consistent coverage per query (conditional coverage guarantee). We propose CondKGCP, a novel method that approximates predicate-conditional coverage guarantees while maintaining compact prediction sets. CondKGCP merges predicates with similar vector representations and augments calibration with rank information. We prove the theoretical guarantees and demonstrate empirical effectiveness of CondKGCP by comprehensive evaluations.
Figures
Figures from the paper (3 more)
Forward citations
Cited by 1 Pith paper
-
Direct Prediction Set Minimization via Bilevel Conformal Classifier Training
DPSM reformulates conformal training as a bilevel problem with quantile regression in the lower level and claims an O(1/sqrt n) learning bound, cutting prediction set size by about 20% in experiments.
Reference graph
Works this paper leans on
-
[1]
Anastasios Nikolas Angelopoulos, Stephen Bates, Michael I. Jordan, and Jitendra Malik. 2021. Uncertainty sets for image classifiers using conformal prediction. In ICLR . OpenReview.net
work page 2021
-
[2]
James Bergstra and Yoshua Bengio. 2012. Random search for hyper-parameter optimization. Journal of machine learning research, 13(2)
work page 2012
-
[3]
Russa Biswas, Lucie-Aim \'e e Kaffee, Michael Cochez, Stefania Dumbrava, Theis E Jendal, Matteo Lissandrini, Vanessa Lopez, Eneldo Loza Menc \' a, Heiko Paulheim, Harald Sack, et al. 2023. Knowledge graph embeddings: open challenges and opportunities. Transactions on Graph Data and Knowledge, 1(1):4--1
work page 2023
-
[4]
Antoine Bordes, Nicolas Usunier, Alberto Garcia-Duran, Jason Weston, and Oksana Yakhnenko. 2013. Translating embeddings for modeling multi-relational data. Advances in neural information processing systems, 26
2013
-
[5]
Samuel Broscheit, Daniel Ruffinelli, Adrian Kochsiek, Patrick Betz, and Rainer Gemulla. 2020. L ib KGE - A knowledge graph embedding library for reproducible research. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations, pages 165--174
work page 2020
-
[6]
Tim Dettmers, Pasquale Minervini, Pontus Stenetorp, and Sebastian Riedel. 2018. Convolutional 2d knowledge graph embeddings. In Proceedings of the AAAI conference on artificial intelligence, volume 32
2018
-
[7]
Tiffany Ding, Anastasios Angelopoulos, Stephen Bates, Michael Jordan, and Ryan J Tibshirani. 2024. Class-conditional conformal prediction with many classes. Advances in Neural Information Processing Systems, 36
work page 2024
-
[8]
Rina Foygel Barber, Emmanuel J Candes, Aaditya Ramdas, and Ryan J Tibshirani. 2021. The limits of distribution-free conditional predictive inference. Information and Inference: A Journal of the IMA, 10(2):455--482
work page 2021
Show all 38 references
-
[9]
Shizhu He, Kang Liu, Guoliang Ji, and Jun Zhao. 2015. Learning to represent knowledge graphs with gaussian embedding. In Proceedings of the 24th ACM international on conference on information and knowledge management, pages 623--632
2015
-
[10]
Yunjie He, Daniel Hernandez, Mojtaba Nayyeri, Bo Xiong, Yuqicheng Zhu, Evgeny Kharlamov, and Steffen Staab. 2024. Generating sroi^ - ontologies via knowledge graph query embedding learning. In Proceeding of 27th European Conference on Artificial Intelligence, pages 4279 -- 4286
2024
-
[11]
Yunjie He, Bo Xiong, Daniel Hern \'a ndez, Yuqicheng Zhu, Evgeny Kharlamov, and Steffen Staab. 2025. Dage: Dag query answering via relational combinator with logical constraints. In Proceedings of the ACM on Web Conference 2025, pages 2514--2529
2025
-
[12]
Jing Lei, Max G’Sell, Alessandro Rinaldo, Ryan J Tibshirani, and Larry Wasserman. 2018. Distribution-free predictive inference for regression. Journal of the American Statistical Association, 113(523):1094--1111
2018
-
[13]
Maximilian Nickel, Volker Tresp, and Hans - Peter Kriegel. 2011. A three-way model for collective learning on multi-relational data. In ICML , pages 809--816. Omnipress
2011
-
[14]
OpenAI . 2024. Chatgpt(3.5)[large language model]. https://chat.openai.com
2024
-
[15]
H Ren, W Hu, and J Leskovec. 2020. Query2box: Reasoning over knowledge graphs in vector space using box embeddings. In International Conference on Learning Representations (ICLR)
2020
-
[16]
Yaniv Romano, Matteo Sesia, and Emmanuel Candes. 2020. Classification with valid and adaptive coverage. Advances in Neural Information Processing Systems, 33:3581--3591
2020
-
[17]
Daniel Ruffinelli, Samuel Broscheit, and Rainer Gemulla. 2019. You can teach an old dog new tricks! on training knowledge graph embeddings. In International Conference on Learning Representations
2019
-
[18]
Tara Safavi, Danai Koutra, and Edgar Meij. 2020. Evaluating the calibration of knowledge graph embeddings for trustworthy link prediction. In EMNLP (1) , pages 8308--8321. Association for Computational Linguistics
2020
-
[19]
Apoorv Saxena, Aditay Tripathi, and Partha Talukdar. 2020. Improving multi-hop question answering over knowledge graphs using knowledge base embeddings. In Proceedings of the 58th annual meeting of the association for computational linguistics, pages 4498--4507
2020
-
[20]
Yuanjie Shi, Subhankar Ghosh, Taha Belkhouja, Janardhan Rao Doppa, and Yan Yan. 2024. Conformal prediction for class-wise coverage via augmented label rank calibration. In NeurIPS
2024
-
[21]
Zhiqing Sun, Zhi - Hong Deng, Jian - Yun Nie, and Jian Tang. 2019. Rotate: Knowledge graph embedding by relational rotation in complex space. In ICLR (Poster) . OpenReview.net
2019
-
[22]
Zhu Sun, Jie Yang, Jie Zhang, Alessandro Bozzon, Long-Kai Huang, and Chi Xu. 2018. Recurrent knowledge graph embedding for effective recommendation. In Proceedings of the 12th ACM conference on recommender systems, pages 297--305
2018
-
[23]
Pedro Tabacof and Luca Costabello. 2020. Probability calibration for knowledge graph embedding models. In ICLR . OpenReview.net
2020
-
[24]
Kristina Toutanova and Danqi Chen. 2015. Observed versus latent features for knowledge base and text inference. In Proceedings of the 3rd workshop on continuous vector space models and their compositionality, pages 57--66
2015
-
[25]
Th \'e o Trouillon, Johannes Welbl, Sebastian Riedel, \'E ric Gaussier, and Guillaume Bouchard. 2016. Complex embeddings for simple link prediction. In International conference on machine learning, pages 2071--2080. PMLR
2016
-
[26]
Vladimir Vovk. 2012. Conditional validity of inductive conformal predictors. In Asian conference on machine learning, pages 475--490. PMLR
2012
-
[27]
Vladimir Vovk, Alexander Gammerman, and Glenn Shafer. 2005. Algorithmic learning in a random world, volume 29. Springer
2005
-
[28]
Quan Wang, Zhendong Mao, Bin Wang, and Li Guo. 2017. Knowledge graph embedding: A survey of approaches and applications. IEEE transactions on knowledge and data engineering, 29(12):2724--2743
2017
-
[29]
Bo Xiong, Shichao Zhu, Mojtaba Nayyeri, Chengjin Xu, Shirui Pan, Chuan Zhou, and Steffen Staab. 2022. Ultrahyperbolic knowledge graph embeddings. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 2130--2139
2022
-
[30]
Wenhan Xiong, Mo Yu, Shiyu Chang, Xiaoxiao Guo, and William Yang Wang. 2018. One-shot relational learning for knowledge graphs. In EMNLP , pages 1980--1990. Association for Computational Linguistics
2018
-
[31]
Bishan Yang, Wen - tau Yih, Xiaodong He, Jianfeng Gao, and Li Deng. 2015. Embedding entities and relations for learning and inference in knowledge bases. In ICLR (Poster)
2015
-
[32]
Hongkuan Zhou, Lavdim Halilaj, Sebastian Monka, Stefan Schmid, Yuqicheng Zhu, Bo Xiong, and Steffen Staab. 2024. Visual representation learning guided by multi-modal prior knowledge. arXiv preprint arXiv:2410.15981
2024 arXiv
-
[33]
Yuqicheng Zhu, Nico Potyka, Mojtaba Nayyeri, Bo Xiong, Yunjie He, Evgeny Kharlamov, and Steffen Staab. 2024 a . Predictive multiplicity of knowledge graph embeddings in link prediction. In Findings of the Association for Computational Linguistics: EMNLP 2024, pages 334--354
2024
-
[34]
Yuqicheng Zhu, Nico Potyka, Jiarong Pan, Bo Xiong, Yunjie He, Evgeny Kharlamov, and Steffen Staab. 2025. Conformalized answer set prediction for knowledge graph embedding. In Proceedings of the 2025 Conference of the Nations of the Americas Chapter of the Association for Compu...
2025
-
[35]
Yuqicheng Zhu, Nico Potyka, Bo Xiong, Trung-Kien Tran, Mojtaba Nayyeri, Evgeny Kharlamov, and Steffen Staab. 2024 b . Approximating probabilistic inference in statistical el with knowledge graph embeddings. arXiv preprint arXiv:2407.11821
2024 arXiv
-
[36]
Yuqicheng Zhu, Nico Potyka, Bo Xiong, Trung - Kien Tran, Mojtaba Nayyeri, Steffen Staab, and Evgeny Kharlamov. 2023. Towards statistical reasoning with ontology embeddings. In ISWC (Posters/Demos/Industry) , volume 3632 of CEUR Workshop Proceedings . CEUR-WS.org
2023
-
[37]
URL: " 'urlintro :=
ENTRY address author booktitle chapter edition editor howpublished institution journal key month note number organization pages publisher school series title type volume year eprint doi pubmed url lastchecked label extra.label sort.label short.list INTEGERS output.state before...
-
[38]
write newline
" write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 gl...
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.