betaFeedback

WorksComputer Science

Graph Label Alignment: A Diagnostic Atlas for Graph Classification

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.

Introduction

Strong performance on a graph classification benchmark can mean two very different things: a model may exploit relational structure, or it may exploit label signal already accessible from coarse marginal views of the data. This ambiguity is increasingly important because graph classification benchmarks vary widely in difficulty: many are handled well by simple pooled baselines, while others challenge expressive GNNs and graph transformers [9, 7]. This motivates a data-centric question: Where does the label signal live in a graph classification dataset, and which parts of it are accessible to standard pooled graph models?

We address this question through a supervised restricted-view diagnostic for graph classification. The goal is to separate marginal label accessibility from interaction-dependent signal: high marginal accessibility can explain why many benchmarks are easy for standard pooled pipelines, while low marginal accessibility highlights regimes where success requires preserving structure–feature correspondence beyond coarse pooled summaries. If labels are predictable from structure alone or from the multiset of node features alone, then strong accuracy may largely reflect this accessibility rather than richer relational reasoning [LCS⁺24, CWSR25]. Conversely, when both restricted views are weak, remaining signal must come from higher-order structure–feature interactions, information not captured by the reference probes, or noise. We instantiate this low-marginal regime through controlled Twins tasks, where structural and feature shortcuts are eliminated by design.

Graph label alignment. Given a dataset D={(Gi,Xi,yi)}i=1N\mathcal{D} = \{(G_i, X_i, y_i)\}_{i=1}^{N}, we introduce two probe-based scores that quantify marginal label accessibility without training a graph encoder. Structural label alignment (SLA) measures label predictability from a fixed, permutation-invariant structural descriptor of GiG_i alone, based on topological and spectral summaries. Feature label alignment (FLA) measures label predictability when edges are discarded and only the multiset of node features in XiX_i is retained. Together, (SLA~,FLA~)(\widetilde{\mathrm{SLA}}, \widetilde{\mathrm{FLA}}) place datasets on an interpretable graph label alignment plane, enabling benchmark comparison and helping identify when performance is likely driven by marginal accessibility versus structure–feature interaction.

A plane that organizes pooled-model performance. Across real benchmarks and pooled graph classifiers, including GCN, GraphSAGE, GAT, and GPS, datasets with higher SLA or FLA tend to yield higher accuracy, while low-alignment datasets cluster in regimes where pooled backbones generally perform worse. Architecture choice shifts absolute performance, but does not reliably remove this difficulty. We quantify the trend using Pearson correlations between alignment scores and test accuracy, and use AlignAvg=(SLA+FLA)/2\mathrm{AlignAvg} = (\mathrm{SLA} + \mathrm{FLA})/2 as a compact dataset ordering.

Controlled stress tests expose what the alignment plane misses. Real datasets confound domain, size, feature type, and class structure, so we complement them with controlled settings. A synthetic sweep independently dials structural and feature separation, validating that accuracy contours follow the alignment geometry. Heterophilic ego-graph classification provides realistic low-marginal tasks where pooled message-passing baselines achieve low accuracy, typically ∼\sim25–45%, and performance is sensitive to hop radius. Most sharply, in balanced binary and three-class Twins tasks, classes have identical structural and feature marginals but distinct role–feature couplings; pooled GNNs and GPS remain near random guessing. These results suggest a correspondence bottleneck in standard pooled graph-classification pipelines: when label signal resides in global role–feature coupling, simply changing the encoder may not preserve the information needed for discrimination.

Contributions.

  • We propose graph label alignment, a label-aware diagnostic for pooled graph classification, and define probe-based SLA and FLA scores for structure-only and feature-only restricted views.

  • We show that pooled GNN and graph transformer performance on real benchmarks is strongly organized by the SLA–FLA plane, supporting AlignAvg as a compact dataset ordering.

  • We provide backbone-specific alignment predictors and a practical decision map (Appendix § 16) that translate SLA/FLA regimes into backbone selection guidance.

  • We introduce controlled synthetic alignment sweeps and interaction-dominated stress tests, including heterophilic ego-graphs and Twins, showing that low-marginal regimes can expose a failure mode of standard pooled pipelines under role–feature coupling.

Background

Related Work

Graph classification models and benchmarks. Graph classification is a core task in graph machine learning with applications in chemistry, biology, and social systems. Most methods learn node representations and aggregate them into graph-level embeddings, typically using message-passing GNNs with global pooling, or attention-based graph transformers with structural encodings. Evaluation is commonly performed on benchmark suites such as TU and OGB graph-level datasets [16 HFR+20]. Prior work has emphasized that graph classification results can be highly sensitive to experimental protocols and that carefully tuned simple baselines can be competitive on several benchmarks [9].

Data-centric evaluation of graph classification datasets. A growing line of work asks whether popular benchmarks effectively test graph reasoning or whether they can be solved by simpler cues. [14] revisit graph classification benchmarks and propose effectiveness metrics based on performance gaps between graph-aware methods and simpler structure-only or attribute-only baselines, together with correlation-controllable synthetic datasets. [6] propose RINGS, a mode-perturbation framework that evaluates datasets through model sensitivity to structure and feature perturbations, using measures such as performance separability and mode complementarity. These works assess benchmark quality via performance gaps and perturbation sensitivity.

