acceptodds
Under review as a conference paper at ICLR 2027

Accuracy, Coverage and Fairness for Knowledge Graph Embedding via Dual Clustering

Abstract

Existing knowledge graph embedding (KGE) models achieve strong link prediction performance but lack reliable coverage and fairness guarantees. Recent conformal prediction (CP) methods for KGE provide coverage guarantees, yet they use CP as a post-hoc calibration step and do not explicitly address accuracy or fairness. We propose the first unified framework that jointly addresses accuracy, coverage, and fairness in KGE via dual label-clustering. Our key insight is that uncertainty in KGE is inherently structured: entities and relations exhibit distinct difficulty patterns that should be captured at the label level. To this end, we propose learnable low-rank factorization for entity and relation spaces, perform representation-driven dual label clustering, and integrate the resulting structure into self-adversarial training and cluster-wise conformal calibration. This produces cluster-adaptive prediction sets that maintain valid coverage while improving base KGE accuracy. We further provide a theoretical prediction set size disparity bound analysis that decomposes unfairness into intra-cluster heterogeneity, cross-cluster spread, and residual cross-group disparity, linking the dual label clustered CP to improved fairness. Empirically, our method consistently outperforms state-of-the-art baselines and achieves better accuracy, coverage effectiveness, and fairness, while acting as a general plug-in approach for diverse base KGE models.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Knowledge Graph Embedding, Conformal Prediction, Fairness

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_5PXoOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper proposes a unified framework for improving accuracy, coverage efficiency, and fairness in knowledge graph embedding (KGE) through dual clustering of entities and relations. It learns low-rank representations of entity and relation embeddings, clusters these representations, and uses the resulting clusters for both cluster-aware self-adversarial KGE training to improve link-prediction accuracy and cluster-wise conformal calibration to maintain coverage and improve prediction set size and prediction-set-size disparity (fairness). The empirical results show that the proposed method outperforms existing KGE methods and KGE + CP methods on all of these metrics. The paper also presents a disparity decomposition to give a bound on the overall unfairness, which is attributed to prior work.

Critical strengths
  • The paper studies an important problem of improving uncertainty quantification and fairness in KGE, in addition to link-predictive accuracy. Addressing all three objectives within a unified framework is interesting, particularly because conformal prediction for KGE is typically applied as a post-hoc mechanism rather than being integrated with representation learning.

  • The dual clustering approach, which explicitly considers entity-relation heterogeneity, is an intuitive and natural architectural choice for knowledge graphs. Further integrating the resulting clusters for both KGE training and conformal calibration is also interesting.

  • The paper has a reasonably comprehensive experimental evaluation across multiple existing (conformal) KGE methods and benchmark datasets, with consistent improvements in predictive accuracy, average prediction-set size, and the proposed prediction-set-size disparity metric against the considered baselines.

Critical weaknesses
  • The theoretical contribution and novelty surrounding Theorem 4.1 seem to be quite overstated. The theorem statement and proof match closely with Theorem 4.1 in [1], which the authors do cite, but already establishes essentially the same prediction-set-size disparity decomposition. Further, the theorem applies to any general label clustering function, so it's not clear what the low-rank dual-clustering procedure adds to the bounds of theory.

  • For the fairness results, the authors define groups based on query difficulty following Zhu et al. (2025). (Note the citation is incorrect in the paper and cites the subsequent 2026 work.) While the metric is useful in assessing robustness to different query difficulties, it would be nice to see results that consist of sensitive attributes that may result in actual bias (e.g., race or gender component). The YAGO3-10 dataset the paper already evaluates includes such attributes (e.g., gender) that could be useful for fairness evaluation.

  • There is limited novelty in the cluster-wise conformal prediction component, as it closely resembles the filtering framework in [2]. In [2], you define a filtering function that partitions or selects calibration examples from the full calibration set and provides conditional guarantees. Admittedly, the specific objectives do differ, since [2] filters based on group fairness metrics and this paper uses learned clusters.

  • The proposed framework contains several interacting components, including low-rank representation learning, entity/relation clustering, cluster-aware self-adversarial training, and cluster-wise conformal calibration, but the empirical evaluation does not include an appropriate ablation study.

[1] Liu et al., 2026. Beyond Procedure: Substantive Fairness in Conformal Prediction, ICML 2026

[2] Vadlamani et al., 2025, A Generic Framework for Conformal Fairness, ICLR 2025

Questions for authors

(See weaknesses)

How much does each component of the framework contribute to the overall performance?

