💻 computer science

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

This paper critiques standard flat leaderboards in relational learning for masking geometry-dependent performance variations and proposes a curvature-stratified evaluation framework that reveals how model effectiveness fundamentally shifts across positive, negative, and near-zero curvature regimes, thereby offering more reliable and interpretable benchmarks.

Original authors: Shuo Wang, Xiangyu Wang, Quanxin Wang, Bailin Wu, Bokui Wang, Shunyang Huang, Boyan Deng, Haonan Liu, Ruiyi Fang, Zhenxiang Xu, Boyu Wang, Zhao Kang

Published 2026-06-05

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Shuo Wang, Xiangyu Wang, Quanxin Wang, Bailin Wu, Bokui Wang, Shunyang Huang, Boyan Deng, Haonan Liu, Ruiyi Fang, Zhenxiang Xu, Boyu Wang, Zhao Kang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to judge the best "travel guide" for a group of tourists. Currently, the industry standard is to take a bunch of different trips—some through flat, open plains, some through dense, twisting forests, and some through steep, mountainous canyons. You then average the guides' scores across all these trips to create a single "Leaderboard."

The paper argues that this "Flat Leaderboard" is misleading. It's like saying a guide who is amazing at navigating flat plains is the "best overall," even if they get everyone lost in the mountains. The paper claims that the shape of the terrain (the geometry) matters more than the guide's general skill.

Here is a breakdown of their findings using simple analogies:

1. The Problem: The "Average" Lie

For the last decade, researchers have tested AI models (which learn from connected data like social networks or molecules) by averaging their scores across many different datasets. They assumed all data is basically the same "shape."

The authors say this is wrong. Some data looks like a flat sheet of paper (Euclidean), some looks like a tree with branches (hyperbolic/negative curvature), and some looks like a cluster of grapes (positive curvature).

The Analogy: If you test a snowboarder, a surfer, and a mountain biker on a single "Average Score" that mixes snow, ocean, and dirt trails, you might declare the snowboarder the winner just because there were more snow days in the test. But if you put them all on a dirt trail, the snowboarder might fail completely.

2. The Solution: "Curvature-Stratified" Evaluation

The authors built a new testing ground called CURVBENCH. Instead of one big leaderboard, they sorted the test data into three "terrain zones" based on their geometric shape:

Near-Zero Zone: Flat, open areas (like standard citation networks).
Positive Zone: Clumpy, compact areas (like tightly knit communities).
Negative Zone: Tree-like, hierarchical areas (like deep family trees or organizational charts).

They then tested 18 different AI models across these specific zones.

3. The Big Discovery: No "One Size Fits All"

When they looked at the results, they found that a model's ranking changes completely depending on the terrain.

In the Flat Zone: Simple, flat models (like standard GCNs) were the kings. They worked great.
In the Tree Zone: The simple flat models crashed. They got lost. But models designed for "negative curvature" (like hyperbolic models) suddenly became the champions.
The Shift: A model that was ranked #1 overall might drop to #10 if you only looked at the "Tree Zone." The paper proves that there is no single "best" model; there is only the "best model for this specific shape of data."

4. The "Foundation Model" Surprise

Recently, huge "Graph Foundation Models" (GFMs) have become popular. These are like giant, pre-trained AI brains that try to learn everything at once and then adapt to new tasks.

The Finding: The authors found that these giant models don't magically fix the geometry problem. In fact, on some terrains, they offered "diminishing returns."
The Analogy: It's like bringing a massive, all-terrain tank to a narrow, winding garden path. Sometimes, a simple, agile bicycle (a smaller, geometry-specific model) gets you to the destination faster and more efficiently. The giant models were sometimes too heavy or just didn't align with the specific shape of the data.

5. The "Table" Twist

The paper also looked at data that comes from spreadsheets (tables) rather than natural graphs.