In contrast, our goal is not to curate benchmarks, but to provide a simple label-centric view of where predictive signal is accessible under restricted information views. We introduce two probe-based scores: structural label alignment (SLA), measuring label predictability from permutation-invariant structural summaries alone, and feature label alignment (FLA), measuring label predictability from node-feature pooling summaries when edges are discarded. Together, they define an interpretable alignment plane that separates structure-accessible, feature-accessible, and low-marginal-accessibility regimes without training full graph encoders.

Alignment between structure, features, and labels. Several works study alignment between graph structure and node features, typically for node-level learning, and use spectral criteria to guide rewiring or denoising. For example, [15] propose jointly rewiring the graph and denoising features by aligning leading spectral spaces of graph and feature matrices. Our setting differs in that we study graph-level classification and define alignment directly in terms of label predictability under restricted views, rather than structure-feature agreement itself. We use the term alignment strictly in this predictive sense.

We further use synthetic and ego-graph datasets to study regimes where labels are accessible from structure, accessible from features, or suppressed under both marginal views. The low-marginal regime is especially useful diagnostically: it can indicate noise, probe underfitting, or genuinely interaction-dependent signal. Our controlled Twins construction isolates the last case by matching structural and feature marginals across classes while varying only role-feature coupling. This lets us compare datasets and architectures on a common plane while making explicit what the alignment scores do and do not establish.

Structural & Feature Probes

We quantify label accessibility under two restricted views: structure-only and feature-only. For each view, we construct lightweight, permutation-invariant summary representations that serve as standardized probes across datasets. These probes are intentionally simple and are used to define controlled diagnostics for SLA and FLA (§ 3); they are not designed to maximize predictive performance. Implementation details are provided in Appendix § 11.

Structural summaries. We represent each graph using a combination of topological, spectral, and statistical descriptors. For topology, we compute Betti-profile summaries derived from persistent homology over a filtration (e.g., node degree) [8, 3] (Appendix § 15.§ 1). For spectral structure, we include a small set of extremal eigenvalues of the normalized Laplacian and adjacency matrices. Together, these features provide compact, permutation-invariant summaries of graph structure (see Appendix § 11).

Feature-only summaries. For the feature-only view, we discard edges and treat node features as an unordered multiset. Each graph is represented by a permutation-invariant pooled descriptor; in our reference setting, we use the feature centroid. Alternative summaries are evaluated in Appendix § 11.

Graph–Label Alignment Framework

Problem Setup

We consider a graph classification dataset D={(Gi,Xi,yi)}i=1N\mathcal{D} = \{(G_i, X_i, y_i)\}_{i=1}^{N}, where Gi=(Vi,Ei)G_i = (V_i, E_i) is a graph, Xi∈R∣Vi∣×dX_i \in\mathbb{R}^{|V_i| \times d} are node features, and yi∈{1,…,C}y_i \in\{1, \ldots, C\} is a graph label. We view each sample through two restricted information views: structure-only (discard XiX_i) and feature-only (discard EiE_i), and ask how much label signal is accessible from each view via standardized, lightweight probe predictors. Throughout, we use alignment strictly to mean label predictability under a restricted view, rather than agreement between structure and features (see § 2).

Restricted-View Summary Vectors

To quantify label signal under each view, we map each graph to a fixed-dimensional summary vector. These summaries are deliberately simple and permutation-invariant: they are not intended to maximize accuracy, but to provide controlled, comparable diagnostics across datasets.

Structural view. Node features are discarded and each graph GG is represented by a Structural Summary Vector ϕstruct(G)∈R48\phi_{\mathrm{struct}}(G) \in\mathbb{R}^{48} that concatenates three families of permutation-invariant descriptors: a degree-filtration Betti profile (PH, 20 dims), a compact spectral signature from the normalized Laplacian and adjacency matrix (8 dims), and global graph statistics including size, density, degree quantiles, and clustering moments (20 dims). The vector uses no attribute information; zero-padding is applied when fewer than four nonzero eigenvalues are available. Full construction details are in Appendix § 11; component-level ablations supporting their complementarity are in Appendix § 12.§ 1.

Feature-only view. We discard edges and treat each graph as an unordered multiset of node features, and represent each graph by a Feature Summary Vector ϕfeat(G)∈Rd\phi_{\mathrm{feat}}(G) \in\mathbb{R}^{d} given by the feature centroid, ϕfeat(F)=1∣V∣∑v∈VXv\phi_{\mathrm{feat}}(F) = \frac{1}{|V|}\sum_{v \in V} X_v. Alternative feature summaries considered are reported in App. B.

Alignment Score Computation

Given summary vectors ϕ(Gi)∈{ϕstruct(Gi),ϕfeat(Gi)}\phi(G_i) \in\{\phi_{\mathrm{struct}}(G_i), \phi_{\mathrm{feat}}(G_i)\}, we estimate label accessibility using a fixed probe protocol. We train two lightweight classifiers—logistic regression and an RBF-kernel SVM—using seeded, stratified cross-validation, and define each alignment score as the average of their cross-validated accuracies.