Do the coverage guarantees hold empirically within individual clusters/groups?

4 comments

We thank the reviewer 5PXo for recognizing the value of taking dual heterogeneity into jointly addressing accuracy, coverage, and fairness, and for highlighting our results and experiments. We also thank the reviewer giving us opportunities to response to novelty and contribution, fairness evaluation, ablation, and individual group coverage guarantee. We will revise our paper accordingly.

W1, W3: Theoretical and methodology novelty and contribution

The current theorem applies to an arbitrary clustering. It explains how within-cluster heterogeneity enters the set-size-disparity bound. Thus, any clustering-based CP can reduces max set-size parity. As explained in our paper lines 314-356, we propose dual heterogeneity modeling and clustering to reduce the first two terms in Eq. (19). And existing conditional/clustered conformal prediction did not influence training process while our method uses factorization-based clustering and new cluster-aware self-adversarial losses which consider entity and relation heterogeneities. Empirical results also show that we actually achieve smallest Δ\Delta with smallest APSS and without violating coverage. Meanwhile, a coarse clustering will result in less calibration samples in each cluster. And less calibration samples in each cluster will result in larger average prediction set size.

Existing conditional/clustered conformal predictions and fairness notions based on conformal set sizes or group-conditional coverage [1, 2] do not influence any training process to improve accuracy and only run the post-hoc CP with known clusters or sensitive classes. These methods all need known sensitive features or labels. We propose negative sampling and contrastive learning with factorization-based clustering and weighting that models dual entity and relation heterogeneity in embeddings to further improve accuracy, coverage, and fairness. We propose the first unified KGE framework and conduct evaluation to jointly addresses accuracy, coverage, and fairness.

W2, Q2: Fairness evaluation and individual group coverage guarantee

Existing KGE benchmark datasets usually have no known sensitive features or labels, and thus we follow reference (Liu 2026) in our paper: reduced max set-size parity is more reasonable for fairness in scenarios that require coverage guarantee but have no sensitive features or labels. We note that Δ\Delta alone is insufficient: equal and large set sizes give Δ=0\Delta=0 but this is without utility. Thus, in the paper, We evaluate Δ\Delta jointly with empirical coverage and average prediction set size. Fairness improvements are only claimed on lower Δ\Delta without violating coverage or inflating APSS. We use Δ\Delta as a diagnostic of fairness only after we meet the coverage target and achieve smallest APSS.

We report experiments compared to Mondrian CP. During the Mondrian CP calibration, the difficulty groups were constructed after training KGE models and based on the model ranks of the true answers using the validation dataset.

WN18RRECAPSSΔ\Delta
CondKGCP0.9054638506
Mondrian CP0.9049828130
Ours0.9135177165

We can see that our method meet the coverage target, achieve smallest APSS and better fairness than Mondrian CP.

Some person entities from the YAGO3-10 dataset has gender attributes, but the rest person entities are still unknown. We further report experiments directly based on such sensitive gender groups, instead of difficulty groups.

YAGO3-10Individual group ECAPSSΔ\Delta (gender groups)
CondKGCP0.9056983209
Mondrian CP0.9057633004
Ours0.9046412957

We can see that our method still achieve the empirical coverage, smallest APSS and better fairness than Mondrian CP. And our method hold the coverage guarantees empirically within individual gender group.

W4, Q1: Ablation

We report ablation compared to (i) clustering raw embeddings; (ii) training without cluster-aware adversarial weighting; (iii) without cluster-wise CP; (iv) training without low-rank and cluster-aware adversarial weighting; and Mondrian CP baseline:

WN18RRECAPSSΔ\Delta
CondKGCP0.9054638506
Mondrian CP0.9049828130
(i)0.9147597862
(ii)0.9148117899
(iii)0.9045378411
(iv)0.9149118002
Ours0.9135177165

We can see that each component is helpful in APSS and Δ\Delta.

I would like to thank the authors for their detailed response and additional experiments. The new experiments address most of my concerns and strengthen the paper. A few of my concerns remain.

  1. [W1] While the authors do attribute Theorem 4.1 to Liu et al. (2026), my concern is that the theoretical analysis does not appear to provide additional insights beyond those already established in that work. In particular, the original theorem already applies to arbitrary clustering functions, and the authors do not theoretically establish that their proposed low-rank dual clustering provably reduces the terms in Eq. 19. Can the authors clarify the theoretical insights from their framework, or dial back on any claims of theoretical novelty?

  2. [W2] I appreciate the gender-based evaluation, but can you clarify what you mean by "Individual group EC"? Do all of the gender groups achieve the empirical coverage? If so, making this clearer or explicitly listing each group and its metrics would make this table much stronger.

  3. [W4] The ablation results look quite interesting. One additional experiment that could be useful is an entity-only vs. relation-only clustering comparison to establish the importance of dual clustering.

