Graph Label Alignment: A Diagnostic Atlas for Graph Classification

Neelam Akula, Varun Shiralkar, Murat Kantarcioglu, Baris CoskunuzerarXiv 2026 · arXiv

TL;DR

This paper introduces Graph Label Alignment (GLA), a lightweight diagnostic framework that reveals whether graph classification benchmarks are solved by genuine relational reasoning or by simple "shortcuts" in the data. By measuring how much label signal is accessible from structure alone or features alone, the authors show that standard Graph Neural Networks (GNNs) often struggle precisely when the signal depends on complex interactions that their global pooling layers tend to wash out.

What Problem Does This Paper Address?

Graph classification benchmarks are notoriously inconsistent. Some datasets are easily conquered by simple baselines, while others remain stubbornly difficult for even the most advanced GNNs and Graph Transformers. This leads to a fundamental ambiguity: when a model performs well, is it actually "reasoning" about the graph's relational structure, or is it just exploiting coarse signals—like the fact that certain labels are associated with larger graphs or specific node feature distributions?

The authors argue that we lack a data-centric way to categorize these benchmarks. Without understanding where the "label signal" lives—whether in the structural marginals, the feature marginals, or their higher-order interactions—it is difficult to know if we are making progress on relational learning or just building better shortcut-detectors.

Methods

The authors propose two probe-based scores that quantify label accessibility without training a full graph encoder:

  1. Structural Label Alignment (SLA): Measures how well labels can be predicted using only structural summaries (topological Betti profiles, spectral eigenvalues, and global graph statistics). Node features are discarded.
  2. Feature Label Alignment (FLA): Measures predictability when edges are removed, using only the pooled multiset of node features (e.g., the feature centroid).

These scores are computed using simple, shallow classifiers (Logistic Regression and RBF-SVM). By plotting datasets on the SLA–FLA plane, researchers can visualize a "diagnostic atlas" of benchmark difficulty.

To explore the limits of standard models, the authors also introduce Twins tasks. These are synthetic datasets where structural and feature marginals are identical across classes, but the coupling between them differs (e.g., in Class A, "red" nodes are hubs; in Class B, "blue" nodes are hubs). This isolates interaction-dependent signal, effectively blinding models that rely on simple shortcuts.

Datasets

The study evaluates a wide range of benchmarks:

  • Real-world Benchmarks: 19 datasets including molecular graphs (AIDS, MOLHIV, BACE), bioinformatics (PROTEINS, ENZYMES), and social networks (REDDIT, IMDB).
  • Vision-to-Graph: MNIST and CIFAR-10 converted into graph formats.
  • Synthetic Sweeps: A controlled grid of datasets where structural and feature separation are independently dialed.
  • Interaction Stress Tests: The newly introduced Twins tasks and Heterophilic Ego-graphs (derived from node classification tasks like Texas and Cornell).

Key Insights and Ideas

  • The "Shortcut" Reality: High performance on many popular benchmarks is strongly correlated with high SLA or FLA. If a label is easily predictable from a "marginal" view, standard pooled GNNs will find it.
  • The Correspondence Bottleneck: Standard GNN pipelines typically use global pooling (like mean or sum) to create graph-level embeddings. The authors show this creates a bottleneck: it discards the specific mapping of which features are at which structural positions.
  • The Failure of Transformers: Surprisingly, even powerful Graph Transformers like GPS fail on the "Twins" tasks, remaining near random guessing. This suggests that the issue isn't just the encoder's expressivity, but the permutation-invariant readout layers used in graph classification.
  • Diagnostic Triage: The authors define $\Delta_{graph}$—the accuracy a GNN adds over the best simple probe. For many molecular benchmarks, $\Delta_{graph}$ is near zero, suggesting these datasets might not be the best for testing "relational reasoning."
Real benchmarks in the alignment plane (GCN). Datasets with high SLA/FLA (top right) are "easy," while those in the bottom left are where standard models struggle.

Key Results

  • Strong Correlation: Across 19 real benchmarks, the average of SLA and FLA (AlignAvg) has a 0.944 Pearson correlation with GCN test accuracy. This confirms that marginal accessibility is a dominant driver of benchmark performance.
  • Predicting Performance: Using only SLA and FLA, the authors could predict GCN accuracy on unseen datasets with a mean absolute error of only 6.30 points.
  • Twins Failure: On balanced binary Twins tasks, where marginal shortcuts are eliminated by design, pooled GNNs and GPS achieved ~50% accuracy (random chance), proving they cannot capture role-feature coupling.
Figure 2: Synthetic alignment sweep (GCN& GPS). Each point is a synthetic dataset positioned by its SLA and FLA, colored by GCN(left) and GPS (right) accuracy. The dashed line marks an illustrative 80% accuracy contour. Other backbones are shown in Appendix Figure 5.

Limitations and Future Work

  • Summary Dependence: The diagnostic is only as good as the structural and feature summaries used. While the authors tested several, richer summaries might reveal signal that their current probes miss.
  • In-Distribution Focus: The current correlations are based on random splits. The authors note that alignment scores tend to weaken under distribution shifts (like OGB's scaffold splits), suggesting that "shortcuts" are often the first things to break when the data distribution changes.
  • Future Directions: The "correspondence bottleneck" identified here points toward a need for new types of readout layers or training objectives that explicitly preserve the relationship between node roles and their features.

Summary updated

Abstract

Graph classification benchmarks vary widely in difficulty: some are solved by simple pooled baselines, while others remain challenging for GNNs and graph transformers. We take a data-centric view and ask whether benchmark success is driven by genuine structure--feature reasoning or by label signal already accessible from restricted marginal views. We introduce graph label alignment, a lightweight diagnostic that measures label accessibility through two supervised probes computed without training a graph encoder: structural label alignment (SLA), based on permutation-invariant topological and spectral summaries, and feature label alignment (FLA), based on pooled node features with edges removed. Across real graph classification benchmarks and multiple pooled backbones, the resulting SLA--FLA plane strongly organizes test accuracy, with low-alignment datasets forming a consistent regime where standard pooled pipelines struggle. To probe what lies beyond marginal accessibility, we introduce controlled interaction-dominated stress tests, including heterophilic ego-graphs and synthetic Twins tasks whose structural and feature marginals are matched across classes but whose role--feature couplings differ. These results show that high alignment explains much of easy benchmark performance, while low alignment reveals regimes where success requires preserving structure--feature correspondence beyond standard pooled representations.
BibTeX
@misc{akula2026graph,
  author = {Neelam Akula and Varun Shiralkar and Murat Kantarcioglu and Baris Coskunuzer},
  title = {{Graph Label Alignment: A Diagnostic Atlas for Graph Classification}},
  year = {2026},
  eprint = {2611.14760},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.14760},
}
Figure