The Post-GCN Decade Revisited: Curvature-Stratified Evaluation of Relational Learning

The Hidden Shape of Data: Why Global Leaderboards Fail Graphs

Current AI benchmarks for graphs often average scores across different types of data. This process hides how models actually perform. This paper introduces a new way to test models. It groups datasets based on their geometric shape, or curvature. The authors found that a model's success depends heavily on its design. Specifically, the design must match the data's shape.

Relational learning involves modeling data where instances are interconnected. Examples include citation networks or molecular structures. The field is entering a massive scaling phase. Researchers are moving from simple Graph Convolutional Networks (GCNs) to high-capacity Graph Foundation Models (GFMs). These GFMs are designed to generalize across many domains. Traditionally, we judge these models using "flat" leaderboards. These calculate a single average performance score across diverse datasets.

The problem is that this averaging assumes all relational data is essentially the same. It treats a tree-like hierarchy and a dense, grid-like molecule as structurally identical. This study argues that this assumption creates a systematic bias. It masks the fact that a model might be a genius in one geometric setting. However, it might be completely incompetent in another.

The fallacy of the average score

The status quo in relational learning relies on aggregated metrics. These metrics smooth over the structural nuances of individual datasets. When researchers report a single accuracy score across ten different graphs, they assume a uniform underlying structure. The authors argue this leads to a "geometric mismatch." This occurs when model design and model assessment do not align.

As shown in, model rankings are not universal properties of an architecture.

Instead, they are functions of the benchmark's composition. A model might rank in the top three on a citation network. Yet, it may fall to the bottom of the pack on a telecommunications graph. Collapsing these differences into a single number obscures critical performance trade-offs. This makes it impossible to tell if a model's success is due to architectural superiority. Or, perhaps, it is simply a "lucky" alignment with the specific data types in a benchmark.

Measuring the bend in the data

To fix this, the authors introduce CURVBENCH. This is a framework that classifies datasets into three "curvature regimes": positive, negative, and near-zero. To do this, they use a metric called the midpoint curvature residual ($\xi_G$).

Think of curvature as the way paths deviate from a straight line. In a flat Euclidean space, the distance between two points is a predictable straight line. In a negatively curved space—like a saddle or a tree-like hierarchy—paths diverge rapidly. In a positively curved space—like a sphere—paths converge. The researchers calculate this by probing local triangles. They measure how these triangles deviate from ideal Euclidean geometry.

The framework also uses curvature skewness ($\gamma_\kappa$). This captures the asymmetry of these shapes. A dataset might have a "near-zero" average curvature. However, high positive skewness means it contains a small subset of highly clustered nodes. This allows the authors to partition 14 diverse datasets into mathematical strata. This ensures models are compared within the same geometric environment.

Stability within the regime

The evidence for this stratification is stark. Model rankings are remarkably stable within a specific curvature regime. However, they fluctuate wildly when crossing between regimes. For node classification, the study finds high consistency within regimes. Specifically, the top-3 model rankings have a Spearman correlation of 0.539 within regimes. In contrast, the correlation is only 0.036 across different regimes.

These performance shifts reveal fundamental truths about model inductive biases (the set of assumptions a model uses to predict outputs). In the near-zero regime, standard Euclidean methods like GraphSAGE and PCNet dominate. However, in the negative regime, Euclidean models drop to 0% of the top-3 positions. Instead, adaptive Riemannian methods take over. These are architectures designed to navigate non-flat surfaces.

The study also examines the "label elasticity" of Graph Foundation Models (GFMs). Elasticity measures how much performance improves when adding more labels. Near-zero, citation-like graphs are highly elastic. Adding more labels leads to an average improvement of 18.41 points. In contrast, negative and positive regimes show much lower elasticity. This suggests that in those environments, the bottleneck is not just a lack of data. Rather, it is a fundamental mismatch between the model's geometry and the data's structure.

Complexity comes at a cost

Geometry-aware models can solve problems that Euclidean models cannot. However, they are not free. The authors provide a detailed efficiency analysis. This highlights a significant trade-off. As visualized in and, Euclidean baselines are very lightweight.

They are efficient during both training and inference (the process of making predictions on new data).

In contrast, many non-Euclidean models introduce heavy computational burdens. For instance, the adaptive Riemannian model GraphMoRE is significantly more expensive. It incurs high costs in both training and testing. Some models, like HAT, suffer from high inference-time overhead. This is due to the complexity of performing manifold operations (mathematical transformations on curved surfaces) during every prediction. Furthermore, several high-performing GFMs encountered Out-of-Memory (OOM) errors on larger datasets like Telecom. This means their theoretical advantages are limited by practical scalability.

A new standard for evaluation

Is the industry ready to abandon flat leaderboards? The answer depends on your goal. If you want a quick, coarse comparison, a flat average is a functional tool. But if you are building a model for a specific application, a global leaderboard is misleading. For example, if you are analyzing biological molecules, you need a model aligned with that specific geometry.

The verdict is clear: model effectiveness is a joint product of architecture, task, and geometry. The authors recommend that practitioners stop looking for a "universally best" model. Instead, select architectures whose inductive biases align with your target data's curvature. For those interested in implementing this approach, the authors have released all code and curvature-stratified dataset splits. You can find them at https://sirbabbage.github.io/CurvBench_HOME/.

Figures from the paper