Overall, the rebuttal addresses most of my empirical concerns and strengthens the paper. While some concerns remain, and I would appreciate further clarification from the authors, I believe these can be addressed relatively easily. Thus, I will increase my score.

We thank again for the time and careful effort you put into our work and provide the insightful comments. We truly appreciate your positive feedback on our rebuttal and increase your score. We will for sure response to the remained issues when we get the experimental results.

We thank you again for giving us opportunities to make more clarification.

W1: Novelty

Prior theories (Liu 2026) are only proved for and applicable to classification tasks. We prove the theories for the KGE ranking task. And then, we propose dual clustering to training process which further controls intra-cluster heterogeneity (embeddings within the same cluster) and cross-cluster spread (embeddings from different clusters) by adaptively adjusting the entity embeddings and relation embeddings while learning clusters end-to-end.

W2: Individual group EC

Individual group EC refers to that the results for each of the gender groups. We report results for each group.

YAGO3-10EC (male)EC ( female)EC (unknown)APSSΔ\Delta (gender groups)
CondKGCP0.900.900.9056983209
Mondrian CP0.910.900.9057633004
Ours0.910.900.9046412957

W4: Ablation

We report ablation compared to (i) entity-only clustering; (ii) relation-only clustering:

WN18RRECAPSSΔ\Delta
CondKGCP0.9054638506
Mondrian CP0.9049828130
(i)0.9138447531
(ii)0.9044857590
Ours0.9135177165

We can see that dual clustering is helpful in APSS and Δ\Delta, and entity clustering is more helpful in APSS.

Reviewer_oNjKOpenReview ↗
Rating
3(+1)
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The authors propose a framework for knowledge graph embedding (KGE) that aims to improve link prediction accuracy, conformal coverage, and fairness (measured by prediction set size disparity across query groups). The method has three components: (i) low-rank factorization of entity and relation embeddings, (ii) cluster-aware modification of self-adversarial KGE training, and (iii) cluster-wise conformal calibration. The authors evaluate the method on standard KGE benchmarks and report improvements in MRR/Hits, empirical coverage, average prediction set size, and maximum set-size disparity. The authors also present a theoretical decomposition of prediction set size disparity into intra-cluster heterogeneity, cross-cluster spread, and residual cross-group disparity.

Critical strengths
  • The paper is well motivated and generally easy to follow.
  • The authors identify a meaningful limitation of standard KGE link prediction: ranking metrics such as MRR and Hits@K do not provide uncertainty guarantees. The proposed framework is also practically appealing because it can be applied to several standard KGE models.
  • The empirical results are consistent across multiple KGE backbones and datasets, and the paper evaluates both ranking accuracy and conformal prediction-set efficiency.
  • The idea of jointly adapting KGE training and conformal calibration to entity and relation heterogeneity is interesting and potentially useful.