The Finding: These table-based graphs often look flat on average, but they have "hidden tails" (extreme outliers in their shape).
The Analogy: Imagine a room that looks flat from a distance, but has a few hidden, deep holes. A model that is good at navigating flat floors might fall right into those holes. The paper found that some models act like "specialists" (great at the holes, bad elsewhere) while others are "generalists" (okay everywhere, but not amazing anywhere).

The Bottom Line

The paper concludes that we need to stop asking, "Which AI model is the best?" and start asking, "Which AI model is best for this specific shape of data?"

They are releasing their tools so that future researchers can stop relying on a single, misleading average score and instead evaluate models based on the actual "geometry" of the problem they are trying to solve. It's about matching the right tool to the right shape of the world.

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

1. Problem Statement

Current evaluation practices in relational learning rely heavily on "flat" leaderboards that average model performance across heterogeneous datasets. This approach implicitly assumes that relational data constitutes a monolithic category with a uniform underlying structure. The authors argue this assumption introduces systematic bias by obscuring geometry-dependent performance variations. Consequently, standard benchmarks may yield misleading conclusions about model generalization, potentially attributing success to architectural superiority when it is actually a result of a fortuitous alignment with the dominant geometric properties of the specific dataset mix.

While recent work has introduced hyperbolic, spherical, and mixed-curvature models to match specific data topologies, the evaluation paradigm remains stagnant, judging specialized models against global averages that hide their true utility. This creates a "geometric mismatch" where models are designed for specific curvatures but evaluated for the "average."

2. Methodology: CURVBENCH

To address these issues, the authors introduce CURVBENCH, a curvature-stratified audit framework. The methodology proceeds through three main stages:

A. Geometric Characterization

The framework treats graphs as finite metric spaces and quantifies their intrinsic geometry using two primary metrics derived from discrete sectional curvature:

Mean Curvature ( $\bar{\kappa}(G)$ ): Measures the average signed curvature of the graph, indicating whether the local geometry is generally Euclidean (near-zero), spherical (positive), or hyperbolic (negative).
Curvature Skewness ( $\gamma_\kappa(G)$ ): Captures the asymmetry of the curvature distribution. This is critical for identifying datasets where a small subset of nodes or edges carries disproportionately large geometric signals (e.g., tail-driven geometry in table-derived graphs), even if the mean curvature is near zero.

Based on these metrics, datasets are partitioned into three regimes:

Near-zero: $|\bar{\kappa}(G)| < 0.01$ and $|\gamma_\kappa(G)| < 0.5$ .
Positive: Characterized by positive mean curvature or positive skewness.
Negative: Characterized by negative mean curvature or negative skewness.

B. Experimental Setup

Datasets: The benchmark evaluates 14 diverse datasets, including 9 natural graphs (e.g., Cora, Citeseer, Airport, Telecom) and 5 table-derived graphs (e.g., Carcinogenesis, Hepatitis, F1).
Models: 18 representative models are evaluated, categorized by their geometric inductive biases:
- Euclidean/Geometry-agnostic: MLP, GCN, GAT, GraphSAGE, PCNet.
- Hyperbolic: HGNN, HGCN, HAT, HyboNet.
- Flexible/Mixed-Curvature: QGCN, CUSP.
- Adaptive Riemannian: GraphMoRE.
- Graph Foundation Models (GFMs): GCOPE, MDGPT, MDGFM, SAMGPT, GraphGluing, SA2GFM.
Tasks: Node Classification and Link Prediction.
Evaluation Protocol: Instead of a single global leaderboard, performance is analyzed via regime-conditioned diagnostics. The authors utilize rank consistency metrics (Spearman, Kendall, Jaccard overlap) to compare model rankings within and across curvature regimes.

C. Theoretical Grounding

The paper provides theoretical justification for the approach:

Curvature Mismatch: It is proven that metric distortion in an embedding is lower-bounded by the mismatch in curvature residuals. If a model's embedding space does not align with the graph's intrinsic curvature, systematic metric distortion is inevitable.
Regime-Conditioned Orders: The authors demonstrate that the gap between within-regime and cross-regime ranking stability serves as a direct estimate of preference variation. If curvature affects model behavior, rankings will be stable within a regime but unstable across regimes.