When ϕ=ϕstruct\phi= \phi_{\mathrm{struct}}, this defines the Structural Label Alignment score SLA^\widehat{\mathrm{SLA}}, measuring how predictive graph structure alone is of the label. When ϕ=ϕfeat\phi= \phi_{\mathrm{feat}}, it defines the Feature Label Alignment score FLA^\widehat{\mathrm{FLA}}, measuring how informative the marginal node-feature distribution is when adjacency is ignored.

Both scores are operational restricted-view diagnostics, not causally isolated measures of structural or feature contributions. If node features encode structural information, as atom types do in molecular graphs where valence partly determines local topology, FLA absorbs that signal by design. Thus FLA asks “how much label signal is accessible from features alone?”, not “how much signal is causally feature-driven?” Similarly, low SLA means structure is not predictive under the chosen structural summary, not that no structural signal exists.

Probe details are in Appendix § 11.§ 3. To assess whether the reference protocol underestimates accessible signal on a given dataset, Appendix § 12.§ 2 introduces a probe sufficiency self-check that compares reference scores against an alternative five-classifier suite and flags probe-sensitive datasets.

Using Alignment in Analysis

We use (SLA^,FLA^)(\widehat{\mathrm{SLA}}, \widehat{\mathrm{FLA}}) as a two-dimensional summary of marginal label accessibility for pooled graph classification pipelines. In § 6, we visualize datasets in the SLA–FLA plane and analyze pooled-model behavior via regime-based comparisons. We also use AlignAvg=(SLA+FLA)/2\mathrm{AlignAvg} = (\mathrm{SLA} + \mathrm{FLA})/2 (when both are defined) as a one-number ordering of alignment for correlation analysis and plotting.

Two properties of this plane are worth noting upfront. First, SLA and FLA are structurally independent axes: the synthetic sweep in § 4 confirms they decouple cleanly under controlled generation, and several real datasets (e.g., MoLHIV, LETTER-HIGH, COIL-DEL) show meaningful SLA–FLA gaps. The positive correlation observed across the broader benchmark suite is an empirical property of existing collections, not a built-in property of the framework: in many current benchmarks, datasets with high marginal accessibility under one view also tend to exhibit high marginal accessibility under the other. Second, low alignment on both axes does not automatically imply interaction-driven signal: it means labels are not accessible from either marginal view, which can arise from genuine noise, from signal in higher-order structure–feature interactions, or from probe underfitting on atypical datasets (see Appendix § 12.§ 2). The distinction matters for interpretation and is addressed directly in the controlled experiments of § 5.

Synthetic Alignment Testbeds

We use controlled synthetic graph families for two purposes. First, an alignment plane sweep spans a range of SLA and FLA values and tests whether pooled-model performance follows the (SLA,FLA)(\mathrm{SLA}, \mathrm{FLA}) geometry under controlled variation. Second, the Twins construction removes marginal shortcuts and isolates interaction-only signal: prediction is possible only if a model captures how node features are arranged relative to graph structure.

Alignment Plane Sweep

Goal. The sweep instantiates three regimes: structure-only (high SLA, low FLA), feature-only (high FLA, low SLA), and jointly aligned (high SLA, high FLA). By varying structural and feature signal independently, we obtain datasets whose location in the alignment plane can be controlled while other factors are fixed.

Base graph generator. For each graph with label y∈{1,…,K}y \in\{1,\ldots,K\}, with K=3K = 3, structure is generated from a label-controlled mixture. Let s∈[0,1]s \in[0,1] be the structural separation parameter. With probability ss, the graph is sampled from a class-specific generator GyG_y; with probability 1−s1-s, it is sampled from a shared label-independent generator G0G_0.

The class-specific generators are drawn from canonical random graph families such as Erdős–Rényi, Barabási–Albert, Watts–Strogatz, and two-block stochastic block models, with class-dependent parameters chosen to induce structural differences. The shared generator G0G_0 is an Erdős–Rényi model with fixed edge probability. We add label-agnostic edge rewiring noise by rewiring a fixed fraction prewirep_{\mathrm{rewire}} of edges uniformly at random, and sample graph sizes from a fixed distribution so expected node counts are matched across classes. Thus s≈0s \approx0 produces structure-agnostic datasets, while s≈1s \approx1 produces structure-informative datasets. Full parameter values are in Appendix § 14.

Feature generator. Node features are generated independently of graph size. For each node vv, we sample xv∼N(0,σ2I)x_v \sim\mathcal{N}(0,\sigma^2 I) with fixed σ2\sigma^2. Let f∈[0,1]f \in[0,1] be the feature separation parameter. With probability ff, all nodes in a graph of label yy receive a class-dependent mean shift μy\mu_y; otherwise features remain label-independent noise. The class means are sampled once, normalized, and scaled by a fixed magnitude. Thus increasing ff makes pooled feature summaries more label-predictive, while f≈0f \approx0 matches marginal feature distributions across classes.

Regime instantiations. We sweep (s,f)(s,f) over a fixed grid to cover the SLA–FLA plane. This yields three families: Structure-only (vary ss with f=0f = 0), Feature-only (vary ff with s=0s = 0), and Jointly aligned (set s=fs = f). Grid size and graphs per cell are given in Appendix § 14.