Critical weaknesses
  • Novelty: Conformal answer sets for KGE have already been investigated [1, 2]. Conditional/clustered conformal prediction is also an established idea [3, 4], and self-adversarial negative sampling is standard in KGE [5]. Fairness notions based on conformal set sizes or group-conditional coverage have also been studied outside KGE [6, 7]. As far as I understand, the potentially novel part of this paper is narrower than what is suggested in the abstract: combining low-rank entity/relation representations, similarity-aware negative sampling, and cluster-wise conformal calibration in a single KGE framework. The work is a reasonable integration of existing ideas, but I find its methodological originality somewhat limited.

  • Fairness definition and motivation: The paper evaluates fairness using maximum prediction set size disparity across query groups. This is an existing notion of procedural fairness in conformal prediction [6, 7], but its applicability to the setting considered here is insufficiently justified. Section 2.3 motivates sensitive groups using attributes such as gender, but the experimental groups are constructed according to query difficulty. If these groups are difficulty strata rather than sensitive groups, reducing set-size disparity across them does not necessarily demonstrate fairness. Different query difficulties may legitimately require different prediction-set sizes. In fact, forcing similar set sizes for easy and hard queries seems to conflict with the goal of adaptive uncertainty quantification.

    Further, the metric Δ\Delta is degenerate when considered independently: it can be minimized by uniformly enlarging prediction sets, even when doing so makes them less informative. I recognize that the paper reports Δ\Delta alongside empirical coverage and APSS, which partially addresses this concern. However, this establishes an efficiency–parity tradeoff rather than fairness across sensitive groups or improved downstream fairness. The paper should better motivate why parity across the selected groups is desirable and explicitly distinguish set-size parity from substantive fairness and other fairness notions studied in graph/link prediction [8–11].

  • Fairness evaluation: Table 3 compares against Top-k, KGCP, and CondKGCP, which are primarily KGE/conformal prediction baselines rather than fairness-aware conformal baselines. Since the proposed method is designed to reduce Δ\Delta, the current comparison provides limited evidence of its fairness advantages. Natural alternatives include group-conditional/Mondrian CP [3], group-aware threshold calibration, or direct set-size equalization, evaluated jointly with coverage and APSS. Of course, group-aware approaches require group assignments available at inference time. If meaningful sensitive groups are unavailable in the adopted datasets, I believe this is a limitation of the fairness evaluation itself rather than sufficient justification for treating difficulty-based disparities as fairness.

  • Low-rank factorization: The motivation for low-rank factorization remains insufficiently justified. The authors argue that directly clustering the learned entity and relation embeddings EE and RR is sensitive to noise or redundancy, and therefore propose E=UEVE⊤E=U_EV_E^\top and R=URVR⊤R=U_RV_R^\top. However, EE and RR are already task-specific learned embeddings, and the paper provides no direct evidence that clustering UE,URU_E,U_R produces more stable or uncertainty-aligned clusters than clustering the original embeddings. The procedure for initializing and jointly optimizing the factor matrices, as well as the timing of clustering, is also insufficiently described. Moreover, some of the considered ranks are close to the embedding dimension, weakening the interpretation of this factorization as a denoising bottleneck.

  • Theoretical contribution: The theoretical analysis is rather limited. Theorem 4.1, attributed to prior work [7], is essentially a disparity decomposition obtained through triangle inequalities and range bounds. It holds for an arbitrary clustering and does not establish that the proposed learned clustering actually reduces Δ\Delta relative to alternative clustering or calibration strategies. A more informative contribution would characterize the relationship between clustering granularity, calibration sample size, prediction-set efficiency, and disparity. As currently presented, the theoretical analysis does not adequately justify the algorithmic design decisions.

  • Missing ablations and sensitivity analysis: The experimental evaluation does not sufficiently isolate the contribution of each component. I would expect comparisons between (i) clustering raw embeddings and low-rank coordinates; (ii) training with and without low-rank factorization; (iii) training with and without cluster-aware adversarial weighting; and (iv) global CP versus cluster-wise CP under the same trained backbone. In addition, the number of clusters KK introduces an important tradeoff: finer clusters may capture uncertainty heterogeneity more precisely, but reduce the calibration sample size available within each cluster. I find the absence of a sensitivity analysis for KK particularly concerning.

  • Numerical consistency: Table 1 appears to contain an inconsistency for DistMult + Ours on WN18RR with embedding dimension 32. The reported MRR is 49.5%, while H@1, H@3, and H@10 are 37.0%, 40.7%, and 45.4%, respectively. These values are mathematically incompatible: the maximum possible MRR consistent with these Hits values is approximately 45.0%. This may be a reporting error, but the authors should verify the results.

References

[1] Yuqicheng Zhu et al. Conformalized Answer Set Prediction for Knowledge Graph Embedding. NAACL 2025.

[2] Yuqicheng Zhu et al. Predicate-Conditional Conformalized Answer Sets for Knowledge Graph Embeddings. Findings of ACL 2025.

[3] Vladimir Vovk, Alexander Gammerman, and Glenn Shafer. Algorithmic Learning in a Random World. Springer, 2005.

[4] Tiffany Ding et al. Class-Conditional Conformal Prediction with Many Classes. NeurIPS 2023.

[5] Zhiqing Sun et al. RotatE: Knowledge Graph Embedding by Relational Rotation in Complex Space. ICLR 2019.

[6] Jesse C. Cresswell et al. Conformal Prediction Sets Can Cause Disparate Impact. ICLR 2025.

[7] Pengqi Liu et al. Beyond Procedure: Substantive Fairness in Conformal Prediction. 2026.

[8] Chirag Agarwal, Himabindu Lakkaraju, and Marinka Zitnik. Towards a Unified Framework for Fair and Stable Graph Representation Learning. UAI 2021.

