# Evaluating Knowledge Graph Complexity via Semantic, Spectral, and Structural Metrics for Link Prediction

arXiv: https://arxiv.org/abs/2508.15291 · HTML: https://mlsanity.com/paper/2508.15291/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 15 references that are in the map.
- First posted on arXiv 21 Aug 2025.

## Builds on (most cited first, 8 of 8)

- [CoDEx: A Comprehensive Knowledge Graph Completion Benchmark](https://mlsanity.com/paper/2009.07810/) (2020)
- [Word Representations via Gaussian Embedding](https://mlsanity.com/paper/1412.6623/) (2014)
- [Knowledge Graphs: Opportunities and Challenges](https://mlsanity.com/paper/2303.13948/) (2023)
- [Spectral Metric for Dataset Complexity Assessment](https://mlsanity.com/paper/1905.07299/) (2019)
- [A Contextualized BERT model for Knowledge Graph Completion](https://mlsanity.com/paper/2412.11016/) (2024)
- [Instance-Conditional Timescales of Decay for Non-Stationary Learning](https://mlsanity.com/paper/2212.05908/) (2022)
- [Structural Quality Metrics to Evaluate Knowledge Graphs](https://mlsanity.com/paper/2211.10011/) (2022)
- [MuCoS: Efficient Drug Target Discovery via Multi Context Aware Sampling in Knowledge Graphs](https://mlsanity.com/paper/2503.08075/) (2025)

## Abstract (arXiv)

Understanding dataset complexity is fundamental to evaluating and comparing link prediction models on knowledge graphs (KGs). While the Cumulative Spectral Gradient (CSG) metric, derived from probabilistic divergence between classes within a spectral clustering framework, has been proposed as a classifier agnostic complexity metric purportedly scaling with class cardinality and correlating with downstream performance, it has not been evaluated in KG settings so far. In this work, we critically examine CSG in the context of multi relational link prediction, incorporating semantic representations via transformer derived embeddings. Contrary to prior claims, we find that CSG is highly sensitive to parametrisation and does not robustly scale with the number of classes. Moreover, it exhibits weak or inconsistent correlation with standard performance metrics such as Mean Reciprocal Rank (MRR) and Hit@1. To deepen the analysis, we introduce and benchmark a set of structural and semantic KG complexity metrics. Our findings reveal that global and local relational ambiguity captured via Relation Entropy, node level Maximum Relation Diversity, and Relation Type Cardinality exhibit strong inverse correlations with MRR and Hit@1, suggesting these as more faithful indicators of task difficulty. Conversely, graph connectivity measures such as Average Degree, Degree Entropy, PageRank, and Eigenvector Centrality correlate positively with Hit@10. Our results demonstrate that CSGs purported stability and generalization predictive power fail to hold in link prediction settings and underscore the need for more stable, interpretable, and task-aligned measures of dataset complexity in knowledge driven learning.