Twins Construction

Goal. Twins eliminate structure-only and feature-only shortcuts. By construction, all classes share the same graph distribution and the same multiset of node feature types, so SLA and FLA are near chance. Label signal comes only from how feature types are coupled to structural roles.

Per-graph labeled variants. For each base graph G=(V,E)G = (V,E) sampled from a fixed-parameter SBM [11], we generate multiple labeled variants that share the same edge set EE and the same balanced multiset of feature types. Each variant contains exactly n/3n/3 nodes of each prototype type, so the marginal feature distribution is matched across labels. Variants differ only in the assignment of feature prototypes to nodes, forcing successful models to detect role–feature coupling rather than structure-only or feature-only signal.

Role scores and quantile bins. To induce structured feature placement, we compute a scalar role score s(v)s(v) for each node and partition nodes into three equal-sized bins by tertiles. We consider four scoring functions, detailed in Appendix § 14: Linear, Radial, PageRank, and Eigen. Feature prototypes (μ1,μ2,μ3)(\mu_1,\mu_2,\mu_3) are then assigned to the bins in class-specific orders with additive Gaussian noise, while preserving identical prototype counts across classes.

Classes. Label 0 corresponds to a random assignment obtained by uniformly permuting prototype labels across nodes while preserving the n/3n/3–n/3n/3–n/3n/3 counts. Labels 1, 2, . . . correspond to structured assignments that align prototype types with role-score bins. We consider binary Twins (random vs. one structured assignment) and three-class Twins (random vs. two structured assignments). Since both structure and feature marginals are matched, any gain over chance must come from preserving global role–feature correspondence.

Experiments

Overview and evaluation protocol. Our goal is to characterize how pooled graph classifiers behave as a function of graph–label alignment, and to separate two questions: (i) whether marginal label accessibility (SLA/FLA) organizes performance on standard graph benchmarks, and (ii) what fails when labels depend primarily on structure–feature interaction that permutation-invariant readouts may wash out. We compute SLA/FLA once per dataset using the restricted-view probes from § 3; these scores are model-agnostic and require no GNN training. To answer (i), we use general benchmarks spanning diverse domains and naturally covering a wide range of SLA/FLA: (1a) real graph classification datasets, and (1b) a synthetic alignment-plane sweep, where we can dial structural and feature signal continuously while holding other factors fixed. To answer (ii), we use interaction-driven stress tests designed to suppress marginal shortcuts and stress coupling: (2a) heterophilic node-to-graph ego networks (Appendix § 13), which provide realistic interaction-dominated instances, and (2b) synthetic Twins, which match structure and feature marginals across classes by construction and isolate role–feature coupling as the only discriminative signal.

For real benchmarks and ego-graphs, we follow the standard dataset splits and evaluation protocols; for synthetic datasets, we use balanced classes with a 60/20/20 train/validation/test split (Section A). Our code is available at the link: https://github.com/avp-neelam/GraphLabelAlignment

Real benchmark suite (1a). We use a diverse set of graph classification datasets spanning molecules, proteins, social networks, and image-to-graph constructions (TU-style and OGB molecular graphs). Some datasets have node features (SLA and FLA); others are featureless (FLA undefined), in which case we report only SLA and omit AlignAvg. Dataset statistics, and feature availability are in Table 4.

GroupDataset#GraphsAv.NodesAv.Edges# Feat.#Classes
MOLECULARAIDS200015.6932.39422
BACE151334.0973.7292
BZR40535.7576.72562
COX246741.2286.89382
DD1178284.321431.32892
ENZYMES60032.60124.27216
FRANKENSTEIN433716.9035.757802
MOLHIV4112725.5154.9492
MOLTOX21783118.5738.5992
MUTAG18817.9339.5972
NCI1411029.8764.60372
PROTEINS111339.06145.6342
PROTEINS_FULL111339.06145.63322
VISIONCIFAR-1045000117.65941.18310
COIL-DEL390021.54108.472100
LETTER-HIGH22504.679.00215
MNIST5500070.56564.50110
SYNTHETICCOLORS-31050061.31182.05511
SYNTHIE40095.00345.86154
SOCIALCOLLAB500074.494914.4303
IMDB-B100019.77193.0602
IMDB-M150013.00131.8703
REDDIT-BINARY2000429.63995.5102
REDDIT-5K4999508.521189.7505

Table 4. Dataset statistics across molecular, computer vision, synthetic, and social graph benchmarks.

Synthetic alignment sweep (1b). To control alignment, we generate synthetic datasets by sweeping structural and feature separation (s,f)(s,f) as in § 4, covering structure-only, feature-only, and jointly-aligned regimes. We evaluate the same architectures and tuning protocol as on real benchmarks and compute SLA/FLA using the restricted-view probes.

Heterophilic ego-networks (2a). To model interaction-driven classification, we convert heterophilic node benchmarks into ego-graph tasks: for each node, we extract the induced kk-hop ego-graph and use the center-node label as the graph label. We include a center-node indicator feature in all ego-graph experiments. Construction and preprocessing are in Appendix Section D.