[9] Mario Arduini et al. Adversarial Learning for Debiasing Knowledge Graph Embeddings. MLG Workshop, 2020.

[10] Joseph Fisher et al. Debiasing Knowledge Graph Embeddings. EMNLP 2020.

[11] João Mattos, Debolina Halder Lina, and Arlei Silva. Breaking the Dyadic Barrier: Rethinking Fairness in Link Prediction Beyond Demographic Parity. AAAI 2026.

Questions for authors
  1. Fairness groups: How exactly are the groups used to calculate Δ\Delta constructed? If they are based on query difficulty rather than sensitive attributes, why should reducing disparity across them be considered fairness rather than simply reducing variation in prediction-set sizes? How does this relate to the goal of adaptive uncertainty quantification?

  2. Fairness baselines: Could the authors compare against fairness-aware conformal baselines, such as group-conditional/Mondrian CP [3] or direct set-size equalization [6, 7], using group assignments available at inference time? These comparisons should report EC, APSS, and Δ\Delta jointly.

  3. Ablations and clustering: Please provide component-wise ablations, particularly raw-embedding versus low-rank clustering and training with versus without cluster-aware adversarial weighting. Could the authors also analyze the sensitivity to the number of clusters KK, including its impact on APSS, coverage, and disparity?

  4. Theoretical justification and implementation: What theoretical or empirical evidence establishes that the proposed low-rank clustering reduces the terms in Theorem 4.1? How are UE,UR,VE,VRU_E,U_R,V_E,V_R initialized and optimized, and when are the clusters computed? How should the conformal coverage guarantee be interpreted when calibration and test queries share the same underlying KG?

  5. Numerical results: Could the authors verify the DistMult results for WN18RR at dimension 32 in Table 1? The reported MRR and Hits values appear inconsistent.

4 comments
AuthorsOpenReview ↗

Official Comment 1 by Authors

We thank the reviewer oNjK for recognizing the value of taking distribution, structural information into jointly addressing accuracy, coverage, and fairness, and for highlighting our motivations, dual heterogeneity, results and experiments. We also thank the reviewer giving us opportunities to response to novelty, fairness definition and evaluation, low-rank factorization, theoretical contribution, and typos. We will revise our paper accordingly.

W1: Novelty

Existing conformal answer sets for KGE (KGCP and CondKGCP) directly use CP without improving accuracy or fairness. Existing conditional/clustered conformal predictions and fairness notions based on conformal set sizes or group-conditional coverage (Liu 2026 and Ding 2023) do not influence any training process to improve accuracy and only run the post-hoc CP with known, fixed clusters and sensitive classes. These methods all need known sensitive features or labels. Existing negative sampling and contrastive learning directly use training scores for weighting without considering dual entity and relation heterogeneity in embeddings. Our method proposes factorization-based clustering and new cluster-aware self-adversarial losses which consider dual heterogeneity to further improve accuracy, coverage, and fairness. We propose the first unified KGE framework and conduct evaluation to jointly addresses accuracy, coverage, and fairness.

W2, Q1: Fairness definition, motivation, and groups

As shown in Section 2.3 line 160, GaG_a denotes sensitive groups for scenarios where sensitive features or labels are known. For references [6-11] from the reviewer oNjK, these methods all need known sensitive features or labels. However, existing KGE benchmark datasets usually have no known sensitive features or labels, and thus we follow reference (Liu 2026) in our paper: reduced max set-size parity is more reasonable for fairness in scenarios that require coverage guarantee but have no sensitive features or labels. We note that Δ\Delta alone is insufficient: equal and large set sizes give Δ=0\Delta=0 but this is without utility. Thus, in the paper, We evaluate Δ\Delta jointly with empirical coverage and average prediction set size. Fairness improvements are only claimed on lower Δ\Delta without violating coverage or inflating APSS. We use Δ\Delta as a diagnostic of fairness only after we meet the coverage target and achieve smallest APSS.

Different query difficulties require different prediction-set sizes. And we did not force similar set sizes for easy and hard queries. In fact, we calibrate different thresholds and thus there are different prediction-set sizes for different clusters learned by our model. And by learning clusters with dual heterogeneity, we reduce max set-size parity Δ\Delta to improve fairness. And we only evaluate Δ\Delta jointly with empirical coverage and average prediction set size; Our fairness improvement claims are based on smallest Δ\Delta with smallest APSS and without violating coverage.

The difficulty groups for evaluating the Δ\Delta were constructed after training KGE models and based on the model ranks of the true answers using the test dataset, following reference (Liu 2025) in our paper.

