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

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.