cs.LGNov 10, 2026

Graph Label Alignment: A Diagnostic Atlas for Graph Classification

Authors: Neelam Akula, Varun Shiralkar, Murat Kantarcioglu, Baris Coskunuzer

Organizations: Department of Mathematical Sciences, University of Texas at Dallas, Richardson, TX 75080 · Department of Computer Science, University of Texas at Dallas, Richardson, TX 75080 · Department of Computer Science, Virginia Tech, Blacksburg, VA 24061

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.

Figures & tables

Appendix figures & tables23 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. Graph Alignment for Benchmarking Graph Neural Networks and Learning Positional Encodings

    May 19, 2025Adrien Lagesse, Marc LelargeGraph Neural NetworksSynthetic Benchmark Generation

  2. Chaining 2-FWL GNNs for Combinatorial Graph Alignment

    Oct 3, 2025Marc LelargeGraph MatchingHigher-Order GNNs

  3. The Role of Node Features in Graph Pooling

    May 7, 2026Jan von Pichowski, Alžbeta Hrabošová, Ingo Scholtes +1Graph Neural NetworksGraph Pooling