W3, Q2: Fairness baselines and evaluation

We report experiments compared to Mondrian CP and direct set-size parity baselines. During the Mondrian CP calibration, the difficulty groups were constructed after training KGE models and based on the model ranks of the true answers using the validation dataset.

WN18RRECAPSSΔ\Delta
CondKGCP0.9054638506
Mondrian CP0.9049828130
Direct set-size parity0.9189090
Ours0.9135177165

We can see that our method meet the coverage target, achieve smallest APSS and better fairness than Mondrian CP. Eventhough direct set-size parity baseline achieve Δ=0\Delta=0, its APSS is too large that has no utility.

Some person entities from the YAGO3-10 dataset has gender attributes, but the rest person entities are still unknown. We further report experiments directly based on such sensitive gender groups, instead of difficulty groups.

YAGO3-10ECAPSSΔ\Delta (gender groups)
CondKGCP0.9056983209
Mondrian CP0.9057633004
Direct set-size parity0.9093470
Ours0.9046412957

We can see that our method still achieve the empirical coverage, smallest APSS and better fairness than Mondrian CP.

AuthorsOpenReview ↗

Official Comment 2 by Authors

W4, W6, Q3, Q4: Low-rank factorization, implementation, ablations and sensitivity

As shown in Eqs. (11)–(15), we use soft assignments during training, and factor matrices are randomly initialized and trained with the KGE model from scratch. As shown in Eqs. (15)–(17), the CP is conducted after training process, and the hard clustering is conducted after training and then fixed. Table 5 shows all searched values across dimensions. For example, the rank 28 as the denoising bottleneck can be much smaller than the embedding dimension 256 or 1000.

Our clustering adds complexity of O(∣E∣KEkE+∣R∣KRkR)O(|\mathcal E|K_Ek_E+|\mathcal R|K_Rk_R). The training time complexity of existing KGE methods is at least O(∣G∣(dE+dR)2)O(|\mathcal{G}|({d_{E}}+{d_{R}})^2). Thus, the overall training time complexity is comparable to each base KGE model. We also report the actual training time (10k steps), total calibration time and testing time (the whole testing procedure) using the same batch size settings:

WN18RRTraining timeCalibration timeTesting time
Base GoldE11.5minN/A23s
CondKGCP11.5min4s23s
Ours11.6min4s23s
FB15K-237Training timeCalibration timeTesting time
Base GoldE26.1minN/A90s
CondKGCP26.1min8s90s
Ours26.3min8s90s
AGO3-10Training timeCalibration timeTesting time
Base GoldE30.1minN/A110s
CondKGCP30.1min9s110s
Ours30.3min9s110s

These results show the scalability of our method. We will also include more Appendix in the final version.

We report ablation compared to (i) clustering raw embeddings; (ii) training without cluster-aware adversarial weighting; (iii) without cluster-wise CP; (iv) training without low-rank and cluster-aware adversarial weighting; and Mondrian CP baseline:

WN18RRECAPSSΔ\Delta
CondKGCP0.9054638506
Mondrian CP0.9049828130
(i)0.9147597862
(ii)0.9148117899
(iii)0.9045378411
(iv)0.9149118002
Ours0.9135177165

We can see that each component is helpful in APSS and Δ\Delta.

We report experiments with different cluster number kk:

WN18RRECAPSSΔ\Delta
CondKGCP0.9054638506
Mondrian CP0.9049828130
k=10k=100.9134927308
k=20k=200.9135177165
k=40k=400.9137847120
k=60k=600.9139587106

We can see that the results are not sensitive to cluster number kk within proper ranges, and are better than baselines.

W5, Q4: Theoretical contribution and justification

The current theorem applies to an arbitrary clustering. It explains how within-cluster heterogeneity enters the set-size-disparity bound. Thus, any clustering-based CP can reduces max set-size parity. As explained in our paper lines 314-356, we propose dual heterogeneity modeling and clustering to reduce the first two terms in Eq. (19). And existing conditional/clustered conformal prediction did not influence training process while our method uses factorization-based clustering and new cluster-aware self-adversarial losses which consider entity and relation heterogeneities. Empirical results also show that we actually achieve smallest Δ\Delta with smallest APSS and without violating coverage. Meanwhile, a coarse clustering will result in less calibration samples in each cluster. And less calibration samples in each cluster will result in larger average prediction set size. Thus, we can not set cluster number kk too coarse to cater to the smaller subgroups.