3. Key Results

A. Curvature Regimes Induce Coherent Partial Orders

Model rankings are highly stable within a homogeneous geometric regime but shift significantly across regimes.

Consistency: Within-regime Spearman correlation for top-3 rankings is 0.539, compared to only 0.036 across regimes.
Reorganization of Inductive Biases:
- Near-zero Regime: Euclidean methods (GraphSAGE, PCNet) dominate.
- Positive Regime: Euclidean methods remain competitive, but MLP becomes highly predictive, suggesting node attributes outweigh relational structure in compact/clustered graphs.
- Negative Regime: Mixed and adaptive Riemannian methods (GraphMoRE, QGCN) dominate, while Euclidean methods drop to 0% of top-3 positions. This indicates Euclidean models are not inherently weak but are regime-limited.

B. Graph Foundation Models (GFMs) are Geometry-Conditioned

GFMs do not eliminate the need for curvature-aware evaluation; they introduce new geometry-conditioned inductive biases.

1-Shot Performance: Rankings remain curvature-conditioned. Token-based models (MDGPT, MDGFM) excel on near-zero graphs, while structure-alignment models (GraphGluing) dominate positive regimes.
Label Elasticity: Increasing supervision from 1-shot to 5-shot yields high gains for near-zero graphs (label-limited) but diminishing returns for positive and negative graphs (geometry-limited).
Feasibility: Several GFMs encounter Out-Of-Memory (OOM) errors on specific datasets (e.g., Telecom), highlighting that feasibility is a manifestation of transfer difficulty, not just implementation detail.

C. Table-Derived Graphs Reveal Tail-Driven Geometry

Table-derived graphs often exhibit near-zero mean curvature but extreme positive skewness.

Specialist vs. Robustness: Models like HAT act as "high-variance specialists," excelling on datasets with pronounced curvature tails (e.g., F1, PTE) but failing on others. In contrast, Euclidean baselines like GraphSAGE provide more stable, robust performance across these heterogeneous datasets.
Metric Necessity: Relying solely on mean curvature obscures these specialist–robustness trade-offs; both mean and skewness are required to explain performance.

D. Efficiency Profiles

Geometry-aware modeling introduces distinct efficiency profiles. While Euclidean baselines are computationally lightweight, adaptive and manifold-heavy methods (e.g., GraphMoRE, HAT) incur substantial training and inference overheads. Notably, training cost and inference cost do not always correlate (e.g., HyboNet has moderate training cost but low inference cost, whereas GraphMoRE is expensive in both).

4. Contributions

Framework Development: A curvature-stratified framework based on mean curvature and skewness to categorize graph and tabular datasets into geometrically meaningful regimes.
Empirical Evidence: Evaluation of 18 methods revealing that performance is fundamentally geometry-dependent rather than universally transferable, with model rankings flipping across regimes.
Methodological Formalization: A regime-stratified methodology that replaces flat leaderboards with geometry-aware comparisons, offering more reliable and interpretable insights for model selection.
Resource Release: Release of all code, curvature-stratified dataset splits, and diagnostic tools to support reproducible assessment.

5. Significance and Claims

The paper claims that reducing model capability to a single aggregate score is no longer sufficient for the current research landscape. The significance of this work lies in shifting the evaluation paradigm from identifying a "globally best" model to determining which inductive biases are most effective under specific geometric conditions.

The authors argue that:

Reliability: Reliable assessment must transcend simple accuracy to incorporate label elasticity, coverage, specialist–robustness trade-offs, and computational feasibility.
Future Trajectories: The field should move toward stratified, coverage-aware diagnostics that reveal the specific conditions under which a model succeeds. Furthermore, future relational learning systems should transition from fixed inductive biases toward geometry-adaptive architectures capable of inferring or composing appropriate biases directly from the data.

By making benchmark design structurally aware, the authors aim to better characterize the fundamental strengths and limitations of the next generation of graph and foundation models.