Twin synthetic datasets (2b). We use Twins (§ 4) to remove structure-only and feature-only shortcuts while preserving the interaction-only label signal. All classes share the same SBM distribution and feature multiset; labels differ only by role-based feature assignment (Linear, Radial, PageRank, Eigen) versus random permutation. We evaluate binary and three-class settings. Unless noted, each dataset has 1000 graphs with 100 nodes; details are in Appendix § 14.

Models and baselines. We evaluate pooled graph classifiers: GCN, GraphSAGE (SAGE), GAT, and GPS. Each model produces node embeddings and applies a permutation-invariant readout, mean pooling by default, to obtain graph-level embeddings for classification; readout variants and hyperparameters are in Appendix Section A. For Twins, we also evaluate GCN+DiffPool to test whether hierarchical pooling mitigates the interaction-only failure mode.

Results

Alignment plane on real benchmarks

We first test whether our restricted-view alignment scores organize the performance of standard pooled graph classifiers on real graph classification benchmarks. For each dataset, we report baseline accuracies for GCN, SAGE, GAT, and GPS together with the corresponding alignment scores (SLA and FLA when node features are available; SLA only for featureless datasets). (Implementation details for backbones, pooled readout, and the hyperparameter grid are in Appendix Section A. Full dataset statistics are in Appendix Table 4.)

Key observation: a clear trend in the SLA–FLA plane. Across featureful benchmarks, datasets with higher SLA and/or higher FLA tend to achieve higher pooled-model accuracy, while low-alignment datasets cluster in a region where all pooled architectures struggle. This trend is visually apparent in Figure 1, which places each dataset in the SLA–FLA plane and colors points by GCN accuracy. Importantly, the qualitative organization is not driven by a particular backbone: corresponding plots for SAGE, GAT, and GPS show the same large-scale pattern (Appendix Figure 3). Throughout, we treat this as a descriptive organization of benchmark difficulty, rather than a causal claim about model behavior.

Figure 1. Real benchmarks in the alignment plane (GCN). Each point is a real graph classification dataset positioned by its SLA and FLA scores, colored by GCN accuracy. Other backbones are shown in Appendix Fig. 3.

Quantifying the trend via correlations. To quantify how well alignment predicts pooled accuracy beyond the qualitative plane plots, we compute Pearson correlations between each alignment score and model accuracy on the subset of real benchmarks where FLA (and thus AlignAvg) is defined.

All four backbones show strong positive correlations with both SLA and FLA: labels that are more accessible from either restricted view tend to yield better pooled-model performance. Moreover, AlignAvg = (SLA + FLA)/2 is consistently among the most correlated summaries, providing a compact ordering for reporting and visualization. Since alignment scores are computed without training any GNN, these correlations serve as an architecture-agnostic diagnostic, suggesting that marginal label accessibility explains a substantial part of benchmark difficulty for these pooled models. Exact summary constructions, probe protocols, and complexity details are given in Appendix § 11.

Robustness of the alignment plane. Appendix § 12 tests the design choices behind the scores. Removing structural blocks keeps SLA rank correlation with the full descriptor at 0.968 or above, and a 12-dimensional subset without persistent homology reaches 0.988. Richer feature summaries raise FLA on some low-alignment datasets, but keep rank correlation with centroid FLA at 0.934 or above. Across summaries and probes, no dataset moves directly between the high/high and low/low regimes, and correlations with accuracy keep their pattern across all four backbones. A stronger five-model probe suite flags LETTER-HIGH as the main probe-sensitive case. Appendix § 17 reports compute cost, leave-one-dataset-out prediction of GCN accuracy (Pearson r=0.917r = 0.917), a benchmark triage score, and scaffold splits, under which our correlations should be read as an in-distribution diagnostic.

Synthetic sweep validates the alignment plane

Real datasets vary simultaneously in many confounding factors (domain, size, feature type, and class structure), so we next test the alignment story in a controlled environment. We generate a grid of synthetic datasets by sweeping structural and feature separation parameters as described in § 4, thereby spanning structure-only, feature-only, and jointly-aligned regimes while holding other factors fixed. (Full generation details and how SLA/FLA track the control parameters are provided in Appendix § 14, with full sweep tables reported at the end of the appendix.)

BinaryTriclass
LinearRadialPageRankEigenLin & RadLin & PRLin & EigenRad & PRRad & EigenPR & Eigen
FLA24.7324.7324.7324.7312.0212.0212.0212.0212.0212.02
SLA27.2727.2727.2727.2714.1114.1114.1114.1114.1114.11
GCN46.9246.9246.1749.8330.6730.4431.0632.4431.3332.00
SAGE49.5048.5048.6749.5033.1132.3931.5632.0033.0033.11
GAT47.9245.5844.0046.8331.7828.5631.0031.0631.3931.33
GPS48.5049.6749.2549.3332.0632.5032.9432.6732.8332.22
DiffPool43.0045.2545.7546.2527.7830.2227.5629.4428.7228.94

Table 3. Twin setting Accuracy results (%) for binary (random assignment vs. one structured assignment) and triclass tasks (random assignment plus two structured assignments).