The calibration and test dataset space is edge-specific. Conditional on the training KG, sharing a vocabulary (entities and relations) and graph-derived features does not by itself violate exchangeability and conformal coverage guarantee, where edges-specific triples are disjointed among training, calibration and test datasets.

W6, Q5: Typos

We revised the typos, and the number is 39.5.

Thanks to the authors for the rebuttal and the additional experiments. My concerns about novelty (mainly the theoretical contribution) still stand, and I'm not totally convinced by the motivation for fairness across difficulty-based groups.

However, I believe the additional experiments make this a better paper. I am increasing my score.

We thank again for the time and careful effort you put into our work and provide the insightful comments. We truly appreciate your positive feedback on our rebuttal and increase your score.

The current theorem explains how intra-cluster heterogeneity and cross-cluster spread influence max set-size parity for sensitive groups and arbitrary groups. Prior theories (Liu 2026) are only proved for and applicable to classification tasks. We prove the theories for the KGE ranking task. And then, we propose dual clustering to training process which further controls intra-cluster heterogeneity (embeddings within the same cluster) and cross-cluster spread (embeddings from different clusters) by adaptively adjusting the entity embeddings and relation embeddings while learning clusters end-to-end.

Our motivation for fairness is reducing max set-size parity for sensitive groups. As most KGE benchmark do not have sensitive features or labels, we conduct experiments with difficulty-based groups, to evaluate the theorem that explains how intra-cluster heterogeneity and cross-cluster spread influence max set-size parity for sensitive groups and arbitrary groups. We provide experiments on YAGO3-10 that has sensitive features for more evaluation.

We will make these more clarified in the revised paper.

And we thank again for your careful effort to improve our paper, your positive feedback on our rebuttal and increasing your score.

Reviewer_FHmtOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

Knowledge graph embeddings (KGEs) aim to compute the vector representation of entities and relations, and output a score for each link determining the plausibility of the link. Most KGEs work focus on performance improvement. However, coverage and fairness guarantee are the less explored aspects. Recent works move one step forwards and utilize conformal prediction as tools to address coverage guarantee, but they are only post-processing steps and lack addressing accuracy and fairness. This paper aims to address accuracy, coverage and fairness jointly. It first utilizes a low-rank factorization and compute clusters over entities/relations, followed by using those clusters information as weights in the loss function as well as providing cluster-based conformal calibration. A theoretical analysis helps to understand unfairness as composition of intra-cluster heterogeneity, cross-cluster spread, and residual cross-group disparity, linking the dual label clustered CP to improved fairness. Empirical results on various KGEs/Datasets/CPs shows the proposed approach obtains better results in terms of accuracy, fairness and coverage.

Critical strengths

– While most previous works only focus on boosting accuracy, this paper addresses multiple important aspects jointly which are fairness, accuracy, and coverage.

– taking various information such distribution, structural patterns, etc into account for fairness, accuracy, and coverage is reasonable and valid approach.

– Overall, the results are consistent and for each of the contributions, a separate experiment is provided to support the claim.

Critical weaknesses

– Given the contribution of previous works (e.g., contrastive learning, Affinity Dependent Negative Sampling, theories in Liu, et al 2026, Ding et al 2023), the core contribution of this paper is limited. This work actually is yet another case study of previous work with a marginal added contribution.

– The method introduces further hyperparameters (gamma, two beta) which makes the practical usage difficult.

– The performance gain in table 1 is marginal, especially on the strongest base KGE. The experiments is not built on top of SOTA KG completion results, thus it is difficult to assess if the accuracy related contribution of this paper pushes the boundary in terms of performance. Also, in table 2, the results are not great in terms of EC.

Questions for authors

If this approach is applied to the SOTA methods in KGEs, will a gain in performance be obtained?

4 comments

We thank the reviewer FHmt for recognizing the value of taking distribution, structural information into jointly addressing accuracy, coverage, and fairness, and for highlighting our results and experiments. We also thank the reviewer giving us opportunities to response to contributions, hyperparameters, and performance gain. We will revise our paper accordingly.

W1: Contributions

Existing conformal answer sets for KGE (KGCP and CondKGCP) directly use CP without improving accuracy or fairness. Existing negative sampling and contrastive learning directly use training scores for weighting without considering dual entity and relation heterogeneity in embeddings. Existing conditional/clustered conformal predictions (Liu 2026 and Ding 2023) do not influence any training process to improve accuracy and only run the post-hoc CP with known, fixed clusters and sensitive classes. These methods all need known sensitive features or labels. Our method proposes factorization-based clustering and new cluster-aware self-adversarial losses which consider dual heterogeneity to further improve accuracy, coverage, and fairness. We propose the first unified KGE framework and conduct evaluation to jointly addresses accuracy, coverage, and fairness.