Key observation: accuracy contours follow the alignment geometry. Figure 2 visualizes the synthetic sweep in the alignment plane for GCN. The dashed curve marks an illustrative boundary for “good” performance (80% accuracy): datasets above this contour concentrate in high-alignment regions of the plane, while low-alignment regions remain challenging. As in the real benchmarks, the same qualitative organization is observed for other backbones (Appendix Figure 5), indicating that the alignment plane captures a stable performance geometry rather than an artifact of a single model.

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.

Twin datasets expose a pooling limitation

The preceding results show that pooled performance is largely organized by marginal label accessibility. We now ask whether low alignment can also reflect a genuine interaction-dependent signal rather than noise. Twins answer this in a controlled setting: by construction, marginal structural and feature shortcuts are removed, while role–feature coupling remains discriminative.

Synthetic Twins isolate an interaction-only failure mode. We study Twins (§ 4), where all classes share the same SBM structure distribution and the same multiset of node feature types. Balanced binary and three-class variants differ only in how feature types are assigned to nodes according to a role score (Linear, Radial, PageRank, Eigen) versus a random permutation. Thus structure-only and feature-only probes are non-informative by design, and any gain over chance requires preserving global role–feature correspondence. Construction details, role-score definitions, and alignment suppression checks are given in Appendix Sections E.5 to E.8.

The result is clear: across all role-score variants and both binary and three-class settings, pooled GNNs and GPS remain near random guessing (50% binary, 33% three-class), with the failure most pronounced in the three-class setting. To test whether hierarchical pooling mitigates this effect, we also evaluate GCN+DiffPool; it remains near chance across Twins variants. These results suggest a correspondence bottleneck in standard pooled graph-classification pipelines: progress in this regime likely requires readouts or objectives that preserve the relation between node roles and feature assignments.

Heterophilic ego-graphs as realistic interaction-driven instances. We convert heterophilic node-classification graphs into ego-graph classification tasks (Appendix § 13) as a noisier but more realistic corroboration. These datasets are interaction-dominated: the class signal can depend on the arrangement of features around the center node rather than on global structure or pooled feature composition alone. Results are summarized in Table 15 and analyzed in Appendix § 13.§ 1. Pooled message-passing baselines achieve low accuracy throughout, typically ∼25\sim25–45%45\%, consistent with the Twins finding. GPS is a consistent outlier on WebKB at small kk, achieving up to 60% on Cornell at k=1k=1 despite AlignAvg⁡≈25\operatorname{AlignAvg} \approx25. We discuss this boundary case in Appendix § 13.§ 1, where global attention and center-node information may capture signal not reflected by marginal alignment scores.

DatasetkkGCNSAGEGATGPSSLAFLAAlignAvg
TEXAS131.05±10.8442.11±6.8635.79±15.4942.11±6.8633.7843.1638.47
TEXAS235.26±4.8836.32±6.3225.79±13.8736.32±6.0951.8161.9656.89
TEXAS330.00±4.5935.79±7.3722.63±12.7437.89±4.8862.6761.8462.26
CORNELL136.32±3.8735.26±12.8535.26±6.3660.00±7.8817.7631.3424.55
CORNELL227.89±4.8825.79±1.9722.11±3.5758.95±2.6829.1332.2930.71
CORNELL327.37±6.7833.68±9.4720.53±3.0758.95±1.2928.8932.1830.54
WISCONSIN139.22±3.2841.57±4.5432.16±4.9052.16±6.9727.8644.7236.29
WISCONSIN248.24±10.4937.65±8.3633.33±6.4453.73±2.0037.9945.4541.72
WISCONSIN339.61±5.0241.96±10.2734.90±8.7250.98±6.2034.9346.0840.51
ACTOR123.37±0.4527.30±0.6921.89±0.4927.20±1.1418.2024.1221.16
ACTOR222.76±0.7325.08±0.1819.99±0.7425.75±0.3619.8120.0519.93
ACTOR320.80±1.0323.95±1.2318.71±1.5726.22±1.299.9919.8714.93

Table 15. Pooled-model accuracy (%) tracked against the alignment plane for heterophilic ego-graph datasets at varying hop sizes kk. AlignAvg summarizes alignment as (SLA + FLA)/2.

Together, Twins and ego-graphs show that low alignment need not mean absence of signal: it can mark regimes where the discriminative information lies in structure–feature correspondence that standard pooled pipelines do not reliably preserve.

Discussion and takeaways

Overall, our experiments support the following takeaways. Alignment is a practical organizer and diagnostic of pooled-model learnability. On real benchmarks, pooled-model accuracy is strongly structured by the SLA–FLA plane, and the same geometry appears under controlled synthetic sweeps where structural and feature signal can be dialed independently. This makes alignment a simple, architecture-agnostic way to diagnose where label signal is accessible from restricted views.

Low alignment is not fixed by swapping encoders. When both marginal views are weak, all pooled architectures degrade substantially and can approach near-chance behavior, suggesting that encoder choice alone is insufficient in interaction-dominated regimes; the bottleneck can lie in what standard pooled pipelines preserve.