W2: Hyperparameters

We would like to clarify that γ\gamma is not new. γ\gamma is the temperature firstly used in RotatE and is present in all SOTA base models. And we use the hyperparameters random search (Bergstra 2012) with the same trial budget according to each base KGE model and find consist improvements in the experimental Table 1.

W3, Q1: Performance gain

For accuracy results, GoldE is the best model as far as we known. The recent published KGE models perform worse than GoldE and do not compare with GoldE. Compared to SOTA base models, our gains are systematically positive across the embedding dimensions in the Table 1. MRR runs +0.1+0.1 to +2.2+2.2; H@10 runs +0.1+0.1 to +3.1+3.1. Besides, SOTA baselines KGCP and CondKGCP are post-hoc CP that do not influence any training process to improve accuracy: their accuracy is the same as each base KGE model and their accuracy improvement is exactly +0+0.

For Table 2, as the target coverage level is set to 0.9 for all methods and EC is used to evaluate whether the method meets the target coverage level, we report the average prediction set size (APSS) to evaluate the coverage effectiveness. APSS drops 5463→3517 on WN18RR, 375→253 on FB15K-237, 5698→4641 on YAGO3-10. Our smaller answer set at the same target coverage level is significant. We also report our results under the target coverage level of 0.95 for more comparison. And we can see that our method still outperforms baselines significantly.

WN18RRECAPSS
Top-k0.907944
KGCP0.908057
CondKGCP0.905463
Ours0.913517
Ours0.955027
Reviewer_FHmtOpenReview ↗

Comment on the authors reply

Thanks to the authors for their reply, especially for clarification on the APSS for Table 2. However, the novelty concern stands: combining well established components (factorization, cluster-aware loss, CP calibration) into a unified framework is a valid engineering contribution, but the rebuttal does not show emergent scientific insight from their interaction that prior work could not predict. In addition, the two new β hyperparameters also remain unaddressed in terms of practical sensitivity.

Given the above points, I would keep my score.

We thank again for the time and careful effort you put into our work and provide the insightful comments to our rebuttal, and for giving us opportunities to make more clarification.

1: Novelty

We would like to clarify that our method is not just combining established components:

A. We propose the first unified KGE framework and conduct the first experimental evaluation that shows jointly improved accuracy, coverage, and fairness, compared to all SOTA prior works.

B. Prior theories (Liu 2026 and Ding 2023) are only proved for and applicable to classification tasks. We prove the theories for the KGE ranking task.

C. We introduce a factorization based dual label-clustering method that models both entity and relation heterogeneity and no prior works have proposed. As explained in our paper lines 314-356, the factorization based clustering is proposed to reduce the first two terms in Eq. (19) following our theories.

D. We firstly propose the cluster-aware loss that no prior works have proposed. We propose dual clustering to training process which further controls intra-cluster heterogeneity (embeddings within the same cluster) and cross-cluster spread (embeddings from different clusters) by adaptively adjusting the entity embeddings and relation embeddings while learning clusters end-to-end.

2: Sensitivity

We provide experimental results to further show that our method outperforms SOTA baselines consistently, rather than just hyperparameters sensitivity.

WN18RRECAPSSΔ\Delta
Top-k0.90794410037
KGCP0.9080579941
CondKGCP0.9054638506
Mondrian CP0.9049828130
Ours (random search)0.9135177165
Ours (βE=βR=0.5\beta_E=\beta_R=0.5)0.9136237149
Ours (βE=βR=1.0\beta_E=\beta_R=1.0)0.9135897140
Ours (βE=βR=1.5\beta_E=\beta_R=1.5)0.9139817285
Ours (βE=βR=2.0\beta_E=\beta_R=2.0)0.9041377404

We thank again for the time and careful effort you put into our work and provide the insightful comments.

We have responsed to your early question. As the deadline is coming soon, we would like to know whether your concerns are addressed. We are glad to make more clarification if needed.

Given the practical and consist jointly improved accuracy, coverage, and fairness, and the theoretical motivation and proof in our paper, we think that our work makes some contributions. We would sincerely appreciate it if you could consider updating your score for our work to have an opportunity to share at the conference.

And thank you again for your dedicated time to assess and improve our paper.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.