Interaction-only tasks reveal a correspondence bottleneck. Heterophilic ego-graphs and Twins instantiate regimes where labels depend on how features are arranged relative to structure. In Twins, where marginal shortcuts are eliminated by design, pooled models remain near chance, indicating that permutation-invariant readout can discard global coupling signatures. This motivates alignment-aware evaluation and, in interaction-dominated settings, objectives or readouts that better preserve role-level structure–feature coupling beyond standard pooling. (For an optional backbone-aware alignment predictor and a practical decision map tying SLA/FLA regimes to backbone choice, see Appendix § 16.)

Conclusion

This work takes a data-centric view of graph classification by studying where label signal is accessible before training a graph encoder. Through graph label alignment, we show a consistent pattern across real benchmarks, heterophilic ego-graphs, and controlled synthetic families: when labels are accessible from structure or pooled features, standard pooled pipelines tend to perform well, whereas low alignment marks regimes where changing the encoder alone yields limited gains. Our interaction-focused stress tests further reveal a correspondence bottleneck in standard pooled pipelines, where global feature-role coupling can be lost despite expressive message passing. More broadly, these results suggest that graph benchmark analysis should distinguish marginal shortcuts from interaction-dependent signal. Future directions include readouts and objectives that preserve structure–feature correspondence, alignment-aware benchmark design, and extensions of this diagnostic view to link prediction, retrieval, and transfer.

Acknowledgments and Disclosure of Funding

This work was partially supported by National Science Foundation under grant DMS-2229417, OAC-2115094, CNS-2331424, ITE-2452833, Simons Foundation under grant SFM-21269, ARL/Army Research Office awards W911NF-24-1-0202 and W911NF-24-2-0114, and Virginia Commonwealth Cyber Initiative grants. The authors acknowledge the Texas Advanced Computing Center (TACC) at UT Austin for providing computational resources that have contributed to the research results reported within this paper.

Appendix

Appendix roadmap. Section A gives reproducibility details, plus dataset metadata and per-backbone SLA–FLA plots.

Section B defines SLA/FLA summaries, probes, and complexity.

Section C reports structural and feature ablations, a probe sufficiency self-check, and regime and seed stability.

Section D covers ego-graphs (construction and extra results).

Section E details synthetics (sweep, coverage, Twins).

Section F reviews signatures (topology and spectrum).

Section G reports GLA (predictor, decision map, backbone rules), with full sweep tables at the end.

Section H reports screening use (compute cost, out-of-sample prediction, Δgraph\Delta_{\mathrm{graph}}) and scaffold splits.

Further Experimental Details

Implementation Details. We evaluated performance across two families of GNNs: (i) message-passing GNNs (GCN, GraphSAGE, and GAT); and (ii) a hybrid local-global GPS architecture. All models operate on node features, producing predictions via global pooling.

Message-passing GNNs. GCN [13], GraphSAGE [12], and GAT [21] use a unified ll-layer message-passing architecture with hidden dimension hh. GCN and SAGE layers map using mean aggregation. For GAT, hidden layers use multi-head attention with HH heads, yielding intermediate representation with dimension hh. Each convolution is followed by batch normalization, a nonlinearity (ReLU for GCN/SAGE, ELU for GAT), and dropout with rate pp. Node embeddings are aggregated using global mean pooling and passed through a linear classifier after the final layer.

GPS. GPS architecture [18] combines local message passing and global attention within each layer. Input features are first projected to dimension hh via a linear map. Each of the ll layers consist of a GraphSAGE convolution as the local MPNN component together with multi-head global attention with HH heads. Outputs are normalized, passed through ReLU nonlinearity, and dropout with rate pp. Residual connections are applied at each layer, updating node states. The final embeddings are pooled at the graph level and mapped to class logits using a linear classifier.

Grid Search for Hyperparameters. For real and heterophilic ego-graph datasets we run a grid search over hyperparameters: l=2,3l = 2, 3 layers; h=32,64,128h = 32, 64, 128 hidden dimension; H=1,2,4,8H = 1, 2, 4, 8 multi-head attention (when relevant); p=0.3,0.5p = 0.3, 0.5 dropout; and learning rate of 1×10−31 \times10^{-3} with early stopping on validation

Structural and Feature Label Alignment

This appendix specifies the exact construction and implementation details of the Structural Summary Vectors and Feature Summary Vectors used to compute Structure Label Alignment (SLA) and Feature Label Alignment (FLA), along with their computational complexity.

Let D={(Gi,Xi,yi)}i=1N\mathcal{D} = \{(G_i, X_i, y_i)\}_{i=1}^{N} denote a graph classification dataset, where each graph Gi=(Vi,Ei)G_i = (V_i, E_i) has node features Xi∈R∣Vi∣×dX_i \in\mathbb{R}^{|V_i| \times d} and class label yiy_i.

Structural Summary Vectors

For each graph G=(V,E)G = (V, E), we construct a fixed-dimensional Structural Summary Vector ϕstruct(G)∈R48\phi_{\mathrm{struct}}(G) \in\mathbb{R}^{48} by concatenating topological, spectral, and global structural statistics. Formally:

ϕstruct(G)=[β0,1(G)∥λ(G)∥μ(G)∥g(G)]\phi_{\mathrm{struct}}(G) = [\beta_{0,1}(G) \mathbin\Vert\lambda(G) \mathbin\Vert\mu(G) \mathbin\Vert g(G)]

where β0,1(G)\beta_{0,1}(G) acts as the topological summary; λ(G)\lambda(G) and μ(G)\mu(G) the spectral summary; and g(G)g(G) contains global structural statistics.

Topological Summary. For each graph we utilize sublevel-filtration based PH with degree as the filtration function, on ten quantiled bins, and compute the Betti-0 and Betti-1 numbers. To improve computational complexity we compute β0\beta_0 as the number of connected components and β1\beta_1 by Euler characteristic. The resulting concatenation

β0,1(G)=(β0(G1),β0(G2),…,β0(G10),β1(G1),β1(G2),…,β1(G10))∈R20\beta_{0,1}(G) = \left(\beta_0(G^1), \beta_0(G^2), \ldots, \beta_0(G^{10}), \beta_1(G^1), \beta_1(G^2), \ldots, \beta_1(G^{10})\right) \in\mathbb{R}^{20}

is the defined topological summary included in ϕstruct(G)\phi_{\mathrm{struct}}(G).

Spectral Summary. Let AA be the adjacency matrix of GG and L=I−D−1/2AD−1/2L = I - D^{-1/2}AD^{-1/2} the normalized Laplacian. To compute λ(G)∈R4\lambda(G) \in\mathbb{R}^{4} we find the four smallest (nonzero) eigenvalues of LL, similarly μ(G)∈R4\mu(G) \in\mathbb{R}^{4} are the four largest eigenvalues of AA. To maintain fixed length summary vectors across graphs, if a graph has fewer than four eigenvalues all available values are used and the remaining length is padded with zeros [4].

Global Summary. The global summary vector g(G)∈R20g(G) \in\mathbb{R}^{20} contains number of nodes, number of edges, graph density, and degree quantiles at 5%, 25%, 50%, 75%, and 95%. Additionally, we report mean, standard deviation, skewness, and excess kurtosis for node-level degree, clustering coefficient, and triangle count.

Feature Summary Vectors

References

  1. [1]Dashti Ali et al. A survey of vectorization methods in topological data analysis. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2023.DOI
  2. [3]Baris Coskunuzer and Cüneyt Gürcan Akçora. Topological methods in machine learning: A tutorial for practitioners. arXiv preprint arXiv:2409.02901, 2024.arxiv.org/abs/2409.02901
  3. [4]Fan RK Chung. Spectral graph theory, volume 92. American Mathematical Soc., 1997.
  4. [5]Corinna Cortes and Vladimir Vapnik. Support-vector networks. Machine learning, 20(3):273–297, 1995.DOI
  5. [6][CWSR25] Corinna Coupette, Jeremy Wayland, Emily Simons, and Bastian Rieck. No metric to rule them all: Toward principled evaluations of graph-learning datasets. In ICML, 2025.arxiv.org/abs/2502.02379
  6. [7][DJL+23] Vijay Prakash Dwivedi, Chaitanya K Joshi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. Journal of Machine Learning Research, 24(43):1–48, 2023.
  7. [8][DW22] Tamal Krishna Dey and Yusu Wang. Computational Topology for Data Analysis. Cambridge University Press, 2022.
  8. [9][EPBM20] Federico Errica, Marco Podda, Davide Bacciu, and Alessio Micheli. A fair comparison of graph neural networks for graph classification. In ICLR, 2020.arxiv.org/abs/1912.09893
  9. [11][HLL83] Paul W Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. Stochastic block-models: First steps. Social networks, 5(2):109–137, 1983.
  10. [12][HYL17] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. NeurIPS, 30, 2017.arxiv.org/abs/1706.02216
  11. [13][KW17] Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. ICLR, 2017.arxiv.org/abs/1609.02907
  12. [14][LCS+24] Zhengdao Li, Yong Cao, Kefan Shuai, Yiming Miao, and Kai Hwang. Rethinking the effectiveness of graph classification datasets in benchmarks for assessing GNNs. In IJCAI, 2024.
  13. [15][LSD25] Jonas Linkerhägner, Cheng Shi, and Ivan Dokmanić. Joint graph rewiring and feature denoising via spectral resonance. In ICLR, 2025.
  14. [16][MKB+20] Christopher Morris, Nils M. Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: A collection of benchmark datasets for learning with graphs. In ICML 2020 Workshop on Graph Representation Learning and Beyond (GRL+ 2020), 2020.
  15. [17][PBMW99] Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. The pagerank citation ranking: Bringing order to the web. Technical report, Stanford infolab, 1999.
  16. [18][R+22] Ladislav Rampášek et al. Recipe for a general, powerful, scalable graph transformer. In NeurIPS, 2022.arxiv.org/abs/2205.12454
  17. [19][Sei83] Stephen B Seidman. Network structure and minimum degree. Social networks, 5(3):269–287, 1983.DOI
  18. [20][Spi11] Daniel A. Spielman. Spectral graph theory and its applications. http://cs-www.cs.yale.edu/homes/~spielman/spectral/, 2011. Tutorial presented at IEEE FOCS 2011.
  19. [21][VCC+18] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. ICLR, 2018.arxiv.org/abs/1710.10903

Paper details

vlnc:W_b2hseum7
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents